...

**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 but the type of the
field is parametric (`value`

) which must be instantiated to**alpha**to match the explication of Binary Search Trees in the book. Your task is to`symbol`

- Give some examples of the
type.`symbol-BSTM`

- Devise a set of test cases (input output pairs expressed using check-expect) for the
function.`getBSTM`

- Write a Template Instantiation for
(based on the general template for functions that process`getBSTM`

**symbol-**s)`BSTM`

- Develop the code for the function
that satisfies the contract given in the stub file.`getBSTM`

- Briefly compare the asymptotic worst case running time of searching a
that is well balanced (maximum depth is proportional to the log N where N is the number of keys in the`symbol-BSTM`

) and function searches an ordered list of`symbol-BSTM`

pairs represented as two element`(key value)`

**list**s (as in Problem 2 below).

- Give some examples of the
- [30 pts] The stub file HW02.rkt provides a detailed description of how to develop the function
(and supporting function`cross`

) that consumes a`cross-help`

and a`number-list`

**symbol-list**where a`number-symbol-pair-list`

is represented by a two element`number-symbol-pair`

containing a**list**

and a**number**.`symbol`

- [30 pts] The stub file HW02.rkt provides a detailed description of how to develop the function
(and supporting function`merge`

) that consumes two ascending (technically non-descending}`merge-help`

s and merges them to form an ascending`number-list`

.**number-list** [10pts] The ubiquitous Fibonacci function defined by the trivial

program given in the stub tile HW02.rkt is interminably slow (exponential running time) for large inputs. Develop a Racket function`fib`

that consumes a natural number input`fastFib`

, produces the same answer as the`n`

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 large`fib`

). Hint: write a help function`n`

that accumulates the result in an accumulator argument performing essentially the same computation as an imperative program relying on a loop that maintains`fastFibHelp`

and`fib(k-1)`

in mutable variables as`fib(k-2)`

`k`

increases from`2`

to n. The poor efficiency the trivial functional program for`fib`

is due to the fact that it repeatedly computes the Fibonacci function for small`k`

exponentially many times.- Show Type Contracts, Purpose Statements, Examples, and Template Instantiations for
and`fastFibHelp`

. (The answers for the Template Instantiations can vary; only the salient features (primarily recursive calls) are matter.)`fastFib`

- 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
and`fastFib`

is shaded in the DrRacket definitions panel. Such shading indicates a failure to evaluate the shaded expressions in any test cases.**fastFibHelp**)

- Show Type Contracts, Purpose Statements, Examples, and Template Instantiations for
**Optional problem for extra credit:**[50 pts]

The Fibonacci functionis defined in the stub for Problem 4 in HW02.rkt. The naive program for computing`fib`

coded in the file HW02.rkt runs in exponential time,*fib**i.e.*the running time foris proportional to C`(fib n)`

`*2^n`

for some constant C. It is straightforward to write a program that computesin time proportional to`(fib n)`

`n`

as assigned in Problem 4. Your challenge is to write a program that computesin`(fib n)`

time assuming that all multiplications and additions take constant time (which is unrealistic for large*log*n`n)`

. More precisely, your program should computeusing only`(fib n)`

`O(`

*log*`n)`

addition and multiplication operations (less than C`*`

*log*`n`

operations for some constant C).**Hints**:

Assume n = Derive a recurrence for

*m`fib(2*`

in terms of`m)`

and`fib(m)`

. Derive a similar recurrence for for`fib(m-1)`

*fib(2***(*m+1)*in terms of`fib 2**m`

and`fib 2**(m-1)`

. . To produce an algorithm that runs in log operations you need to reduce computing the pair`(`

*fib(2*m),fib(2*m-1))*`(`

using a bounded number of arithmetic operations and tests.*fib(m),fib(m-1))*Initially write a program that works when

`n`

is when n 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.

- In my solution, I used "dotted pairs" to reduce overhead. The "dotted pair" representation of a pair (a,b) is (cons a b) which is illegal in all of the HTDP dialects when b is not a list, It is supported in the "other language" called "Pretty Big". Of course you can define pairs using
`(define-struct pair (left right))`

. My intuition was that such pairs have more overhead than dotted pairs but I did not perform any benchmark comparisons. If you decide to use a language other than**Intermediate student with lambda**, please put your solution to the challenge problem in a separate file called Chal02.txt and put a comment in your regular solution file HW02.rkt for problem 5 to that effect.

- [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 but the type of the