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
Introduction to Grammar and Languages; Finite Automata, DFA, NFA; Equivalence of DFA nad NFA; Minimization of DFA; Regular Expressions; Regular expressions and DFA; Properties of Regular Languages; Closure properties of Regular Languages; Pumping lemma for Regular languages, proof examples: use of pumping lemma to prove not Regular.
Context Free Grammar (CFG) and Context Free Language (CFL); Equivalence of left most derivation and right most derivation; Chomsky Normal Form (CNF and related proofs; Converting given grammar to CNF; Push Down Automata (PDA); Examples of PDA; CFG and PDA, NPDA; Pumping lemma CFLs, proof, examples; Closure properties of CFL; Properties of CFL, more examples.
Introduction to Turing Machine (TM), Basics of TM, examples of TMs; Basic operations in TM as language recognizer, countably infinite and uncountable sets; Languages not Turing computable, Church-Turing thesis; Variants of TM, standard TM, universal TM, Recursive and recursively enumerable languages; Halting problem theorem and its proof, Problems reducible to halting problem; Complexity classes, reduction, etc.
Books/References:
1. Introduction to Automata Theory, Languages and Computation by John E. Hopcroft and Jeffrey D. Ullman.
2. Elements of the Theory of Computation by H. Lewis and C. Papadimitriou.
3. Introduction to the Theory of Computation by Michael Sipser.
4. Computers and Intractability: A Guide to the Theory of NP-Completeness by Michael Garey and David S. Johnson.
Database Management Systems (CSC 603)
Link: Slides/Materials/Practice Exercises: https://db-book.com/
Module-I: Geometric algorithms: convex hulls, Voronoi diagram, line segment intersections, closest pairs, range searching, KD-trees, polygon triangulation. (10 Lectures)
Module-II: A quick revision of Complexity Classes: computation model, classes: P, NP, NP-hard and NP-complete; reducibility between problems and NP-completeness: discussion on different NP-complete problems like satisfiability, clique, vertex cover, independent set, Hamiltonian cycle, TSP, knapsack, set cover, bin packing, etc. (4-6 Lectures)
Module-III: Approximation algorithms: approximation ratio, vertex cover, set cover, knapsack problem, art gallery problems, and other examples. Randomized algorithms: Monte Carlo and Las Vegas algorithms, examples. (6 Lectures)
Module-IV: Algorithms on arrays: Linear-time median finding, sorting in linear time, string matching (Rabin-Karp and Knuth-Morris-Pratt algorithms). (4 Lectures)
Module-V: The Idea of Parallelism, PRAM Model of Parallel Computation, Pointer Jumping and Divide & Conquer: Useful Techniques for Parallelization. PRAM Algorithms: Parallel Reduction, Prefix Sums, List Ranking, Merging Two Sorted Lists, Graph Coloring, sorting, matrix multiplication etc. (6-8 Lectures)
Books:
1. R. Motwani and P. Raghavan, Randomized Algorithms, Cambridge University Press, 1995.
2. T. H. Cormen, C. E. Leiserson and R. L. Rivest, Introduction to Algorithms, Second Edition, Prentice-Hall India, 2003.
3. V. Vazirani, Approximation Algorithms, Springer, 2003.
4. M. de-Berg, O. Cheong, M. van-Kreveld, M. Overmars, Computational Geometry, Springer.
Introduction: Phases of compilation and overview.
Lexical Analysis: Regular language, finite automata, regular expression, regular expression to finite automata, recognition of tokens, reserved words, identifiers, scanner generator (lex, flex).
Syntax Analysis: Context free language and grammar, pushdown automata, derivations, parsing, parse trees, ambiguity, eliminating ambiguity, elimination of left recursion, top-down parsing, bottom-up parsing, recursive descent parsing, LL(1) grammars, predictive parsing, Shift-Reduce parsing, LR(0), SLR, LR(1), LALR(1) grammars and parser generator.
Semantic Analysis: Attributed grammar, syntax directed definition, evaluation and flow of attribute in a syntax tree. Symbol Table: Structure, symbol attributes and management.
Runtime environment: Procedure activation, parameter passing, value return, memory allocation, and scope.
Intermediate Code Generation: Translation of different language features, different types of intermediate forms.
Code Improvement/optimization and Target Code Generation: control flow, dataflow dependencies etc; Code improvement: local optimization, global optimization, loop optimization etc. Architecture dependent code improvement: instruction scheduling (for pipeline), loop optimization etc, register allocation and target code generation.
Books:
Textbook: Compilers: Principles, Techniques and Tools, Aho, Lam, Sethi & Ullman, 2007
References:
1. Allen I. Holub, Compiler Design in C, Prentice-Hall (https://holub.com/goodies/compiler/compilerDesignInC.pdf)
2. Andrew W. Appel, Modern Compiler Implementation in C/Java, Cambridge University Press
(Link: https://www.cs.princeton.edu/~appel/modern/).
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.