CPSC 229: Foundations of Computation
Syllabus Revisions for Weeks 9 through 15

Statement About the Pandemic

We have been thrown out of our regular classroom routine into a world of on-line classes, with almost no warning or time for preparation. And that is just one small aspect of a world dealing with a global crisis. There is no way that the rest of this course will be all that it would have been, but we all need to try to make the course as good as it can be under the circumstances. I will try to preserve some sense of continuity and normalcy in the course, and I will cover as much as possible of the material that we were originally scheduled to cover. However, I recognize that this is a time of great stress for all of us. I will try to take that into account, while at the same time running a rigorous and useful course.

I have your grades for the first eight weeks of the course. It is a fact of life in courses like this one that, with a few exceptions, most students' final grades do not differ all that much from their midterm grades. My policy for final grades will be that if you participate in the rest of the course and turn in homework that represents a reasonable attempt under the circumstances, then your final grade will not be lower than your midterm grade. (On my grading scale, the passing grade for a C- is 65%.) You will still have the opportunity to improve that grade, but you can only lower it by not participating in the rest of the course. More detailed policies are discussed below.

There is no way that on-line classes with Zoom can be as satisfactory as in-person classes. After one week of trying to lecture on-line, I find the experience to be difficult and exhausting. I really miss the sense of connection with people in the audience. However, I see some hopeful signs that the classes can still be worthwhile, if we work together to improve them. (I acknowledge that there is certainly room for improvement.)

Feedback about the course would be appreciated. Consider contributing to the "Running this course" discussion in Canvas. If you want to send more private comments, you can email me or message me in Canvas.

Participation Requirement

I hope to keep people from drifting away from this course. To help stop that from happening, I am imposing a participation requirement for the last five weeks of the course. The following are "participation events" that will count towards this participation requirement:

You should plan to have at least two "participation events" every week. I understand that this might not be possible every week, but even if you cannot participate in any of the ways listed above, you should try to send me at least a short email to let me know that you are still involved in the course.

Homework Assignments

There will be several more homework assignments, similar to the ones that were assigned before break. To help me keep homework submissions organized, I am asking that you turn in your work through Canvas, if possible. (If that is not possible for you for some reason, let me know.)

I will grade homework as usual, but as noted above, as long as you make an attempt to do most of the assignments, your grade on remaining assignments will not lower the grade that you had at midterm.

I will accept photos of your work, but photos are not easy to grade, so I would appreciate it if you could find better ways to submit. A PDF would be good. (There are apps that can scan documents with your phone's camera and assemble them into a PDF. If you know or want to learn LaTeX, you can use that to make nice PDFs.) Maybe you could use a drawing program to make diagrams instead of drawing them by hand. A Microsoft Word or OpenOffice/LibreOffice document would be OK. A plain text file would be OK for many homework problems; it would be OK to say, for example, "x in A" instead of "x ∈ A".

About Exams

Giving regular exams under the circumstances would be difficult or impossible. We were scheduled to have one-more in-class test and a final exam. I would like to eliminate the in-class test and replace the final exam with some kind of final assessment. The final assessment will probably be a take-home exam, given on the honor system, due during the exam period at the end of the semester. However, I am open to other ideas.

Tentative Schedule

Here is a tentative schedule of topics for the last five weeks of the course:

Week Topics Sections
Mar. 30 to Apr. 3 Nondeterministic finite automata (NFAs).
Converting NFAs to DFAs.
Converting regular expressions to NFAs.
3.5, 3.6
Apr. 6 to 10 The Pumping Lemma and non-regular languages.
Context-free grammars.
3.7,4.1
Apr. 13 to 17 Parsing and parse trees.
Pushdown automata.
4.3,4.4
Apr. 20 to 24 Non-context-free languages.
General Grammars.
4.5,4.6
Apr. 27 to May 1 Turing Machines and Computability.
5.1–5.3
May 4 Wrap-up and Review.