| Date | Topic | Reading or Title |
What's due (announcements) |
|---|---|---|---|
| Week 1 | |||
| Jan 4 | Overview, mathematical preliminaries, proofs. | 1.1-1.4. | . |
| Jan 5 |
Proofs, languages. Islanders with red eyes problem. |
1.4-1.8. |
Assignment #1 posted. Hats problem: logic.ps. Mathematical induction: Induction.pdf. |
| Week 2 | |||
| Jan 9 |
Proofs, cont., languages. Regular Expressions. |
Chapter 2. | . |
| Jan 11 |
DFAs. Odd numbers < 1010 problem. |
Chapter 2. | . |
| Jan 12 |
More DFAs, intro NFAs. Trick with 4 cards. |
Chapter 2. | . |
| Week 3 | |||
| Jan 16 | More NFAs. | Chapter 2. | . |
| Jan 18 | NFA = DFA, closure properties. | Chapter 2. |
|
| Jan 19 | NFA = RE, R(i,j,k) recurrence. | Chapter 2. |
Assignment #1 due.
Assignment #2 posted. |
| Week 4 | |||
| Jan 23 | Intro to pumping lemma. | Chapter 2. |
The amazing guide. Hummer shuffles: Chapter 1. Ron Graham. Article about Persi Diaconis. |
| Jan 25 |
More pumping lemma. |
Chapter 2. | . |
| Jan 26 |
FA and rational GF. Equivalence relations and state minimization. |
Chapter 2. | . |
| Week 5 | |||
| Jan 30 | Intro to CFLs. | Chapter 3. | . |
| Feb 1 |
Parse trees. Intro to PDAs. |
Chapter 3. | . |
| Feb 2 | Pumping lemma for CFLs. | Chapter 3. |
Imbolic (Wiccan), no exam / no work |
| Week 6 | |||
| Feb 6 | . | . | . |
| Feb 8 | |||
| Feb 9 | . | . |
Assignment #2 due.
|
| Week 7 | |||
| Feb 13 | READING BREAK. | READING BREAK. | READING BREAK. |
| Feb 15 | READING BREAK. | READING BREAK. | READING BREAK. |
| Feb 16 | READING BREAK. | READING BREAK. |
READING BREAK.
Assignment #3 posted. |
| Week 8 | |||
| Feb 20 | |||
| Feb 22 | MIDTERM |
MIDTERM |
MIDTERM |
| Feb 23 | |||
| Week 9 | |||
| Feb 27 | Midterm Solutions. | . | . |
| Feb 29 | Turing Machines. | . |
|
| Mar 1 | . | . |
Assignment #3 due.
Assignment #4 posted. |
| Week 10 | |||
| Mar 5 | |||
| Mar 7 | |||
| Mar 8 | Universal Turing Machines. | ||
| Week 11 | |||
| Mar 12 | The halting problem. | . | . |
| Mar 14 | Undecidable problems. | . | Shortest program. |
| Mar 15 | More undecidable problems. |
Hoare/Allison paper. Golly. HashLife. GoL news. GOL TM. Hackers |
Assignment #4 due.
Assignment #5 posted. |
| Week 12 | |||
| Mar 19 | Computational Complexity. | Chapter 6. | . |
| Mar 21 | . | . |
New Year's Day / Naw-Ruz / Navruz (Baha'i / Muslim) no exam / no work |
| Mar 22 | NP-completeness. | . |
Cook description (at Clay I.). Sipser talks about P vs NP. Proofs of P?NP. An interesting take. |
| Week 13 | |||
| Mar 26 | . | . | . |
| Mar 28 | More poly-time reductions. | Chapters 6 and 7. | SUBSET-SUM reduction. |
| Mar 29 | . | . |
|
| Week 14 | |||
| Apr 2 | . | . |
Holy Week (Orthodox Christian) no exam / no work. |
| Apr 4 | . | . |
Holy Week (Orthodox Christian) no exam / no work. |
| Apr 5 | . | . |
Holy Week (Orthodox Christian) no exam / no work. Assignment #5 due. |
| Week 15 | |||
| Apr 10 |
EXAMS BEGIN |
GOOD LUCK | GOOD LUCK |
| Apr 25 | EXAMS END | HAVE GREAT SUMMER! | HAVE GREAT SUMMER! |