CS3313: Theory of Computation (Fall 2024)

• Instructor: Huan Long, longhuan (at) sjtu.edu.cn
• Class: 12:55 - 15:40 every Thursday
  
• Place: Dong ShangYuan 107
• TA: TBA
• Office hour: 9:00am - 11:00am every Tuesday,
                          Location: Dianxin Building 3-327 (电信群楼3-327)

Announcement

• An adverced version of this course: Computational Complexity, by Prof. Yuxi Fu.
• Sep. 14, 2024, Introduction to CS3313 .

PART I: Automata and Language

1. Finite automata and regular language (pdf)
2. Pushdown automata and context free language (pdf)
3. (*) Deterministic Context-Free Languages (pdf)

PART II: Computability

1. The Church-Turing Thesis (pdf)
2. Decidability (pdf)
3. Reducibility (pdf)
4. (*) Goedel Number (pdf)

PART III: Computational Complexity

1. Time Complexity (pdf)
2. NP-completeness (pdf)
3. Space Complexity (pdf)
4. The log Space (pdf)
5. Intractability (pdf)

Assignments

1. CANVAS

References

• Introduction to the Theory of Computation, Michael Sipser, Third Edition, 2012.
• 计算复杂性, 傅育熙，清华大学出版社，2023.
• N.J.Cutland, Computability:An introduction to recursive function theory, 1980
• Robert I. Soare, Recursively Enumerable Sets and Degrees: A study of computable functions and computably generated sets, 1987

Last updated: Sep. 14, 2024