...
- 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] The ubiquitous Fibonacci function defined by the trivial
fib
program given in the stub tile HW02.rkt is interminably slow (exponential running time) for large inputs. Develop a Racket function fastFib that consumes a natural number input n, produces the same answer as the fib function defined in the stub file, and runs in linear time (assuming that the primitive addition operation runs in constant time, which fails for very largen
). Hint: write a help functionfastFibHelp
that accumulates the result in an accumulator argument performing essentially the same computation as an imperative program relying on a loop that maintainsfib(k-1)
andfib(k-2)
in mutable variables ask
increases from2
to n. The poor efficiency the trivial functional program forfib
is due to the fact that it repeatedly computes the Fibonacci function for smallk
exponentially many times.- Show Type Contracts, Purpose Statements, Examples, and Template Instantiations for
fastFibHelp
andfastFib
. (The answers for the Template Instantiations can vary; only the salient features (primarily recursive calls) are matter.) - As usual testing comes for free given that you provided input-output examples. Make sure that after you run your program that no source code text (definitions of
fastFib
andfastFibHelp)
is shaded. Such shading indicates a failure to evaluate the shaded expressions in any test cases.
- Show Type Contracts, Purpose Statements, Examples, and Template Instantiations for
Optional problem for extra credit: [50 pts]
The fibonacci function fib is defined in the stub for Problem 4 in HW02.rkt. The naive program for computingfib
coded in the file HW02.rkt runs in exponential time, i.e. the running time for(fib n)
is proportional to C*2^n
for some constant C. It is straightforward to write a program that computes(fib n)
in time proportional ton
as assigned in Problem 4. Your challenge is to write a program that computes(fib n)
inlog n
time assuming that all multiplications and additions take constant time (which is unrealistic for largen)
. More precisely, your program should compute(fib n)
using onlyO(
log
n)
addition and multiplication operations (less than C*
log
n
operations for some constant C).Hints: assume
n = 2**m
. Derive a recurrence forfib 2**(m+1)
in terms offib 2**m
andfib 2**(m-1)
. Initially write a program that works whenn
is a power of 2. Then refine this prototype to a program that works for all n. This is a challenging problem. Make sure that you have thoroughly completed the regular homework problems before attempting it.
- [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