The exam will consist of a few multiple choices conceptual questions, one free response question that will be hand graded when the exam is over, and one programming question. The exam will cover content up to and including Wednesday, September 9 and does not include the stack or the queue.
The free response question will test your understanding of Big O in the context of List implementations. You will be expected to state the best Big O for the implementation you are given and then justify your claim in about a paragraph of full-sentence text. The implementations will be minor modifications of the core implementations seen in class.
When preparing and practicing for the FRQ, consider the following rubric as a loose approximation of the actual grader rubric:
| Points | Rubric Item | Description |
|---|---|---|
| 2 | Overall Big O is correct | The answer has the best correct Big O for the overall problem |
| 3 | Minimum necessary steps described | The explanation correctly describes all steps needed to solve the problem. This can be done either by writing a full recursive pseudo-code for a Tree problem (including base case, recursive step, combining step) or explaining the algorithm in plain English. |
| 1 | Individual Step Big O is correct | The explanation correctly describes the Big O of all steps. (To receive points, you must receive full credit for the minimum necessary steps) |
| 2 | Explanation of how the ‘twist’ affects Big O | Each problem has at least one adjustment beyond the core data structure. Your answer should explicitly state how these changed parameters / structural requirements affected (or didnt affect) the runtime. |
| 1 | Answer is given in complete sentences | Even when practicing, write in full complete sentences. |
| 1 | Answer has appropriate structure | Start with a clear declaration of Big O. On a new line state the steps and their Big Os explicitly. Then start a new paragraph where you explain why. Make it easy for your peer graders (and later real graders) |
The programming question will require writing complete and correct C++ code. 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.
Topics Covered:
Assignments referenced:
Points: 80
Registration: Thursday, September 03
Start: Wednesday, September 16
End: Friday, September 18