Final Exam
- Date
- December 8 - 15, 2016
- Practice
Final Exam Study Suggestions
- Make a list of all of our data structures.
- Make sure you understand the basic function of each. (Is it a special purpose structure or a dictionary?)
- Make sure you understand the implementation issues for each. (Why is it ok to store a heap in an array, but we can’t do that for an AVL tree?)
- Make sure you understand the running times of each of the basic functions.
(For most, this means the running time of
remove
,insert
, andfind
). - Spend a fair amount of time on graph implementations, making sure you understand the tradeoffs between adjacency lists and arrays, and why each of those is better than just an edge list.
- We did the following graph algorithms: traversals — DFS & BFS, MST — Prim’s & Kruskal’s. Make sure you understand running times and implementations of each.
We strongly suggest you get together with 2 other people and just crank through the material mentioned above.