There will be five questions on the Final Exam, a two-hour exam. There may also be extra credit portions of some of the questions.

If you have questions about the material in the days leading up to the final exam, contact me by email or in mid-evening at home, 617-244-8261, since I won't be on campus all the time during those days.

Question 1 will deal with sorting. You should be familiar with the code for selection sort, insertion sort, and quicksort. In particular, by studying the code, you should be able to estimate the number of comparisons and/or exchanges required to sort a particular array that I give you. For example, in the improved code for insertion sort on page 276, the while loop will always terminate after one step if the array is already sorted, yielding a linear run time for an already sorted array. Of course, I will give you any code you need, you do not have to memorize and reproduce the code. A typical problem will be to discuss how a given sort deals with an array that is initially sorted or sorted in reverse order or only has a few items out of order.

Question 2 will also deal with sorting. But it will involve a different sorting algorithm than Question 1, but still drawn from the set: selection, insertion, or quicksort. A typical problem here would be show the difference between the simple and efficient insertion sort implementations for a particular example. In both questions 1 and 2 you will be expected to correctly use the concepts of complexity in describing the operations, "Big-Oh" notation.

Question 3 will deal with Heaps. Since you have just been tested on your understanding of fixUp(), used when an item is inserted, the Final Exam will use either fixDown() or the Heapsort code on page 391. As usual, you'll be given the code and asked to discuss it for a particular case.

Question 4 will deal with Binary Search Trees, BSTs, and rotations in particular. There is a separate page of notes about this.

Question 5 will deal with hashing. In particular, linear probing to resolve collisions. You will be given a set of keys and their hash values and a partially filled hash array, already built by linear probing. You will then be asked to work through examples of insert and/or search in the hash table for a given key or keys, using the code in Program 14.4, which I will give you.