Monday, July 25, 2011

Cusat Compleat Syllabus

B. Tech. Degree in Computer Science and Engineering
Scheme Of Examinations
Course No Subject No of Hrs
per week Internal University Total
SEMESTER I&II (common to all)
E/SE 101
Engineering Mathematics I 2 50 100 150
E/SE 102
Engineering Mathematics II 2 50 100 150
E/SE 103
Engineering Physics 2 50 100 150
E/SE 104
Engineering Chemistry 2 50 100 150
E/SE 105
Engineering Mechanics 3 50 100 150
E/SE 106
Engineering Graphics 4 50 100 150
E/SE 107
Fundamentals of Engineering I 2 50 100 150
E/SE 108
Fundamentals of Engineering II 2 50 100 150
E/SE CS 109
Computer Fundamentals 3 50 100 150
E/SE 110
Humanities 2 50 100 150
E/SE 111
Computer Programming lab 3 100 100
E/SE 112
Workshops 3 100 100
Total 30 700 1000 1700
E/SE 301
Engineering Mathematics III 5 50 100 150
/ME/MRE 302
Electrical Technology 4 50 100 150
CS/IT 303 Discrete Mathematical
Structures 5 50 100 150
I 304 Digital Electronics 5 50 100 150
CS 305 Electronic Circuits 5 50 100 150
CS 306 Electronics Circuits Lab 3 75 75 150
Electrical Lab 3 75 75 150
Total 30 400 650 1050
Engineering Mathematics IV 5 50 100 150
CS 402 Principles of Programming
Languages 5 50 100 150
CS 403 Automata Languages and
Computation. 5 50 100 150
CS 404 Computer Architecture and
Organization 4 50 100 150
CS/IT 405 Data Structures and Algorithms 5 50 100 150
I 406 Digital Electronics Lab 3 75 75 150
CS/IT 407 Data Structures Lab 3 75 75 150
Total 30 400 650 1050
CS 501 Language Processors 5 50 100 150
CS/IT 502 Software Engineering 5 50 100 150
CS 503 Microprocessors 5 50 100 150
CS 504 Data Communication 4 50 100 150
CS/IT 505 Data Base Management Systems 5 50 100 150
I 506 Microprocessor Lab 3 75 75 150
CS 507 Language Processors Lab 3 75 75 150
Total 30 400 650 1050
CS/EE/EI 601 Digital Signal Processing 5 50 100 150
CS/IT 602 Operating systems 5 50 100 150
CS 603 Computer Graphics 4 50 100 150
CS 604 Microprocessor System design 5 50 100 150
Control Systems Engineering 5 50 100 150
CS 606 System Programming &
Hardware Lab 3 75 75 150
CS 607 Minor Project 3 150 150
Total 30 475 575 1050
I/IT 701 Computer Networks 5 50 100 150
CS 702 Artificial Intelligence 4 50 100 150
CS 703 Analysis & Design of
Algorithms 5 50 100 150
CS 704 Advanced Architecture &
Parallel Processing 4 50 100 150
CS 705 Elective I 4 50 100 150
CS 706 Network and Operating systems
Lab 3 75 75 150
CS 707 Computer Graphics Lab 3 75 75 150
CS 708 Seminar 2 50 50
CS/IT 705 B
705 C
CS 705 D
Digital Image Processing
Information Retrieval
Artificial Neural Networks
Advanced Digital System
Total 30 450 650 1100
CS 801 Security in Comput ing 5 50 100 150
CS 802 Distributed Computing 5 50 100 150
Industrial Organisation &
Management 5 50 100 150
CS 804 Elective II 5 50 100 150
CS 805 Project Work 10 300 300
CS 806 Viva Voce 100 100
CS 804 A
CS/EB/IT 804 B
CS 804 C
CS 804 D
CS/EC/IT 804 E
Embedded Systems
Software Architecture
Algorithms & Complexity
Intellectual Property Rights
Total 30 500 500 1000
CE/CS/EB/EC /EE/EI/IT/ME/MRE/SE 301Engineering Mathematics III
Module I
Fourier series and Fourier integrals : Periodic functions, Euler formulae for Fourier coefficients,
functions having arbitrary period, even and odd functions, half range expansions, Fourier integral,
Fourier cosine and sine transformations, linearity property, transform of derivatives, convolution
theorem (no proof)
Gamma and Beta functions, error functions - definitions and simple properties.
Module II
Special functions: Legendre polynomial, Rodrigue's formula- generation function, recurrence formula
for Pn (x), orthogonality. Bessel function, Jn(x)- recurrence formula, general function, orthoganilty.
Module III
Partial differential equations : Solutions of equations of the form F(p, q) = 0, F(x,p,q)=0, F(y,p,q)=0,
F(z,p,q)=0, F1(x,p) = F2 (y,q), Lagrange’s form Pp+Qq = R.
Vibrating string: one dimensional wave equation, D’Alembert’s solution, solution by the method of
separation of variables. One dimensional heat equation, solution of the equation by the method of
separation of variables, solutions of Laplace’s equation over a rectangular region and a circular region by
the method of separation of variables.
Module IV
Probability and Statistics : Probability distributions : random variables (discrete & continuous),
probability density, mathematical expectation, mean and variance of a probability distribution, binomial
distribution, Poisson approximation to the binomial distribution, uniform distribution , normal
Curve fitting : method of least squares, correlation and regression, lines of regression.
Module V
Sampling distributions : population and samples, the sampling distribution of the mean
(? known), the sampling distribution of the mean (? unknown), the sampling distribution of the
variance, point estimation, interval estimation, tests of hypotheses, null hypotheses and significance
tests, hypothesis concerning one mean, type I and type II errors, hypotheses concerning two means.
The estimation of variances: Hypotheses concerning one variance - Hypotheses concerning two
Note:- Treatment of the topics under Modules IV, V should be oriented towards application of statistical
techniques to problems in real life.
1) Ervin Kreyszig : Advanced Engineering Mathematics, Wiley Eastern
2) Potter, Goldberg : Mathematical Methods, Prentice - Hall
3) Churchill R.V. : Fourier series and Boundary Value Problems - McGraw Hill
4) Irvrin Miller & John E. Freind : Probability and statistics for Engineers , Prentice Hall of India.
5) Bowker and Lieberman : Engineering Statistics Prentice - Hall
6) Kirk - Patrick : Introductory statistics and probability for engineering science and
technology , Prentice -Hall
7) Parzen E : Modern Probability Theory and its Applications, Wiley estern.
CS/EB/EC/EI/IT/ME/MRE 302 Electrical Technology
Module I
Transformers: working principles and elementary theory of an ideal transformer, Constructional
features of single phase transformer, emf equation, turns ratio, vector diagram , equivalent circuit,
impedance transformation, transformer losses, flux leakage, efficiency, open circuit and short circuit
test, load test. Auto transformer - working principle and saving copper, basic idea of current transformer
and potential transformer, distribution and power transformer, applications, standard rating, IS
Module II
Basic principles of electrical machines: Concepts of motoring and generating action,
DC machines- Main constructional features, principles of operation, types of generators, emf equation,
characteristics, applications, armature reaction and commutation, types of motors, torque, speed, and
power, characteristics, applications, starting losses, and efficiency, speed control, testing, load test of dc
Module III
AC Machines: Alternator- rotating field, speed and frequency, effect of distribution of winding, coil
span, characteristics, emf equation, losses and efficiency, regulation (emf method only), applications,
synchronous motor- principle of operation, over excited and under excited, starting, applications,
synchronous capacitor.
Module IV
Induction Motor: Three phase induction motor, principles of operation, constructional features of
squirrel cage and slip ring motors, torque-slip characteristics, starting, speed control, losses and
Single phase induction motor: Principle of operation, types of single phase induction motors
Module V
Generation, transmission & distribution of electrical energy:
Different methods of power generation- thermal, hydro-electric, nuclear, diesel, gas turbine stations
(general idea only), electrical equipments in power stations, concept of bus bar, load dispatching,
methods of transmission, transmission lines, overhead lines and insulators, corona and skin effect of DC
& AC distribution, substation (elementary idea only)
1) Electrical Machines : By F.S.Bimbra, Khanna publications.
2) Advanced Electrical Technology : By H.Cotton, Wheeler publications.
3) Electrical Machines : Nagarath & Kothari, (TMH)
CS/IT 303 Discrete Mathematical Structures
Module I
Introduction to set theory –sets and subsets – operation on sets – sequences – characteristic functions –
Introduction to logic propositions and logic operations – methods of proof – mathematical induction.
Counting – permutations and combinations – elements of probability
Module II
Relations and Digraphs – properties of relations – paths in relation and digraphs – Equivalence relations
and partitions – operations on relations. Functions – composition of functions – functions for Computer
Module III
Introduction to graph theory – graphs – Eulerian paths and circuits- Hamiltonian Path and circuits -
coloring of graphs - trees – minimal spanning trees
Module V
Algebraic Systems – Semi groups and monoids. Groups – subgroups and homomorphism – group codes
– error correcting codes.
Module VI
Partially ordered sets- Hasse diagram – isomorphism – extremal elements – lattice- properties of lattices.
1) J.P.Tremblay, R. Manohar, “Discrete mathematical Structures with Applications to Computer
Science, McGrawHill
2) Bernard Kolman,, “Discrete Mathematical Structures”, 3rd ed., Prentice Hall India, New
Delhi, 1999
3) John Truss, "Discrete Mathematical Structures for Computer Science", Addison Wesely,
4) Seymour Lipchutz, Marc Lipson, "Discrete Mathematics", Tata McGraw-Hill
CS /EB/EC/EE /EI304 Digital Electronics
Module I
Number system and codes: Binary, Octal, and Hexa-decimal number systems - Binary arithmetic,
Binary code, Excess - 3 code Gray error detection and correction - Boolean algebra - Minimization of
Boolean function using Karnaugh Map and Quine - Mclusky methods - Formation of switching
functions from word statements, realisation using NAND, NOR & X - OR Gates. Combinational
circuits- multiplexer demultiplexer decoder encoder
Module II
Sequential circuits: Flip-flops - RS, JK & T & D flip- flops, shift registers - counters - Asynchronous
and synchronous counters, Up-Down counter, Modulo counter, Ring counter, Johnson counter -
sequence generators - Analysis of sequential circuits - state table and diagrams
Arithmetic circuits: Half adder, Full adder, Subtractor, Serial and parallel addition - Carry look ahead
adder - Binary multiplication and division - Multivibrators - Monostable and astable multivibrators
using discrete gates.
Memories - ROM, RAM, EPROM, Programmable logic array, devices - Basic ideas - PLD architecture -
PAL and PLA - Programming examples with software tools - Study of PAL 22v10
Logic families: DCTL, RTL, DTL, TTL, ECL, CMOS - Tri-state logic - specification and transfer
characteristics of basic TTL interfaces, - Standard logic levels - Current and voltage parameters - fan in
and fan out - Propagation delay, integrated circuit modules, noise consideration- interfacing of CMOS to
TTL and interfacing of TTL to CMOS
1) Taub & Schilling, “Digital Integrated Electronics”, Mc Graw Hill
2) Samuel C Lee, ”Digital Circuits and Logic Design”, Prentice Hall
3) A P Malvino,”Digital Computer Electronics”, Tata Mc Graw Hill
4) Morris & Miller, “Design with TTL Integrated Circuit”, Mc Graw Hill
5) Peatman , ”Digital Hardware Design”, Mc Graw Hill
6) Ronald J Tocci , “Digital Systems, Principles and Applications “, Prentice Hall
7) Lloyd T L, ”Digital Fundamentals”, Universal, N. Delhi
8) Mercins, ”Switching Circuits”, Prentice Hall
9) MOS-LSI Circuits, Publication of Texas Instruments
10) Douglas V Hall, “Digital Circuits and Systems”, Mc Graw Hill
11) R P Jain, Principles of Digital Electronics
CS 305 Electronic Circuits
Module I
Semiconductor devices PN junction- barrier potential, biasing PN junction, - principle of zener and
avalanche diodes - photodiodes -LDR - tunnel diode -PIN diode - varactor diode. Bipolar junction
transistors - NPN, PNP types, current components in transistors Transistor configurations -
Characteristics - current amplification factors - relations between alpha & beta - comparison - Field
effect transistors: JFET - basic structures - principle of operation - basic principles & characteristics of
phototransistors - UJT. & MOSFET.
Module II
Small Signal amplifiers –- Biasing techniques - stabilization of operating point - h-parameters - CE RC
coupled amplifier - concept of load lines- frequency response of RC coupled amplifier -- frequency
analysis of R C coupled amplifier - lower cut-off frequency - upper cut-off frequency - 3 db bandwidth
Multistage Amplifiers& Feed-back amplifiers: Negative and positive feedback - Different types Pulse
circuits - pulse characteristics - Pulse shaping using RC circuits - Differentiating and integrating circuits
- clipping and clamping circuits - Transistor as a switch– Multivibrators.
Module III
Power amplifier -classification - class A, class B, Class AB and class C - Transformer coupled & -
Transformerless class AB push-pull Power amplifier - complementary symmetry power amplifier –
Harmonic distortion – Heat sinks. Principle of sinusoidal oscillators - Bark Hausen criteria - RC - LC,
Crystal oscillators
Module IV
Difference amplifier. Common mode and difference mode operation - CMRR - merits and demerits -
use of constant current source, drift and offset problems - Operational amplifier block diagram -
Characteristics of ideal op-amps - Linear circuits using op-amp - -inverting amplifier, non-inverting
amplifier instrumentation amplifier, adder, substractor, log and antilog amplifier, integrator,
differentiator, peak detector, precision rectifier. Nonlinear circuits using op-amp-comparators,
multivibrators, function generators - Active filters.
1) Millman & Halkias, ”Electronic Devices & Circuits”
2) Bapat K N, ”Electronic Devices & Circuits”
3) Allan Mottorshed, ” Electronic Devices & Circuits”
4) Millman & Halkias, ”Integrated Electronics”
5) Boylestead & Neshelsky,”Electronic Devices & Circuits
6) Schilling &Belove “Electronic Circuits, Discrete & Integrated” TMH
7) Gayakwad, “ Op-Amp and Integrated Circuit”
8) Clayton,” Operational Amplifiers”
9) Sergio Franco “Design with Op amps & Analog Integrated Circuits” MH International
10) Theodore F.Bogart Electronic Devices & Circuits Universal Book Stall, New Delhi.
CS 306 Electronics Circuits Lab
1. Study of - Multimeter, Signal generators, CRO etc. and measurement of electrical quantities
2. Testing of Passive and Active components - Resistors, Capacitors, inductors, Transformers,
diodes, Transistors, etc.
3. Characteristics of Active devices
4. Rectifying circuits
i) HW rectifier
ii) FW rectifier
iii) FW Bridge rectifier
iv) Filter circuits - Capacitor filter, inductor filter and Pi section filter
(Measurement of ripple factor, maximum ratings of the devices)
5. Differentiating circuit and integrating circuit.
6. Clipping & Clamping circuits.
7. Amplifying circuits Simple common emitter amplifier configuration - gain and
8. Oscillators –
9. Multivibrators - Astable only.
10. Circuits using OP- Amps
CS /EB/EC /EI 307 Electrical Lab
Compulsory experiments
1. (a) Preliminary study of AC and DC Power supplies in the laboratory.
(b) Study of instruments and their mode of use
2. Open circuit characteristics of
(a) Self excited generator
(b) Separately excited generator.
3. Load characteristic of compound generator
4. Load characteristic of shunt generator
5. Study of face plate starter and starting of DC motors
6. Load characteristics of DC series motor.
7. Swinburn’s test
8. Polarity and transformation ratio test on single phase transfer.
9. O.C & SC test on single phase transformer - equivalent circuit
10. Load rest on single phase transformer.
11. Study of starting methods of squirrel cage and slip ring induction motor.
12. Load test on slip ring induction motor and study of characteristics.
Optional Experiments
1. Study of single phase motors.
2. Load test of DC shunt motor.
3. Poly phase connection of single phase transformer.
4. Load test on squirrel cage induction motor
5. Study of alternators.
CEA/CS/EB/EC/EE/EI/IT/ME/SE 401Engineering Mathematics IV
Module I
Complex Analytic functions and conformal mapping: curves and regions in the complex plane,
complex functions, limit, derivative, analytic function, Cauchy - Riemann equations, elementary
complex functions such as powers, exponential function, logarithmic, trigonometric and hyperbolic
Conformal mapping: Linear fractional transforma tions, mapping by elementary functions like ez, sin z,
cos z, sin hz, and cos hz, Schwarz - Christoffel transformation.
Module II
Complex integration: Line integral, Cauchy's integral theorem, Cauchy's integral formula, Taylor's
series, Laurent's series, residue theorem, evaluation of real integrals using integration around unit circle,
around the semi circle, integrating contours having poles, on the real axis.
Module III
Numerical Analysis: Errors in numerical computations, sources of errors, significant digits. Numerical
solution of algebraic and transcendental equations: bisection method, regula falsi method, Newton -
Raphson method, method of iteration, rates of convergence of this method,
Solution of linear system of algebraic equations: exact methods, Gauss elimination method, iteration
methods, Gauss-Jacobi method.
Polynomial interpolation: Lagrange interpolation polynomial, divided differences, Newton’s devided
differences interpolation polynomial.
Module IV
Finite differences: Operators ? ,? ,? , and ? , Newton’s forward and backward differences interpolation
polynomials, central differences, Stirlings central differences interpolation polynomial.
Numerical differentiation: Formulae for derivatives in the case of equally spaced points.
Numerical integration: Trapezoidal and Simpson’s rules, compounded rules, errors of interpolation and
integration formulae. Gauss quadrature formulae (No derivation for 2 point and 3 point formulae)
Module V
Numerical solution of ordinary differential equations: Taylor series method, Euler’s method,
modified Euler’s method, Runge-Kutta formulae 4th order formula,
Solution of linear difference equations with constant co-efficients: Numerical solution of boundary
value problems, methods of finite differences, finite differences methods for solving Laplace’s equation
in a rectangular region, finite differences methods for solving the wave equation and heat equation.
1) Ervin Kreyszig: Advanced Engineering Mathematics, Wiley Eastern
2) S.S.Sastry: Introductory Method of Numerical Analysis, Prentice -Hall of India
3) Ralph G. Stanton: Numerical Methods for Science and Engg. Prentice - Hall of India
4) S.D.Conte and Carl de Boor: Elementary Numerical Analysis Analograthmic approach McGraw Hill
5) M.K.Jani, S.R.K Iyengar and R.K. Jain : Numerical Methods for scientific and Engineering
Computations. Wiley Eastern.
6) P.Kandaswamy K.Thilagavathy : Numerical Mehtods , S.Chand & Co. K.Gunavathy
7) E.V.Krishnamurthy, S.K.Sen: Numerical Algorithms, Affiliated East West.
CS 402 Principles of Programming Languages
Module I
Programming Domains. Language evaluation. Evolution of major programming languages. Describing
Syntax and Semantics. Formal methods of Describing Syntax and semantics. Backus Naur Form.
Attribute grammars. Describing semantics - Denotational semantics.
Module II
Data types and ariables - Names - variables . Scope and lifetime. Expression and assignment Statements.
Control structures. Subprograms - parameter passing - overloading - generic subprograms.
Module III
Data abstraction and Encapsulation. Polymorphism and inheritance. Features of object oriented
Languages. Smalltalk, C++ and JAVA. Design and implementation issues. Exception handling.
Constructs for concurrency
Module IV
Functional programming languages - Lambda calculus- Introduction to pure LISP. Applications of
functional programming languages.
Module V
Logic programming languages- a brief introduction to predicate calculus - Horn clauses - Logic
programming. Introduction to prolog. Applications of Logic programming.
1) James Gosling “Java Programming Language”, Addison Wesley,
2) “Symbolic Logic and Logic Programming”, Learning Material Series, Indian Society for Tech.
Education, 1996
3) Bjarn Stroustrup, “Design and Evolution of C++”, Addison Wesley, 1991
4) Michael J.Gordon, “Programming language Theory and its implementation”, Prentice Hall, 1991
5) Terence W. Pratt, “Programming Languages”, Prentice Hall, Ninth edition 1996
6) Ravi Sethi, “Programming Languages-concepts and constructs”, Addison Wesely, Second Edition,
7) Robert W.Sebesta, "Concepts of Programming Languages",
CS 403 Automata Languages and Computation
Module I
Finite State systems – Non Deterministic Finite Automata and Deterministic Finite Automata.
Equivalence of NFA and DFA. Equivalence of NFA with and without epsilon moves.
Module II
Regular expressions – Equivalence of Finite Automata and regular expressions. Finite Automata with
output. Moore and Meelay Machines. Equivalence of Moore and Meelay machines. Applications –
Lexical Analysers. Properties of regular sets. Pumping Lemma for regular sets. Closure properties.
Decision algorithms. Myhill Nerode’s theorem and Minimisation of Finite Automata. Minimisation
Module III
Context Free Grammars – Derivation of Languages – Derivation trees. Ambiguity. Simplification.
Chomsky Normal Form and Greibach Normal Form. Push Down. Automata. Deterministic Push Down
Automata. Equivalence of Push Down Automata and Context Free Languages. Pumping Lemma for
Context free languages. Closure properties. Decision Algorithms.
Module IV
Turing machines – Computation – languages and functions. Techniques for Turing machine
construction – storage in finite control – multiple tracks – checking of symbols, shifting over -
subroutines. Non Deterministic Turing machines.
Module V
Undecidability – Recursive and recursively enumerable functions. Universal Turing machine. Halting
problem of Turing machine. Chomsky Hierarchy – Equivalence of regular grammar and Finite
Automata. Equivalence of Unrestricted grammar and Turing Machine. Context Sensitive Grammars.
Equivalence of Context Sensitive languages and Linear Bound Automata (LBA). Relation between
classes of Languages.
Text Books
1) J.E. Hopcroft, J.D. Ullman, “Introduction to Automata Theory, Languages and Computation”,
Addison Wesley, 1990.
2) K.L.P. Misra, N. Chandrasekharan, “Theory of Computation”, Prentice Hall, 1998.
1) H.R. Lewis, Shistos H. Papadimitrou, “Elements of Theory of Computation”, Prentice Hall India,
New Delhi, 1991.
2) John Martin, “introduction to Language and Theory of Computation”, Tata McGraw-Hill, New
Delhi, 1998.
3) Peter Linz, An Introduction to Formal Languages and Automata, Narosa Publications, 2000
4) Thomas A. Sudkamp, “languages and Machine – An Introduction to Computer Science”, Addison
Wesley, Reading, MA, 1990
CS 404 Computer Architecture & Organization
Module I
Basic structure of computer hardware and software - Addressing methods and machine program
sequencing - Computer arithmetic - logic design for fast adders - multiplication - Booth’s algorithm -
Fast multiplication - integer division - floating point number representation- floating point arithmetic
Module II
Control unit - instruction execution cycle - seque ncing of control signals - hardwired control - PLAs -
micro programmed control - control signals - microinstructions- micro program sequencing- Branch
address modification- Prefetching of micro instructions- emulation-Bit slices
Module III
Memory organisation-Semiconductor RAM memories- internal organisation-Bipolar and MOS devices -
Dynamic memories - multiple memory modules and interleaving - cache memories - mapping functions
- replacement algorithms - virtual memory - address translations - page tables memory management
units - Secondary memory - disk drives - organisation and operations - different standards
Module IV
Input-output organisations - accessing I/O devices - direct memory access (DMA) - interrupts - interrupt
handling - handling multiple devices - device identification - vectored interrupts - interrupt nesting -
Daisy chaining - I/O interfaces - serial and parallel standards - buses - scheduling - bus arbitration –
bus standards.
Module V
Introduction to parallel organisations – multiple processor orginisation - symmetric multiprocessors -
cache coherences – non uniform memory access –vector computation –introduction to CISC & RISC -
Architectures –comparison
Text Books:
1) Hamacher C V, “Computer Organisation – 4th Edition” , Mc.Graw Hill., NewYork ,1997
2) Stallings William, “Computer Orginisation and Architecture”,6th Edition Pearson Education ,2003
1) Pal Chaudhary P, “Computer Organisation and Design “ , Prentice Hall, New Delhi,
2) Hayes J P , “Computer Organisation and Architecture - 2nd Edition “, Mc Graw Hill,
3) Tanenbaum A S , ”Structured Computer Organisation - 3rd Edition”, Prentice Hall,
4) Kai Hwang & Faye A Briggs “Computer Archtecture and Parallel Processing “Mc.Graw Hill.,
NewYork –1985
5) D.A Pattersen and J.L Hennesy ,”Computer Orginisation and Design: The hardware/software
Interface 2nd Edition”, Harcourt Asia private Ltd. (Morgan Kaufman),Singapore 1998
CS/IT 405 Data Structures and Algorithms
Module I
Introduction to data structures. Arrays. Sparse matrices. Strings - representation. Implementation of
abstract data type (ADT) string. Linked Lists. Representation of polynomials using linked lists. Doubly
linked list. Garbage collection. Buddy systems.
Module II
Stacks, implementation of ADT stack using arrays and lists. Typical problems. Conversion of infix to
postfix. Evaluation of postfix expression. Queues and Deques, implementation. Priority queues
Trees, definition and mathematical properties. Binary trees. Binary tree traversal - Preorder, inorder and
post order. Expression trees. Threaded Binary Trees. Representation of trees using binary trees. Search
trees. Balanced binary trees.
Module III
Graphs. Mathematical properties - Degree - connectedness. Directed graphs - Directed acyclic graphs.
Representation using matrix. Graphs traversal. Shortest path. Minimum Spanning Tree - Kruskal
Algorithm. Symbol tables. Binary search. Hash tables. hashing functions.
Module IV
File structures. Random Access files. Indexed Sequential Files. B- Trees and B+ trees. External and
internal sorting algorithms.
Note: The course should be taught using Object Oriented Programming Language JAVA
1) Aaron M.Tanenbaum, Moshe J.Augenstein, “Data Structures using C”, Prentice Hall International
Inc., Englewood Cliffs, NJ, 1986
2) Ellis Horowitz and Sartaj Sahni, “ An introduction to Data Structures”, Computer Science Press,
Rockville, MA, 1984
3) Gregory L. Heileman, “Data structures, Algorithms and Object oriented programming”, McGraw-
Hill, New York 1997.
4) Jean Paul Tremblay and Paul G Sorenson, “An introduction to Data Structures with Applications”,
McGraw-Hill, Singapore, 1984
5) Mark Allen Weiss, “Data Structures and Algorithm Analysis in C++”, Benjamin/Cummings
Publishing Company Inc., Redwood City, CA, 1991
6) Mark Allen Weiss, “Data Structures and Algorithm Analysis in C++”, Peach pit Press
Benjamin/Cummings Publishing Company Inc., Redwood City, CA, 1991
7) Michael T. Goodrich and Roberto Tamassia, “ Data Structures and Algorithms in Java”, John Wiley
and Sons, Inc., 1999
8) Michael Waite and Robert Lafore, “Data Structures and Algorithms in Java” , Techmedia, New
Delhi, 1998
9) Robert L.Cruse, "Data Structures and Program Design", Prentice Hall India, 3rd ed., 1999
10) Sartaj Sahni, 'Data Structures, Algorithms, and Applications in Java", McGraw-Hill
1. Transfer characteristics and specifications of TTL and MOS gate
2. Design of half adder and full adder using NAND gates.
3. Set up R-S & JK flip flops using NAND Gates
4. Code conveters - Binary to Gray and gray to Binary using mode control.
5. Asynchronous UP / DOWN counter using JK Flip flops
6. Design and realisation of sequence generators.
7. Study of shift registers and design of Johnson and Ring counter using it.
8. Binary addition and subtraction (a) 1's complement (b) 2's complement
9. Study of IC counters 7490, 7492, 7493 and 74192.
10. Astable and monostable multi- vibrators using gates - IC version Timing circuit using 555
11. ADC using dual slope method.
12. Study of MUX & Demux
13. ROM & RAM Chips - Verification as memories
CS/IT 407 Data Structures Lab
Implementation and study of algorithms in a suitable programming language for the following
1. Sorting and Searching
2. Linked List
3. Stacks and Queues
4. Trees and Graphs
Module I
Assembler: Overview of the assembly process – Design of two pass assembler – Single pass assembler –
Macros – Macro definition and usage schematics for macro expansion – Design of a Macro preprocessor
– Design of a Macro assembler – Introduction to Loaders and Linkers.
Module II
Compiler: Introduction – Analysis of the source program – phases of a compiler – Compiler
construction tools – Lexical analysis – Role of the lexical analyser – Specification of tokens –
Recognition of tokens – Lexical analyser generators.
Module III
Syntax Analysis – Role of the parser – Context free grammars – Top-down parsing – Bottom- up parsing
– Operator precedence parsing – LR parsers (SLR, Canonical LR, LALR) – Parser generators.
Module IV
Syntax-directed translation – Syntax-directed definitions – S-attributed definition – L-attributed
definition – Top-down and bottom- up translation – Type checking – Type systems – Specification of a
type checker. Run time environment – Source language issues – Storage organization – Storage
allocation strategies – Access to nonlocal names – Parameter passing – Symbol tables.
Module V
Intermediate code generation – Intermediate languages – Declaration – Assignment Statement – Boolean
expression – Procedure calls - Code optimisation – Introduction – Sources of optimisation – Introduction
to data flow analysis. Code generator – Issues in the design of a code generator, the target machine, A
simple code generator.
Text Book:
1) Alfred V. Aho, Ravi Sethi & Jeffrey. D. Ullman, Compilers Principles, Techniques & Tools.
1) Aho. A.V & Ullman J.D Principles of Compiler Design .
2) S.S. Muchnick – Harcourt Asra (Morgan Kaufman),Advanced Compiler Design implementation,
3) Modern Compiler Implement ation in C , Cambridge Uty. Press 1997.
4) Alan Holub, Compiler Design in C, PHI
5) Kenneth C. Louden, Compiler Construction, Principle and Practice, Thomson Books
6) Leland L.Beck, “System Software – An Introuction to System Programming”, Addison Wesely
7) D.M.Dhamdhere, "System Programming and Operating Systems”, 2ond Ed., Tata Mcgrawhill
Module I
Software Life Cycle – Waterfall Model – Prototyping – Object Oriented Analysis – Object, Dynamic &
Functional Models – SRS – Format for SRS – Data Dictionary
Module II
Design: Principles – Cohesion & Coupling – Abstraction.
Object Oriented Design:- System Design – Object Design – Designing Algorithms – Design of
association – Design Implementation
Module III
UML: Structural Modelling: Developing UML Object diagrams – Basic Components of Object
Diagrams – Classes – Interfaces – Packages. UML: Behavioural Modelling: Use Case Diagrams –
Activity Diagrams – State Chart Diagrams
Module IV
UML Architectural Modelling: Component Diagrams – Deployment Diagrams – Unified Process
Case Study: - Applying Object Oriented Methodologies in Software Development
Module V
Case Tools: - A Study on Computer Aided Software Engineering – Workbenches – General Study on
Case Tool usage in various phases
Case Study: - Preparing SRS, Plan and Object Oriented Design of typical Software project.
1) Pankaj Jalote ,An Integrated approach to Software Engg: ,Narosa Publishers
2) Roger. S. Pressman.,Software Engg – A Practioner’s approach (Mc. Graw Hill Publishers)
3) James Rimbough & Blaha.,Object Oriented Modelling & Design (PHA Publishers)
4) Booch & Rambaugh. – User Guide ,The Unified Modelling Language (Addisson Wesly Publishers)
Module I
Introduction to microprocessors - Architecture of typical 8 bit microprocessor – Intel 8085
microprocessors - study of functional units. Function of various controls signals -Design of CPU section
with buffers and latches. Interrupt structure of 8085.
Module II
Instruction set of 8085 microprocessors - Addressing modes - Programming - examples - Instruction
timing .Memory design - Design of memory using standard chips – Address decoding - I/O addressing
schemes - I/O mapped I/O, and memory mapped I/O techniques
Module III
Interfacing peripherals – Basic interfacing concepts - Interfacing output displays – Interfacing input
keyboards . 8085 Interrupts – Programmable Interrupt Controller (8259A)-Block diagram and operation
- Direct Memory Access(DMA) – DMA Controller (Intel 8257)- Interfacing 8085 with Digital to
Analog and Analog to Digital converters.
Module IV
Programmable peripheral interface (Intel 8255A) - Programmable communication interface ( Intel 8251
- Programmable interval timer(Intel 8253 and 8254). Programmable Keyboard /display controller(Intel
8279). Serial and parallel bus standards– RS 232 C, IEEE 488, Centronics. Microprocessors
Module V
Introduction to microcontrollers - comparison with microprocessors - Study of Microcontroller (MCS
51 family) -8051 microcontroller: Architecture –instruction set - addressing modes – interruptsprogramming-
Interfacing with Stepper motor ,ADC and DAC- Typical applications.
1) Ramesh S. Gaonkar ,Microprocessor Architecture, Programming, and Applications with the 8085,
5/E Prentice Hall ,2002.
2) Adithya P. Mathur , Introduction to Microprocessors , 3/E Tata McGrahill
3) Barry B. Brey ,8085A Microprocessor, The: Software, Programming and Architecture, 2/E
Prentice Hall , 1993.
4) Richard H. Barnett, The 8051 Family of Microcontrollers, Prentice Hall ,1995.
5) Muhammad Ali Mazidi and Janice Gillispie Mazidi, The 8051 Microcontroller and Embedded
Systems , Pearson education ,2000
6) Scott MacKenzie , The 8051 Microcontroller, 3/E Prentice Hall ,1999
7) James W. Stewart, 8051 Microcontroller, The: Hardware, Software, and Interfacing, 2/E Prentice
Hall ,1999.
CS 504 Data Communication
Module I
Introduction – Various types of communication systems. Modulation: need for modulation - different
types - definition – expression. Noise in Communication Systems: classification, SNR, CNR noise
figure, relationships between noise figures. Voice Signal Digitization: PAM, PPM, PWM, PCM, Delta
modulation, PCM and DM voice signal comparison, TDM of PCM signals.
Module II
Digital Radio: block diagram, ASK, FSK, PSK, QAM, digital demodulation, QAM demodulation
Components in a data communication system - Transmission media: transmission rate - bandwidth
requirements. Shannon's theorem - channel capacity - Bandwidth, Modems - Switching - Multiplexing
digital PBXs
Module III
Data Encoding, Data transmission basics: bit – serial transmission, transmission modes - asynchronous
and synchronous transmission, bit, character and frame synchronization
Module IV
Protocol basics, Error control, Idle RQ, Continuous RQ, Link utilization, selective repeat and go-back-
N. Link management.
Module V
Error detection methods, Parity, Block sum check, Cyclic redundancy check, Data compression,
Huffman coding, Dynamic Huffman coding, Facsimile compression, transmission control circuits,
Communication control devices: time division multiplexer, statistical multiplexer. Block-mode device
Text Books
1) Fred Halsall : Data Communications Computer Networks and Open Systems, Pearson Education,
Fourth edition
2) William Stallings : Data & Computer Computer Communications:, Pearson Education, Sixth edition
1) B. Forouzan, Introduction to Data Communication and networking 5/E, PHI, 1997
2) Prakash. C. Gupta, Data Communications, PHI, 1999
3) R.P. Singh, S.D. Sapre : Communication systems Analog & Digital
Module I
Introduction: Characteristics of the Database approach – Data models, schemas and instances – DBMS
architecture – Data independence – Database languages and interfaces – Database administrator – Data
modeling using Entity - Relationship (ER), Entity sets, attributes and keys - Relationships, Relationship
types, roles and structural constraints - Weak Entity types - Enhanced Entity-Relationship (EER) and
object modeling. Sub classes, super classes and inheritance - Specialization and generalization.
Module II
Record storage and file organizations: Placing file records on disks – Fixed length and variable length records
Spanned Vs unspanned records – Allocating file records on disk– Files of unordered records(Heap files), Files
of ordered records(Sorted files).- Hashing Techniques. Indexed structures for files – Types of single level
ordered index, multi- level indexes - B - trees and B + trees, Indexes on multiple keys, Other types of indexes.
Module III
The Relational model: Relational model concepts – Relational model constraints - The Relational
Algebra – Relational calculus – Tuple Relational calculus, Domain Relational calculus. - SQL.
Database Design: Functional dependencies – Basic definitions – Trivial and non trivial dependencies –
Closure of a set of dependencies – Closure of a set of attributes – Irreducible sets of dependencies – Non
loss decomposition and Functional dependencies. First, Second and Third normal forms – Boyce-codd
normal form.
Module IV
Transaction processing - Desirable properties of Transactions, Schedules and Recoverability -
Serializability of Schedules. Concurrency Control Techniques - Locking techniques, Time Stamp
Ordering, Multi version concurrency control techniques, Granularity of data items. Database recovery
techniques - Database recovery techniques based on deferred update and immediate update, Shadow
paging, ARIES recovery algorithm. Database security and Authorization - Security issues, Access
Control based on granting/revoking of privileges, Mandatory access for Multilevel Security.
Module V
Distributed databases: Motivation for distributed databases – concepts – Types of distribution –
Distributed Query Processing – Commit Protocol for distributed databases.
Introduction to object oriented databases, Active databases. Data warehouses – Data mining.
1) Elmasri and Navathe, “Fundamentals of Database Systems” , 3/e, Addison - Wesley, 2001.
2) A Silberschatz, H. F. Korth, and S Sudarshan, “Database System Concepts”, 3/e,Tata McGraw Hill,
3) C.J Date, “ An Introduction to Database Systems “, Addison-Wesley, 1995
4) M.Tamer Ozsu & Patric Valduriez , “Principles of Distributed Database Systems”.
5) Margaret.H.Dunham ,”Data Mining. Introductory and advanced topics”, Pearson Education,2003.
6) Hector Garcia-Molina,Jeffret D. Ullman, Jenniffer Widom ,”Database System implementation”,
Prentice Hall International, Inc, 2000.
- Creation of Single Pass – Two Pass assembler – Macro processor.
- Generation of Lexical Analyzer using tools such as Lex
- Generation of Parser using tools such as YACC.
- Generation of LL(1) Parser
- Generation of intermediate code
- Creation of type checker
- Developing a compiler for a subset of a programming language.
Module I
Introduction to Operating Systems. Extended Machine - Operating System Structure . Processes -
Interprocess Communication - Race Conditions - Critical Sections - Mutual Exclusion - Busy Waiting -
Sleep And Wakeup - Semaphores - Event Counters - Monitors - Message Passing. Process Scheduling -
Round Robin Scheduling - Priority scheduling - multiple queues - Shortest Job First - Guaranteed
scheduling - Two- level scheduling.
Module II
Memory management. Multiprogramming. Multiprogramming and memory usage - Multiprogramming
with fixed partitions. Swapping - multiprogramming with variable partitions - Memory management
with bit maps, linked lists, Buddy system - allocation of swap space. Virtual memory - paging and page
tables, associative memory - inverted page tables. Page replacement algorithms. Design issues for
paging systems - Working set model. Example systems.
Module III
File systems and I/O files. Directories - File system implementation - security and protection
mechanisms. Principles of I/O hardware - I/O devices - device controllers - DMA. Principles of I/O
software - interrupt handlers - device drivers - Disk scheduling - clocks and terminals.
Module IV
Deadlock - conditions for deadlock - deadlock modelling. Deadlock detection and recovery. Deadlock
avoidance - resource trajectories - safe and unsafe states - bankers algorithm. Deadlock prevention. Two
phase locking – non-resource deadlocks - starvation.
Module V
Introduction to distributed operating systems - distributed systems - design issues. Client server model.
Remote procedure call. Synchronisation in distributed systems - clock synchronisation - concurrency
control - Deadlocks in distributed systems. Process management - threads - system models - processor
allocation algorithms - distributed file systems.
Case Study
UNIX / LINUX operating system
Text Book
1) Andrew S. Tanenbaum, “Modern Operating Systems”, Prentice Hall, 1991
1) Bach, M.J., “Design of UNIX Operating System”, Prentice Hall
2) Charles Crowley, “Operating systems – A Design Oriented Approach”, Tata McGrawhill, 1997
3) D.M.Dhamdhere, “System Programming and Operating Systems”, Tata McGraw-Hill,1996
4) Deital, H.M., “Operating Systems”, Addison Wesley, 1992
5) Garry Nutt, “Operating Systems – A Modern perspective ”, Second Edition, Addison Wesley, 2000
6) Pradeep K.Sinha, “Distributed Operating Systems”, Tata McGrahill, 1998
7) Silberschatz, “Operating System Concepts”, Addison Wesley, 1993
8) William Stallings, “Operating systems”, Prentice Hall, 1997
9) Michael Palmer, Guide to Operating System, Thomson
Module I
Overview of Graphic s systems. Video display devices - Raster scan systems - Random Scan systems -
input devices. Hardcopy devices - Graphic Software. Output primitives –points and lines. Line drawing
algorithms - circle generating algorithms - polygon filling algorithms – Filling arcs –pttern filling Output
attributes - Bundled attributes. Antialiasing. Graphical user interface - Logical classification of input
Module II
Two dimensional transformations. basic transformations - translation - rotation - scaling.
Matrix representation and homogeneous cordinates - composite transformations.
Transformation between cordinate systems - Affine transformations. Two dimensional
viewing - viewing pipeline - Windows to viewport transformations - clipping operations -
point clipping - line clipping - polygon clipping.
Module III
Three dimensional object representations. polygon surfaces - curved surfaces. Spline
representations - Hermite polynomials - Cubic splines - Bezier curves - B-splines. Octrees
and BSP trees. Fractal geometry methods. Three dimensional transformations.. Three
dimensional viewing. Projections. View volumes. Three dimensional clipping - Hardware
Modula IV
Visible surface detection. Classification of visible surface detection algorithms. Back face
detection - Depth buffer - A-buffer. Scan line algorithms- Depth sorting - Area subdivision
methods octrees - BSP trees - octrees - Ray casting.
Module V
Shading . Illumination models - light sources. Basic Illumination models. Polygon rendering - constant
intensity - Goraud shading - Phong shading . Ray tracing. Texture mapping. Color models. Introduction
to Animation. Raster animation – animation languages- Key frame systems - Morphing - Motion
specifications. Introduction to Virtual reality - Virtual Reality Modellling Language(VRML).
Text Book
1. Donald Hearn ,M Pauline Baker, Computer Graphics C version, 2/E
Pearson Education ,2003 .
1) James D.Foley, Introduction to Computer Graphics, Addison Wesley Publishing Company,
2) Alan Watt, Mark Watt, Introduction to Animation and Rendering,, Addison Wesley Publishing
Company, 1994
3) Newmann W and Sproull R.F., Principles of Interactive Computer Graphics, McGraw-Hill,1980
4) Rogers D.F., Procedural Elements for Computer Graphics, McGraw-Hill, 1985
Module I
Architecture 16 bit microprocessors : Intel 8086 Archetecture- Memory address space and data
organization - Segment registers and memory segmentation - I/O address space - Addressing modes -
Comparison of 8086 and 8088 - Basic 8086/8088 configuration - Minimum mode - Maximum mode -
System timing. – Bus interface. Interrupts and interrupt priority management. Intel 80286 Archetecture-
Comparison with 8086 processor.
Module II
Architecture of 32 bit Microprocessors : Intel 80386 Architecture – Special 80386 Registers- Memory
management -interrupts and exceptions - management of tasks - Real, protected and virtual 8086 mode-
Introduction to 80486 microprocessor – Architecture – Comparison with 80386 processor.
Module III
Advanced Microprocessors: Introduction to Pentium and Pentium pro architectures: RISC concepts-
BUS operation- Super scalar architecture- Pipelining-Branch prediction-Instruction and data caches-
FPU- Comparison of Pentium and Pentium pro architecture. Introduction to Pentium II, Pentium III and
Pentium IV processors – Introduction to Intel and AMD 64 bit architectures. RISC Archetecture :
Definition of RISC –Properties of RISC Systems– Practices in RISC Systems –Register windowing –
Advantages and shortcomings – Comparison with CISC architecture .
Module IV
Intel 80x86 Programming: 80x86 Instruction set , Assembly level programming with DEBUG and MASM –
MS-DOS Functions andBIOS Calls - programming examples using 80x86.
Module V
Introduction IBM PC Architecture , Peripherals & Interface Buses: Motherboard- Chip sets - graphic
adapters and monitors-drive controllers - floppy and hard disk drives- IDE and SCSI - streamers and
other drives -parallel interfaces and printers - serial interfaces – 16550 UART CMOS RAM and real
time clock- keyboard and mouse- the power supply (SMPS) - BIOS and Boot Process Bus Systems:
PC/XT and AT Buses – Microchannel and ISA – Local Buses: VESA and PCI- I/O Buses: SCSI and
References :
1) Barry B. Brey , The Intel Microprocessors 8086 to Pentum 4- Archetecture Programming and
Interfaceing, 6/e Pearson Education ,2003.
2) James L. Antonacos , An Introduction to Intel Family of Microprocessors , 3/e Pearson Education,
3) John Uffenbeck , The 80x86 Family – Design Programming and Interfacing, 3/e Pearson Education,
4) YU-Cheng Liu & Glenn A Gibson, Microprocessor System , Architecture Programming & Design,
Pentice Hall of India.
5) Douglas V Hall, Microprocessors & Interfacing, Tata McGrahill, 1998
6) Intel Users manual for 8086, 80386 & 80486, Pentium processors
7) H. P. Messmer, The Indispensable PC Hardware Book, 3/e, Addison Wesley, 1997
8) S. J. Bigelow, Troubleshooting, Maintaining, and Repairing PCs, 2/e, Tata McGraw Hill, New
Delhi, 1999
9) Ytha Yu and Charles Marut , Assembly Language Programming and Organisation of IBM PC,
International Edition , McGrawhill Inc, 1992
10) K. Miller, An Assembly Language Introduction to Computer Architecture using the Intel Pentium,
Oxford University Press, 1999.
1. Identification of components/cards and PC assembling from components
2. Assembly language program for implementing arithmetic operations
3. Assembly Language programs for time and date ma nipulation.
4. Assembly Language programs for display /video manipulation
5. Assembly Language program for equipment status
6. Implementation of a file manager using DOS/BIOS interrupts
7. TSR (Terminate and Stay Resident) Programming
8. ADC interface
9 .Stepper Motor interface using DAC
10. Parallel Interface: Printer and HEX keyboard.
11. Serial Interface: PC to PC serial interface using null modem
Note: Programs can be implemented using MASM /TASM
References :
1) H. P. Messmer, The Indispensable PC Hardware Book, 3/e, Addison Wesley, 1997
2) S. J. Bigelow, Troubleshooting, Maintaining, and Repairing PCs, 2/e, Tata McGraw Hill, New
Delhi, 1999
3) Douglas V. Hall, Microprocessors and Interfacing, 2/e, Tata McGraw Hill, 1988
4) Ytha Yu and Charles Marut , Assembly Language Programming and Organisation of IBM PC,
International Edition , McGrawhill Inc , 1992
5) Barry B. Brey , The Intel Microprocessors 8086 to Pentium 4- Archetecture Programming and
Interfaceing, 6/e Pearson Education ,2003

Digg Google Bookmarks reddit StumbleUpon Technorati Yahoo! Buzz DesignFloat Delicious BlinkList

0 comments: on "Cusat Compleat Syllabus"