Assignments

Homeworks are due at 10:20AM before the start of class digitally through Gradescope. Unfortunately, due to a lack of a physical hand-in bin this season, we cannot accept baked goods alongside submissions.

Your Banner ID should appear on all pages; please do not include your name anywhere.

Before submitting any assignment, please make sure you read and subscribe to the class collaboration policy (linked below as Homework 0).

Late submission policy: Each student is given 4 late day passes to extend the submission deadlines of homeworks and midterms. However, no more than 2 passes may be applied to a given deadline. Additional late day passes may be granted by the instructors in consideration of extenuating circumstances (e.g., illness). Requests should be submitted to the instructors at least 24 before a deadline via a Google form.

# Homework Topic Out In Solutions
0 Collaboration Policy Sep 10 Sep 17 ---
0 Review of Discrete Math Sep 11 Sep 17 Solutions
1 DFAs and NFAs Sep 17 Sep 24 Solutions
2 Regular Languages and Pumping Lemma Sep 24 Oct 1 Solutions
3 Context-Free Grammars and Pumping Lemma Oct 1 Oct 8 Solutions
4 Turing Machines Oct 8 Oct 15 Solutions
- Midterm 1 Oct 15 Oct 22 Solutions
5 Turing Decidability and Rice's Theorem Oct 22 Oct 29 Solutions
6 Runtime, P and NP Oct 29 Nov 5 Solutions
7 NP and NP-Completeness Nov 10 Nov 17 Solutions
8 PSPACE Nov 17 Nov 24 Solutions
- Midterm 2 Dec 2 Dec 9