CSE581

Computer Science Fundamentals: Theory
Fall 2025

Course Information

News:

EQ2 Date  CHANGED to Thursday, November 6
Midterm 2 Date CHANGED to Tuesday, November 18
Midterm 3 Date CHANGED to Tuesday, December 2

We covered Book B2, TCB Lectures 2, 3, 4 (no automata),

MIDTERM 1 SOLUTIONS Posted
Midterm 1 Return and Grades Consultatiion DAYS;
Monday, October 20  2:00pm  - 3:00pm
Tuesday, October 21  11:00 am - 1:00pm

NEW UPDATED   TESTS SCHEDULE  and   SYLLABUS posted
We finished Book B1 LOGIC LECTURES  (covered chapters 2 and 3 only)
We covered B2  DISCRETE  Mathematics  BASICS Lectures 1, 2, 3
Review Definition 1, 2, 3. for Midterm 1

 Discrete Mathematics  DM Self STUDY Test posted

Time:  Tuesday, Thursday  2:00pm  -  3:20pm

Place:  JAVITS 102

We  have   our own  LOGIC, Theory of Computation  LECTURES  YOUTUBE CHANEL

  LOGIC, Theory of Computation 

The first 4 Lectures are for the Theory of Computation and  cover  Chapter 1- Chapter 5 of  Book B2

  Book B1  LOGIC LECTURES follow  next and cover all Chapters of the book, of which we cover parts of Chapters 2 -5 only

The YOUTUBE CHANNEL contains a set of  professional VIDEOS filmed in Stony Brook TV Studio

 Please use them  for relevant lectures and to  review and  study during the semester

Professor:

 Anita Wasilewska

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

e-mail: anita@cs.stonybrook.edu

Professor Anita Wasilewska  - Office Hours

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

Teaching Assistants  Office Hours

 TAs Office Hours are  posted and updated on BRIGHTSPACE an mailed to all students


TAs Office Location:
2126  OLD CS Building
 

COURSE TEXTBOOKS 

Book B1

 Anita Wasilewska
LOGICS FOR COMPUTER SCIENCE:  Classical and Non-Classical
Springer 2018
 ISBN 978-3-319-92590-5             ISBN 978-3-319-92591-2 (e-book)

