TAing
CS 4820 · Intro to Analysis of Algorithms (Summer 2020)
Principal instructor: Ali Erkan.
I am taking over a sequence of five lectures on NP-completeness and reductions. The lecture slides are intended to be reasonably comprehensive, and usable as a reference on their own:
- Lecture 1 (Wed. 2020-06-24): Hardness of problems. Asymptotic complexity of fastest algorithm as a measure of how hard a problem is. How do we know that we won't find a faster algorithm in the future? Reductions and relative hardness of problems. The chicken-and-egg problem of hardness, and how we might overcome it by an argument from large numbers.
- Lecture 2 (Thu. 2020-06-25): Formalising computation. Large families of problems whose only commonality is in the computers they can be solved on. Decision problems. Turing machines and the class P. Solving a problem vs. verifying a solution. The class NP. Nondeterministic Turing machines. Equivalence between the verifier view and the nondeterministic TM view of NP.
- Lecture 3 (Fri. 2020-06-26): The Cook-Levin theorem. All problems in NP are reducible to CNF-SAT in polynomial time. Hence, if any of them is not in P, then CNF-SAT isn't either: so CNF-SAT, itself in NP, is NP-complete. This solves the chicken-and-egg problem from Lecture 1, if only we are willing to believe P≠NP.
- Lectures 4 and 5 (Mon. 2020-06-29/Tue. 2020-06-30): NP-completeness reductions. A poly-time reduction from one NP-complete problem to a problem in NP shows the latter is also NP-complete. 3-CNF-SAT as a common source problem. Reducing CNF-SAT to 3-CNF-SAT. / More on NP-completeness reductions. Breaking problems and solutions into building blocks. The search tree view of problem solving. Gadgets: building reductions by replicating one problem's search tree with building blocks from another. The Independent Set problem. NP-completeness of IS. Graph colouring. NP-completeness of 3-colourability of graphs.
CS 4820 · Intro to Analysis of Algorithms (Spring 2014)
Principal instructors: Bobby Kleinberg and David Steurer.
Course page · Central course rubric · CMS (for submitting homework assignments) · Piazza (for discussion)
CS 4810 · Introduction to Theory of Computing (Fall 2013)
Principal instructor: David Steurer.
Course page · Central course rubric · CMS (for submitting homework assignments) · Piazza (for discussion)
Notes on NTMSAT≤pSAT: here
My current office hours are Tuesdays 4pm..5pm, to be held in 328B Upson Hall. Sometimes, I can make time to meet people with individual questions outside of regular office hours; please contact me via Piazza or e-mail if you are interested.
A good approximation to a Turing machine.
Classic Nintendo Games are (NP-)Hard.
Others
- CS 4820, (Summer 2014 · Spring 2019); CS 2110, CS 1110 (Summer 2014)
- CS 6820 · Analysis of Algorithms (Fall 2014 · Fall 2018 · Fall 2019)
- CS 1110 · Introduction to Computing Using Python (Spring 2015)
|