CSE 326, Winter 2001.  Final Exam Review

Monday, Mar 12 (2:30-4:20pm).
EE1 037 (same room as lecture).

Closed book.  You will be allowed to bring in one
8.5" x 11" sheet of paper with notes written on it
(both sides of the page).  You may not use magnifying
glasses or similar aids during the exam.


The final exam will emphasize the material from the
course covered after the midterm, but you are responsible
for any material covered in the course.  (Note, for
example, how Project #3 uses ideas from queues, priority
queues, and graphs.)

Please look at the midterm review page for material
covered up to the midterm.  Here's what we covered after
the midterm:


+ Hashing (Ch. 5).  Properties of a good hash function.
Techniques: separate chaining, open addressing (linear
and quadratic probing, double hashing).  Rehashing.
Extendible hashing.  Performance.

+ Heaps (Ch. 6: 6.1-6.3, 6.5).  Binary heaps definition:
structure property, heap order property.  Operations
(insert, deleteMin, decreaseKey, increaseKey, remove,
buildHeap) and their performance.  d-heaps and their
performance.

+ Graph Algorithms (Ch. 9: 9.1-9.3, 9.5, 9.6.1).
Representation of graphs. Topological sort and its
running time.  Shortest path algorithms (unweighted,
Dijkstra (proof of correctness), negative edge weights,
acyclic) and their performances.  Minimum spanning tree
algorithms (Prim, Kruskal), proof of correctness,
and their performances.  Breadth-first search.
Depth-first search.

+ Union/Find Algorithms (Ch. 8: 8.1-8.5).  The data
structure used to implement it.  Union-by-size,
union-by-height, path compression.  Performance.

+ Sorting (Ch. 7).  Simple Algorithms (insertion sort,
selection sort).  Shellsort.  O(N log N) algorithms:
heapsort, mergesort, quicksort.  Performance.  Lower
bound for comparison based sorting.  External sorting
(main idea).

+ Randomized algorithms.  (Depends on how much we cover
in the final week -- stay tuned.)


Things you don't need to know about:
- leftist heaps, skew heaps, binomial queues (6.6-6.8)
- NP-completeness (9.7) -- you'll see this in the
  algorithms course (CSE 421).
- analysis of union-by-rank and path compression (8.6)
- worst-case analysis of Shellsort (7.4.1).
- Multiway merge, polyphase merge, replacement selection
  (7.11.4-7.11.6)


Study tips:

Review your notes, the homework, and the book.  Work on
the suggested homework problems.  As on the midterm, one
or more of the suggested problems will appear in part or
in whole on the final exam.

Be able to "play computer" and perform the various operations
on the data structures.  Look at other problems in the book
to get more ideas for how the data structures and algorithms
can be used or applied.