TAing
CS 4820 · Intro to Analysis of Algorithms (Summer 2020)
Principal instructor: Ali Erkan.
I am taking over a sequence of five lectures on NPcompleteness and reductions. The lecture slides are intended to be reasonably comprehensive, and usable as a reference on their own:
 Lecture 1 (Wed. 20200624): 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 chickenandegg problem of hardness, and how we might overcome it by an argument from large numbers.
 Lecture 2 (Thu. 20200625): 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. 20200626): The CookLevin theorem. All problems in NP are reducible to CNFSAT in polynomial time. Hence, if any of them is not in P, then CNFSAT isn't either: so CNFSAT, itself in NP, is NPcomplete. This solves the chickenandegg problem from Lecture 1, if only we are willing to believe P≠NP.
 Lectures 4 and 5 (Mon. 20200629/Tue. 20200630): NPcompleteness reductions. A polytime reduction from one NPcomplete problem to a problem in NP shows the latter is also NPcomplete. 3CNFSAT as a common source problem. Reducing CNFSAT to 3CNFSAT. / More on NPcompleteness 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. NPcompleteness of IS. Graph colouring. NPcompleteness of 3colourability 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≤_{p}SAT: 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 email 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)
