CS 22

CS 22 -- Homework 12

Due: Monday, Feb. 18

  1. Read pp. 161-179
  2. Finish Clab 12 (do not hand in--just do it!)
  3. Email solutions and evidence of testing forProfessor K's database. Professor K maintains a database of students in his class as a binary search tree (BST) organized by key value student number. bigdb.txt is such a BST with student numbers and homework grades generated by a random number generator. From time to time students ask Professor K what their homework average is. The kind hearted professor has asked you to implement some procedures to handle this and some other tasks. Fortunately for you (at this point in the course), Professor K is so wonderful that no students ever drop his course nor will you ever have to change an existing record. All you have to do is implement the procedures below. This is still not simple so start this assignment earlier than the previous ones and make sure you use abstraction barriers. findbykey should be fast because it should exploit the BST property. findbyname will have to possibly look at every node and will not be as fast.
    1. ;;;addrec returns a BST that has the student record nrec inserted
      ;;;properly to maintain the BST property
      (define (addrec nrec tree)
    2. ;;;findbykey searches for a record with key value kval in the BST tree
      ;;; that is organized by key values. If the search is succcessful,
      ;;; findbykey returns the entire record. Otherwise, the empty list is returned.
      (define (findbykey kval tree)
    3. ;;;findbyname searches for a record with name value nam in the BST tree
      ;;; that is organized by other key values. If the search is succcessful,
      ;;; findbyname returns the entire record. Otherwise, #f is returned.
      (define (findbyname nam tree)
    4. ;;;namesfromyear returns a list of names of the people in the BST tree
      ;;; that have year value of yr
      (define (namesfromyear yr tree)
    5. ;;;hwavg returns the name and average of the grades
      ;;; associated with hw1 and hw2 in the
      ;;;record of the student with student number stuno from the BST tree
      (define (hwavg stuno tree)