Final Exam Study Guide
CSE 373: Data Structures & Algorithms
Winter 2009

Final Exam, Tuesday March 17, 2009.

• 2:30 - 4:20pm in MUE 153 (Our regular lecture room)

• Exam policies
• Closed book, closed notes. Calculators NOT allowed.
• The exam begins promptly at 2:30pm and ends at 4:20pm.

Topics covered on the Final Exam:

The Final exam is cumulative, although a bit more weight will be given to topics covered since the second midterm.

From Midterm 1 & 2:

• Stacks and Queues, array and list implementations.
• Recursion. Designing algorithms recursively.
• Asymptotic analysis, Big-O. Worst case, upper bound, lower bound, analyzing loops, recurrences, amortized complexity.
• Trees – definitions
• Dictionary ADT
• Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
• AVL trees - Single and double rotations, insert, find.
• Binary Heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
• D-heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
• Leftist Heaps and Skew Heaps - Findmin, Deletemin, Insert. Additional operations of merge, increase, decrease
• Disjoint Union/Find. Up-trees. Weighted union (union by size) and path compression.
• The memory hierarchy. Temporal and spatial locality. Data structure choice and the memory hierarchy.
• B-trees. Motivation, choice of M and L, Insert (no delete).
• Hashing. Properties of good hash functions. Selecting hash table size. Separate chaining and open addressing. Linear Probing, Quadratic Probing, & Double Hashing to resolve collisions. Rehashing.

After Midterm 2:

• Graphs. Directed and undirected. Adjacency list and adjacency matrix representations.
• Topological sorting.
• Graph searching. Depth-first, breadth-first search.
• Shortest paths. Dijkstra's algorithm. Greedy Algorithms.
• Minimum spanning tree: Prim’s and Kruskal’s algorithms.
• Sorting: Insertion sort, Selection sort, Heap sort, Merge sort, Quicksort.
• Bucket sort, Radix sort. Lower bound on comparison sorting. In-place sorting. Stable sorting.

Sample final problems:

• B-tree problem & solution
• Sample Final Exam (note that calculators will NOT be allowed on our exam, Splay trees will not be on our exam)
• Solution to Sample Final Exam

Study suggestions:

• Do concrete problems from the book and re-work problems from lecture, and HW.
• All material from lecture up through sorting is fair game.

---