CSE581

Computer Science Fundamentals: Theory
Fall 2024

Course Information

News:

FINAL THURSDAY, December 12, 5:30 pm - 8:00 pm JAVITS 110

Midterm 1 Thursday October 17, 5:00 pm in CLASS

Midterm 1 covers MATERIAL from Q1-Q4
Midterm will have three Parts: 1. Problems, 2.Y/N DM Definitions, 3. DM Y/N Questions

Q1 - Q4 SOLUTIONS are POSTED

Q3 and Midterm 1 Dates Changes

Q3 Thursday, OCTOBER 10
Midterm 1 Thursday, OCTOBER 17

Here is a short review tests to help you revew for Midterm1

PREDICATE LOGIC REVIEW Yes/No Self Test

Q2 is given as scheduled on Thursday, September 26
Q1 SOLUTIONS were distributed in class and posted on Brightspace pace

OUR 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
Extra QUIZZES SCHEDULE
Quizzes are given on THURSDAYS during last 25 minutes of class
September 12, 26, October 10, 24, November 7, 21

Time: Tuesday, Thursday 5:00pm - 6:20pm

Place: JAVITS 110

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 the book B2

The book B1 LOGIC LECTURES follow and cover all 11 Chapters of the book

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

Please use them for relavant 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:30pm - 7:30pm
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
In person: 2126 OLD CS Building

COURSE TEXTBOOKS

Book B1

Anita Wasilewska
LOGICS FOR COMPUTER SCIENCE: Classical and Non-Classical
Springer 2019
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:
Classicsal and Many Valued, and of some parts of Chapters 4, 5,6 (Proof Systems, Proof of the Completeness Theorem for Classical Propositional Logic, and Intriduction to automated Theorems Proving )

Here is my 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 2024 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 Webpage and on BRIGHTSPACE

We give MAKE-UP TESTS 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 2 MIDTERMS - 80pts each, and a FINAL - 140pts examination
The consistency and honesty of your efforts and work is the most important for this course

EXTRA CREDIT
There wil be some extra credit problems as a part of tests and
6 extra credit ONE PAGE QUIZZES given in class (up to total of 30pts)

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 CURRENT Schedule

MIDTERM 1 Thursday, October 17
Fall Break October 14 - 15
MIDTERM 2 Thursday, November 14
Thanksgiving Break November 27 -December 1
Last Day of Classes Saturday, December 6
FINAL - December 12, 5:30pm - 8:00pm

QUIZZES SCHEDULE
Quizzes are given on THURSDAYS during last 25 minutes of class
September 12, 26, October 10, 24, November 7, 21

DOWNLOADS

Q1 Solutions

Q2 Solutions

Q3 Solutions

Q4 Solutions

Fall 2024 SYLLABUS

F24 Lecture 0: Course Structure,Principles, and Syllabus

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-

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 OVERVIEW

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 at 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

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.