Harvey Mudd College
Computer Science 60
Assignment 2, Due Monday, September 14, by 11:59pm

Higher-order functioning

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.

Submitting your work

For this assignment, you should type (and test!) your programs in two files:


You should submit your files 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, commenting, and formatting

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.

The Problems

Part 1: To be completed individually

Problem 1:    subbag

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)
Note that subbag needs only work with elements at the "top level."


Problem 2:    tail-log2

Write (tail-log2 N), a tail-recursive version of the log2 function we considered in class on Th, 9/4: 

(define (tail-log2 N)
Recall that to be tail-recursive, tail-log2 (and/or helper functions!) should do no work after any recursive calls. tail-log2 should return the largest integer less than or equal to the log-base-2 of the input, N. N will always be a positive integer. For example, 
(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)


Problem 3:    tail-fib

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 ...
Thus, 
(test (tail-fib 8) 21)


Problem 4:    tail-range

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))

Using higher-order functions   

For the next three functions ("three" 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.


Problem 5:    superreverse and indivisible

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))


Part 2: To be completed individually or with a partner

Problem 6 and 7:    bestWord

This problem is worth 20 points.

This problem is the same as last week's extra credit, but this time it's required -- and for this assignment, you need to use higher-order functions (and lambda) rather than raw recursion in solving it. The only exception to this rule is that you may use the subbag function you wrote for problem 1, even if you implemented it recursively.  

Define a function best-word as follows: 

(define (best-word rack wordList)
where best-word takes two inputs: a string of letters rack and a list of legal strings named wordList. Then, best-word should return a list of two elements: the return value's first element should be the highest-scoring word from wordList that can be made from the letters in rack. The return value's second element should be the score of that highest-scoring word. If there is a tie, any one of the strings in the wordList with maximal score may be returned. When we test your code, we will make sure that the highest-scoring word in each test case is unique.

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 that "paper" could not be made in the third example, because the rack had only a single #\p.

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.

Trees!   

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 () ()) ()) ))
We will use binary search trees of only integers for the following three problems.

Note: you may - and are encouraged - to use raw recursion for these problems. Higher-order functions are OK, too! It's your choice.


Problem 8:    height and find-min

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


Problem 9:    flatten-tree

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


Problem 10:    delete

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 () ())))

Extra Credit

General Tree Sort  (optional.  Worth up to 15%)

One application for binary search trees is to sort elements*.  Because of the structure of the tree, with the smallest elements on the left and the largest elements on the right, it is simple and easy to sort elements using the tree: simply insert all of the elements into the tree and then read them out from left to right.  This process also
can be very fast (though your running time analysis below will explore this idea).

* Actually, sorting is more often done using a similar data structure called a Heap.  We'll look at Heaps later in the semester, but BSTs are quite similar so the idea is the same.

In this extra credit problem, you will write a general sorting function that uses a binary tree to perform the sorting:
(tree-sort L comp).  Your tree-sort function will take two arguments:
L, a list to be sorted, and comp, a function that compares two elements and returns #t if the first is less than the second and #f otherwise.  This function should expect as input the type of elements in the list to be sorted.  It is this comparison function that allows your tree-sort function to be applied to any list of elements, not just numbers.  For example:

(tree-sort '(1 5 3 9 2) <) --> (1 2 3 5 9)
(tree-sort '("welcome" "to" "computer" "science" "60") (lambda (x y) (< (length (string->list x)) (length (string->list y))))) --> ("60" "to" "science" "welcome" "computer")

Reember that the function
(lambda (x y) (< (length (string->list x)) (length (string->list y))))
is an anonymous function.  That is, it is a function without a name.  This particular function takes two arguments, x and y, both strings.  It returns #t if the string x is shorter than the string y, and #f otherwise.  An alternative way to write the same code as the second example above is:

(define (shorter x y)
  (< (length (string->list x)) (length (string->list y))))

(tree-sort '("welcome" "to" "computer" "science" "60") shorter)

As we'll discuss in class next week:
(define (shorter x y)
  (< (length (string->list x)) (length (string->list y))))

is just a shorter way of writing:
(define shorter
  (lambda (x y)
    (< (length (string->list x)) (length (string->list y)))))

In your tests you can use whichever construct you prefer.

For your tree-sort function you must use the following algorithm:
You will certainly need to implement an insert function.  You use other functions you have already written and you may also wish to write other helper functions.

Testing: In your file you should include several (3 or 4) tests on different types of data showing that your tree-sort function works correctly.

Running time analysis: Finally, in a comment in your file, answer the following questions about the theoretical running time of your tree-sort and how it compares to other sorting algorithms.