Overview

In this course, we study formal models of computation, notions of undecidability, and basic complexity theory. Models of computation include finite state automata, pushdown automata, and Turing machines.

Topics covered include: properties of regular sets and context-free languages, partial recursive functions, primitive recursive functions, recursively enumerable sets, Turing decidability and unsolvable problems, reductions, time and space complexity classes, and the polynomial-time hierarchy

Instructor:   Riccardo Pucella
328 West Village H
Office Hours: Thu 15h00-17h00
 
Time: Mon/Wed 14h50-16h30
 
Location: 433 Ryder Hall

 

Announcements

Apr 24: The final has been handed out. Due monday, May 1st, at 17h00.

Apr 5: Homework 7 is out. Due wednesday April 12, at the beginning of class.

Mar 22: Homework 6 is out. Due wednesday March 29, at the beginning of class.

Mar 13: The midterm is out. Due monday March 20th, at the beginning of class.

Feb 27: Homework 5 is out. Due monday March 13th, at the beginning of class.

Feb 15: Homework 4 is out. Due next wednesday, at the beginning of class. By the way, the version I distributed in class used a grammar format that I did not describe, so if you confused, just used the amended version I give below.

Feb 8: Homework 3 is out. Due next wednesday, at the beginning of class.

Feb 1: Second homework is out. Due next wednesday, at the beginning of class.

Jan 24: Some notes on homework 1 can be found here.

Jan 18: First homework is out. Due next wednesday, at the beginning of class.

Jan 18: I have updated the schedule to reflect the sections in Sipser (2nd edition) corresponding roughly to the lectures

Jan 9: Note that the course location has been changed to 433 Ryder Hall

Administration

Resources

 

Course Information

 

Course Staff

Instructor:   Riccardo Pucella
328 West Village H
Office Hours: Thursday 15h00-17h00
 
Teaching Assistant: In my dreams...

 

Prerequisites

CSG 713 (Advanced Algorithms).

 

Grading

Homework will be assigned every 1-2 weeks; it should be handed in in lecture, at the beginning of class, the day it is due.

Late homework will not receive credit. (If a genuine emergency situation prevents you from handing in an assignment on time, come talk to me and we can work something out.)

You may discuss the homework problems with other members of the class, but you must write up the assignment separately and list the names of the people with whom you discussed the assignment.

There will be a take-home midterm in the middle of the semester, and a take-home final at the end of the semester. Unlike the homework assignments, these must be done completely on your own.

The homework will count for 50% of the grade, the midterm for 20%, and the final for 30%.

 

Books

The textbook is

  • Introduction to the Theory of Computation, by Sipser

Some other useful books are

  • Introduction to Automata Theory, Languages, and Computation, by Hopcroft and Ullman (first edition), Hopcroft, Motwani, and Ullman (second edition).
  • Computational Complexity, by Papadimitriou
  • Computers and Intractability: A Guide to the Theory of NP-Completeness, by Garey and Johnson

 

 

Schedule and Lecture Notes

Here is a list of the lectures planned for the course. Note that this schedule is subject to change.

Date       Topic
 
Automata Theory
Jan 9       Overview; DFAs; state diagrams
(Sipser, section 1.1, "Finite Automata")
Jan 11 Regular languages; regular operations
(1.1, "Finite Automata")
Jan 16 Martin Luther King Jr.'s Birthday - no classes
Jan 18 Closure properties; non-determinism; equivalence of NFAs and DFAs
(1.2, "Nondeterminism")
Jan 23 Regular expressions; equivalence of RE and FA
(1.3, "Regular Expressions")
Jan 25 Non-regular languages; Pumping Lemma
(1.4, "Nonregular Languages")
Jan 30 Kleene's Theorem; Higman's Theorem
Feb 1 Context-free languages; context-free grammars; ambiguity
(2.1, "Context-Free Grammars")
Feb 6 Pushdown automata
(2.2, "Pushdown Automata")
Feb 8 Equivalence of CFLs and PDAs
(2.2, "Pushdown Automata")
Feb 13 Pumping Lemma for CFLs; closure properties
(2.3, "Non-Context-Free Languages")
 
Computability Theory
Feb 15 Turing Machines; state diagrams; Church-Turing thesis
(3.1, "Turing Machines")
Feb 20 Presidents' Day - no classes
Feb 22 Decidable and recognizable languages
(4.1, "Decidable Languages")
Feb 27 Turing Machine variants; multi-tape and non-deterministic
(3.2, "Variants of Turing Machines")
Mar 1 Decidability; cardinality of infinite sets; diagonalization
(4.2, "The Halting Problem")
Mar 6 Spring Break - no classes
Mar 8 Spring Break - no classes
Mar 13 Halting problem
(4.2, "The Halting Problem")
Mar 15 Reducibility
(5.1, "Undecidable Problems From Language Theory")
Mar 20 Rice's theorem
Mar 22 Post correspondence problem
(5.2, "A Simple Undecidable Problem")
 
Complexity Theory
Mar 27 Time complexity
(7.1, "Measuring Complexity")
Mar 29 P and NP
(7.2, "The Class P", 7.3, "The Class NP")
Apr 3 Polytime reductions
(7.4, "NP-Completeness")
Apr 5 NP-completeness
(7.4, "NP-Completeness")
Apr 10 NP-completeness
(7.5, "Additional NP-Complete Problems")
Apr 12 co-NP
Apr 17 Patriots' Day - no class
Apr 19 Space complexity
(8, 8.2, parts of 8.3)
Apr 24 Savitch's Theorem
(8.1)

 

 

Homework Assignments

All homeworks are provided in PDF.