CS440 Theory of Computation

CS 440 Theory of Computation

3 credits

Spring 2024

General Information

Instructor:

Student Learning Information

Course Description

Finite automata, regular sets, and regular expressions; pushdown automata, context-free languages, and normal forms for grammars; Turing machines and recursively enumerable sets; Chomsky hierarchy; computability theory.

Statement of Expected Learning

The course objectives are to:

As learning outcomes, students completing this course should be able to:

Course Materials

The main textbook is a draft textbook in preparation by Professor Gordon, "Automata Theory in Context" (ATiC). The text will be uploaded into BBLearn, and regularly updated throughout the term. All students are encouraged to email Professor Gordon if they find any part of the text confusing, misleading, or technically incorrect, or with any other suggestions, regardless of how well you feel you are doing in the course.

There is a supplementary textbook, the freely-available Automata, Computability, and Complexity Theory and Applications (abbreviated as ACCTA), which students can use as an additional resource.

Readings will be assigned in pairs, from both ATiC and ACCTA, though students only need to read from one textbook each time. Naturally professor Gordon recommends his own textbook draft, but ACCTA is still an excellent textbook, and students who would prefer to stick to a textbook that is not still in the process of being written are welcome to do all of their reading from ACCTA. No preference will be given to students preferring one book over the other.

Required and Supplemental Materials and Technologies

Later, the course may include a few small programming assignments with an automata library in Racket to make the theoretical constructions' relevance to practice clearer.

Getting Help

