Theory of Computation


Instructor:
Yijia Chen

Time:
1:30pm - 4:30pm every Wednesday

Textbook:

Introduction to the Theory of Computation
by Michael Sipser, Third Edition, 2012.



Slides:

(1) Sep. 16 Regular Languages
(2) Sep. 23 Non-Regular Languages, and Context-Free Languages
(3) Sep. 27 Context-Free Languages and Pushdown Automata
(4) Sep. 30 Pushdown Automata, Non-Context-Free Languages, and Turing Machines
(5) Oct. 14 Turing Machines and Variants
(6) Oct. 21 Algorithms and Decidability
(7) Oct. 28 Decidability and Undecidability
(8) Nov. 4 Mapping Reducibility
(9) Nov. 11 Time Complexity, P and NP
(10) Nov. 18 P vs. NP
(11) Nov. 25 NP-completeness (I)
(12) Dec. 2 NP-completeness (II)
(13) Dec. 9 NP-completeness (III)
(14) Dec. 16 Space Complexity (I)
(15) Dec. 23 Space Complexity (II)


Homework:

(1) Sep. 16
(2) Sep. 23
(3) Sep. 27/30
(4) Oct. 14
(5) Oct. 21
(6) Oct. 28
(7) Nov. 4
(8) Nov. 11
(9) Nov. 18
(10) Nov. 25
(11) Dec. 2
(12) Dec. 9
(13) Dec. 16


To view pdf files, you need Acrobat Reader.

Back


Yijia Chen, last modified: 23. 12. 2020