# NIT Raipur B-Tech Syllabus 5th Sem Computer Science Engineering

# NIT-RAIPUR

## V SEM COMPUTER SCIENCE & ENGINEERING SYLLABUS

OPERATING SYSTEM

UNIT–1 INTRODUCTION:

Operation System objective and function, The Evolution of operating Systems, Batch, Multi program, interactive, time sharing and real time systems, Distributed OS, Network OS, Embedded OS, Parallel OS . Operating System Structure- Kernel , Shell, System calls, System Components, operating system service, Distributed Computing, The Key Architecture Trend; Parallel Computation, Input-Output Trends.

UNIT-2 PROCESS AND CPU SHEDULING:

Process concept:- Introduction, Definitions of “Process”, Process States, Process State Transitions ,The process Control Block ,Operations on Processes, advantages, comparison with program, interrupt Processing, Threads ,multithreading, user level threads, kernel level threads, advantages, comparison with process, CPU scheduling: concepts, types of schedulers, scheduling criteria, and scheduling Algorithms. Algorithm evaluation, Multiprocessor scheduling, Real Time Scheduling.

UNIT- 3 CONCURRENT PROCESSES AND DEAD LOCKS:

Mutual Exclusion, the critical section problem ,Software and Hardware solutions for mutual exclusion, semaphores, Classical problems in concurrency , inter process communication Concurrent Process:- introduction, parallel Processing ,A Control Structure for indicating parallelism, Deadlock-System model, Deadlock characterization. Prevention, Avoidance and Detection, Recovery from deadlock, combined approach.

UNIT-4 MEMORY MANAGEMENT:

Base machine, resident Monitor, multiprogramming with fixed partition, Multiprogramming with variable partitions, Paging, Segmentation, paged – segmentation, Virtual Memory concepts, Demand paging, performance, page Replacement algorithms, Allocation of frames, Thrashing, cache memory organization impact on performance.

UNIT-5 I/O AND FILES MANAGEMENT:

I/O Device and the organization of the I/O function, I/O Buffering, Disk I/O, Disk Sheduling

Algorithms, File system: File Concepts, attributes, operations, File organization and Access

mechanism, disk space allocation methods, Directory structure, free disk space management, File sharing,

**Implementation **issues. Case studies: Unix system, Windows XP.

Text Books:

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

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

SYLLABUS

**DATABASE MANAGEMENT SYSTEM**

UNIT-I INTRODUCTION TO DATA BASE & INDEXING TECHNIQUES: –

Advantages of DBMS, Type of Data Models, Schema and instances, DBMS Architecture and Data Independence, Entity- Relationship Model, Attributes and Keys, Relationship Types, Weak Entity set, Strong Entity Set, Enhanced E–R Modeling, Specialization and Generalization, Indexes, Multi level indexes, Dynamics Multilevel indexes using B trees and B+- Trees.

UNIT-II THE RELATIONAL DATA MODEL & SQL:-

Relational data model concepts, constraints, relational algebra, relational calculus, Tuple relational calculus. SQL: DDL,DML, DCL, Types of constraints, Defining different constraints on a table, Defining & Dropping integrity constraints in the alter table command, View, Index.

UNIT-III DATABASE DESIGN:-

Functional Dependencies and Normalization for Relational Databases: Informal design guidelines for relation schemes, Functional dependencies, Normal forms based on primary keys, General definitions of second and third normal forms, Boyce- Codd normal form, problem related with normal forms & solutions. Multi valued & Join Dependencies, 4th & 5th Normalization.

UNIT-IV QUERY & TRANSACTION PROCESSING:-

Query Processing : Query processing stages , Query interpretation, Query execution plan, Table scans, Fill factor, Multiple index access, Methods for join tables scans, Structure of a query optimizer. Transaction Processing

**: **Types of failures, ACID property, schedules and recoverability, serialbility of schedules, Levels of transaction consistency, Deadlocks, Nested transaction, Transaction benchmarking.

UNIT –V CRASH RECOVERY & CONCURRENCY CONTROL:-

Failure classification, Different type of Recovery techniques & their comparative analysis, deferred update, immediate update, Shadow paging, Check points, On-line backup during database updates. Concurrency Control: Different type of concurrency control techniques & their comparative analysis, Locking techniques, Time- stamp ordering, Multi-version techniques, Optimistic techniques, Multiple granularity.

Text Books:

1. Database system concept, Korth & Sudarshan, MH.

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

SYLLABUS

COMPUTER GRAPHICS & FUNDAMENTAL

