(*Last updated: September 26, 2021*)

(*Note that due to the rapidly changing world that we find ourselves in, this syllabus’s policies are perpetually subject to change.* *All changes to course policies will be reflected in this document and announced in advance in class.*)

**Table of Contents **

# Overview

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?

**Course Topics**

- Mathematical literacy
- Reading and studying mathematical prose
- Writing formal mathematical arguments

- Regular Languages
- Machine- and linguistic-based models
- Nondeterminism
- Equivalence of models
- Closure operations, properties, and decision procedures
- Irregularity (the pumping lemma, Myhill-Nerode theorem)

- Context-free Languages
- Models and properties

- Decidable Languages
- Turing machines: low-level and high-level operations
- Properties and variants

- Complexity Theory
- P vs. NP
- Cook’s theorem, NP-completeness, and reductions
- Space complexity and Savitch’s theorem

- Decidability Theory
- Decision procedures for Turing machines
- Undecidability and reductions
- The post-correspondence problem
- Rice’s theorem
- The recursion theorem
- Logical theories

- Special Topics in the Theory of Computation

# Textbook, Software, and Connectivity

We will use the following required textbook for the course:

• Introduction to the Theory of Computation, Michael Sipser.

The most recent edition of the book is the third edition. The second edition is also fine for this course if you would like to be frugal. In addition, we also distribute additional course notes electronically via the course schedule. The course webpage page contains suggestions for supplementary texts.

In this course, we will use the following software packages and services:

- Microsoft Teams: class communication and synchronous meetings.
- Gradescope: deliverable submission and feedback reporting.

You will receive an invite to the relevant Microsoft Teams and Gradescope sites. Please let me know if you have not received access to these sites. You should sign up for a free Overleaf account using your email (either your college or personal email). The course webpage also contains additional software resources, *e.g.*, LaTeX tutorials and other utilities, you might find useful in this course.

For document creation, we will use the Markdown format coupled with common extensions that add LaTeX-style syntax for the purposes of embedding mathematics. There are a variety of offline and online tools for authoring and previewing Markdown files. What tools you use are up to you, although we require that your tool allows you to export your Markdown file (with mathematics) to a rendered PDF for submission to Gradescope. Recommendations by platform can be found on the course website.

If you are familiar with LaTeX already or wish to learn it, you may use LaTeX instead. However, please be aware that LaTeX can obscure learning with its baroque syntax and user-unfriendly tools. If you use LaTeX this semester, it is your responsibility to ensure that you are not bogged down with its particulars!

**Internet Connectivity**

In addition to software, you will also need a stable Internet connection capable of streaming audio and video. While we plan to conduct learning in-person, the pandemic may require us to switch to various forms of virtual learning where such technology is necessary. If your Internet connection does not meet these requirements, please contact me as soon as possible so we can work with Grinnell’s Information Technology Services (ITS) group to get you an adequate connection.

# 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, Goodnow Hall, 3rd floor (x3089)

## Religious Observance Policy

I also 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 Accommodations

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** so we can make suitable arrangements. For situations that arise within a given week, I will ask you to utilize the token system (described below) to manage your workload.

# Pandemic Policies

In recognition of the on-going global pandemic, the course, while in-person, will be conducted somewhat differently from a standard offering with an emphasis on increased flexibility while trying to maintain the high-level of individualized instruction, guidance, and rigor of a standard Grinnell College course.

**Regardless of any these stated policies, if any issues surrounding comfort, mental or physical health, or other factors arise, please do not hesitate to contact me so that we can discuss how we can accommodate your learning this semester.**

## Classroom Policies

The College has established strong policies surrounding conduct indoors. We will adhere to these evolving policies in our classroom over the course of the semester. Consequently, please feel free throughout the class period to get up, stretch, or take a breather outside as needed. Also, note that irrespective of the College’s current policies, you are free to wear a mask or face shield in the classroom as your comfort level dictates.

In order to optimize our learning time together, classes will consist primarily of collaborative activities, *e.g.*, discussion and group work, similar to a standard semester. Please start your time with your group by establishing how you will physically work with each other during the period. Be aware that someone’s comfort level with physical interaction may be different from yours, and you may need to compromise in order to effectively work together. Ultimately, I ask you to exercise continual patience and grace with your peers throughout the semester.

## Extended Absences

In the event that you need to take an extended absence from in-person learning, *i.e.*, longer than 3 days, I am happy to work with you individually to develop accommodations that will help you succeed and thrive. The only thing I need you to do is to **let me know as soon as possible when such a situation will arise or has arisen**. I cannot take action to give you assistance if I do not know what is going on, and due to the busyness of the semester, I may notice your absence too late to provide meaningful help.

