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 or explain the following terms:

• Stable Matching a.k.a. Stable Marriage
• Asymptotic Notation (big-Oh, big-Omega, big-Theta)
• induction
• 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)
• Cook-Levin Theorem
• NP-Complete problems (SAT, VertexCover, IndependentSet, SetCover, 3-Coloring, 3SAT, ...)
• Travelling Salesman Problem (TSP)
• polynomial-time reduction
• polynomial-time verifier
• Approximation Algorithm
• approximation ratio
• minimization problem, maximization problem
• pricing method
• linear programming (LP)
• LP-based approximation algorithms
• Randomized Algorithms
• discrete probability
• random variable
• expected value
• linearity of expectation
• Las Vegas, Monte Carlo algorithms
• Conditional vs Unconditional Lower Bounds
• encoding argument
• communication complexity
• streaming algorithm
• frequency moment

Practice problems

1. Divide and Conquer. (Kleinberg and Tardos 5.1) You are interested in analyzing some hard-to-obtain data from two separate databases. Each database contains n numberical values---so there are 2n values total---and you may assume that no two values are the same. You'd like to determine the median of this set of 2n values, which we will define here as the nth smallest value.
   However, the only way you can access these values is through queries to the databases. In a single query, you can specify a value k to one of the two databases, and the chosen database will return the kth smallest value that it contains. Since wueries are expensive, you would like to compute the median using as few queries as possible.
   Give an algorithm that finds the median value using at most O(log n) queries.
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.
   Design and analyze an algorithm to solve the Subset-Sum problem. Your algorithm should run in O(nW) time.
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. Your algorithm for Subset-Sum runs in O(nW) time. Why does this not give you a polynomial-time algorithm for SSum??
4. 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.

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

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

7. Streaming Algorithms.
   1. Give a randomized streaming algorithm that, given input S = (a₁, ..., a_m), outputs the ith item a_i with probability 2^-i, and outputs NULL with probability 2^-m. Your algorithm should use O(log m + log n) space.
   2. Let p be any distribution on {1,..., m}. (e.g. if X is distrubuted according to p, then Pr[X=i] = p_i.) Give a randomized streaming algorithm that, given input S = (a₁, ..., a_m), outputs the ith item a_i with probability p_i. How much space does your algorithm use?

Home Page