Topics
This is a list of topics we'll cover in the course, together with an estimate of which weeks we'll spend on each topic.
The reading is optional, and you'll have access to the the course textbooks without buying them. Information about the textbooks is in the Textbooks section of the front page, and further reading is on the Further reading page.
For another view of the course topics, try this topic graph (source .dot file), but be warned that although I've tried to make it accurate and complete, I don't guarantee it covers everything. An arrow from A to B means it's helpful to know about A before learning B.
See also: the From class section of the More page.
Predicate and propositional logic
Weeks 1-2 (see online lectures before week 2)
Reading (optional):
- Textbook chapters:
- Mathematics for Computer Science, chapters 1.1–1.2, 3
- 236/240 course notes, chapters 5, 6
- Further reading:
- Learning to Reason, chapter 1
Proofs
Week 3 (watch online lectures first)
Reading (optional):
- Textbook chapters:
- Mathematics for Computer Science, chapters 1.3–1.9
- Further reading:
- How to Read and Do Proofs
- Learning to Reason, chapter 2
Induction
Predicted: Weeks 4-6
Reading (optional):
- Textbook chapters:
- Mathematics for Computer Science, chapters 2, 5, 7
- 236/240 course notes, chapters 1, 4
- Further reading:
- How to Read and Do Proofs
- Learning to Reason, chapter 2
Diagonalization and the Halting Problem
Predicted: Week 6
Reading (optional):
- Textbook chapters:
- Mathematics for Computer Science, chapters 4.1, 8.1–8.2
- Further reading:
- Learning to Reason, chapter 3
Correctness and Analysis of Iterative and Recursive Algorithms
Predicted: Weeks 7-10
Reading (optional):
- Textbook chapters:
- Mathematics for Computer Science, chapter 22
- 236/240 course notes chapters 2, 3
- Further reading:
- Introduction to Algorithms, chapters 2, 3, 4
Languages and Automata Theory
Predicted: Weeks 10-11
Reading (optional):
- Textbook chapters:
- An Introduction to Formal Languages and Automata, chapters 2-4
- 236/240 course notes, chapter 7