The final exam includes short essay questions, as well as solving problems and tracing execution of algorithms. You will not be asked to write actual code during the exam, but you might be asked to write an algorithm in pseudo-code (e.g., when you are asked to solve a problem using dynamic programming). You might be asked to solve a problem or to develop an algorithm that is a minor variation of an algorithm that was discussed in class (after the midterm test). Majority of the questions will be related to the second half of the course. You are expected to know also what you studied in the first half of this course, if this knowledge is somewhat related to background for the problems that you are trying to solve on the final exam. Pay attention to all algorithms discussed in class after the midterm test.
You have to study your text book and your lecture notes. If you missed a class, ask your peers for copies of their hand written notes. It is strongly recommended to review also problems from all Labs, from Quizzes, from your assignments and the handouts posted on Blackboard: check Documents folder. If you wrote any of the solutions with partners, then make sure you know how to solve the problems yourself. Practice solving independently problems similar to labs and quizzes.
Here are some highlights. You have to know the Big-O upper bound on the running time of all algorithms discussed in class (and Big-Theta bound, when applicable). This knowledge is assumed by default and will not be explicitly listed below.
The matrix chain-product problem. Minimal weight triangulation of a convex polygon and an algorithm that computes an optimal triangulation. Note that recurrences for these two problems are very similar. The algorithms that solve these problems; the running time of the algorithms.
The 0-1 knapsack problem. The general case of the coin change problem. The problem of computing the largest sum in a contiguous subsequence of a numerical array. How to write recurrences for each of these problems. The algorithms that solve these problems; Complexity of algorithms.
Text similarity testing. The longest common subsequence problem (and the related longest common substring problem). Recurrences and examples. The dynamic programming algorithm that solves this problem.
The graph abstract data type. The adjacency list and the adjacency matrix: advantages and disadvantages of these representations. Directed graphs. Simple properties of graphs. Transitive closure algorithm. Topological sorting.
Weighted graphs. Single-source shortest paths (for graphs with positive-weight edges only). Dijkstra's algorithm (the running time analysis is included).
An example of a graph that demonstrates why Dijkstra's algorithm does not work for graphs with negative-weight edges. The Bellman-Ford shortest paths algorithm (read your notes, read slides available from this WWW site).
All-pairs shortest paths. The Floyd-Warshall algorithm: recurrence, complexity.
Minimum Spanning Trees. Problem definition. Kruskal's algorithm. Prim-Jarnik algorithm. Complexity of Kruskal's and Prim-Jarnik's algorithms: analysis of the running time. Correctness of Kruskal's algorithm is excluded.
Text compression. The Huffman coding algorithm. Simple properties of Huffman coding.