| Date | Class Period & Lecture Topic | Reading | Assignment | |
|---|---|---|---|---|
| Sep 03 | 1. What is the class about and how will it work? (Syllabus, policies, business) |
|||
| Sep 05 | 2. What tools should we use? (Introduction and basic concepts) |
Chapter 0 | pp. 1-25 | |
| Sep 08 | 3. Can we build a simple model of computation? (Finite automata) |
Chapter 1 | pp. 31-43 | 1 |
| Sep 10 | 4. What if we include a bit of magic in our model?
(Nondeterminism) |
pp. 47-54 | 2 | |
| Sep 12 | 5. What? Magic doesn't help? (Equivalence of DFAs and NFAs) |
pp. 54-63 | 3 | |
| Sep 15 | 6. Can we think of this another way? (Regular expressions) |
pp. 63-69 | 4 | |
| Sep 17 | 7. And, is this really the same thing? (Kleene's theorem) |
pp. 69-76 | 5 | |
| Sep 19 | 8. So, is this model good enough? (Nonregular languages) |
pp. 77-83 | 6 | |
| Sep 22 | 9. What if we aren't sure about how our "world" works? (Markov Chains) |
Additional Reading 1 | 7 | |
| Sep 24 | 10. What if we know even less about our "world"? (Hidden Markov Models) |
Additional Reading 2 | 8 | |
| Sep 26 | 11. Ok, then how about this better model? (Context free grammars) |
Chapter 2 | pp. 101-107 | 9 |
| Sep 29 | 12. This is getting confusing; can we do avoid that? (Ambiguity and normal form) |
pp. 107-111 | 10 | |
| Oct 01 | 13. How is this new model like our old one? (Pushdown automata) |
pp. 111-116 | 11 | |
| Oct 03 | 14. And are we thinking of it the right way? (Equivalence of CFGs and PDAs) |
pp. 117-124 | 12 | |
| Oct 06 | 15. So, now this better model is good enough, right? (Non-context free languages) |
pp. 125-129 | 13 | |
| Oct 08 | 16. What do we know so far? (Review) |
14 | ||
| Midterm 1 (October 7–10 in the testing center) | ||||
| Oct 10 | 17. No lecture (Midterm) | |||
| Oct 13 | 18. Why Should I consider Grad School? | |||
| Oct 15 | 19. How can we improve our model yet again? (Turing machines) |
Chapter 3 | pp. 165-173 | |
| Oct 17 | 20. And, what about some other possible improvements? (Variations on Turing machines) |
pp. 174-182 | 15 | |
| Oct 20 | 21. And, what does any of this have to do with writing code, anyway? (Algorithms) |
pp. 182-187 | 16 | |
| Oct 22 | 22. Ok, so what can our model do? (Decidable languages) |
Chapter 4 | pp. 193-200 | 17 |
| Oct 24 | 23. Wait, there's something it can't do? (Halting problem) |
pp. 201-207 | 18 | |
| Oct 27 | 24. Wait, there's lots of stuff it can't do? (Undecidable and unrecognizable) |
pp. 207-210 | 19 | |
| Oct 29 | 25. How can I tell what it can't do? (Reducibility) |
Chapter 5 | pp. 215-220 | 20 |
| Oct 31 | 26. Reducibility cont. | pp. 220-226 | 21 | |
| Nov 03 | 27. Even more reducibility | 22 | ||
| Nov 05 | 28. Can we, again, look at this another way? (Post correspondence problem) |
pp. 227-233 | ||
| Nov 07 | 29. And this helps us how? (Mapping [many-one] reducibility) |
pp. 234-238 | 23 | |
| Nov 10 | 30. So what do we know now? (Review) |
24 | ||
| Midterm 2 (November 10–13 in the testing center) | ||||
| Nov 12 | 31. No lecture (Midterm) | |||
| Nov 14 | 32. How can we decide if an algorithm is practical? (Big O analysis) |
Chapter 7 | pp. 275-284 | |
| Nov 17 | 33. What can our model do practically? (The class P) |
pp. 284-291 | 25 | |
| Nov 19 | 34. Wait, not everything it can do is practical? (The class NP) |
pp. 292-298 | 26 | |
| Nov 21 | 35. Are you sure? (The class NP-complete) |
pp. 299-304 | 27 | |
| Nov 24 | 36. So, magic might be useful after all? (Cook's theorem) |
pp. 304-311 | 28 | |
| Nov 25 | 37. Are there are lot of these nasty problems? (More NP-complete problems) |
pp. 311-322 | 29 | |
| Dec 01 | 38. Probabilistic Turing Machines | Additional Reading 3 | 30 | |
| Dec 03 | 39. No lecture (ICMLA) | |||
| Dec 05 | 40. Naive Bayes | Additional Reading 4 | 31 | |
| Dec 08 | 41. What about other ways of computing? (Quantum Computing, etc.???) |
32 | ||
| Dec 10 | 42. Finally, what do we know? (Review) |
|||
| Dec 12 | Reading Day | |||
| Dec 17 | Sec. 1 Final (11:00am–2:00pm in class) | |||
| Dec 19 | Sec. 2 Final (7:00am–10:00am in class) | |||
TA Schedule
(TA office is 3308 TMCB)
| Monday | Tuesday | Wednesday | Thursday | Friday | |
|---|---|---|---|---|---|
| 8:00 - 9:00 | Martin | Martin | |||
| 9:00 - 10:00 | Martin | Martin | |||
| 10:00 - 11:00 | Martin | Martin | |||
| 11:00 - 12:00 | Martin | Martin | Martin | ||
| 12:00 - 1:00 | Martin | Martin | Martin | ||
| 1:00 - 2:00 | Aaron | Aaron | Aaron | Aaron | Aaron |
| 2:00 - 3:00 | Derrall & Aaron | Derrall & Aaron | Derrall & Aaron | Derrall & Aaron | Derrall & Aaron |
| 3:00 - 4:00 | Derrall | Derrall & Aaron | Derrall | Derrall & Aaron | Derrall |
| 4:00 - 5:00 | Derrall | Derrall | |||
| 5:00 - 6:00 | |||||
| 6:00 - 7:00 | |||||
| 7:00 - 8:00 |