Algorithm Design, Analysis & Complexity, Winter 2017
This webpage will be populated with brief descriptions of actual material covered in lectures in reverse chronological order. This webpage will be frequently updated.
| Date | Description of Lecture |
|---|---|
| Apr 5 | Last lecture. Discussed the final exam. DP algorithm for TSP (small correction: the final answer is stored in min(D[V,i] + w(i,s)), not D[V,s], since we assume that s in S when we define D[S, j] and j is not equal to s), 2 approximation algorithm for Steiner Tree Problem on Graphs, dynamic programming solution to a pebbling problem. |
| Apr 3 | A lecture on various unconventional computers and algorithms. You can find slides here (warning: large file (~30mbs)). Advanced tutorial covered an approximation algorithm for k-centers problem. Regular tutorial covered FPTAS for the knapsack problem. EDIT (April 5, 2017): tutorial notes (from Vazirani's book: Approximation Algorithms). |
| Suggested exercises for approximation algorithms: read and understand CLRS chapter 35 in its entirety, CLRS 35-1, 35-2, 35-3, 35-4, 35-6. | |
| Mar 31 | Subset Sum optimization version. Exact exponential time algorithm for Subset Sum. The FPTAS based on trimming operation. Proof of the approximation ratio, analysis of runtime. A greedy approximation algorithm for Set Cover problem. Proof of (log m + 1) approximation ratio, where m is the size of the universe. |
| Mar 29 | Approximation algorithms continued. Definition of Max-3SAT. Randomized 8/7-approximation algorithm for Max-3SAT. Derandomization of this algorithm via the method of conditional expectations. Weighted vertex cover (WVC). Formulation of WVC as an integer program. Relaxation to the linear program + rounding gives a polynomial time 2-approximation algorithm for WVC. |
| Mar 27 | Coping with NP completeness. Approximation algorithms. Definition of approximation ratio for maximization and minimization problems. 2-approximation algorithm for vertex cover. Approximating TSP within a constant factor is not possible unless P = NP. Special case of TSP -- TSP with triangle inequality. 2-approximation algorithm for TSP with triangle inequality. EDIT (April 5, 2017): tutorial notes (borrowed from University of Maryland, College Park) |
| Suggested exercises on complexity theory: read and understand CLRS chapter 34 in its entirety. The following problems are elementary: solving each of them should not take more than 5 minutes given that you understand the material: 34.1-2, 34.1-3, 34.1-4, 34.1-5, 34.1-6, 34.2-1, 34.2-3, 34.2-5, 34.2-8, 34.2-10, 34.3-3, 34.3-7, 34.5-7, 34.5-8. | |
| Mar 24 | Classes co-NP and co-NPC. Exercise: P subset of NP intersection co-NP. Conjectured relationships: co-NP is not equal to NP, co-NP intersection NP is not equal to P. Venn diagram of this conjectured relationship between classes. Definition of a canonical search problem for decision problems in NP. Definition of self-reducibility. Examples: 3-SAT, k-clique, hamiltonian cycle, TSP, vertex cover (not all were done in class, those that were not done in class are left as exercises). |
| Mar 22 | Subset sum is NP-complete. Decision version of knapsack problem is NP-complete. Partition is NP-complete: exercise. |
| Mar 20 | Continued reductions and proofs of NP-completeness. Vertex cover - definition, example, decision problem, language. Proof of NP-completeness of vertex cover. Hamiltonian cycle - definition, simple example + more involved example (graph of dodecahedron), decision problem, language. Hamiltonian cycle is NP-complete - stated as a fact in the lecture (see CLRS for a proof). Hamiltonian path - definition, example. Proof that Hamiltonian path is NP-complete. Recalled travelling salesman problem (TSP). Proof that TSP is NP-complete. EDIT (April 5, 2017): tutorial notes |
| Mar 17 | Finished proof of NP-completness of L_3-SAT. Detailed example. Definition of a clique. Clique decision problem. Clique language. Proof that L_clique is in NP. Proof that L_clique is NP-hard via a reduction from L_3-SAT. See CLRS 34.5.1. |
| Mar 15 | Circuit satisfiability problem. Proof that circuit satisfiability is NP-complete. This is the first and only problem for which we need to argue NP-hardness directly. Once we have circuit-sat NP-complete, we can conclude other problems are NP-complete via polytime reductions. We discussed this strategy, and applied it to show 3-SAT is NP-complete. Read CLRS 34.1-34.4. |
| Mar 13 | Class P. Class NP. Million dollar question: does P = NP? Examples of languages in P and NP. Definitions of Boolean variable, literal, clause, CNF formula, k-CNF. Satisfiability of k-CNF is in NP. Exercise: prove that satisfiability of 2-CNF is in P. Decision version of shortest path is in P. Decision version of MST is in P. Decision problems corresponding to 3-SAT, longest path, traveling salesman problem are not known to be in P and believed to not be in P. Polytime reductions. Definitions of NP-hard, NP-complete problems. Class NPC. If L1 reduces to L2 in polytime and L2 in P implies L1 in P. If L in NPC and L in P, then P = NP. Term test 2 held during the tutorial. |
| Some students requested simplex practice problems. I compiled a small collection of such problems. Warning: I haven't solved them to check that you get "nice" numbers, but the problems are taken from trusted resources. Let me know if you find any problems with problems. | |
| Mar 10 | Briefly discussed upcoming term test. Solutions to Q3,Q4(e), and Q5 from A2. The written up sample solutions have been posted on the assignments webpage. The solutions are provided as is. Please, let me know if you find any typos or bugs. |
| Mar 8 | Complexity theory. Optimization problem. Decision problem. Reducing one to another. Formal languages. Correspondance between decision problems and formal languages via "reasonable" encodings. Class P - class of efficiently solvable decision problems. Class NP - class of problems for which a given solution can be verified efficiently. |
| Mar 6 | Finishing up Simplex. Extended example. Definitions of basic, nonbasic variables. Basic solution. Pivoting. Geometric interpretation. How to solve LPs with negative b-entries. Degeneracy of a vertex. Cycling. Bland's Rule. Running time of Simplex. See CLRS 29.3-29.5. EDIT (Mar 10): see Colin's notes for the material covered in regular tutorial. Advanced tutorial covered derivation of max-flow min-cut theorem from strong duality. See Luca Trevisan's notes here. |
| Suggested problems for week 8: CLRS 29.1-4, 29.1-5, 29.1-6 (use Farkas Lemma introduced in class), 29.1-7, 29.1-8, 29.1-9, 29.2-3, 29.2-7. | |
| Mar 3 | LP duality continued: implications of weak duality. Statement and proof of strong duality. High level description of the simplex algorithm. Definition of a vertex of a polytope. Definition of neighboring vertices. Specification of simplex in the special case: b >= 0. Convenient notation for the slack form. Basic and nonbasic variables. If you would like to read ahead, see CLRS 29.3-29.5 |
| Mar 1 | LP application: Min-Cost Flow Problem. 2 popular LP forms: standard/canonical and slack. Useful transformations of LP fomulations: (1) changing min. into max. and vice versa, (2) changing equality into inequalities, (3) changing inequality into equality and nonnegativity, (4) changing unconstrained variable into two constrained variables. Duality: motivating example, definition of a dual, weak duality theorem, a version of Farkas lemma. |
| Feb 27 | Introduction to Linear Programming (LP): linear function, linear constraints, feasible solution, feasible region, matrix representation of LPs, polyhedron, polytope, infeasible LP, unbounded LP, complexity of LP - polytime methods (interior point, ellipsoid), Simplex algorithm, applications: shortest s-t path, max-flow. Reading: CLRS 29.1, 29.2. Regular tutorial: CLRS 26-2 (Minimum Path Cover). Advanced tutorial: CLRS 26.4 (Push-Relabel Algorithm). |
| Feb 20-26 | Reading week. No classes. |
| Suggested problems for week 6: 26.1-3, 26.1-6, 26.1-7, 26.2-6, 26.2-9, 26.2-11, 26.2-13, 26-1. | |
| Feb 17 | Last lecture on network flows. Discussion of different polytime algorithms for network flows. Lemma: a flow network with integral capacities admits a maximum flow that is also integral. Simple application of max-flow: multi-source multi-sink max flow. Definition of a bipartite graph, matching. One of the most famous and importnat applications of max flow: maximum bipartite matching. Correctness, runtime. See CLRS 26.3. |
| Feb 15 | Continued network flows. Larger example of FF running on a flow network. Discussion of runtime of FF. Case of arbitrary capacities. Case of integral capacities. Polynomial time algorithm based on FF - Edmonds-Karp. Proof of O(|V| |E|^2) runtime of Edmonds-Karp. See CLRS 26.2. |
| Feb 13 | Continued network flows. Definition of residual capacities, residual graph, augmenting path, capacity of augmenting path. Pseudocode for Ford-Fulkerson method. Detailed example. Definitions of (s,t)-cut, flow across a cut, capacity of a cut. Flow across every cut is equal to the value of the flow. Flow value is at most capacity of a cut. Main theorem of flow networks: Max-Flow Min-Cut Theorem. See CLRS 26.1, 26.2. Regular tutorial covered linear-time algorithm for finding strongly connected components - CLRS 22.5. Advanced tutorial covered the notion of tree decomposition and treewidth - see KT 10.4. |
| Suggested problems for weeks 4-5 (not to be handed in): given adjacency list of graph G = ([n], E) sort all the lists in time O(n + |E|). Review BFS, DFS, Kruskall's algorithms. Prove facts about trees: tree on n nodes has n-1 edges, any connected undirected graph with |E|=|V|-1 is a tree, an undir graph is a tree iff there is a unique path between any pair of nodes. Realize Bellman-Ford as a DP algorithm: semantic array, syntactic array, etc. Write pseudocode for Floyd-Warshall that uses only O(|V|^2) memory. CLRS 22.1-1, 22.1-3, 22.2-8, 22.3-2, 22.3-7, 23.1-1, 23.2-2, 24.1-3, 24.1-4, 24.3-6, 25.2-6, 25.3-6. | |
| Feb 10 | Continued all-pairs shortest path. Improvement for sparse graphs - Johnson's algorithm. Reweighting procedure. Analysis of correctness, runtime. See CLRS 25.3. Started network flows. Definition of a network graph. Definition of network flow, flow value. Example. High level idea of the proof based on local search. Ford-Fulkerson method. Description of augmenting paths, residual graph. See CLRS chapter 26. |
| Feb 8 | Continued single-source shortest path. Bellman-Ford algorithm to handle negative-weight edges (still assuming no negative-weight cycles) - correctness, pseudocode, runtime (see CLRS 24.1). Modification of Bellman-Ford to detect presence of negative-weight cycles reachable from the source. All pairs shortest paths problem. Possible approaches and their runtimes - Bellman-Ford, Matrix Multiplication (see CLRS 25.1). Floyd-Warshall dynamic programming algorithm (see CLRS 25.2) - semantic, computational arrays, equivalence, runtime. |
| Feb 6 | Started shortest path algorithms in graphs. Single-source shortest paths problem. Key observations: negative-weight cycle reachable from source leads to an ill-defined problem, may assume shortest paths are simple, the problem admits optimal substructure property. Special special case: unitary weights - can be solved by BFS. Slightly less special case: positive weights - can be solved by Dijkstra. Dijkstra's (greedy) algorithm is like BFS with priority queue instead of queue. Pseudocode, proof of correctness. See CLRS 24.3. Term test was held during the tutorial hour. |
| Feb 3 | Discussed upcoming term test. Went over solutions for Q4 and Q3 from assignment 1. I have typed up sample solutions for assignment 1. You can access them here: Question 1, Question 2, Question 3, Question 4, Question 5. The solutions are provided "as is" and might contain typos - please let me know if you find any. |
| Feb 1 | Graph theory overview - directed, undirected graphs, subgraphs, spanning subgraphs, trees, weighted graphs, three representations of graphs - list of edges/adjacencies, adjacency lists, adjacency matrix. Facts about trees - |E|=|V|-1, characterization of trees in terms of unique paths. Assumed background - BFS, DFS, Union/Find datastructure. Minimum spanning tree problem. High level overview of Kruskal's algorithm. Detailed overview of Prim's algorithm including proof of correctness, pseudocode, and analysis of runtime. Recommended reading: CLRS Chapters 22, 23. |
| Jan 30 | Dynamic programming subparadigms - a list of most common (input, optimal substructure) pairs. For a similar list see DPV chapter 6 page 178. General coin change problem (see this link for an exposition similar to the one I presented in class). Edit distance (DPV 6.3). Advanced tutorial covered fast Fourier transform (see these excellent notes of Eric Bannatyne). Regular tutorial covered CLRS problem 15-4 (printing neatly). |
| Suggested problems for week 3 (not to be handed in): CLRS 15.2-1, 15.2-2, 15.2-5, 15.3-2, 15.3-3, 15.3-4, 15.4-1, 15.4-2, 15.4-6, DPV 6.7, 6.21 | |
| Jan 27 | More examples of dynamic programming problems with different optimal substructures. Chain matrix multiplication (CLRS 15.2). Maximum independent set in trees (DPV 6.7). |
| Jan 25 | Elements of a DP problem. Elements of a DP solutions. Pros of DP table implementation. Pros of memoization implementation. Longest increasing subsequence problem (DPV 6.2). Longest common subsequence problem (CLRS 15.4). |
| Jan 23 | Dynamic Programming (CLRS 15). Two key properties: optimal substructure property, and overlapping subproblems property (see CLRS 15.3). Elements of a DP solution: semantic array, computational array, correctness: equivalence of the two arrays, pseudocode, analysis of running time, reconstructing the solution. Running example: weighted interval scheduling problem (WISP) aka weighted activity selection. Another example: 0/1 Knapsack problem (see CLRS 16.2). See these slides of Borodin for notes on WISP and Knapsack. EDIT:Tutorial covered CLRS problem 16-1 (Greedy Coin Change Problem). CLRS 16-2 is also recommended for extra practice with greedy algorithms. LATER EDIT (Jan 30, 2017) see this writeup for a solution to CLRS 16-1 (a-c) (due to Qiyang Li). |
| Suggested problems for week 2 (not to be handed in): design an O(n log n) algorithm for interval scheduling to minimize the number of machines (aka interval coloring), design an O(|F|) algorithm for satisfiability of Horn formulas, fill in the details of fractional Knapsack algorithm and analysis, CLRS 16.1-2, CLRS 16.2-5, CLRS 16.3-2, CLRS 16.3-3, CLRS 16.3-7. | |
| Jan 20 | Optimal substructure property (see, e.g., this Wikipedia page). Boolean variables, literals, Horn clauses. Satisfiability of Horn Formulas problem. Greedy solution. Analysis, runtime. (see DPV 5.3). Fractional knapsack problem. Greedy algorithm for this problem (see this set of slides for a good summary). |
| Jan 18 | Finished the analysis of interval scheduling to minimize the number of machines (aka interval coloring). Binary codes. Fixed-length codes. Variable-length codes. Prefix-free codes. Compression task. Huffman coding, correctness, running time (CLRS Ch 16.3). |
| Jan 16 | Strassen's algorithm was covered during the tutorial (see CLRS Ch 4.2). Lecture material: started greedy algorithmic paradigm. Presented 4 greedy algorithms for activity selection problem (aka interval scheduling on a single machine). See CLRS Ch 16.1, 16.2. Optimality of earliest finishing time (EFT) algo. General approach to proving optimality of greedy algorithms based on partial solution loop invariant. Started interval scheduling to minimize number of machines (aka interval coloring, machine name = color number) problem (see these notes from Allan Borodin). |
| Suggested problems for week 1 (not to be handed in): CLRS exercises 4.2-2, 4.2-4, 4.2-5, 4.2-7, problem 4-1 (page 107), exercises 33.4-2, 33.4-4, 33.4-6 | |
| Jan 13 | Finished divide and conquer algorithm for closest pair of points in the Euclidean 2D space (see CLRS 33.4). L-tiling of the 2^k by 2^k chessboard with one square removed (see Cut the Knot article and Amherst interactive version. Counting inversions (Kleinberg, Tardos "Algorithm Design" 5.3). Additional suggested reading for week 1: chapter 4 of CLRS - feel free to skip 4.1; chapter 4.2 will be covered in the tutorial; chapters 4.3-4.5 are reminders on how to solve recurrences. |
| Jan 11 | Divide and conquer continued. Finding closest pair of points in the Euclidean 2D space (see CLRS 33.4). Measure of interest: number of operations on real numbers. Trivial algorithm runs in O(n^2). A divide and conquer algorithm can be made to run in O(n log n) time. Crucial observation: merge step can be made to run in O(n) time. Argument about local sparsity. |
| Jan 9 | Divide and conquer algorithmic paradigm (see this wikipedia entry for general overview). Mergesort (CLRS 2.3.1). Algorithm for multiplying integers from elementary school takes O(n^2) single-digit ops. Trivial recursive algorithm takes O(n^2) single-digit ops. 1960 - tremendous improvement: Karatsuba algorithm for multiplying integers (notes from UChicago, wikipedia entry, Dasgupta et al "Algorithms" Chapter 2.1). |
| Jan 6 | Introduction. Tentative schedule, organization of the course. Computational problem: specification of input, output. Efficiency measures. Structure of solutions: pseudocode, proof of correctness, estimation of cost with respect to a given efficiency measure. Working example: modular exponentiation. Elegant version of repeated squaring algorithm. See this writeup of repeated squaring and binary search. Binary search was not covered in the lecture. |
| Week no | Dates | Topic | Suggested Readings |
|---|---|---|---|
| 0 | Jan 6 - Jan 8 | Intro | Course Contents |
| 1 | Jan 9 - Jan 15 | Divide and Conquer | CLRS Ch 4, DPV Ch 2, KT Ch 5 |
| 2 | Jan 16 - Jan 22 | Greedy Algorithms | CLRS Ch 16, DPV Ch 5, KT 4 |
| 3 | Jan 23 - Jan 29 | Dynamic Programming | CLRS Ch 15, DPV Ch 6, KT Ch 6 |
| 4 | Jan 30 - Feb 5 | Dynamic Programming | CLRS Ch 15, DPV Ch 6, KT Ch 6 |
| 5 | Feb 6 - Feb 12 | Graph Algorithms | CLRS Ch 22-25, DPV Ch 3-4, KT Ch 3 |
| 6 | Feb 13 - Feb 19 | Network Flow | CLRS Ch 26, DPV Ch 7(7.1-7.3), KT Ch 7 |
| 7 | Feb 20 - Feb 26 | No Classes, Reading Week | N/A |
| 8 | Feb 27 - Mar 5 | Linear Programming | CLRS Ch 29, DPV Ch 7 |
| 9 | Mar 6 - Mar 12 | Linear Programming | CLRS Ch 29, DPV Ch 7 |
| 10 | Mar 13 - Mar 19 | Complexity | CLRS Ch 34, DPV Ch 8, KT Ch 8 |
| 11 | Mar 20 - Mar 26 | Complexity | CLRS Ch 34, DPV Ch 8, KT Ch 8 |
| 12 | Mar 27 - Apr 2 | Approximation Algorithms | CLRS Ch 35, DPV Ch 9, KT 11 |
| 13 | Apr 3 - Apr 5 | Special Topic, Exam Prep | TBA |
| Exam Period | Apr 10 - Apr 30 |