ASSAM SCIENCE AND TECHNOLOGY UNIVERSITY

MCA
SYLLABUS STRUCTURE

2nd Semester subjects

Paper Subject Name L T P Credits

Theory Subjects
CA132201 Data and File Structure (DFS) 3 2 0 4
CA132202 Computer Architecture and 3 2 0 4
Organization (CAO)

CA132203 Computer Based Optimization 3 2 0 4

Techniques (CBOT)

CA132204 Graph Theory (GT) 3 2 0 4

CA132205 Probability and Statistics (PS) 3 2 0 4
Practical Subjects
CA132216 Programming Laboratory-II 0 0 10 5
(LAB-2)
Total Contact Hrs : 35
Total Credits : 25

1|Page
ASSAM SCIENCE AND TECHNOLOGY UNIVERSITY
 MCA 2ND SEMESTER SYLLABUS
Paper : CA132201
Subject Name : DATA AND FILE STRUCTURE
Marks : (Theory-60, Internal Evaluation – 20, Midterm Examination -20)
L-T-P :: C : 3-2-0 :: 4

UNIT PARA Content Weeks

1 Fundamental Notions : Primitive and composite data types ; Time and Space Complexity of 1
algorithms, Concept of Big-O, small-o & Big-.

2 Data Structures : Linear List: Stacks, Queues, Arrays, Linked Lists, Circular & .Doubly Linked Lists. 2

3 Trees and Graphs : Introduction to Graph & Trees. Tree: Properties of trees; Pedant vertices in a 3
tree; center of a tree; Rooted binary trees.Concepts of trees; Extended Binary trees; Complete Binary
trees; General Trees. Binary Search Trees; Weight balanced and Height balanced trees; AVL Tree;
Balanced Multi-Way Trees; Threaded Binary Trees.

4 Graph: Concept of graph, vertex set, edge set, connected graph,etc., 2

Adjacency matrix, Path matrix, Warshall’s algorithm, Modified Warshall’s algorithm,
Adjacency list, Node list, Edge list.
Spanning trees – Spanning tree algorithms; Fundamental circuits spanning trees of weighted graph.

5 File Structures : 2
Concepts of Fields, Records and Files; Concepts of Blocks, Clusters, Sectors.
Sequential File Organization, Variable length Records and Text Files; Indexing Structures like B-
trees; ISAM; Hashing Techniques for Direct Files; Inverted lists; Multilists.

6 Sorting and Searching: 2

Selection_sort, Insertion-sort, Bubble-sort, Quick-sort, Heap-sort, Merge-sort.
Searching Techniques; Binary search, Linear search.

Books : 1 Abo,Hopcroft and Ullman , Data Structures and Algorithms,Addson Wesley Publishing Co.
2 Horowitz and Sahni , Fundamentals of Algorithms, Narosa Publishing House .
3 Cormen , Leiserson , Rivest, Introduction to Algorithms, Mil Press & MeGraw - Hill Books Company.
4 Kunth.D., The Art of Computer Programming,Vol - 1 & 11 , Addison Wesely.
5 Rauthan & Patel, Expert Data Structures, Khanna Publication Co(Ltd ).
6 Weiss, Data Structures and Algorithm Analysis in C++, Pearson Education

Paper : CA132202
Subject Name : COMPUTER ARCHITECTURE AND ORGANISATION (CAO)
Marks : (Theory-60, Internal Evaluation – 20, Midterm Examination -20)
L-T-P :: C : 3-2-0 :: 4

UNIT PARA Content Weeks

1 Overview: Simplified block diagram of a computer system, Instruction execution Model. 1

2 2.1 Processor Organization: Instruction set, types, formats, addressing modes; Register set; Assembly 2
and machine language programming.

2.2 Computer arithmetic: Review of addition and subtraction; Multiplication- basic, Booth's, array; 2
Division- basic, restoring, non-restoring; Floating point arithmetic.

3 Data path organization, concept of a bus. 3

Control structure: Hardware, Microprogramming.

4 4.1 Memory Organization: Interfacing of memory with a processor; Cache memory; Introduction to 2
virtual memory.

4.2 Input output organization: Synchronization of data transfer: strobes and handshaking, I/O mapping 3
and control: Program controlled, Interrupt, driven, DMA, Interrupt and DMA mechanisms.

5 Microprocessors: Introduction to Intel 8085 microprocessor and its peripheral chips, addressing 2
modes and simple programming examples, A RISC processor (e.g. Motorola 88000) to introduce the
basic concepts of RISC architecture,SISD,SIMD,MISD,MIMD,,.

Books: 1. Hamacher, Vranesic and Zaky: Computer Organization, TMGH

2. Mano M.M: Computer system Architecture, PHI (EEE)
3. William Stallings, Computer Organisation and architecture, Pearson
4. Hennessey : Computer Architecture, Elsevier
5. Stallings : Computer Organization & Architecture, PE
6. Hayes : Computer Architecture & Organization,MGH

2|Page
ASSAM SCIENCE AND TECHNOLOGY UNIVERSITY
Paper : CA132203
Subject Name : COMPUTER BASED OPTIMIZATION TECHNIQUES
Marks : (Theory-60, Internal Evaluation – 20, Midterm Examination -20)
L-T-P :: C : 3-2-0 :: 4

UNIT PARA Content Weeks

1 1.1 Linear Programming: Mathematical model, assumptions of linear programming, Principles of 3
simplex method, Revised simplex method, Applications, Duality, Dual Simplex method, sensitivity
analysis

1.2 Special type of linear programming problems: Transportation and assignment problems. 3

