CSE303
INTRODUCTION TO THE THEORY OF COMPUTATION
SPRING 2026

Course Information


News:

FIRST CLASS- Tuesday, January 27

Time:  Tuesday, Thursday   3:30pm  -  4:50pm

Place:  Engineering 143

WE  HAVE  our own  CSE303 LECTURES  YOUTUBE CHANEL

  CSE303: Theory of Computation 

The YOUTUBE CHANNEL contains a set of VIDEOS filmed in Stony Brook TV Studio
VIDEOS cover Chapter 1 to Chapter 4 of the  course Textbook
 Please use them  for class lectures review and  study during the semester

Professor:

Anita Wasilewska

208  New CS Building
phone:  (631) 632-8458

e-mail: anita@cs.stonybrook.edu

Professor Office Hours

Short questions via email any time
e-mail: anita@cs.stonybrook.edu
Office Hours: Tuesday, Thursday 1:30pm - 2:30pm
and by appointment
In person: 208  New CS Building   

Teaching Assistants  Office Hours

 TAs Office Hours will be   posted and updated on Brightspac


TA Office hours: 
In person:  Room 2126  Old  CS Building

TEXTBOOK

Elements of the Theory  of Computation 

Harry R. Lewis and Christos H. Papadimitriou, Prentice Hall  (Second Edition,1998)

Additional Textbook

Turing's Vision -  The Birth of Computer Science

Chris Bernhard, The MIT Press, Cambridge, Massachusetts, London England (2016)

COURSE OBJECTIVES

Introduce abstract models of computation such as finite and push-down automata, and analyze their relative expressive power. Explore the connection between abstract machine models and formal languages, as specified by grammars.
Enhance students awareness of both the power and inherent limitations of algorithmic computation via the study of Turing machines and/or other abstract computational models.

COURSE DESCRIPTION

The course is an introduction to the abstract notions encountered in machine computation. Topics include finite automata, regular expressions, and formal languages, with emphasis on regular and context-free grammars. Questions relating to what can and cannot be done by machines are covered by considering various models of computation, including Turing machines, recursive functions, and universal machines.


PRELIMINARY TESTS SCHEDULE

Changes, if any will be advertised in NEWS section and posted on Blackboard

 All TESTS are CLOSED book

MIDTERM 1
Tuesday, March 10
SPRING BREAK
March 16 - March 20
MIDTERM 2
Tuesday, April 21
Last Day of classses
May 8
FINAL  - t.b. a in  period  May 12-20


 21 Preliminary STUDY PLAN 

WEEK 1: 
Class Lecture 1
VIDEO Lecture 1 
Chapter 1: Sets, Relations, and Languages
WEEK 2:
Class Lecture 2,4
VIDEO Lecture 1
Chapter 1: Sets, Relations, and Languages
WEEK 3:      
Class Lecture 4a   Chapter 1 Review
Class Lecture 5
VIDEO Lecture 2
Chapter 2:  Finite Automata  - Deterministic Automata  FIRST PART
WEEK 4:  
Class Lecture 5
VIDEO Lecture 2 
Chapter 2: Finite Automata -  Deterministic Automata  SECOND PART 
WEEK 5: 
Class Lecture 5
VIDEO Lecture 2
Chapter 2: Finite Automata - Nondeterministic Automata
WEEK 6: 
Class Lecture 6, 6a
VIDEO Lecture 2
Chapter 2: Finite Automata - Nondeterministic Automata
WEEK 7:
Class Lecture 7     
VIDEO Lecture 2 
Chapter 2: Finite Automata - Finite automata and Regular Languages
WEEK 8:           Spring Break, March 16 -20   

VIDEO Lecture 2
Chapter 2: Finite Automata - Closure Theorems, Main Theorem
WEEK 9:
Class Lecture 8
Video Lecture 2
Book Chapter 2: Finite Automata - Languages that are not Regular, Pumping Lemma
WEEK 10:
Book Chapter 3: Context Free Grammars  
 

THE FULL STUDY PLAN will be  POSTED  on BRIGHTSPACE

Grading General Principles and Workload

TESTING

ALL TESTS, including the FINAL Examination will be given IN CLASS

 The PRELIMINARY schedule is posted above
 Changes will be posted on the course Web page and in Brightspace Announcements.
 

 MAKE-UP EXAMS POLICY

The Course Policy on make-up exams, is consistent with university policy on Student Participation in University Sponsored Events, the policy on Final Exams and the New York State Education Law regarding Equivalent Opportunity and Religious Absences _2as defined in the UNDERGRADUATE BULLETIN https://www.stonybrook.edu/sb/bulletin/current/

No MAKE-UP TESTS  except of documented cases of illness or documented emergencies

Make-up exams will be given only in extenuating circumstances
For example doctor's note stating that you were ill and unfit to take the exam
Students who miss an exam for a valid reason must contact the instructor immediately
to take a make-up exam at the earliest possible time
 Specific arrangements will be made on a case-by-case basis

GRADING PRINCIPLES
 
HONESTY of students is the most important part of the class work.TESTS are ”closed book” - no cell phones, no computers, desks must be empty - no extra papers, no communication with other students. Professor supervises all tests together with course TAs. Anybody violating these rules would have to immediately submit the test to the Professor and leave the class.
Student will get 0pts for the TEST and will be reported, if needed, to the University Academic Judiciary, as stated and explained the the Syllabus’ Academic Integrity Statement

  ALL GRADES are listed on Brightspace

 Contact TAs if you need more information or need to talk about grading

