• CLEARLY PRINT YOUR NAME HERE:

• The exam is closed book, and no calculators, electronic dictionaries, or laptops are permitted, but you are permitted one sheet of 8.5x11" notes (double-sided).

• You have three hours to complete the exam (9:00-12:00)
• There are 10 questions on the exam, worth 10 marks each.
• Answer directly on the exam paper, using the backs of pages if extra space is required.
• Be sure to check your exam to make sure all pages are included: 11 pages including this cover page.

Question	Mark
1. Complexity, Efficiency [10 marks]
2. Skiplists [10 marks]
3. Heaps [10 marks]
4. AVL trees [10 marks]
5. Self-Organizing Lists and Caching [10 marks]
6. Sparse Tables [10 marks]
7. Graph Traversals: DFS, BFS [10 marks]
8. Spanning trees [10 marks]
9. Shortest paths [10 marks]
10. Hash tables [10 marks]
Total [100 marks]