CS 6505: Computability and Algorithms

Spring 2012, MWF 10am, Klaus 1456.
Instructor: Santosh Vempala (Office: Klaus 2222, hours: MW 9-10am)
Assistants: Karthekeyan "Karthik" Chandrasekaran (karthe at cc, Office: Theory Atrium (Between Klaus 2116 & Klaus 2124), hours: Tu 11-1, Th 5-7, F 4-5)
Rajalakshmi Ramesh (ramesh.rajalakshmi at gmail, Office: Theory Atrium (Between Klaus 2116 & Klaus 2124), hours: Tu 1-3, Th 1-2, F 1-3)

[Grading] [Schedule] [Readings] [Homework Submission Guidelines] [Lecture Notes] [Homeworks]

Grading

Homework/Problem Sets: 10 weekly problem sets worth 5% each (for 50% total)
2 Midterms: 10% each (for 20% total)
Midterm I: In class, Monday, February 20nd
Midterm II: In class, Monday, March 26th

Take-Home Final Exam: 30% April 18-20.

Tentative Schedule

We will alternate between algorithms and complexity topics each week.

Week 1, Jan 9-13: Problems, languages and Undecidability.
Week 2, Jan 18,20: Greedy algorithms. HW1
Week 3, Jan 23-27: Turing Machines, time/space hierarchies, nondeterminism. HW2
Week 4, Jan 30 - Feb 3: Divide-and-conquer, sorting, median finding. HW3
Week 5, Feb 6-10: P, NP, coNP, PH, PSPACE-completeness. HW4
Week 6, Feb 13-17: Dynamic programming. HW5
Week 7, Feb 20-25: Midterm I: Monday, February 20, P vs NP, reductions, NP-completeness. HW6
Week 8, Feb 27, 29, Mar 2: Recursion, matrix multiplication. HW7
Week 9, Mar 5-10: BPP, identity testing. HW8
Week 10, Mar 12-16: FFT, primality testing. HW9
Week 11, Mar 19-23: Spring Break
Week 12, Mar 26-30: Midterm II: Monday, March 26; Matchings in graphs. HW10
Week 13, Apr 2-6: Network flow. HW11
Week 14, Apr 9-13: Linear and Convex programming.
Week 15, Apr 16-20: PCP, approximation and hardness, Take home Final: given out Apr 18, due in class Apr 20.
Week 16, Apr 23-27: Overview of topics not covered (e.g., sampling, spectral methods, game theory, learning theory, crypto, coding theory).

Each Friday will typically be a problem-solving session, where students break into groups of two or three. At the end of the session, the solutions to the problems will be presented.

Notes for each lecture will also be posted to this web site.

Readings

There will be several books on reserve at the library:

Homework Submission Guidelines

All homeworks are due in class on the assigned due date. Late submissions will not be accepted. All work must be legible and typed or written clearly. If there are issues with reading hand-written homework, you will be asked to submit a typewritten solution. When submitting typewritten solutions, diagrams and figures may be hand-drawn but must be clear. You are welcome to work together with other students from the class on homework problems, but you must formulate and write your own solutions.