Due: 11:59pm, Thursday, Sep 15, 2022
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.
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.
value
field is parametric (alpha
) which must be instantiated to symbol
to match the explication of Binary Search Trees in the book. Your task is to symbol-BSTM
type.getBSTM
function.getBSTM
(based on the general template for functions that process symbol-BSTM
s)getBSTM
that satisfies the contract given in the stub file.symbol-BSTM
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 (key value)
pairs represented as two element lists (as in Problem 2 below).cross
(and supporting function cross-help
) that consumes a number-list
and a symbol-list
and produces a number-symbol-pair-list
where a number-symbol-pair
is represented by a two element list
containing a number
and a symbol
.merge
(and supporting function merge-help
) that consumes two ascending (technically non-descending} number-list
s 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 large n
). Hint: write a help function fastFibHelp
that accumulates the result in an accumulator argument performing essentially the same computation as an imperative program relying on a loop that maintains fib(k-1)
and fib(k-2)
in mutable variables as 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.
fastFibHelp
and fastFib
. (The answers for the Template Instantiations can vary; only the salient features (primarily recursive calls) are matter.)fastFib
and fastFibHelp)
is shaded in the DrRacket definitions panel. Such shading indicates a failure to evaluate the shaded expressions in any test cases.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 for (fib n)
is proportional to C*bn
for some proportionality constant C and base b > 1. It is straightforward to write a program that computes (fib n)
in time proportional to n
as assigned in Problem 4. Your challenge is to write a program that computes (fib n)
in log n
time assuming that all multiplications and additions take constant time (which is unrealistic for large n)
. More precisely, your program should compute (fib n)
using only O(
log
n)
addition and multiplication operations (less than C*
log
n
operations for some constant C).
Hints:
Derive a recurrence for fib(2*m)
in terms of fib(m)
and fib(m-1)
. Derive a similar recurrence for 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))
to computing (fib(m),fib(m-1))
using a bounded number of arithmetic operations and tests.
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.
(define-struct pair (left right))
without compromising the goal of a solution that only requires O(
log
n)
operations. 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.