We will cover Chapter 2 (Introduction to Classical Propositional and Predicate Logic,
 present an OVERVIEW of  parts of Chapter 3 (Formal syntax and propositional extensional semantics: Classical and Many Valued, and of some  parts of  Chapters 4, 5 (Proof Systems, Proof of the Completeness Theorem for Classical Propositional Logic)

Here is the  Logic Book B1 for you to use

My Logic Book

Book B2

Harry R.Lewis and Christos H. Papadimitriu
ELEMENTS OF THE THEORY OF COMPUTATION
Prentice Hall, Second Edition, 1998

We will cover  all  Chapter 1. This is Discrete Mathematics Basics segment of the course. We will supplement it by  special Discrete Mathematics Lectures.  We also  present  an OVERVIEW  of parts of  Chapters 2, 3 - in particular of Regular and Context Free Languages,
 and their relationship with Finite  and Push Down Automata, respectively)

Book B3
 
R. Graham, D.Knuth, O.Patachnik
CONCRETE MATHEMATICS: A FOUNDATIONS FOR COMPUTER SCIENCE
Addison-Wesley Publishing Company, Third edition

We will cover some content of Chapter 1 (Recurrent and Closed Form Formulas, Repertoire Method), some of Chapter 2 (Sums and Recurrences), and some of Chapter 4 (Number Theory).

Course Structure

The course presents FUNDAMENTALS of Computer Science Theoretical Foundations
divided into Three PARTS: P1  - LOGIC,  P2 - Discrete Mathematics, Theory of Computation,   P3 - Concrete Mathematics

  Fall 2025 SYLLABUS

Grading General Principles and Workload

TESTING

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

The PRELIMINARY schedule is posted below.
Changes will be posted on the course Web page and on BRIGHT SPACE

We give  MAKE-UP TESTS  ONLY in  documented cases of illness or  emergencies  and  other cases
 as defined in the course Syllabus.

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

  WORKLOAD
 There will be  3 MIDTERMS - 100pts each,  and no final  examination.
The consistency and honesty of your efforts and work is the most important for this course

 EXTRA CREDIT
There will be 2  ONE PAGE QUIZZES, each 10pts given in class for extra credit.
You can earn up to 20 extra credit pts.

None of the grades will be curved

Final Grade Computation

You can earn up to 300 points + x extra points = 300+x points during the semester.
The grade will be determined in the following way: number of earned points divided by 3 = % grade.
The % grade is translated into a letter grade in a standard way - see SYLLABUS for explanation

Tests FINAL Schedule

EQ1 Tuesday, September 25
Fall Break  October 13 - 14
MIDTERM 1  Thursday, October 16
EQ2  Tuesday, November 4
MIDTERM 2  Tuesday, November 18
Theorems List for Mid 3 - November 20
Thanksgiving Break  November  26 - 30
MIDTERM 3  Tuesday, December 2
 Last Class  Thursday, December 4
FINAL  - no Final

QUIZZES POLICY
The  Extra  Credit Quizzes are nor obligatory and you free to take  them or not to take them - it means
there are  no makeups. Corrected copies of Quizzes will be distributed  in class on Tuesdays following the Quiz
 by TA who is in charge of a given Quiz and will be kept after Tuesday class by her/him

DOWNLOADS

Fall 2025 SYLLABUS

F25 Lecture 0: Course Structure and Syllabus

Here are  a short review tests  to help you review for Midterm1

 PREDICATE LOGIC REVIEW Yes/No Self Study Test

  DM- Discrete Mathematics Self Study Test

  MIDTERM 1 SOLUTIONS


P1: LOGIC LECTURES

Logic Lecture 1

Book B1 Chapter 2: Introduction to Classical Logic - OVERVIEW
Lecture 2: Propositional Language and Semantics 
Lecture 2a: Predicate Language and Semantics
Lecture 2b: Chapter 2 Review

Book B1 Chapter 3: Propositional Semantics: Classical and Many Valued - OVERVIEW

Lecture 3: Formal Propositional Languages
Lecture 3a: Classical Propositional Semantics 
Lecture 3b : Many Valued Semantic: Lukasiewicz, Heyting, Kleene, Bohvars 
Lecture 3c: Extensional Semantic M
Lecture 3d :Classical Tautologies and Equivalence of Languages
Lecture 3e: Chapter3 Review

End of P1: Logic Lectures

Book B1 Chapter 4: General Proof Systems: Syntax and Semantics   - OVERVIEW

Lecture 4: General Proof Systems
Lecture 4a: Chapter 4 Review

General Proof Systems SHORT OVERVIEW

Book B1 Chapter 5: Hilbert Proof Systems for Classical Propositional Logic  - OVERVIEW
Lecture 5: Hilbert Proof Systems for Classical Logic

  Chapter 5 - SHORT OVERVIEW

Book B1 Chapter 6: Automated Proof Systems for Classical Propositional Logic  -reading

Lecture 6: RS Systems, Proof of Completeness Theorem 
 Chapter 6 SHORT OVERVIEW

Book B1 Chapter 7: Introduction to Intuitionistic and Modal Logics   - reading 

Lecture 7; Introduction to Intuitionistic Logic
Lecture 7a: Introduction to Modal Logics

Book B1 Chapter 11: Classical Formal Theories: Consistency and Completeness - reading

Lecture 11: Hilbert Program, Godel Incompleteness Theorems

  BOOK B1: VIDEO LECTURES  

CHAPTER 1
CHAPTER 2  
CHAPTER 3
CHAPTER 4
CHAPTER 5
CHAPTER 6
CHAPTER 7
CHAPTER 8
CHAPTER 9
CHAPTER 10
CHAPTER 11

P2: DISCRETE MATHEMATICS and THEORY OF COMPUTATION LECTURES

Book B2  Chapter 1: Sets, Relations, and Languages

All Chaper 1 

Book B2  Chapter 1 and  DISCRETE MATHEMATICS BASICS

DMB -  Lecture 1
DMB - Lecture 2
DMB - Lecture 3
DMB - Lecture 4

DM DEFINITIONS 1

DM DEFINITIONS 2

DM DEFINITIONS 3

Book B2  Chapters 2, 3 THEORY of COMPUTATION BASIC

TCB - Lecture 1: Closures and Algorithms

TCB - Lecture 2: Alphabets and Languages

TCB -  Lecture 3: Finite Representation of Languages - Regular Languages

TCB -  Lecture 4: Finite Automata and Regular Languages

TCB -  Lecture 5: Context-Free GRAMMARS and LANGUAGES

TCB -  Lecture 6: CONTEXT FREE and NOT CONTEXT FREE LANGUAGES

  BOOK B2: VIDEO LECTURES  

P2 CHAPTER 1
P2 CHAPTER 2  
P2 CHAPTER 3
P2 CHAPTER 4

Book B3  Chapters 1,4 CONCRETE MATHEMATICS BASICS

CM Lecture 1: Recurrent Problems - Tower of Hanoi, Josephus Problem

CM Lecture 2: Generalized Josephus

CM Lecture 3: Number Theory



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.

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

Academic Dishonesty Statement

The following statement about academic dishonesty, is required to be included in syllabi for all undergraduate courses: "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. Faculty is required to report any suspected instances of academic dishonesty to the Academic Judiciary. Faculty in the Health Sciences Center (School of Health Technology, Management, Nursing, Social Welfare, Dental Medicine) and School of Medicine are required to follow their school-specific procedures. For more comprehensive information on academic integrity, including categories of academic dishonesty please refer to the academic judiciary website at the academic judiciary website." Be advised that any evidence of academic dishonesty will be treated with utmost seriousness. Those involved will be prosecuted to the fullest extent permitted by the University and College policies.}

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.