CS 4510, Automata and Complexity

Spring 2010

• Instructor: Subrahmanyam Kalyanasundaram
• Time and place: MWF 3:05 P.M. - 3:55 P.M, Bunger Henry 311
• E-mail: subruk-at-cc.gatech.edu
• Office: Klaus 2116
• Office Hours: Tuesdays 3:30-4:30, Thursdays 11-12. Please email me to schedule a meeting outside office hours.
• Lectures: See the lecture schedule page.

Course Survey:

• The Course/Instructor Opinion Survey (CIOS) is now open and would remain open till midnight of Sunday May 9.
• Please enter your valuable inputs at the CIOS survey.
• Why should you care about this? See this short presentation.

Midterm exams:

• Midterm #1: Feb 24
      - Some practice questions here.
      - The midterm exam and the solutions.
      - The class average was 40 out of a maximum 60.
• Midterm #2: April 14
      - We will have the second midterm in class, the take home midterm was an April Fool's joke.
      - However, it would be a good exercise to work out the NP completeness proofs for the problems in it (I'm serious now).
      - Here are the reductions to see that these problems are NP-complete.
      - The midterm exam and the solutions (Update: Solution to 1(a) fixed).
      - The class average was 40.8 out of a maximum 60.

Make up Assignment:

• The make up assignment is available here.
• Purely optional. Can be used to substitute one of your midterm scores.
• The report is due latest by April 23, 2010.
• For a LaTeX template, download this source file of one of the online notes.
• The oral exam will be scheduled after the report is turned in.
• Topic Assignments
      - Complexity of Primes: Lander Basterra, Paige Hoffman, David Hwang
      - FP, FNP and DP: Antonio Blanca, Nicolas Villanueva
      - #P-completeness: Aaron Clarke, Andrew Melim, Andrew Rosen
      - P-completeness, Odd Flow: Jake Martin, Chris Mize
      - Complexity of Cuts: Wade Baxter, Sam Brett, James Eilers

Final exam:

• Final Exam: Monday, May 3, 2:50pm - 5:40pm
      - Here is a practice final exam.
      - The final exam.
      - Please email me if you are interested in seeing the solutions.
      - The class average was 80 out of a maximum 105.

Fifth homework assignment:

• Homework #5
• Solutions
• The class average was 23 out of a maximum 30.

Fourth homework assignment:

• Homework #4
• Solutions
• The class average was 46.1 out of a maximum 60.

Third homework assignment:

• Homework #3
• Solutions
• The class average was 40.5 out of a maximum 60.

Second homework assignment:

• Homework #2
• Solutions
• The class average was 38.2 out of a maximum 50.

First homework assignment:

• Homework #1
• Solutions
• The class average was 35.6 out of a maximum 50.

Handouts

• Course introductory handout.
• General Homework Guidelines.
• Notes on Myhill-Nerode Theorem.
• Notes on Ambiguity, Empty Rules and Unit Rules.
• Notes on Cocke-Kasami-Younger Algorithm.
• A short note on the role of state control in simulations and nondeterminism.
• Notes on simulation of NTMs using DTMs.
• Practice Midterm Questions.
• Notes on reducibility. (Thanks to Prof H Venkateswaran for letting us use his notes.)
• Notes on computation histories and the undecidability of ALL_CFG. (Thanks to Prof H Venkateswaran.)
• Notes on PCP and an example. (Thanks to Prof H Venkateswaran.)
• More on reducibility, follow up to a question in class.
• Notes on valid windows in Cook-Levin Theorem.
• Notes on co-NP and Polynomial Hierarchy from Tsinghua and Cornell.
• A chapter on Polynomial Hierarchy from Arora and Barak's book.
• Notes on NL = co-NL.
• Why one needs to careful while using nondeterministic algorithms are subroutines.
• Draft of Chapter 13 from Arora-Barak on communication complexity and notes on randomized algorithm for equality.

Course outline:

This is an undergraduate introductory course to automata theory and computational complexity theory. The following topics shall be covered. If time permits, more topics shall be included.

• Introduction:

  Introductory concepts in formal languages and automata theory: languages, operations on languages, and basic machine models.

• Regular languages:

  Deterministic and nondeterministic finite state automata. Closure under union, intersection, complementation, concatenation, and star operations. Equivalence of Non-deterministic finite state automata and deterministic finite state automata. Regular expressions and equivalence of regular expressions and regular languages. Pumping lemma. Myhill-Nerode theorem.

• Context-free languages:

  Context-free grammars. Ambiguity. Normal forms such as Chomsky normal form. Closure under union, concatenation, and star operations. Non-closure under intersection and complementation operations. Pumping lemma.Pushdown automata. Equivalence of pushdown automata and context-free grammars. Cocke-Kasami-Younger algorithm.

• Decidability and Reducibility:

  Turing machines. Decidable and recognizable languages. Equivalence of varieties of models such as multi-tape and non-deterministic Turing machines with the deterministic Turing machines. Diagonalization. Undecidability of the Halting problem. Undecidable problems from Language theory. Post Correspondence Problem. Many-one reducibility.

• Time Complexity:

  Complexity classes P and NP. Polynomial time reducibility. NP-Completeness. The Cook-Levin theorem. Examples of NP-Complete problems.

• Space Complexity:

  Space complexity. Savitch's theorem. PSPACE-Completeness. The classes L and NL. NL-Completeness. NL equals co-NL.

Exams:

There will be 2 in-class midterm exams during the course of the semester, plus a cumulative final exam at the end of the course.

Homework:

Homework will be assigned every 2-3 weeks. There will be 4-5 homeworks in all.

Grading Policy:

All the homeworks together will count for 25% of your grade, the two midterm exams will each count for 20% and the final will count 35%. The grading would be relative, and the cut-offs would be decided by the end of the semester. Please contact me if you have any questions about the grading.

Collaboration:

On the homework sets, collaboration is allowed. However, you must write up yourself and understand your own homework solutions. Any academic dishonesty on the midterm or final exams, if detected, will result in a score of zero for that exam. All students are expected to comply with the Georgia Tech Honor Code.