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

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