Newsgroup: git.cc.class.3500a
Web page: http://www.cc.gatech.edu/classes/AY2000/cs3500a_spring/

Textbooks:

• Introduction to the Theory of Computation, by Michael Sipser.
• Introduction to Algorithms by Thomas H. Cormen, Charles E. Leiserson, and Ronald L. Rivest.

Prerequisites: CS1050, CS1302, and MATH3012. (MATH 3012 may be taken concurrently).

General Description: Computational machine models and their language classes. Decidability and undecidability. Design and analysis of efficient algorithms for fundamental computational problems. Tractability and intractability.

• Regular languages: deterministic and non-deterministic finite automata, regular expressions, closure properties, pumping lemma for regular languages.
• Context-free languages: context-free grammars, Chomsky normal form, push-down automata, pumping lemma for context-free languages.
• Computability theory: Turing machines, decidability, the halting problem.
• Introduction to the analysis of algorithms: asymptotic notation, recurrences, the master theorem.
• Algorithm design techniques: divide and conquer (Strassen's matrix multiplication); greedy algorithms (Huffman codes); dynamic programming (matrix-chain multiplication).
• Sorting and searching: merge sort, heap sort, quick sort, lower bound for comparison sorting, counting sort, medians and order statistics, optimum binary search trees, balanced binary search trees.
• Graph algorithms: breadth-first and depth-first search, minimum spanning trees (Kruskal's and Prim's algorithms), shortest paths (Dijkstra's algorithm and Bellman-Ford algorithm), Warshall's algorithm for transitive closure.
• String matching: string matching with finite automata, the Knuth-Morris-Pratt algorithm.
• NP-completeness: polynomial-time reducibility, Cook's theorem, basic NP-complete problems, proving NP-completeness, approximation algorithms.

Grading: Weekly homeworks (20%), 3-4 in-class quizzes (10%), 2 programming projects (20%), mid-term exam (25%), final exam (25%).

Late policy: The weekly assignments are due in class, at the date specified in the assignment. Late assignments will be assesed a penalty of 20% of their grade if turned in whithin 48 hours; assignments that are more than 48 hours late will not be accepted.

General advice: Assignments will be handed out in class, and also posted on the class web page. Plan to spend a fair amount of time on the homework assignments. Always try first to solve the problems by yourself; seek outside help only if you get stuck.

Getting help: Don't hesitate to get help if you get stuck on a homework problem. The most obvious sources of help are your instructor, your TA, and the newsgroup for the class. You are also allowed to verbally collaborate on homework problems with other students, provided that you acknowledge the collaboration by writing the names of those with whom you discussed solutions. You are not allowed to share written answers or code with anyone else, and you may not look up the answer to a homework problem if it happens to be published either in print or on the internet.