Teaching
Teaching
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