Assignment 2

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

Graphical programming

Although CS 60 will introduce 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.

Pair problems

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.

Design, testing, commenting, and formatting!

Just a reminder that these are important! 25-30% of the assignment's points will be based on these. A few details:

Design matters! Be sure the use small helper functions to maintain a modular, "Racket-clean" style for your solutions.
Testing matters! Be sure to use our tests, as well as at least one -- and perhaps more -- of your own for all of your functions.
Include a top-of-function comment for all functions you write, including helper functions. Have a brief description of what the function does and the format/meaning of its inputs and output.
Include a top-of-file comment with your name(s), roughly how much time the assignment took, and any other comments you'd like to share with us or the grutors.
Comments are not necessary within function bodies, unless something tricky is going on. Particularly if you are writing many small functions (instead of fewer, larger ones), the top-of-function comment is most often enough.
Do format your code to make it easy to understand. Choose a formatting and indentation style that is clear and stick with it! Formatting also includes coding style: clean and clear structure, meaningful variable and function names, ample use of spacing, and indenting that reflects code structure.

Submitting your work

Be sure to submit your hw2pr1.rkt file to the submission site!

The Problems

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.

Problems 1 and 2: `superreverse` and `indivisible`

This problem asks you to write two functions. 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.

Problem 3: `lotto-winner`

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) (cdrthecat 3 15 16 41 42) )

Note: in class we looked at a helper function named matches. However, there may have been a pair of parens missing from that definition. 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)

It's important that the inputs to a lambda-expression be in a list, i.e., in parentheses; otherwise, Racket will add list structure to the inputs!

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

should pass, because 'cdrthecat 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!

Trees!

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 binary search tree shown. Its root is 42 and the root of its left subtree is 20 (and so on...).

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.

Problem 4: `height` and `find-min`

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. For instance,

(check-expect (find-min BT1) 1) ;; using the tree defined above

In 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.

