Class 55: Discussion of Exam 3

Back to Scheme, Revisited. On to Evaluation and Wrapup.

Held: Wednesday, May 10, 2006

Summary: Today we discuss possible solutions to examination 3.

Related Pages:

Notes:

• Attendance on Friday is required.

Overview:

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

• 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

Back to Scheme, Revisited. On to Evaluation and Wrapup.

Disclaimer: I usually create these pages on the fly, which means that I rarely proofread them and they may contain bad grammar and incorrect details. It also means that I tend to update them regularly (see the history for more details). Feel free to contact me with any suggestions for changes.

This document was generated by Siteweaver on Wed May 10 08:47:03 2006.
The source to the document was last modified on Thu Jan 12 14:58:07 2006.
This document may be found at `http://www.cs.grinnell.edu/~rebelsky/Courses/CS152/2006S/Outlines/outline.55.html`.

You may wish to validate this document's HTML ; ; Check with Bobby

Samuel A. Rebelsky, rebelsky@grinnell.edu