Compiler Design :: Course Content & online available resources

Course Content

Introduction: Translators, Various phases of compiler, tool based approach to compiler construction.

Lexical analysis: token, lexeme and patterns, difficulties in lexical analysis, error reporting, implementation, regular definition, transition diagrams, LEX.

Syntax Analysis: top down parsing (recursive descent parsing, predictive parsing), operator precedence parsing, bottom-up parsing (SLR, LALR, Canonical LR), YACC.

Syntax directed definitions: inherited and synthesized attributes, dependency graph, evaluation order, bottom-up and top-down evaluation of attributes, L-attributed and S-attributed Definitions.

Type checking: type system, type expressions, structural and name equivalence of types, type conversion, overloaded functions and operators, polymorphic functions.

Run time system: storage organization, activation tree, activation record, parameter passing, dynamic storage allocation, symbol table: hashing, linked list, tree structures.

Intermediate code generation: intermediate representation, translation of declarations, assignments, control flow, Boolean expressions and procedure calls, implementation issues.

Code generation and Optimization: issues, basic blocks and flow graphs, register allocation, code generation, dag representation of programs, code generation from dags, peephole optimization.

Reference Texts and E-Resources

Compilers: Principles, Techniques, & Tools, second edition, by Aho, Lam, Sethi, Ullman

Compilers: Principles, Techniques, and Tools, first edition, By Aho, Sethi, Ullman

The Theory and Practice of Compiler Writing, By J. P. Trembley and P. G. Sorensen

Compiler Design in C, By Allen I. Holub

Basics of Compiler Design, By Torben Ægidius Mogensen

Modern Compiler Implementation in C, By Andrew W. Appel

Modern Compiler Design, Springer

Modern Compiler Implementation in Java, By Andrew W. Appel and Jens Palsberg

Engineering a Compiler, By Keith D. Cooper, Linda Torczon; Morgan Kaufmann Publishers

Notes by Allan Gottlieb: https://cs.nyu.edu/courses/spring09/G22.2130-001/class-notes.html

Slides: https://www.cse.iitk.ac.in/users/karkare/cs335/

Video Lectures: http://nptel.ac.in/course.php

Lab Assignments

C Language Specification: Appendix A: Reference Manual, C Programming Language, Kernighan and Ritchie

Lex & Yacc Tutorials by: Tom Niemann, Victor Eijkhout, A. Karkare, Dragon Book(Pages- 140, 287)

gcc Compiler: https://gcc.gnu.org/onlinedocs/gcc/

Lex Files and Commands used in Lecture on Lex: Download

Yacc and Lex Files, and Commands used in Lecture on Yacc: Download


Assignments

1. Implement the Lexical Analyzer using C language.
2. Tokenize the hello world program using Lex/Flex tool.
3. Write a program in Flex which recognizes identifiers in C language.
4. Write a program in Flex which recognizes integers and float numbers in C language.
5. Write a program in Flex which recognizes relational operators in C language.

6. Implement the Lexical Analyzer using LEX tool. (Reference: page number 143 of Dragon Book).
7. Compile and execute the yacc source programs given on page numbers 289, and 292 of Dragon Book.
8. Write parser and lexer for a desk calculator using Yacc and Lex tool. Compile and link parser and lexer together to create      a single executable calculator.exe.

9. Write a program to implement symbol table and its operations.
10. Write a program to generate abstract syntax tree using Yacc.
11. Write a program to parse a given string using following parsers:
      (i) Recursive descent parsing,   (v) Predictive parser,    (i) Operator precedence parser,    (ii) LR parser

12. Write a program to generate parsing table for SLR parser.

13. Write a program to check whether the given grammar is LR(0) or not.

14. Write a program to check whether the given grammar is SLR(1) or not.

Reading Assignments:

1. Bootstrapping in Compiler Design
2. Run Time System

Object Oriented Programming through JAVA :: Course Content & online available resources

Course Content

