This assignment has two parts. You'll be ready to start part 1 right away. You're ready to start part 2 after Tuesday's lecture.
In the first part, you will begin construction on your very own programming language, called Unicalc. This language will support simple mathematical operations of the type you might do in your physics class, complete with error bar propogation. You might actually find this language quite useful in your future....
The second part gives you practice with Racket's higher-order functions (those that take other functions as inputs or yield them as outputs) and with tail recursion.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 42 Submission Site.
Keep in mind
that you may submit multple times -- only the final submission before
the deadline will be graded.
As with assignment 1, design, formatting and testing will account for roughly a quarter of the credit for each function or program you complete. The commenting and code-formating guidelines carry over from homework #1. Here, however, there will also be consideration for algorithm design and modularity, especially in problem 1:
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.
| Function Call Form | Meaning |
| (normalize-unit Unit) | Returns a normalized Quantity for a single unit. |
| (normalize Quantity) | Converts any Quantity to a normalized Quantity. |
| (multiply Quantity1 Quantity2) | Multiplies two normalized Quantities, returning a normalized Quantity. |
| (divide Quantity1 Quantity2) | Divides normalized Quantity1 by normalized Quantity2, returning a normalized Quantity. |
| (add Quantity1 Quantity2) | Adds normalized Quantity1 to normalized Quantity2, returning a normalized Quantity, provided the quantities are interconvertible. Returns (error "illegal add" Quantity1 Quantity2) value if not. |
| (subtract Quantity1 Quantity2) | Subtracts normalized Quantity2 from normalized Quantity1, returning a normalized Quantity, provided the quantities are interconvertible. Returns (error "illegal subtract" Quantity1 Quantity2) value if not. |
| (power Quantity1 p) | Raises normalized Quantity1 to the integer power p returning a normalized Quantity. You may assume that p will be an integer (though it may be positive, negative or 0). |
; Provided test casesThis will make it easier for the graders to find your new test cases. (Being nice to the graders is an important skill to learn early!)
(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)
; MY OWN TESTS
(test (subbag '(3 2 1) '(1 2 3)) #t)
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)Note that subbag needs only work with elements at the "top level."
(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, XXX:
(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)
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)
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) ())Using higher-order functions
(test (tail-range 40 50) '(40 41 42 43 44 45 46 47 48 49))
For the rest of this assignment (Problem 2.5 and Problem 2.6), 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 the same as last week's problem, but 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 2.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.
(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.
;; 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. 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 extra credit problem 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.
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. 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 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 () ())))