Harvey Mudd College
Computer Science 42
Assignment 3, Due Monday, September 20, by 11:59pm

Unicalc with Error Bars and Graphs and Trees

This assignment has two problems and one extra credit option.  In problem 1 you will continue your development of the Unicalc application by adding error-propagation to your back-end functionality.  You're ready to start this problem right away. In problem 2 you will work with a graph to find the shortest path between two nodes.  You'll want to wait until after Thursdays lecture to start this problem.  The extra credit problem is to implement a game of 20 questions.  Again, you're ready to go on this one.  You don't have to do the extra credit of course, but it's a lot of fun and it'll give you practice with trees, which you will be responsible for understanding on the midterm and final exams.

Design, commenting, testing and formatting

The same guidelines apply as for homework 1 and homework 2.

Testing

A few tests are provided below, but as these problems become larger, it becomes increasingly important to create and use additional tests of your own -- not only for top-level functions, but for helper functions, as well.  For problem 1 and the extra credit, you do not have to include additional tests, but for problem 2 you should provide at least one additional test.  Again make sure these tests are clearly identified for the graders with comments in your code.

The Problems

Problem 1 [40 points]: Unicalc with Error Bars [Individual or Partner], submitted in a file named ucErrorProp.rkt

Supplied files

• unicalc-tests.rkt -- The same tests from last week.
• unical-with-error-tests.rkt -- Unit tests for the version of unicalc you will implement below.
• unicalc_solutions.rkt -- A solution file for last week's assignment.  Feel free to use this as a starting point if you want.  Looking at this code before you have completed Assignment 2 is a violation of the HMC Honor Code.

Background

Your Task

• (make-QL val num den) -- Creates an Uncertain Quantity with a quantity val and zero error.  As before, num is the list of units in the numerator, and den is a list of units in the denomintor.  This function is provided for backward compatibility with our tests from last time.
• (make-UQL val err num den) -- Creates an Uncertain Quantity with a quantity val, and specified standard error, err.  num and den are as above.
• (get-quant Quantity) -- Returns the quantity (value) of the Quantity
• (get-error Quantity) -- Returns the standard error of the Quantity
• (get-num Quantity) -- Returns the list of units in the numerator
• (get-den Quantity) -- Returns the list of units in the denominator

Problem 2 [60 points]: Graphs and Direction Finding [Individual], submitted in a file named shortestPath.rkt

Graphs are an extremely important data structure in computer science.  As we discussed in class, they can represent any number of things, but a popular use of graphs is to represent cities on a map.  Used in this way, an important ability is to find the shortest path from one node in the graph (city) to another.

Write a function (min-path 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-path 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. 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:

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

(test (min-path 'a 'e Gt) '(10 a c d e))
(test (min-path 'e 'b Gt) '(67 e a b))
(test (min-path 'd 'd Gt) '(0 d))
(test (min-path 'a 'z Gt) '(+inf.0)) ;; z's not there!

To help sanity-check your tests, here is a picture of Gt:

Feel free, also, to use a subgraph for debugging.

For this problem, you should also test on at least 1 other pair of nodes from Gt.  Include this test in your code with a comment that clearly identifies it as your additional test.

Hints: 

1. Break this problem down into many subfunctions.  Try to do as little as possible with each subfunction
2. As suggested in class, maintain a list of "paths so far" complete with their costs.  Keep this list in order from smallest cost to largest cost.  Always continue exploring from the first path in the list.  You might find it helpful to actually store nodes in reverse as you compute the path, and simply reverse them at the end once you find the complete path.

Extra Credit [up to +20 points]: Trees [Individual], submitted in a file named twentyQ.rkt

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

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

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 in last week's HW. In this case, the leaves are not empty, but 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"))