CS3313: Theory of Computation (Fall 2025)

• Instructor: Huan Long, longhuan (at) sjtu.edu.cn
• Class: 12:55 - 15:40 every Thursday
  
• Place: Dong ZhongYuan 2-403
• 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, 2025, Introduction to CS3313 .

PART I: Automata and Language

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

PART II: Computability

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

PART III: Computational Complexity

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

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, 2025