Object Oriented Concepts: Objects and Classes, Bottom-up approach, O-O design principles, O-O Design and Modeling.

Basic O-O language Constructs: Primitive Data Types and Operations, Selection Statements, Loops, Arrays, Strings, Objects and Classes, Inheritance and method overriding, Polymorphism.

Java Language Fundamentals: Object Design: constructors, instance variables, methods. Memory models, scope, streams and I/O programming, Inner classes, Interfaces and packages, Exception Handling, Multithreading.

Advanced Concepts: Creating GUIs and Displaying Data, Event Driven Programming.

Frameworks: The framework concept, Frameworks in the Java API: Collections Framework, Graphics Framework.

Reference Texts and E-Resources

E. Balagurusamy, Programming with Java, TMH

C. Thomas Wu, An introduction to Object Oriented Programming with JAVA, Mc Graw Hill

Herbert Schildt, The Complete Reference JAVA, McGraw Hill

Bruce Eckel, Thinking in Java, Pearson

Simon Kendal, Object oriented programming using java, Ventus Publishing

R. Buyya, S. T. Selvi, X. Chu, Object Oriented Programming with Java: Essentials and Applications, Mc Graw Hill

C. S. Horstmann, G. Cornell, Core Java Volume I—Fundamentals, Prentice Hall

Different Programming Paradigms:

https://en.wikipedia.org/wiki/Comparison_of_programming_paradigms

http://funkyjavascript.com/procedural-vs-object-oriented-vs-functional-programming/

Lab Assignments

Parallel Computing :: Course Content & online available resources

Course Content

Introduction to Parallel Computing: Supercomputers and grand challenge problems, Modern Parallel Computers, Data Dependence Graph, Data Parallelism, Functional Parallelism, Pipelining and Data Clustering.

Interconnection Networks: Switch Network Topologies, Direct and Indirect Network Topology, Bus, Star, Ring, Mesh, Tree, Binary Tree Network, Hyper Tree Network, Hybrid, Hypercube, Perfect Shuffle Network, Torus and Butterfly Network.

Performance Analysis: Introduction, Execution Time, Speedup, Linear and Superlinear Speedup, Efficacy and Efficiency, Amdahl’s Law and Amdahl Effect, Gustafson-Barsis’s Law, Minsky's Conjecture, The Karp-Flatt Metric, The Isoefficiency Metric, Isoefficiency Relation, Cost and Scalability.

Parallel Computational Models: Flynn’s Taxonomy, PRAM, EREW, CREW, ERCW, CRCW, Simulating CRCW, CREW & EREW, PRAM algorithms.

Introduction to Parallel Algorithms: Parallel Programming Models, PVM, MPI Paradigms, Parallel Programming Language, Brent’s Theorem, Simple parallel programs in MPI environments, Parallel algorithms on network, Addition of Matrices, Multiplication of Matrices.

Reference Texts and E-Resources

Hwang and Briggs, Computer Architecture and Parallel Processing, McGraw Hill

Behrooz Parhami, Introduction to parallel processing: algorithms and architectures, Springer

Joseph JA JA, Introduction to Parallel Algorithms, Addison Wesley

S. G. Akl, The Design and Analysis of Parallel Algorithms, PHI

A. Grama, A. Gupta, G. Karypis, V. Kumar, Introduction to Parallel Computing, Addison Wesley

H. Casanova, A. Legrand, Y. Robert, Parallel Algorithms, CRC Press

Notes (by Anuradha Bhatia): Parallel and Distributed System

Tutorial: Introduction to Parallel Computing

Slide: Parallel computing

Parallel Virtual Machine: http://www.itec.uni-klu.ac.at/~harald/PVM/pvm_guide.html

Parallel Programming using MPI and Lab Assignments

Computer Graphics :: Course Content & online available resources

Course Content

Introduction to Computer Graphics, Display Technologies, Random and Raster Scan, frame buffer, bit plane, Input Devices, Graphics Standards, Graphics Hardware.

