Computer graphics, Autumn 2014-15, Autumn 2015-16, Autumn 2016-17, NIT Meghalaya
Theory of Computation, Spring 2014-15, Spring 2015-16, NIT Meghalaya (M. Tech course)
Principles of Programming Languages, Spring 2014-15, NIT Meghalaya
Computer Programming, Autumn 2015-16, Autumn 2016-17, NIT Meghalaya
Algorithms I, Autumn 2018-19, IIIT Kalyani
Algorithms II, Autumn 2019-20, IIIT Kalyani
Graph Theory, Spring 2017-18, 2018-19, IIIT Kalyani
Image Analysis, Spring 2017-18, Spring 2019-20, IIIT Kalyani
Discrete Mathematics, Spring 2019-20, IIIT Kalyani
1. Introduction, easy and hard problems, algorithms and complexity.
2. Turing machines, models of computation, multi-tape deterministic and non-deterministic Turing machines, decision problems.
3. The halting problem and undecidable languages, counting and diagonalisation, tape reduction, universal Turing machine, undecidability of halting, reductions, Rice's theorem.
4. Deterministic complexity classes, linear speed-up theorem, polynomial reducibility, polytime algorithms: 2-satisfiability, 2-colourability.
5. NP and NP-completeness, non-deterministic Turing machines, polynomial time verification, NP-completeness, Cook-Levin theorem, polynomial transformations: 3-satisfiability, clique, colourability, Hamilton cycle, partition problems. pseudo-polynomial time, strong NP-completeness, knapsack, NP-hardness.
6. Space complexity and hierarchy theorems. linear Space compression Theorem, PSPACE, NPSPACE, PSPACE = NPSPACE, PSPACE-completeness. The quantified boolean formula problem is PSPACE-complete, L, NL and NL-completeness, NL=coNL, hierarchy theorems.
7. Optimization and approximation, combinatorial optimisation problems, Relative error, Bin-packing problem, Polynomial and fully polynomial approximation schemes, Travelling salesman problem, minimum partition.
8. Randomized Complexity, The classes BPP, RP, ZPP.
Books:
1. Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael R. Garey, David S. Johnson
2. Dexter C. Kozen, Automata and Computability, Undergraduate Texts in Computer Science, Springer.
3. Vijay Vazirani, Approximation Algorithms, Springer.
4. John E. Hopcroft, Rajeev Motwani and Jeffrey D. Ullman, Introduction to Automata Theory, Languages, and Computation, Pearson Education Asia.
5. C. H. Papadimitriou. Computational Complexity, Addison-Wesley.
6. T. H. Cormen, S. Clifford, C. E. Leiserson and R. L. Rivest. Introduction to Algorithms, MIT Press, Second Edition.
=========================================
19-01-15: Introduction to Grammar and Languages
23-01-15: Fininte Automata, DFA, NFA
27-01-15: Equivalence of DFA nad NFA
02-02-15: Minimization of DFA, Mark and Reduce method
03-02-15: Mark and Reduce algorithm
09-02-15: Regular Expressions
10-02-15: Regular expressions and DFA
13-02-15: Properties of Regular Languages
17-02-15: Closure properties of Regular Languages
20-02-15: Pumping lemma for Regular languages, proof
23-02-15: Examples: use of pumping lemma to prove not Regular.
24-02-15: CFG and CFL
27-02-15: Equivalence of left most derivation and right most derivation,
Chomsky Normal Form (CNF)
02-03-15: Chomsky Normal Form related proofs
03-03-15: Converting given grammar to CNF
16-03-15: Push Down Automata (PDA)
17-03-15: Examples of PDA
23-03-15: CFG and PDA, NPDA
24-03-15: Pumping lemma CFLs, proof, examples
26-03-15: Closure properties of CFL
30-03-15: Properties of CFL, more examples
31-03-15: Introduction to Turing Machine
06-04-15: Basics of TM, examples of TMs
07-04-15: Basic operations in TM, more examples of TMs
10-04-15: TM as language recognizer, countably infinite and uncountable sets.
13-04-15: Languages not Turing computable, Church-Turing thesis
17-04-15: Variants of TM
20-04-15: Variants of TM (contd.), equivalence with standard TM, Universal TM
21-04-15: Recursive and recursively enumerable languages
24-04-15: Recursive and recursively enumerable languages (contd.)
27-04-15: Halting problem theorem and its proof
28-04-15: Problems reducible to halting problem
01-05-15, 04-05-15: Reduction to Halting problem (contd.)
05-05-15, 08-05-15, 11-05-15, 12-05-15, 13-05-15: Complexity classes, reduction, etc.
20/01/2015: Preliminaries - Recursion, example: Tower of Hanoi
21/01/2015: Recursion - more examples.
22/01/2015: Programming Language Paradigms
27/01/2015: Compiler, phases, compiler vs interpreter
28/01/2015: Syntactic items, Lexical analysis
29/01/2015: Parsing techniques, Top-down, Bottom-up parsing
03/02/2015: First, Follow computation for a given CFG, Construction of predictive parsing table
04/02/2015: Parsing algorithm
10/02/2015: Left recursion elimination, examples, why needed.
11/02/2015: Data types, Data objects
12/02/2015: Vectors/Arrays, representation: row major, column major, l-value, r-value
17/02/2015: Address computation in a multi-dimensional array.
18/02/2015: Records
19/02/2015: Parameter passing techniques
24/02/2015: Sequence control
25/02/2015: Control Flow Diagram: Basic blocks
03/03/2015: Logic programming
05/03/2015: Prolog program example
17/03/2015: PROLOG programming example, use of Cut
18/03/2015: Permutation, sorting using permutation, Mergesort, Quicksort using PROLOG
19/03/2015: Computation Models
24/03/2015: Designing Push Down Automaton using PROLOG
26/03/2015: Object oriented programming: Introduction
31/03/2015: Objects, Classes, Constructors, access specifiers
01/04/2015: Polymorphism: Overloading of operators
06/04/2015: Examples of Overloading of operators
07/04/2015: Inheritance: features; base class, derived class.
09/04/2015: Overloading of member functions
13/04/2015: Levels of inheritance
15/04/2015: Example of inheritance
16/04/2015: Purely virtual function, examples.
21/04/2015: Purely virtual function: more examples
23/04/2015: Friend function, examples.
28/04/2015: Destructor, use of destructor, examples.
29/04/2015: Syntax directed translation scheme, inherited, synthesized attributes
30/04/2015: Evaluation order, dependency graphs
05/05/2015: Applications of syntax-directed translation
07/05/2015 - 14/05/2015: Syntax Directed Definition: examples, problems.