Final Exam Study Guide
CSE 373: Data Structures & Algorithms
Midterm 3 (a.k.a. Final Exam), Friday December 11, 2009.
- 1:30pm in GLD 322 (Our regular lecture room)
- Exam policies
- Closed book, closed
notes. Calculators NOT
- The exam begins
promptly at 12:30pm and ends at 1:30pm.
Topics covered on the Midterm 3:
The Midterm 3 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.
- Trees – definitions
- Dictionary ADT
- Binary search trees – Inorder, preorder, postorder traversals, insert, delete, find.
- AVL trees - Single and double rotations, insert, find.
- B-trees. Motivation, structure, choice of M and L, insert/delete.
- Binary Heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
- D-heaps - Findmin, Deletemin, Insert. Additional operations of increase, decrease, buildheap.
- 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, Extendible Hashing
- Sorting: Bubble Sort, Insertion sort, Selection sort, Heap sort, Merge sort, Quicksort. Lower bound on comparison sorting. Bucket sort, Radix sort.
After Midterm 2
- Disjoint Union/Find: Dynamic equivalence relations, Up-tree representation, union, find, weighted union (union by size) and path compression.
- Graphs. Directed and undirected. Adjacency list and adjacency matrix
- 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.
- Netwrk Flow: Definition, Residual Graph, Ford-Fulkerson Method, Minimum Cuts.
Sample Midterm 3:
Links to previous exams (copied from the Midterm 1 and Midterm 2 pages):
- Do concrete problems
from the book and re-work problems from lecture, and HW.
- All material from
lecture up through Network Flow is fair game.