Last updated: September 9, 2025

General Information

Shawn Ong, Assistant Professor of Computer Science
Preferred name: Professor Ong (he/him)
Email: ongshawn@grinnell.edu
Office: Noyce 3811

We will be using Piazza for our course discussion board — please feel free to post questions regarding course content or logistics here. For other questions or concerns which either do not require an office hours appointment or for which you do not feel comfortable discussing at office hours (e.g., something of a more personal nature, illness, or emergency), feel free to contact me by email. Please allow up to 24 working-hours for a response to email (this means that if you email me on Friday, I may not get back to you until Monday). I encourage you to also find balance between your schoolwork and other areas of your life.

Some background: I'm a recent graduate in applied math from Cornell University, with my primary field of research in theory of computation (hey, that's the name of the course). As I'm new to Grinnell and slightly more face-blind than average, I'd like to meet briefly (5-10 mins) with each of you at the start of the semester, to help me start putting names to faces, as well as to discuss anything you think I should know (this can include topics such as accommodations, planned absences, or any concerns you may have regarding the course). Please sign up for a time slot on Calendly; if none of the available times work for you, please email me to set up time to chat.

Logistics

Class meets Tuesdays and Thursdays in Noyce 3819.

Office hour times are tentatively set for:

I may adjust these times at some point in the semester to meet specific demand. Office hours are drop-in and therefore communal, but if you have something that you want to discuss one-on-one or you cannot make the scheduled times, please send me a quick email with some times that do work for you so we can find a time to meet. If my door is closed, please assume that I am in either an in-person or online meeting — but if we do have something scheduled, feel free to knock!

Textbook

We will use Michael Sipser's Introduction to the Theory of Computation (3rd edition). Note that you will have access to this textbook through GrinnBooks, unless you opt out. If you are looking to independently procure a copy, the second edition of the text will probably suffice, but may be missing things or have different page numbers. I will distribute additional reading and material as needed.

Communication and Software

We will primarily use Piazza for announcements in this class, and I expect that you check regularly (i.e., at least once before every class) for information. Piazza will also be used for discussions and clarification questions; questions you post may be answered by both course staff and students. Readings, problem sets, and labs will be submitted on Gradescope. You will be able to see your graded work (and comments) on Gradescope. Grades will also be secondarily posted to Canvas so that you can get a sense of your overall standing in the course — please do not submit any work to Canvas, as I will not see it. Canvas is also where any additional course materials will be posted. All of the important course information can be found on the course website here.

Mentors

This course employs the use of a mentor to aid you in navigating the course. Our course mentors will host 1 or 2 mentor sessions throughout each week. Mentor Sessions may review course content, provide practice problems, or provide help with problem sets or labs. While each section will have one assigned mentor in lecture, you are free to attend Mentor Sessions run by either mentor (or both!).

Mentors: Alma Ordaz (Section -01) and Devanshu Pandey (Section -02)
Mentor Session Times: Sundays 7-8pm in Noyce 3819, Wednesdays 7-8pm in Noyce 3821

Course Overview, Topics, and Learning Outcomes

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

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

Course Learning Outcomes

  1. Represent a problem using regular models of computation.
  2. Prove closure and algorithmic properties of the regular languages.
  3. Prove the irregularity of a problem.
  4. Represent a problem using context-free models of computation.
  5. Represent a problem using a Turing machine.
  6. Prove closure and algorithmic properties of Turing machines.
  7. Prove the decidability of a given machine analysis algorithm.
  8. Prove the undecidability of a given problem by way of a reduction.
  9. Prove the undecidability of a given problem through Rice's Theorem.
  10. Describe the practical ramifications of computational undecidability.
  11. Describe the practical ramifications of the Church-Turing thesis.
  12. Prove that a problem is in a particular time complexity class.
  13. Prove that a problem is NP-hard by way of polynomial-time reduction.
  14. Explain the practical ramifications of the P vs. NP problem.
  15. Prove that a problem is in a particular space complexity class.
  16. Describe the essential characteristics of problems belonging to each of the major complexity classes.
  17. Describe the relationships between various time and space complexity classes.
  18. Describe problem-solving strategies for dealing with intractable problems.

Class Components

There will be 5 components to your grade in this class:

Your attendance and participation in class is an integral part of your learning, thus it is a requirement. Since much of the course is collaborative, your absence will detract from not only your own learning but also that of your peers. Class will start promptly at the start time each day, so you should be sure to arrive before class starts. I will hold my end of the social contract by making sure we end class on time every day.