Because of the finite time we have together this semester, some situations may arise where a reasonable accommodation may not be possible. I will also work individually with you on evaluating options for managing your workload and assisting you in deciding whether continuing with the course is feasible.

Note that while I welcome you to disclose whatever information you feel would be helpful for me to give you appropriate accommodations, you do not need to share any specific medical information with me that you are uncomfortable sharing. I only need to know as early as possible, ideally in advance, of an extended absence, to be able to work with you.

## Instructor Absences

In the case that I (the instructor) must take an extended absence from in-person learning, we will modify our course format depending on my ability to continue leading the class. Likely possibilities include:

- “In-person” class with a virtual instructor. The class will continue normally in-person with daily group activities, but I will conduct discussion with the class virtually via Teams broadcasted to the classroom.
- Full synchronous virtual instruction where we meet at our designated time, but on Teams.

In the case where I am unable to continue operating the course, I will work with the department to determine an appropriate path forward, *e.g.*, a change of instructors.

# Evaluation

This course employs a grading system based on *mastery grading* and *specifications grading* to evaluate your work. These systems, inspired by adult learning theory, are designed to create a “low-threat” learning environment where:

- Mastery is obtained via exploration, experimentation, and failure.
- Eventual mastery is valued as highly as “getting it right” the first time.
- Your final grade accurately reflects your mastery of the stated learning goals of the course.
- The expectations for grades are both easy to understand and easily trackable.

## Deliverables

There are several kinds of common deliverables I use to assess your mastery of the material that are described below in detail. Note that some of these deliverables may not appear in our class. Descriptions of course-specific deliverables also appear in our course-specific syllabus.

**Lab exercises**: practice problems worked on during class, frequently in a collaborative fashion.**Demonstration exercises (demos)**: individually completed homework assignments that apply the weekly concepts to problems of significant complexity.**Learning assessment (LAs)s**: individually completed problems that directly assess your mastery of the course’s learning goals.**Explorations**: individual meetings with me where you present selected portions of your demonstration exercises and we collaborative dive deeper into the material.

### Lab Exercises

The bulk of your practice and exploration of the course learning goals comes through *lab exercises*. Lab exercises will allow you to gain familiarity and eventual fluency with the course concepts by exploring and working through problems. More often than not, lab exercises will be completed in small groups so that you can take advantage of the benefits of collaborative learning.

Lab exercises are graded on a binary **satisfactory (S)/non-satisfactory (N)** scale. If it is clear that you have put effort into these deliverables by completing most of the problems with positive results, you can expect to receive a satisfactory grade. However, be aware that the bulk of actionable feedback we give to you will be on labs, so don’t neglect to look at our comments!

**Lab Deadlines and Feedback**

Labs are meant to serve as *practice* for eventual demonstration of mastery through other course deliverables. Thus, there are strict deadlines for completing labs so that we can give you feedback. We recommend turning all labs for the week **on the Saturday of that week**. When relevant, we will send solutions for lab problems (when relevant) to everyone who turned in labs at this time.

Ultimately, labs for the week are due **two Saturdays from the week they are assigned**, *i.e.*, one week after the recommended turn-in date. If you turn in a lab during this time, you may contact me to receive solutions (when relevant) to check your work. Please note that this final deadline for weekly labs is *firm*; you will not be able to turn in a lab past its final due date.

### Demonstration Exercises

*Demonstration exercises* are opportunities for you to demonstrate mastery of the course learning goals by applying these concepts and skills to problems larger in scope and complexity than the labs. As often as possible, demonstrations are drawn from “real-world” domains to also help you begin drawing connections between the course and other areas of computer sciences.

We grade demos in more depth than the other deliverables, specifically along two dimensions:

- Is the deliverable
*correct*? Does it accurately solve the posed problem? Does it meet the specification outlined in the problem description? - Is the deliverable
*well-designed*? Does it follow the design requirements and conventions appropriate to the medium? Is the deliverable clear, and does it communicate a proper understanding of both the problem and its solution?

Rather than using a point-based system that obscures these two dimensions, we codify these requirements with the *EMRN rubric* (an adaption of the “EMRF” rubric designed by Stutzman and Race). Demos are graded on a four-point scale:

**Excellent (E)**- Complete understanding of the material is evident.
- Exhibits no errors and can serve as an exemplar solution for the course.

**Meets Expectations (M)**- Complete understanding of the material is evident without the need for further revision.
- Exhibits some minor errors that warrant revision but are covered by comments.

**Needs Revision (R)**- Limited understanding of the material is evident.
- Exhibits many minor errors or one or more major errors that necessitate revision.

**Not Completed (N)**- Not completed to a degree where understanding is evident.

Note that excellent ratings represent work that reflects mastery of the material and mindfulness towards producing quality work. To obtain excellent ratings, you should dedicate ample time to review and revise your work—just like writing a paper—before the deadline.

