B.E. COMPUTER SCIENCE AND ENGINEERING SEMESTER VI /6 SYLLABUS

ANNA UNIVERSITY CHENNAI:: CHENNAI 600 025
CURRICULUM 2004
B.E. COMPUTER SCIENCE AND ENGINEERING SEMESTER VI

SEMESTER VI
(Applicable to the students admitted from the Academic year 2006 – 2007 onwards)

Code No.	Course Title	L	T	P	M
THEORY
CS1351	Artificial Intelligence	3	0	0	100
CS1352	Principles of Compiler Design	3	1	0	100
CS1353	Software Engineering	3	0	0	100
CS1354	Graphics and Multimedia	3	0	0	100
MA1251	Numerical Methods	3	1	0	100
	Elective – I	3	0	0	100
GE1352	Communication Skills Laboratory **	0	0	4	100
PRACTICAL
CS1355	Graphics and Multimedia Lab	0	0	3	100
CS1356	Compiler Design Lab	0	0	3	100

** Offered in VI semester for B.E. (CSE), B.E. (ECE) & B.E. (Mech.) only.

CS1351 ARTIFICIAL INTELLIGENCE 3 0 0 100

AIM
Artificial Intelligence aims at developing computer applications, which encompasses perception, reasoning and learning and to provide an in-depth understanding of major techniques used to simulate intelligence.

OBJECTIVE
• To provide a strong foundation of fundamental concepts in Artificial Intelligence
• To provide a basic exposition to the goals and methods of Artificial Intelligence
• To enable the student to apply these techniques in applications which involve perception, reasoning and learning.

UNIT I INTRODUCTION 8
Intelligent Agents – Agents and environments - Good behavior – The nature of environments – structure of agents - Problem Solving - problem solving agents – example problems – searching for solutions – uniformed search strategies - avoiding repeated states – searching with partial information.

UNIT II SEARCHING TECHNIQUES 10
Informed search and exploration – Informed search strategies – heuristic function – local search algorithms and optimistic problems – local search in continuous spaces – online search agents and unknown environments - Constraint satisfaction problems (CSP) – Backtracking search and Local search for CSP – Structure of problems - Adversarial Search – Games – Optimal decisions in games – Alpha – Beta Pruning – imperfect real-time decision – games that include an element of chance.

UNIT III KNOWLEDGE REPRESENTATION 10
First order logic – representation revisited – Syntax and semantics for first order logic – Using first order logic – Knowledge engineering in first order logic - Inference in First order logic – prepositional versus first order logic – unification and lifting – forward chaining – backward chaining - Resolution - Knowledge representation - Ontological Engineering - Categories and objects – Actions - Simulation and events - Mental events and mental objects

UNIT IV LEARNING 9
Learning from observations - forms of learning - Inductive learning - Learning decision trees - Ensemble learning - Knowledge in learning – Logical formulation of learning – Explanation based learning – Learning using relevant information – Inductive logic programming - Statistical learning methods - Learning with complete data - Learning with hidden variable - EM algorithm - Instance based learning - Neural networks - Reinforcement learning – Passive reinforcement learning - Active reinforcement learning - Generalization in reinforcement learning.

UNIT V APPLICATIONS 8
Communication – Communication as action – Formal grammar for a fragment of English – Syntactic analysis – Augmented grammars – Semantic interpretation – Ambiguity and disambiguation – Discourse understanding – Grammar induction - Probabilistic language processing - Probabilistic language models – Information retrieval – Information Extraction – Machine translation.

TOTAL : 45
TEXT BOOK
1. Stuart Russell, Peter Norvig, “Artificial Intelligence – A Modern Approach”, 2nd Edition, Pearson Education / Prentice Hall of India, 2004.
REFERENCES
1. Nils J. Nilsson, “Artificial Intelligence: A new Synthesis”, Harcourt Asia Pvt. Ltd., 2000.
2. Elaine Rich and Kevin Knight, “Artificial Intelligence”, 2nd Edition, Tata McGraw-Hill, 2003.
3. George F. Luger, “Artificial Intelligence-Structures And Strategies For Complex Problem Solving”, Pearson Education / PHI, 2002.

CS1352 PRINCIPLES OF COMPILER DESIGN 3 1 0 100

