Theory of Computation
CSE 105 - Winter 2026

Place and Time:Peterson 110, MWF 9:00am-9:50am
Instructor:Daniel Grier (dgrier@ucsd.edu)
Resources:Canvas, Gradescope, Piazza

Discussion:Center 101, F 4:00pm-4:50pm
Instructor office hours:Tuesdays from 10:30am-11:30am in CSE 4218
Wednesdays from 1pm-2pm in CSE 4218
TA/tutor office hours:Refer to this spreadsheet

Textbook:Introduction to the Theory of Computation, Michael Sipser

Assignments

Schedule
Jan 5 Introduction and decision problems
Jan 7 Alphabets, strings, languages, and DFA Sipser 0.2,1.1
Jan 9 Regular languages Sipser 1.2
Overview

In this course, we will develop mathematical tools that will allow us to reason formally about computation. We will tackle the following fundamental questions:

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

We begin with a very simple model of computation, and work our way to the most powerful. You will learn how to prove that a problem can be solved by some models of computation, but not others. Ultimately, we will show that some problems are so difficult that no computer can ever hope to solve them. Along the way, you'll develop your technical communication skills in writing formal arguments and proofs.

Evaluation
  • Homework (15%): There will be 7 homework assignments. The lowest score will be dropped.
  • Participation (5%): Participation is based entirely on Gradescope quizzes given in class. Your lowest 3 quiz scores will be dropped.
  • Midterms (40%): There will be two midterms. The first midterm is February 6 in class.
  • Final (40%): March 18 at 8am in Peterson 110. If higher, your final will replace the lowest of your two midterm scores.

Letter grades will be assigned at least as follows:

  • A range (A-,A,A+): 90% - 100%
  • B range (B-,B,B+): 80% - 89.9%
  • C range (C-,C,C+): 65.0% - 79.9%
  • D: 50.0% - 64.9%
  • F: below 50.0%
The designation of +/- inside a grade range will be determined at the end of the term. The above scale is guaranteed for this quarter: for example, if your cumulative average is 82, your final grade will be at least B-. These are the guaranteed thresholds. The thresholds may be adjusted downward, so that a lower percentage corresponds to a higher letter grade, if deemed appropriate.
Podcasts
There are no public podcasts for this course. If you are sick or otherwise need to miss class for an extenuating circumstance, please submit this podcast request form. It is important for you to follow the instructions on the form so that we can properly share the podcast with you.
Accommodations
Students requesting accommodations for this course due to a disability must provide a current Authorization for Accommodation (AFA) letter issued by the Office for Students with Disabilities. Students are required to discuss accommodation arrangements with instructors and OSD liaisons in the department in advance of any exams or assignments.