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 ---
7 More NP-Complete Languages Oct 19 Oct 26 ---
8 Regular Languages Oct 26 Nov 2 ---
9 Context-Free Grammars Nov 2 Nov 9 ---
--- Take-Home Midterm Nov 9 Nov 16 ---
10 Hard Languages and Approximation Algorithms Nov 16 Nov 30 ---
11 Space-Time Tradeoffs and Hierarchies Nov 30 Dec 7 ---
--- Final Exam Dec 14 Dec 14 ---