CS 228 – LOGIC FOR COMPUTER SCIENCE
Instructor: Prof. Krishna S.
Session: 2019-2020
Prerequisites: N/A
Course content and structure:**
This course was entirely a theory course with no programming assignments etc. (but an abundance of very interesting problems). The main topics covered were:
- 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)
- 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
Feedback on lectures: There was no mandatory attendance policy and it wasn’t even recorded. However, a lot of examples and explanations were on the board, so I imagine those who skipped classes would spend more time covering up for them in self-study. The professor’s teaching was easy to understand, and the material covered was quite interesting and intellectually stimulating. The lectures were, for the most part, evenly paced (though a little slow at the beginning). The professor encouraged doubts and, in my opinion, always understood and cleared them up quite effectively.
Feedback on tutorials and exams: I found the tutorial problems very intriguing and enjoyed solving them. We were given the problems beforehand and encouraged to solve them before the session, where they were discussed in detail. Doubts regarding the problems or otherwise were addressed on Piazza and the solutions to the unsolved problems were also posted here. The examinations were neither too easy nor too hard. A number of problems (especially in the end-semester exam) were quite original and not just derived from the tutorials. However, solving the tutorials did help a lot. The strictness of the evaluation was largely dependent on the TA allotted to the question.
Difficulty (on a scale of 1 being very easy to 5 being very hard): 3
Textbooks & References: The lecture slides and class notes were more than sufficient. However, the professor also recommended some textbooks for additional reading on some of the topics, pdfs of which were provided by her on Piazza.
Grading Statistics: AP 2 AA 8 AB 17 BB 36 BC 30 CC 15 CD 11 DD 7 FR 6
Additional comments & what you learnt from the course: Overall, I quite enjoyed the course and especially liked the formalization of the logic which we use nearly everywhere. If the absence of coding isn’t a deal-breaker for you and you enjoy solving logical problems, I would recommend that you try this course out.
Review by – Devak Sinha (devakdsinha@gmail.com)