Computer Network

Unit 1 Introduction to Data Communication:

Data Communication Components, Data Representation, data flow (Simplex, Half-Duplex and Full-Duplex mode), Network Criteria, Type of connection, physical topology, Categories of Network (LAN, MAN, WAN,PAN), study of OSI reference model.

Unit II:

Physical Layer and Media:

Analog and digital Data, Analog and digital signals, TRANSMISSION MODES: Serial and Parallel transmission, Asynchronous and Synchronous Transmission. COMMUNICATION MEDIA: guided media and unguided.

Unit III:

Data Link Layer:

Types of errors, framing (character and bit stuffing), Protocols: for noiseless channels (Simplex, Stop and wait), for noisy channels (Stop and wait ARQ, Go back-N ARQ, Selective repeat ARQ), Point-to-Point (PPP), Multiple Access Protocol: Pure ALOHA, Slotted ALOHA, CSMA, CSMA/CD, CSMA/CA.

Unit IV:

Network Layer:

IPv4 Addresses, IP addressing Methods with sub-netting and super-netting, Routing Protocols: Distance Vector, Link State, Path Vector.

Transport Layer:

Duties of transport layer, Process-to-process delivery, Congestion control: Data Traffic, Congestion control Category (Open loop, closed loop),

Unit V:

Quality of Service: Introduction to QoS, Techniques to improve QoS: Leaky bucket algortinm, Token bucket algorithm. Application Layer: Domain Name System, Functions of Network management system, Voice over IP, Firewall

Text Books:

• B. A. Forouzan - "Data Communications and Networking (Jra Ed.) - 1 MII
• A. S. Tanenbaum - "Computer Networks (4th Ed.)" - Pearson Education/PHI
• W. Stallings - "Data and Computer Communications (8th Ed.)" - PHI/ Pearson Education

Reference Books:

• Kurose and Rose - "Computer Networking -A top down approach featuring the internet" Pearson Education
• Introduction to Data Communications and Networking by Wayne Tomasi-Pearson Edition
• Comer - "Internetworking with TCP/IP, vol. 1,2,3(4th Ed.)" - Pearson Education/PHI

DISCRETE MATHEMATICS AND GRAPH THEORY

UNIT-I: Mathematical Logic and Set Theory (08 Hrs)
Propositions and Logical Operations, Quantifiers, Conditional Statements and
Tautologies, Methods of Proof, Principle of Mathematical Induction. Basic
concepts of set theory, Operations on Sets, The power set.
UNIT-II: Relations and Functions (12 Hrs)
Relations: Ordered pairs and n-tuples, Product Sets and Partitions, Relations and
Digraphs, Matrix of Relation, Paths in Relations and Digraphs, Properties of
Relations, Equivalence Relations & Partitions, Compatible Relation, Manipulation
of Relations, Composition of Relations, Transitive Closure of a relation, Partial
order relation, Partially ordered set, Hasse Diagrams. Functions: Definition,
Composition of functions, Types of Functions, Invertible Function, Permutation
Function, Characteristics function of a set with Theorems.
UNIT-III: Group Theory (12 Hrs)
Binary Operations, Properties, Semigroups, Monoids,Subsemigroup,Submonoid,
Isomorphism & Homomorphism, , Groups (only definitions and examples)
Subgroups and Homomorphism, Cosets and Lagrange’s Theorem, Normal
subgroups.
Unit- IV:Rings, Lattices & Boolean Algebra(10 Hrs)
Rings, Fields, Integral Domain, Ring Homomorphism (definitions & examples),
Lattices: Properties, Types of Lattices, Sub lattices, Isomorphic Lattices,
Complemented & Modular Lattices (definitions & examples), Boolean Algebra:
Definition, Properties, Simplification of Switching Circuits.
Unit-V: Graph Theory (12 Hrs)
Basic concepts of Graph Theory, Digraphs, Basic definitions, Paths and Circuits,
Reachability and Connectedness, Matrix representation of graphs, Subgraphs&
Quotient Graphs, Isomorphic digraphs & Transitive Closure digraph, Euler’s Path
& Circuit (only definitions and examples). Trees, Binary Tree, Labeled Trees,
Undirected Trees, Spanning Trees of Connected Relations, Prim’s Algorithm to

construct Spanning Trees, Weighted Graphs, Minimal Spanning Trees by Prim’s
Algorithm &Kruskal’s Algorithm.

Unit-VI: Combinatorics(06 Hrs)
Generating Functions, Recurrence Relations, Counting: Permutations &
Combinations, Pigeonhole Principle with Simple Applications.
Text Books
1. Discrete Mathematical Structures(3rd Edition) by Kolman, Busby & Ross
PHI.
2. Discrete Mathematical Structures with Applications to Computer Science by
Tremblay &Manohar, Tata McGraw- Hill.
3. Combinatorial Mathematics, C.L. Liu (McGraw Hill)
Reference Books
1. Discrete Maths for Computer Scientists & Mathematicians by Mott,
Kandel, Baker.
2. Elements of Discrete Mathematics by C. L. Liu.
3. Discrete Mathematics by Lipschutz.
4. Discrete Mathematics by R.Johnsonbaugh.
5. Higher Engineering Mathematics by B.S. Grewal, 40th Edition, Khanna
Publication

BE4S2T: Data Structures & Program Design

UNIT I
Introduction to algorithm, Time and space analysis of algorithms, Big oh and theta notations and
omega notations, Average, best and worst case analysis, linear and binary search, selection sort,

