• 必读：第0章
  Reading: Chapter 0
• 讲义1，大纲
  Handout 1, General Information
• 作业1，第4日开始上课时缴交。
  Homework 1 out, due Day 4 at the beginning of class (PDF)

复习 1 (第2日)：数学复习
Recitation 1 (Day 2): Math Review

• 必读：第0章
  Reading: Chapter 0
• 讲义2：数学复习
  Handout 2: Math Review (PDF)

• 确定性有限自动机(FA) 与其可接受的语言
  Deterministic Finite Automata (FA) and the languages they accept
• 必读：1.1 节
  Reading: Section 1.1

课程 3 (第4日)：不确定性有限自动机
Lecture 3 (Day 4): Nondeterministic Finite Automata

• 不确定性有限自动机(FA) 与其可接受的语言
  Nondeterministic FA & languages they accept
• 确定性有限自动机(DFA)与不确定性有限自动机(NFA)相等的条件
  Equivalence of DFA and NFA
• 必读：1.2 节
  Reading: Section 1.2
• 作业1缴交日
  Homework 1 due
• 作业2，第7日开始上课时缴交
  Homework 2 out, due Day 7 at the beginning of class (PDF)
• 一般来说，作业的范围不会超出教材与课程的范围。
  In general homework covers material covered up to and including the lecture in which it is handed out

复习2 (第5日)
Recitation 2 (Day 5)

• 有限自动机复习
  Review of FA

课程 4 (第6日)：正规表示式
Lecture 4 (Day 6): Regular Expressions

• 正规表示式
  Regular Expressions
• 引理1.29 (用正规表示式方式描述正规语言)
  Lemma 1.29 (Regular expressions describe regular languages)
• 必读：1.3 节
  Reading: Section 1.3

课程5 (第7日)：正规表示式补充
Lecture 5 (Day 7): More Regular Expressions

• 定理 1.28，引理 1.32
  Theorem 1.28, Lemma 1.32
• 作业2缴交日
  Homework 2 due
• 讲义3：随堂练习
  Handout 3: Quiz practice problems (PDF)

复习3 (第8日)
Recitation 3 (Day 8)

• 正规表示式与正规语言的复习
  Review of regular languages, expressions
• 讲义4：复习的问题
  Handout 4: Recitation Problems (PDF)

课程6 (第9日)：自动机结尾
Lecture 6 (Day 9): End of Automata

• 非正规语言
  Non-regular languages
• 推入引理
  Pumping Lemma
• 必读：1.4 节
  Reading: Section 1.4

课程7 (第10日)：测验1
Lecture 7 (Day 10): Quiz 1

• 随堂考1
  Quiz 1 (PDF), in class
• 范围：课程1~6
  Covers lectures 1 through 6
• 作业3，第13日缴交
  Homework 3 (PDF) out, due Day 13

复习4 (第11日)
Recitation 4 (Day 11)

• 随堂考复习
  Quiz Review

• Turing机导论
  Introduction to Turing Machines
• Church-Turing 论题
  Church-Turing Thesis
• 多磁带 Turing 机
  Multi-tape Turing Machines
• 必读：第3章
  Reading: Chapter 3

课程9 (第13日)：不确定性 II
Lecture 9 (Day 13): Non-determinism II

• 不确定性的 Turing 机并没有更好
  Non-deterministic Turing Machines are no better
• “可决定的语言”的定义；范例
  Definition of Decidable Languages; Examples
• 必读：4.1 节
  Reading: Section 4.1
• 作业3缴交日
  Homework 3 due
• 作业4，第16日缴交
  Homework 4 out, due Day 16 (PDF)

复习5 (第14日)
Recitation 5 (Day 14)

• Turing 机
  Turing Machines
• 讲义9：复习问题集
  Handout 9: Recitation Problems (PDF)

课程10 (第15日)：不可判定性
Lecture 10 (Day 15): Undecidability

• 停机问题
  The Halting Problem
• 停机问题是不可判定的
  The Halting Problem is Undecidable
• 必读：第4.2章
  Reading: Chapter 4.2

课程11 (第16日)：不可判定性 II
Lecture 11 (Day 16): Undecidability II

• Post对应问题是不可判定性的
  Post Correspondence Problem is Undecidable
  (译注：一般译为“波斯特对应问题”)。
• 必读：5.2 节
  Reading: Section 5.2
• 作业4缴交日
  Homework 4 due
• 作业5，第19日缴交
  Homework 5 out, due Day 19 (PDF)

复习6 (第17日)
Recitation 6 (Day 17)

• 不可判定性
  Undecidability

课程12 (第18日)：不可判定性III
Lecture 12 (Day 18): Undecidability III

