# NIT-RAIPUR

## IV SEM Information Technology Syllabus

**SEMESTER – IV**

**Probability, Statistics and Queuing Theory”**

**Theory Periods: 30 Tutorials: “10”**

**Credits: 4 Code: IT 401**

UNIT I

Probability:

Definitions of probability, Addition theorem, Conditional probability, Multiplication

theorem, Bayes theorem of probability and Geometric probability, Random variables and their

properties, Discrete Random variable, Continuous Random variable, Probability Distribution, joint

probability distributions their properties, Transformation variables, Mathematical expectations,

probability generating functions.

UNIT II

Probability Distributions / Discrete distributions:

Binomial, Poisson Negative binominal

distributions and their properties. (Definition, mean, variance, moment generating function.,

Additive properties, fitting of the distribution.), Continuous distributions: Uniform, Normal,

exponential distributions and their properties. Curve fitting using Principle of Least Squares.

UNIT III

Multivariate Analysis:

Correlation, correlation coefficient, Rank correlation, Regression Analysis,

Multiple Regression, Attributes, coefficient of Association,

?2 – test for goodness of fit, test for

independence, Sample, populations, statistic, parameter, Sampling distribution, standard error,

unbiasedness, efficiency, Maximum likelihood estimator, notion & interval estimation.

UNIT IV

Testing of Hypothesis:

Formulation of Null hypothesis, critical region, level of significance, power of

the test. Small Sample Tests: Testing equality of .means, testing equality of variances, test of

correlation coefficient, test for Regression Coefficient. Large Sample tests: Tests based on normal

distribution.

UNIT V

Queuing theory:

Queue description, characteristics of a queuing model, study state solutions of

M/M/1:

? Model,

M/M/1: N Model.

Name of Text Books:

1.

Probability, Statistics and Random Processes by T.Veerarajan, Tata McGraw Hill.

Name of Reference Books:

1.

Probability & Statistics with Reliability, Queuing and Computer Applications by Kishor S.

Trivedi , Prentice Hall of India ,1999.

2.

An Introduction to Queuing Systems, S.K. Bose, Kluwer Academic / Plenum Publishers, 2002

NATIONAL INSTITUTE OF TECHNOLOGY, RAIPUR, CG 492010

Department of Information Technology

SEMESTER – IV

“

Discrete Structures”

Theory Periods: 30 Tutorials: “10”

Credits: 4 Code: IT 402

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, First Order Predicate Logic.

UNIT – II: SET THEORY, RELATIONS, FUNCTIONS

Basic concept of set theory, Relations, Properties of relation in a set, Equivalence relation,

Composition of relations, Partial order & total order relations, Lattices & Hasse diagram,

Introduction to function, Inverse, Identity, Injective, Surjective & Bijective functions, Composition of

functions and some special functions.

UNIT – III: GROUP THEORY

Binary Operation, Algebraic Structure, Semi groups, Monoid, Groups, Abelian Groups, Finite

Groups, Addition and Multiplication Modulo, Order of Group, Subgroups, Permutation Group,

Cyclic Group, Cosets, Lagrange’s theorem, some theorems on sub groups, Isomorphism,

Automorphism, Homomorphism of groups, Normal Subgroup, Quotient group.

UNIT – IV: GRAPH THEORY

Introduction to graph theory, Types of graphs (Simple, Di-Graph, Non-Directed Graph , MultiGraph

, Connected, Regular, Cycle, Cyclic, Acyclic, Complete, Wheel, Bi-partite & Complete Bi-Partite),

Complement of Graph, Eulerian, Hamiltonian, Isomorphic graphs, Planarity (Region & Properties),

