Date
| Type
| Topics
| reference
| handouts
| |
| March 29 | 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 |
| April 8 | 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 |
| April 14 | Targil* 1 | O-notations: definitions. Turing machines: 1-tape TM for palindrome identification. | P chapter 2.1-2.3. | Exercise 1 |
| April 19 | Lecture 3 | Random Access Machine: definition and examples. Polynomial equivalence of RAM and TM. Nondeterministic Machines (incomplete) | P 2.6 | Exercise 2 |
| April 22 | Lecture 4 | nondeterministic machines, proper complexity functions, complexity classes, complementary classes, universal Turing machines | 2.7, 7.1 | - |
| April 23 | Lecture 5 | Time and Space Hierarchy theorems, Gap theorem (w/o proof), relations between deterministic and nondeterministic complexity classes (incomplete); | 7.1 7.2 | - |
| April 23 | Lecture 6 | relations between deterministic and nondeterministic complexity classes, Savitch's theorem; the configuration graph, the reachability method, Immerman's theorem. Reductions (incomplete). | 7.3 | - |
| April 23 | Targil 2 | Simulating DTM by a DTM with fixed alphabet. | - | - |
| April 26 | Lecture 7 | Reductions; Hamlitonian Path < SAT; Circuit SAT < SAT; reduction by generalization Transitivity of (logspace) reductions; | 8.1 | - |
| April 28 | Targil 3 | Equivalent definitions of NP | P chapter 9.1 | Exercise 3, Solutions to ex. 1 |
| April 29 | Lecture 8 | Completeness; Circuit Value is P-complete (two proofs) Cook's Theorem (2 proofs) | 8.1 8.2, JaJa 10.5 | Outline of JaJa's reduction, Outline of Cook's theorem a-la Even |
| May 3 | Lecture 9 | variation of SAT: 3SAT, 3 occurences per variable. SAT < Independet Set; SAT < Hypergraph 2-colorability Hypergraph 2-colorability: restrictions; Set Splitting; Not-All-Equal SAT; 3SAT < MAX2SAT | 8.2 9.1 Even 9.3 | my notes |
| May 6 | Lecture 10 | 3SAT < Directed Hamiltonian Cycle | DHC reduction from Hopcroft-Ullman | simplified figure for the DHC reduction |
| May 10 | Lecutre 11 | 3SAT < 3DM , X3C | GJ 3.1.2 | 3DM reduction summary and sketch |
| May 13 | Lecture 12 | NAE-3SAT < Max Cut; Max Bisection, Bisection width. X3C < Subset Sum; Subset Sum < Partition. Dynamic Programming algorithm for Subset Sum. | P 9.1; 9.2; GJ 3.1.5 simplified | - |
| May 19 | Targil 4 | NAE-3SAT < 3-COLORING; 3-SAT < E3-SAT; UHC < UHP | P 9.3 | Exercise 4, Solutions to ex. 2 |
| May 24 | Lecture 13 | Number problems; Pseudopolynomial algorithms; strong NP-completeness; Pseudopolynomial reductions; | GJ 4.2 | - |
| May 26 | Targil 5 | DHC < UHC; CVP < LP(D); Bin-Packing with constant number of bins | JaJa p. 552 | Exercise 5, Solutions to ex. 3 |
| May 27 | Lecture 14 |
Bin Packing is Strongly NP-complete (redcution from 3DM);
3-Partition (w/o proof); Interval Sequencing: Pseudo polynomial
reduction from Bin Packing
Subgraph Isomorphism is NPC;
Subforest isomorphism: pseudo-polynomial reduction from
bin packing. | P 9.4, GJ 4.2.2 | - |
| May 31 | Lecutre 15 |
Dynamic Programming: order of matrix multiplication; TSP; coNP, the intersection of NP and coNP, Primality and Pratt's theorem (w/o proof) |
GJ 4.2.2, AHU 2.8, BB p. 159; P 10 | - |
| Jun 2 | Targil 6 | Characterization of the intersection of NP and CoNP. Polynomial algorithm for coloring a 3-Colorabale graph with O(sqrt |V|) colors; Approximation algorithms for MAX Independen Set in bounded degree graphs. | P 13.1 | Exercise 6, Solutions to ex. 4 |
| June 3 | Lecture 16 | Function problems, FP, FNP, reductions between function
problems;
Oracle Turing Machines, Turing reductions, NP-hardness; K-th Largest Subset is NP-hard. |
P 10, P 14.3, GJ 5.1; | - |
| June 7 | Lecture 17 | Approximation: 1/2-approximation for Bin Packing; First Fit, First Fit Decreasing, Best Fit (w/o proofs); TSP with triangle inequality: 1/3-approximation algorithm. | P 13.1, GJ 6.1 | - |
| Jun 9 | Targil 7 | Approximation algorithm for MAX Independen Set in bounded degree graphs. 2-approximation algorithms for MIN (weight) vertex cover | P 13.1 | Exercise 7, Solutions to ex. 5 |
| June. 10 | Lecture 18 | 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. | GJ 6.1, P. 13.1, 13.2 | - |
| June 14 | Lecture 19 | PCP definition; New (PCP) results on hardness of approximations (w/o proofs). Minimum Equivalent Expression; The Polynomial Heirarchy; Complete problems for levels of the PH. Backtracking example for Hamiltonian Cycle | GJ 6.1, P. 13.2 Sedgewick | Backtracking example for Hamiltonian Cycle (Sedgewick) |
| Jun 16 | Targil 8 | 2-approximation algorithm for MAX CUT. Nonexistence of constant ratio algorithm for MAX Independent Set. | - | Exercise 8, Solutions to ex. 6 |
| June 17 | Lecture 20 |
Backtracking algorithms: n queens, 3 cloroing.
Examples of branch and bound heuristics: TSP, Knapsack. PSPACE; The Quantified Boolean Formula (QBF) problem; QBF is PSPACE complete; | Sedgewick, BB p. 200 P 19.1 | - |
| June 21 | Lecture 21 |
More PSPACE-complete problems: Geography; In-Place Acceptance. Counting problems: The class #P, parsimonious reductions; #SAT is #P-complete. Perfect matchings and the permanent. Valiant's Theorem (w/o proof). 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. 19.4, P. 18.1 | - |
| Jun 23 | Targil 9 | QBF is in PSPACE. Sigma_i = Pi_i implies that PH=Sigma_i | P 17.2 | Solutions to ex. 7 |
| June 24 | Lecture 22 |
Parallel algorithms for matrix multiplications, Reachability.
NC; Logarithmic space; In pursuit of the P?NP question (review) |
P. 15.1 15.2 GJ 7.6 P 14 |
This page was visited times since March 31 1999.