California State University, Chico
Computer Science Department
CSCI 415, Theory of Computation, Fall 2026

Instructor

Oleksiy Al-saadi
Office Location: O'Connell 222
Phone: 530-898-6442
Email: oal-saadi (at) csuchico (dot) edu

General Information

We meet synchronously in our designated class times at our designated classroom. Details for synchronous meetings are on the calendar in Canvas.

Prerequisites: Grade of C- or better in CSCI 311.

Overview

Lecture, 3 units. This course studies abstract models of computation, including their formal definition, corresponding languages, computing power, and capabilities. Models studied will include finite automata, pushdown automata/regular expressions, and Turing machines. Related topics will include regular languages, context-free languages, time and space complexity, Classes P and NP, intractable problems, unsolvable problems, and intractable problems.

Section Time Location
1
Mon/Wed/Fri 1:00 PM - 1:50 PM O'Connell Center 241



Objectives

A tentative schedule is provided below. Canvas shows the most accurate due dates for each assignment and the true pace of our activities.

Week(s) Topics
1
M1. Regular Languages, Finite Automata
2
M1. Nondeterminism
3
M1. Pumping Lemma
Homework 1 Due
4
Exam 1
M2. Context-free Languages
5
M2. Pushdown Automata
6
M2. Pumping Lemma for CFL's
Homework 2 Due
7
Exam 2
M3. Turing Machines
8,9
M3. Decidable Languages, Halting Problem
10
Homework 3 Due
M4. Complexity Classes
11
Exam 3
M4. Reductions and NP-Hard Problems
12-15
M4. Graph Theory and NP-Completeness
Oracles and Reductions Labs Due
Gadgets Homework Due
Exam 4


Materials

Textbook
Introduction to the Theory of Computation. 3rd Edition. 
Michael Sipser
ISBN: 9781133187790
Publisher:  Cengage Learning
Year:  2012

CSU Email - I send emails regularly throughout this course. You are required to check your email often.
Canvas - Canvas always holds the most current and authoritative set of due dates, exam dates, assignment instructions, and other course material. Course announcements will be done via Canvas (which also sends these to your csuchico.edu email address).
Overleaf - LaTeX will be used to write your solutions for homework assignments and Overleaf will facilitate group work. Create an Overleaf account here.

Grading

A tentative partition of your final grade is made up of the following components:
Grading Scale

Note: Up to 0.5% may be added to your final grade at the instructor's discretion for constructive participation in the class. Constructive participation includes in-class participation; asking good questions or providing help during activities; etc. Regular attendance is necessary but not sufficient for this bonus. No other adjustments of borderline grades will be considered.

Late Policy

An important part of your education and professional development in college is about learning to independently manage work and deadlines. This skill is incredibly authentic and valued by employers. It is a disservice to you if I act like deadlines do not matter. Moreover, new concepts need to be applied quickly to be retained in memory. Therefore, there is a late policy in effect.

All assignments can be turned in up to 48 hours late and are subject to a 5% penalty per day, even if turned in minutes after the due date. Exceptions are granted only for specific circumstances such as illness or emergency. Only your most recently submission will be graded (e.g., if you submit an incomplete program before the due date and then submit a complete program after the due date, I will grade the late submission.)

Illness

If you are ill (fever, coughing or contagious with anything), please don't come to school. Stay home. Although in-class activities may not be made up for any reason, the lowest scored quiz (which may include 0's from missed quizzes) will be dropped from the gradebook automatically. Extra credit opportunities provide ways to obtain additional points.

Regrade Policy

Regrade requests will be accepted up to 1 week after a graded item is returned. The reason for the regrade request must be explained in email, with a copy of the assignment to be re-graded, to the instructor's university email. Note that all regrade requests, except for those pointing out mistakes in the totaling of points, will cause the entire assignment to be re-graded. The adjusted grade may therefore be higher or lower than the initial grade.

Incomplete Grade Policy

It is the policy of the Computer Science Department that a grade of Incomplete (I) shall be assigned only when the instructor concludes that a clearly identifiable portion of course requirements cannot be met within the academic term for unforeseen, but fully justified, reasons; and when there is still a possibility of earning credit.

An incomplete shall not be assigned when: The student must retain the grades for any coursework that was due prior to the incomplete being assigned. An incomplete grade cannot be removed on the basis of work taken at another institution nor by re-enrolling in the course.

An incomplete must be made up within one calendar year immediately following the end of the term in which it was assigned. This limitation prevails whether or not the student maintains continuous enrollment. Failure to complete the assigned work will result in an incomplete "I" being converted to an "NC" which will affect the grade point average.

Academic Dishonesty

Collaboration is a complex idea in the programming world, since professionals routinely work in teams sharing solutions; they also navigate a variety of complex intellectual property rules that sometimes encourage (and sometimes discourage) sharing solutions more generally. In our class, the collaboration policies are more artificial than the real world since they are designed to support you, as a beginner learner, to grow towards mastery and independence.

Generally, I encourage you to seek help from and provide support to your peers, but only in ways that do not steal learning opportunities from them or from yourself. I call this "supportive collaboration." It is not only allowed, it is encouraged.

Warning: The boundary between collaboration and plagiarism is often unclear. Once you see someone's solution, it is hard to unsee. It is safer to collaborate without looking at each other's screens. Use drawings to communicate ideas. Use references to quizzes or lecture modules and class resources to establish common ground ("I just modified everything after line 40 in the textbook solution to 9.4, and that really helped me as a guide"). Help identify tools that are useful ("I found that a proof by contradiction was helpful") without sharing solutions. If you just share your screen and show someone how you did it, you are robbing them of a learning opportunity.

In particular, you are responsible not just for understanding every aspect of a solution you write, but also for knowing what would happen if your solution was modified in some way or how to modify it to accomplish some nearby task.

There is no collaboration of any form allowed on exams. Generally, graded work is to be completed by the individual student or class pair unless otherwise specified and following the university's policies on academic integrity. Academic dishonesty will be severely penalized; at a minimum, you will receive a grade of 0 on the assignment. A second case of academic dishonesty will result in automatic failure of the course.

Copying any text provided by artificial intelligence (i.e. ChatGPT) is academic dishonesty and will result in an automatic 0 on the assignment. Any homework LaTeX submissions that use math display mode, signified as \[ and \], will be assumed to be AI-generated. The use of terms such as "Verifier" or "Certificate" in any solution implies to me that it is AI-generated. If you receive a 0 on an assignment and do not come to office hours within one week of the grade being posted to discuss your solutions, this constitutes an admission of academic dishonesty. If you are unable to explain any aspect of your submission based on my questions (i.e. "I forget why I wrote this" or "I don't know what this symbol in my solution means"), then the grade will remain a 0.

Accomodations

Disability Services for Students

If you are a student with a disability, and think you may need academic accommodations, please contact Accessibility Resource Center (ARC, see link) as early as possible in order to avoid a delay in receiving accommodation services. Use of ARC services, including testing accommodations, requires prior authorization by ARC in compliance with university policies and procedures.

Athletic Schedules

To student athletes: I value your identity as a scholar/athlete. Please notify me before the end of the drop/add period about any possible game conflicts with our class schedule (and as soon as possible about subsequent changes).