CS 46: Theory of Computation — Spring 2026

Instructor: Prof. Andrew Danner

Class: MW 9:00am-10:15am Science Center 204

Lab A: W 1:05-2:35pm Martin 227

Office hours: M 10:30am-12:00pm, R 1:30-2:40pm Martin 306

Textbook: Introduction to the Theory of Computation 3e by Michael Sipser (any edition is ok) Errata.

Clickers: You will need an iClicker (physical device, not the app) for this class. Register your iClicker here.

Edstem: CS46 Q&A forum

GitHub CS46 Swarthmore GitHub Organization

Welcome to CS46: Theory of Computation! This course is an introduction to the formal systems that are commonly used as abstract models for computational processes. We will study a variety of computational models, and classify and solve problems in each of them. While computers are now ubiquitous and the idea of an algorithm seems natural, where did these ideas originate? Why, for instance, do we have memory on our machines --- is it necessary for computation, or simply a convenience? Do other methods of computation even exist? Could we solve more interesting problems with another model?

Along the way, this course will develop mathematical concepts which are fundamentally important for computer science: decidability, undecidability, and computational complexity. We will go beyond simply saying "this problem seems hard" and show that some computational problems are inherently harder than others, or simply unsolvable by computers. We will examine the limits of computers and computation, and consider the consequences of these limits. By approaching these topics from a formal standpoint, this course aims to teach students how to describe and to reason precisely about computational objects.

By the end of this course, you will have developed the following knowledge and skills:

Above all, the goal of this course is to instill a deep understanding of the limits of computation, and how to think about these in a thorough and systemic way.

CS46 is different from most other computer science courses, in that the course focuses on abstract thinking about problems. It does not ask you (often) to implement every solution in code. This course is much more about reasoning about which problems are solvable by computers, and less about actually solving every problem with a coded project. To succeed in this course, you should consistently do the following:

Grades will be weighted as follows:

Some work during lab sessions will consist of in-lab practice exercises for group discussion and will not be graded. Written weekly lab assignments are separate from these practice exercises, submitted electronically via git, and graded for correctness and completeness.

Lab assignments are submitted electronically using git, and are typically due by 11:59pm on Tuesdays. You may submit your assignment multiple times, but only the final submission will be graded. You’ll be able to work with a partner on several but not all homework assignments; each homework assignment will specify if working with a partner is allowed. Lab assignments will be a mix of written problems (in LaTeX) and coding problems.

Limited collaboration in planning and thinking through solutions to problems is allowed and encouraged, but no collaboration is allowed in writing up solutions. Your submitted write-up is your own. Please list your discussion partners and the extent of your discussions in your post-lab survey. If you used any resources beyond the textbook and professor, you MUST cite them in your survey.

Note: in the following paragraphs, "code" refers to all solutions, including written programs but also proofs, analysis, written reports, etc.

Academic honesty is required in all your work. Under no circumstances may you hand in work done with (or by) someone else under your own name. Your code should never be shared with anyone; you may not examine or use code belonging to someone else, nor may you let anyone else look at or make a copy of your code. This includes, but is not limited to, obtaining solutions from students who previously took the course or code that can be found online. You may not share solutions after the due date of the assignment.

Discussing ideas and approaches to problems with others on a general level is fine (in fact, we encourage you to discuss general strategies with each other), but you should never read anyone else’s code or let anyone else read your code. All code you submit must be your own with the following permissible exceptions: code distributed in class, and code found in the course text book. In these cases, you should always include detailed comments that indicates on which parts of the assignment you received help, and what your sources were.

Failure to abide by these rules constitutes academic dishonesty and will lead to a hearing of the College Judiciary Committee. According to the Faculty Handbook: "Because plagiarism is considered to be so serious a transgression, it is the opinion of the faculty that for the first offense, failure in the course and, as appropriate, suspension for a semester or deprivation of the degree in that year is suitable; for a second offense, the penalty should normally be expulsion."

The spirit of this policy applies to all course work, including code, homework solutions (e.g., proofs, analysis, written reports), quizzes, and exams. Please contact me if you have any questions about what is permissible in this course.

Students must strictly adhere to the following policy, which applies to all exams taken in a Computer Science course at Swarthmore:

Exam takers must place all non-essential items at the front of the room (or other designated area). Unless otherwise permitted, students may not have any electronic devices or course materials in their possession during the entirety of the exam. This includes cell phones, tablets, laptops, smart watches, course notes, articles and books, among others. These items should be placed at the front of the room near the proctor. If you need to leave the room during the exam, you must obtain permission from an instructor first. Any non-permitted discussion or aide in regards to exam material will result in immediate forfeiture of the exam and a report to the College Judiciary Committee. Please discuss any concerns or accommodations with your instructor prior to starting the exam.

If you believe you need accommodations for a disability or a chronic medical condition, please contact Student Disability Services via e-mail at studentdisabilityservices at swarthmore.edu to arrange an appointment to discuss your needs. As appropriate, the office will issue students with documented disabilities or medical conditions a formal Accommodations Letter. Since accommodations require early planning and are not retroactive, please contact Student Disability Services as soon as possible. For details about the accommodations process, visit the Student Disability Services website.

To receive an accommodation for a course activity, you must have an Accommodation Letter from the Office of Student Disability Services and you need to meet with us to work out the details of your accommodation at least two weeks prior to the activity.

You are also welcome to contact us privately to discuss your academic needs. However, all disability-related accommodations must be arranged, in advance, through Student Disability Services.

We’ll be using Edstem, an online Q&A forum for class discussion, help with labs, clarifications, and announcements that pertain to all sections of CS46. You should be automatically enrolled in CS46 on Edstem. If you don’t have access, please let me know.

Edstem is meant for questions outside of regular meeting times such as office hours, class, and lab. Please do not hesitate to ask and answer questions on Edstem, but keep in mind the following guidelines:

Writing lab solutions is required for this course. It is also a good skill to learn. If you plan on going to graduate school and/or publishing papers in the future, you will end up writing in $\LaTeX$. This page gives some resources and links to good latex tutorials.

For most latex files, you should be able to compile a latex file using e.g. 'pdflatex foo.tex'. As with other compilable programs like C++, you might get some compilation errors.

Links that are related to the course may be posted here. If you have suggestions for links, let me know.