CS228 - Logic for Computer Science

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

  1. Rules for Natural Deduction and Proof Engines
  2. Soundness and Completeness of Propositional Logic
  3. Normal Forms, Horn Algorithm and Resolution
  4. Introduction to First Order Logic
  5. First Order Logic for Languages
  6. Deterministic Finite State Automata (DFA)
  7. Nondeterministic Finite State Automata (NFA)
    9.Conjunctive normal forms, satisfiability and validity of propositional formulae
    10.Horn clauses and satisfiability
    11.Resolution
  8. Monadic Second Order (MSO) Logic
  9. MSO on Words
  10. Transition Systems and Linear Temporal Logic (LTL)
  11. Infinite Words and Buchi Automata (DBA and NBA)
  12. LTL Model Checking
  13. 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