Info about the CPS616 final exam

The test will be 2h 30min long. Aids: you can bring 1 page of notes written by your hand. You can use both sides of a page to write your notes, if you like. Write your name and your student number in the top right corner. Photocopies are NOT allowed. Printed notes are not allowed too. You have to hand in the page with your notes at the end of the exam together with your exam paper to the instructor. You cannot use any other aids during the final test. Remember to bring also your Ryerson One card.

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.

  1. Dynamic Programming (DP). The main steps in using the dynamic programming technique. The optimal substructure property. Common types of sub-problems. How to write a recurrence based on the structure of sub-problems of the given problem. Iterative algorithms computing a solution bottom up by reusing solutions to smaller sub-problems. Recursive algorithms with memoization (to avoid repetitions) computing a solution top-down. Similarities/differences between greedy, divide-and-conquer, and DP algorithms. Correctness of algorithms is excluded.

  2. 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.

  3. 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.

  4. 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.

  5. 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.

  6. Weighted graphs. Single-source shortest paths (for graphs with positive-weight edges only). Dijkstra's algorithm (the running time analysis is included).

  7. 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).

  8. All-pairs shortest paths. The Floyd-Warshall algorithm: recurrence, complexity.

  9. 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.

  10. Text compression. The Huffman coding algorithm. Simple properties of Huffman coding.


Be reminded of the following Ryerson policies.
All forms of academic dishonesty are considered serious offences within the university community. It is important that you read and understand the Student Code of Conduct