AIM
At the end of the course the student will be able to design and implement a simple compiler.

OBJECTIVES
• To understand, design and implement a lexical analyzer.
• To understand, design and implement a parser.
• To understand, design code generation schemes.
• To understand optimization of codes and runtime environment.

UNIT I INTRODUCTION TO COMPILING 9
Compilers – Analysis of the source program – Phases of a compiler – Cousins of the Compiler – Grouping of Phases – Compiler construction tools – Lexical Analysis – Role of Lexical Analyzer – Input Buffering – Specification of Tokens.

UNIT II SYNTAX ANALYSIS 9
Role of the parser –Writing Grammars –Context-Free Grammars – Top Down parsing – Recursive Descent Parsing – Predictive Parsing – Bottom-up parsing – Shift Reduce Parsing – Operator Precedent Parsing – LR Parsers – SLR Parser – Canonical LR Parser – LALR Parser.

UNIT III INTERMEDIATE CODE GENERATION 9
Intermediate languages – Declarations – Assignment Statements – Boolean Expressions – Case Statements – Back patching – Procedure calls.

UNIT IV CODE GENERATION 9
Issues in the design of code generator – The target machine – Runtime Storage management – Basic Blocks and Flow Graphs – Next-use Information – A simple Code generator – DAG representation of Basic Blocks – Peephole Optimization.

UNIT V CODE OPTIMIZATION AND RUN TIME ENVIRONMENTS 9
Introduction– Principal Sources of Optimization – Optimization of basic Blocks – Introduction to Global Data Flow Analysis – Runtime Environments – Source Language issues – Storage Organization – Storage Allocation strategies – Access to non-local names – Parameter Passing.

TUTORIAL 15

TOTAL : 60
TEXT BOOK
1. Alfred Aho, Ravi Sethi, Jeffrey D Ullman, “Compilers Principles, Techniques and Tools”, Pearson Education Asia, 2003.
REFERENCES
1. Allen I. Holub “Compiler Design in C”, Prentice Hall of India, 2003.
2. C. N. Fischer and R. J. LeBlanc, “Crafting a compiler with C”, Benjamin Cummings, 2003.
3. J.P. Bennet, “Introduction to Compiler Techniques”, Second Edition, Tata McGraw-Hill, 2003.
4. Henk Alblas and Albert Nymeyer, “Practice and Principles of Compiler Building with C”, PHI, 2001.
5. Kenneth C. Louden, “Compiler Construction: Principles and Practice”, Thompson Learning, 2003

CS1353 SOFTWARE ENGINEERING 3 0 0 100

AIM
To introduce the methodologies involved in the development and maintenance of software (i.e) over its entire life cycle.

OBJECTIVE
To be aware of
• Different life cycle models
• Requirement dictation process
• Analysis modeling and specification
• Architectural and detailed design methods
• Implementation and testing strategies
• Verification and validation techniques
• Project planning and management
• Use of CASE tools

UNIT I SOFTWARE PROCESS 9
Introduction –S/W Engineering Paradigm – life cycle models (water fall, incremental, spiral, WINWIN spiral, evolutionary, prototyping, object oriented) - system engineering – computer based system – verification – validation – life cycle process – development process –system engineering hierarchy.

UNIT II SOFTWARE REQUIREMENTS 9
Functional and non-functional - user – system –requirement engineering process – feasibility studies – requirements – elicitation – validation and management – software prototyping – prototyping in the software process – rapid prototyping techniques – user interface prototyping -S/W document. Analysis and modeling – data, functional and behavioral models – structured analysis and data dictionary.

UNIT III DESIGN CONCEPTS AND PRINCIPLES 9
Design process and concepts – modular design – design heuristic – design model and document. Architectural design – software architecture – data design – architectural design – transform and transaction mapping – user interface design – user interface design principles. Real time systems - Real time software design – system design – real time executives – data acquisition system - monitoring and control system. SCM – Need for SCM – Version control – Introduction to SCM process – Software configuration items.

UNIT IV TESTING 9
Taxonomy of software testing – levels – test activities – types of s/w test – black box testing – testing boundary conditions – structural testing – test coverage criteria based on data flow mechanisms – regression testing – testing in the large. S/W testing strategies – strategic approach and issues - unit testing – integration testing – validation testing – system testing and debugging.

