# Homework 2

**Due:** 11:59pm, Wednesday, Sept 18, 2024

**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.

For all Racket assignments in this course, set the DrRacket Language to **Intermediate Student with lambda** (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 correctness of your code as determined by our test cases. Much of the grade is based on how well you follow the*design recipe*. For a crisp example of what an ideal solution looks like look at the**Sample Solution to a Programming Problem**that sortsat the end of`(list-of number)`

**Sample Solution to a Programming Problem**in the the**Racket HW Guide**. This process may appear painful but it shows "in the small" how program design should be done "in the large". It is not difficult. If you carefully inspect the sample program, it shows the level of detail in describing your program design (and its derivation!) that we want.

**Do the following programming problems using only the primitives mentioned in Lectures 2-5****. Do not use the functions in the Racket library if they are not mentioned in Lectures 2-5.**

- [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 a Binary Search Tree contains both keys and values in each node and hence represents a finite mapping from keys to values. The stub file contains 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. Using the stub code for Problem 1 in`symbol`

as a starter template, your task is to`HW02.rkt`

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

- Devise a set of test cases (input-output pairs expressed using

) for the**check-expect**function.`getBSTM`

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

**(**`BSTM-of symbol).`

- 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`BSTM-of symbol)`

**(**) and function searches an ordered`BSTM-of symbol)`

, where each pair is represented as a two-element`(list-of`

`(pair-of key value))`

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

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

(and supporting function`cross`

) that consumes a`cross-help`

and a`(list-of number)`

**(list-of****symbol)**where a`(pair-of number symbol)`

is represented by a two-element`(pair-of number symbol)`

containing a**list**

and a**number**.`symbol`

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

(and supporting function`merge`

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

inputs merges them to form an ascending`(list-of number)`

.`(list-of number)`

[10pts] The ubiquitous Fibonacci function defined by the trivial

program given in the stub tile`fib`

is interminably slow (exponential running time) for large inputs. Develop a Racket function**HW02.rkt**that consumes a natural number`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)`

increases from`k`

`2`

to n. The poor efficiency of the trivial functional program foris due to the fact that it repeatedly computes the Fibonacci function for small`fib`

exponentially many times.`k`

- 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) 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 case.**fastFibHelp**)

- Show Type Contracts, Purpose Statements, Examples, and Template Instantiations for

**Optional problem for extra credit:** [50 pts (a challenging problem)]

The Fibonacci function * fib* is 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, *i.e.*the running time ofh

**is proportional to C**

`(fib n)`

`*b`^{n}

for some proportionality constant C and base b > 1. It is easy to write a program that computes **in time proportional to**

`(fib n)`

`n`

as assigned in Problem 4. Your challenge is to write a program that computes **in**

`(fib n)`

*log* n

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

. More precisely, your program should compute **using only**

`(fib n)`

`O(`

*log *

`n)`

addition and multiplication operations (less than C`*`

*log *

`n`

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

Derive a recurrence for

in terms of`fib(2*m)`

and`fib(m)`

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

*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 a power of 2. Then refine this prototype to a program that works for all n based on determining whether n is even or odd.

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". This design choice is a bit of a stunt to minimize obvious overhead. Of course, you can define pairs using
without compromising the goal of a solution that only requires`(define-struct pair (left right))`

`O(`

*log*`n)`

operations. My intuition was that such pairs have more overhead than dotted pairs but I did not perform any benchmark comparisons. Please put your solution to the challenge problem in a separate file called Chal02.rkt and submit as instructed in the Canvas announcement (11:59 pm on Monday, Sept 23).