On each day of class, you will be marked as present and engaged (or not). To be marked positively you will minimally need to:

When you miss a class day (excused or unexcused) you are still responsible for the material covered in class. You should review readings, labs, and notes from class and consult with peers who were in class the day you missed to catch up.

If you miss a significant number of class days (including via excused absences) it may be difficult for you to meet the expectations of the course. Additionally, if you miss more than one class period in a row without notice to me, you should expect to hear from me as well as student advising (via SAL). The goal here is not to scold you, but to make sure you're aware of the situation and have the information you need to stay on track or withdraw from the course if completing it successfully is no longer feasible.

Unexcused absences: An excessive number of unexcused absences (including being marked as late or not participating) will impact your grade in the following manner. If you are unexcused for more than 2 days, you may not receive a grade higher than a B+ in our class. Similarly, if you are unexcused for more than 4 days you may not receive higher than a C+ in our class. Finally, if you are unexcused for more than 6 days, you may not receive a grade higher than a D.

Excused absences: You may be excused for a class under certain situations. I encourage students who plan to observe holy days that coincide with class meetings or assignment due dates to consult with me in the first three weeks of classes so that we may reach a mutual understanding of how you can meet the terms of your religious observance and also the requirements for this course. Likewise, please discuss with me in the first three weeks of the semester if you will be absent due to athletic events or other activities as a representative of Grinnell College. Again, excused absences absolve you of the responsibility of attending a specific class, but not of learning the material which was covered.

You may also be excused from class in the event of an emergency or illness. I will not require proof or details, just please let me know as soon as you are able. If you attend class with respiratory symptoms, please consider wearing an N-95 mask to protect others.

Readings

Accompanying most class days there will be a required reading that you are to complete before class starts. Readings may be accompanied by either a written or discussion component. After reading, find corresponding questions on the schedule, and, following the accompanying directions, either answer those questions and submit your answers to Gradescope, or read over them and prepare for a short in-class discussion. These are meant to be an accountability device; namely, motivation to complete the reading before class. My hope is that the questions will help you to pinpoint the important information or help you identify concepts that are unclear.

Readings will be graded on a scale of full credit, or no credit. Answers will receive full credit if they are either correct, or incorrect while showing evidence of significant effort. Incomplete answers or work that is incorrect with little evidence of effort will earn zero.

There will be no revisions on Readings.

There is no 48-hour grace period for Readings.

Labs

Most class days will consist of a Lab component. Lab exercises give you a chance to engage with our class material in a low-stakes way, with the benefit of collaboration from your peers. Labs will typically be due the Sunday after they are distributed, to give you time to finish any activities you did not complete during class. You will turn in each Lab as a group, and they will be graded on a scale of full credit, half credit, or no credit. Work that is correct or nearly correct with evidence of significant effort will earn full credit. Incomplete submissions or work that is incorrect with little evidence of further effort will earn half credit. Missing work or work that shows very little effort will earn a zero.

There will be no revisions for Lab exercises.

Problem Sets

Problem Sets 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. They will be assigned most weeks, with at least one week to work on each. Submissions that receive full credit will minimally meet the following criteria:

  1. The Problem Set must be complete, by providing answers to all questions, and/or following all instructions.
  2. Submission is neat. If hand-written it is legible, and if typed it is formatted appropriately using LaTeX or word equations.
  3. Answers are correct or nearly correct, showing full understanding of course material.
You will have the opportunity to revise Problems Sets using our token system.

Exams

We will have three exams this semester. The dates are as follows:

Exams will be on paper in class, however you will be allowed to use a limited set of notes. More details will be given as the exam approaches. You may be allowed to revise one problem from each of the first two exams using our token system.

Revision Tokens

Tokens are meant to give you the opportunity to revisit work from our course that challenged you the first time around. I hope this system will remove some of the pressure of "performance" in our course, since you may resubmit some things without penalty.

You may earn tokens by supporting your peers and being an active member of the Grinnell computer science community. Upcoming eligible opportunities will be listed at the start of each class. You will be limited to a maximum of 6 total tokens: up to 3 from supporting your peers and up to 3 for attending academic events. (See Token FAQ)

