This week, you'll get to practice writing operations over Binary Search Trees (BSTs). You'll also get some more practice with the use-it-or-lose-it style of algorithm.
All of the problems this week may be done in a pair, in you wish. Certainly it's OK to work on them individually, too. If you do work in a pair, make sure you follow the pair-programming practices as noted on the CS 60 syllabus.
Whether individual or pair, place all of your functions for this week in a file named hw2pr1.rkt. There is a (small) starter file by that name.
Just a reminder that these are important! 25-30% of the assignment's points will be based on these. A few details:
Be sure to submit your hw2pr1.rkt file to the submission site!
Start with the hw2pr1.rkt starter file -- it has placeholders for the functions you will need.
Some of these problems have a component of open-ended algorithm design, as well as reinforcement of this week's themes. Feel free to seek out help in discussions with other students, the grutors, or to chat with your instructor any time about any of these problems... .
Using higher-order functions
For the first three functions,
superreverse, indivisible, and
lotto-winner, you should not use
recursion explicitly, i.e., you should not call
superreverse from within superreverse's
definition, and so on... .
Instead, use higher-order functions and/or anonymous functions in order to implement these. Recall that higher-order functions are those that take in functions as input and/or produce a function as output. Helper functions are still welcome -- but they, too, should use higher-order functions and other Racket built-in functions, rather than raw recursion. As a reminder, some of the higher-order functions we examined in class include map, foldr, sort, and filter. Also, lambda is the Racket keyword that creates a function without necessarily giving it a label.
Implement (superreverse
L), whose functionality is identical to what it was in
hw1. Again, assume that the input L
will be a list that
contains zero or more lists (and only lists) as elements.
The output of (superreverse L) should be a list similar
to L, but with all of its top-level sublists reversed.
You should write simple tests. Here are two example tests that are not simple:
(check-expect (superreverse '( (1 2 3) (4 5 6) (#\k #\o #\o #\l) (#\a #\m) ))
'( (3 2 1) (6 5 4) (#\l #\o #\o #\k) (#\m #\a) ) )
(check-expect (superreverse '( (1 2 3) (4 5 6 (7 8) 9 ) ))
'( (3 2 1) (9 (7 8) 6 5 4) ) )
Implement (indivisible k L), where k
is a positive
integer and L is a list of positive integers.
Then, indivisible should return a list consisting of all of the
elements of L that are not
evenly divisible by k. Those elements
should appear in the same order as they do in L.
For instance,
(check-expect (indivisible 3 '( 2 3 4 5 6 7 8 9 10 )) '(2 4 5 7 8 10))
This problem is challenging! We have a starting point for this one, along with suggestions to help make progress... .
For this problem, write
(define (lotto-winner list-of-tickets winning-numbers)
'( (alice 2 4 16 33 42) (bob 3 4 5 6 7) (cdrthecat 3 15 16 41 42) )
(define (matches L W)
(length (filter (lambda (x) (member x W)) L)))
(check-expect (matches '(ace 2 3 4) '(3 42 2)) 2)
(check-expect (matches '(ace 2 3 4) '(8 4 5)) 1)
The lotto-winner function should output a list of two
things: first, the name (symbol) of the person who matched the
most numbers and, second, the number of numbers they matched.
For the above example data,
(check-expect (lotto-winner
'( (alice 2 4 16 33 42) (bob 3 4 5 6 7) (cdrthecat 3 15 16 41 42) )
'(2 3 15 32 42))
'(cdrthecat 3))
The next few problems in this assignment ask you to implement functions that manipulate binary search trees (BSTs) in a variety of ways. Recall, all leaves within a left-hand subtree are strictly less than the value of the root. All elements within a right-hand subtree are strictly greater than the root. Finally, no value may be repeated in a BST. We will use binary search trees of only integers for the following three problems.
We will use the following functions to create and work with binary search trees.
For full credit, you should use these constructors and these selectors to make your code MUCH more readable! These are not built into Racket so we have provided them in the starter file.
;; make-BST creates a BST by calling list
;; inputs: a key and two trees
;; output: a non-empty BST
(define (make-BST key left right)
(list key left right))
;; make-empty-BST creates an empty BST.
;; inputs: none
;; output: an empty BST
(define (make-empty-BST)
'())
;; make-BST-leaf: creates a BST with one node (aka a leaf).
;; inputs: a key
;; output: a new BST, with key as the root
(define (make-BST-leaf key)
(make-BST key ; key
(make-empty-BST) ; left subtree
(make-empty-BST))) ; right subtree
;; emptyTree?: checks if a tree is empty
;; inputs: a BST
;; outputs: #t if tree is empty; otherwise #f
(define (emptyTree? tree)
(null? tree))
;; leaf? - checks if the input is a BST with no children
;; inputs: a BST
;; output: #t if it is a leaf, otherwise #f
(define (leaf? tree)
(and (null? (leftTree tree))
(null? (rightTree tree))))
;; key - returns the key for the BST
;; inputs: a BST
;; output: the key
; Access the key from a BST
(define (key tree)
(first tree))
;; leftTree - returns the left tree from the BST
;; inputs: a BST
;; output: the left subtree
(define (leftTree tree)
(second tree))
;; rightTree - returns the right tree from the BST
;; inputs: a BST
;; output: the right subtree
(define (rightTree tree)
(third tree))
For example,
(define BigBST
(make-BST 42
(make-BST 20
(make-BST 7
(make-BST-leaf 1)
(make-BST-leaf 8))
(make-BST 31
(make-empty-BST)
(make-BST-leaf 41)))
(make-BST 100
(make-BST-leaf 60)
(make-empty-BST))))
> BigBST
'(42 (20 (7 (1 () ()) (8 () ())) (31 () (41 () ()))) (100 (60 () ()) ()))
Note: you may use raw recursion for these problems -- and we encourage you to do so. Higher-order functions are OK, too, but may not be as natural in this context.
Begin by creating small binary search trees for testing the functions you write. You should define trees (and give them appropriate names) for each of the following cases:
... what are these tree-structure things? If you're feeling uncertain about trees, you might try Prof. Colleen Lewis's Racket-trees YouTube channel!
Write a function (height BT)
whose input is a binary
search tree and whose output
is the number of edges in the longest path from the root of BT
to any one of its bottom-level nodes, i.e.,
the height of the binary search tree.
Note that in this case we are defining the
height of the empty binary search tree as -1.
For instance,
(check-expect (height BigBST) 3) ;; using the tree defined above
(check-expect (height (make-empty-BST)) -1)
(check-expect (height (make-BST 42 (make-empty-BST) (make-empty-BST))) 0)
Write a function (find-min BT)
whose input will always be a
non-empty binary search tree and whose output
is the value of the smallest node in that binary search tree.
For instance,
(check-expect (find-min BigBST) 1) ;; using the tree defined above
Write a function (in-order BT) whose input is any binary search tree and whose output is a list of all of the elements, in order, of the input. Instead, use the recursive structure of the tree. (Note that you can call in-order recursively on the left and right subtrees. Where will the root go?)
For example,
(check-expect (in-order BigBST) '(1 7 8 20 31 41 42 60 100)) ;; using the tree defined above
Write the function (tree-map f BST) whose input
f is a function that takes in one input and whose
input BST is a Binary Search Tree created using the
make-BST function. It should return a Binary Search
Tree with the exact same structure as the input BST,
but each key should be replaced by the value returned by calling
the function f on the original key.
For example,
(check-expect (tree-map (lambda (x) (+ x 2)) BigBST)
'(44 (22 (9 (3 () ())
(10 () ()))
(33 ()
(43 () ())))
(102 (62 () ())
())))
The final binary search tree function this week is to write a function (delete value BT) whose input value is an integer and whose input BT is a binary search tree. 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 -- and other adjustments made, as necesary, to ensure that the result is a valid binary search tree. The next paragraph describes these adjustments.
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 more complicated 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 greater than value. (Use your
find-min function!)
Here are two examples:
(check-expect (delete 20 BigBST)
'(42
(31 (7 (1 () ()) (8 () ())) (41 () ()))
(100 (60 () ()) ())))
(check-expect (delete 42 BigBST)
'(60
(20 (7 (1 ()()) (8 ()())) (31 () (41 () ())))
(100 ()())))
Before writing code for this problem, we encourage you to write some simple-as-possible test cases. Here are some ideas:
For this problem write a Racket function
(define (make-change total coin-list)
(check-expect (make-change 0 '(1 4 6 15 54 25 29)) #t)
(check-expect (make-change 29 '(1 4 6 15 54 25 29)) #t)
(check-expect (make-change 11 '(1 4 6 15 54 25 29)) #t)
(check-expect (make-change 76 '(1 4 6 15 54 25 29)) #t)
(check-expect (make-change 6 '(2 2 2 2 2 2 2 2 2)) #t)
(check-expect (make-change 9 '(1 4 6 15 54 25 29)) #f)
(check-expect (make-change 77 '(1 4 6 15 54 25 29)) #f)
Head back to practice some java
Be sure to submit hw2pr1.rkt and Hw2pr1.java to the submission site.
This completely optional problem asks you to implement the game of 20 questions. It is worth up to +10 points.
Submission Please submit this extra credit in a file named hw2extra.rkt on the submission site.
First, to give you a sense of the game of 20 questions,
here is an example of a run in Racket. The user's input is in
blue
> (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? Does it 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 it 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 it 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
Features
Your twenty questions should allow users to
Representation
For consistency, your game should always start with the question Is it bigger than a
breadbox? and should have the objects spam and a computer scientists
available as guesses if the user answers the initial question with a n or a y,
respectively.
You are welcome to represent the game's data however you like. However as a guide to one possible
representation, you might
consider a tree in which internal nodes are questions and leaf nodes are objects, e.g.,
(define initialTree '("Is it bigger than a breadbox?" "spam" "a computer scientist"))
Possible decomposition
As with the data structure, the choice here is yours. As one possible suggestion
to get you started (if you'd like), consider the decomposition that we used in our solution,
which included
Input:
Here are two functions demonstrating how to use (read-line) to
grab a line of user input.
The first tests 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)))
Hints: (feel free to disregard!)
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 lists;
rather, they 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" ("Does it 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.