• The Halting Problem (Rosen 3.1)
• lecture: material from pages 176 to 177
• Complexity (Rosen 3.2 3.3)
• 3.2 sets the scene with the Growth of Functions
• 3.3 on Complexity and see below
• Examples will be given from outwith the text book
• The Pigeonhole Principle (Rosen 5.2)