Basic Information
Course Objectives:
To introduce students to the basic concepts in theoretical computer science, and the formal relationships among machines, languages, and grammars and computational problems.
Syllabus:
Following is the syllabus for the course. This is an almost lossless rephrasing of the syllabus from department website, except for the word "optional". It is very likely that we will not cover the optional topics. But we will reach a point where they are just a few reads away so that interested readers can go after the extra references provided in the class.- Finite Automata & Regular Languages: Introduction to automata theory, languages and computational problems. Finite state automata, Regular Languages. Deterministic and Non-deterministic finite automata, Subset construction. Regular Expressions, Pattern Matching
- Context Free Languages and Push Down Automata : Grammars - Production systems - Chomskian hierarchy - Context free grammars - Normal forms - uvwxy theorem - Parikh mapping - Self embedding property - subfamilies of CFL - Derivation trees and ambiguity. Pushdown automata - Acceptance by empty store and final state - Equivalence between push-down automata and context-free grammars - Closure properties of CFL - Deterministic push-down automata - Parsing - CYK algorithm
Optional Topics : Deterministic bottom-up and top-down parsing - LR(k) and LL(k) grammars - Complexity of parsing algorithms, Lex and Yacc, Compiler tools. - Turing machines & Computability - Techniques for Turing machine construction - Generalized and restricted versions equivalent to the basic model - Universal Turing machine - Recursively enumerable sets and recursive sets. Decidability; Undecidability, Reductions. Rice's theorem (mention); decidability of membership, emptiness and equivalence problems of languages. Context sensitive languages and linear bounded automata (mention). Basic complexity classes.
Learning Outcomes:
We will be working on the top five levels of Bloom's Taxonomy.The student will be able to (in other words, this is what the exams will test):
- Model, compare and analyse different computational methods using combinatorial methods.
- Apply rigorously formal mathematical methods to prove properties of languages, grammars and automata.
- Construct algorithms for different problems and argue formally about correctness on different restricted machine models of computation.
- Identify limitations of some computational models and possible methods of proving them.
Course Pre-requisites:
The IITM curriculum aims this core course to be delivered to the second year B.Tech students. There is no formal pre-requisite for crediting this course, other than eligibility to attend the 4th semester of your BTech course. The informal pre-requisite is CS2100: Discrete Mathematics Course.Evaluation:
The final score will depend on 5-6 parameters:- Quiz-I (20%) - Feb 26, 2022, 10:00 - 11:30
- Quiz-II (20%) - Mar 26, 2022, 10:00 - 11:30
- Endsem Exam (40%) - May 09, 2022, 09:00 - 12:00
- Biweekly Short Tests & Tutorials (30%)
Course Load :
Here is estimated load for each of the course activities for an average student in the class.Activity | Hrs/Wk |
---|---|
Lectures/Tutorials | 4 |
Weekly Problem Sets | 2 |
Self-study | 4 |
Total | 10 |
TA Contact Hours | 1.5(optional) |
Instructor Contact Hours | 1.25(optional) |