## Final Exam Study Guide CSE 326: Data Structures Winter 2006

#### Location: EE1-105 (Note this is different than the regular exam slot and location.)

• Exam policies
• Closed book, closed notes. Calculators allowed (not sure they will be useful for anything but you may use one if desired)
• The exam begins promptly at 12:30pm and ends at 2:20pm.

Topics covered on the Final Exam:

Pre-Midterm:

• 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
• Binary Heaps, 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
• Binomial Queues - Findmin, Deletemin, Insert. Additional operations of merge, increase, decrease.
• Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
• AVL trees - Single and double rotations, insert, find.
• Splay trees - Splaying, insert, find.

Post Midterm:

• 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.
• Disjoint Union/Find. Up-trees. Weighted union (union by size) and path compression.
• Sorting. Insertion sort, Selection sort, Heap sort, Merge sort, quicksort.
• Bucket sort, Radix sort. Lower bound on comparison sorting. In-place sorting. Stable sorting.
• Topological sorting.
• Graph searching. Depth-first, breadth-first search, best-first search.
• Shortest paths. Dijkstra's algorithm. Greedy Algorithms.
• Minimum spanning tree: Prim’s and Kruskal’s algorithms.

• Study suggestions:

• Do concrete problems from the book and re-work problems from lecture, section, and HW #1-3. I would focus on those examples but if you would like some more problems to look at here are some suggestions from the book:

From midterm study guide:

• Chapter 2: 2.6, 2.10.
• Chapter 3: 3.21, 3.22, 3.23 (a).
• Chapter 4: 4.1, 4.2, 4.8, 4.9, 4.22, 4.27, 4.28.
• Chapter 6: 6.2, 6.3, 6.26, 6.30.

For material covered since the midterm:

• Chapter 5: 5.1, 5.10, 5.11.
• Chapter 7: 7.1, 7.15, 7.19, 7.39; 7.48.
• Chapter 8: 8.1, 8.2.
• Chapter 9: 9.20, 9.53.

All material from lecture up through Minimum spanning trees is fair game.

cse326-request@cs.washington.edu (Last Update: 03/02/06 )