Page History

...

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

• 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 
  • .   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.
      
      
    Each of these five subtasks, except for the collection of test cases takes only a few lines.  A good set of test cases might take as many as 10 lines.
    
    
  1. [10 pts] Develop the function count-symbols that consumes a list of symbols and produces the number of items in the list.
  2. [10 pts] Develop the function count-numbers that counts how many numbers are in a list of numbers. 
  3. [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 of average-price very easy.  If the list of toy prices is empty, the function avg-price produces an error message as described in Guidance below 
  4. [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, called lotp, and produces a list of all those prices in lotp that are below or equal to mp. For example
     

     (check-expect (elim-exp 1.0 (list 2.95 .95 1.0 5) (list .95 1.0)) = #true

      

  5. [10pts] Develop the function delete to eliminate specific toys from a list. The function consumes the name of a toy, called ty, and a list of names, called lon, and produces a list of names that contains all components of lon with the exception of ty. For example,

     (check-expect (delete 'robot (list 'robot 'doll 'dress)) (list 'doll 'dress)) = #true

      

  6. [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 symbols los (representing a set) and produces a list of list of symbols representing the power set (set of all subsets) of los.  Hint: write an auxiliary function cons-all that consumes a symbol sym and a list of list of symbols lolos and inserts symbol sym at the front of each list in lolos. 

     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

...