RTU Computer Science Engineering Syllabus 5th Sem 2017
Introduction to Computer Architecture and Organization. Von Neuman Architecture, Flynn Classification.
Register Transfer and Micro operations: Register transfer language, Arithmetic Micro-operations, Logic Micro-operations, Shift Micro-operations, Bus and memory transfers.
Computer Organization and Design: Instruction cycle, computer registers, common bus system, computer instructions, addressing modes, design of a basic computer
Central Processing Unit: General register organization, stack organization, Instruction formats, Data transfer and manipulation, program control. RISC, CISC characteristics.
Pipeline and Vector processing: Pipeline structure, speedup, efficiency, throughput and bottlenecks. Arithmetic pipeline and Instruction pipeline.
Computer Arithmetic: Adder, Ripple carry Adder, carry look Ahead Adder, Multiplication: Add and Shift, Array multiplier and Booth Multiplier, Division: restoring and Non-restoring Techniques. Floating Point Arithmetic: Floating point representation, Add, Subtract, Multiplication, Division.
Memory Organization: RAM, ROM, Memory Hierarchy, Organization, Associative memory, Cache memory, and Virtual memory: Paging and Segmentation.
Input-Output Organization: Input-Output Interface, Modes of Transfer, Priority Interrupt, DMA, IOP processor.
Text/Reference Books :
- Computer Organization and Architecture – William Stallings (Pearson Education Asia)
- Computer Organization and Architecture -John Hayes (McGraw -Hill)
- Computer Organization -V. Hamacher (McGraw-Hill)
Digital Logic Design
Hardware Description Languages and their use in digital logic design.VHDL: Modelling Concepts, Lexical Elements & Syntax Descriptions, Scalar Data types & Operations, Sequential Statements, Composite Data Types & Operations, Basic Modelling Constructs. Case Study: VHDL Simulation of Ripple Carry, & Look Ahead carry Adders.
VHDL: Subprograms, Packages & Use Clauses, Aliases, Resolved Signals, Components & Configurations, Generate Statements, Concurrent Statements. Use of VHDL in simulation and synthesis.
Clocked Sequential circuits. Design steps for synchronous sequential circuits. Design of a sequence detector. Moore and Mealy Machines. Design using JK flip-flops and D flip-flops. State reduction, State assignment, Algorithmic State Charts, converting ASM charts to hardware, one-hot state assignment.
Considerations of clock skew, set-up time, hold-time and other flip-flop parameters, time constraints.Programmable Logic Devices. Read-only memory. Boolean function implementation through ROM. PLD, PGA, PLA, PAL, FPGA.
Event-driven Circuits. Design procedure for asynchronous circuits, stable and unstable states, races, race-free assignments. State reduction of incompletely specified machines. Compatibility and state reduction procedure. Hazards in combinational networks. Dynamic hazards, Function Hazards, and Essential Hazards. Eliminating hazards.
Field Programmable Gate Arrays: Introduction, Logic Elements & programmability, Interconnect structures & programmability, Extended Logic Elements, SRAM, Flash Memory & Antifuse Configuration, Case Studies of Altera Stratix & Xilinx Virtex-II pro.
Technology Mapping for FPGAs: Logic Synthesis, Lookup Table Technology Mapping.
Text/Reference Books :
- Brian Holdsworth and Clive Woods. Digital Logic Newnes (Elsevier). [Available in Indian Edition].
- Ashenden, The Designer’s Guide to VHDL,
- Stephen D. Brown, et.al., Field Programmable Gate Arrays, Kluwer Academic
- Scott Hauck, André DeHon , Reconfigurable computing: the theory and practice of FPGA based computation
- Zvi Kohavi: Switching and Finite Automata Theory.
- Parag K. Lala, Practical Digital Logic Design and Testing. PHI
- Stephen H. Unger, The essence of logic circuits. Wiatrowski & House
Data Transmission: Terminology, Frequency, spectrum, bandwidth, analog and digital transmission, Transmission impairments, channel capacity, Transmission Media. Wireless Transmission: Antenna and antenna gain. Network Reference Models (OSI/ISO and TCP/IP)
Physical Layer: Line Encoding Schemes. Concept of bit period, effect of clock skew, Synchronous and Asynchronous communication.
Data Link Layer: Functions of data link layer and design issues
Flow Control: Flow control in loss less and lossy channels using stop-and-wait, sliding window protocols. Performance of protocols used for flow control.
Error Control Coding: Error Detection, Two Dimensional Parity Checks, and Internet Checksum. Polynomial Codes, Standardized polynomial codes, error detecting capability of a polynomial codes. Linear codes, performance of linear codes, error detection & correction using linear codes.
Data Link Control: HDLC & PPP including frame structures.
MAC sublayer: Channel Allocation Problem, Pure and slotted Aloha, CSMA, CSMA/CD, collision free multiple access. Throughput analysis of pure and slotted Aloha. Ethernet Performance.
Wireless LAN: Hidden node and Exposed node Problems, RTS/CTS based protocol, 802.11 Architecture, protocol stack, Physical layer, MAC Sublayer.
Bluetooth Architecture and Protocol Stack Data Link Layer Switching: Bridges (Transparent, Learning and Spanning Tree), Virtual LANs
Multiplexing: Frequency division, time division (Synchronous and statistical) multiplexing. ADSL, DS1 and DS3 carriers.
Multiple Accesses: TDMA frame structure, TDMA Burst Structure, TDMA Frame efficiency, TDMA Superframe structure, Frame acquisition and synchronization, Slip rate in digital terrestrial networks.
Switching: Qualitative description of Space division, time division and space-time- space division switching.
Spread Spectrum Techniques: Direct sequence(DSSS) & frequency hopping(FHSS); Performance consideration in DSSS & FHSS; Code division Multiple access (CDMA): frequency & channel specifications, forward & reverse CDMA channel, pseudo noise(PN) sequences, m-sequence, gold sequence, orthogonal code, gold sequences, Walsh codes, synchronization, power control, handoff, capacity of CDMA system, IMT-2000, WCDM.
Text/Reference Books :
- Stallings, Data and computer communication, 8th Pearson
- T.Ha, Digital Satellite Communications, 2/e, Tata McGraw Hill
- Alberto Leon-Garcia, Indra Widjaja, COMMUNICATION NETWORKS, 2nd e, TMH
- Wireless Communications, 2/e, Rappaport, PHI
Database Management System
INTRODUCTION TO DATABASE SYSTEMS: Overview and History of DBMS. File System v/s DBMS .Advantage of DBMS Describing and Storing Data in a DBMS. Queries in DBMS. Structure of a DBMS.
ENTITY RELATIONSHIP MODEL: Overview of Data Design Entities, Attributes and Entity Sets, Relationship and Relationship Sets. Features of the ER Model- Key Constraints, Participation Constraints, Weak Entities, Class Hierarchies, Aggregation, Conceptual Data Base, Design with ER Model-Entity v/s Attribute, Entity vs Relationship Binary vs Ternary Relationship and Aggregation v/s ternary Relationship Conceptual Design for a Large Enterprise.
RELATIONSHIP ALGEBRA AND CALCULUS: Relationship Algebra Selection and Projection, Set Operations, Renaming, Joints, Division, Relation Calculus, Expressive Power of Algebra and Calculus.
SQL QUERIES PROGRAMMING AND TRIGGERS: The Forms of a Basic SQL Query, Union, Intersection and Except, Nested Queries ,Correlated Nested Queries, Set-Comparison Operations, Aggregate Operators, Null Values and Embedded SQL, Dynamic SQL, ODBC and JDBC, Triggers and Active Databases.
SCHEMA REFINEMENT AND NORMAL FORMS: Introductions to Schema Refinement, Functional Dependencies, Boyce-Codd Normal Forms, Third Normal Form, Normalization-Decomposition into BCNF Decomposition into 3-NF.
Text/Reference Books :
- f. Korth and Silberschatz: Database Systems Concepts, McGraw Hill
- Almasri and S.B. Navathe: Fundamentals of Database Systems,
- J. Date: Data Base Design, Addison Wesley
- Hansen and Hansen : DBM and Design, PHI
Introduction and need of operating system, layered architecture/logical structure of operating system, Type of OS, operating system as resource manager and virtual machine, OS services, BIOS, System Calls/Monitor Calls, Firmware- BIOS, Boot Strap Loader.
Process management- Process model, creation, termination, states & transitions, hierarchy, context switching, process implementation, process control block, Basic System calls- Linux & Windows. Threads- processes versus threads, threading, concepts, models, kernel & user level threads, thread usage, benefits, multithreading models.
Interprocess communication- Introduction to message passing, Race condition, critical section problem, mutual exclusion with busy waiting- disabling interrupts, lock variables, strict alteration, Peterson’s solution, TSL instructions, busy waiting, sleep and wakeup calls, semaphore, monitors, classical IPC problems.
Process scheduling- Basic concepts, classification, CPU and I/O bound, CPU scheduler- short, medium, long-term, dispatcher, scheduling:- preemptive and non-preemptive, Static and Dynamic Priority, Co-operative & Non-cooperative, Criteria/Goals/Performance Metrics, scheduling algorithms- FCFS, SJFS, shortest remaining time, Round robin, Priority scheduling, multilevel queue scheduling, multilevel feedback queue scheduling, Fair share scheduling.
Deadlock- System model, resource types, deadlock problem, deadlock characterization , methods for deadlock handling, deadlock prevention, deadlock avoidance, deadlock detection, recovery from deadlock.
Memory management- concepts, functions, logical and physical address space, address binding, degree of multiprogramming, swapping, static & dynamic loading- creating a load module, loading, static & dynamic linking, shared libraries, memory allocation schemes- first fit, next fit, best fit, worst fit, quick fit. Free space management- bitmap, link list/free list, buddy’s system, memory protection and sharing, relocation and address translation.
Virtual Memory- concept, virtual address space, paging scheme, pure segmentatio n and segmentation with paging scheme hardware support and implementation details, memory fragmentation, demand paging, pre-paging, working set model, page fault frequency, thrashing, page replacement algorithms- optimal, NRU, FIFO, second chance, LRU, LRU- approximation clock, WS clock; Belady’s anomaly, distance string; design issues for paging system- local versus global allocation policies, load control, page size, separate instruction and data spaces, shared pages, cleaning policy, TLB ( translation look aside buffer) reach, inverted page table, I/O interlock, program structure, page fault handling, Basic idea of MM in Linux & windows.
File System- concepts, naming, attributes, operations, types, structure, file organization & access(Sequential, Direct ,Index Sequential) methods, memory mapped files, directory structures- one level, two level, hierarchical/tree, acyclic graph, general graph, file system mounting, file sharing, path name, directory operations, overview of file system in Linux & windows.
Input/Output subsystems- concepts, functions/goals, input/output devices- block and character, spooling, disk structure & operation, disk attachment, disk storage capacity, disk scheduling algorithm- FCFS, SSTF, scan scheduling, C-scan schedule.
Text/Reference Books :
- Silberschatz and Peter B Galvin: Operating System Principals, Wiley India Pvt. Ltd.
- Achyut S Godbole: Operating Systems, Tata McGraw Hill
- Tanenbaum: Modern Operating System, Prentice
- DM Dhamdhere: Operating Systems – A Concepts Based Approach, Tata McGraw Hill
- Charles Crowly: Operating System A Design – Oriented Approach, Tata McGraw
Advanced Data Structures
ADVANCED TREES: Definitions, Operations on Weight Balanced Trees (Huffman Trees), 2-3 Trees and Red- Black Trees. Dynamic Order Statistics, Interval Tree; Dictionaries.
MERGEABLE HEAPS: Mergeable Heap Operations, Binomial Trees, Implementing Binomial Heaps and its Operations, 2-3-4. Trees and 2-3-4 Heaps. Amortization analysis and Potential Function of Fibonacci Heap, Implementing Fibonacci Heap.
GRAPH THEORY DEFINITIONS: Definitions of Isomorphic Components. Circuits, Fundamental Circuits, Cut-sets. Cut- Vertices Planer and Dual graphs, Spanning Trees, Kuratovski’s two Graphs.
GRAPH THEORY ALGORITHMS: Algorithms for Connectedness, Finding all Spanning Trees in a Weighted Graph, Breadth First and Depth First Search, Topological Sort, Strongly Connected Components and Articulation Point. Single Min-Cut Max-Flow theorem of Network Flows. Ford-Fulkerson Max Flow Algorithms.
SORTING NETWORK: Comparison network, zero-one principle, bitonic sorting and merging network sorter.
Priority Queues and Concatenable Queues using 2-3 Trees. Operations on Disjoint sets and its union-find problem, Implementing Sets.
NUMBER THEORITIC ALGORITHM: Number theoretic notions, Division theorem, GCD, recursion, Modular arithmetic, Solving Modular Linear equation, Chinese Remainder Theorem, power of an element, Computation of Discrete Logarithms, primality Testing and Integer Factorization.
Text/Reference Books :
- Cormen, Leiserson, Rivest: Introduction to Algorithms, Prentice Hall of
- Horowitz and Sahani: Fundamental of Computer
- Aho V , J.D Ulman: Design and analysis of Algorithms, Addison Wesley
- Brassard : Fundamental of Algorithmics PHI
Digital Signal Processing
INTRODUCTION : Discrete time signals and systems, properties of discrete time systems, Linear time invariant systems – discrete time. Properties of LTI systems and their block diagrams. Convolution, Discrete time systems described by difference equations.
Fourier Transform: Discrete time Fourier transform for periodic and aperiodic signals. Properties of DTFT. Z-transform: The region of convergence for the Z- transform. The Inverse Z-transform. Properties of Z transform.
SAMPLING: Mathematical theory of sampling. Sampling theorem. Ideal & Practical sampling. Interpolation technique for the reconstruction of a signal from its samples. Aliasing. Sampling in freq. domain. Sampling of discrete time signals.
THE DISCRETE FOURIER TRANSFORMS (DFT): Properties of the DFT, Linear Convolution using DFT. Efficient computation of the DFT: Decimation– in-Time and Decimation-in frequency FFT Algorithms.
FILTER DESIGN TECHNIQUES: Structures for discrete-time systems- Block diagram and signal flow graph representation of LCCD (LCCD – Linear Constant Coefficient Difference) equations, Basic structures for IIR and FIR systems, Transposed forms. Introduction to filter Design: Butterworth & Chebyshev.IIR filter design by impulse invariance & Bilinear transformation. Design of FIR filters by Windowing: Rectangular, Hamming & Kaiser.
Text/Reference Books :
- Oppenheim, Discrete-Time Signal Processing, 2/e, Pearson Education
- Proakis, Digital Signal Processing, 4/e, Pearson Education
- K.Mitra, Digital Signal Processing, 2/e, Tata McGraw Hill
Information Theory And Coding
Introduction to information theory. Uncertainty, Information and Entropy, Information measures for continuous random variables, source coding theorem. Discrete Memory less channels, Mutual information, Conditional entropy.
Source coding schemes for data compaction: Prefix code, Huffman code, Shanon-Fane code & Hempel-Ziv coding channel capacity. Channel coding theorem. Shannon limit.
Linear Block Code: Introduction to error connecting codes, coding & decoding of linear block code, minimum distance consideration, conversion of non systematic form of matrices into systematic form.
Cyclic Code: Code Algebra, Basic properties of Galois fields (GF) polynomial operations over Galois fields, generating cyclic code by generating polynomial, parity check polynomial. Encoder & decoder for cyclic codes.
Convolutional Code: Convolutional encoders of different rates. Code Tree, Trllis and state diagram. Maximum likelihood decoding of convolutional code: The viterbi Algorithm fee distance of a convolutional code.
Text/Reference Books :
- Digital Communication, Simon Haykin,