CS 6505: Computability, Algorithms, and Complexity

Georgia Tech, Spring 2006

Instructor: Dr. David A. Bader

Office: CCB 257
Office Hours: Tu/Th 11am-12pm, or by appointment.

Teaching Assistant: Rishi Saket, saket@cc.gatech.edu.
Teaching Assistant Hours: Wed. 11am-12pm and Fri. 12pm-1pm, in the CoC Commons Area.

Textbooks:

Sipser, Introduction to the Theory of Computation, Second edition, Course Technology, 2005.
Cormen, Leiserson, Rivest, and Stein, Introduction to Algorithms, Second edition, MIT Press, 2001.

Course Information:

• Syllabus
• Homework Set #1, due 24 January.
• Homework Set #2, due 2 February.
• Homework Set #3, due 7 March.
• Homework Set #4, due 6 April.
• Homework Set #5, due 20 April.

Useful Links:

• Purchase an inexpensive used copy of the Sipser textbook!
• Purchase an inexpensive used copy of the Cormen, et al. textbook!
• Georgia Tech CS6505
  • Fall 2005 (H. Venkateswaran)
  • Fall 2003 (H. Venkateswaran)
• Web sites of related courses:
  • Berkeley; CS172 (Win van Dam)
  • CMU; FLAC (Lenore/Manuel Blum)
  • U Chicago; CMSC 386 (Lance Fortnow)
  • Princeton; COS 522 (Boaz Barak)
  • Columbia U; COMS 3261 (Zeph Grunschlag)
  • U Houston; COSC 3340 (Rakesh Verma)
  • U New Mexico; CS 500 (Peter Gemmell)
  • Tel Aviv U; Computational Complexity Theory (Muli Safra)
  • Tel Aviv U; Adv. Computational Complexity Theory (Muli Safra)
  • Princeton; COS 423 (Kevin Wayne)
    • Fibonacci slides
    • Max Flow slides
    • Demo-Max-Flow slides
    • Demo-BFS slides