MNIT Jaipur Syllabus Information Technology Advanced Compiler
A Tour of Compiler Design, LR Parsers – SLR parsers, Canonical LR and LALR parsers, Lex and Yacc
Tools, Control-flow Analysis, Control-flow Graphs, Basic Blocks, Data-flow Analysis, Dependence
Analysis, Global Optimizations, Loop Optimizations, Dominators, Loop-invariant computations, Code
motion, Data Dependence Analysis in Loops, Loop Scheduling, Runtime System Architectures and
Automatic Memory Management Techniques.
1. Aho, Alfred V., Sethi, Ravi, Ullman, Jeffrey D., Compilers: Principles, Techniques and Tools,
2. Steven Muchnick, Advanced Compiler Design & Implementation, Morgan Kaufmann.
3. Keith Cooper and Linda Torczon, Engineering a Compiler, Morgan Kaufmann.
IT-483 Design and Analysis of Algorithms (3-0-2) 4Review of Algorithms: Seaching and Sorting, Tree and Graph traversal. DFS and its applications.
Shortest path algorithms, minimum spanning tree algorithm. Algorithm Design Techniques: Greedy
algorithm, dynamic programming, divide and conquer, backtracking, branch and bound.
Algorithm Analysis: Asymptotic notation, solution of recurrence, model of computation, time and space
complexities, average and worst case analysis, Amortized analysis. Master’s theorem. Recurrence
Graph Algorithms: network flow, matching, coverings, applications of DFS:- bi-connectivity, Euler
circuits, strongly connected components, topological sort, and articulation point. Network Flow.
Greedy Algorithms: Knapsack problem.
Dynamic Programming: Chained matrix multiplication, longest common subsequence.
Divide and Conquer: Order Statistics – finding the median, exponentiation, matrix multiplication, LCS.
Approximate Algorithm: Travelling Salesman Problem, vertex-cover problem.
Matrix Algorithms – Strassen Matrix multiplication, LUP decomposition.
Number Theoretic Algorithms: Primality Testing, Factorization.
Miscellaneous: Introduction to appoximate, randomized and probabilistic algorithms.
Introduction to problem classes – NP, NPC, NP-Hard.
Text / References:
1. Cormen, Leiserson, Rivest: Introduction to Algorithms, Prentice Hall of India.
2. Horowitz and Sahani: Fundamental of Computer algorithms.
3. Aho A.V , J.D Ulman: Design and analysis of Algorithms, Addison Wesley
4. Brassard : Fundamental of Algorithmics, PHI.
5. W.W. Peterson and E. J. Weldon: Error correcting codes.
6. Sara Baase, Allen Van Gelder: Computer Algorithms: Introduction to Design and Analysis,