# NIT Raipur B-Tech Syllabus 4th Semester Computer Science Engineering

# NIT- RAIPUR

## IV SEM COMPUTER SCIENCE & ENGINEERING SYLLABUS

**MICRO PROCESSOR & INTERFACE**

UNIT – I Microprocessor Architecture

Introduction to Microprocessor and Microcomputer Architecture, Pins & Signals, Register Organization, Timing & Control Module, 8085 Instruction Timing &Execution, 8085 Interrupts. Elementary Concepts of Assemblers & Assembler Directive in 8085.Simple Assembly language Programs using Instruction of 8085.

UNIT – II Fundamentals of Device Interfacing with 8085, Memory Interfacing: –

Interfacing EPROM &RAM memories. Address Decoding, Device Selection, Memory & I/O mapped I/O, Types of I/O. Programmable Interfaces: – 8155, 8255, 8251, 8253. Overview of DMA & DMA controller, Key & Display controller.

UNIT – III Intel 8086 (16 bit processor):-

8086 Architecture, Addressing Modes, Instruction Format, Pins &Signals, 8086 Basic System Concept, Interfacing with Memories, 8086 Interrupts. Simple Assembly language Programs using Instruction of 8086.

UNIT – IV Intel 80386:-

Introduction to 80386 Microprocessor, Architecture, Pins & Signals, Memory System, Registers, Memory Management in 80386, Paging Technique, Protected Mode Operation. Brief Introduction to 80387 Math Coprocessor. Pentium Processor (

**Only Features**): Introduction to Pen tium Processors, Memory System, Input /Output System, Branch Prediction Logic, Floating Point Module, Cache Structure, Superscalar Architecture.

UNIT – V Microcontroller (Architecture and Programming):-

Introduction to 8051 Microcontrollers Architecture, Pin Description), Interrupt of 8051, Assembly Language Programming (Jump, Loop, Call Instructions), I/O Port Programming, 8051 Addressing Modes, Arithmetic & Logic Instructions. Interfacing of Microcontroller with 8255.

TEXT BOOKS:

1. Microprocessor Architecture, Programming and Application by R. S. Gaonkar, Wiley

Eastern.(Unit 1 & 2)

2. Advance Microprocessor and Peripherals (Architecture, Programming & Interfacing)

by A. K.Roy & K. M. Bhurchandi

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

SYLLABUS

DATA STRUCTURE

Unit – I Introduction: Introduction to Data Structures, algorithm evaluation, Algorithm

Complexity and Time-Space trade-off. Arrays:-

Array Definition, Representation and Analysis, Single and Multidimensional Arrays, address calculation, application of arrays, Array as Parameters, Sparse Matrices Representation and its Transpose Algorithm Recursion: Recursive definition and processes, recursion in C, example of recursion, Tower of Hanoi Problem, simulating recursion, Backtracking, recursive algorithms, principles of recursion, tail recursion, removal of recursion.

UNIT – II Stacks:-

Array Representation and Implementation of stack, Operations on Stacks: Push & Pop, Array Representation of Stack, Operations Associated with Stacks, and Application of stack: Conversion of Infix to Prefix and Postfix Expressions, Evaluation of Postfix expression using stack. Queues: Array representation and implementation of queues, Operations on Queue: Create, Add, Delete, Full and Empty, Circular queues, D-queues and Priority Queues.

UNIT – III Linked list:-

Representation and Implementation of Singly Linked Lists, Two-way Header List, Traversing and Searching of Linked List, Overflow and Underflow, Insertion and deletion to/from Linked Lists, Insertion and deletion Algorithms, Doubly linked list, Linked List in Array, Polynomial representation and addition, Generalized linked list, Garbage Collection and Compaction. Linked Representation of Stack & Queues.

UNIT – IV Searching and Hashing:-

Sequential search, binary search, comparison and analysis, Hash Table, Hash Functions, Collision Resolution Strategies, Hash Table Implementation Sorting: Insertion Sort, Bubble Sorting, Quick Sort, Selection sort, Merge sort, Heap sort, maxima and minima heap, Time complexity & memory requirements.

UNIT – V Graphs:

–

Terminology & Representations, Graphs & Multi-graphs, Directed Graphs, Sequential Representations of Graphs, Adjacency Matrices, Path Matrix, Warshall’s algorithm Traversal, Connected Component and Spanning Trees, Minimum Cost Spanning Trees, Topological Sorting. Trees: Basic terminology, Binary Trees, Binary tree representation, algebraic Expressions, Complete Binary Tree, Extended Binary Trees, Array and Linked Representation of Binary trees, Traversing Binary trees, Threaded Binary trees, Traversing Threaded Binary trees, Huffman algorithm.

Reference text books:

1. Data Structures using C/C++ by Langsam, Augenstein & Tananbaum ( PHI ) 2. Data Structure by Seymour Lipschutz & G. a. Vijayalaksmi Pai ( Schaum’s outlines) 3. Data Structures & Program Design by Robert

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING SYLLABUS

OOPS USING C++

UNIT I : Introduction:

Basic concepts of OOP, Benefits of OOP, Object Oriented Language, Structure of C++ Program, Compiling & Linking, Operators & Expressions, Looping Concepts, Arrays & Structures, functions. **UNIT II : Classes & Object**: Specifying a class, Define member function, Scope of class and its member, Nested Class, Data hiding & encapsulation, Friend function, Array within a Class, array of object as function argument, function returning object, static member. **UNIT III: Constructors and Destructors**: Constructor function, parameterized multiple constructor, default constructor, copy constructor, const and class, Data conversion between objects of different classes, Destructor function, Polymorphism, function overloading, Operator overloading. **UNIT IV: Inheritance, Pointer & Virtual function**: Define derived classes, single inheritance, multilevel inheritance, Hierarchical inheritance, Hybrid Inheritance, Pointers to objects, this pointer, Pointers to derived class, Virtual function, Pure Virtual function, Abstract classes. **UNIT V: File I/O & Templates**: files streams, opening & closing a file, read () & write()functions, detecting end-of-file, seekp(), seekg(), tellg(), tellp()function. Introduction to Templates & Exception, Creating and handling Templates and Exception in OOP, Standard template Library. **Name of Text Books **1. OOPS with C++ : E. Balagurusamy 2. OOP with C++: Robort Laphore.

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING SYLLABUS

