Class 55: Discussion of Exam 3

Held: Wednesday, May 10, 2006

Summary: Today we discuss possible solutions to examination 3.

Related Pages:

• EBoard.
• Sample Code.

Notes:

• Attendance on Friday is required.

Overview:

• Grading.
• Final.
• Problem 1: Removing from Binary Search Trees.
• Problem 2: Text Analysis.
• Problem 3: Median.
• Problem 4: Genetic Matching.

Grading

• Upon reflection, this was a very hard exam.
• Exams now graded on new scale: 3 is an A, 2 is a B, 1 is a C, 0 is a D
• Homework grades depend primarily on post-midsem homework (B assumed on previous homework)
• How stupid is it to return your grades to you the day before you fill out my evaluation forms?

Final

• The final is scheduled for Friday of finals week.
• You may take it earlier if you obtain the form from the registrar.
• The final will be closed-book, on paper.
  • You may, however, bring one double-sided, hand-written, sheet of notes to the final.
• You can compute whether or not it's worth taking the final.

Problem One: Removing from Binary Search Trees

• Clearly the hardest problem.
• The biggest difficulty may have been with terminology, in that we do two kinds of removal
  • One uses a key
  • One removes a particular node
  • The way you do the two differs
• General strategy:
  • Find the node containing the key, toBeRemoved
  • If there's a right subtree, find the leftmost node in the right subtree, leftMost
    • Copy the key and value from leftMost to toBeRemoved
    • Delete leftMost (by finding its p arent)
• How do you delete leftMost?
  • If leftMost is the right child of toBeRemoved, you update the right child of toBeRemoved
  • Otherwise, you find the parent of toBeRemoved, parent, and make its left child the right child of toBeRemoved
• Pictures on the board.

Problem 2: Text Analysis

• Many of you got this right, but with subtle errors.
• When should you remove a value from unique (or, preferably, a clone of unique)?

Problem 3: Median

• There were some subtle errors in what you do with the pivot and how you recurse on the larger subtree.
• Many of you neglected to document median or to document it well.
• Many of you neglected to gather and analyze steps.

Problem 4: Genetic Matching