...
- 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
cross
(and supporting functioncross-help
) that consumes a - [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