CIS 315 Final Exam Study Guide

The broad topics that you need to focus on for the final exam are listed below. The "example of problems" are exercises from the text (homework problems not explicitly quoted) that you should know how to solve in order to solve the test problems. (While the subjects studied after the midterm will be stressed, the knowledge of the subjects tested by the midterms will be necessary.) Obviously, not all subjects will be represented in the final test.

Loop invariants, proofs using induction (mostly from Chapters 1- 6). Example of problems: Exercises 2.2-3, 2.2-6, 2.2-8, 5.2-1, 5.2-5, Problems 2-1..6.
Recurrence relations (Chapter 4). Example of problems: Exercises 4.2-4, 4.2-5, 4.3-1, 4.3-2.
Sorting methods - heapsort, quicksort, indirect sorting, linear time sorting, lower bounds for comparison based sorting (Chapters 7-9). Example of problems: Exercises 7.1-4, 7.1-5, 7.4-2, 9.1-1, 9.2-5, 9.3-4.
Order statistics (Chapter 10). Example of problems: Exercises 10.3-3, 10.3-8.
Priority Queues (Chapters 20 and 21). Example of problems: Exercises 20.1-3, 20.2-9, 21.3-2, Problem 20-2.
Amortized complexity analysis (Chapter 18). Example of problems: Exercises 18.1-2, 18.1-3, 18.2-2.
Union/Find data structure and applications (Chapter 22). Example of problems: Exercises 22.1-3, 22.3-4, Problem 22-1.
Graph representations, traversals, applications (Chapters 5 and 23). Example of problems: Exercises 5.4-1, 5.4-4, 5.4-5, 5.5-6, 23.1-1, 23.1-3, Problems 5-1, 23-3.
Minimum Weight Spanning Tree algorithms; coloring invariants and coloring rules (Chapter 24). Example of problems: Exercises 24.1, 24.1-5, 24.2-7.
Shortest paths in graphs: single source -- Dijkstra's and Bellman-Ford's algorithms, in directed acyclic graphs, all-to-all -- Warshall's algorithm (Chapters 24-25). Example of problems: Exercises 25.1-7, 25.2-2, 26.1-5, 26.2-7.