Each demo has a rubric in its write-up that outlines what we will be looking for regarding correctness and design. In general, correctness errors tend to be major, whereas design errors tend to be minor. However, this is dependent on the actual error involved. For example, missing an insubstantial corner case could be construed as a minor correctness error, while having egregious formatting issues with your code could be considered a major design error.

**Demo Revisions and Feedback**

To promote learning and encourage you to produce quality work, we use a revision system for demonstration exercises. If you earn an **E** on a demo, you do not need to perform further revision! Otherwise, you are free to turn in a revision based on your prior submission’s feedback. Note that revisions are graded as entirely new submissions, so it is essential to check that your revised work fixes all outstanding issues raised in the feedback.

When submitting a revision, please include a short *changelog* at the beginning of your submission summarizing the changes you have made. Such a changelog will help us process your revision more quickly.

If you earn a **M** or **R** on a demo, the feedback you will be reflective of what you need to change to achieve an **E**. Conversely, if you earn a **N**, your submission was not complete enough to give you substantial feedback. If you earn an **N** on a demo, you **must meet with me either in office hours or through a 1-on-1 meeting** in advance of turning in your revision, so that we can resolve any misconceptions that you have.

**Recommended Deadlines and Grading Limits**

To allow you to produce your best work as well as manage your other obligations this semester, there are *no strict deadlines* for turning in demonstration exercises or revisions beyond the final deadline for all work at the end of the semester. However, be aware that in order to keep up with the course, you should aim to complete demos *one week* after they are assigned. Revisions should also be completed the week that you receive back feedback.

To manage our own workload, we will grade **at most three demonstration exercises and revisions** each week. You should upload your work to Gradescope and indicate on the appropriate Gradescope entry which demos we should grade. Be aware that this grading limit is firm, so if you fall too far behind in weekly turn-ins, you be unable to complete enough demos at a satisfactory level to pass the course. If you fall behind in submitting demonstration exercises throughout the semester, I will contact you to formulate a plan for catching up or to consider other options.

### Learning Assessments

To directly assess your mastery of this course’s learning goals, we will conduct a series of learning assessments (LAs) over the semester. This course’s LAs are inspired by mastery-based testing practices found in mathematics. See the course schedule for the specific dates that LAs are conducted.

LAs consist of one problem for each learning goal of the course covered so far at the time of the LA. The learning goals organized by LA period are listed below. At the start of a learning assessment period, the problems are released online on Gradescope. You then have 24 hours to complete problems from the LA. You may choose to attempt as many of the LA problems as you wish for that period.

LA problems are graded on a **binary satisfactory (S)/non-satisfactory (N)** scale where a satisfactory answer is *completely correct*. Note that, unlikely the demonstration exercises, LA problems more closely resemble lab problems in terms of their scope and complexity. Once you receive an **S** on a problem tied to a particular learning goal, you do not need to attempt additional problems connected to that learning goal in subsequent LAs, *i.e.*, you have demonstrated mastery of that goal, so you are done with it!

**Learning Assessment 1**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.

Represent a problem using a Turing machine.

Prove closure and algorithmic properties of Turing machines.

**Learning Assessment 2**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 charactistics of problems belonging to each of the major complexity classes.

Describe the practical relationships between various time and space complexity classes.

**Learning Assessment 3**Prove the decidability of a given machine analysis algorithm.

Prove the undecidability of a given problem by way of a 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.

Design and reason about an approximation algorithm to an optimization problem.

The final LA period of the course, held during finals week, is a *revision learning assessment*. No new learning goals are introduced, so that you have a final opportunity to demonstrate mastery.

### Explorations

To assess your ability to communicate the technical content of the course as well as your ability to work through complex problems, I will meet with you periodically throughout the semester for short interview-style meetings. You should schedule these exploration meetings with me during designated periods throughout the semester. In these meetings, you will work through one or more *explorations*, each of which consist of two parts:

- Present your work from a previous demonstration exercise and
- Work on new problems related to the demonstration exercise with my guidance.

Explorations are graded on a **satisfactory (S)/non-satisfactory (N)** scale along two dimensions:

- Did you present your solutions to the demonstration exercise in a technically accurate and understandable fashion?
- Did you demonstrate the capability to apply the techniques of the course to solve novel problems?

Note that I am not interested in assessing whether you can *complete* a problem given the limited time constraints of the meeting. I am looking for evidence that you can apply a course concept to a novel setting, *i.e.*, you have sufficiently generalized your knowledge, and whether you can reasonably push through technical challenges

## Final Deadline for All Work

