This assignment expands the functional subset of Scheme to include higher-order functions (those that take other functions as inputs or yield them as outputs). In addition, it looks at efficient means of expressing recursive relationships via tail-recursion and a very efficient data structure: binary trees.
For this assignment,
you should type (and test!) your programs in a file named
hw2.scm.
You should submit your file in the usual way at the CS 60
submissions site. Keep in mind
that you may submit multple times -- only the final submission before
the deadline will be graded.
Design and formatting account for roughly a quarter of the credit for each function or program you complete. A description of the formatting and comments appropriate for CS 60 assignments is listed on the HW1 description. It is included here again for reference.
Design, here, means algorithm design, that is, how you break a problem
down into smaller pieces and then compose those pieces into an overall solution.
Large, convoluted functions are difficult to understand (and debug!). Use
small, clear functions with lots of small helper functions, as necessary.
Formatting includes coding style: clean and clear structure, meaningful
variable and function names, ample use of spacing, and indenting that reflects
code structure.
As for commenting,
in each assignment we ask you to include
Function names
Be sure that you name your functions as specified in each problem -- this
helps enormously with the grading! Helper
functions may have any names appropriate for their operation.
Testing
Again, we will provide several tests in the problem descriptions.
These example are not complete, however -- designing and using
your own tests is crucial to testing all of the cases your code
needs to handle. You will need tester.scm
in your directory in order to use the test and tester
summary.
review of recursion
For this problem
define a function, named subbag, taking two list arguments,
L1 and L2. Each of these lists is to be considered a
mathematical "bag" of elements, that is, a set in which duplicates are
allowed. Then, subbag should return #t in the case that
all of the elements of L1 appear in L2 at least
as many times as they appear in L1. Otherwise, this
function should return #f. Here are some examples:
(test (subbag '(1 2 2 3) '(1 2 2 3)) #t)
(test (subbag '(1 2 2 3) '(1 2 3)) #f)
(test (subbag '(1 2 2 3) '(2 1 3 2 2 1 1)) #t)
(test (subbag '("h" "m" "c") '("c" "h" "a" "r" "m")) #t)
Write (tail-log2 N), a tail-recursive version
of the log2 function we considered in class on Th, 9/4:
(define (tail-log2 N)
(test (tail-log2 2) 1)
(test (tail-log2 3) 1)
(test (tail-log2 4) 2)
(test (tail-log2 10) 3)
(test (tail-log2 1000) 9)
Write a tail-recursive function (tail-fib N) that takes in a positive
integer N and outputs the Nth fibbonacci number, i.e.,
the appropriate term of the series in which the first and second elements are 1 and subsequent elements are the sum of the previous two:
1 1 2 3 5 8 13 21 ...
(test (tail-fib 8) 21)
Write a tail-recursive function (tail-range low high)
where low and high are two integers. The output
should be the empty list if low ≥ high. Otherwise,
the output should be the list (low low+1 low+2 ... high-1),
For example,
(test (tail-range 3 3) ())
(test (tail-range 40 50) '(40 41 42 43 44 45 46 47 48 49))
For the next three functions (two problems), you should not use any explicit recursion at all in their implementation. Rather, your solutions should rely on Scheme's higher-order functions, i.e., functions that take other functions as input or yield them as output. Thus, constructs such as map, foldr, filter, and lambda will be the most important building blocks.
This problem asks you to write two functions. First, implement
(superreverse L), whose functionality is almost identical what it was in hw1. In this case,
however, you may assume that the input L will be a list that
contains zero or more lists (and only lists) as elements. (Remember to use
no raw recursive calls in these three functions' implementation.)
(test (superreverse '( () (1 2 3) ((c b) a))) '( () (3 2 1) (a (c b))))
Second, implement (indivisible k L), where k is a positive
integer and L is a list of positive integers. Then, indivisible should return a list of the elements of L that are not evenly divisible by k. They should appear in the same order as they do in L. For instance,
(test (indivisible 3 '( 2 3 4 5 6 7 8 9 10 )) '(2 4 5 7 8 10))
This problem is worth 20 points.
This problem is the same as last week's extra credit -- except that for this assignment,
you need to use higher-order functions (and lambda) rather than raw recursion in solving it. And it's
not extra credit!
Define a function best-word as follows:
(define (best-word rack wordList)
For example,
(best-word "academy" (list "ace" "ade" "cad" "cay" "day")) ==> ("cay" 8)
(best-word "appler" (list "peal" "peel" "ape" "paper")) ==> ("paper" 9)
(best-word "paler" (list "peal" "peel" "ape" "paper")) ==> ("peal" 6)
Note: You will likely want to use score-letter and score-word from the
last assignment in your solution to best-word. Although score-letter was probably not recursive,
score-word probably was ~ be sure to re-implement it using higher-order functions for the purposes of
this problem. Also, you'll want to copy this definition into your file:
;; scrabble-tile-bag
;;
;; letter tile scores and counts from the game of Scrabble
;; the counts aren't needed (but don't hurt)
;; obtained from http://en.wikipedia.org/wiki/Image:Scrabble_tiles_en.jpg
;;
(define scrabble-tile-bag
'((#\a 1 9) (#\b 3 2) (#\c 3 2) (#\d 2 4) (#\e 1 12)
(#\f 4 2) (#\g 2 3) (#\h 4 2) (#\i 1 9) (#\j 8 1)
(#\k 5 1) (#\l 1 4) (#\m 3 2) (#\n 1 6) (#\o 1 8)
(#\p 3 2) (#\q 10 1)(#\r 1 6) (#\s 1 4) (#\t 1 6)
(#\u 1 4) (#\v 4 2) (#\w 4 2) (#\x 8 1) (#\y 4 2)
(#\z 10 1) (#\_ 0 2)) ) ;; end define scrabble-tile-bag
Hint: planning out your strategy for this problem before diving in to the coding is a good thing! In particular, you will want to define and use a number of helper-functions to keep your definition of best-word simple and elegant. In fact, earlier parts of this assignment may be of use... . You'll want to keep your helper-functions short, as well! As a guide, consider the lotto example we looked at in class on Tuesday.
The remainder of the problems in this assignment ask you to
implement functions that manipulate binary search trees in a variety
of ways. Recall that the representation of a binary search tree that we
are using is either null? (the empty list) or a list of
three elements: first the root of the tree; second, the left-hand subtree;
and third, the right-hand subtree. Also, all elements of a left-hand subtree
are strictly less than the value of the root. All elements of a right-hand
subtree are strictly greater than the root.
Finally, no value may be repeated in the tree.
For example,
(define BT1 '( 42 (20 (7 (1 () ()) (8 () ())) (31 () (41 () ()))) (100 (60 () ()) ()) ))
Note: you may - and are encouraged - to use raw recursion for these problems. Higher-order
functions are OK, too! It's your choice.
First, write a function (height BT) whose input is a binary
search tree and whose output
is the length of the longest path from the root of BT to any one of its leaves, i.e.,
the height of the binary search tree.
For instance,
(test (height BT1) 4) ;; using the tree defined above
Next, write a function (find-min BT) whose input is a
non-empty binary search tree and whose output
is the value of the smallest node in that binary search tree.
For instance,
(test (find-min BT1) 1) ;; using the tree defined above
Write a function (flatten-tree BT) whose input is any binary search tree and whose output
is a list of all of the elements, in order, of the input. In a comment with your code,
explain what the big-O running time of your flatten-tree function is in the worst case.
For example,
(test (flatten-tree BT1) '(1 7 8 20 31 41 42 60 100)) ;; using the tree defined above
The final binary search tree exercise this week (except the extra credit) is to write a function (delete value BT) whose inputs are a numeric argument, value, and a binary search tree, BT. If value does not appear in BT, then a binary search tree identical to BT is returned. On the other hand, if value does appear in BT, then a tree similar to BT is returned, except with the node value deleted.
If the value to delete has zero children, it is straightforward to delete.
Similarly, if it has only one non-empty child, it is replaced by that child.
When the value to be deleted has two non-empty
children, however,
it is not clear which of its children (or descendants) are to take its place. For the
sake of this problem,
the node that should take value's place should be the
smallest value in BT that is larger than value.
Here are two examples:
(test (delete 20 BT1) '(42 (31 (7 (1 () ()) (8 () ())) (41 () ())) (100 (60 () ()) ())))
(test (delete 42 BT1) '(60 (20 (7 (1 () ()) (8 () ())) (31 () (41 () ()))) (100 () ())))
> (twenty-questions)
Is it bigger than a breadbox? (y/n) y
Is it a computer scientist? (y/n) n
What was it? a chemist
What's a question distinguishing a computer scientist and a chemist? Do you titrate?
And what's the answer for a chemist? (y/n) y
Play again? (y/n) y
Is it bigger than a breadbox? (y/n) y
Does you titrate? (y/n) y
Is it a chemist? (y/n) n
What was it? Wally Wart
What's a question distinguishing a chemist and Wally Wart? Is it concrete?
And what's the answer for Wally Wart? (y/n) y
Play again? (y/n) y
Is it bigger than a breadbox? (y/n) y
Do you titrate? (y/n) y
Is it concrete? (y/n) y
Is it Wally Wart? (y/n) y
I got it!
Play again? (y/n) n
The idea here is to start with the following question and two items:
(define initialTree '("Is it bigger than a breadbox?" "spam" "a computer scientist"))
From there, the goal is to build
Hints:
Here is a function you may find useful. It demonstrates how to
grab a line of user input and then use the resulting value (which will
be a string). The second is a more general-purpose question-asking function:
(define (askyn Q) ;; asks a yes/no question Q and returns #t or #f
(begin
(display Q)
(display " (y/n) ")
(if (equal? "y" (read-line))
#t
#f)
))
(define (ask Q)
(begin
(display Q)
(read-line)))
Strategy:
The binary tree used in this game is slightly different than the numeric
ones used earlier in the HW. In this case, the leaves are not empty, but
contain possible objects; internal nodes contain questions. After the first round
in the example above, the tree's structure would be
("Is it bigger than a breadbox?" "spam" ("Do you titrate?" "a computer scientist" "a chemist"))
A crucial facet of the game is that (tq-once tree) must return
a valid twenty-questions tree from all of the different conditional branches it handles.
That returned tree will be augmented by an additional question and an additional object if
the previous run did not guess the object correctly. If it did guess the object
correctly, the original tree will be returned.
The tq-continuer function will want to give a name to the value of that new tree
(using let is one way to do this). It will then ask the user whether they would
like to continue and use that new tree as appropriate.
As with any large functional program, the key is to break up the tasks into manageable
chunks, write functions that handle those pieces, and then compose them into a solution.
Write a number of helper functions that will keep your code succinct and straightforward.
Good luck!