| FOUNDATIONS OF COMPUTING SCIENCE Autumn 2017-18 |
|---|
|
Teaching Assistants: Antonio Bruto da Costa, Sudipa Mandal, Madhumita Mallick |
| |
Introduction | Prof. Pallab Dasgupta | |
|
| |
Quiz 1 - Regular Languages | |
|
|
| Regular Languages | Prof. Pallab Dasgupta | |
Preliminaries, DFAs, NFAs, Understanding Non-Determinism | |
| |
Regular Languages | Prof. Pallab Dasgupta | |
Closure Properties (Union, Intersection, Concatenation), Introduction to Regular Expressions and the Pumping Lemma [Student Task: What is the pumping length? And what is its impact in relation to Regular Languages?] |
| |
Tutorial 1 - Regular Languages | |
||
| |
Context Free Languages | Prof. Pallab Dasgupta | |
Context Free Languages, Context Free Grammars, Ambiguity |
| |
Context Free Languages Contd. | Prof. Pallab Dasgupta | |
CFL Ambiguity Contd., Chomsky Normal Form, Push Down Automata, Excercise: CFGs <=> PDAs interconversion |
| |
Quiz 2 - Context Free Languages | |
|
|
| |
Context Free Languages Contd. | Prof. Pallab Dasgupta | |
Pumping Lemma for Context Free Languages (Date for Class Test 1 TBD) |
| |
Context Free Languages Contd. | Prof. Pallab Dasgupta | |
Pumping Lemma for Context Free Languages and Closure Properties for CFLS, NPDAs are strictly more powerful than DPDAs |
| |
Non-Regular Languages | |
Some non-regular languages also satisfy the Pumping Lemma for Regular Languages. Read the attached document | |
| |
The Church-Turing Thesis | |
An introduction to Turing Machines and configurations of the machine | |
| |
The Church-Turing Thesis | |
Reducability and Decidability; Variants of the Turing Machines | |
| |
Tutorial : Context Free Languages | |
Worked on CNF, Pumping Lemmma, English Descriptions of CCFGs. Students must attempt unsolved problems. | |
| |
The Church-Turing Thesis | |
Decidability and Recognizability of Languages | |
| |
The Church-Turing Thesis | |
Decidability and the Halting Problems | |
| |
Tutorial : Turing Machines | |
Worked on CNF, Pumping Lemmma, English Descriptions of CCFGs. Students must attempt unsolved problems. | |
| |
Class Test 1 (24-08-2017) | [Solutions] |
Class Test 1 | |
| |
Reducability Decidability | [PDF-Decidability] |
Reducability Decidability | |
| |
Complexity Theory | [Space Complexity Slides] |
[Polynomial Hierarchy - Additional Material] | |
| |
Tutorial: Complexity Theory | |
||
| |
Logic and Reasoning | |
||
| |
Tutorial: Propositional Logic | |
||
| |
Tutorial: Predicate Logic | |
||
| |
Class Test 2 | |
||
| |
Past Question Papers | |