| Problem Set 0 | Mathematical Preliminaries | Due Mon 9/14 at 1:20pm | [pdf] [tex template] |
| Problem Set 1 | Finite Automata | Due Fri 9/25 at 1:20pm (9/28 late) | [pdf] [part A tex template] [part B tex template] |
| Problem Set 2 | Regular Expressions, and Countability | Due Fri 10/2 at 1:20pm (10/5 late) | [pdf] [part A tex template] [part B tex template] |
| Problem Set 3 | Nonregular Languages and CFGs | Due Fri 10/9 at 1:20pm (10/12 late) | [pdf] [part A tex template] [part B tex template] |
| Problem Set 4 | Pushdown Automata, Closure Properties of CFLs, Non-CF Languages. | Due Mon 10/19 at 1:20pm (No Late Submissions) | [pdf] [part A tex template] [part B tex template] |
| Problem Set 5 | Chomsky Normal Form, Turing Machines | Due Fri 10/30 at 1:20pm (11/2 late) | [pdf] [part A tex template] [part B tex template] |
| Problem Set 6 | Decidability, Recognizability | Due Fri 11/6 at 1:20pm (11/9 late) | [pdf] [part A tex template] [part B tex template] |
| Problem Set 7 | Undecidability, Reductions | Due Fri 11/13 at 1:20pm (11/16 late) | [pdf] [part A tex template] [part B tex template] |
| Problem Set 8 | Computational Complexity, Polynomial Time | Due Fri 11/20 at 1:20pm (11/23 late) | |
| Problem Set 9 | NP, NP Completeness | Due Fri 12/4 at 1:20pm (12/7 late) |
We strongly recommend that you use LaTeX because it makes it easier to modify your answers without rewriting, and it makes it far easier for us to read what you wrote, so you'll never lose points for illegibility. If you do, you'll also get a 5% bonus to your pset score.
To use LaTeX, you'll need to install it--there are versions available for all major operating systems--see here.
Once you've done that, you can download the LaTeX source for the problem set you're working on to get the problem definitions, and just add your answers. You'll also need the cs121 class file: cs121.cls. (CSCI E-207 students should use the cscie207 class file instead, from the CSCI E-207 course webpage.) You can either put the class file in the directory where the problem set .tex file is, or add it to your TEXINPUTS path: on OS X or Linux, use something like:
setenv TEXINPUTS ":$HOME/files/tex"assuming you put the cs121.cls (or cscie207.cls) file in ~/files/tex, of course.