# NIT Raipur Syllabus 6th Semester CSE Branch

NIT-RAIPUR

VI SEMESTER COMPUTER SCIENCE & ENGINEERING

SYLLABUS

ANALYSIS & DESIGN OF ALGORITHM

Unit –I

Analyzing algorithms, Algorithm types, Recurrence Equations, Growth function: Asymptotinotation, Standard notation & common functions, Recurrence relation, different methods of solution of recurrence equations with examples.

Unit –II

Introduction to Divide and Conquer paradigm, Quick and merge sorting techniques, Linear time selection algorithm, the basic divide and conquer algorithm for matrix multiplication Strassen Multiplication and, Red Black tree, Binary Search tree , heap sort, shell & bucket sort.

Unit –III

Overview of the greedy paradigm examples of exact optimization solution (minimum cost spanning tree), Knapsack problem, Single source shortest paths. Overview, difference between dynamic programming and divide and conquer, Applications: Shortest path in graph, Matrix multiplication, Traveling salesman Problem, longest Common sequence

.

Unit –IV

Representational issues in graphs, Depth first search & Breath first search on graphs, Computation of biconnected components and strongly connected components using DFS, Topological sorting of nodes of an acyclic graph & applications, Shortest Path Algorithms , Bellman-Ford algorithm, Dijkstra’s algorithm & Analysis of Dijkstra’s algorithm using heaps, Floyd-Warshall’s all pairs shortest path algorithm

Unit –V

The general string problem as a finite automata, Knuth Morris and Pratt algorithms, Linear time analysis of the KMP algorithm, The Boyer-Moore algorithm. Backtracking & Recursive backtracking, Applications of backtracking paradigm ,Complexity measures, Polynomial Vs non polynomial time complexity; NP- hard and NP-complete classes, examples.

References:

1. Coreman, Rivest, Lisserson, : “Algorithm”, PHI

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING

COMPUTER NETWORKS

UNIT- I:- INTRODUCTION TO COMPUTER NETWORK: –

Uses of Computer Network, Network hardware, Layered Architecture, function of the layers, OSI & TCP/IP Reference model, Physical layer services & Transmission Media, Guided Media and Unguided Media, Switching technique (Circuit Switching, Message Switching, Packet Switching) and its timing diagram.

UNIT –II:- DATA LINK CONTROL: –

Framing, Flow Control : Stop and wait Protocols, Sliding Window Protocols. Error Detection & Error Control, High Level Data Link Control ( HDLC),MAC Protocols: Pure ALOHA & Slotted ALOHA, CSMA, CSMA/CD, IEEE Standards(IEEE 802.3, IEEE 802.4, IEEE 802.5), FDDI : access method , addressing, electrical specification, frame format, comparison of FDDI-I & FDDI-II . DQDB.

UNIT-III :- NETWORK LAYER :-

Network Layer Protocols: Design issues : Virtual Circuits and datagram’s, Repeaters, Bridge Routers & Gateways, Routing Algorithms: Optimality principle, Shortest path routing- Dijkstra’s algorithms, Distance Vector routing, Link state routing, Flow and Congestion Control: packet discarding , Traffic shaping , Choke packets, RSVP, IP fragment, RIP, OSPF, IP protocol, IP addresses, ARP, RARP, ICMP, Mobile IP.

UNIT-IV:- TRANSPORT LAYER:-

Functions of the transport layer: end to end delivery, addressing, reliable delivery, flow control, multiplexing, Connection Management : Establishment and releases , Crash recovery, TCP & UDP, Wireless TCP and UDP.

UNIT-V:- UPPER LAYERS: –

Session Layer Protocols

: Dialog Management, Synchronization.

Presentation layer functions

: translation, encryption, compression.

Application layer protocols & services

: Network Security Email, World Wide Web, file

transfer protocol, DNS.

Text Books:-

1. Computer networks”, Second Ed., A.S. Tannenbaum, Prentice Hall India.

2. Data Communication & Networking,

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING SYLLABUS

UNIX & SHELL PROGRAMMING

UNIT – 1: INTRODUCTION :

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING SYLLABUS

SOFTWARE ENGINEERING

UNIT –1 SOFTWARE PROCESS

The Evolving role of Software – Software – The changing Nature of Software –Legacy software ––A generic view of process– A layered Technology – A Process Framework – The Capability Maturity Model Integration (CMMI) – Process Assessment – Personal and Team Process Models. Product and Process. Process Models – The Waterfall Model – Incremental Process Models – Incremental Model – The RAD Model – Evolutionary Process Models – Prototyping – The Spiral Model –The Concurrent Development Model – Specialized Process Models – the Unified Process.

UNIT –2 SOFTWARE REQUIREMENTS

Functional and non-functional requirements – user and system requirement – requirement engineering process-feasibility studies –elicitation and analysis– validation and management – software prototyping– prototyping in the software process – rapid prototyping techniques – user interface prototyping – SRS Analysis and modeling – data, functional and behavioral models – Data Dictionary.

UNIT– 3 DESIGN CONCEPTS AND PRINCIPLES

Design process and concepts – modular design – design heuristic – design model and document. Architectural design, software architecture data design, architectural design transform and transaction mapping – user interface design – user interface design principles, monitoring and Control system. SCM – Need for SCM – Version control – introduction to SCM process – Software Configuration items

UNIT– 4 TESTING & MAINTENANCE

