CS 6505: Computability and Algorithms
MWF, 11am, Klaus 1456.
Instructor: Santosh Vempala (Office: Klaus 2222, hours: M 9-11)
TAs:
Scott McManus (email: smcmanus at cc, office: Klaus 3402, hours: M 1-3, W 1-2, Th 2-3)
David Rutter (email: d.rutter at gatech.edu, office: Klaus 2124, hours: M 12-1, W 12-1, Th 12-2)
[Grading]
[Tentative Schedule]
[Readings]
[Homework Submission Guidelines]
[Lecture Notes]
[Homeworks]
Sample problems for midterm 2
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 22nd
Midterm II: In class, Wednesday, March 31st
Take-Home Final Exam:
30%
April 21-23.
We will alternate between algorithms and complexity topics each week.
Week 1, Jan 11-15: Problems, languages and Undecidability.
Week 2, Jan 20 & 22: Greedy algorithms. HW1
Week 3, Jan 25-29: Turing Machines, time/space hierarchies, nondeterminism. HW2
Week 4, Feb 1-5: Divide-and-conquer, sorting, median finding. HW3
Week 5, Feb 8-12: P, NP, coNP, PH, PSPACE-completeness. HW4
Week 6, Feb 15-19: Dynamic programming. HW5
Week 7, Feb 22-26:
Midterm I: Monday, February 22, P vs NP, reductions, NP-completeness. HW6
Week 8, Mar 1-5: Recursion, matrix multiplication. HW7
Week 9, Mar 8-12: BPP, identity testing. HW8
Week 10, Mar 15-19: Mon: ARC3, FFT, primality testing.
Week 11, Mar 22-26: Spring Break
Week 12, Mar 29 & 31, Apr 2:
Midterm II: Wednesday, March 31; Matchings in graphs. HW9
Week 13, Apr 5-9: Network flow. HW10
Week 14, Apr 12-16: Linear and Convex programming.
Week 15, Apr 19-23: PCP, approximation and hardness, Take home Final: given out Apr 21, due in class Apr 23.
Week 16, Apr 26-30: Overview of topics not covered (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.
There are several books on reserve at the library:
Sanjeev Arora and Boaz Barak also have a draft online of their upcoming
book,
Computational Complexity, A Modern Approach
All homeworks are due in class on the assigned due date.
Late submissions will not be accepted.
All work must be legible and written clearly.
If there are issues with reading your homework, then you will be asked
to submit a typewritten solution using the editor of your choice.
When submitting typewritten solutions, diagrams and figures may be
handwritten but must be written clearly and legibly.