CSE 413 Winter 2001

Assignment 1 -- Scheme Warmup

Due: Electronic turnin due no later than 10:00 pm, Tuesday, January 16, 2001.  Paper receipt and written problems due at the beginning of lecture on Wednesday, January 17.

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 x '(3 5))
    (define y (cons 1 x))
    (define z (list 'a 'b x))
    (define w (cons x y))
  2. Assuming that the following definitions are executed in this order,
    3. (define a '(dog cow pig))
    (define b (reverse a))
    (define c (cons a b))
    (define d (append a b))
    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. (car b)
    2. (cadr b)
    3. c
    4. (cadar c)
    5. (cons (cdr a) b)
    6. (equal? a b)
    7. (equal? d (reverse d))
    8. (equal? (car c) a)
    9. (eq? (car c) a)
    10. (eq? d (reverse d))
    11. (cons '(car a) b)
    12. (pair? a)

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 should 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. The greatest common divisor of two positive integers x and y has the following mathematical properties:

            gcd(x, y) = gcd(x, y-x) = gcd(x-y, y)
            gcd    (x, y) = gcd(x, x+y) = gcd(x+y, y)
            gcd    (x, x) = x
            gcd    (x, y) = gcd(y, x)
            gcd    (x, 0) = gcd(0, x) = x

    Use (some subset of) these properties to write a recursive function gcd(x,y) that yields the greatest common divisor of positive integers x and y.
     
  2. Define a function 2nd-last that returns the 2nd last element of the list that is its argument, or returns a null list if there is no such element.
    3. (2nd-last '(x y (b c) (d (e f))) => (b c)
    (2nd-last '(ha)) => ()
  3. Define a function sum-digits that returns the sum of all the digits of the integers in a list.  Embedded lists and things that are not integers should be ignored.  For example:
    4. (sum-digits '(23 3 44 9)) => 25
    (sum-digits '(3 fooled-you 41 (30))) => 8

    Hint: feel free to define an additional, auxiliary function if it makes your life simpler.

  4. Define a function depth that returns the depth of a list.  The depth of an empty list is 0, a list containing no sublists is 1, etc. Examples::
    5. (depth '()) => 0
    (depth '(a b c)) => 1
    (depth '((((a))))) => 4
    (depth '(a (b (c) d) (e ((f) g))) => 4
  5. In lecture we demonstrated that a naive implementation of a function that calculates Fibonocci numbers is grossly inefficient (exponential time): 
    (define (fib  n)
   (cond ((= n 0) 0)
          (= n 1) 1)
          (else (+ (fib (- n 1)) (fib (- n 2))))
    Write a new function fibt that calculates the nth Fibonocci number in linear time.  Remember, you may not use assignments (set!) or global variables (other than global function names, of course).

    Hint: Tail recursion.  You may also find an it useful to define an auxiliary function.

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 printed copy of the receipt you received when you electronically turn in 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. Part of your grade will be determined by the quality of the test cases you use for this.  (Don't worry if there are some minor typos in the transcript - just draw a line through anything we should ignore.)