The schedule below is tentative, and may be subject to change. Changes will be announced in class, and you are responsible for knowing about any changes even if you miss the class when they are announced.
| Week | Topic | Notes | Homework |
|---|---|---|---|
| 1 | Boolean circuits | Week 01 | HW1 |
| 2 | Finite automata | Week 02 | HW2 |
| 3 | Nondeterministic finite automata | Week 03 | HW3 |
| 4 | Regular expressions & languages | Week 04 | HW4 |
| 5 | Pumping lemma, Midterm 1 | Week 05 | |
| 6 | Context free languages | Week 06 | HW5 |
| 7 | Pushdown automata | Week 07 | HW6 |
| 8 | Pumping lemma 2 | Week 08 | HW7 |
| 9 | Turing machines | Week 09 | HW8 |
| 10 | Decidability, Midterm 2 | Week 10 | |
| 11 | Enumerability | Week 11 | HW9 |
| 12 | Complexity theory | Week 12 | HW10 |
| 13 | Nodeterministic algorithms | Week 13 | HW11 |
| 14 | NP-completeness, Midterm 3 | Week 14 |
Attendance in this class is required. Repeated absences may result in a forced withdrawal from the course. You are responsible for any material you miss due to absence. Please let me know ahead of time if you know that you will not be able to attend class.
The term grade will be based on the following factors.
| Component | Proportion |
|---|---|
| Homework | 40% |
| Midterms | 30% |
| Final Exam | 30% |
There will be homework problems assigned every week. These will typically be collected on Mondays. I will drop the lowest homework grade. Late homework will only receive a fraction of the full possible grade.
There will be three in-class midterm exams and a cumulative final. These exams will be announced in advance, and you will know exactly what concepts will be covered on each exam.
My office hours are shown on my weekly schedule. I am also available by appointment. If you can’t stop by during my regular office hours, just ask me after class or by e-mail, and I’ll be happy to make an appointment that works for both of us.
Students who think they may need accommodations in this course because of the impact of a disability are encouraged to meet with me privately at the beginning of the semester. Students also should contact Melissa Wood, Title IX/504 Coordinator (mwood@hsc.edu, 434-223-6061) to verify their eligibility for reasonable accommodations. Early contact will help to avoid unnecessary inconvenience and delays.