CS228 - Logic for Computer Science
Instructor
Prof. Krishna S.
Semester
Autumn ‘20
Course Difficulty
Moderate
Time Commitment Required
Moderate
Grading Policy and Statistics
AA 5
AB 12
BB 20
BC 32
CC 8
DD 2
Total 79
Attendance Policy
No mandatory attendance required
Pre-requisites
None
Evaluation Scheme
There were 8 short quizzes that were held on Moodle(which comprised of 10% weightage),4 assignments and 4 subsequent peer reviews for the assignments (which comprised of 20% ),Midsem+Endsem(70%).
Topics Covered in the Course
1.Introduction to Propositional Logic
- Rules for Natural Deduction and Proof Engines
- Soundness and Completeness of Propositional Logic
- Normal Forms, Horn Algorithm and Resolution
- Introduction to First Order Logic
- First Order Logic for Languages
- Deterministic Finite State Automata (DFA)
- Nondeterministic Finite State Automata (NFA)
9.Conjunctive normal forms, satisfiability and validity of propositional formulae
10.Horn clauses and satisfiability
11.Resolution - Monadic Second Order (MSO) Logic
- MSO on Words
- Transition Systems and Linear Temporal Logic (LTL)
- Infinite Words and Buchi Automata (DBA and NBA)
- LTL Model Checking
- Generalized NBA and LTL Model Checking Complexity
Teaching Style
Lectures were made available on the YouTube channel made by the prof for the course. Doubt/Discussions sessions were held every Wednesday and tutorials sessions were held on Fridays. Excellent lecture slides were also made available by the instructor which were used in the YouTube lectures . The professor’s teaching style was easy to understand, and the material covered was quite interesting and intellectually stimulating. The lectures were, for the most part, evenly paced. The professor encouraged doubts and always cleared them up quite effectively.
Tutorials/Assignments/Projects
I found the tutorial problems very intriguing. We were given the problems beforehand and encouraged to solve them before the session, where they were discussed in detail.
Feedback on Exams
The examinations were neither too easy nor too hard. Solving the tutorials and following the lecture slides did help a lot .
References Used
Lectures slides and video lectures were enough.
For additional reading Books suggested by prof were:
1.LOGIC IN COMPUTER SCIENCE ~~by MICHAEL HUTH, MARK RYAN
2.Applied Automata Theory ~~Prof. Dr. Wolfgang Thomas, RWTH Aachen
3.Principles of Model Checking ~~Christel Baier and Joost-Pieter Katoen
CS 228 Review By: Arpit Tiwari