CS 6505: Computability, Complexity & Algorithms

Course Creators and Instructors

Charles Brubaker
Charlie Brubaker
Creator, Instructor


This course will cover important concepts from computability theory; techniques for designing efficient algorithms for combinatorial, algebraic, and number-theoretic problems; and basic concepts such as NP-Completeness from computational complexity theory.

To view an outline of the course, you may download the Syllabus. A sample lesson on the Maximum Flow problem is also available.


Students are expected to be familiar with: (a) mathematical proof techniques such as induction (b) basic models of computation such as finite automata or Turing machines, and (b) basic algorithms and data structures for sorting, graph traversal (breadth-first and depth-first search), minimum spanning trees (Kruskal's algorithm, Prim's algorithm), and shortest path (Dijkstra's algorithm). The main prerequisite is an abiding interest in learning theoretical computer science.

If you answer “no” to any of the following questions, it may be beneficial to acquire background knowledge concurrently or prior to taking CS 6505.

  • Can you show that the sum of the first n numbers is n(n+1)/2? Can you give the proof as an induction on n?
  • Can you give an O(n log n) algorithm for sorting n numbers?
  • Can you describe the difference between breadth-first and depth-first search?
  • Given an nxn matrix A and an n-dimensional vector b, can you give a polynomial-time algorithm to find a vector x such that Ax=b?

  "Discrete Mathematics and Its Applications" by Ken Rosen provides an excellent background for this course if you had trouble with these questions.

Lesson Preview


Grades will be based on written assignments and two proctored exams.

Recommended Course Readings

All course material will be covered in lecture. Homework will not reference specific problems from textbooks. It is recommended, however, that students obtain their own copies of:

Michael Sipser, Introduction to the Theory of Computation, T. H. Cormen, C.E. Leiserson, R. L. Rivest, and C. Stein, Introduction to Algorithms

Minimum Technical Requirements

  • Browser and connection speed: An up-to-date version of Chrome or Firefox is strongly recommended. We also support Internet Explorer 9 and the desktop versions of Internet Explorer 10 and above (not the metro versions). 2+ Mbps recommended; at minimum 0.768 Mbps download speed
  • Operating system: - PC: Windows XP or higher with latest updates installed - Mac: OS X 10.6 or higher with latest updates installed - Linux: Any recent distribution that has the supported browsers installed

Other Info

Academic Honesty

All Georgia Tech students are expected to uphold the Georgia Tech Academic Honor Code.