BE 6th sem CSE syllabus of RTM Nagpur University

66CS1: Design And Analysis Of Algorithms

UNIT – 1
Mathematical foundations, summation of arithmetic and geometric series, n, n2 , bounding summations using integration, recurrence relations, solutions of recurrence relations using technique of characteristic equation and generating functions, Complexity calculation of various standard functions, principles of designing algorithms

UNIT – 2
Asymptotic notations of analysis of algorithms, analyzing control structures, worst case and average case analysis, amortised analysis, application of amoterized analysis, Sorting networks, comparison networks, biotonic sorting network, advanced data structures like Fibonacci heap, disjoint set representation, red and black trees and their applications.

UNIT – 3
Divide and conquer basic strategy, binary search, quick sort, merge sort, matrix operations, Greedy method – basic strategy, application to job sequencing with deadlines problem, minimum cost spanning trees, single source shortest path
etc.

UNIT – 4
Dynamic Programming basic strategy, multistage graphs, all pairs shortest path, single source shortest paths, optimal binary search trees, traveling salesman problem, Maximum flow networks.

UNIT 5
Basic Traversal and Search Techniques, breadth first search and depth first search, connected components. Backtracking basic strategy, 8-Queen’s problem, graph colouring, Hamiltonian cycles etc, Approximation algorithm and concepts based on approximation algorithms.

UNIT 6
NP-hard and NP-complete problems, basic concepts, non-deterministic algorithms, NP-hard and NP-complete, decision and optimization problems, graph based problems on NP Principle, Computational Geometry, Approximation algorithm.

Text Books:
· Thomas H. Cormen et.al. “Introduction to Algorithms”, Prentice Hall of India.
· Design & Analysis of Computer Algorithms by Aho, Pearson education. Horowitz, Sahani, Rajsekharam,
· “Computer Algorithms”, Galgotia Publications Pvt. Ltd. Brassard, Bratley, “Fundamentals of Algorithms”, Prentice Hall

Reference Books:
· Computer Algorithms: Introduction to Design and analysis, 3rd Edition, By Sara Baase & A. V. Gelder Pearson Education.

66CS2: Database Management Systems

UNIT-I
Database system concepts and Architecture – concept of relational database, Relational data model, Relational algebra, SQL-the relational database standard, introduction to PL/SQL

UNIT-II
Database design theory – Functional dependencies and normalization, relational database design algorithms, practical database design and demoralization, Relational constants, programmatic ways for implementing constraints, triggers..

UNIT-III
Physical database design – Concept of physical and logical hierarchy, storage structures like cluster, index organized table, partitions, various table storage parameters and block storage parameters, concept of index, B-trees, hash index, function index, bitmap index.

UNIT-IV
Process and memory management in database: Various types of tasks in database, database buffer management, log buffer management code reuse, concept of two tier and N-tier architecture, data dictionary and catalog information database
recovery technique. Aries Algorithm for recovery.

UNIT-V
Query optimization and performance tuning – Various techniques for query optimization, strong and weak equivalence, cost base optimization, Use of different storage structures in query optimization.

UNIT-VI
Transaction Processing -Transaction and system concepts, Desirable properties of transaction, Schedules and recoverability, serializability of schedules, concurrency control, lockbase protocols and time stamp based protocols, read
consistency.

BOOKS:
· Fundamentals of Database Systems – Elmasiri ,Navathe & Gupta, Pearson Education.
· Database Systems by S. K. Singh, Pearson Education.
· Principles of Database Systems – Ullman, Golgotia Publications 1998.

Reference Books
· Database System Concepts by Henry Korth and Others
· Database Systems by Connolly,3rd edition, Pearson Education.

66CS3: Computer Networks

Unit I :
Uses of Computer Networks, Network Hardware:- LAN,WAN,MAN, Network Software-protocol hierarchies, design issues for layers, connection oriented and connection less services, service primitives, Services to protocol relationship.
Reference models- OSI and TCP/IP. Performance: Bandwidth and Latency, Delay X Bandwidth Product, High Speed Networks, Application Performance Needs.

Unit II :
Switching and MAC Layer: Packet Switching, Circuit Switching: Multiplexing: TDM FDM. Multiple Access: Random Access, Controlled Access, Channelization, LAN: Token Ring, FDDI, Ethernet- Fast Ethernet, Gigabit Ethernet, Wireless LANs: IEEE 802.11.

Unit III :
Data Link Layer: Error Detection and Correction, Flow Control protocols, Error control protocols, HDLC, PPP.

Unit IV:
Network Layer: Routing Algorithms –Shortest path Algorithm, Flooding, Flow based routing, Distance vector routing, Link state routing, Hierarchical routing.
Congestion Control Algorithms: Leaky bucket algorithm, Token bucket algorithm. Congestion prevention Policies, Traffic shaping, Choke packets, Load Shedding, Jitter Control.

