Exams
Final Exam
The Final Exam is closed-book and closed-notes. In the event of a verifiable medical emergency or other dire circumstance, it is your responsibility to make arrangements for a make-up exam as soon as possible.
The final exam will be held on Wednesday, December 21, 1:00 – 3:00. The exam will be held in the usual classroom.
There is also the option to take the exam early, on Monday, December 19, 9:00 – 11:00 in ITE 231. You must register to take the final exam early.
Exam Topics
Required questions (3) will be taken from the following topics:
- Matroids and Greedy Algorithms
- Properties of matroids; proving whether an object is or is not a matroid.
- Unit-time scheduling (Kozen, p. 230; CLRS, p. 443)
- Amortized Analysis
- Multi-Pop and Increment using all three methods (aggregate, accounting, potential)
- Table-Insert with aggregate and potential method (CLRS, p. 465)
- Table-Insert and Table-Delete with potential method (CLRS, p. 469)
- Binomial and Fibonacci Heaps
- Parallel Computation
- Multithreading model and greedy scheduling
- Analyzing multithreaded algorithms — work, span, parallelism
- Race conditions
- The class NC; proving an algorithm is in NC. Matrix multiplication, binary addition, general prefix sums
Student-choice questions (choose 2) will be taken from the following topics:
- Computational Models
- Max Flow
- Boolean Functions
- Complexity
- Moment generating functions and Chernoff bounds
Previous Undergraduate Exams
- Previous undergraduate exams are available on the CMSC 441 website.