Date
| Type
| Topics
| reference
| handouts
| |
| Feb. 21 | 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 23 | Targil* 1 | O-notations: definitions. Turing machines: 1-tape TM for palindrome identification. | P chapter 2.1-2.3. | Exercise 1 TM for palindrome identification. |
| Feb 24 | 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 27 | Lecture 3 | Random Access Machine: definition and examples. Polynomial equivalence of RAM and TM. | P 2.6 | - |
| Feb. 29 | Targil 2 | Simulating DTM by a DTM with fixed alphabet. | - | Exercise 2 |
| March 1 | Lecture 4 | nondeterministic machines, proper complexity functions, | 2.7, 7.1 | my notes |
| March 6 | Lecture 5 | complexity classes, complementary classes, universal Turing machines Time Hierarchy theorem, | 7.1 7.2 | - |
| March 8 | Targil 3 | Equivalent definitions of NP | P chapter 9.1 | Exercise 3 |
| March 9 | Lecture 6 | Space Hierarchy theorem, Gap theorem (w/o proof), relations between deterministic and nondeterministic complexity classes, Savitch's theorem; Immerman's theorem | 7.3 | - |
| March 13 | Lecture 7 | Nondeterministic space classes are closed under complement; Reductions; Hamlitonian Path < SAT; Circuit SAT < SAT; reduction by generalization | 8.1 | - |
| March 15 | Targil 4 | P,NP, simple observations. Reachability < CVP. | - | Exercise 4 |
| March 16 | Lecture 8 | Transitivity of (logspace) reductions; Completeness; Circuit Value is P-complete (two proofs). Monotone CVP is P-complete. | 8.1 8.2, JaJa 10.5 | Sketches of recduction (from P.), Outline of JaJa's reduction, Outline of Cook's theorem a-la Even |
| March 20 | 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 | my notes |
| March 22 | Targil 5 | NAE-3SAT < 3-COLORING; SAT < 3-SAT; 3-SAT < E3-SAT | P 9.3 | Exercise 5 |
| March 23 | Lecture 10 | Hypergraph 2-colorability: restrictions; Set Splitting; Not-All-Equal SAT; 3SAT < Directed Hamiltonian Cycle | DHC reduction from Hopcroft-Ullman | simplified figures for the DHC reduction |
| March 27 | Lecutre 11 |
DHC < TSP 3SAT < 3DM , X3C | GJ 3.1.2 | 3DM reduction summary and sketch |
| March 29 | Targil 6 | E3-SAT < MAX2SAT; DHC < UHC; UHC < UHP; CVP < LP(D) | JaJa p. 552 | Exercise 6 |
| March 30 | Lecture 12 |
Characterization of NP in terms of Binary relation. NAE-3SAT < Max Cut; Max Bisection, Bisection width. X3C < Subset Sum; | P 9.1; 9.2; GJ 3.1.5 simplified | - |
| April 3 | Lecture 13 |
Subset Sum < Partition. Dynamic Programming algorithm for Subset Sum. Number problems; Pseudopolynomial algorithms; strong NP-completeness; Pseudopolynomial reductions; | GJ 4.2 | - |
| April 5 | Targil 7 | IS < IP. P is cloesed under reductions, Space(n) is not. | - | Exercise 7 |
| April 6 | Lecture 14 (IP) | Bin Packing is Strongly NP-complete (redcution from 3DM); 3-Partition (w/o proof); Interval Sequencing: Pseudo polynomial reduction from Bin Packing | P 9.4, GJ 4.2.2 | - |
| April 10 | Lecutre 15 (IP) |
Subgraph Isomorphism is NPC;
Subforest isomorphism: pseudo-polynomial reduction from
bin packing. Dynamic Programming: order of matrix multiplication; TSP; Floyd's algorithm |
GJ 4.2.2, AHU 2.8, BB p. 159; | summary |
| April 12 | Targil 8 | Dynamic Programming algorithm for Weighted IS on a path. | - | Exercise 8 |
| April 13 | Lecture 16 (IP) |
coNP, the intersection of NP and coNP,
Primality and Pratt's theorem DP for bin packing with two bins |
P 10, | Summary |
| May 1 | Lecture 17 |
Function problems, FP, FNP, reductions between function
problems; Minimum edit distance between sequences | P. 10 | Minimum edit distance example from Gusfield's book. |
| May 3 | Targil 9 | Characterization of the intersection of NP and CoNP. X3C < EXACTLY ONE SAT. | - | Exercise 9 |
| May 4 | Lecture 18 |
Total functions: Factoring, Happynet, equal-sum subsets.
Oracle Turing Machines, Turing reductions, NP-hardness; K-th Largest Subset is NP-hard. Backtracking algorithms: n queens, Backtracking example for Hamiltonian Cycle | P 14.3, GJ 5.1 Sedgewick | Backtracking example for Hamiltonian Cycle (Sedgewick) |
| May 8 | Lecture 19 (RS) |
Approximation: 1/2-approximation for Bin Packing;
First Fit, First Fit Decreasing, Best Fit (w/o proofs);
Approximation ratios; 1/2-approximation for max-sat | GJ 6.1, p 13.1, Mot | Ron's slides |
| May 11 | Lecture 20 (RS) |
TSP with triangle inequality: 1/3-approximation algorithm.
Nonexistence of constant ratio approximation for TSP. Polynomial and fully polynomial time approximation schemes; FPTAS for Knapsack. | P 13.1, GJ 6.1, Mot | Ron's slides |
| May 15 | Lecture 21 (RS) |
Parameterized Complexity: 1 definition of a param. problem. 2. definition of an fpt problem. 3. techniques - bounded search tree and reduction to problem kernel. 4. examples on vertex cover and 3-hitting set. 5. definition of param. reductions. 6. brief review on the W-hierarcy; clique,IS are W[1] complete (w/o proof). | - | - |
| May 17 | Targil 10 | Approximation algorithm for MAX Independen Set in bounded degree graphs. 2-approximation for MIN weight Vertex Cover. | P 13.1 | Exercise 10 |
| May 18 | Lecture 22 |
2-approximation for Vertex Cover. Absolute approximation for coloring planar graphs. Nonexistence of Absolute approximation for Knapsack. Branch and bound algorithm for Knapsack. | GJ 6.1, CLR 37.1, 37.4 | CLR example, B&B notes and example. |
| May 22 | Lecture 23 |
Aymptotic approximation ratio L-reductions: Definitions and properties L-reduction from IS to VC MAXSNP and PCP (w/o definitions and proos) | GJ 6.1 P. 13 | - |
| May 24 | Targil 11 | 2-approximation algorithm for MAX CUT. A L-reduction from MAX-3-SAT to MAX IS. | - | Exercise 11 |
| May 25 | Lecture 24 |
Minimum Equivalent Expression; The Polynomial Heirarchy;
Complete problems for levels of the PH. PSPACE; The Quantified Boolean Formula (QBF) problem, examples of PSPACE complete problems Branch and bound heuristics for TSP | GJ 6.1, P. 13.2, BB p. 200 | PH definitions TSP branch and bound example |
| May 29 | Lecture 24 |
QBF is PSPACE complete
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 | - |
| June 1 | 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 | my notes |
| June 5 | Lecture 26 |
NC In pursuit of the P?NP question (review) Course overview |
GJ 7.6 P 14 | course outline (this document) |
| June 7 | Targil 12 | QBF is in PSPACE. Sigma_i = Pi_i implies that PH=Sigma_i | P 17.2 | - |
This page was visited times since February 21 2000.