Syllabus

Introduction
Diversity and Inclusion
Evaluation
Mental Health, or: Why We Often Fall Behind
Help, Collaboration, and Academic Honesty

Introduction

In your journey through computation, you likely have noticed that many problems can be solved with the same solution through a skill you have honed called abstraction. Through this process, you may have noticed more nuanced connections between problems. Some problems require some translation before being solved using the solution to another problem. Other problems are immune this sort of transformation and feel fundamentally more difficult than others. Some problems feel downright impossible to solve—are they actually impossible?

In this course, we study the theory of computation where we use mathematics to model problems of increasing complexity and study their relationships with each other. By going through this modeling process, we can:

Deeply understand a problem and its potential corner cases.
Prove properties of a problem, e.g., the correctness a candidate solutions.
Reduce a problem to another problem, i.e, formally solve one problem in terms of another.
Categorize a problem as easier or harder than other problems in a precise way.

By the end of the course, we will explore the limits of computation. Are there problems that are intractable in practice? Are there problems that can provably never have a solution?

Learning Outcomes

I want you to see that the concrete and the abstract are symbiotic. In particular, I hope you will leave this course with the ability to identify abstractions in your own work. This is to say, to

identify problems that can be solved by solutions to other problems; and
identify structures that radically simplify a task or problem.

Further, I would like you to see that computation is a concept manifested in one of many forms on physical machines. In the past, you have likely learned to believe the opposite: that computation is a phenomena manifested on physical machines that has a singular model (namely, the Von Neumann architecture). In this course, we will study the former.

The outcome of any course is always a mix of content and behavior—I want you to leave this course with the behaviors above, which you will acquire by learning the content below. In particular, each bullet below describes a particular point of mastery you should aim to acquire this semester.

Outcomes #1 (Automata and Languages)

Represent a problem using a regular model of computation.
Prove closure and algorithmic properties of the regular languages.
Prove the irregularity of a problem.
Represent a problem using a context-free model of computation.

Outcomes #2 (Computability)

Prove closure and algorithmic properties of Turing machines.
Prove the decidability of a given machine analysis algorithm.
Prove the undecidability of a given problem by way of reduction.
Prove the undecidability of a given problem through Rice’s Theorem.
Describe the practical ramifications of computational undecidability.
~~Describe practical problem solving strategies for dealing with intractable problems.~~

Outcomes #3 (Complexity)

Prove that a problem is in a particular time complexity class.
Prove that a problem is NP-complete by way of a reduction.
Explain the practical ramifications of the P vs. NP problem.
Prove that a problem is in a particular space complexity class.
Describe the essential characteristics of problems belonging to each of the major complexity classes.
Describe the practial relationships between various time and space complexity classes.

Textbook

We will use Michael Sipser’s Introduction to the Theory of Computation (3rd Edition). Alternatively, the second edition of the text will likely suffice for the purposes of this course. Additional reading may possibly be assigned (and distributed) on the course schedule.

Communication & Software

In this course, we will use both Microsoft Teams and email to facilitate communication. The former is the preferred means of communication.

Online submitted documents are preferably typeset in LaTeX. I will also accept suitably legible handwritten work and Microsoft Word. For the former, please make sure to get the work in to me at the lecture date closest to (and before) the assignment’s due date. For the latter, I expect you to format all mathematical typing professionally and legibly using either (i) the Microsoft Word equation editor or (ii) pasting LaTeX images in.

See the Resources page for how to learn and use LaTeX.

Diversity and Inclusion

I believe that any college-level course should challenge you and put you outside of your comfort zone. My mission as an instructor is to help you manage that discomfort so that you can grow in knowledge and maturity. Therefore, I strive to create a fully inclusive setting so that we all can ultimately succeed in the classroom.

Learning Needs

I welcome you to talk to me as early as possible about your distinctive learning needs. I particularly encourage students with disabilities to meet with me and discuss how our classroom and course activities could impact their work and what accommodations would be essential. As part of the accommodations process, I recommend talking to our Coordinator for Student Disability Resources for guidance and further instructions: Jae Hirschman.

If you require accommodations for this course, please email me, message me in Teams, or come in to my office hours so we can discuss them further in private.

Religious Observance Policy

I support the class’s religious diversity and anyone who needs to balance academic work with religious observations. Please let me know by week two if you will need to be absent from class for any religious holidays this semester, and we can work out an appropriate schedule for making up absences or missed work.

Other Accomodations and Absences

There are a limitless number of dimensions to diversity and inclusion, the totality of which are un-addressable with a finite set of policies. These may include other issues best addressed earlier in the semester (e.g., student-athlete scheduling) or as they arise (e.g., chronic health flare-ups). I will do my best to be flexible in these cases with the ultimate goal of facilitating your growth in this course. To do this, I need to receive advanced notice from you at least one week in advance (when possible) so we can make suitable arrangements.