Revise Problem Set: You may use one token to resubmit a Problem Set. You may not resubmit a problem set which you did not turn in. This system is meant to encourage you to take a second look at concepts that you may have struggled with initially, not as a way to turn in things late. Problem Sets must show a good faith effort initially in order to be revised. The same collaboration policies apply as in the original submission.

Revise Exam Problem: You may use one token to revise one exam problem. After each of the first two exams, I will announce which of the problems are eligible for revision, and you may choose to revise up to one of them. You are not allowed to obtain help from any person or resource other than me (Professor Ong), the textbook, your notes, and our course webpage.

A note on feedback: I urge you to read all feedback given through Gradescope, especially on labs and problem sets. Feedback on these assessments is essential for you to understand how to improve, and sometimes you may receive full credit even though you would not on an exam. In Gradescope, viewing feedback means clicking through a few buttons beyond your grade.

A note on instructor/grader workload: In order for your instructor to maintain sanity this semester, no more than three of your problem sets or revisions (problem sets or exams) may submitted in a single week. This will help to keep the grading load reasonable. While revised work is not officially due until the last day of finals, this means you cannot submit more than 2 revisions in a single week.

Letter Grades

The graded components for this course will contribute to your total grade in the following proportions:
Component Percentage of Final Grade
Readings 5%
Labs 20%
Problem Sets 30%
Exams 45%
Attendance and Participation Only as a penalty

Your letter grade will be determined with the usual scale (lower bounds are inclusive, so you would receive an A- if you achieve an overall percentage of exactly 90%):
Letter Grade Percentage Range
A 93 – 100%
A- 90 – 93%
B+ 87 – 90%
B 83 – 87%
B- 80 – 83%
C+ 77 – 80%
C 70 – 77%
D 60 – 70%
F 0 – 60%
I reserve the right to curve final letter grades, but I do not plan on doing so. In the case that I do, any changes will be a net positive to your grade, i.e., I will only lower the percentage boundaries. This means that if your final point total was an 85%, you will not be curved below a B (but may be curved up to a B+).

Course and College Policies

Late Work

All assignments (readings, labs, and problem sets) are to be turned in electronically on the day they are due. I am aware that there are a number of things outside of your control that may affect your ability to complete work on time, so any Lab or Problem Set may be submitted up to 48 hours late without prior approval and without penalty. I do, however, appreciate knowing in advance if you plan to turn in work late.

If you believe you will need an extension of more than 48 hours, please talk with me as soon as possible. Assignments turned in more than two days late, without prior approval (before the original due date) of the instructor, will not be accepted. Please refer to the Student Workload statement below, to emphasize that you should attempt to follow the posted deadlines. Please keep in mind that if you turn in work late, I may not be able to grade it as quickly as you or I hope.

Readings will not be accepted late. If you have a planned absence, you should arrange to complete the reading ahead of time. If you have an un-planned excused absence, please communicate with me about getting the accompanying reading excused if needed.

Incomplete Grades

All work for the course must be submitted by 5:00 pm on the last day of finals (December 19, 2025). In exceptional circumstances, incomplete grades can be granted. Talk with me if you think you might need an incomplete to complete all the requirements of the course.

Student Workload

You can expect to spend an average of 12 hours per week on this course, including all in-class and out of class time. This number is based off the Grinnell Guidelines for credit-hours. Since our class meets for approximately 3 hours each week, you can expect to work 9 additional hours outside of class time. This includes: reading and interrogating the textbook, attending mentor sessions and office hours, working on problem sets, and general studying.

Academic Honesty

Grinnell College's Academic Honesty policy is located in the online Student Handbook. It is the College's expectation that students be aware of and meet the expectations expressed in this policy. In addition, in this course, it is my expectation that students may collaborate on the Problem Sets and Labs, however your collaboration must be attributed on Problem Sets. Moreover, Problem Set submissions must be written individually and independently — you should be able to explain every part of your submission. A good rule of thumb is that you should be able to recreate your deliverable on the spot with minimal effort if it was accidentally deleted. Labs should be submitted in groups, but it is fine to also work with students outside your group.

In this course, you are not allowed to use solutions you find on the internet, and further, you are not allowed to search for information about problems using any resources outside of the course materials. This includes any AI assistive tools such as ChatGPT. I know that there is great temptation to look for solutions online when things get difficult. I will provide you with numerous resources to get help which include office hours, group class work, mentor sessions, and revisions. It is my hope that allowing you to resubmit problem sets without penalty eases some of the pressure that you might feel regarding grades.