Taxonomy of software testing – levels – test activities – types of s/w test – black box testing – white box testing – testing boundary condition – structural testing –test coverage criteria Based on data flow mechanisms – regression testing – S/W testing strategies – strategic approach and issue – unit testing – integration testing – validation testing – system testing and debugging, SQA, Software Maintenance, Reengineering and Reverse engineering

UNIT – 5 SOFTWARE METRICES AND ESTIMATION

Measures and metrics – S/W complexity and size measure –data and logic structure measure, information

flow measure. Software cost estimation-Function oriented models – COCOMO model-Delphi method – Defining a Task Network – Scheduling Earned Value Analysis – Error Tracking – Risk Management, Software changes – program evolution dynamics software maintenance – Architectural evolution Taxonomy of CASE tools.

Text Book

1. Software engineering – A practitioner’s Approach, Roger S. Pressman, McGraw-Hill International Edition,

5th edition, 2001

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING SYLLABUS

COMPILER DESIGN

UNIT –1 INTRODUCTION:

Introduction to Compiler, Translators, interpreter, cousins of compiler, single and multi-pass compilers, Phases of Compilers, Compiler construction tools, Bootstrapping, cross compilers Lexical Analyzer: Role of Lexical Analyzer, Specification of tokens, Recognition of tokens, Regular expression, Finite automata, regular expression to finite automata transition diagrams, Tool for lexical analyzer LEX. Context free grammars (CFG), simplification of CFGs, ambiguity, left factoring, left recursion.

UNIT-2 SYNTAX ANALYSIS AND PARSING TECHNIQUES:

Introduction to parsing techniques, Bottom-up parsing and top down parsing. Top down Parsing , recursive descent parsing, Predicative Parsing ,Bottom Up Parsing : Operator precedence parsing, LR parsers- Construction of SLR, canonical LR and LALR parsing tables, Construction of SLR parse tables for Ambiguous grammar, the parser Generator tools – YACC, error recovery in top down and bottom up parsing.

UNI–3 SYNTAX DIRECTED TRANSLATION & INTERMEDIATE CODE GENERATION:

Syntax directed definitions, Synthesized and inherited attributes, dependency graph, Construction of syntax trees, bottom up and top down evaluation of attributes, S-attributed and L-attributed definitions ,Postfix notation, Three address codes, quadruples, triples and indirect triples, Translation of assignment statements, control flow, Boolean expression, case statements and Procedure Calls.

UNIT-4 TYPE CHEKING AND RUNTIME ENVIRONMENTS:

Introduction, simple type checker, type conversions, overloading of functions and operators, Source language issues, Storage organization, storage allocation strategies, Parameter passing, symbol tables, dynamic storage allocation techniques,

UNIT–5 CODE OPTIMIZATION & CODE GENERATION:

Basic blocks and flow graphs, Optimization of basic blocks, Loop optimization, Global data flow analysis, Loop invariant computations, DAG representation of basic blocks, Peephole optimization, Issue in the design of Code generator, register allocation, the target machine, and simple Code generator.

Text Books:

1. Compilers-Principles, Techniques and Tools, Alfred V. Aho, Ravi Sethi and Ullman J.D.,Addison Wesley.

2. Principle of Compiler Design,

DEPARTMENT OF COMPUTER SCIENCE & ENGINEERING SYLLABUS

PARALLEL PROCESSOR & COMPUTING

UNIT-I: Introduction & Technique of Parallelism:

Trends towards parallel computing, parallelism in Uni-processor systems, Architectural classification schemes, Amdahl’s law, Moore’s law, Principles of Scalable Performance, Parallel Processing in Memory, Models of Parallel Processing, Cache coherence, Cache coherence Protocols.

UNIT-II: Pipeline & Vector Processing:

Conditions of Parallelism: Data & Resource dependencies, Program flow mechanisms: Control-flow .vs. Data flow computers Principle of pipelining and vector processing: principles of linear pipelining, classification of pipeline processors. General pipelines and reservation tables.

UNIT-III : SIMD & Multiprocessor Architecture:

SIMD Array Processer: Masking & Data Routing mechanisms, Inter-PE communication SIMD Networks: Mesh connected iliac network, Cube interconnection network, Shuffle- Exchange and Omega network, Star versus Dynamic networks. Function Structure: Loosely coupled multiprocessors, Tightly coupled multiprocessors Interconnection network: Time shared or common buses, Crossbar switch& Multiport Memories, Multistage network for multiprocessors, Parallel Memory Organizations: Interleaved Memory configurations.

UNIT-IV: Multiprocessor architecture and Programming:

Emulation and Scheduling, Emulations among Architectures, Distributed Shared Memory ,Data Storage, Input, and Output, Multithreading and Latency Hiding, Parallel I/O Technology, Defect-Level Methods, Fault-Level Methods, Error-Level Methods.

UNIT-V: Parallel System Implementations:

Shared-Memory MIMD Machines, Variations in Shared Memory, MIN-Based BBN Butterfly, Vector-Parallel Cray Y-MP, CC-NUMA Stanford DASH, Message-Passing MIMD Machines, Data-Parallel SIMD Machines.

Name of Text Books:-

1.Computer Architecture & Parallel processing – Kai Hwang 7 Briggs.(MGH).

2.Parallel Computers Arch.& Prog- Rajaraman & Siva Ram Murthy, PHI.

3. Introduction to Parallel Processing: Algorithms and Architectures-B.Parhami

Name of Reference Books :-