CIS 315 Spring 2008
Final Exam
Study Guide
The final will take place on Tuesday at 10:15 in 109 Deady. Only the text (Cormen et al.) and one page of notes will be allowed. The subject of the test will be the material covered in lectures (which includes that already tested on the midterm and detailed in guide to midterm exam). The problems may include the following concepts.
- Implementations of disjoint set families ("Union/Find");
- Amortized complexity: argue for amortized complexity of some simple tasks like, for instance,
- incrementing binary counter,
- updating dynamic tables,
- consolidating lazy binomial heaps;
- use of credit invariant;
- Divide-and-Conquer algorithm design paradigm:
- Master method to solve recurrence equations;
- matrix multiplication;
- integer multiplication;
- searching and sorting;
- Graph Traversals:
- definition, properties;
- graph connectivity properties;
- applications (2-SAT).
- Abstract complexity:
- classes P, NP, NPC;
- simple poly-time reductions;