Evaluation

Deliverables

There are several kinds of common deliverables (described below) I use to assess your mastery of the material that are described below in detail. The details of each are provided on the assignments page once appropriate.

Quizzes

We will have somewhere in the range of 10 to 15 small, in-class quizzes. Quizzes are designed to help you identify content that you might have missed or not mastered as well as you think you had. I intend for these to be as low-stakes as possible—I am not trying to examine you; these are just one other form of rapid feedback I can give. To prove to you these are low stakes, your final quiz average (see Final Letter Grades below) will be composed only of your top n quiz scores for some n fairly less than the total quiz count. In other words, we have total quiz count = n + m, with m the number of dropped lowest quiz scores. We will start with m = 3. I reserve the right to increase (but not decrease) m so that more low quiz scores may be dropped as necessary.

Retake Tokens. Quizzes are designed to encourage you to (i) show up to class and (ii) do the reading. If that is you, but you are still struggling on quizzes, it could mean that either:

like me, you over-think timed exams, or
you are struggling (but trying) with the material.

Quizzes are an intended to be positive and not negative reinforcement. To (try to) remedy this for those of you who identify with the above criteria, I am happy to offer quiz retakes in exchange for retake tokens. Retake tokens can be earned by asking valid questions or participating in lecture during Tuesday lectures. You may earn a maximum of 1 per week, and must use that token for either the preceding quiz (the Thursday before) or the following quiz (the Thursday that week).

There will be one mega-token which grants access to retake any quiz, but must be used within a week of its earning. I will distribute tokens after lecture so that I am not throwing coins at you during lecture (tokens will be physically manifested as heavy poker chips).

Labs

Labs are in-class activities or discussions (small group or whole class) that are designed to allow you to gain familiarity and fluency with the course concepts through grappling with the material directly with oversight. Labs will be completed in small groups so that you can take advantage of the benefits of collaborative learning.

Labs are graded on a satisfactory (S) / non-satisfactory (NS) basis. If you have clearly put effort into your lab by considering the question at hand or completing the problems given to you (whether they are correct or not quite so), you can expect to receive a satisfactory grade.

Labs are to be turned in (legibly handwritten or typed) on gradescope. We reserve the right to not grade illegible solutions.

Homeworks

Homeworks are longer assignments that will challenge you to interact, question, and analyze the course material more rigorously. Homeworks will be graded on a point-based scale. While you are free to discuss them with your peers, they should be completed on your own in your own words.

Homeworks are to be turned in (legibly handwritten or typed) on gradescope. We reserve the right to not grade illegible solutions.

Exams

To directly access your mastery of this course’s learning outcomes, we will conduct a series of three exams over the semester covering the three major categories of the theory of computation: formal automata and languages, computability theory, and computational complexity. Each exam will be take-home and is to be completed entirely on your own without discussion amongst peers, professors, Internet access, or any other source. Use of your notes and your textbook, however, is permitted.

Exams are to be turned in (legibly handwritten or typed) on gradescope. We reserve the right to not grade illegible solutions.

Grading Scheme

This course will follow the standard weighted-average grading scale model. The weights of each deliverable are assigned as follows.

Deliverable	Weight	Note
Quizzes	5%
Labs	10%	S/Ns.
Homeworks	25%
Exams	60%	3 exams @ 20% each.

Final Letter Grades

Let n be your final weighted average as determined by the table above. Your final letter grade is determined by the row below with the greatest p such that p ≤ n, rounding decimals in your favor. (Exercise for the class: what is the term for such a p?)

Letter Grade	`p`
A	93%
A-	90%
B+	87%
B	83%
B-	80%
C+	77%
C	73%
C-	70%
D+	60%
F	0%

…But will there be a curve?

I reserve the right to curve final letter grades, but I do not plan on it. In the case that I do, I will only curve in a manner that benefits all students.

Mental Health, or: Why We Often Fall Behind

I encourage you to watch this talk given by Talia Ringer describing how her struggles with depression interfered with her academic life. For some reason, it moved me to hear a (very accomplished!) professor finally state the obvious: mental health is an everyone problem.

If you struggle with your mental health, too, you are not alone! I myself get to enjoy frequent depressive episodes and fairly constant generalized anxiety. I procrastinate, I sometimes hate my work, I sometimes feel like I don’t get any of this stuff. It’s okay.

I refuse to believe that students become disengaged or disinterested for lack of character or grit. More often than not, students develop emotional blocks to course content because it is designed to be difficult and uncomfortable. I understand that these blocks can keep students capable of excelling from doing so. For this reason, I have tried to design late-work, extension, and student absence policies with this empathy in mind.

Late Policy & Extensions

