CSE 373 -- Data Structures and Algorithms

Winter 2001

Department of Computer Science and Engineering, University of Washington

Steve Tanimoto (instructor)

Assignment 4

Version 1.0 of February 7.

Search Trees 

Due dates and times: See the section below on "Timing", because some portions of the assignment must be completed prior to the applet deadline. The final applets are due Thursday, February 22, 2001, at 6:00 PM.

Turn in this assignment by filling in the A4 online submission form.

 

Title: Search Trees.

Purposes: (a) continue to develop discussion skills, particularly in talking about the properties of data structures and algorithms, (b) continue teamwork, and (c) develop a more complicated data structure applet.

Instructions:  Do parts A, B, and C.

Part A.  Online communication.

Each student completes an "initial post" during the week of February 5 and at the latest by Monday, February 12 at 6:00 PM. These initial posts are to be done individually and independently -- not as teamwork. The initial posts are to done in INFACT-FORUM by making a REPLY to the question posted by the instructor. Your initial posts will be invisible to everyone else during the initial posting period.

Some time shortly after Monday, February 12 at 6:00 PM, the initial posts will become visible to others within the same groups. Each group should consider the posts of its members and debate the points raised. By the end of the second week, each group is to come up with a consensus answer to the question, plus a "retrospective" account of how the group arrived at its agreed-upon solution. The group solution and retrospective must be posted by Wednesday, February 21 at 6:00 PM. The retrospective should also include a description of what each team member contributed or is contributing to Parts B and C as well as Part A.

Part B.  Applets and documentation.

Each group will produce an applet that implements its assigned technique. The group will investigate the behavioral aspects assigned to it using (1) the book and other resources to be found online, and (2) the applet and data that the group makes up to test and demonstrate the behavior of interest.

The group will also put documentation on the web (on the page with the applet) explaining (a) the technique and the details of how it works, and (b) the special behavior studied.

Part C.  Oral presentation.

Each group should prepare a 5-minute oral presentation. Responsibility for giving the presentation can be assigned to one or two members of the group, but all group members should participate in the planning of the presentation. There should be a rotation in the role of presenter, so that every student gets to give a presentation in the class during the quarter. These presentations are to be given in class or, if sufficient time is not available during class periods, during extra periods to be scheduled.

Topics

There are 4 techniques with 4 approaches to each technique = 16 topics. Each group will be assigned one of these.

Techniques

  • 1. AVL Trees
  • 2. Red-Black Trees
  • 3. B-Trees
  • 4. Splay Trees

    • Possible Assumptions

  • A. Use strings as keys.
  • B. Use numbers (e.g., 12.75) as keys.
  • C. Worst-case behavior is of primary interest.
  • D. Average case behavior is of primary interest.

    • Approaches

  • 1. Use assumptions A and C.
  • 2. Use assumptions A and D.
  • 3. Use assumptions B and C.
  • 4. Use assumptions B and D.
  • Initial posts should respond go the following question: How appropriate are the technique and approach (that your group has been assigned) to the solutions of each of the following two software application problems?

    • Application: Scooter Rental Reservations.

    " The Blue Lake Scooter Rental company has outlets at five locations: Blue Lake, Sunrise Bay, College Green, Main Street, and Silver Mall. It rents out battery powered scooters by the hour, half day or day. The company accepts reservations over the Internet. After handling reservations manually for a year by having reservation agents reading email and then filling out index cards, they have decided to automate. They want to improve their "turnaround time" and so be able to tell a customer immediately if no scooters will be available during the time and at the place they have requested. You've been contacted to develop the data-handling part of their reservations system. For some reason, they don't want to use a standard database system, and they want you to implement a data structure that will normally reside in RAM and process the querying, insertion and deletion of reservations. To what extent can your assigned technique and analysis methods be used for this application? (If you've been assigned the user of numerical keys, think about how the data could be organized in terms of numbers, too., and what might be involved in checking the name field of a record even though the record is stored according to a number. Also, to what extent will it be important to efficiently support insertion, finding, deletion, and printing daily schedules for the 5 outlets in the early morning?"

    Topic Assignments by Group

    • Amber: Technique 1, Approach 1.
    • Beige: Technique 2, Approach 1.
    • Chartreuse: (group now merged with Amber)
    • Dandelion: Technique 3, Approach 1.
    • Emerald: Technique 4, Approach 1.
    • Fuschia: Technique 1, Approach 2.
    • Gold: Technique 2, Approach 2.
    • Hyacinth: Technique 3, Approach 2.
    • Indigo: Technique 4, Approach 2.
    • Jade: Technique 1, Approach 3.
    • Khaki: Technique 2, Approach 3.
    • Lavender: Technique 3, Approach 3.
    • Mauve: Technique 4, Approach 3.
    • Navy: Technique 1, Approach 4.
    • Orange: Technique 2, Approach 4.
    • Purple: Technique 3, Approach 4.
    • Quartz: (group now merged with Purple)
    • Ruby: Technique 4, Approach 4.

    Timing

     Wednesday, February 7: Assignment is posted
  Meet any new group members.
  Begin reading about binary search trees in Sahni, pp.566-599, 601-603.
  Read parts of Chapter 16 as needed for your groups.
  (By February 21, everyone should have read all of Chapter 16.)

 Friday, February 9:
  Begin writing your individual answers to the thought question.
  Work out a work-sharing arrangement for developing your group's
  applet, documentation, and analysis.  Begin following the arrangement.

 Monday, February 12 at 6:00 PM:
  Deadline for posting your individual answers to the thought question.

 Monday evening through Wednesday, February 21:
  In the online forum, debate your answers to the thought question.
  Work on applets, documentation and presentations.

 Wednesday, February 21 at 6:00 PM:
  Deadline for posting your group's concensus answer to the
  thought question, with retrospective.

 Wednesday, February 21:
  Oral presentations.

 Thursday, February 22 at 6:00 PM:
  Deadline for turning in your group's applet(s) and other files 

    Presentation Guidelines:

    (1) prepare a web page with your applet, plus about one page of bullet points to guide your presentation; (2) tell what technique(s) you are using; (3) tell us about the test data you are using to investigate the performance of your technique,  (4) tell us how you are handling deletion; (5) demonstrate your applet but watch the time; (6) explain your findings so far regarding the performance of your technique on your test data and any insights you have gained about hashing.  If your applet has any extra features, explain or demonstrate them.  If your applet is not fully working, then compensate in your talk by going over more of the issues, theory, or math related to your technique.
      The presentations serve many purposes.  They will be a chance for each group to get some feedback on their work so far.  They'll be an opportunity for all of us to gain more insight into the different types of binary search trees.  (Also, they'll count for a small portion of your grades.)