Course Creators and Instructors
Overview
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.
Prerequisites
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
Grading
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.