UNIT-I OVERVIEW OF GRAPHICS SYSTEM:-

Video display devices, Input devices, Raster scan & Random scan system, line-circle ellipse generating algorithm, filled area primitives, 2-D & 3-D transformation, Clipping:, Liang Barsky 2-D clipping :Cohen Sutherland, Polygon clipping: Sutherland Hodgeman & Weiler-Atherton polygon clipping.

UNIT-II CURVES & SURFACES:-

Conics-Parametric forms for circle, ellipse, parabola, Bezier Curves-Need for cubic parametric curves c0, c1, c2 continuity, Generation though Bernstein polynomials, Condition for smooth joining of 2 segments, Convex Hull property, B-Spline Curves: Knot vectors uniform and open uniform curves, Uniform, Periodic B-splines, Open, Uniform B-splines, Non-uniform, rational B-splines, Beta splines, subdividing curves, Drawing curves using forward differences.

UNIT-III PROJECTIONS & HIDDEN SURFACE REMOVAL:-

Parallel projection on xy-plane(including oblique view), Perspective projection-1, 2 and 3 Vanishing points, Hidden Surface Removal: Back face removal, Floating Horizon method for curved objects, Z-Buffer or depth buffer algorithm, Painter’s algorithm(Depth sorting method), Binary space partitioning trees, Scanline algorithm, Warnock’s algorithm(Area subdivision method).

UNIT-IV SHADING & COLOR ISSUES :-

Illumination model for diffused & specular reflection, Computing reflection vector, Gouraud and Phogtracing, Texture mapping & their characteristics, Basic ray tracing algorithm, Constructive solid geometry methods–Octrees and Fractals, Color issues: Wavelength spectrum, RGB, CMY, HSV color model.

UNIT-V MULTIMEDIA:-

Data Compression requirement, Information Theory based and frequency domain based compression, Basic compression techniques: lossy & lossless compression, Huffman coding, LZW coding, run length coding, DCT, compression of multimedia data.

Animation: In-between using rotation and translation, Procedural animation, Image Transformation- Translation and rotation, Morphing, Motion Control (Key framing), Spline Driven animation.

Text Books :-

1. Computer graphics-Hearn and Baker, PHI

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING SYLLABUS

**DATA COMMUNICATION**

UNIT I – IMPERATIVE PROGRAMMING:

The Role of Programming Languages: – Toward Higher-level Languages, Problems of Scale, Programming Paradigms, Language Implementation Bridging the Gap. Language Description:- Syntactic Structure : Expression Notations, Abstract Syntax Trees, Lexical Syntax, Context -Free Grammars, Grammars for Expressions, Variants of Grammars. Statements: Structured Programming:- The Need for Structured Programming, Syntax-Directed Control Flow, Design Considerations: Syntax, Handling Special Cases in Loops, Programming with invariants, Proof Rules for Partial Correctness, Control flowin C. Types: Data Representation:- The Role of Types, Basic Types, Arrays Sequences of Elements, Records: Named Fields, Unions and variant Records, Sets, Pointers: Efficiency and Dynamic Allocation, Two String Tables, Types and Error Checking. Procedure Activations:- Introduction to Procedures, Parameter-passing Methods, Scope Rules for Names, Nested Scopes in the Source Text, Activation Records, Lexical Scope: Procedures as in C, Lexical Scope: Nested Procedures and Pascal. **UNIT II- OBJECT ORIENTED PROGRAMMING: **Groupings of Data and Operations:- Constructs fro Program Structuring, Information Hiding, Program Design with Modules, Modules and Defined Types, Object-Oriented Programming:- What is an Object? ,Object-Oriented Thinking, Inheritance, Derived Classes and information Hiding. **UNIT III – FUNCTIONAL PROGRAMMING: **Elements of Functional Programming:- A little Language of expressions, Types : Values and Operations, Function declarations, Approaches to Expression Evaluation, Lexical Scope, Type Checking. Functional Programming in a Typed Languages:- Exploring a List, Function Declaration by Cases, Functions as First-Class Values, ML: Implicit Types, Data Types, Exception Handling in M, Little quit in Standard ML. Functional Programming with Lists:- Scheme, a Dialect of Lisp, The Structure of Lists, List Manipulation, A Motivating Example: Differentiation, Simplification of Expressions, Storage Allocation for Lists. **UNIT IV- LOGIC PROGRAMMING **Logic Programming:- Computing with Relations, Introduction to Prolog, Data Structures in Prolog, Programming techniques, Control in Prolog, Cuts. **UNIT V- CONCURRENT PROGRAMMING **An Introduction to Concurrent Programming:- Parallelism in Hardware, Streams: Implicit Synchronization, Concurrency as interleaving, Liveness Properties, Safe Access to Shared Data, Concurrency in Ada, Synchronized Access to Shared variables. **Text Book: **1. Programming Languages –

