Instructor | Yuxin Deng |
---|---|

Office | Room B1115, Science Building |

Office Hour | 10am - 2pm, Monday - Friday |

Phone | 021-62231281 |

yxdeng(AT)sei.ecnu.edu.cn | |

Homepage | basics.sjtu.edu.cn/~yuxin/ |

- Michael Sipser. Introduction to the Theory of Computation (3rd edition). Cengage Learning. 2012.
- Harry Lewis and Christos H. Papadimitriou. Elements of the Theory of Computation (2nd Edition). Prentice-Hall, 1997.
- See also the nice slides made by Prof. Yijia Chen.
- Locally downloadable slides

- Finite automata
- Nondeterminism
- Regular languages
- Context-free languages
- Pushdown automata
- Turing machines
- Decidable problems
- Undecidable problems
- Reducibility
- The class P
- The class NP
- Space complexity
- Approximation algorithms
- Probabilistic algorithms

- Quizzes: 20%
- Assignments: 20%
- Written exam: 60%

Back