• Mathematical descriptions of languages and grammars, and categorization of languages according to how they can be mathematically described. This is the underpinning of several areas of computer science, in particular the study of compilers.
• Discussions of which problems can be solved algorithmically.
• Categorization of problems according to how efficiently they can be solved.

Some of the major ideas in the course predate computers themselves, going back to Allen Turings 1937 proof that the Halting Problem is not algorithmically solvable. This is largely a mathematics course. There will be no required programming assignments. Nevertheless, there are many ways in which this material will deepen your abilities as a programmer. There are also many places in the course in which coding the algorithms we discuss might expand your understanding of them.

• Syllabus
• Assignments to hand in
  • HW1, due on Wednesday, 2/15
  • HW2, due on Wednesday, 2/22
  • HW3, due on Wednesday, 3/1
  • HW4, due on Wednesday 3/15
  • HW5, due on Wednesday 3/22
  • HW6, due on Monday 4/10
  • HW7, due on Monday 4/17
  • HW8, due on Wednesday 5/3
  • HW9 (optional)