The final exam is Tues Dec 8, 8-10 AM. It is in our normal classroom. The format for the exam will be very similar to the previous two exams (but with different content). The final is cumulative so anything from the entire course can be on the exam. Having said that, roughly 60%-70% of the questions will be from material from Day 30 through the end of the course (this is material that did not appear on Exam 1 or Exam 2).
Similar to the last two exams, I am likely to ask you questions where you write some pseudocode implementing a method on a data structure. For example, implement extract_min on an unbalanced binary search tree but I require you to do so in a persistent way. Or something like Exercise 9..10 from the book (which is similar to the join method we wrote for treaps). Or maybe something like count_positive from exam 2, but instead of a list implement it on a binary tree.
It is likely there will be a question where I give you a data structure and ask you to describe something about it. (On exam 2 I asked you to describe the memory usage and deallocation for the doubly linked list.) This could be from red-black trees or B-trees. A google search turned up this review from a different university but it has good questions. For example, question 8 on why a black node with one child must have a red child (think about nil nodes).
Try not to look at the following and do it yourself, but here I will give you the solution to writing a count_positive method on a binary tree.
Say the struct I gave you was:
struct StringIntTree {
struct Node {
shared_ptr<Node> left;
shared_ptr<Node> right;
string key;
int val;
};
shared_ptr<Node> root;
};The problem is to write a count_positive method which counts the number of values which are positive. The solution is as follows:
int count_helper(shared_ptr<Node> n) {
if (!n) {
return 0;
}
int leftCount = count_helper(n->left);
int rightCount = count_helper(n->right);
if (n->val > 0) {
return leftCount + rightCount + 1;
} else {
return leftCount + rightCount;
}
}
int count() {
return count_helper(root);
}