**COM 1201 Algorithms and Data Structures 2**

**
Notes on the Final Exam **

**To be given Wednesday, March 15th, 1pm**

#### Winter 2000 -- Professor Futrelle

College of Computer Science, Northeastern U., Boston, MA

#### (Version of 3/11/00)

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.