Homework 2
Due: 11:59pm, TuesdayWednesday, Sep 0816, 2020
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.
- 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 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.
- Check out (and SVN command) the file svn.rice.edu/r/comp311/courses/HW02.rkt from the Rice SVN repository and use as a stub for writing your solution the problems below.
- Use the Racket language called Intermediate student with lambda because it supports tracing and provides better diagnostics. Beware of typos such as mistyping the name of a function (e.g.,
empty
instead ofempty?
) or improperly matched parentheses.
- Do the following programming problems:
- [20 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. Check out the file from
- [10 pts] Develop the function
count-symbols
that consumes a list of symbols and produces the number of items in the list. - [10 pts] Develop the function
count-numbers
that counts how many numbers are in a list of numbers. - [20 pts] Develop the function
avg-price
. It consumes a list of toy prices and computes the average price of a toy. The average is the total of all prices divided by the number of toys. toy prices are numbers. [Hint: develop several auxiliary functions (following the design recipe to develop each auxiliary function) that you can use to make the definition ofaverage-price
very easy. If the list of toy prices is empty, the functionavg-price
produces an error message as described in Guidance below - [10pts] Develop the function
elim-exp
to eliminate expensive toys. The function consumes a number, called mp (short for "maximum price) and a list of toy prices, calledlotp
, and produces a list of all those prices inlotp
that are below or equal tomp
. For example(check-expect (elim-exp 1.0 (list 2.95 .95 1.0 5) (list .95 1.0)) = #true
[10pts] Develop the function
delete
to eliminate specific toys from a list. The function consumes the name of a toy, calledty
, and a list of names, calledlon
, and produces a list of names that contains all components oflon
with the exception ofty
. For example,(check-expect (delete 'robot (list 'robot 'doll 'dress)) (list 'doll 'dress)) = #true
[30pts] A list can be used to represent a finite set. For example,
(list 'c 'o 'm 'p)
represents the set of symbols {'c , 'o, 'm, 'p}. In such a representation, we assume all elements in the list are unique; there are no duplicates. Develop the function
power
that consumes a list of symbolslos
(representing a set) and produces a list of list of symbols representing the power set (set of all subsets) oflos
. Hint: write an auxiliary functioncons-all
that consumes a symbol sym and a list of list of symbolslolos
and inserts symbolsym
at the front of each list inlolos.
For example,
(check-expect (cons-all 'a (list (list 'c) (list 'o) (list 'm) (list 'p)) (list (list 'a 'c) (list 'a 'o) (list 'a 'm) (list 'a 'p))) = #true
...
- 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
value
field is parametric (alpha
) which must be instantiated tosymbol
to match the explication of Binary Search Trees in the book. Your task is to- Give some examples of the
symbol-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 symbol-BSTM
s) - 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
symbol-BSTM
that is well balanced (maximum depth is proportional to the log N where N is the number of keys in thesymbol-BSTM
) and function searches an ordered list of(key value)
pairs represented as two element lists (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
cross
(and supporting functioncross-help
) that consumes anumber-list
and asymbol-list
and produces anumber-symbol-pair-list
where anumber-symbol-pair
is represented by a two elementlist
containing anumber
and asymbol
. - [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-list
s and merges them to form an ascendingnumber-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 functionfastFib
that consumes a natural number inputn
, produces the same answer as thefib
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 in the DrRacket definitions panel. 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 functionfib
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:
Derive a recurrence for
fib(2*m)
in terms offib(m)
andfib(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.
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.
- 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
...