- Review your lecture notes
- Review lecture videos on Panopto
- Look over assigned readings from the textbook
- Review previous homeworks,
- Review previous tests, and
- Review lab assignments

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

**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_{1},a_{2},...,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)) algoirthm to count the number of significent inversions between two orderings.**Recurrence Relations.**Solve the following recurrence relation.

T(n) = 2T(n/2) + 2n^2, T(1) = 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 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.

**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.- Show that
**SSum**is**NP-Complete**. - Show how to solve
**SSum**using your solution for Subset-Sum. - 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.- Show that
**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:- Start with S equal to the empty set
- While some node remains in G
- Pick the heaviest remaining node v.
- Add v to S
- Delete v and all its neighbors from G

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