The best way to get help is to use the course Discord channels, email the professor and TA (both at once means you'll probably get answers sooner), or show up to office hours.

Examples of questions that are best for Discord include:

These are good for Discord because they're questions of general interest which don't go into too much detail about specific code or proofs you're writing.

Examples of questions that are best for email or office hours only:

Questions about personal circumstances (e.g, extension requests) should go to the professor only, via email.

Assignments, Assessments, and Evaluations

Graded Assignments and Learning Activities

The course grade is based on a mixture of graded in-class activities (for which you'll want to do reading beforehand, see below) and at-home assignments. The last of these is a take-home exam due during finals week.

Readings

Each week except the first, you will have assigned readings from Professor Gordon's draft book ATiC and/or ACCTA, due before the Tuesday class, which will form the foundation for the week's class time. Reading does take time, and while the readings will often be challenging due to the concepts involved, they will generally be fairly short readings.

While there will not be actual quizzes on the reading, it is essential that you do the reading! This course covers subtle and complex ideas. Class time alone is \emph{not} enough to fully internalize what's going on in the material, and the lecture (below) is designed assuming that you have been keeping up on the reading.

I realize assigned readings are not popular, but consider this: reading outside class, you're engaging with the material at your speed. If you need to go back over something, you can do that as many times, in as many places as you like. It's also an additional step in learning: only so much learning happens the first time you see a new bit of material.

In-class Activities

Lecture each class period will consist of roughly half recap of the reading, including clarifications, followed by small in-class activities in small groups (typically 3 students, unless you really want to work solo). Occasionally we will have classes that lean more heavily towards lecture (such as the first class), or more heavily towards activities.

You'll be given paper to work on, but please bring writing implements (ideally pencils with working erasers).

The in-class problem sets are meant to help you quickly try to apply new material, and to discover what you do and don't understand. The expectation is that nobody will fully grasp the material immediately, so the activities are graded based on active participation and demonstrated learning rather than absolute correctness. They should not be a source of grade stress.

To receive credit for the in-class activities, you must be in class! If you have to miss class for a legitimate reason you can make up the activity, subject to the attendance guidelines below.

Your lowest 2 activity grades will drop automatically unless they are due to unexcused absence (i.e., a 0 from an unexcused absence will not drop).

Take-Home Assignments

The remainder of your grade comes from take-home assignments.

Take-home assignments are larger and more difficult than in-class activities, typically involving a mix of more in-depth problems (which will build on in-class examples). You will have 1 week to work on each, and you should expect 10 assignments.

The final assignment is due during finals week, as your final exam (but is still weighted the same as other take-home assignments).

You have 5 late days to use on these assignments as you see fit. You do not have to ask in advance to use one or more late days, simply hand in however late you intend. EXCEPT for the final exam: you may not apply late days for the final because we need to submit grades for the term. Unused late days do not convert to extra credit.

You do have the option to work with a partner for any (or all) homeworks (only one partner per homework) and submit together. You're allowed to switch between solo and partnered work, or switch partners, between any assignments, as long as each assignment is either done by yourself or with just one partner for that assignment.

There is a catch, though: each of you will need to individually come to Professor Gordon's office hours (or schedule a separate appointment) and you will be asked a couple quick questions about your submission. If you both do well (it's a light check to see if you understand what you submitted, not an in-depth oral exam), you both get the same grade. This usually takes about 5 minutes, half of which is Professor Gordon looking up the submitted assignment. (If the assignment is submitted late, you both use that number of late days.) If your responses give me reason to believe one of you did all of the work and the other was just along for the ride, you may be given an alternate assignment to do as individuals.

You may not discuss the assignments with any students other than your partner if you have one.

Grading Matrix

The late/skip policies were described above.

In addition to the late and skip policies, extensions are possible for good reason with reasonable notice.
I am aware that students have jobs, family matters, paper deadlines if involved in research, etc., which can interfere with completing assignments. I want your grade to reflect your mastery of the material and quality of work you hand in, not whether or not you were fortunate enough to avoid major life events during the term. If something comes up during the term, let me know. If it's unexpected (e.g., you end up in the ER when you were planning to work on coursework), let me know when you can and we'll figure it out. If it's something you know about in advance (e.g., you must travel for work), let me know as soon as you know, and we can discuss whether we should give you an extension on an assignment.
I reserve the right to request supporting evidence for your stated need for an extension (only so far as justifying the existence of a good excuse; e.g., I might ask for a note confirming existence of a health issue interfering with attendance or assignment completion, but I don't need to know the details of the particular health issue).

Attendance

Attendance is required for all classes at the University; non-attendance, even if it's not graded, can lead to a wide array of complications if things go wrong for you (student visas, financial aid, athletics participation, and many other things are all contingent upon attendance).

In this class the graded in-class activities clearly add an additional impetus to attend.

If you must miss class for good reason, let me know as soon as you know. If you know ahead of time that you have to miss class for a job interview, a critical medical appointment, a funeral, etc., let me know as soon as you know, and we'll coordinate on making up the in-class activity.

If you don't let me know ahead of time, you will receive a 0 for that class's activities. (EXCEPT for cases of medical emergency, of course; in those cases get yourself taken care of first, we'll sort out class stuff later.)

Academic Integrity, Cheating, and Plagiarism

The list of links at the end of the syllabus include a link to the University's academic integrity policy. If you haven't actually read it before, you should, because not meaning to plagiarize is not an excuse for plagiarism. This includes not realizing that something needed to be quoted, or being unfamiliar with the idea that paraphrased sentences still require citation (and possibly quotes), or opting to reuse someone else's words or code because you're not confident in the quality of your own.

The general idea is that you should not submit work that is not your own --- code or written prose or proofs --- that is not properly attributed. This includes, but is not limited, to things like putting direct quotes from someone else's writing in quotes and citing the source, and giving the source for small snippets of code you might have taken from StackOverflow or similar. Again, you should read the actual university integrity policy.

The University leaves the penalty for cheating, plagiarism, etc. in a course up to the professor. If you cheat in this class, I will give you an F for the term. I realize that most cheating is a consequence of poor time management, or unexpected or hard-to-manage obligations beyond the class, rather than trying to put one over on the professor.
That is exactly why you have late days for homeworks and the course has a fairly flexible extension policy - I want you to succeed, but I want you to do so honestly. If you have any doubts about whether something might cross the line into cheating, please ask me before you do it. The worst I'll say is "No, don't do that."
And I'll be glad you asked. This is far better than an F for the term.

To avoid misunderstandings, please do not share pieces of your assignments via Discord.

Two final notes:

First, if you quote or reuse other sources (properly, with attribution) so heavily I feel like you haven't actually done the work for the assignment/response, I'll give you a 0 for the assignment because you didn't actually do the work. But that's not technically plagiarism so won't result in academic misconduct procedures.

Second, a popular question these days is what to do with ChatGPT. Submitting ChatGPT answers (or output from similar systems, even if edited) is considered cheating in this course, because if you ask ChatGPT how to do something you're not submitting your own work. However, there are two much more important reasons not to use ChatGPT in this course:

  1. Asking ChatGPT to do a problem for you will short-circuit the learning that's supposed to happen when you think about the problems yourself. You won't learn.
  2. ChatGPT will give you wrong answers with absolute confidence; these systems simply won't be effective in helping you for this course. ChatGPT and similar systems simply do not have any notion of whether the text they generate makes true or false claims; there is no notion of truth in their training data, only token frequencies. If most training data on a certain topic happens to encode true facts, they will probably not regurgitate falsehoods (but that can still happen due to quirks in how the probabilities of the training data are smoothed). If you ask ChatGPT to do a proof, it will give you something that might superficially look like a proof. But language models don't capture any form of logical consequence, so steps are likely to be re-ordered, proofs are likely to come out with pieces of similar-but-critically-different proofs mixed together, or omitting critical reasoning steps that are actually what would earn most of the grade for a question.

The short version: using ChatCPT and similar systems isn't permitted in this class, but independent of that, trying to use them is almost certainly more work than just doing the work yourself, due to the nature of the course.

I also recommend against trying to use ChatGPT as a tutor for the topics in this course. While this is an increasingly popular idea (I recommend reading Failure to Disrupt for why it's also a very naive idea, pedagogically speaking), it tends to work very poorly for CS theory, because the systems make up examples where it gets all the details wrong --- when the details are usually what students are already confused about. I have never met more confused students than those who tried to use ChatGPT as a tutor for automata theory topics, and spent hours trying to make sense of broken examples. Save yourself the frustration and just read the book(s) and come to office hours (this is exactly why we have office hours!).

Grade Scale

The following scale will be used to convert points to letter grades:

Grade
97-100 A+ 82-86.99 B 70-71.99 C-
92-96.99 A 80-81.99 B- 67-69.99 D+
90-91.99 A- 77-79.99 C+ 60-66.99 D
87-89.99 B+ 72-76.99 C 0-59.99 F

Note that the instructor may revise this conversion if/when necessary.

Course Schedule

(This schedule is tentative and may change during the course.)

Week by week:

  1. Introduction, Overview

Academic Policies

This course follows university, college, and department policies, including but not limited to:

The instructor(s) may, at his/her/their discretion, change any part of the course before or during the term, including assignments, grade breakdowns, due dates, and schedule. Such changes will be communicated to students via the course web site. This web site should be checked regularly and frequently for such changes and announcements.

Students requesting accommodations due to a disability at Drexel University need to request a current Accommodations Verification Letter (AVL) in the ClockWork database before accommodations can be made. These requests are received by Disability Resources (DR), who then issues the AVL to the appropriate contacts. For additional information, visit the DR website at drexel.edu/oed/disabilityResources/overview/, or contact DR for more information by phone at 215.895.1401, or by email at disability@drexel.edu.