Assignments

Homeworks are due at 12:55PM before the start of class.

Make sure to attach the required cover sheet to the front of your homework. Your Banner ID should appear on all pages; please do not include your name anywhere.

Cover Sheet (pdf)
Cover Sheet (tex)

# Homework Topic Out In Solutions
0 Collaboration Policy Sep 7 Sep 14 ---
1 Review of Discrete Math Sep 7 Sep 14 SOL1
2 Functions and Circuits Sep 14 Sep 21 SOL2
3 Finite-State and Random-Access Machines Sep 21 Sep 28 SOL3
4 Turing Machines and Nondeterminism Sep 28 Oct 5 SOL4
5 Language Recognition and Complexity Classes Oct 5 Oct 12 SOL5
6 NP-Complete Languages Oct 12 Oct 19 SOL6
--- In-Class Midterm Oct 19 Oct 19 SOLM1
7 More NP-Complete Languages Oct 19 Oct 26 SOL7
8 Regular Languages Oct 26 Nov 2 SOL8
9 Phrase Structure Grammars Nov 2 Nov 9 SOL9
--- Take-Home Midterm Nov 9 Nov 16 SOLM2
10 Decidable and Undecidable Languages Nov 16 Nov 30 SOL10
11 Space-Time Tradeoffs and Approximation Algorithms Nov 30 Dec 7 SOL11
--- Final Exam Dec 14 Dec 14 ---