If you have questions about how a particular assignment relates to the College's policy, or how to attribute your collaboration, I will gladly consult with you in advance of the assignment's due date. Asking about course policies is never an academic honesty violation, but violating academic honesty policies is a serious issue whether you do so knowingly or unknowingly.

Artificial Intelligence Policy

AI assistance tools like ChatGPT may not be used in this course. In particular, you may not use them to help produce any work which will be submitted in this class — submitted work that includes text produced by an AI tool will receive an automatic zero. These tools can do a very good job of imitating the work of students. Often, they can even produce correct code and proofs. However, the current state of these models is that they are (1) not very good at math and (2) susceptible to very subtle errors that are difficult to spot without sufficient domain knowledge. As such, use of these tools is more likely to interfere with your learning than to support it. Submitting AI tool output without citation is a violation of the academic honesty policy and will be handled through the College's formal academic honesty process.

Title IX and Pregnancy Related Conditions

Grinnell College is committed to compliance with Title IX and to supporting the academic success of pregnant and parenting students and students with pregnancy related conditions. If you are a pregnant student, have pregnancy related conditions, or are a parenting student who wishes to request reasonable related supportive measures from the College under Title IX, please email the Title IX Coordinator at titleix@grinnell.edu. The Title IX Coordinator will work with Disability Resources and your professors to provide reasonable supportive measures in support of your education while pregnant or as a parent under Title IX.

Students with Disabilities

I encourage students with documented disabilities, including invisible disabilities such as chronic illness, learning disabilities, and psychiatric disabilities, to discuss appropriate accommodations with me. You will also need to have a conversation about and provide documentation of your disability to the Office of Accessibility and Disability Resources, located on the first floor of Steiner Hall, by email at access@grinnell.edu, or by phone at (641)-269-3124.

Technology Usage Policy

Materials you have obtained from this course including problem sets and exams should not be distributed outside of the members of our class. Live synchronous sessions should not be recorded by students. You may not use your cell phone during class, and it should be silenced and put away during class time. Laptops and tablets are allowed for note-taking, however you should personally assess if these devices are a distraction to your learning.

Inclusion Statement

It is my intention that students from all backgrounds and perspectives will be well served by this course, and that the diversity that students bring to this class will be viewed as an asset. I welcome individuals of all ages, backgrounds, beliefs, ethnicities, genders, gender identities, gender expressions, national origins, religious affiliations, sexual orientations, socioeconomic background, family education level, ability, and other visible and nonvisible differences. All members of this class are expected to contribute to a respectful, welcoming, and inclusive environment for every other member of the class. Math (yes, this is really a math course in disguise) can be very difficult to learn if you are hesitant and not comfortable making mistakes. Rather than avoiding mistakes, I find it much more productive to instead develop the skill to recognize mistakes, and how to correct them. I will do my best to create an inclusive learning environment where you feel confident to push your boundaries, and I hope that you will take advantage of this to maximize your growth. Your suggestions are encouraged and appreciated.

Academic Support

If you have other needs not addressed above, please let me know soon so that we can work together to establish the best possible learning environment. In some cases, I wll recommend consulting with the Academic Success Center (ASC). They are an excellent resource for developing strategies for academic success and can connect you with other campus resources as well. If I notice that you are encountering difficulty and I have reached out to you and not received a response, or if you have missed multiple class sessions or are not meeting our course objectives repeatedly, I will submit an academic alert via the Academic Success Center's SAL portal. This alert notifies you of my concern, as well as alerting your advisor(s) and the ASC staff, so that they can reach out to you with additional offers of support.

Take Care of Yourself

Do your best to maintain a healthy lifestyle this term by eating well, exercising, avoiding drugs and alcohol, getting enough sleep and taking some time to relax. This will help you achieve your goals and cope with stress.

All of us benefit from support during times of struggle. You are not alone. There are many helpful resources available through campus and an important part of the college experience is learning how to ask for help. Asking for support sooner rather than later is often beneficial.

If you or anyone you know experiences any academic stress, difficult life events, or feelings like anxiety or depression, I strongly encourage you to seek support. Student Health and Wellness (SHAW) is here to help: call 641-269-3230 or visit their website. Consider reaching out to a friend, faculty, or family member you trust for help getting connected to the support that can help.

If you or someone you know is feeling suicidal or in danger of self-harm, call someone immediately, day or night:

Miscellaneous Resources

Syllabus Acknowledgements