CS 3500 A Theory I - Part 2

Topics

Date(s)

Reading

Introduction to Computability.
Decision Problems and Languages. Decidability.

Tue., Mar. 2

Reading:
Sipser Ch. 0, Sec. 3.3
1st set of Lecture Notes.

Undecidability of the Halting Problem.
Diagonalization and Reduction.

Thu., Mar. 4

Reading:
Sipser Sec. 4.2 pp. 165-167,
and Sec. 5.1 pp. 172-173
2nd set of Lecture Notes.

More Undecidable Problems.
Reductions Revisited and Formally Defined.

Tue., Mar. 16

Reading:
Sipser Sec. 5.1 pp. 172-176
and Sec. 5.3
3rd set of Lecture Notes.

Introduction to Complexity.
Lower Bound for Comparison-Based Sorting.
The Complexity Classes P and NP .

Thu., Mar. 18

Reading:
CLRS Sec. 8.1
Sipser Sec. 7.2, 7.3
4th set of Lecture Notes.

The class NP
P vs NP

Tue., Mar. 23

Sipser Sec. 7.2, 7.3
5th set of Lecture Notes.

Polynomial Time Reduction
NP-Completeness
The Cook-Levin Theorem: SAT is NP-Complete
More NP-Complete Problems

Tue., Mar. 30

Sipser Sec. 7.4
6th set of Lecture Notes.

More NP-Complete Problems

Thu., Apr. 1

Sipser Sec. 7.4, 7.5, CLRS 34.5
7th set of Lecture Notes.