Sonoma State University
Computer Science Department
CS454, Theory of Computation, Spring 2025

Instructor

Oleksiy Al-saadi
he/him/his
Office Location: Darwin 116E
Zoom: SonomaState.zoom.us/my/oleksiyalsaadi
Email: alsaadio (at) sonoma (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 CS 315, or consent of instructor.

Overview

Lecture, 4 hours. 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
Tues/Thurs 3:00 PM - 4:50 PM Stevenson Hall 1211

In addition, the SSU CS faculty have designated CS 454 as the course that will meet SSU's Upper Division GE Area B Requirement for CS Majors.

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
Exam 1
4
M2. Context-free Languages
5,6
M2. Pushdown Automata
Exam 2
7
M3. Turing Machines
8,9
M3. Decidable Languages, Halting Problem
Exam 3
10
M4. Complexity Classes
11
M4. Reducability
12-15
M4. Perfect Graphs
Exam 4


Materials

Textbook - (Required) Sipser, Michael. Introduction to the Theory of Computation. 3rd ed. Cengage Learning, 2012. ISBN: 9781133187790.

(Supplemental use by instructor / optional) Golumbic, Martin. Algorithmic Graph Theory and Perfect Graphs. 2nd edition. North Holland. 2004. ISBN: 9780444515308.
SSU 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 sonoma.edu email address).
Piazza - We will be using Piazza for class discussion. The system is highly catered to getting you help fast and efficiently from classmates and myself. Rather than emailing me, I encourage you to post questions on Piazza so everyone benefits from my response. Piazza gives you the option of sending messages to me that are anonymous, too.
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 helpful responses via Piazza; 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 10% 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.)



Administrative Drops

If you do not indicate your commitment to taking this course in the first two weeks of the semester, you may be administratively dropped from the class. In this course, your commitment is evidenced by:
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 condition for removal of the Incomplete shall be entered on the “Request for Incomplete” form and a copy filed in the department office prior to listing an “I” on the Grade Roster. 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 a “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 code; they also navigate a variety of complex intellectual property rules that sometimes encourage (and sometimes discourage) sharing code 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 past labs 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 using a while loop was helpful") without sharing code. 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 line of code you write, but also for knowing what would happen if your code 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 or quizzes, unless explicitly directed. Generally, graded work is to be completed by the individual student 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. For more information, see SSU's cheating and plagiarism policy and the Dispute Resolution Board website.

Copying any code provided by artificial intelligence (i.e. ChatGPT) will result in an automatic 0 on the assignment.

Accomodations

Disability Services for Students

If you are a student with a disability, and think you may need academic accommodations, please contact Disability Services for Students (DSS), Voice: (707) 664-2677, TTY/TDD: (707) 664-2958, as early as possible in order to avoid a delay in receiving accommodation services. Use of DSS services, including testing accommodations, requires prior authorization by DSS in compliance with university policies and procedures. See SSU’s policy on Disability Access for Students.

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).