Final Exam Study Guide
CSE 373: Data Structures & Algorithms
Final Exam, Tuesday December 14, 2010.
- 4:20pm in SAV 264 (Our regular lecture room)
- Exam policies
- Closed book, closed
notes. Calculators NOT
- The exam begins
promptly at 2:30pm and ends at 4:20pm.
Topics covered on the Final Exam:
The Final exam is cumulative, although 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
analysis, Big-O. Worst case, upper bound, lower bound, analyzing loops,
- Trees –
- Dictionary ADT
- Binary search trees
– Inorder, preorder, postorder
traversals, insert, delete, find.
- 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.
- AVL trees - Single and
double rotations, insert, find, (NOT delete).
- 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,
operations of merge.
- Disjoint Union/Find -
Dynamic equivalence relations, Up-tree representation, union, find,
weighted union (union by size) and path compression.
memory hierarchy. Temporal and spatial locality. Data structure choice and the memory
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
- Minimum spanning
tree, Prim’s and Kruskal’s
- B-trees. Motivation,
structure, choice of M and L, Insert, Delete.
- Insertion sort, Selection
sort, Heap sort, Merge sort, Quicksort. Lower bound on comparison sorting.
sorting. Stable sorting.
- Bucket sort, Radix
Sample final exam:
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, old midterms, and HW.
- All material from
lecture up to and including sorting is fair game.