CSE 105 - Theory of Computation, Fall 2025

Welcome to CSE 105! This course will help you answer fundamental questions about computing:

• What problems are computers capable of solving?
• What resources are needed to solve a problem?
• Are some problems harder than others?

In this course, we will explore what it means to be "computable". We begin with a very simple model of computation, and work our way to the most powerful, the Turing machine, named after Alan Turing, who formalized the notion of "algorithm" in this last model even before there were any physical computers. You'll also learn about the relationship of these models to some essential tools in a computer scientist's toolkit, such as regular expressions and context-free grammars. Finally, you'll develop your technical communication skills in writing formal arguments and proofs.

Michael Sipser, Introduction to the Theory of Computation, 3rd ed.
We will use the international edition, which is much more affordable. It is available on Amazon for about $20.
See also the errata for a list of known typos/errors in the book.

The final grade will be composed as follows:

• Final exam: 50% (must pass to pass class)
• Midterms: 35% (2 midterms, best of the two)
• Homework: 15% (7 homeworks, lowest grade dropped)
• In-class participation: up to +3 points (out of 100), see explanation below.

A passing grade in the final exam (at least 50%) is required to pass the class. Letter grades will be assigned as follows:

• A range (A-,A,A+): 88.0% - 100%
• B range (B-,B,B+): 75.0% - 87.9%
• C range (C-,C,C+): 60.0% - 74.9%
• D: 50.0% - 59.9%
• F: below 50.0%

The designation of +/- inside a grade range is based on the instructor discretion, and will depend on the grade distribution as well as your particiaption in class and discussion, coming to office hours, and improvement throughout the class.

Homework is 15% of the final grade. There will be 7 homework sets; the lowest grade will be dropped. In each homework set, you will receive a list of questions, out of which you need to choose 5 problems to solve. The same set of problems will also be your set of practice problems for midterms and final. After the homework deadline, we will release solutions to all problems, to set expectations on how we expect you to solve the problems.

Homework is due on Mondays midnight, no exceptions! Because we will release the solutions shortly after, we will not accept late submissions. Submission is online via Gradescope. You should already be enrolled; if not, enroll using your @ucsd.edu email and the code PGZG43.
Instructions:

• Homework should be solved in groups of 4-5 students (you may change groups between homework assignments).
• Submit only one submission per group.
• No collaboration or discussion outside the groups is allowed (but if you are stuck on a problem, please come to discussion or office hours).
• Late submissions are not allowed.

I want to keep this class as interactive as possible, to help you follow lectures better and to help identify mis-understood concepts early on.
We will use Webclicker to run polls during class. Please sign in using your @ucsd.edu email and use the code DGJZYU to find the class.
If you participate in all polls, you will get 3 extra points in the overall class grade (out of 100).
If you participate in some, you will get a partial grade based on the fraction that you participated in.

We use Piazza for discussion forums: any questions that you have on the material, and finding other students for group study and homework. Please use public posts for general questions about the class or material, and private posts for personally relevant questions or questions that can reveal a solution or approach to a homework problem. You should already be enrolled; if not, enroll using your @ucsd.edu email and the code ld7is6dwdem.

You can access all previous classes through podcast.

Your goal is to excel in this class with integrity. It is an academic violation to:

• Ask others to give you homework or test answers
• Share your answers on homework or tests
• Work on the homework with anyone other than your homework partners
• Share answers or notes while taking an exam
• Search the internet or other resources not provided for the class for homework solutions
• Use ChatGPT or similar services to ask or get answers for homework or exams

This is a partial list of common academic violations in this class. If you are not sure if some activity constitutes an academic violation or not, please ask us before doing it. We will report academic violations to the academic integrity office. See also the detailed academic integrity policy for more information.