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
GradingHomework/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.
Tentative ScheduleWe 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
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 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.
Click here to toggle editing of individual sections of the page (if possible). Watch headings for an "edit" link when available.
Append content without editing the whole page source.
Check out how this page has evolved in the past.
If you want to discuss contents of this page - this is the easiest way to do it.
View and manage file attachments for this page.
A few useful tools to manage this Site.
See pages that link to and include this page.
Change the name (also URL address, possibly the category) of the page.
View wiki source for this page without editing.
View/set parent page (used for creating breadcrumbs and structured layout).
Notify administrators if there is objectionable content in this page.
Something does not work as expected? Find out what you can do.
General Wikidot.com documentation and help section.
Wikidot.com Terms of Service - what you can, what you should not etc.