CSE 413 Spring 2011

Assignment 1 -- Scheme Warmup

All of these problems must be done without using side effects (i.e. redefining variables or using set!) and by using recursion instead of iteration constructs like do.  Be sure to test your functions on various cases, including empty lists, simple lists with no sublists, complex lists, etc.

Some of the problems can be answered by just typing expressions into a Scheme interpreter and transcribing the results. Feel free to use DrRacket to check your results, but, even though you might get the points, you won't learn what you need if you don't actually do the exercise.

Part I.  Written problems

    (define lst '(a b c))
    (define another '(x (y)))
    (define q1 (list lst another))
    (define q2 (cons lst another))

(b) What are the values of q1 and q2 if these are printed?

    (define lst '(p q r))
    (define more '((a b) c))
    (define app (append lst more))
    (define rev (reverse more))

For each of the following, give the value that results from evaluating the given expression.

(a) (cdr lst)

(b) (cddr lst)

(c) (cadr more)

(d) app

(e) rev

(f) (cons more rev)

Part II. Programming Problems.

Write and test Scheme functions to solve the following problems. In some cases you may find it useful to write additional helper functions besides just the functions requested. You should save all of your function definitions in a single source file named hw1.scm.  In DrRacket you can use  File->Save definitions as...  to create a file that contains your function definitions.

You may assume that all arguments have appropriate types (numbers, lists, tree nodes, etc.) and appropriate values (for example, if you are asked to compute something like n!, you can assume the argument will not be negative). You do not need to add explicit checks for these error cases.

1. The number of possible combinations (subsets) of k things taken from a set of n items is given by the formula C(n,k) = n! / (k! (n-k)!). (where ! is the factorial function) Write a function (comb n k) to compute C(n,k). You may use any recursive implementation of factorial that you like.
   

2. Write a function zip that takes two lists as arguments and returns a single list whose elements are taken alternatively from the original lists. For example, (zip '(a b c) '(x y z)) should evaluate to (a x b y c z). If the lists have different lengths, the remaining unpaired elements of the longer list should appear at the end, e.g., (zip '(1 2) '(w x y z)) should evaluate to (1 w 2 x y z).
   

3. Write a function unzip that takes a list as an argument and returns a list containing two lists that have alternating elements from the original list. For example, (unzip '(a b c d e f)) should evaluate to ((a c e) (b d f)). If the original list has an odd number of elements, the extra element at the end may appear at the end of either of the resulting lists.
   

4. If a list contains multiple copies of the same element in succession, the list can often be stored more compactly using run length encoding, in which the repeated element is given just once, preceded by the number of times it is repeated. Write a function expand that takes a list of elements and frequencies and expands them into a simple list. For example, the result of (expand '(a (3 b) (3 a) b (2 c) (3 a)) should be (a b b b a a a b c c a a a).
   

5. A binary tree can be represented as a list in many ways. One way is to represent each node in the tree as a list of three items containing the node value and left and right subtrees, with the empty list () being used to represent an empty tree or subtree. For example, () is an empty tree, (1 () ()) is a single node containing the value 1 and empty left and right subtrees, and (1 (2 () ()) (3 () ())) is a tree with root 1, a left subtree containing the value 2, and a right subtree with the value 3.

   To make it easier to work with data structures in Scheme, one convention is to define simple functions to construct and access elements of the data structure. For a binary tree, we can define the constructor (node value left right) to be (list value left right). Nothing changes underneath, but we can then use this function when we construct list nodes, instead of using list, to make the intended use clearer to the reader.

   1. Write functions value, left, and right that return respectively the node value, left subtree and right subtree from a tree node as defined above. (Hint: these are simple operations like cadr.) Use these functions in the rest of this problem.
   2. Write a function (size tree) that returns the number of non-null nodes in the given tree.
   3. Write a function (contains item tree) that returns true if item appears somewhere in the tree, otherwise false. Use equal? to compare items.
   4. Write a function (leaves tree) that returns a list of the values in the leaves of the tree in order from left to right. For example, in the second example tree above, the result of leaves would be the list (2 3).
   5. Write a function (isBST tree) that returns true if the tree is a Binary Search Tree and false otherwise. You may assume the tree given as an argument contains only numbers as values.

   Note that the values stored in the tree nodes can be any Scheme expression, not just numbers or symbols, unless the problem states otherwise.

What to Hand In

Turn in a file containing your answers to the questions from Part I, your hw1.scm source file for part II, and a transcript file demonstrating the results of your functions.

For the problems in part I you can use any common file format including plain text (if you are a fan of ASCII art), Word, or pdf. You can also submit a scanned document of a handwritten solution if that is convenient, as long as it is clear and legible.

For part II, turn in the hw1.scm source file and a file containing the transcript of a 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.) To save the transcript of the DrRacket interactions window to a file, use File > Save Other... > Save Interactions as Text... .