...
- Carefully follow the Sample Solution to a Programming Problem in the Racket HW Guide. Only half of the credit for each programming problem is based on the the correctness of your code as determined by our test cases. Much of the grade is based on how well you follow the design recipe.
- Check out (and SVN command) the file svn.rice.edu/r/comp311/courses/HW02.rkt from the Rice SVN repository and use as a stub for writing your solution the problems below.
- Use the Racket language called Intermediate student with lambda because it supports tracing and provides better diagnostics. Beware of typos such as mistyping the name of a function (e.g.,
empty
instead ofempty?
) or improperly matched parentheses.
- Do the following programming problems:
- [30 pts] Section 14.2 in the HTDP First Edition book describes what it calls Binary Search Trees. The terminology in this section of the book is non-standard because the Binary Search Trees contain both keys and values in each node and hence represents a finite mapping from keys to nodes. The stub file contains describes a simple Racket programming problem (with a solution consisting of only a few lines of executable Racket code) based on essentially the same inductive data definition as Binary Search Trees. Your task is to
- Give some examples of the BSTM type.
- Devise a set of test cases (input output pairs expressed using check-expect) for the
getBSTM
function. - Write a Template Instantiation for
getBSTM
(based on the general template for functions that process BSTMs) - Develop the code for the function
getBSTM
that satisfies the contract given in the stub file. - Briefly compare the asymptotic worst case running time of searching a BSTM that is well balanced (maximum depth is proportional to the log N where N is the number of keys in the BSTM) and function searches an ordered list of (key value) pairs.
- [10 pts] Develop the function
count-symbols
that consumes a list of symbols and produces the number of items in the list. - [10 pts] Develop the function
count-numbers
that counts how many numbers are in a list of numbers. - [20 pts] Develop the function
avg-price
. It consumes a list of toy prices and computes the average price of a toy. The average is the total of all prices divided by the number of toys. toy prices are numbers. [Hint: develop several auxiliary functions (following the design recipe to develop each auxiliary function) that you can use to make the definition ofaverage-price
very easy. If the list of toy prices is empty, the functionavg-price
produces an error message as described in Guidance below - [10pts] Develop the function
elim-exp
to eliminate expensive toys. The function consumes a number, called mp (short for "maximum price) and a list of toy prices, calledlotp
, and produces a list of all those prices inlotp
that are below or equal tomp
. For example(check-expect (elim-exp 1.0 (list 2.95 .95 1.0 5) (list .95 1.0)) = #true
[10pts] Develop the function
delete
to eliminate specific toys from a list. The function consumes the name of a toy, calledty
, and a list of names, calledlon
, and produces a list of names that contains all components oflon
with the exception ofty
. For example,(check-expect (delete 'robot (list 'robot 'doll 'dress)) (list 'doll 'dress)) = #true
[30pts] A list can be used to represent a finite set. For example,
(list 'c 'o 'm 'p)
represents the set of symbols {'c , 'o, 'm, 'p}. In such a representation, we assume all elements in the list are unique; there are no duplicates. Develop the function
power
that consumes a list of symbolslos
(representing a set) and produces a list of list of symbols representing the power set (set of all subsets) oflos
. Hint: write an auxiliary functioncons-all
that consumes a symbol sym and a list of list of symbolslolos
and inserts symbolsym
at the front of each list inlolos.
For example,
(check-expect (cons-all 'a (list (list 'c) (list 'o) (list 'm) (list 'p)) (list (list 'a 'c) (list 'a 'o) (list 'a 'm) (list 'a 'p))) = #true
- [30 pts] Section 14.2 in the HTDP First Edition book describes what it calls Binary Search Trees. The terminology in this section of the book is non-standard because the Binary Search Trees contain both keys and values in each node and hence represents a finite mapping from keys to nodes. The stub file contains describes a simple Racket programming problem (with a solution consisting of only a few lines of executable Racket code) based on essentially the same inductive data definition as Binary Search Trees. Your task is to
- 30 pts] The stub file HW02.rkt provides a detailed description of how to develop the function
merge
(and supporting functionmerge-help
) that consumes two ascending [technically non-descending} number-lists and merges them to form an ascending number-list. [10pts]
- Follow the design recipe imitating Sample Solution to a Programming Problem .
- Problem 4 asks you to write a function that checks for the empty list as an input error and throws an aborting error in the case. (The purpose statement should document this behavior!) In DrRacket, the
error
function take a single argument not two arguments as documented in the book. We recommend using a string (text enclosed in double quotation marks like"An empty list of toy prices triggers this aborting error"
. You can test the error throwing behavior of a function usingcheck-error
which is documented in the DrRacket Help Desk. - Study Figure 26 in 9.4 for a detailed description of the design recipe and how it is documented in the program text that you develop.
To follow the design recipe, you must write down the type contract, purpose, provide at least 3 well-chosen examples (more for complex functions likepower
), write the template for the function (trivial when no recursion is involved), write the code for the function, and include illustrative test cases for the function (using at least the examples you developed ahead of time). You should bundle the examples and test cases together as a block ofcheck-expect
invocations, which was not part of DrScheme when the book was written. These tests should precede your template and code. Your chosen examples should illustrate the output you expect, and the test cases should produce the actual output (leave them uncommented). If the function processes an inductive type, make sure that your examples include the base case(s) and sample inductive cases.
- 30 pts] The stub file HW02.rkt provides a detailed description of how to develop the function