CSE 373, Autumn 2001.

Final Exam Wednesday, Dec 19 (8:30-10:20am)

Closed book, one 8.5"x11" page (both sides) of notes.

The final exam will cover material from Chapters 1 through 9 in the Weiss book, along with any other material discussed in class, or that appeared on the homework and/or programming assignments.

Material you should know:

Everything listed in the midterm review.

Heaps:

• Definition, basic operations (deleteMin, insert).  How they are implemented.

• other operations (findMin, increaseKey, decreaseKey, remove, buildHeap)

• d-heaps: definition, running times for heap operations with d-heaps

Optimal binary search trees

• Why do we want to build such a data structure?

• Finding an optimal tree

• Probabilty-balanced trees

Graphs

• Topological sort: know what the algorithm is supposed to do, know how it does it, when it cannot produce a topological ordering, and its running time.

• Shortest path algorithms: know how the algorithms work, why they are correct, and how to analyze the running times (not just the bottom-line running time)

  • unweighted: breadth-first search

  • weighted, non-negative weights: Dijkstra's algorithm

  • weighted, negative weights: Bellman-Ford algorithm (Weiss, section 9.3.3)

  • acyclic graphs: essentially topological sort

  • Why is the notion of a negative-cost cycle an important concept?

• Minimum spanning tree algorithms: again, know how the algorithms work, why they are correct, and how to analyze the running times.

  • Prim's algorithm

  • Kruskal's algorithm

• What kinds of applications are these algorithms useful for?

Union/Find algorithms

• What the dynamic equivalence problem is

• Basic data structure to support the union and find operations: uptree

• union-by-size, union-by-height

• path compression when doing find

• How the data structure is used in Kruskal's MST algorithm

Sorting

• insertion sort

• selection sort

• heapsort

• mergesort

• quicksort

• lower bound for comparison-based sorting algorithms

• breaking the Omega(N log N) lower bound: bucket sort

• external sorting using mergesort

• Think about the various criteria for goodness of a sorting algorithm: Does it use any extra space?  How fast does it run in the worst case?  Average case?  How well does it perform on special kinds of input (for example, already sorted input)?

• Think about why quicksort performs better in practice than heapsort, which performs better than mergesort, even though they are all O(N log N) algorithms (in the average case).

Material NOT covered on the final exam:

• Everything listed in the midterm review as not being covered, except that you should now know a little bit about infix to postfix conversion if you did this in project 3.

• Shellsort (section 7.4)

• Indirect sorting (section 7.8)

• More advanced external sorting algorithms (sections 7.11.4-7.11.6)

• Worst case analysis of union-by-rank and path compression (section 8.6)

• Maze application example (section 8.7), although it is a fun example worth reading about

• The second part of section 9.3.4, where Weiss discusses critical path analysis.  (Again, useful material.)

• Network flow problems (section 9.4)

• Applications of depth-first search (section 9.6)

• NP-completeness (section 9.7)

Tips for studying:

Review definitions and general concepts.  Think about why we need various data structures.  (Why do we even want to have a priority queue? Or a graph?)  Work through examples of how the various data structures work.  Review the analysis for why the algorithms work correctly and why they run in the time they run. (Why does Kruskal's algorithm work?)

Briefly review your programming projects.  Think about the design decisions you needed to make.  What criteria did you use to make those decisions?

Review your homework.  For the problems that required a little analysis or a little more complicated reasoning, make sure you understand the parts of the solution and how they fit together.

Work on some suggested problems (as though they were exam problems) to see if there are gaps in your understanding.  If there are, then go back to the previous steps.

Carefully construct a notes sheet for the exam.  Be selective.  You can't include the whole book.  Things you might want to include: "memorization" types of information, such as what you are supposed to do in a splay or AVL tree in the zig-zig and zig-zag cases.  Or what double hashing is versus rehashing.  Or the code to buildHeap.  Concepts or ideas that you feel are difficult for you to understand.  Anything that you think you might have difficult remembering in an exam situation.