If for some reason you cannot meet a deadline for a lab, homework, or exam, please let me know as soon as you can. I hold a don’t dissappear policy, meaning: as long as we are in communication, we can figure something out. That said, be mindful that late submissions can sometimes (possibly severely) delay when your assignment is graded. Further, access to solutions (if they are posted) will be denied until submission; this can put you in a situation that gets you further behind.

A necessary disclaimer: Please do not abuse this policy, or I will have to require more rigid deadlines. As a gentle precaution, I will institute an Extension Point Penalty past your first extension, resulting in lost points per each additional extension. I reserve the right to choose, at the point of extension, the quantity of points penalized on a case-by-case basis. This penalty is in effect not only to discourage abuse of the extension policy but, more importantly, to encourage you to hand your work in as soon as you can. In most cases, the penalty will be very minimal.

Finally, no homework may be submitted later than the last day of class.

Student Absence

I would really like to have you in class. Labs give you an opportunity to learn with your peers. Further, quizzes are taken (and handed-in) in person. In general, all I ask is that you do your best to make it and, if you cannot, you let me know. In particular, if you miss a quiz, we will need to schedule a time for you to take it.

A necessary disclaimer: Please do not abuse this policy. In particular, I and the course staff, by nature of our frail human mortality, are limited and fragile beings. We can only help you catch up so much. As a gentle precaution, I will institute a Missed Quiz Restriction: you may only make-up so many quizzes as are dropped from your final grade (see Quizzes above). This is to say, if I drop your worst m quizzes, you are permitted to miss (and take later) this many. This policy is not extremely rigid; again, I am simply trying to give you an extra nudge to attend class.

Instructor Absence

I live in Cedar Rapids, Iowa, and so I must drive a car to campus. Unfortunately, Iowa has snow, cars break down, and instructors get runny noses. If any of these cases is to occur and I am not able to be on campus, we will hold our class period virtually on Teams. In such an event, I will message you as soon as I can with clear instructions on how to attend class virtually.

Help, Collaboration, and Academic Honesty

Instructor and Course Mentors

When asking questions about the course or course material, please use the Microsoft Teams site (a work in progress) or a direct message (DM) as a first stop. We will respond to emails as well; however, Teams is the preferred method of contact.

I will try to make sure it is clear to which channel you should post a question. I highly encourage active discussion among classmates for (most of) your assigned work. Learning to communicate technical material effectively and clearly with your peers will some day be your job! That being said, please reach out to me or the course mentor directly for questions that might reveal too much about a given assigned problem. Also, feel free to reach out to me on Teams (or email) if you have questions about computer science, research, academia, life, et cetera that exceed the scope of this course.

On timely replies

I and the class mentor will try to get back to all questions in a timely fashion. That being said, we are also humans who must eat, run errands, sleep, and play video games. Further, if we answer your question in depth, we expect you to expend as much intellectual depth in exploring the answer. So, this is to say: we will do everything we can to help you succeed, but we are not a paid support channel, and we reserve the right to miss a question or turn off Teams for a(n) hour/day/weekend with less chatter. This is to preserve my mental health and the mental health of the class mentor.

Peer Collaboration

Peer collaboration is an essential skill not just in scientific pursuits but in all careers and indeed in all aspects of life. However, this must be balanced in education with one’s own intellectual growth. While I actively encourage you to discuss both assignments and the course material with fellow students (or anyone else), all material presented as your own work must in fact be your own work. For example, if you work through a homework problem together with a classmate, you both should write the solution up individually in your own words and cite all resources you used in authoring your work. As a rule of thumb, you should be capable of reproducing your own work on the spot with minimal effort. Your goal should be to incorporate the course material into your greater body of knowledge rather than pursuit of a grade and degree.

Keep in mind that adaptation of pre-existing code or solutions, whether it comes from a peer, myself, or the Internet, requires a citation in cases where it is allowed.

If you feel that the stress and pressure of the course are compelling you to violate the academic honesty policies of the course and the college as explained in the student handbook, please talk to me as soon as possible. The course’s grading policies are designed to help you manage your time in light of the different stressors in your life. I will do my best to work with you to figure out how to help you better manage your time relative to your learning goals and desired achievement level for the course.

Course Materials

Our goal is to create an inclusive learning environment where people feel free to share, fail, and ultimately grow in knowledge. To create such an environment, we must be mindful of what we share outside of our learning space. To this end, I request that you refrain from sharing any recordings of our class meetings with others outside of the class. Recordings of class meetings that we provide, e.g., recorded through Microsoft Teams, are meant for your personal use and should not be shared outside of the class. By “recordings,” we mean video and audio capture, include static screenshots.

Furthermore, while you retain copyright of the work you produce in this course, we must still uphold the academic integrity of this course. To this end, you may not share copies of your assignments with others (unless otherwise allowed by the course policies) or upload your assignments to third-party websites unless substantial changes are made to the assignment (for example, significant extensions and improvements to your code). Ultimately, it must be clear that the end product is significantly different from what was asked in the original assignment.