CS 217 Programming Assignment: Scheme B

CS 217: Programming Languages

Programming Assignment 2: Scheme B

Assigned on Wednesday, 1/18.
Due by 11:55 PM on Wednesday, 2/2.

Submission instructions: If you are working in a team, one member of the team should use hsp to turn in an entire directory called scheme_team_b that contains the files memoization.scm, nestedsets.scm, and sieve.scm. Make sure that both team members are credited in program comments. For the individual assignment at the bottom of this web page, each student should individually use hsp to submit a directory called scheme_indiv_b that contains the file mergesort.scm.

Note that these problems vary significantly in amount of difficulty. You should start early and look at each problem.

You should use recursion, and not iteration, on each of these problems.

For all parts of this assignment, you may not use side-effects.

Team Problems

Memoization

(a) Write a function that computes the following recursive function (written here in traditional mathematical notation):

f(0) = 1
f(-1) = 0
f(-2) = 0
f(-3) = 0
f(m) = f(m-1) + f(m-2) + f(m-3) - f(m-4) for m >= 1

What are the values of f(28), f(29), and f(30)? How long does it take to compute each of these values? Use the Scheme function time to measure how long an evaluation takes. (Example: (time (f 0)))

(b) In a functional language without side-effects or assignments, the value of a function always depends solely on its arguments. This allows us to use an optimization known as memoizing. You can pass a list of previous answers (a "memo") as a parameter that the function can use to speed its work. Write an Scheme function called fastF that is a solution to part (a) using memoizing. How long does it take now to compute your answer?

Nested Sets

In the last assignment, you wrote code to represent sets as lists. In general sets can contain other sets. Revisit the sets problem from the last assignment and construct new code to allow sets to contain other sets. For example:

(set-equal? '(1 (2 3)) '((3 2) 1)) ---> #t
(set-equal? '(1 2 3) '((3 2) 1)) ---> #f
(set-equal? '(1 2 3) '((1 2 3))) ---> #f
(union '(1 (2) 3) '(3 2 1)) ---> (1 2 3 (2))
(union '((1 2 3)) '((3 4 5))) ---> ((1 2 3) (3 4 5))
(union '((1 2 3)) '((3 2 1))) ---> ((1 2 3))
(intersect '((1 2 3)) '((3 2 1))) ---> ((1 2 3))
(intersect '((1 2 3)) '((4 5 6))) ---> ()
(intersect '((1) (2) (3)) '((2) (3) (4))) ---> ((2) (3))

Make sure to test additional cases of sets containing sets containing sets, etc.

Sieve of Eratosthenes

(a) Recall that a lazy list is a useful structure for representing a long or even infinite list. A lazy list is represented in Scheme with a cons cell, where the "car" contains a data item and the "cdr" contains a function which returns the rest of the lazy list. If the function returns #f, the list is empty. Write the following functions that create and manipulate lazy lists:

(seq first last)
This function takes two integers and returns an integer lazy list containing the sequence of values first, first+1, ... , last. This is just a renaming of the function gen-lazy-list from the previous assignment, so this one should be pretty easy.
(infSeq first)
This function takes an integer and returns an integer lazy list containing the infinite sequence of values first,first+1, ....
(firstN lazyList n)
This function takes a lazy list and an integer and returns an ordinary Scheme list containing the first n values in the lazyList. If the lazy list contains fewer than n values, then all the values in the lazy list are returned. You may assume that n is an integer greater than or equal to 1. If the lazy list is empty, return an empty Scheme list.
(nth lazyList n)
This function takes a lazy list and an integer and returns the n-th value in the lazyList (counting from 1). If the lazyList contains fewer than n values, then #f is returned.
(filterMultiples lazyList n)
This function returns a new lazy list that has n and all integer multiples of n removed from lazyList. For example, a non-lazy list version of filterMultiples would behave as follows:
(filterMultiples '(2 3 4 5 6) 2) ---> (3 5) (filterMultiples '(3 4 5 6 7 8) 3) ---> (4 5 7 8)

(b) A wide variety of techniques have been devised to compute prime numbers (numbers evenly divisible only by themselves and 1). One of the oldest techniques is the "Sieve of Eratosthenes." This technique is remarkably simple.

You start with the infinite list L = 2, 3, 4, 5, .... The head of this list (2) is a prime. If you filter out all values that are a multiple of 2, you get the list 3, 5, 7, 9, .... The head of this list (3) is a prime. Moreover, if you filter out all values that are a multiple of 3, you get the list 5, 7, 11, 13, 17, .... Repeating the process, you repeatedly take the head of the resulting list as the next prime, and then filter from this list all multiples of the head value.

You are to write an function (primes) that computes a lazy list containing all prime numbers, starting at 2, using the "Sieve of Eratosthenes." To test your function, evaluate (firstN (primes) 10). You should get (2 3 5 7 11 13 17 19 23 29). Try (nth (primes) 20). You should get 71. (This computation may take a few seconds, and do several garbage collections, as there is a lot of recursion going on.)

(Hint: Create a recursive function (sieve lazyList) that returns a new lazy list. The car of this lazy list should indicate the current value, as usual. The cdr should be a function that calls sieve again appropriately.)

Individual Problem

Mergesort

(a) Assume that we have a list L of integers. Define a function (listify L) that divides L into one or more sublists so that each sublist contains integers in non-decreasing (sorted) order. That is if v1 and v2 are adjacent in L and v1 <= v2 then v1 and v2 are adjacent in the same sublist. However, if v1 > v2 then v1 ends one sublist and v2 begins the next sublist. For example.

(listify '(3 5 1 8 9 2 1 0)) ---> ((3 5) (1 8 9) (2) (1) (0))
(listify '(1 2 3 4 5 6)) ---> ((1 2 3 4 5 6))
(listify '(5 4 3 2 1)) ---> ((5) (4) (3) (2) (1))

(b) If the output of listify contains a single sublist, then we know the input list L was in sorted order. Otherwise, we can implement a merge-sort-like sorting algorithm as follows. Take the first two sublists produced by listify and merge them into a single sorted list. Then take the next two sublists and merge them. Repeat until all sublists are considered. (The last sublist is copied unchanged if it has no partner to merge with). If only one sublist remains, we are done. Otherwise, we repeat the process, merging sublists pairwise. At each stage, the number of sublists is cut in half. For example,

((3 5) (1 8 9) (2) (1) (0)) is reduced to
(1 3 5 8 9) (1 2) (0)) and then to
((1 1 2 3 5 8 9) (0)) and finally to
((0 1 1 2 3 5 8 9)).

Implement (merge-sort L), which sorts the values in L using listify as a subroutine. The function merge-sort should accept a list of integers, and return a list of integers in order. For example:

(merge-sort '(3 5 1 8 9 2 1 0)) ---> (0 1 1 2 3 5 8 9)

(c) It is sometimes the case that a sorted list should contain no duplicate values. Modify your implementation of merge-sort so that if it sees two duplicate values it immediately returns the pair (duplicate.val) instead of the sorted list. duplicate is a fixed symbol; val is the duplicate value that was seen in L. Hence (duplicate.17) would indicate that 17 was duplicated in L.

Note that you should not check for duplicates after the sort is done, or as a preprocessing step before the sort has started. Duplicate checking should be integral to your implementation of listify and the merge component of your merge sort. You should use call/cc to implement the exception mechanism you will need to return a duplicate value.

You should only turn in the code you write for part (c) if you succeed. Otherwise, turn in your code for parts (a) and (b). Indicate in program comments what level of functionality you were able to achieve.

Many thanks to Prof. Charles Fischer at University of Wisconsin-Madison.