UNIT V SOFTWARE PROJECT MANAGEMENT 9
Measures and measurements – S/W complexity and science measure – size measure – data and logic structure measure – information flow measure. Software cost estimation – function point models – COCOMO model- Delphi method.- Defining a Task Network – Scheduling – Earned Value Analysis – Error Tracking - Software changes – program evolution dynamics – software maintenance – Architectural evolution. Taxonomy of CASE tools.

TOTAL : 45
TEXT BOOK
1. Roger S.Pressman, Software engineering- A practitioner’s Approach, McGraw-Hill International Edition, 5th edition, 2001.
REFERENCES
1. Ian Sommerville, Software engineering, Pearson education Asia, 6th edition, 2000.
2. Pankaj Jalote- An Integrated Approach to Software Engineering, Springer Verlag, 1997.
3. James F Peters and Witold Pedryez, “Software Engineering – An Engineering Approach”, John Wiley and Sons, New Delhi, 2000.
4. Ali Behforooz and Frederick J Hudson, “Software Engineering Fundamentals”, Oxford University Press, New Delhi, 1996.

CS1354 GRAPHICS AND MULTIMEDIA 3 0 0 100

AIM
To impart the fundamental concepts of Computer Graphics and Multimedia.

OBJECTIVES
• To study the graphics techniques and algorithms.
• To study the multimedia concepts and various I/O technologies.
• To enable the students to develop their creativity

UNIT I OUTPUT PRIMITIVES 9
Introduction - Line - Curve and Ellipse Drawing Algorithms – Attributes – Two-Dimensional Geometric Transformations – Two-Dimensional Clipping and Viewing.

UNIT II THREE-DIMENSIONAL CONCEPTS 9
Three-Dimensional Object Representations – Three-Dimensional Geometric and Modeling Transformations – Three-Dimensional Viewing – Color models – Animation.

UNIT III MULTIMEDIA SYSTEMS DESIGN 9
An Introduction – Multimedia applications – Multimedia System Architecture – Evolving technologies for Multimedia – Defining objects for Multimedia systems – Multimedia Data interface standards – Multimedia Databases.

UNIT IV MULTIMEDIA FILE HANDLING 9
Compression & Decompression – Data & File Format standards – Multimedia I/O technologies - Digital voice and audio – Video image and animation – Full motion video – Storage and retrieval Technologies.

UNIT V HYPERMEDIA 9
Multimedia Authoring & User Interface – Hypermedia messaging - Mobile Messaging – Hypermedia message component – Creating Hypermedia message – Integrated multimedia message standards – Integrated Document management – Distributed Multimedia Systems.

TOTAL : 45
TEXT BOOKS
1. Donald Hearn and M.Pauline Baker, “Computer Graphics C Version”, Pearson Education, 2003.
(UNIT I : Chapters 1 to 6; UNIT 2: Chapter 9 – 12, 15, 16)
2. Prabat K Andleigh and Kiran Thakrar, “Multimedia Systems and Design”, PHI, 2003.
(UNIT 3 to 5)
REFERENCES
1. Judith Jeffcoate, “Multimedia in practice technology and Applications”, PHI, 1998.
2. Foley, Vandam, Feiner, Huges, “Computer Graphics: Principles & Practice”, Pearson Education, second edition 2003.

MA1251 NUMERICAL METHODS 3 1 0 100

AIM
With the present development of the computer technology, it is necessary to develop efficient algorithms for solving problems in science, engineering and technology. This course gives a complete procedure for solving different kinds of problems occur in engineering numerically.

OBJECTIVES
At the end of the course, the students would be acquainted with the basic concepts in numerical methods and their uses are summarized as follows:

• The roots of nonlinear (algebraic or transcendental) equations, solutions of large system of linear equations and eigenvalue problem of a matrix can be obtained numerically where analytical methods fail to give solution.
• When huge amounts of experimental data are involved, the methods discussed on interpolation will be useful in constructing approximate polynomial to represent the data and to find the intermediate values.
• The numerical differentiation and integration find application when the function in the analytical form is too complicated or the huge amounts of data are given such as series of measurements, observations or some other empirical information.
• Since many physical laws are couched in terms of rate of change of one/two or more independent variables, most of the engineering problems are characterized in the form of either nonlinear ordinary differential equations or partial differential equations. The methods introduced in the solution of ordinary differential equations and partial differential equations will be useful in attempting any engineering problem.

