PAPER II
SECTION-A
Total Marks:100

1. Theory of Automata and Formal Languages.
Finite State Models: Language definitions preliminaries, Regular expressions/Regular languages, Finite automatas (FAs), Transition graphs
(TGs),NF As, kleene's theorem, Transducers (automata with output), Pumping
lemma and non regular language Grammars and PDA: Context free grammars,
Derivations, derivation trees and ambiguity, Simplifying CFLs , Normal form
grammars and parsing, Push-down Automata, Pumping lemma and non-context
free languages, Decidability, Chomsky's hierarchy of grammars, Turing
Machines Theory: Turing machines, Post machine, Variations on 1M, 1M
encoding, Universal Turing Machine, Context sensitive Grammars, Defining
Computers by TMs.
2 Compiler Theory & Design
Compiler techniques and methodology. Organization of compilers. Lexical and
syntax analysis. Parsing techniques. Object code generation and optimization,
detection and recovery from errors. Comparison between compilers and
interpreters.
3. Numerical Methods
Mathematical Preliminaries, Solution of Equations in one variable, Interpolation
and Polynomial Approximation, Numerical Differentiation and Integration, Initial
Value Problems for Ordinary Differential Equations, Direct Methods for Solving
Linear Systems, Iterative Techniques in Matrix Algebra, Solution of non-linear
equations, Approximation Theory, Eigenvalues and Eigenvector computation.

SECTION -B

I. Data Base Systems
Basic database concepts, Entity Relationship modelling, Relational data model
and algebra, Structured Query language, RDBMS; Database design, functional
dependencies and normal forms, Transaction processing and optimization
concepts, concurrency control and recovery techniques, Database recovery
techniques, Database security and authorization. Small Group Project
implementing a database. Physical database design: Storage and file structure,
indexed files, hashed files, signature files, b-trees, files with dense index, files
with variable length records, database efficiency and tuning Data Warehousing
and Data Mining, Emerging Database Technologies and Applications.

2. Software Engineering
Software Engineering, Process Models, Software verification and validation.
Techniques are introduced to evaluate software correctness, efficiency,
performance and reliability, integration of these techniques into a verification and
validation plan. Technical reviews, software testing, programme verification,
prototyping, and requirement tracing. Attitude of industry toward reliability and performance.

SECTION -C

1. Artificial Intelligence
Introduction to Common Lisp. AI classical systems: General Problem Solver,
rules, simple search, means-ends analysis. ElIZA, pattern matching, rule based
translators, OPS-5. Knowledge Representation: Natural language, rules,
productions, predicate logic, semantic networks, frames, objects, scripts.
Searching, Depth first search, breadth first search, best first search, hill climbing,
min-max search. Symbolic Mathematics: student solving algebra problems,
translating English equations, solving algebraic equations, simplification rules, rewrite
rules, meta-rules, Macsyma, PRESS, ATLAS. Logic Programming:
Resolution, unification, horn-clause logic, Prolog, Prolog programming. Sample
case studies of shells and Knowledge Based Systems. A brief appreciation of
state of the art computational techniques like neural networks, genetic algorithm,
fuzzy sets.

2. Computer Graphics
Graphics hardware, Fundamental algorithms, Applications of graphics. Interactive
graphics programming -graph plotting, windows and clipping, and segmentation.
Programming raster display systems, panning and zooming. Raster algorithms
and software Scan-Converting lines, characters and circles. Region filling and
clipping. Two and three dimensional imaging geometry and transformations.
Curve and surface design, rendering, shading, colour and animation.