Although CS 60 will return to graphics in the coming weeks, this week's "graphical" programming refers to mathematical graphs, i.e., connection networks of nodes and edges that might represent human relationships, physical links, or hierarchical structures. Trees and even lists are special types of graphs: trees are graphs for which each node has at most 1 parent node, but any number of children nodes. Lists are graphs in which each node has at most 1 parent node and at most 1 child node, i.e., a purely linear structure.
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 linked below.
Each problem this week is worth 10 points
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 CS 60 tutors, or to chat with me 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 was the Racket keyword that created a function without necessarily giving it a label.
First, 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. Two example tests:
(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) ) )
Hint: the reverse function is built-in to Racket. Use it!
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 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))You might consider using an anonymous function for indivisible.
For this problem, write
(define (lotto-winner list-of-tickets winning-numbers)in which the winning-numbers input will be a list of distinct positive integers representing a set of winning lottery numbers, e.g., '(2 3 15 32 42). The list-of-tickets input will be a nonempty list of "lottery tickets" that were purchased. Each "lottery ticket" will, in turn, be a list whose first element is a symbol (the name of the person who purchased the ticket) and whose rest is a list of the lottery numbers they played. The number of lottery numbers will be equal to the length of winning-numbers. For example, here is a possible list-of-tickets:
'( (alice 2 4 16 33 42) (bob 3 4 5 6 7) (cat 3 15 16 41 42) )
Note: in class we looked at a helper function named
matches. Here it is for reference,
along with a couple of tests:
(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,
should pass, because 'cat matched three numbers (3, 15, 42), whereas
'bob matched only one number (3) and 'alice matched
two numbers (32, 42).
If there is more than one equally-good ticket, you may return either one -- but
do return only one!
(check-expect
(lotto-winner
'( (alice 2 4 16 33 42) (bob 3 4 5 6 7) (cat 3 15 16 41 42) )
'(2 3 15 32 42))
'(cat 3))
The next few problems in this assignment ask you to implement functions that manipulate binary search trees (BSTs) in a variety of ways. You might recall from class that the representation of our 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 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.
For example,
(define BT1 '( 42
(20 (7 (1 () ()) (8 () ())) (31 () (41 () ())))
(100 (60 () ()) ()) ) )
binds the label BT1 to the representation of the binary search tree shown here:
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.
This problem involves two relatively short functions. 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 bottom-level nodes, i.e., the height of the binary search tree. The height of the empty binary search tree is 0. For instance,
(check-expect (height BT1) 4) ;; using the tree defined above (check-expect (height '()) 0)
Next, 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. (Hint: if you're not already at the smallest node, which direction do you need to go to find it?) For instance,
(check-expect (find-min BT1) 1) ;; using the tree defined aboveIn a comment in your code, explain the big-O running time of the height and find-min functions in the best-case and the worst-case for binary search trees with N nodes.
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. However, for this function you should not use the flatten function we wrote in class, because it would require a subsequent call to sort (and pay its penalty in big-O run time...). Instead, use the recursive structure of the tree. (Note that you can call flatten-tree recursively on the left and right subtrees. Where will the root go?)
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,
(check-expect (flatten-tree BT1) '(1 7 8 20 31 41 42 60 100)) ;; using the tree defined above
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 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 greater than value. (Use your find-min function!) Here are two examples
(check-expect (delete 20 BT1)
'(42
(31 (7 (1 () ()) (8 () ())) (41 () ()))
(100 (60 () ()) ())))
(check-expect (delete 42 BT1)
'(60
(20 (7 (1 ()()) (8 ()())) (31 () (41 () ())))
(100 ()())))
These three problems involve either the use-it-or-lose-it approach to problem solving (discussed in the second lecture this week) or graphs of general structure -- or both!
For this problem write a scheme function
(define (make-change total coin-list)whose first input total is a nonnegative integer and whose second input coin-list is a (possibly empty) list giving the value of coins in your pocket. The make-change function should output #t if some combination of your coin values sum up to the desired total. (You may use each coin only zero or one times.) If no combination of coin values sums up to total, then make-change should return #f. We won't limit coins to U.S. denominations: any nonnegative values will be allowed. For example,
(check-expect (make-change 0 '(1 4 6 15 25 29 54)) #t) (check-expect (make-change 29 '(1 4 6 15 25 29 54)) #t) (check-expect (make-change 11 '(1 4 6 15 25 29 54)) #t) (check-expect (make-change 76 '(1 4 6 15 25 29 54)) #t) (check-expect (make-change 9 '(1 4 6 15 25 29 54)) #f) (check-expect (make-change 77 '(1 4 6 15 25 29 54)) #f)The use-it-or-lose-it approach will help here! For each coin value in the list, consider "asking" (recursively), whether the appropriate value can be reached if we use the coin or if we don't....
Write a function
(define (gchildren N n G)which takes in
;; Graph1 (define Graph1 '((a b) (b c) (c d) (d e) (c f) (e g) (e h) (f x) (x y) (y z) (z b)) ) (check-expect (gchildren 0 'a Graph1) '(a)) (check-expect (gchildren 1 'a Graph1) '(b)) (check-expect (gchildren 2 'a Graph1) '(c)) ;; these tests use sortsym to make sure we don't mark ;; your answer "wrong", just because you returned the ;; correct descendents in a different order. (define (sym<? s1 s2) (string<? (symbol->string s1) (symbol->string s2))) (define (sortsym L) (sort L sym<?)) ;; will sort a list of symbols (check-expect (sortsym (gchildren 1 'c Graph1)) '(d f)) (check-expect (sortsym (gchildren 2 'c Graph1)) '(e x)) (check-expect (sortsym (gchildren 3 'a Graph1)) '(d f)) (check-expect (sortsym (gchildren 3 'c Graph1)) '(g h y))You might want to implement (kids n G) - a function that returns the list of children of node n in graph G: it can be used to do most of the work of gchildren.
Write two related functions -- the first is (min-dist a b G), which takes in two nodes a and b and a directed, positively-weighted graph G. Graph G will be represented as a list of edges: (src dst weight). See Gt, below, for an example.
Your min-dist should return the smallest distance that is required to travel from a to b through graph G. Every node should be considered 0.0 away from itself. However, if there is no path from a to b in G, for different nodes a and b, your function should return the value 42000000, which will be bigger than any feasible path in our graphs. (The problem with using the value +inf.0 is that it is floating-point, which changes check-expect's behavior.) For example,
(define Gt '((e b 100) (a b 25) (e a 42) (a c 7) (a d 13) (a e 15)
(b c 10) (b d 5) (d e 2) (b e 100) (c d 1) (c e 7)) )
(check-expect (min-dist 'a 'e Gt) 10)
(check-expect (min-dist 'e 'b Gt) 67)
(check-expect (min-dist 'd 'd Gt) 0)
(check-expect (min-dist 'f 'a Gt) 42000000)
To help sanity-check your tests, here is a picture of Gt:
The second function, an extension of the first, is min-path:
(define (min-path a b G)whose inputs are the same as min-dist's.
This min-path function, however, should return a list whose first element is the minimum distance from a to b in G and whose remaining elements list the nodes, in order, on the minimum path from a to b. The minimum path from a to itself is simply a. If no minimum path exists, omit the nodes altogether. If more than one equal-cost minimum path exists, your function may return any one of them. (We will only test your code on goals and graphs offering a single minimum path.) As examples:
(check-expect (rest (min-path 'a 'e Gt)) '(a c d e)) (check-expect (first (min-path 'a 'e Gt)) 10) (check-expect (rest (min-path 'e 'b Gt)) '(e a b)) (check-expect (first (min-path 'e 'b Gt)) 67) (check-expect (rest (min-path 'd 'd Gt)) '(d)) (check-expect (first (min-path 'd 'd Gt)) 0) (check-expect (rest (min-path 'a 'z Gt)) '()) ;; z's not there! (check-expect (first (min-path 'a 'z Gt)) 42000000) ;; z's not there!in which Gt is the same graph used in testing min-dist.
Hints: Consider using use-it-or-lose-it analysis for this problem in a manner similar to the reachable example we considered in class. That file is linked here and from the top-level assignment page. In fact, you might start with that reach code and consider how to change the return values appropriately from booleans to numeric quantities... !
Note: there are several algorithms for the shortest-path problem that are more efficient than the use-it-or-lose-it approach. We'll return to this problem later in the course.
This problem provides an introduction to the syntax and some of the idiosyncrasies of Java, a language very different from Racket. We will consider the big ideas of Java and object-oriented programming in a few weeks -- this problem is about Java "in the small," as warm-up for larger applications later.
So, to start getting used to Java, we will use an online resource
known as CodingBat or JavaBat. Go to its site, at
http://codingbat.com/java
Once you're there, you might try the first problem in the Warmup-1 set of problems.
But I've never used Java! One of CS 60's goals is that
CS60ers can program anything even in languages never used before! After all,
the basic ideas (booleans, ifs, strings, arrays (lists), etc.) are the same in every
language. The CodingBat site has a brief (but sufficient) explanation of Java's
syntax in the links at the top of the page:
What to do? The tasks here are
Be sure to submit hw2pr1.rkt to the submission site. We can score the Java problems as long as you "share" to stone@cs.hmc.edu, as noted above.
This completely optional problem asks you to implement the game of 20 questions.
It is worth up to +10 points.
First, to give you a sense of the game of 20 questions,
here is an example of a run in Scheme. 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 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 Does 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 (the one used for the example program demoed in class), 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"))
Strings are likely the simplest data structure for questions and objects. The function
string-append, along with the other string functions noted on the Scheme reference card may be of use.
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 of the demo version,
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 are strings (possible answers); 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"))
Note that, by our convention, "no" traverses to the left and "yes" to the right.