DISCRETE STRUCTURE

UNIT – I MATHEMATICAL LOGIC & BOOLEAN ALGEBRA

Basic concept of mathematical logic, Statements, Connectives, Conditional and biconditional statements, Logical equivalence, Logical implication & quantifiers, Basic concept of Boolean Algebra, Properties of Boolean Algebra, Boolean functions, Disjunctive & conjunctive normal forms of Boolean functions, Applications of Boolean Algebra in switching circuits & logic circuits, Karnaugh map methed for simplification of Booleen expression. **UNIT –II RELATIONS, FUNCTIONS and Group **Relations, Properties of relation, Partial order and total order relations, Function, Properties of function, composition of function, Recursive functions, Group, Permutation Group, Cyclic group, Sub- group, Cosets, Langranges theorem, Some theorem, on subgroups, Homomorphism and isomorphism of group, Normal sub group, Quotient group **UNIT – III Ring, Field and Element of coding theory **Ring- Definition and examples, subring ,integral domains, field –Definition and examples. Elements of coding theory, parity check code ,Binary Symmetric channel ,Hamming Weight and Distance, Group codes, Parity check and Generator Matrix, Decoding, Hamming Matrices, Coset Decoding, Hamming Codes. **UNIT – IV GRAPH AND LATTICE THEORY **Introduction to graph theory, Walks, Paths & Circuits, Types of graphs, Shortest path problems, Eulerian and Hamiltonian graphs, Basic concept of tree: spanning tree, minimal spanning tree,search tree, rooted binary tree, Cut sets, Network flow, Matrix representation of graph, Partially ordered set, Lattice, Lattice as Algebraic system, Sub lattices , Some Special Lattices. **UNIT – V COMBINATORICS **Permutation and combinations, Pigeon-hole principle, Multimonial Coefficients , Generating function, Recurrence relation, Generating function for combinations, Enumeration for permutations, Partition of an integer, Some special partition generating functions, The principle of inclusion and exclusion, General formula for number of objects having m properties out of r, Derangments, Permutations with restrictions on relative positions, The rook polynomials. **TEXT BOOKS: – **1. Elements of discrete mathematics by C.L. Liu, Tata McGraw-Hill, publications. 2. Discrete Mathematical structures, by Bernard Kolman, Robert C. Busby and Sharon Cutler Ross

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

SYLLABUS

COMPUTER SYSTEM ARCHITECTURE

Unit I: Processor Basics

CPU Organization, Fundamental and features, Data Representation – Basic formats, Fixed and Floating point representation, Instruction Sets, Formats, Types and Programming Considerations, Addressing modes.

Unit II: Datapath Design

Fixed-Point Arithmetic Multiplication Algorithms: Hardware algorithm, Booth Multiplication algorithm, Division algorithms: Hardware algorithm, Divide overflow algorithm, Combinational ALU and Sequential ALU, Floating point arithmetic operations.

Unit III: Control Design

Basic Concepts, Hardwired control, Microprogrammed Control, CPU control unit and Multiplier control unit, Pipeline Control: Instruction Pipelines, Pipeline performance, Superscalar Processing.

Unit IV: Memory Organization

Memory device characteristics, RAM technology and Serial access memories technology, Multilevel memory systems, Address translation and Memory allocation systems, Cache memory: Features, address mapping.

Unit V: System Organization

Communication Method: Basic concepts, Bus Control, Programmed I/O , DMA, Interrupts and IO

Processors, Parallel Processing: Processor-level Parallelism, Multiprocessor and Fault tolerance

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING SYLLABUS

UNIT – I : Amplitude Modulation System

Need for Modulation, Amplitude Modulation, Amplitude Modulation Index, Modulation Index for Sinusoidal AM, Frequency spectrum for Sinusoidal AM, Average power for Sinusoidal AM, Effective voltage and current for sinusoidal AM, Balanced Modulator, The Square law demodulator, Nonsinusoidal modulation, DSBSC Modulation, SSB modulation and generation, VSB, FDM. **UNIT – II : Angle Modulation System **Phase and frequency modulation and their relationship. Frequency deviation, spectrum of FM Signal, BW of FM Signal, Effect of modulation on BW, constant BW, FM phasor diagram, Narrow band F.M. Armstrong and Parameter variation methods of FM generation and FM demodulators. **UNIT – III : Digital Communication **Sampling theorem, Pulse Modulation: PAM, PPM, PWM. Quantization of Signals, Quantization error, Pulse Code Modulation (PCM) and the system, Time division multiplexing (TDM), DPCM, DM, ADM,PSK FSK and DEPSK. **UNIT – IV : Elements of Information Theory **Average Information, Entropy, Information Rate. Communication Channel. Discrete and Continuous channel, Shannon-Hartley Theorem and its Implications, Channel capacity, Gaussian channel. Bandwidth s/N trade off. **UNIT – V : Advanced Communication Techniques **Satellite Communication: Components and Block diagram of Satellite communication system, Transponders, Up-link and Down-link budget calculations. Fiber Optic Communication: Principles of light propagation in optical fiber, Losses in fibers, Dispersion, Connectors and splices, Fiber optic communication link

## Recent Comments