Final Exam Study Guide
CSE 326: Data Structures
Winter 2006
Final Exam, 12:30-2:20 p.m. Saturday, March 11, 2006 (Both sections)
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:
- Linked lists. Simple
linked lists, doubly linked lists, circularly linked lists.
- 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.
- Dictionary ADT
- 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.
- Graphs. Directed and
undirected. Adjacency list and adjacency matrix representations.
- 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.
- 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.