Line and Circle Drawing Algorithms, Scan Conversion, filling algorithms, clipping.

Two Dimensional transformations, Homogeneous Coordinates, Rigid Body and Affine transformations, Parallel and perspective projections, vanishing points, viewing transformation.

Hidden line removal method, Cubic Spline, Bezier curve, B-Spline Curves, Fractal Curves.

Reference Texts and E-Resources

Computer Graphics - C Version 2nd Ed, By Hearn, Baker

Theory and Problems of Computer Graphics By Z. Xiang, R. A. Plastock, Schaum's Series

Mathematical Elements for Computer Graphics by D F Rogers

Computer Graphics (Principles and Practice) by Foley, van Dam, Feiner and Hughes, Addisen Wesley

Slides: Computer Graphics Hearn & Baker ppt

Graphics Programming:

http://www.cprogramming.com/graphics-programming.html

http://www.programmingsimplified.com/c/graphics.h

http://www.techcrashcourse.com/2015/08/c-graphics-programming-tutorial.html

https://www.cs.colorado.edu/~main/bgi/doc/

https://en.wikipedia.org/wiki/Borland_Graphics_Interface

Lab Assignments

Database Management Systems :: Course Content & online available resources

Course Content

Introduction: Database Systems, View of Data Models, Database Languages, DBMS Architecture, Database Users and Data Independence.

ER Modeling: relation types, role and Structural Constraints, Extended ER Modeling Features, Design of an ER Database Schema, Reduction of ER Schema to Tables.

Relational Model: Relational Model Concepts, Relational Algebra.

Introduction to SQL: SQL data types and literals, Types of SQL commands, SQL operators, Tables, views and indexes, Queries and sub queries, Aggregate functions.

Relational Database Design: Functional and multi-valued Dependencies, Desirable Properties of Decomposition, Normalization up to 3 NF and BCNF.

Selected Database Issues: Security, Transaction Management, Introduction to Query Processing and Query Optimization, Concurrency Control, and Recovery Techniques.

Reference Texts and E-Resources

Fundamentals of Database Systems 6th Edition - Ramez Elmasri & Navathe

Database System Concepts 6th edition - Silberschatz & Korth

An Introduction to Database Systems, By C.J.Date, Addison Wesley

Database Management Systems, By R. Ramakrishnan, McGraw-Hill

Elmasri and Navathe Slides

Silberschatz, Korth and Sudarshan Slides

Lecture Slides (Extended and Modified version of Elmasri and Navathe):
ch1-korth, ENCh01, ENCh02, ENCh03, ENCh04a, ENCh05, ENCh07, ENCh23, SQL-I, SQL-II

Lab Assignments

Information Retrieval and Web Mining :: Course Content & online available resources

Course Content

Information Retrieval Concepts and Models, Introduction to World Wide Web, Hypertext Data, Search Engines, Crawling the Web.

Indexing and Search: Boolean Queries and Inverted Index, Relevance ranking, Similarity search, Web directories, Combining Searching with Browsing,  Meta-searchers, Dynamic Search and Software Agents.

Clustering and Classification, Social, Semantic Web.

Reference Texts and E-Resources

An Introduction to Information Retrieval, By C.D. Manning, P. Raghvan and H. Schutze, Cambridge University Press

Web Data Mining Exploring Hyperlinks Contents and Usage Data: Bing Liu, Springer

Mining the Web Discovering knowledge from hypertext data: Soumen Chakrabarti IITB, Elsevier

Search Engines: Information Retrieval in Practice, By B. Croft, D. Metzler, T. Strohman, Addison Wesley

SemanticWebNotes

Managing and Mining Graph Data, By Charu C. Aggarwal, H. Wang

Tutorial: Web Information Retrieval, By Monika Henzinger

Slides: Web Mining : Accomplishments & Future Directions By Jaideep Srivastava