Polyhedral Graph, kuratowski`s theorem, Coloring, Matchings & Coverings, Spanning Tree,

Connectivity (Edge & Vertex).

UNIT – V: COMBINATORICS AND PROBABILITY

Permutation and combination, Counting & Summation, Pigeon-hole principle, Mathematical

induction, Principle of Inclusion and Exclusion, Generating function, Recurrence relation.

Probability:

Conditional Probability; Mean, Median, Mode and Standard Deviation; Random Variables;

Distributions; uniform, normal, exponential, Poisson, Binomial.

Name of 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, Pearson Education.

Name of Reference Books:

1.

A Text Book of Discrete Mathematics, Swapan Kumar Sarkar, S. Chand & Compeny Ltd.

2.

Graph theory with applications to engineering and computer science, by Narsingh Deo,

Prentice Hall of India.

3.

Discrete mathematics for computer scientists and mathematicians, by J.L. Mott, A. Kandel and

T.P. Baker, Prentice Hall of India.

4.

Discrete Mathematical Structures with applications to computer science, by J.P. Tremblay and

R. Manohar,, Tata McGraw-Hill.

NATIONAL INSTITUTE OF TECHNOLOGY, RAIPUR, CG 492010

Department of Information Technology

SEMESTER – IV

“

Computer Organization”

Theory Periods: 30 Tutorials: “10”

Credits: 4 Code: IT 403

Unit I: Processor Basics

CPU Organization, Fundamental and features, Data representation – Basic formats, Fixed and

Floating point representation, Instruction set, formats, types and programming considerations,

Addressing modes.

Unit II: Data Path Design

Fixed point arithmetic multiplication algorithms: hardware algorithms, Booth multiplication

algorithm, Division algorithm: Hardware algorithm, Divide overflow algorithm, Combinational ALU

and Sequential ALU, Floating point arithmetic operations

Unit III: Control Design

Basic concepts, Hard-wired control, Micro Programmed Control, CPU control Unit and Multiplier

Control Unit, Pipeline control: Instruction pipelines, Pipeline Performance, Superscalar processing.

Unit IV: Memory Organization

Memory Device Characteristics, RAM Technologies 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 I/O

processors, Parallel Processing: Processor-level Parallelism, Multiprocessor and Fault Tolerance

System.

Name of Text Books:

1.

Computer System Architecture By, M. Morris Mano Prentice- Hall, 1993.

2.

Computer Architecture & Organization By John P. Hayes, McGraw Hill-1998

Name of Reference Books:

1.

Structured Computer Organization by Andrew S. Tanenbaum.

2.

Computer architecture a quantitative approach, Patterson D. A. and Hennessy, J. L., Second

Edition, Morgan Kaufman, 1996.

3.

Computer Organization and Architecture, W. Stallings, LPE

NATIONAL INSTITUTE OF TECHNOLOGY, RAIPUR, CG 492010

Department of Information Technology

SEMESTER – IV

“

Principles of Communication System”

Theory Periods: 30 Tutorials: “10”

Credits: 4 Code: IT 404

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, AM demodulation,The Square law

demodulator, PLL, Nonsinusoidal modulation, DSBSC Modulation, SSB modulation and generation

& demodulation, 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 FM.

Armstrong and Parameter variation methods of FM generation and FM demodulators.

UNIT – III : Digital Communication

Sampling theorem, Pulse Modulation: PAM, PPM, PWM, Digital Base Band Modulation technique:

Bandwidth of digital data, Base band System, Formatting textual data, messages, characters &

symbols, Formatting Analogue information, source of corruption, PCM, Uniform & Non-uniform

Quantization, Base band modulation, Correlative Coding, Formatting Analogue information, DPCM,

Delta Modulation

UNIT – IV : Digital Modulation Techniques

Fundamentals of Binary ASK, PSK, FSK, Generation & detection of BASK, BPSK, BFSK,

Fundamentals of QPSK & DPSK, Generation & detection of QPSK & DPSK, MSK, M-ary PSK

signaling schemes, Equalization Principles, Optimum filter, Matched filter, Error probability of

various Digital Modulation technique.

UNIT – V : 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.

Satellite Communication:

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.

Name of Text Books:

1.

Electronic Communications by Roddy & Coolen, PHI.

2.

Electronic Communication System by Kenedy & Davis, TMH

3.

Modern Digital & Analogue Communication systems, B.P.Lathi, Ed.-3, Oxford Press.

Name of Reference Books:

1.

Principles of Communication system by H.Taub and K.L. Shiling.

2.

An Introduction to the Principle of Communication Theory by J.C. Hancock,Mc-Graw Hill.

3.

Signal Processing, Modulation and Noise -by Betts, English University Press,London.

4.

Communication System-by A.B. Carlson ,Mc-Graw Hill.

NATIONAL INSTITUTE OF TECHNOLOGY, RAIPUR, CG 492010

Department of Information Technology

SEMESTER – IV

“

Theory of Computation”

Theory Periods: 30 Tutorials: “10”

Credits: 5 Code: IT 405

UNIT- I: Machines

Basic machine, FSM , Transition graph, Transition matrix, Deterministic and non-deterministic

FSM’S, Equivalence of DFA and NDFA, Mealy & Moore machines, minimization of finite automata,

Two-way finite automata.

UNIT- II: Regular Sets and Regular Grammars

Alphabet, words, Operations, Regular sets, Finite automata and regular expression, Pumping lemma

and regular sets, Application of pumping lemma, closure properties of regular sets.

UNIT- III: Formal Grammars & Languages

Basic definitions and examples of languages, Chomsky hierarchy, Regular grammars, context free &

context sensitive grammars, context free languages, non-context free languages, Chomskey normal

forms, binary operations on languages.

UNIT- IV: Turing Machines & Pushdown Automata

TM model, representation and languages acceptability of TM Design of TM, Universal TM & Other

modification, composite & iterated TM, Pushdown automata , Acceptance by PDA.

Computability:

Basic concepts, primitive & partial recursive function, Recursive function,

Decidability, Kleen’s theorem.

Unit- V: Undecidibility

Properties of recursive & recursively enumerable languages, Universal Turing machine and an

undecidable problem, Rice’s theorem & some more undecidable problems.

Computational complexity Theory:

Definition, linear speed-up, tape compression & reduction in

number of tapes, Hierarchy Theorem, Relation among complexity measures, Transition lemmas &

non deterministic hierarchies, properties of general complexity measures, the gap, speed-up, union

theorem, Automatic complexity theorem.

Name of Text Books:

1.

John E. Hopcroft, Jeffery Ullman, Introduction to Automata theory, Langauges & computation,

Narosa Publishers.

Name of Reference Books:

1.

E.V. Krishnamurthy, Introductory Theory of computer science.

K.L.P. Mishra, Theory of computer Science, Prentice Hall of India Pvt. Ltd.

NATIONAL INSTITUTE OF TECHNOLOGY, RAIPUR, CG 492010

Department of Information Technology

SEMESTER – IV

“

Operating Systems”

Theory Periods: 30 Tutorials: “10”

Credits: 4 Code: IT 406

UNIT I

Introduction:

Operating system and function, Evolution of operating system, Batch, Interactive,

Time Sharing and Real Time System, System protection.

Operating System Structure:

System Components, System structure, Operating System Services.

UNIT II

Processes:

Process concept, Principle of Concurrency, Producer Consumer Problem, Critical Section

problem, Semaphores, Classical problems in Concurrency, Inter Process Communication, Process

Generation, Process Scheduling.

CPU Scheduling:

Scheduling Concept, Performance Criteria Scheduling Algorithm, Evolution,

Multiprocessor Scheduling.

UNIT III

Deadlock:

Deadlock Characterization, Prevention, Avoidance and Detection, Recovery from

deadlock combined approach.

File System:

File Concept, File Organization and Access Mechanism, File Directories, File Sharing,

Implementation Issues.

UNIT IV

Memory Management:

Multiprogramming with fixed partition, Multiprogramming with variable

partition, Multiple base register, Paging, Segmentation, Virtual memory concept, Demand paging,

Performance, Paged replaced algorithm, Allocation of frames, Thrashing, Cache memory,

Organization, Impact on performance.

UNIT V

I/O Management & Disk Scheduling:

I/O devices and organization of I/O function, I/O Buffering,

Disk I/O, Disk scheduling algorithms,Case study: WINDOWS-NT, Linux, Unix, Inferno

Name of Text Books:

1.

Operating System concepts, Silberscatz A and Peterson, J.L, PE- LPE.

Name of Reference Books:

1.

1.Operating System Design & Implementation, Tanenbaum, A.S., PHI.

2.

Operating system concepts Galvin, Silberscatz John Weiley & Sons

3.

Operating systems H.M.Deital Pearson Education

4.

Operating System Concept & Design, Milenkovic M, McGraw Hill.

5.

Operation System, Stalling William, Maxwell MCMillan International Editions.