This study guide includes topics covered over the entire semester. The final will be cumulative. This study guide is intended to be comprehensive, but not guaranteed to be complete.

In addition to using this study guide, you should:

• Review your lecture notes
• Look over assigned readings from the textbook
• Review previous homeworks,
• Review previous tests, and
• Review lab assignments

You should be able to define or explain the following terms:

• Stable Matching a.k.a. Stable Marriage
• Asymptotic Notation (big-Oh, big-Omega, big-Theta)
• induction
• directed, undirected graphs
• breadth-first search, depth-first search (BFS/DFS)
• bipartite graph
• cycle
• connected component
• topological ordering
• spanning tree
• Minimum Spanning Tree (MST)
• Kruskal's/Prim's Algorithms
• Greedy Algorithm
• stays-ahead method
• exchange argument
• Divide and Conquer
• Recurrence Relation
• Recursion Tree
• Substitution/Partial Substitution
• Dynamic Programming
• memoization
• tabulation
• Network Flow
• Residual Graph
• Ford-Fulkerson Algorithm
• minimum s-t cut
• computational complexity
• intractability
• decision problem
• optimization problem
• complexity classes (P, NP, NP-Complete)
• Cook-Levin Theorem
• NP-Complete problems (SAT, VertexCover, IndependentSet, SetCover, 3-Coloring, 3SAT, ...)
• polynomial-time reduction
• polynomial-time verifier
• Approximation Algorithm
• approximation ratio
• minimization problem, maximization problem
• pricing method

Practice problems

Note: The problems below should take much more than three hours to complete. They are not indended to represent a sample final exam. Consider them good practice and good preparation for the final.

1. Divide and Conquer. Consider an n-node complete binary tree T, where n=2^h-1 for some h. Each node v in T is labeled with a unique real number x_v. A node v in T is a local minimum if for all neighbors w of v, we have x_v < x_w.
   Access to vertex labels is restricted; you can only see the node labels by probing the node. Your goal is to find a local minimum using the fewest number of probes possible. Given a complete binary tree T, design an algorithm findmin(T) to find a local minimum using O(log(n)) probes to the nodes of T.
2. Recurrence Relations. Solve the following recurrence relations.
   1. T(n) = 2T(n/2) + 2n^2, T(1) = 3
   2. T(n) = 4T(n/2) + 2n^2, T(1) = 3
   3. T(n) = 5T(n/2) + 2n^2, T(1) = 3
   
   
3. Dynamic Programming. In the Subset-Sum problem, you are given n items {1, ..., n}. Each item has a nonnegative integer weight w_i. You are also given an integer weight threshold W. For a subset of elements S, define w(S) to be the sum of w_i, taken over all i in S. Your goal is to output the set S that maximizes w(S), subject to w(S) <= W.
   Design and analyze an algorithm to solve the Subset-Sum problem. Your algorithm should run in O(nW) time.
   
   Note:To get full credit, you only need to give a "short form" solution; i.e., you only need to define the table your dynamic program will use, show how to use it to solve Subset-Sum, and show how to compute each table entry recursively, using smaller table entries. For example, if you needed to solve the Steel-Rod Problem, the following solution is sufficient for full credit:
   • Let R[0...n] be a one-dimenstional table, such that R[k] is the maximum revenue obtainable from a k foot rod.
   • We wish to output R[n].
   • R[0] = 0, and for k>0, R[k] = max {P[j] + R[k-j]}, where the maximum is taken over all 1<=j<=n.
   Of course, showing any intuition or work will maximize your chances of getting partial credit.
4. Intractability. Consider the following decision-version of Subset-Sum, which we'll call SSum. In this version, you're given n items {1,..., n} with item weights w_i, and a weight threshold W, and you must output YES iff there exists a subset whose item weights total exactly W; i.e., if there is S such that w(S) = W.
   1. Show that SSum is NP-Complete.
   2. Show how to solve SSum using your solution for Subset-Sum.
   3. Your algorithm for Subset-Sum runs in O(nW) time. Why does this not give you a polynomial-time algorithm for SSum??
   Note: This problem is more work than is reasonable for a three hour exam. If you can complete and understand this problem, you should be well-prepared for any NP-Complete problems that might appear on the final exam.
5. Approximation Algorithms. (Kleinberg and Tardos 11.10) Suppose you are given an n by n grid graph G. Associated with each node v is a weight w(v), which is a nonnegative integer. You may assume that the weights of all nodes are distinct. Your goal is to choose an independent set S of nodes of the grid so that the sum of the weights of the nodes in S is as large as possible. Consider the following greedy algorithm for this problem:
   1. Start with S equal to the empty set
   2. While some node remains in G
      • Pick the heaviest remaining node v.
      • Add v to S
      • Delete v and all its neighbors from G
   3. Return S

   First, let S be the independent set returned by this algorithm, and let T be some other independent set in G. Show that for each node v in T, either v is in S, or v is adjacent to some v' in S with w(v') >= w(v).

   Show that this algorithm returns an independent set with total weight at least 1/4 of the maximum total weight of an independent set.

Home Page