UNIT I SOLUTION OF EQUATIONS AND EIGENVALUE PROBLEMS 9+3
Linear interpolation methods (method of false position) – Newton’s method – Statement of Fixed Point Theorem – Fixed point iteration: x=g(x) method – Solution of linear system by Gaussian elimination and Gauss-Jordon methods- Iterative methods: Gauss Jacobi and Gauss-Seidel methods- Inverse of a matrix by Gauss Jordon method – Eigenvalue of a matrix by power method.

UNIT II INTERPOLATION AND APPROXIMATION 9+ 3
Lagrangian Polynomials – Divided differences – Interpolating with a cubic spline – Newton’s forward and backward difference formulas.

UNIT III NUMERICAL DIFFERENTIATION AND INTEGRATION 9+ 3

Derivatives from difference tables – Divided differences and finite differences –Numerical integration by trapezoidal and Simpson’s 1/3 and 3/8 rules – Romberg’s method – Two and Three point Gaussian quadrature formulas – Double integrals using trapezoidal and Simpson’s rules.

UNIT IV INITIAL VALUE PROBLEMS FOR ORDINARY DIFFERENTIAL EQUATIONS 9+ 3
Single step methods: Taylor series method – Euler and modified Euler methods – Fourth order Runge – Kutta method for solving first and second order equations – Multistep methods: Milne’s and Adam’s predictor and corrector methods.

UNIT V BOUNDARY VALUE PROBLEMS IN ORDINARY AND PARTIAL DIFFERENTIAL EQUATIONS 9+ 3
Finite difference solution of second order ordinary differential equation – Finite difference solution of one dimensional heat equation by explicit and implicit methods – One dimensional wave equation and two dimensional Laplace and Poisson equations.

TUTORIAL 15

TOTAL : 60
TEXT BOOKS
1. Gerald, C.F, and Wheatley, P.O, “Applied Numerical Analysis”, Sixth Edition, Pearson Education Asia, New Delhi, 2002.
2. Balagurusamy, E., “Numerical Methods”, Tata McGraw-Hill Pub.Co.Ltd, New Delhi, 1999.

REFERENCES
1. Kandasamy, P., Thilagavathy, K. and Gunavathy, K., “Numerical Methods”, S.Chand Co. Ltd., New Delhi, 2003.
2. Burden, R.L and Faires, T.D., “Numerical Analysis”, Seventh Edition, Thomson Asia Pvt. Ltd., Singapore, 2002.

CS1355 GRAPHICS AND MULTIMEDIA LAB 0 0 3 100

1. To implement Bresenham’s algorithms for line, circle and ellipse drawing
2. To perform 2D Transformations such as translation, rotation, scaling, reflection and sharing.
3. To implement Cohen-Sutherland 2D clipping and window-viewport mapping
4. To perform 3D Transformations such as translation, rotation and scaling.
5. To visualize projections of 3D images.
6. To convert between color models.
7. To implement text compression algorithm
8. To implement image compression algorithm
9. To perform animation using any Animation software
10. To perform basic operations on image using any image editing software

CS1356 COMPILER DESIGN LAB 0 0 3 100
1 & 2 Implement a lexical analyzer in “C”.
3. Use LEX tool to implement a lexical analyzer.
4. Implement a recursive descent parser for an expression grammar that generates arithmetic expressions with digits, + and *.
5. Use YACC and LEX to implement a parser for the same grammar as given in problem
6. Write semantic rules to the YACC program in problem 5 and implement a calculator that takes an expression with digits, + and * and computes and prints its value.
7 & 8. Implement the front end of a compiler that generates the three address code for a simple language with: one data type integer, arithmetic operators, relational operators, variable declaration statement, one conditional construct, one iterative construct and assignment statement.
9 &10. Implement the back end of the compiler which takes the three address code generated in problems 7 and 8, and produces the 8086 assembly language instructions that can be assembled and run using a 8086 assembler. The target assembly instructions can be simple move, add, sub, jump. Also simple addressing modes are used