The exam will consist of multiple choice questions, one free response question, and one coding question. It will require programming complete and correct C++ programs. Partial credit will only be given for working, compilable code that passes some test cases. Code that doesnt compile will not receive any credit. Multiple (but not unlimited) submissions will be allowed.
The programming question will be on using and implementing heaps.
The free response question will require you to outline a proof behind the efficiency of a core data structure seen thus far. While you will not be required to write a full formal proof, you will be tested on understanding the core ideas behind the proof itself such as key equations or properties of the data structure used in the proof itself. This can include any previously seen data structure in CS 225.
To give some additional guidance, you are strongly encouraged to look at past lectures titled ‘Analysis’ as each contains a proof of interest. This includes Amortized List Analysis, AVL Tree Analysis, BTree Analysis, Heap Analysis, and Disjoint Set 2 (Analysis). You will not be asked details about the amortized rank with path compression proof as we did not have time to cover it in sufficient detail.
The content on the exam may cover all lecture material up through (and including) October 25. Notably, this means graph fundamentals and implementations are valid but traversals and graph algorithms are not.
Points:60
Registration: Thursday, October 31
Start: Wednesday, November 13
End: Friday, November 15