Home
Teaching
 
CS 390 Fl '07
General
Academic Honesty
Texts
Syllabus
Assignments
Communication
Ofc Hrs
Announcements

Assignments

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.

WeekAssignmentsDue Date
1     

0. Math Review

9/12
2     

1. Finite State Automata

9/19
3     

2. Nondeterministic Finite State Automata

9/26
4     

3. Pumping Lemma, Regular Languages

10/3
5     

4. Context-Free Grammars

10/17
6     

4. Context-Free Grammars

10/17
7     

5. Push-Down Automata

10/24
8     

6. Turing Machines

10/31
9     

7. Decidability

11/19
10     

7. Decidability

11/19
11     

8. Reducibility

11/28
12     

8. Reducibility

11/28
13     

9. NP-Completness

12/5
14     

9. NP-Completness

12/5

last updated on Mon Sep 17 11:20:26 EDT 2007generated with PLT Scheme