- This course will cover: (a) important concepts from computability theory; (b) techniques for designing efficient algorithms for combinatorial, algebraic, and number-theoretic problems; and (c) basic concepts such as NP-Completeness from computational complexity theory.
- This course can be taken by M.S. and non-theory CS Ph.D. students to satisfy the theory breadth requirement. This course cannot be taken by CS theory/ACO Ph.D. students to satisfy the theory breadth requirement.
- Pre-requisites: Familiarity with: (a) topics in automata theory such as such as finite automata, regular languages, pushdown automata, context-free languages, and Turing machines, and (b) basic algorithms 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). Talk to the instructor if you are not sure that you have the pre-requisites for this course.
Announcements: Check here regularly for updates.
- Homework submission guidelines: guidelines
- There are 4 tests which will tentatively take place on the following days:
- Friday, January 24
- Friday, February 28
- Friday, March 28
- Friday, April 18
- The date and time of the final exam is determined by Georgia Tech and cannot be changed. The final exam date is: Friday, May 2, 11:30am - 2: 20pm.
MWF 10:05-10:55 pm, KACB 1443.
Office: KACB 3366B
Office hours: Tuesdays, Thursdays 2:30 - 3:30pm or by appointment
Office hours: Thursdays 4pm - 6pm. In the theory common area next to room 2116 KACB. You can also get in touch with Arindam through email.
Office hours: Wednesdays 4pm - 6pm. In room 2201 KACB. You can also get in touch with Dushmanta through email.
Krishna Pallavi Vemulapalli
Office hours: MOndays 4pm - 6pm. In the theory common area next to room 2116 KACB. You can also get in touch with Pallavi through email.
Topics covered in this course:
[KT] Algorithm Design by J. Kleinberg and E. Tardos.