Harvey Mudd College
Computer Science 60
Assignment 2, Due Monday, February 10, 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.

On average, each problem this week is worth 10 points The earlier ones are a bit less; the later ones, a bit more... .

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 Zach or Colleen any time about any of these problems... .

Using higher-order functions

For the first three functions, superreverse, indivisible, and lotto-winner, see if you can use higher-order functions (filter, map, foldr, and sort, along with lambda) instead of using recursion explicitly, i.e., instead of calling superreverse from within superreverse's definition, and so on... . This isn't a requirement, but it will help familiarize the ideas of those HOFs (and will be more concise, codewise).

Be sure to include (and label) at least one test of your own for each function...

As with the previous homeworks, be sure to devise and include not only the provided tests in your submitted hw2pr1.rkt file, but at least one more test for each of the homework functions. Writing the tests will ensure you're confident of what each function should do and asks you to consider the space of possibilities for the function's behavior. This case analysis is a crucial skill in software design and development -- some would say the crucial skill... .

In addition, be sure to include a comment just above the test you create in order to indicate it. For example,

;; This is an additional test I've included:
(check-expect (indivisible 1 (range 1 10))  '())

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

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

Problem 3:    lotto-winner

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

Again, if this problem seems hard to start or is going awry, consider our lotto starting point and suggestions on how to proceed... .

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

Note: you're welcome to 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.

Code from class    This is the file of tree-based example functions from class - at the bottom are the find-max, find, and insert functions, good starting points for these problems.

... what are these tree-structure things?   If you're feeling uncertain about trees, you might try Prof. Colleen Lewis's Racket-trees YouTube channel!

• Video: Tree vocab, BST introduction and representations
• Video: Binary Search Trees (BSTs) - Insert and Remove Explained

Problem 4:    find-min and height

First, 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

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

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

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

Hint #1: As with the insert example, which is included at the bottom of this file of examples from Tuesday's class, this is challenging because you need to ensure your code always returns a complete binary search tree! If you're not deleting the right-hand branch, for example, you'll need to make sure it stays as the right-hand branch!

Hint #2: This one also has many cases. Here is only one of those cases, when the element to be deleted is less than the root:

   (if (< value rt)
       (list rt (delete value L) R)
       ;; otherwise, probably check some other cases...!

This problem boils down to handling all of the (many!) different cases in appropriate ways... .

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!

Code from class: Three well-commented examples of UIOLI are at the top of the example functions from class - you might use these as a starting point... .

Aargh! What is this UIOLI approach?   If you're feeling uncertain about use-it-or-lose-it, you might try Prof. Colleen Lewis's Racket-based UIOLI YouTube channel!

• Video: Graph representations: nodes, kids, leaf?, grandkids
• Video: Use-it or lose-it: sublist   (We didn't do this in class, but it's another UIOLI example... .)
• Video: Use-it or Lose-it: reach   (This is the reachable example from class... .)

Problem 7:    make-change

For this problem write a scheme function

(define (make-change total coin-list)

If no combination of coin values sums up to total, then make-change should return #f. For this problem, you have one coin of each value that appears in the list coin-list: imagine a pocketful of coins of those values. Later on in the term we'll tackle the more general problem of having as many coins of each value as possible.

We won't limit coins to U.S. denominations: any nonnegative values will be allowed. For example,

(check-expect (make-change 4 '(2 2)) #t)
(check-expect (make-change 4 '(2)) #f)
(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)

Problem 8:    gchildren

Write a function

(define (gchildren N n G)

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

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

This problem does not really fall into the use-it-or-lose-it pattern, since "it" is already provided (the input n). Rather, it is an extension of the gkids function we wrote in class -- here, to handle any number of generations of descendants!

Problem 9:    min-dist and min-path

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

Just to emphasize - be sure to use 42000000 to represent the "infinite" distance between two nodes for which there is no connecting path.

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)

The second function, an extension of the first, is min-path:

(define (min-path a b G)

The output of min-path should be a list whose

• first element is the minimum distance from a to b in G, and whose
• rest is the list of nodes from a to b in G (without repeating...)

Note that because of this output format, you will want to cons the best distance onto the list of nodes in the best path. Keep this structure in mind (dist-cons-path) to avoid lots of extra-parens bugs!!!

Here are some examples using Gt from above:

(check-expect (min-path 'd 'd Gt) '(0 d))
(check-expect (min-path 'a 'z Gt) '(42000000)) ;; z's not there!
(check-expect (min-path 'a 'e Gt) '(10 a c d e))
(check-expect (min-path 'e 'b Gt) '(67 e a b))

Hint: It's helpful to start with the reachable (reach) code from class and consider how to change the return values appropriately from booleans to numeric quantities... !

What if there are two different paths, each of which is the same (minimal) distance? In this, case you can break ties arbitrarily in returning a single solution. We will, however, only test your code on unique minimal paths -- that way there will be only one answer to worry about... .

Problem 10:    Java!

Head back to CodingBat to practice some java

• If you need a reminder about CodingBat, head back to Homework 1 for an introduction. For this week...
• ... review the Java Example Code up through and including String on this page.
• Write code for the following 8 functions (which are the next 8 within Warmup-1. Again there will be a show solution button. Try solving the problems without referring to the solutions at first -- if you need to use them, however, that's not a problem at all! The goal is that you build familiarity and comfort with the (quite different) syntax and style of Java programming... !
  
  Here are the 8 to solve:
  
  • notString
  • missingChar
  • frontBack
  • front3
  • backAround
  • front22
  • startHi
  • icyHot
• To do these, read over the Java documentation for charAt(int index), substring(int beginIndex, int endIndex), subString(int beginIndex), and length()
• Once you've completed these eight, submit the sentence

  I finished the java problems!
  

  under hw2pr2.txt within the submission site. Again, don't place that in the "partner-situation" textbox; rather, click "edit" and place it in the assignment-submission textbox.
  Good luck with Java!

Submitting your work

Be sure to submit hw2pr1.rkt to the submission site; if you've completed the Java problems, submit that note under hw2pr2.txt. If you're interested in more trees, Racket, and a very cool application (20 Q's), check out the optional extra-credit below!

Extra-credit!    twenty-questions

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 as well-labeled functions at the bottom of your hw2pr1.rkt file... .

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

• 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

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

Possible approach to 20Q...

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

1. 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.
2. 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.
3. 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"))