Homework 2
Due: 11:59pm, Tuesday, Sep 08, 2020
100 points
For all Racket assignments in this course, set the DrRacket Language to Advanced Student
(under How to Design Programs
). Your assignment will be graded using the specified language level. If you use a different language level, your code may not work when it is graded.
- 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.
- [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]
- [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