Problem 5: `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. However, for this function you should avoid the flatten we wrote in class, which would require sort, and 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

Problem 6: `delete`

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

Graphs and use-it-or-lose-it

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!

Problem 7: `make-change`

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 of coin values that you currently have. The make-change function should output #t if some combination of your coin values sum up to the desired total. 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 in the list, consider "asking" (recursively), whether the appropriate problem can be solved with it and without it... .

Problem 8: `gchildren`

Write a function

(define (gchildren N n G)

which takes in

N, a nonnegative integer
n, a symbol representing a node in a graph
G, a graph represented as a list of (src dst) pairs of nodes: (source destination)

As output, gchildren should return a list of all of the N-th generation descendants of node n in graph G. If N is 0, then (list n) should be returned, regardless of G. If node n does not have any descendants that are n-levels deep in G, the empty list should be returned. Here is an example graph and a few examples:

;; 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 avoid ambiguity in node 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.

Problem 9: `min-dist`

Write a function (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 valid Scheme value +inf.0, which represents positive, floating point infinity. 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-within (min-dist 'a 'e Gt) 10.0 .5)
(check-within (min-dist 'e 'b Gt) 67.0 .5)
(check-within (min-dist 'd 'd Gt) 0.0 .5)
(check-within (min-dist 'f 'a Gt) +inf.0 .5)

Here we have used check-within in order to allow testing with floating-point values. Fortunately, +inf.0 is within 0.5 of itself! To help sanity-check your tests, here is a picture of Gt:

Hints: Consider using weirdo 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... !

Problem 10: `Java!`

This problem will provide a brief introduction to using Java, a language very different from Racket. You'll get Java running (either on your machine or elsewhere) and alter this hw2pr2.java file before submitting it.

Setting up Java Go to this Java set-up page for instructions on geting started with the Java language.

The problem

First, download hw2pr2.java and open in in Dr. Java or the IDE (integrated development environment) of your choice. Once it's open in Dr. Java, you should

compile the code (with the compile button or F5)
run the code (with the run button or F2)

If everything goes as expected, you should see the interactions pane prompt you for four numbers: the x- and y-coordinates of two 2d points. It will then print the Manhattan distance between those two points and a final message, based on that distance. Here, the human input is in blue:

Hello from Java!
Type an x-coordinate:  10
Type a  y-coordinate:  20
Type another x-coordinate:  11
Type another y-coordinate:  21
Point p1 is (10.0,20.0)
Point p2 is (11.0,21.0)
Their manhattan distance is 2.0
Too close!

The Manhattan distance is the sum of the absolute differences between the x- and y-coordinates: |10-11| + |20-21| == 2 in this case.

Read over the code and, perhaps, the annotated "slide" that describes some of how that program works. Then, change the file so that

It asks for three pairs of x- and y-coordinates (instead of two). It should construct three objects of type Point, named p1, p2, and p3.
It should compute the Euclidean distance between the three possible pairs of Points: (a) from p1 to p2, (b) from p2 to p3, and (c) from p1 to p3. To do this, you should write a new method (that is, a function), almost identical to the existing manhattan_distance method, but called euclidean_distance (and that computes Euclidean distance). You will want to use Java's Math.sqrt function to take square roots. Another Math methods is Math.pow( base, power ). All of Java's extensive libraries are documented at the Java 1.6 API -- click on the Math class in the lower left-hand pane for the details of Math.pow and Math.sqrt. The Euclidean distance is the square root of the sum of the squares of the x- and y- differences.

Finally, your Java program should print out the smallest of those three Euclidean distances. You'll want to adapt Java's if construct, which appears at the end of the provided file. Here is an example run with some sample input and output (human input in blue):

Hello from Java!
Type an x-coordinate:  10.0
Type a  y-coordinate:  10.0
Type another x-coordinate:  11.0
Type another y-coordinate:  11.0
Type yet another x-coordinate:  15.0
Type yet another y-coordinate:  15.0
Point p1 is (10.0,10.0)
Point p2 is (11.0,11.0)
Point p3 is (15.0,15.0)
Their Euclidean distances are
1.4142135623730951 (1 -> 2)
7.0710678118654755 (1 -> 3)
5.656854249492381 (2 -> 3)
The minimum distance is from 1 -> 2: 1.4142135623730951

We will add unit-testing to our Java programs next week -- this is simply a chance to familiarize yourself with the language a bit... .

Submit your changed hw2pr2.java file to the submission site as usual.

Submitting your work

Be sure to submit both hw2pr1.rkt and hw2pr2.java to the submission site. Be sure to include your tests -- provided and your own -- for the Racket code. If you'd like to work on one or both of the extra-credit problems -- include those in hw2pr1.rkt, too. (They're below.)

Extra-credit! `min-path` and `twenty-questions`

min-path

Write the Racket function

(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.) In addition, we need to use check-within for the floating-point values. As examples:

(check-expect (rest (min-path 'a 'e Gt)) '(a c d e))
(check-within (first (min-path 'a 'e Gt)) 10.0 0.1)
(check-expect (rest (min-path 'e 'b Gt)) '(e a b))
(check-within (first (min-path 'e 'b Gt)) 67.0 0.1)
(check-expect (rest (min-path 'd 'd Gt)) '(d))
(check-within (first (min-path 'd 'd Gt)) 0.0 0.1)
(check-expect (rest (min-path 'a 'z Gt)) '()) ;; z's not there!
(check-within (first (min-path 'a 'z Gt)) +inf.0 1.0) ;; z's not there!

in which Gt is the same graph used in testing min-dist.

20 Questions!

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

Features

Your twenty questions should allow users to

play the game, in the spirit described above
play again, once the game ends (whether the object was guessed or not)
contribute new items to the computer's "database," along with a yes/no question distinguishing a new item from another alreay known to the system

Many of the questions can be yes/no questions. You are welcome to use the askyn function below to handle those. In particular, your game should always allow y to represent a "yes" answer. Also, n should always be allowed to represent a "no" answer. This will make the submissions simpler for the graders to try out!

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

A function named (tq-once tree) that plays the game of 20 questions, as described above, and then returns the augmented tree after one complete round of the game. If the computer guesses the object correctly, it would simply return the same tree it was originally passed.
A function named (tq-continuer tree) that calls tq-once in order to run one round of the game. When finished, this function should ask if the user wants to play again and take the appropriate action.
A function named (twenty-questions) that calls tq-container using the default tree named initialTree.

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" ("Do you titrate?" "a computer scientist" "a chemist"))

Note that, by our convention, "no" traverses to the left and "yes" to the right.

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.

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

Graphical programming

Pair problems

Design, testing, commenting, and formatting!

Submitting your work

The Problems

Problems 1 and 2: superreverse and indivisible

Problem 3: lotto-winner

Trees!

Problem 4: height and find-min

Problem 5: flatten-tree

Problem 6: delete

Graphs and use-it-or-lose-it

Problem 7: make-change

Problem 8: gchildren

Problem 9: min-dist

Problem 10: Java!

Submitting your work

Extra-credit! min-path and twenty-questions

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

Problems 1 and 2: `superreverse` and `indivisible`

Problem 3: `lotto-winner`

Problem 4: `height` and `find-min`

Problem 5: `flatten-tree`

Problem 6: `delete`

Problem 7: `make-change`

Problem 8: `gchildren`

Problem 9: `min-dist`

Problem 10: `Java!`

Extra-credit! `min-path` and `twenty-questions`