insertion sort, bubble sort, shell sort, Radix sort. Abstract data structure as an organization of
data with specified properties and operations, General concepts of data structures. Representation
of Arrays -Single and Multi dimensional.
UNIT II
List: - representation of ordered list using array and operation on it, sparse matrix, polynomial,
Linked Lists, Simply linked list, Implementation of linked list using static and dynamic memory
allocation, operations on linked list, polynomial representations and manipulations are using
linked list, circular linked list, doubly linked list, Generalized list
UNIT III
Stack & Queue: Representation of Stack & queue using array and linked list, , Application of
stacks, Conversion from infix to post fix and pre-fix expressions, Evaluation of postfix
expression using stacks, Multiple stacks, Circular queues, Priority Queues, Dequeue.
UNIT IV
Trees: General and binary trees, Representations and traversals, Threaded Binary Trees, Binary
search trees, Applications, The concept of balancing and its advantages, B-Trees, B+ Trees, AVL
Trees.
UNIT V
Graphs and digraphs: Representations, Breadth and depth first searches, connected component,
spanning trees, shortest path–single source & all pairs , activity networks, topological sort,
Hamiltonian path.
UNIT VI
Symbol Tables: static tree tables, dynamic tree tables, hash tables, hash functions, Collision
resolution, overflow handling, Applications
Textbooks:

Data Structures using C and C++ by Y. Langsam, Pearson Education
Algorithms in a Nutshell, George H & Garry, O’reilly Publication
Data Structures using C by Tanenbaum, Pearson Education
S. Sahani, Data Structures in C,
Data structures -Robert Kse

Database Management System

UNIT I:

Introduction to database systems: Approaches to building a database, Three-schema architecture of a database, Challenges in building a DBMS, DBMS Architecture-Various components of a DBMS, Types of data models.

UNIT II:

Relational Data Model: Concept of relations, Schema-instance distinction, Keys, referential integrity and foreign keys, Relational algebra operators, Tuple relation calculus, Domain relational

calculus. Physical and logical hierarchy: Concept of index, B-trees, hash index, function index, bitmap index. Concepts of Functional dependency, Normalization (1NF,2NF,3NF,BCNF, etc).

 UNIT III:   (07 Hrs) 

Ouery Processing and Optimization: Query Processing and Optimization process, measures of query cost estimation in query optimization, pipelining and Materialization, Structure of query evaluation plans.

UNIT IV: 

Transactions: Transaction concepts, properties of transactions, Serializability of transactions,

Testing for serializability, System recovery, Two-Phase Commit protocol, Recovery and Atomicity,

Log based recovery, concurrent executions of transactions, Locking mechanism, solution to concurrency related problems, deadlock, two-phase locking protocol, Isolation.

UNIT V:

Recovery System and advanced databases: Failure classification, recovery and atomicity, log based recovery, checkpoints, buffer management, advanced recovery techniques, Web databases, Distributed databases, Data warehousing, Data mining, Data Security, NOSQL databases.

Textbooks:

• Database System Concepts by Avi Silberschatz, Henry F. Korth, S. Sudarshan, Iata McGraw Hill, Fifth Edition.
• Fundamentals of Database Systems - Elmasiri and Navathe, Addison Wesley, 2000.
• An introduction to Database Systems, C J Date, A. Kannan, S. Swamynathan -Eight Edition.

Reference books:

• Database Management Systems - by Raghu Ramakrishnan and Johannes Gehrke, lata McGraw Hill Publication, Third Edition.
• Introduction to Database Management Systems by Kahate, Pearson Education.

BE4S5T: SYSTEM PROGRAMMING

UNIT 1:
IBM 360/370 & Assembler – Introduction to System Programming & its components, M/c
Architecture, Instruction Formats, Data Formats & Register Formats, Concept of assembler,
design of single pass and two pass assembler.
UNIT 2:
Macroprocessor – Concept of macro, macro call within macro, macro definition within macro,
recursive macro calls, design of macro processor.
UNIT 3:
Linker and Loader – Concept of static and dynamic relocation, external symbols, design of
linker, design of object file for different loading schemes.
UNIT 4:
Common Object files format & System Utilities – Structure of object file and executable file,
section or segment headers, symbol table, concept of storage class, string, various data types, line
insert, character, arrays structures. Source code control system), make, link editor, symbolic
debugger, GNU debugger.
UNIT 5:
Unix Device Drivers – Definition, Anatomy and Types, Device programming, Installation,
Incorporation of driver routines, Basic device operation, Implementation with Line Printer,
Comparative study between device drivers for UNIX & Windows.
UNIT 6:
Compiler – Phases of Compilers, Overview of Databases and Algorithms required for all
phases. Role of lexical analyzer, recognition of tokens, Study of LEX & YACC.
Text Books:
1. System Programming- J. J. Donovan, Tata McGraw-Hill Education.
2. UNIX Device Drivers- George Pajari, Pearson Education.
3. UNIX system Utilities manual.
4. UNIX programming Tools LEX and YACC –Levine, Mason and Brown, O’Reilly.
Reference Books:
1. System Programming and Operating systems- D. M. Dhamdhere, Tata McGraw-Hill
Education.
2. UNIX programming Environment- Keringham and Pike, PHI.
3. System Software: An introduction to systems programming- Leland L. Beck, Pearson
Education.
4. Principles of Compiler Design-Aho and Ullman, Pearson Education.