This study guide includes topics covered over the entire semester. The final will be cumulative, although weighted towards the second half of the semester. 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, and
• Review lab assignments

---

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

• stable matching
• matching instability
• Gale-Shapley algorithm
• asymptotic notation (big-Oh, big-Omega, big-Theta)
• induction
• proof by contradiction
• recurrence relations
• recursion tree
• substitution method (and partial substitution method)
• 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
• dynamic programming
• memoization
• tabulation
• computational complexity
• intractability
• decision problem
• optimization problem
• complexity classes (P, NP, NP-Complete)
• The Cook-Levin Theorem
• NP-Complete problems (SAT, VertexCover, IndependentSet, SetCover, 3-Coloring, 3SAT, ...)
• travelling salesman problem (TSP)
• polynomial-time reduction
• polynomial-time verifier
• network flow
• augmenting path
• Ford-Fulkerson algorithm
• maximum flow / minimum cut
• approximation algorithm
• approximation ratio
• minimization problem, maximization problem
• linear programming (LP)
• LP-based approximation algorithms
• local search algoriths
• neighborhood in a solution space
• hill climbing / gradient descent
• local optimum / global optimum
• maximum cut
• randomized algorithms
• discrete probability
• random variable
• expected value
• linearity of expectation

Practice problems:

1. Divide and Conquer. (Kleinberg and Tardos 5.2) Recall the problem of finding the number of inversions. As in the text, we are given a sequence of n distinct numbers a₁,a₂,...,a_n, and we define an inversion to be a pair i< j such that a_i > a_j. However, one might feel like this measure is too sensitive. Call a pair a significant inversion if i < j and a_i > 2a_j. Give an O(n log(n)) algorithm to count the number of significent inversions between two orderings.
2. 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.
   The Subset-Sum problem can be solved using a dynamic programming approach where the subproblems use a subset of the elements and a smaller threshold. The dynamic programming table stores in entry (i, j) the solution to the subset sum problem for items {1, ..., i} with threshold j.
   1. Explain how to calculate SubsetSum(i, j), assuming that the table already contains correct answers to all smaller subproblems (i', j'), namely those such that either (i' ≤ i and j' < j) or (i' < i and j' ≤ j).
   2. What is the running time of the dynamic programming algorithm that fills this table for successively larger subsets and thresholds and then returns entry (n, W)?
3. 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. Why does your answer to (b) not pose a contradiction with your dynamic programming algorithm for Subset-Sum (assuming P ≠ NP)?
4. Network flow. (Kleinberg and Tardos 7.45) We are given a set of n countries that are engaged in trade with one another. For each country i, we have the value s_i of its budget surplus; this number may be positive or negative, with a negative number indicating a deficit. For each pair of countries i and j, we have the total value e_ij of all exports from i to j; this number is always nonnegative. We say that a subset S of the countries is free-standing if the sum of the budget surpluses of the countries in S, minus the total value of all exports from countries in S to countries not in S, is nonnegative.

   Give a polynomial-time algorithm that takes this data for a set of n countries and decides whether it contains a nonempty free-standing subset that is not equal to the full set.

5. Approximation Algorithms. (Kleinberg and Tardos 11.4) Given a set A = {a₁, ..., a_n} and subsets B₁, ..., B_m of A, a hitting set is a subset H of A such that for any 1 <= i <= m, H intersects with B_i. In the HittingSet problem, written HS, you're given A and B₁, ..., B_m. Furthermore, each element a_i has an item weight a_i. You must output the hitting set H of minimum cost.

   Give a polynomial time b-approximation algorithm for HS, where b = max_{1 <= i<= n} |B_i|. Hint: Use LP-relaxation.

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

7. Randomized Algorithms. (Kleinberg and Tardos 13.8) Let G = (V,E) be an undirected graph with n nodes and m edges. For a subset of vertices X, let G[X] denote the subgraph induced on X; i.e., the graph whose vertices are X and whose edge set consists of all edges in G with both endpoints in X.
   We are given a natural number k <= n and are interested in finding a set of k nodes that induces a "dense" subgraph of G; we'll phrase this concretely as follows. Give a randomized algorithm that produces, for a given graph G and natural number k, a set X of k vertices with the property that the induced subgraph G[X] has at least [mk(k-1)]/[n(n-1)] edges.

   Your algorithm should have expected polynomial time but always output correct answers. What is the expected running time of your algorithm?

8. Local search. (Kleinberg and Tardos 12.2) Recall that for a problem in which the goal is to maximize some underlying quantity, gradient descent has a natural ``upside-down'' analogue called hill climbing.

   The observations we made about gradient descent carry over to hill climbing: for many problems, you can easily end up with a local optimum that is not very good (that is, it is far from the global optimum). But we saw a problem (finding the maximum cut) for which a local search came with a strong guarantee. We now consider the Bipartite Maximum Matching Problem and find that the same phenomenon happens here as well.

   Consider the following hill climbing algorithm for finding a matching in a bipartite graph: As long as there is an edge whose endpoints are unmatched, add it to the current matching. When there is no longer such an edge, terminate with a locally optimal matching.

   1. Give an example of a bipartite graph $G$ for which this hill climbing algorithm does not return the maximum matching.
   2. Let $M$ and $M'$ be matchings in a bipartite graph $G$. Suppose that $|M'| > 2|M|$. Show that there is an edge $e' \in M'$ such that $M \cup \{e'\}$ is a matching in $G$.
   3. Prove an approximation ratio for this algorithm. (Hint: use part (b).)