Date
| Type
| Topics
| reference
| handouts
| |
| Feb. 17 | Lecture 1 | Introduction, Algorithms, growth rate of fuctions. Reachability; Max Flow; Matching; The Travelling Salesman Problem. | P chapter 1, GJ 1.3 | whitepaper and syllabus |
| Feb. 19 | Targil* | Survey about orders of magnitude and Turing machines. | P chapter 2. | Home assignment #1. |
| Feb. 20 | Lecture 2 | Turing Machines: Model, time complexity, k-tape machine, simulation by 1-tape machine; linear speedup theorem; space complexity | P 2.1-2.5 | my notes |
| Feb 24 | Lecture 3 | Random Access Machine: definition and examples. Polynomial equivalence of RAM and TM. Nondeterministic Machines (incomplete) | P 2.6 | my notes |
| Feb. 26 | Targil | A RAM program to solve the reachability problem. Few examples of Turing machine programs. | P chapter 2. | P pages 41-42. Home assignment #2. |
| Feb 27 | Lecture 4 | nondeterministic machines, proper complexity functions, complexity classes | 2.7, 7.1 | - |
| March 3 | Lecture 5 | complementary classes, universal Turing machines, Time and Space Hierarchy theorems, Gap theorem (w/o proof), relations between deterministic and nondeterministic complexity classes (incomplete); | 7.1 7.2 | - |
| Mar. 5 | Targil | TM program for addition and subtraction. Survey about flow problems. Brief survey of the following classes: P, NP and CO-NP. | - | Home assignment #3. |
| March 6 | Lecture 6 | relations between deterministic and nondeterministic complexity classes, Savitch's theorem; the configuration graph, the reachability method, Immerman's theorem. | 7.3 | - |
| March 10 | Lecture 7 | Reductions; Hamlitonian Path < SAT; Circuit SAT < SAT; reduction by generalization | 8.1 | - |
| Mar. 12 | Targil | SAT < 3SAT | - | Home assignment #4. |
| March 13 | Lecture 8 | Transitivity of (logspace) reductions; Completeness; Circuit Value is P-complete (two proofs) | 8.1 8.2, JaJa 10.5 | Outline of JaJa's reduction |
| March 17 | Lecture 9 | Cook's Theorem (2 proofs) variation of SAT: 3SAT, 3 occurences per variable. SAT < Independet Set; SAT < Hypergraph 2-colorability | 8.2 9.1 Even 9.3 | Outline of Cook's theorem a-la Even |
| Mar. 19 | Targil | 3SAT < 3COLORING; A language decided by a k-string NDTM can be decided a 2-string NDTM without affecting the time complexity. | - | Home assignment #5. |
| March 20 | Lecture 10 | Hypergraph 2-colorability: restrictions; Set Splitting; Not-All-Equal SAT; 3SAT < Directed Hamiltonian Cycle | DHC reduction from Hopcroft-Ullman | simplified figure for the DHC reduction |
| March 24 | Lecutre 11 | 3SAT < 3DM , X3C | GJ 3.1.2 | 3DM reduction summary and sketch |
| Mar. 26 | Targil | Reductions; Reachability < Boolean Circuit ; CVP < Liner Inuequality ; 3SAT < MAX2SAT | 8.2 ; JaJa p. 552 | Home assignment #6. |
| March 27 | Lecture 12 | Characterization of NP by poly. balanced and poly. decidable relations NAE-3SAT < Max Cut; Max Bisection, Bisection width. X3C < Subset Sum; Subset Sum < Partition. | P 9.1; 9.2; GJ 3.1.5 simplified | - |
| Mar 31 | Lecture 13 | Dynamic programming algorithm for Subset Sum; Number problems; Pseudopolynomial algorithms; strong NP-completeness; Pseudopolynomial reductions; | GJ 4.2 | - |
| Apr. 2 | Targil | Reductions: Few variants of UHP and UHC | - | Home assignment #7. |
| Apr. 3 | Lecture 14 | Bin Packing is Strongly NP-complete (redcution from 3DM); 3-Partition (w/o proof); Interval Sequencing: Pseudo polynomial reduction from 3-partition | P 9.4, GJ 4.2.2 | - |
| Apr. 7 | Lecutre 15 |
Subgraph Isomorphism is NPC;
Subforest isomorphism: pseudo-polynomial reduction from
3-partition. Dynamic Programming: order of matrix multiplication; TSP; Minimum edit distance between sequences (incomplete) |
GJ 4.2.2, AHU 2.8, BB p. 159; Gusfield's text | Minimum edit distance example from Gusfield's text. |
| Apr. 9 | Targil | Few variants of UHP and UHC (cont'); Restricted version of Clique (which is NPC); Restricted version of VC (which is polynomial) | - | Home assignment #8. |
| Apr. 10 | Lecture 16 | Minimum edit distance between sequences (completed); coNP, the intersection of NP and coNP, Primality and Pratt's theorem; Function problems (incomplete) | P 10 | - |
| Apr. 14 | Lecture 17 | Function problems, FP, FNP, reductions between function
problems;
Oracle Turing Machines, Turing reductions, NP-hardness; Approximation: 1/2-approximation for Bin Packing; First Fit, First Fit Decreasing, Best Fit (w/o proofs); |
P 10, P 14.3, GJ 5.1; P 13.1, GJ 6.1 | - |
| Apr. 30 | Targil | Difference between Log Space Reduduction, Karp Reduction and Cook (Turing) Reduction | - | Home assignment #9. |
| May. 1 | Lecture 18 | 1/2-approximation for vertex cover. TSP with triangle inequality: 1/3-approximation algorithm. FPTAS for Knapsack. | P 13.1, GJ 6.1 | - |
| May. 5 | Lecture 19 | Approximation ratios; Polynomial and fully polynomial time approximation schemes, Absolute approximation for coloring planar graphs. Hardness of approximation: Nonexistence of Absolute approximation for Knapsack, fixed ration for TSP. L-reductions, properties, MAXSNP; | GJ 6.1, P. 13.1, 13.2 | - |
| May. 7 | Targil | Polinomial algorithm for coloring a 3-Colorabale graph with O(sqrt |V|) colors; A polinomial 1.5-epsilon approximation algorithm for VC implies a polinomial algorithm for coloring a 3-Colorabale graph with O(log |V|) colors; A 1/2-approximation algorithm for Knapsack; | Wi83 | Home assignment #10. |
| May 8 | Lecture 20 | MAXSNP, MAXSNP-completeness; the new (PCP) results on hardness of approximations (w/o proofs). Minimum Equivalent Expression; The Polynomial Heirarchy; Complete problems for levels of the PH. Backtracking algorithms: n queens, 3 cloroing. | GJ 6.1, P. 13.2 | - |
| May. 15 | Lecture 21 |
Backtracking algorithms: n queens, 3 cloroing, Hamiltonian Cycle.
Examples of branch and bound heuristics: TSP, Knapsack. PSPACE; The Quantified Boolean Formula (QBF) problem; | Sedgewick, BB p. 200 P 19.1 | Backtracking example for Hamiltonian Cycle (Sedgewick) Home assignment #11. |
| May 19 | Lecture 22 | QBF is PSPACE complete; Alternating Turing Machines, AP, AL. AL=P; AP=PSPACE. | P 19.1; P. 16.2, 19.1, 19.4 | - |
| May 22 | Lecture 23 |
More PSPACE-complete problems: Geography; In-Place Acceptance. Counting problems: The class #P, parsimonious reductions; #SAT is #P-complete. |
P. 19.4, P. 18.1 | - |
| May 26 | Lecture 24 |
Perfect matchings and the permanent.
Valiant's Theorem (w/o proof).
The class PP; Toda's theorem (w/o proof). Parallel Computations. The PRAM model and its variants. Finding the minimum of n elements in constant parallel time. |
P. 18.1 - | - |
| May. 28 | Targil | An existence of a polynomial algorithm that achieves a constant ratio when approximating the maximum clique implies the existence of a polynomial algorithm that achieves 1 + epsilon ratio when approximating the maximum clique for every constant epsilon > 0. Travelling salesman optimization problem is NP-easy. | - | Home assignment #12. |
| May 29 | Lecture 25 | Parallel algorithms for matrix multiplications, Reachability. Parallel computations models: Uniform Boolean Circuits, PRAM. Simulation Theorems (w/o proofs). | P. 15.1 15.2 | - |
| Jun. 4 | Targil | The polynimial hierarchy. Turing reductions and Karp reductions. | - | Home assignment #13. |
| June 5 | Lecture 26 | NC; Logarithmic space; In pursuit of the P?NP question (review) | GJ 7.6 P 14 | - |
*Targil=recitation (in Hebrew)
< = reduces to (using logarithmic space deterministic Turing Machine)
P= C. Papadimitriou Computational Complexity
(Addison Wesley, 1994)
GJ= Garey and Johnson, Computers and Intractability
(Freeman, 1979)
AHU= Aho, Hopcroft, and Ullman.
The Design and Analysis of Computer Algorithms .
(Addison Wesley, Reading, Mass., 1974).
BB= Brassard and Bratley.
Algorithmics: Theory and Practice .
(Prentice Hall, Englewood Cliffs, N. J., 1988).
CLR= Cormen, Leiserson and Rivest,
Introduction to Algorithms
(MIT press, 1990)
JaJa = J. JaJa.
An Introduction to Parallel Algorithms
(Addison-Wesley, Reading, Mass., 1992).
Wi83= A. Wigderzon, Improving the performance guarantee for
approximate
graph coloring, Journal of the ACM,30(4);729-735,1983