CS363: Theory of Computation (Spring 2017)

• Instructor: Huan Long, longhuan (at) sjtu.edu.cn
• Class: 12:55am - 15:40 every Monday
  
• Place: Dong ShangYuan 303
• TA: Xiuting Tao(陶秀挺）, xiutingtao@sjtu.edu.cn
• Office hour: 9:00pm - 10:00pm every Tuesday,
                          Location: Dianxin Building 3-327 (电信群楼3-327)

Announcement

• Feb. 20, 2017, Tip: you can always print multiple pages into one page. For example, to Adobe user: Print multiple pages per sheet.
• Feb. 20, 2017, Welcome to CS363.

PART I: Computability

1. Introduction(pdf)
2. Computable function(pdf)
3. Generating computable functions(pdf)
4. Church-Turing thesis (pdf)
5. Goedel number (pdf)
6. Universal program (pdf)
7. Decidability, undecidability, partial decidability (pdf)
8. Recursive and recursively enumerable sets (pdf)
9. Goedel's incompleteness theorem (pdf)
10. Reducibility and degrees (pdf)
11. The recursion theorem
12. Complexiy of computation

PART II: Automata and Language

1. Finite automata and regular language( pdf)
2. Context free language( pdf)

PART III: NP and computational complexity

1. Complexity ( pdf)
2. Propaganda ( pdf)

Assignments

• Week 01: Due 2017/02/27, Chapter 1: Section 3.3- 1.(c)(e),3,4; Section 4.3 - (a); Section 5.2 - 2.
• Week 02: Due 2017/03/06, Chapter 2: Section 4.16- 1.(e), 3, 4.(b)
• Week 03: Due 2017/03/13, Chapter 2: Section 5.4-1,2,3.
• Week 04: Due 2017/03/20, Chapter 4: Section 3.2-2,3,4; Section 4.4-2.
• Week 05: Due 2017/03/27, Chapter 5: Section 1.5-1.(i),(iii); Section 3.2-2,3.
• Week 06: Due 2017/04/01, Chapter 6: Section 1.8-1.(a),(d),(g),2.
• Week 07: Due 2017/04/08, Chapter 6: Section 6.14-7;Chapter 7: Section 1.4-1, Section 2.18-2,8.
• Week 08: Due 2017/04/17, Chapter 7: Section 2.18-11,13.
• Week 09: Due 2017/04/24, Chapter 7: Section 3.13-2,3,4.
• Week 12: Due 2017/05/15, Chapter 9: Section 1.7-3,4; Section 2.9-4
• Week 14: Due 2017/05/27, Introduction to the theory of computation Page 88, excercise 1.29, 1.30; page 131 exercise 2.30

Solution for selected assignments

• Chapter 1-8 (pdf)

References

• 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