Your instructor will treat you as a professional, and you should plan on conducting yourself in an appropriate way. No behavior that compromises academic honesty (such as use of someone else's work or code, using prohibited materials during tests, or making your work available to others) will be tolerated in this course. If you need assistance with anything, do not hesitate to contact the instructor.
The ND Academic Code of Honor is in effect. It is expected that your work represents your own understanding of the problem. If work of others is used, it must be properly cited. Use of properly cited material is acceptable, but no referencing is treated as claiming the work as your own.
| Date | Topic | Textbook sections | Assignments |
| Tuesday, January 17 | Introduction and course outline | Chapter 0 | Read chapter 0 |
| Thursday, January 19 | Languages and finite automata | Section 1.1 | |
| Tuesday, January 24 | DFAs and NFAs | Sections 1.1-1.2 | hw1 is assigned |
| Thursday, January 26 | Equivalence of DFA and NFA classes | Section 1.2, handout | |
| Tuesday, January 31 | State minimization | Handout | hw1 is due, project 1 is assigned |
| Thursday, February 2 | Closures, finite state transducers | Sections 1.1-1.2, handout | |
| Tuesday, February 7 | Regular expressions, equivalence with finite automata | Section 1.3 | |
| Thursday, February 9 | Nonregular languages | Section 1.4 | project 1 is due at midnight, hw2 is assigned |
| Tuesday, February 14 | Nonregular languages | Section 1.4 | |
| Thursday, February 16 | Context-free languages and grammars | Section 2.1 | hw2 is due, hw3 is assigned |
| Tuesday, February 21 | Context-free grammars, ambiguity | Section 2.1 | |
| Thursday, February 23 | Chomsky normal form, push-down automata | Section 2.2 | |
| Tuesday, February 28 | Push-down automata, midterm review | Section 2.2 | hw3 is due |
| Thursday, March 1 | First midterm | Chapters 0 and 1 | hw4 is assigned |
| Tuesday, March 6 | Equivalence of CFGs and PDAs | Section 2.2, handout | |
| Thursday, March 8 | Deterministic PDA | Handout | hw4 is due, project 2 is assigned |
| Tuesday, March 13 | Spring break | ||
| Thursday, March 15 | Spring break | ||
| Tuesday, March 20 | Deterministic PDA | ||
| Thursday, March 22 | Review of first exam | ||
| Tuesday, March 27 | Non-context-free languages | Handout, Section 2.3 | project 2 due on 3/26 at midnight, hw5 is assigned |
| Thursday, March 29 | Non-context-free languages and Turing machines | Sections 2.3 and 3.1 | |
| Tuesday, April 3 | Turing machines | Section 3.1 | hw5 is due |
| Thursday, April 5 | Second midterm | Chapters 0 - 2 | |
| Tuesday, April 10 | Variants of Turing machines, decidability | Sections 3.2, 3.3, and 4.1 | project 3 is assigned |
| Thursday, April 12 | Undecidable problems | Section 4.2 | |
| Tuesday, April 17 | Reducibility | Section 5.1 | project 3 is due at midnight, hw6 is assigned |
| Thursday, April 19 | Reducibility, time complexity, class P | Sections 5.3, 7.1 and 7.2 | |
| Tuesday, April 24 | Class NP, review of second exam | Section 7.3 | hw6 is due, hw7 is assigned |
| Thursday, April 26 | NP-completeness | Section 7.4, handout | |
| Tuesday, May 1 | Course review, Introduction to cryptography | hw7 is due |