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.

# | 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 | --- |