Assigned on Wednesday, 1/7.
Due by 5 PM on Wednesday, 1/21.
Use hsp to turn in an entire directory called scheme that contains the files problem1.scm, problem2.scm, problem3.scm, problem4.scm, and problem5.scm. If you need to resubmit your homework, resubmit the entire directory with a version number. For example, if I need to resubmit my scheme directory, I would name it scheme2 (for version 2).
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.
Write Scheme functions that implement integer binary search trees. A non-empty binary search tree can be represented as a list of three entries. The first entry is a node's value (an integer), the middle is the node's left subtree, and the last is a node's right subtree. Non-empty left and right subtrees are themselves lists of three elements. An empty tree is represented as an empty list. For example, the list
(5 () ())
represents a tree whose only node is the leaf 5. The list
(5 (3 () (4 () ()) ) ())
represents the tree whose root node is 5 and has only one child, a left child, 3: this left child has only one child, a right child, 4. In a binary search tree it is always the case that values in the left subtree are less than the root's value, and values in the right subtree are greater than the root's value. You may assume that a binary search tree that is given to you will never have duplicate entries, but you will need to make sure when inserting a new entry that it is not a duplicate.
For all parts of this question, you may not use side-effects (e.g. set!).
Write the following functions:
(null-bst)
Return an empty tree.
(null-bst? bst)
Return true (#t) if bst is empty, and
false (#f) otherwise.
(entry bst)
(left bst)
(right bst)
These functions return the node, left subtree, and right subtree,
respectively, of bst. If bst is empty or if
bst does not contain three entries where the last two are
lists, return #f.
(make-bst elt left right)
This function creates a new tree whose root node is elt,
left subtree is left, and right subtree is
right. You chould check that elt is in fact a
number, and that left and right are either empty
lists or lists of three elements each where the last two are
lists. Return #f is the input is bad.
(preorder bst)
Print each node in bst in preorder (the root of
bst, then the left subtree in preorder, then the right
subtree in preorder). Use the Scheme function (print) to
write out each number, and use the Scheme code (write-char
#\space) to put a space between each item that you print.
(inorder bst)
Print each node in bst inorder (the left subtree inorder,
then the node, then the right subtree inorder).
(postorder bst)
Print each node in bst in postorder (the left subtree in
postorder, then the right subtree in postorder, then the
node). (Fixed on 1/13)
(insert v bst)
Create a new binary search tree identical to bst but with
integer v inserted in its proper location. Smaller values
are inserted to the left of a node, larger values to the right of a
node. If v is already in the tree, just return the original
tree without changing it. You may assume that bst and all its
subtrees are valid binary search trees.
In Scheme sets can be represented as lists. However, unlike lists, the order of values in a set is not significant. Thus both (1 2 3) and (3 2 1) represent the same set.
(a) Write a Scheme function (set-equal? S1 S2) that tests whether S1 and S2 (represented as lists) are equal. Two sets are equal if they contain exactly the same members, ignoring ordering. In this part you may assume that sets contain only atomic values (numbers, string, symbols, etc.) For example
(set-equal? '(1 2 3) '(3 2 1)) ---> #t (set-equal? '(1 2) '(3 2 1)) ---> #f (set-equal? '(susan john lyta) '(lyta john susan)) ---> #t
You may assume that no sets contain duplicate members.
(b) Two common operations on sets are union and intersection. The union of two sets is the set of all elements that appear in either set (with no repetitions). The intersection of two sets is the set of elements that appear in both sets.
Write Scheme functions (union S1 S2) and (intersect S1 S2) that implement set union and set intersection. You may again assume that set elements are always atomic, and that there are no duplicates. For example
(union '(1 2 3) '(3 2 1)) ---> (1 2 3) (union '(1 2 3) '(3 4 5)) ---> (1 2 3 4 5) (union '(a b c) '(3 2 1)) ---> (a b c 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 5 6)) ---> (2 3)
The ordering of the elements in your answer may differ from the above.
(c) In general sets can contain other sets. Extend your solution to parts (a) and (b) 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.
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) for functions that you were unable to make work in part (c). Indicate in program comments what level of functionality you were able to achieve.
(a) Write a pair of Scheme functions, (gen-list start stop) and (pair-sum? list val). The function gen-list will generate a list of consecutive integers, from start to stop. (If start > stop then the empty list is generated.) For example:
(gen-list 1 5) ---> (1 2 3 4 5)
The predicate pair-sum? tests whether any two adjacent values in numlist sum to val. For example,
(pair-sum? '(1 2 3) 3) ---> #t
since 1+2=3. Similarly,
(pair-sum? (gen-list 1 100) 1000) ---> #f
since no two adjacent integers in the range 1 to 100 can sum to 1000.
(b) An alternative to generating the entire list of numbers is to instead produce a lazy list. Consider the following example.
(define (gen-lazy-list start stop)
(if (> start stop)
#f
(cons start
(lambda () (gen-lazy-list (+ start 1) stop)))))
When called, gen-lazy-list defines a pair of values. The car is the first integer in the sequence. The cdr is a function that, when called, will return another pair. That pair consists of the next integer in the sequence plus another suspension function. When the end of the sequence is reached, the function in the cdr of the pair returns #f, indicating that no more values can be produced.
Rewrite your solution to pair-sum? as a new function called pair-sum-lazy? that takes a lazy integer sequence as defined by gen-lazy-list.
Scheme can represent numbers in a variety of forms, including integer, rational, real, and complex. Let's add a new form - English. That is, we will allow numbers to be represented as a list of symbols representing English language words corresponding to numbers. Thus 0 would be represented as (zero), 123 as (one hundred twenty three) and -456789 as (minus four hundred fifty six thousand seven hundred eighty nine).
Assume that we represent numbers (in English) using the symbols minus, zero, one, two, ..., ten, eleven, twelve, ..., nineteen, twenty, thirty, ..., ninety, hundred, thousand, million, ... For simplicity, numbers that are normally hyphenated (like twenty-three) won't be.
(a) Write a Scheme function (int->eng int-val) that converts an integer int-val into English form (that is, a list of symbols representing the number in English). Your function should handle numbers at least as large as one trillion (handling even larger numbers is fairly easy). For numbers larger than your implementation limit (of one trillion or more) you may return the integer unconverted. You may find the Scheme functions quotient, remainder, expt, and/or abs useful.
(b) Now write an inverse function (eng->int L) that converts a number in English form back to integer form. Of course it should be the case that
(eng->int (int->eng int-val)) = int-val
for all integers in the range you handle. You may assumed that this number in English is well-formed.
(c) Finally, redefine the +, -, *, and quotient functions so that they accept numbers in English form as well as integer form (you may ignore numbers in rational, real, and complex forms). You may assume that your extended operators will be called with only two operands. If both operands are in integer form, then you will return in an integer result. If one or both are in English form, then you will return a result in English form. For /, you may use truncate to convert fractional quotients to integers; that is, you need not worry about divisions that have a non-zero remainder.
The following are sample calls that you should handle:
(+ 123 456) ---> 579 (- 111111 '(ten)) ---> (one hundred eleven thousand one hundred one) (* '(two thousand fifty five) '(one million one)) ---> (two billion fifty five million two thousand fifty five) (quotient 123456789 '(three)) ---> (forty one million one hundred fifty two thousand two hundred sixty three)
Note that redefining the built in arithmetic operations is in general dangerous (but fun for our purposes!). Once you start playing with this, be aware that you may need to quit MzScheme and restart it each time that you run your code.
(a). Assume thatwe 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.