ECE 461: Theoretical Computer Science
Spring 2024
Tuesdays 5:00 PM - 5:50 PM, Rm. 105;
Thursdays 3:00 PM - 4:50 PM, Rm. 105
Instructor:
Carl Sable
e-mail: carl.sable@cooper.edu
Office: Room 614
"Introduction to the Theory of Computation, 3rd edition"
by Michael Sipser
(2nd edition is OK)
Other resources (not required):
"Computational Complexity: A Modern Approach"
by Sanjeev Arora and Boaz Barak
"Computational Complexity"
by Christos Papadimitriou
- 3 Problem Sets: 50% total
- 4 Quizzes: 50% total
Problem sets will be posted here when they are assigned.
Note 1: All dates and topics which have not yet occurred are
tentative.
Note 2: Starting with week 2, I encourage students to do the related
reading before class.
Note 3: Sections match the Sipser book, both Editions 2 and 3
- Thursday, January 18
Topic: Course Introduction, Notations, and Terminology
(Slides)
Reading: Sipser, Preface and Chapter 0
See the syllabus
as a single document
- Tuesday, January 23
Topic: Deterministic Finite Automata
(Slides)
Reading: Sipser, Section 1.1
- Thursday, January 25
Topic: Deterministic Finite Automata (cont.)
Topic: Nondeterministic Finite Automata
(Slides)
Reading: Sipser, Section 1.2
- Tuesday, January 30
Topic: Nondeterministic Finite Automata (cont.)
Topic: Regular Expressions
(Slides)
Reading: Sipser, Section 1.3
- Thursday, February 1
Topic: Regular Expressions (cont.)
Topic: Nonregular Languages and the Pumping Lemma
(Slides)
Reading: Sipser, Section 1.4
- Tuesday, February 6
Topic: Context-Free Grammars
(Slides)
Reading: Sipser, Section 2.1
- Thursday, February 8
Topic: Pushdown Automata
(Slides)
Reading: Sipser, Section 2.2
Topic: Non-Context-Free Languages and the Pumping Lemma
(Slides)
Reading: Sipser, Section 2.3
- Tuesday, February 13
Topic: Non-Context-Free Languages and the Pumping Lemma (cont.)
Topic: Turing Machines and Algorithms
(Slides)
Reading: Sipser, Chapter 3
- Thursday, February 15
Topic: Turing Machines (cont.)
- Tuesday, February 20
Topic: Turing Machines (cont.)
- Thursday, February 22
Topic: Decidable Languages
(Slides)
Reading: Sipser, Section 4.1
Quiz #1
- Tuesday, February 27
Topic: Undecidability and Diagonalization
(Slides)
Reading: Sipser, Section 4.2
- Thursday, February 29
Topic: Undecidability and Diagonalization (cont.)
Topic: Reductions and Computation Histories
(Slides)
Reading: Sipser, Chapter 5
- Tuesday, March 5
Topic: Reductions and Computation Histories (cont.)
- Thursday, March 7
Topic: Reductions and Computation Histories (cont.)
- Tuesday, March 12
Topic: The Recursion Theorem
(Slides)
Reading: Sipser, Section 6.1
- Thursday, March 14
Topic: The Recursion Theorem (cont.)
Quiz #2
- Tuesday, March 26
Topic: Logical Theories, (introduction to) Oracles
(Slides)
Reading: Sipser, Sections 6.2 - 6.3
- Thursday, March 28
Topic: Logical Theories, (introduction to) Oracles (cont.)
Topic: Time Complexity, Big-O Notation, the Class P
(Slides)
Reading: Sipser, Sections 7.1 - 7.2
- Tuesday, April 2
Topic: Time Complexity, Big-O Notation, the Class P (cont.)
- Thursday, April 4
Topic: The Classes NP and coNP, The P versus NP Question
(Slides)
Reading: Sipser, Section 7.3
Topic: NP-Complete Problems, the Cook-Levin Theorem,
and (more) Reductions
(Slides)
Reading: Sipser, Sections 7.4 - 7.5
- Tuesday, April 9
Topic: NP-Complete Problems, the Cook-Levin Theorem,
and (more) Reductions (cont.)
- Thursday, April 11
Topic: NP-Complete Problems, the Cook-Levin Theorem,
and (more) Reductions (cont.)
- Tuesday, April 16
Topic: Space Complexity, Savitch's Theorem, the Class PSPACE
(Slides)
Reading: Sipser, Sections 8.1 - 8.2
- Thursday, April 18
Topic: PSPACE-Complete Problems
(Slides)
Reading: Sipser, Section 8.3
Quiz #3
- Tuesday, April 23
Topic: The Classes L, NL, and coNL
(Slides)
Reading: Sipser, Sections 8.4 - 8.6
- Thursday, April 25
Topic: Intractable Problems and Hierarchy Theorems
(Slides)
Reading: Sipser, Section 9.1
Topic: Relativization and (more about) Oracles
(Slides)
Reading: Sipser, Section 9.2
- Tuesday, April 30
Topic: Approximation Algorithms
(Slides)
Reading: Sipser, Section 10.1
- Tuesday, May 7
Topic: Randomization, Probabilistic Algorithms, the Class BPP
(Slides)
Reading: Sipser, Section 10.2
- Thursday, May 9
Topic: Interactive Proof Systems
(Slides)
Reading: Sipser, Section 10.4
Quiz #4