Note that *all* work must be submitted by Friday, December 17, 11:59 PM CDT . This is College policy and cannot be waived for any reason. If you find yourself needing to turn in work past this deadline, you must consult with me as soon as possible to submit an *incomplete request* for the course. Note that incomplete requests are not automatically granted; make sure you have a backup plan in case your incomplete request is denied.

## Overall Letter Grades

Major letter grades for the course are determined by *bundles*, a collection of required grades for each of the deliverable categories. You will receive the grade corresponding to the bundle for which you meet *all* of the requirements. All bundles list *minimum amounts*; you may exceed the bundle requirements and still qualify for it.

Note that I reserve the right to update the requirements for grades as circumstances dictate during the semester, *e.g.*, if a deliverable is cut. However, I will always update the requirements so that they are **no stricter** than they were previously.

**Plus/minus grades**

To earn a plus/minus grade, you must have completed one tier’s requirements and meet the next tier’s requirements for *at least* one of the demos, LAs, and explorations. This will arise in two situations: **C/B** and **B/A**. For example, you may completely meet the requirements of a **C** and meet the requirements of a **B** for demos, but not the LAs or explorations.

- If you fulfill at least 2 of the requirements for the higher tier between LAs, demos, and explorations, you earn a minus grade for the higher tier,
*i.e.*,**B-**if you are between a C and a B. - Otherwise, you fulfill exactly 1 of the requirements for the higher tier between the three deliverable categories. You then earn a plus grade for the lower tier,
*i.e.*,**C+**if you are between a C and a B.

Major Grade | Labs (35) | Demos (9) | LAs (18) | Explorations (4) |
---|---|---|---|---|

C | 26xS | 1xR+, 6xM+, 2xE | 12xS | 1xS |

B | 29xS | 4xM+, 5xE | 14xS | 2xS |

A | 32xS | 2xM+, 7xE | 16xS | 3xS |

**D**: 2–3 requirements of a C are met.**F**: 0–1 requirements of a C are met.

# Help, Collaboration, and Academic Honesty

To help expedite your learning, you can rely on the course staff and your peers as outlets in this course.

**The Instructor and Course Staff**

When asking questions about the course, please use the **Q&A** channel on our Microsoft Teams site as a first stop, so that your peers can benefit from your insight. Feel free to ask questions of these sort in the channel:

- General logistics questions,
*e.g.*, questions about how grading works. - Any general questions about course content not related to deliverables.
- Any questions about lab exercises.
- Any general questions about demonstration exercises.

We will prioritize answering questions in the **Q&A** channel first.

Please use direct messages (DM) on Microsoft Teams to contact the course staff directly about individual issues concerns logistics, grades, or demonstration exercises. Note that even though may be marked online we will generally not respond immediately—we will check and respond to our messages at fixed times throughout the day.

While seemingly convenient, I highly discourage you from using email to contact me directly as I receive large volumes of email each day. There is a strong likelihood that your mail will be buried and missed. Please favor Teams as much as possible this semester.

The course mentors also holds optional *mentor sessions* outside of regular class time. In these sessions, the mentors guide you through practice problems designed to help you master the material and answer any questions about the material. I highly recommend you attend each of these sessions, even if you feel like you understand the material. You never know what you don’t know, and the purpose of these sessions is to bring these blind spots to light!

If you would like to discuss things in more detail—course content, more general questions about computer science, or other things—feel free to meet me during my regular office hours or schedule a meeting with me via Calendly:

I am open to either virtual or in-person meetings as my schedule permits, but be aware that due to high volume, I ask that you restrict 1-on-1 meetings with me to **one meeting per week** scheduled **no earlier than 2 weeks in advance**. In particular, any sort of recurring meeting must be approved by me in advance so that everyone has a chance to meet if needed.

**Peer Learning**

Utilizing discussion with peers to facilitate your learning is a critical skill for success in computer science. However, at the same time, you must be aware that getting stuck and pushing through challenging problems is essential for robust learning. To this end, we allow the following forms of collaboration.

- You are encouraged to collaborate with your peers on labs. You may also consult the course staff as well as other people and external resources. In all cases, you (or your group in the case of group work) should independently write up your solutions and cite all the resources you used in authoring your work.
- You may only discuss demonstration exercises, learning assessments, and explorations with the course staff. When completing these, you may only consult the
**course website**when developing your solutions. You may not collaborate with peers, consult external resources beyond the ones mentioned above, or share information about these assignments with others.

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.

In all cases, the work that you produce should be your own. The golden rule is that you should be capable of reproducing your deliverable on the spot with minimal effort if it was accidentally deleted.

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.

**Sharing of 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 (*e.g.*, 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. I do recognize that there are times where you want to do this, *e.g.*, uploading projects to Github for your resume, and so I encourage you to talk to me in advance so that we can ensure that you upload a meaningful project that does not run afoul of this policy.