• 更多不可判定的问题
  More Undecidable Problems
  o 计数器
    Counter Machines
     - Kozen 课程 I (第269页)
       Lecture I (page 269) of Kozen
  o 生存游戏 (模拟可在 http://www.math.com/students/wonders/life/life.html 找到)
     The Game of Life (simulation to be found at http://www.math.com/students/wonders/life/life.html)

课程13 (第19日)：简化
Lecture 13 (Day 19): Reductions

• 简化与对应可简化性
  Reductions and Mapping Reducibility
• 必读：5.3 节
  Reading: Section 5.3
• Rice定理：会发Kozen的讲义34的影本。
  Rice's Theorem: A photocopy of Lecture 34 from Kozen was passed out
• 作业5缴交日
  Homework 5 due

复习7 (第20日)
Recitation 7 (Day 20)

• 不可判定性与递回
  Undecidability and Recursion

课程14 (第21日)：可计算性结尾
Lecture 14 (Day 21): End of Computabillity

• 计算机病毒与不可判定性
  Computer Viruses and Undecidability

课程15 (第22日)：测验2
Lecture 15 (Day 22): Quiz 2

• 随堂考2
  Quiz 2, in class (PDF)
• 范围：课程8~14
  Covers lectures 8 through 14
• 测验2a，不在课堂上举行的补考
  Quiz 2a, a make-up test not given out in class (PDF)
• 作业6，第 24日缴交
  Homework 6 out, due Day 24 (PDF)

• 复杂性理论导论
  Introduction to Complexity Theory
• 时间复杂度
  Time Complexity
• P 类别
  The Class P
• 必读：7.1 - 7.2 节
  Readings: Sections 7.1 - 7.2

课程17 (第24日)：不确定性复杂度
Lecture 17 (Day 24): Nondeterministic Complexity

• NP类别; 范例
  The Class NP; Examples
• P 与 NP
  P vs. NP
• 必读：7.3 节
  Reading: Section 7.3
• 作业6缴交日
  Homework 6 due
• 作业7，第26日缴交
  Homework 7 out, due Day 26 (PDF)

复习9 (第25日)
Recitation 9 (Day 25)

• 复杂度类别
  Complexity Classes

课程18 (第26日)：NP-完整
Lecture 18 (Day 26): NP-Completeness

• NP 完整
  NP Completeness
• 多项式时间的可简化性
  Poly-time Reducibility
• 必读：7.4 节
  Reading: Section 7.4
• 作业7缴交日
  Homework 7 due
• 作业8，第29日缴交
  Homework 8 out, due Day 29 (PDF)

复习10 (第27日)
Recitation 10 (Day 27)

• 简化
  Reductions
• 讲义14以问题集形式发放
  Handout 14 given out as problems (PDF)

课程19 (第28日)：Cook-Levin 定理
Lecture 19 (Day 28): Cook-Levin Theorem

• Cook-Levin 定理的叙述与证明
  Statement and Proof of Cook-Levin Theorem

课程20 (第29日)：NP-完整 II
Lecture 20 (Day 29): NP-Completeness II

• 附加的NP-完整 问题
  Additional NP-complete Problems
• 必读：7.5 节
  Reading: Section 7.5
• 作业8缴交日
  Homework 8 due

复习11 (第30日)
Recitation 11 (Day 30)

• 更多关于 NP-完整 的资讯
  More on NP-completeness
• 讲义16以问题集形式发放
  Handout 16 given out as problems (PDF)

课程21 (第31日)：NP-完整 III
Lecture 21 (Day 31): NP-Completeness III

• 附加的NP-完整 问题
  Additional NP-complete Problems

课程22 (第32日)：测验 3
Lecture 22 (Day 32): Quiz 3

• 随堂考3
  Quiz 3, in class (PDF)
• 范围：课程16-21
  Covers Lectures 16-21
• 作业9，第35日缴交
  Homework 9 out, due Day 35 (PDF)
• 测验3a，不在课堂上举行的补考
  Quiz 3a, a make-up test not given out in class (PDF)

复习12 (第33日)
Recitation 12 (Day 33)

• 选修课程：NP延伸出的复杂度类别。
  Optional lecture on Complexity Classes Beyond NP

• 概率算法
  Probabilistic Algorithms
• 可以在 http://www.cs.ucsd.edu/~russell/RANDCLASS/outline.html　找到更多关于Min-Cut算法的资讯。
  More information about the Min-Cut algorithm can be found at http://www.cs.ucsd.edu/~russell/RANDCLASS/outline.html

课程24 (第35日)：随机 II
Lecture 24 (Day 35): Randomness II

• 概率算法
  Probabilistic Algorithms
• 讲义来自Randomized 算法 (Motwani 与 Raghavan) 会在课堂上发给各位，其他在课堂抽屉里。
  Handout from Randomized Algorithms (Motwani and Raghavan) given out in class. Extras in course drawer
• 附加的教材可以在 http://icg.harvard.edu/~cs225/Scribenotes/ 的标注的第2节中找到。
  Additional material can be found in Section 2 of the scribe notes at http://icg.harvard.edu/~cs225/Scribenotes/
• 作业9缴交日
  Homework 9 due

复习13 (第36日)
Recitation 13 (Day 36)

• 概率算法
  Probabilistic Algorithms
• 讲义19以问题集形式发放
  Handout 18 given out as problems (PDF)

课程25 (第37日)：密码学
Lecture 25 (Day 37): Cryptography

• 密码学与复杂度理论
  Cryptography and Complexity Theory
• 必读：10.6节，讲义
  Readings: Section 10.6, handout

课程26 (第38日)：密码学 II
Lecture 26 (Day 38): Cryptography II

• 密码学与复杂度理论
  Cryptography and Complexity Theory

复习14 (第39日)
Recitation 14 (Day 39)

• 取消！
  Canceled!

期末考(第40日)
Final Exam (Day 40)

• 期末考：3 小时，7 个问题
  Final exam: 3 hours, 7 problems (PDF)