2 Integer programming: introduction, Branch and bound techniques, Assignment and travelling 4
salesman problems with algorithmic approach.

3 Dynamic programming: deterministic and probabilistic dynamic programming 3

4 Queueing model: Specification and measure of queueing systems, Structures of basic queueing system- 2
Definition and classification of stochastic processes, Characteristics of a Queing system, Interpretation of
a model, Single Channel waiting line- (M/M/1) (∞: FIFO), Single channel finite population queue (M/M/1):
(C/FIFO), Multichannel Queing problem (Infinite population) (M/M/C): (∞: FIFO), Earlang Distribution
(M/Ek/1): (∞: FIFO).

Books 1 Natarajan, Balasubramani, Tamilasari : Operations Research , Pearson

2 Gillett, B.G.: Introduction to operations research - A Computer oriented Algorithmic approach,
McGraw-Hill.
3 Srinath, L.S: Linear programming, East-west, New Delhi.
4 Hiller, F.S. and Liberman, G.J.: Introduction to Operations Research, Holden Day In
5 Taha: Operations Research , Pearson

Paper : CA132204
Subject Name : GRAPH THEORY
Marks : (Theory-60, Internal Evaluation – 20, Midterm Examination -20)
L-T-P :: C : 3-2-0 :: 4

UNIT PARA Content Weeks

1 Graph: Incidence and degree; Handshaking Lemma; Isomorphism; Sub graphs and Union of graphs; 3
Connectedness; Walks, Paths and Circuits; Components and Connectedness; Walks, Paths
and Circuits; Components and Connectedness algorithms; Shortest Path Algorithms, Eulerian
graph, Fleury's algorithm and Chinese postman problem; Hamiltonian graph - necessary and
sufficient conditions; Travelling salesman; Bipartite graph.

2 Tree: Properties of trees; Pedant vertices in a tree; Centre of a tree; Rooted binary trees; 2
Spanning trees - Spanning tree algorithms; Fundamental circuits; Spanning trees of a
weighted graph; cut-sets and cut-vertices; Fundamental cut-sets; Connectivity and separativity;
network flow; max-flow min-cut theorem.

3 3.1 Planner graph: Combinatorial and geometric duals; Kuratowski's graph; detection of planarity; 2
Thickness and crossings

3.2 Matrix representations of graph: Incidence; Adjacency; matrices and their properties 2

4 Colourings: Chromatic number: Chromatic polynomial; The six and five colour theorems; The four 1
colour problem.

5 5.1 Directed graphs: Binary relations; Directed graphs and connectedness; directed trees; 2
Aborecence; Polish method; Touranaments.

5.2 Counting of labelled trees: Cayley's theorem; Counting methods; Polya theory. 2

6 Switching and coding theory and VLSI design 1

Books 1 Deo, N.: Graph Theory with Applications to Engineering and Computer Science
2 Agnarsson: Graph Theory ,Pearson
3 Harary : Graph Theory, PHI(EEE).
4 : West : Graph Theory, PHI
5 Chartran : Introduction To Graph Theory, TMH

3|Page
ASSAM SCIENCE AND TECHNOLOGY UNIVERSITY
Paper : CA132205
Subject Name : PROBABILITY AND STATISTICS
Marks : (Theory-60, Internal Evaluation – 20, Midterm Examination -20)
L-T-P :: C : 3-2-0 :: 4

UNIT PARA Content Weeks

1 Probability: 7
Probability Theory: sample spaces; Events and probability; Discrete Probability; Union, intersection
and compliment of events; conditional probability; Bay's Theorem; Random variables and
Distribution: random variables, Discrete Probability Distribution - Binomial, Poisson, Geometric and
Hyper geometric distributions; Density functions; Continuous probability distribution - Uniform,
Exponential, Normal, Student’s t,Ӽ 2, Beta and F - static. Expectations; Characteristics Functions.

2 Statistics: 3
Basic statistics: Measures of central tendencies- Mean, Median, Mode; Measures of dispersion:-
Range, Variance and Standard deviation: Frequency distributions and cumulative frequency
distributions and cumulative frequency.

3 Moments and Moment generating functions: Linear correlation coefficient: Linear and Non-linear 3
regression; Multiple correlation and multi-regression.

4 Sampling: Theory of sampling: Population and sample; sampling survey methods and estimation. 2
Statistical inference; testing of hypothesis and inference.
Central limit theorem.

Books 1 Hogg,Tanis and Rao: Probability and Statistical Inference , Pearson

2 Mendenhall,Beaver, Beaver , Probability and Statistics, Cengage.
3 Yule, U.G., Kendall, M.G: An Introduction to the Theory of statistics, Chalies Griffin and Co.Ltd.
4 Milton : Introduction To Probability & Statistics, TMH
5 Das : Statistical Methods, combined edition, TMH
6 Leon & Garcia : Probability & Statistics, PE

Paper : CA132216
Subject Name : PROGRAMMING LABORATORY-II
Marks : Internal Evaluation (as per regulation): 100; External Evaluation: 100
L-T-P :: C : 0-0-10 :: 5

LAB PART PARA Laboratory Content Total Weeks

1(75%) 1.1 Concept of Object oriented programming in C++ 1
1.2 Simple link list, Stack, queues. 2
1.3 Single, double, circular Link lists, queues. 2
1.4 graphs and trees, Several searching and sorting techniques, using 3
Graphs and trees.
1.5 B Tree, B+ Trees: Insertion deletion techniques. 3

2(25%) Simple programming on Numerical Methods 4

Books As on CA132201and CA132205

*************************************

4|Page
ASSAM SCIENCE AND TECHNOLOGY UNIVERSITY