ECE 461: Theoretical Computer Science

Other resources (not required):

Grading

• 3 or 4 Problem Sets: 50% total
• 4 Quizzes: 50% total

Assignments

Problem sets will be posted here when they are assigned.

• Problem Set #1
• Problem Set #2
• Problem Set #3

Schedule

Note 1: All dates and topics which have not yet occurred are tentative.

Note 2: Starting with week 2, I expect students to do the related reading before class.

Note 3: Sections match the Sipser book, both Editions 2 and 3

• Thursday, January 20
  Topic: Course Introduction, Notations, and Terminology (Slides)
  Reading: Sipser, Preface and Chapter 0
• Tuesday, January 25
  Topic: Deterministic Finite Automata (Slides)
  Reading: Sipser, Section 1.1
• Thursday, January 27
  Topic: Deterministic Finite Automata (cont.)
  Topic: Nondeterministic Finite Automata (Slides)
  Reading: Sipser, Section 1.2
• Tuesday, February 1
  Topic: Regular Expressions (Slides)
  Reading: Sipser, Section 1.3
• Thursday, February 3
  Topic: Nonregular Languages and the Pumping Lemma (Slides)
  Reading: Sipser, Section 1.4
  Topic: Context-Free Grammars (Slides)
  Reading: Sipser, Section 2.1
• Tuesday, February 8
  Topic: Context-Free Grammars (cont.)
  Topic: Pushdown Automata (Slides)
  Reading: Sipser, Section 2.2
• Thursday, February 10
  Topic: Pushdown Automata (cont.)
  Topic: Non-Context-Free Languages and the Pumping Lemma (Slides)
  Reading: Sipser, Section 2.3
• Tuesday, February 15
  Topic: Turing Machines (Slides)
  Reading: Sipser, Chapter 3
• Thursday, February 17
  Topic: Turing Machines (cont.)
  Reading: Sipser, Section 3.3
• Tuesday, February 22
  Topic: Decidable Languages (Slides)
  Reading: Sipser, Section 4.1
  Quiz #1
• Thursday, February 24
  Topic: Decidable Languages (cont.)
  Topic: Undecidability and Diagonalization (Slides)
  Reading: Sipser, Section 4.2
• Tuesday, March 1
  Topic: Reductions and Computation Histories (Slides)
  Reading: Sipser, Chapter 5
• Thursday, March 3
  Topic: Reductions and Computation Histories (cont.)
• Tuesday, March 8
  Topic: Reductions and Computation Histories (cont.)
• Thursday, March 10
  Topic: Reductions and Computation Histories (cont.)
  Topic: The Recursion Theorem (Slides)
  Reading: Sipser, Section 6.1
  Quiz #2
• Tuesday, March 22
  Topic: The Recursion Theorem (cont.)
• Thursday, March 24
  Topic: The Recursion Theorem (cont.)
  Topic: Logical Theories, (introduction to) Oracles (Slides)
  Reading: Sipser, Sections 6.2 - 6.3
• Tuesday, March 29
  Topic: Logical Theories, (introduction to) Oracles (cont.)
• Thursday, March 31
  Topic: Time Complexity, Big-O Notation, the Class P (Slides)
  Reading: Sipser, Sections 7.1 - 7.2
• Tuesday, April 5
  Topic: The Classes NP and coNP, The P versus NP Question (Slides)
  Reading: Sipser, Section 7.3
• Thursday, April 7
  Topic: NP-Complete Problems, the Cook-Levin Theorem, and (more) Reductions (Slides)
  Reading: Sipser, Sections 7.4 - 7.5
• Tuesday, April 12
  Topic: NP-Complete Problems, the Cook-Levin Theorem, and (more) Reductions (cont.)
• Thursday, April 14
  Topic: NP-Complete Problems, the Cook-Levin Theorem, and (more) Reductions (cont.)
  Topic: Space Complexity, Savitch's Theorem, the Class PSPACE (Slides)
  Reading: Sipser, Sections 8.1 - 8.2
• Tuesday, April 19
  Topic: Space Complexity, Savitch's Theorem, the Class PSPACE (cont.)
  Quiz #3
• Thursday, April 21
  Topic: PSPACE-Complete Problems (Slides)
  Reading: Sipser, Section 8.3
  Topic: The Classes L, NL, and coNL (Slides)
  Reading: Sipser, Sections 8.4 - 8.6
• Tuesday, April 26
  Topic: Intractable Problems and Hierarchy Theorems (Slides)
  Reading: Sipser, Section 9.1
• Thursday, April 28
  Topic: Intractable Problems and Hierarchy Theorems (cont.)
  Topic: Relativization and (more about) Oracles (Slides)
  Reading: Sipser, Section 9.2
  Topic: Circuit Complexity (Slides)
  Reading: Sipser, Section 9.3
• Tuesday, May 3
  Topic: Approximation Algorithms (Slides)
  Reading: Sipser, Section 10.1
• Tuesday, May 10
  Topic: Randomization, Probabilistic Algorithms, the Class BPP (Slides)
  Reading: Sipser, Section 10.2
• Thursday, May 12
  Topic: Interactive Proof Systems (Slides)
  Reading: Sipser, Section 10.4
  Quiz #4