CSE 413 Spring 2000

Assignment 1 -- Scheme Warmup

Due: at the beginning of lecture on Wednesday, April 5, 2000

All of these problems should be done without using side effects (i.e. redefining variables or using set!).  Be sure to test your functions on various cases, including empty lists, simple lists with no sublists, complex lists, etc.

Part I.  Written (paper) problems

  1. Draw a boxes and arrows diagram to show the result of executing the following definitions.
    2. (define a '(1 3))
    (define b (cons '(4 5) a))
    (define c (append a a))
  2. Assuming that the following definitions are executed in this order,
    3. (define a '(1 2 3 4))
    (define b '(1 2 3))
    (define c (cons a '(a)))
    (define e (reverse a))
    (define f 33)
    (define g 34)
    show the value that results from evaluating each of the following expressions.  If something is wrong, say so.  (Obviously you could trivialize the problem by typing these expressions into a Scheme interpreter and transcribing the results.  Feel free to use a computer to check your answers, but be sure you can answer the questions without using a machine.) 

    1. b
    2. (car e)
    3. (cadr e)
    4. (cons (car b) a)
    5. c
    6. (> 'f 'g)
    7. (list f a)
    8. (equal? (cdr e) b)
    9. (eq? (car b) (car a))
    10. (+ (* f 2) 55 11)
    11. (pair? (car c))
    12. (length c)

Part II. Programming Problems.

Write and test Scheme functions to solve the following problems.  You should save all of your function definitions in a single source file.  In DrScheme you can use  File->Save definitions as  to create a file that contains your function definitions.  The normal convention is to use the extension .scm to end Scheme file names.

You will be asked to turn in both the function definitions themselves and a printout showing a Scheme session where you test the functions.  Your test cases should be sufficient to show that the functions work correctly (i.e., works on both empty and non-empty lists, etc.)  In DrScheme, you can use File->Print Interactions to print the session transcript.

  1. Define a function make-pal that takes one list as an argument and returns a palindrome created from that list as follows:
    2. (make-pal '(s t e p o n)) => (s t e p o n n o p e t s)
    (make-pal '(n e v e r o d)) => (n e v e r o d d o r e v e n)
  2. Define a function even-numbers that takes a simple list of numbers as input and returns a copy of that list containing only the even numbers from the original list.  For example:
    3. (even-numbers '(1 2 3 4))  => (2 4)
    (even-numbers '(1 17 192 -76)) => (192 -76)
  3. Define a function multiply-numbers that takes a simple list as input and returns the product of all of the numbers in the list. List elements that are not numbers should be ignored. For example:
    4. (multiply-numbers '(1 2 3 f 4)) => 24
    (multiply-numbers '(14 () (100) 2.5)) => 35.0
    (multiply-numbers '(fred 1/2 "says hello" 3/7)) => 3/14
  4. Define a function list-length that returns the number of top-level elements of the list that is its argument  (i.e., create your own implementation of the standard Scheme function length).   Do NOT use the Scheme function length in your implementation. NOTE: your function should treat the empty list in the same way that length treats it.. For example:
    5. (list-length '(1 2 3 4 () ))  => 5
    (list-length '((A B) C (D (E F))) => 3
  5. Define a function deep-length that returns the number of elements in the list that is its argument.  If elements of the list are themselves lists, they should be examined recursively and their elements added to the total length.   Do NOT use the Scheme function length in your implementation.  NOTE: In deep-length, an empty list will be examined recursively and thus will not contribute to the length of the list.  Example:
    6. (deep-length '(1 2 3 4 ())) => 4
    (deep-length '((A B) C (D (E F))) => 6

What to Hand In

For this (as well as most) assignments, you should turn in your work both electronically over the web and on paper.

Electronic Submission

Turn in a copy of your Scheme source file from part II using this turnin form.

Paper Submission

Hand in the following:

  1. Written answers to the problems from Part I.
  2. A printout of the receipt you received from the online submission of the file containing your Scheme functions from Part II.  This listing will include a copy of your Scheme code.
  3. A printout showing the transcript of the Scheme session demonstrating the results produced by your functions for suitable test cases.  This should contain enough to show that your functions work, but no more than necessary to do that. (Don't worry if there are some minor typos in the transcript - just draw a line through anything we should ignore.)