Final Exam

Date

December 8 - 15, 2016

Practice

• sp10
• fa09
• sample1
• sample2
• su05 solution
• sample1 solution
• sample2 solution

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, and find).
• 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.