There will be almost-weekly written assignments, generally due in class on Monday or Wednesday (see the schedule)
and always provided electronically
(via this website) at least one week before their due date . Some of the exercises will be routine,
but others will be more challenging. I do not expect you to solve all of the homework problems,
but I hope that you will benefit from working on the more difficult ones. A few hints on the homework assignments:
- Start early: Difficult problems are not typically solved in one sitting.
Start early and let the ideas come to you over the course of a few days.
- Be rigorous: CSU390 is a theory course, so a certain level of mathematical rigor
will be expected in your solutions.
- Be concise: Express your solutions at the proper level of detail.
Give enough details to clearly present your solution, but not so many that the main ideas are obscured.
- Work with others:
Some of the problems will be difficult, and it will often be helpful to discuss them with others.
Feel free to form study groups. However, the idea is for everyone to understand the problems and
experience working through the solutions, so you may not simply "give" a solution to another classmate.
In particular, each student must write up his or her own homework solutions and
must not read or copy
the solutions of others. If you work with others on a problem, you must note with whom
you discussed the problem at the beginning of your solution write-up.
DUE DATES:
Homework assignments are due at the beginning of the class on Monday or Wednesday -- as indicated.
Instructions for submitting programming assignments will be provided later.
Week | Assignments | Due Date |
---|
|
0. Math Review
| 9/12 |
|
1. Finite State Automata
| 9/19
|
|
2. Nondeterministic Finite State Automata
| 9/26 |
|
3. Pumping Lemma, Regular Languages
| 10/3 |
|
4. Context-Free Grammars
| 10/17 |
|
4. Context-Free Grammars
| 10/17 |
|
5. Push-Down Automata
| 10/24 |
|
6. Turing Machines
| 10/31 |
|
7. Decidability
| 11/19 |
|
7. Decidability
| 11/19 |
|
8. Reducibility
| 11/28 |
|
8. Reducibility
| 11/28 |
|
9. NP-Completness
| 12/5 |
|
9. NP-Completness
| 12/5 |