WORKLOAD

 There will be   TWO  MIDTERMS (100pts each) and a FINAL (100pts)  examination
The consistency of your efforts and work is the most important for this course.
There will be some extra credit problems as a part of quizzes and tests
 
EXTRA CREDIT
You can earn up to 20 extra credit points during the semester.
Each TEST will include an Extra Points PROBLEM.

None of the grades will be curved

Final Grade Computation

The grade will be determined in the following way: number of earned points divided by 3 = % grade
 
The % grade is translated into letter grade in a standard way i.e.

100 - 90 % is A range,   89 - 80 % is B range,    79 - 70 % is C range,  69 - 60 % is D range,   and F is below 60%.
 
See SYLLABUS for detailed  distribution and explanation

Homework Assignments and Tests

Lectures Homework: study  yes/no questions and examples included  in Lectures covered during each week. Study  also posted solutions of  previous quizzes and tests that cover the  material in Lectures. Book Homework:  Homework 1- Homework 4  as posted in the Syllabus.

None  of the Homework Assignments  will be collected or graded.
 Students are responsible for solving the problems They cover solutions to majority of Book Homework assignments. 
and checking  their solutions  included in Lectures  and posted solutions  of previous tests. 
Your Tests problems will be very close to  posted  previous Quizzes,Tests, Examples, Book's  Examples and  Examples in the  Class Lectures.

DOWNLOADS

Fall 2026 Syllabus

Fall 2026 Syllabus slides


CLASS LECTURES
 
Book Chapter 1: Sets, Relations, and Languages

 Lecture 1 
Lecture 2
Lecture 3
Lecture 4
Lecture 4a - REVIEW of Chapter 1
 
Book Chapter 2: Finite Automata

 Lecture 5
Lecture 6
Lecture 6a - REVIEW 1 for Lectures 5, 6 
Lecture 7
Lecture 8 - Review 2 for Chapter 2
 
 
Book Chapter 3: Context Free Languages

 Lecture 9
Lecture 10
Lecture 11 - Chapter 3 Problems
Lecture 12 - Chapter 3 Short Review

 Book Chapter 4: Turing Machines

 Lecture 13  
Lecture 14 - Short REVIEW for Final

 VIDEO LECTURES: Slides and VIDEOS

Video Lectures SLIDES are exactly the SLIDES  used in the VIDEOS
 Use them  when you watch the Videos (as many times as you need!)

Slides - Lecture 1
Video Lecture 1

Slides -Lecture 2
Video Lecture 2

Slides - Lecture 3
Video Lecture 3

Slides - Lecture 4
Video Lecture 4

PAST   QUIZZES and  TESTS SOLUTIONS

Q1 Solutions
Q2 Solutions
Practice Midterm Solutions
Practice Final Solutions
FINAL Solutions

MORE PAST QUIZZES SOLUTIONS

Q1 Solutions
Q2 Solutions
Q3 Solutions
Q4 Solutions

MORE PAST TESTS SOLUTIONS

Practice Midterm Solutions
Midterm Solutions
FINAL Solutions

MORE PAST QUIZZES SOLUTIONS

Q1 Sample Solutions
Q1 Practice Solutions
Q1 Solutions
Q2 Sample Solutions
Q2 Practice Solutions
Q2 Solutions
Q3 Practice Solutions
Q3 Solutions
Past Q3 Solutions
Past Q4 Practice Solutions
Q4 Practice Solutions
Past Q4 Solutions
NEW Q4 Solutions

ACADEMIC INTEGRITY STATEMENT

Each student must pursue his or her academic goals honestly and be personally accountable for all submitted work. Representing another person's work as your own is always wrong. Any suspected instance of academic dishonesty will be reported to the Academic Judiciary. For more comprehensive information on academic integrity, including categories of academic dishonesty, please refer to the academic judiciary website at A Judiciary Website

Stony Brook University Syllabus Statement

If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact Disability Support Services at (631) 632-6748 or http://http://studentaffairs.stonybrook.edu/dss They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential. Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and Disability Support Services. For procedures and information go to the following website: http://www.sunysb.edu/ehs/fire/disabilities.shtml

Critical Incident Management

Stony Brook University expects students to respect the rights, privileges, and property of other people. Faculty are required to report to the Office of University Community Standards any disruptive behavior that interrupts their ability to teach, compromises the safety of the learning environment, or inhibits students' ability to learn. Faculty in the HSC Schools and the School of Medicine are required to follow their school-specific procedures. Further information about most academic matters can be found in the Undergraduate Bulletin, the Undergraduate Class Schedule, and the Faculty-Employee Handbook.

Stony Brook University Syllabus Statement

If you have a physical, psychological, medical, or learning disability that may impact your course work, please contact Disability Support Services at (631) 632-6748 or Disability Support ServicesWebsite They will determine with you what accommodations are necessary and appropriate. All information and documentation is confidential. Students who require assistance during emergency evacuation are encouraged to discuss their needs with their professors and Disability Support Services. For procedures and information go to the following website: Disability Support Services Website