DEPATMENT OF COMPUTER SCIENCE & ENGINEERING SYLLABUS

THEORY OF COMPUTATION

UNIT-1. THE FINITE AUTOMATA:

Introduction to automata theory, Examples of automata machine, Finite automata as a language acceptor and translator. Deterministic finite automata, Non deterministic finite automata, finite automata with output (Mealy Machine. Moore machine). Finite automata with Epsilon moves, Conversion of NFA to DFA by Arden’s method, Minimizing number of states of a DFA .Properties and limitation of FSM. Two way finite automata. Application of finite automata.

UNIT-2. REGULAR EXPRESSIONS :

Regular expression, Properties of Regular Expression. Finite automata and Regular expressions. Regular Expression to DFA conversion & vice versa. Pumping lemma for regular sets. Application of pumping lemma, My-hill Nerode theorem, Regular sets and Regular grammar. Closure properties of regular sets. Decision algorithm for regular sets and regular grammar.

UNIT-3. GRAMMARS:

Definition and types of grammar. Chomsky hierarchy of grammar. Relation between types of grammars. Role and application areas of grammars. Context free grammar. Left most linear &right most derivation trees. Ambiguity in grammar. Simplification of context free grammar. Chomsky normal from. Greibach normal form, properties of context free language. Pumpinglemma from context free language. Decision algorithm for context tree language.

UNIT-4. PUSH DOWN AUTOMATA AND TURING MACHINE:

Basic definitions. Deterministic push down automata and non deterministic push down automata. Acceptance of push down automata. Push down automata and context free language. Turing machine model. Representation of Turing Machine Construction of Turing Machine for simple problem’s. Universal Turing machine and other modifications.

UNIT-5 COMPUTABILITY:

Introduction and Basic concepts. Recursive function. Partial recursive function. Partial recursive function. Initial functions, computability, A Turing model for computation. Turing computable functions, Construction of Turing machine for computation. Space and time complexity. Recursive enumerable language and sets. Church’s Hypothesis. Post correspondence problem. Halting problem of Turing Machine

Text Books

:

(1) Introduction to Automata theory. Language and Computation, John E. Hopcropt & Jeffery D. Ullman, Narosa Publishing House.

(2) Theory of Computer Science

DEPATMENT OF COMPUTER SCIENCE & ENGINEERING SYLLABUS

OPERATION RESEARCH

UNIT –1 LINEAR PROGRAMMING PROBLEM

Mathematical formulation of L.P.P, Graphical method for solving LP with 2 variables, Simplex method, Application of simplex method for maximization and minimization of LP problems, Artificial variable technique for finding the initial basic feasible solution, The Big-M method, Degeneracy in simplex method, Duality theory in LP, Dual simplex method. **UNIT-2 TRANSPORTATION, ASSIGNMENT AND REPLACEMENT PROBLEMS Transportation: **North – West comer rule, Least cost method, Vogel’s Approximation method, Modi Method, Assignment problem. **Replacement: **Replacement of equipment/Asset that Deteriorates Gradually, Replacement of equipment that fails suddenly, Recruitment and Promotion problem, equipment renewal problem. **UNIT- 3 INVENTORY MODELS **Introduction to the inventory problem, Deterministic models, The classical EOQ (Economic order quantity) model, Purchasing model with no shortage, Manufacturing model with no shortage, purchasing model with shortage, Manufacturing model with shortage, Inventory models with probabilistic demand. **UNIT –4 SEQUENCING AND QUEUING THEORY **Sequencing problem, Johnson’s algorithm for processing N-jobs through 2 machine problem, N-jobs through 3 machine problem, 2- job through N machine by graphical method, Characteristics of queuing system- steady state M/M/1, M/M/1K and M/M/C queuing models. **UNIT- 5 NET WORK ANALYSIS **Introduction, Network and basic Components, logical sequencing, Rules of Network Construction, CPM/PERT Techniques, Critical path method(CPM), Determination of Critical path(Labelling Method), The Project Evaluation and Review Technique(PERT), Probability Considerations in PERT, Distinction between PERT and CPM, Project Cost, Time-Cost Optimization Algorithm. **Name of Text Books:- **1. Operation Research-2ed, Panneerselvam, Prentice Hall of India 2. Operation Research: An Introduction

## Recent Comments