Course Schedule

- Lecture 1: Overview and Fundamental Concepts
- Lecture 2: The Regular Languages
- Lecture 3: Regular Languages, continued
- Lecture 4: Context-Free Languages and Chomsky Normal Form
- Lecture 5: Pushdown Automata
- Lecture 6: The Existence of Non-Context-Free Languages
- Lecture 7: Computability
- Lecture 8: Decidable Languages
- Lecture 9: Halting Problem
- Lecture 10: Undecidable Problems
- Lecture 11: PCP and Reductions
- Lecture 12: Time Complexity Classes
- Lecture 13: Classes P and NP
- Lecture 14: NP-Complete Problems
- Lecture 15: More NP-Complete Problems
- Lecture 16: Savitch's Theorem
- Lecture 17: PSPACE and PSPACE Complete Problems
- Lecture 18: NL

**
Wednesday, January 18
Overview and Fundamental Concepts
**
We go over the course organization. Then we motivate the course content.
We also go over some fundamentals from CSC 173 to refresh our memory.

**
Monday, January 23
Chapter 1: The Regular Languages
**
We review the concepts of regular languages and finite automata,
including the descriptive

**
Wednesday, January 25
Chapter 1: The Regular Languages, continued
**We show that the regular languages are

**
Monday, January 30
Section 2.1 — Context-free Languages
**

We recall the notions of context-free languages and parse trees and learn the concept of ambiguity. We also learn a type of CFG called

**
Wednesday, February 1 & Monday, February 6
Section 2.2 — Pushdown Automata
**

**
Wednesday, February 8 & Monday, February 13
Section 2.3 —
The Existence of Non-context-free Languages
**

We study and prove the

**
Wednesday, February 15
Chapter 3: Computability Theory
**
We recall the concept of Turing machines and study variants of Turing
machines
(

**
Monday, February 20
Section 4.1 — Decidable Languages
**
A language is

**
Wednesday, February 22
Section 4.2 - The Halting Problem
**
There are problems that are not Turing-decidable. We show here that

**
Monday, February 27 & Wednesday, March 1
Section 5.1 — Undecidable Problems
**
We learn the technique of reducing the undecidability of a problem
to another. To prove a problem

**
Monday, March 6 (continued March 8)
Sections 5.2 & 5.3 —
PCP and Reductions
**
We show the undecidability of a simple, puzzle-like problem called

**
Wednesday, March 8
Sections 5.2 & 5.3 —
PCP and Reductions (cont'd from March 6)
**
We formalize the concept of

**
Monday, March 13 - Friday, March 17, Spring Break
**

**
Wednesday, March 20
Problem Session
**

Wednesday, March 22

* NON-CUMULATIVE EXAM I *

Covers up to Chapter 5 (inclusive).

**
****
Monday, March 27
Section 7.1 — Time Complexity Classes
**
We introduce the concept of

**
Wednesday, March 29
Section 7.1 — Time Complexity Classes (cont'd)
**

**
Monday, April 3 & Wednesday, April 5
Sections 7.2 & 7.3 — Classes P and NP
**
We study the two most important time complexity classes,

**
Monday, April 10
Section 7.4 — NP-complete Problems
**
A NP-complete problem is one of the ``most difficult'' problems in NP,
in the sense that each problem in NP is

**
Wednesday, April 12
Section 7.5 — More NP-complete Problems
**
Thousands of practical and important problems have been identified as
being NP-complete. We review the proofs of NP-completeness of some such
problems, including

**
Monday, April 17
Section 8.1 — Savitch's Theorem
**
We introduce the concept of the

**
Wednesday, April 19
Sections 8.2 & 8.3 — PSPACE and
PSPACE-complete Problems
**
We introduce the polynomial space class, written as

**
Monday, April 24
Section 8.4, 8.5, and 8.6 — NL
**
We study logarithmic space classes

**
Wednesday, April 26
Problem Session
**

**
Monday, May 1
Problem Session
**

**
Wednesday, May 3
NON-CUMULATIVE EXAM II
**
Covers Chapters 7 and 8.