Unit V:
Transport Layer: The transport Service: Service Provided to upper layers, Transport Service primitives, Berkeley sockets, Elements of Transport protocols: Addressing, Connection establishment, Connection release, Flow control and buffering, Multiplexing, Crash recovery, Introduction to Internet Transport Protocols: Introduction to UDP, Remote procedure call, Introduction to TCP, Performance issues: Performance problems in Computer Network, Network performance measurement, System design for better performance, Fast TPDU processing., Protocols for Gigabit Networks.

Unit VI:
· Wide Area Networks: Packet switching principles, X.25, ATM and frame relay: ATM protocol Architecture, Cells, Cell format, Segmentation and reassembly in ATM, ATM adaptation Layer ¾, ATM adaptation Layer5;
· Introduction to Frame relay and frame relay protocol architecture.

Text Book:
· Computer Networks: 4th ed by Andrew. S. Tanenbaum, Pearson Education.
· Data Communications and Networks: 4thed by Behrouz A. Forouzan. Tata McGraw Hill Publication.
· Computer Networks: A systems approach by Larry L. Peterson and Bruce S. Davie, 3rd Edition, Morgan
Kaufmann Publishers.
· Data & Computer Communications: William Stallings, Sixth Edition, Pearson Education Asia.

Reference Book:
· Communication Networks: By Alberto Leon-Garcia & Indra Widjaja, 2nd Edition , McGraw Hill.

66CS4: Microprocessor & Interfacing
UNIT –I :
8085 based Microprocessor organization, 8085 Instruction set , Assembly language programming.

UNIT-II:
Memory & I/O organization, Address decoding, , Interrupts of 8085 , Basic timing diagram of 8085.

UNIT-III:
8085 Interfacing with 8255, Simple keyboard matrix interfacing with 8085, Interfacing of 7 segment LED with 8085, Introduction to DMA using HOLD/HLDA Signals.

UNIT-IV:
8279 keyboard/display controller, Interfacing of Stepper motor with 8085.

UNIT-V:
8051 architecture, code/data memory interfacing, I/o interfacing, Address decoding logic, Interrupts.

UNIT-IV:
Serial data communication, UART operation, 8051 Instruction set, assembly language programming.

TEXT BOOKS:
· Microprocessor Architecture, Programming and Applications with 8085/8080 A by R.S. Gaonkar, Wiley Eastern Ltd.
· The 8051 Microcontroller & Embedded Systems. By Mazidi & Mazidi, Pearson Education
· The 8051 Microcontroller, Architecture, programming & applications, second edition by K.J.Ayala, Penram
International.
· Microcontrollers: Architecture, Programming, Interfacing & System design by Rajkamal, Pearson Education.
· The 8 bit microprocessor & Microcontroller by V.J. Vibhute.

66CS5: Software Engineering and Project Management

Unit 1
Software Engineeringan: Introduction Introduction to Software Engineering, Software Myths, Software Engineering-A Layered Technology, Software Process Framework, Software Process Models, The Waterfall Model, Incremental Process Models, Evolutionary Process Models, Specialized Process Models, The Unified Process Model, Agile Process Models.

Unit 2
Software Engineering Practice: An overview, Communication Practices, Planning Practices, Modeling Practices, Construction Practice & Deployment, System Engineering Hierarchy, Business Process Engineering, Product Engineering, System
Modeling, Requirements Engineering.

Unit 3:
Software Engineering Analysis & Design An overview, Requirements Analysis, Analysis Modeling Approaches, Data Modeling, Object-Oriented Analysis, Scenario-Based Modeling, Flow- Oriented Modeling, Class-based Modeling, Behavioral Model.
Design Engineering Concepts, Design Model, Pattern-Based Software Design.

Unit 4
Testing Strategies and Tactics An overview, Unit Testing, Integration Testing, Validation Testing, System Testing, Debugging. Software Testing Fundamentals, Black-Box Testing, White-Box Testing.

Unit 5
Product Metrics :An overview, Software Quality, A Framework for Product Metrics, Metrics for Analysis & Design Models, Metrics for Source Code, Metrics for Testing & Maintenance.

Unit 6
Software Project Management: An overview, Software Measurements, Metrics for Software Quality, Software Project Estimation Techniques, Project Scheduling, Risk Management, Quality Management, Change Management, Software Reengineering.

Text Book:
· Software Engineering- A Practitioner’s Approach (Sixth Edition)- Roger Pressman (TMH)

Reference Books:
· Software Engineering (Seventh Edition)- Ian Summerville, Pearson Education.
· Softeare Engineering Theory and Practice by Pfleeger, Pearson Education.
· Software Engineering- Schaum’s Series (TMH)