# RTU Computer Science Engineering Syllabus 6th Sem 2017

**Computer Networks**

Unit-1

Network layer-design issue, routing algorithms: Distance vector, link state, hierarchical, Broadcast routing.

Congestion control: congestion prevention policies, congestion control in Datagram subnets, load shedding, jitter control, Leaky bucket and token bucket algorithms.

Unit-2

Internetworking: Differences in networks, Tunneling, Internetwork routing, Fragmentation Network layer in the Internet: IPv4 classful and classless addressing, subnetting Network layer protocols(only working and purpose; packet headers etc. not included), Differences in IPV6 over IPV4. Routing to Mobile Hosts and Mobile IP

Unit-3

Elements of transport protocols: addressing, connection establishment and release, flow control and buffering, multiplexing and demultiplexing, crash recovery, introduction to UDP protocol.

Principles of Reliable Data Transfer: Reliable data transfer over a perfectly reliable channel, Channel with bit errors and Lossy Channel with bit errors.

Unit-4

Transport Layer in the Internet: Introduction to TCP, TCP service Model, TCP Header and segment structure, TCP connection establishment and release, transmission policy, timer management, Transactional TCP. Mobile TCP

TCP Congestion Control: Fairness, TCP delay modeling.

Unit-5

Application Layer: World Wide Web (WWW), Domain Name System (DNS), E-mail, File Transfer Protocol (FTP), Introduction to Network security.

P2P File Sharing: Centralized Directory, Query flooding, exploiting heterogeneity.

Text/Reference Books :

Tanenbaum; Computer Network, 4th , Pearson.

Kurose; Computer Networking, 3rd , Pearson.

Peterson, Davie; Computer Networks, 4rd , ELSEVIER

**Design And Analysis Of Algorithm**

Unit-1

BACKGROUND: Review of Algorithm Complexity, Order Notations: definitions and calculating complexity.

DIVIDE AND CONQUER METHOD: Binary Search, Merge Sort, Quick sort and Strassen’s matrix multiplication algorithms.

GREEDY METHOD: Knapsack Problem, Job Sequencing, Optimal Merge Patterns and Minimal Spanning Trees.

Unit-2

DYNAMIC PROGRAMMING: Matrix Chain Multiplication. Longest Common Subsequence and 0/1 Knapsack Problem.

BRANCH AND BOUND: Traveling Salesman Problem and Lower Bound Theory. Backtracking Algorithms and queens problem.

Unit-3

PATTERN MATCHING ALGORITHMS: Naïve and Rabin Karp string matching algorithms, KMP Matcher and Boyer Moore Algorithms.

ASSIGNMENT PROBLEMS: Formulation of Assignment and Quadratic Assignment Problem.

Unit-4

RANDOMIZED ALGORITHMS. Las Vegas algorithms, Monte Carlo algorithms, randomized algorithm for Min-Cut, randomized algorithm for 2- SAT. Problem definition of Multicommodity flow, Flow shop scheduling and Network capacity assignment problems.

Unit-5

PROBLEM CLASSES NP, NP-HARD AND NP-COMPLETE: Definitions of P, NP-Hard and NP-Complete Problems. Decision Problems. Cook’s Theorem. Proving NP-Complete Problems – Satisfiability problem and Vertex Cover Problem. Approximation Algorithms for Vertex Cover and Set Cover Problem.

Text/Reference Books :

Cormen, Leiserson, Rivest: Introduction to Algorithms, Prentice Hall of India

**THEORY OF COMPUTATION**

Unit-1

Finite Automata & Regular Expression: Basic Concepts of finite state system, Deterministic and non-deterministic finite automation and designing regular expressions, relationship between regular expression & Finite automata minimization of finite automation mealy & Moore Machines.

Unit-2

Regular Sets of Regular Grammars: Basic Definition of Formal Language and Grammars. Regular Sets and Regular Grammars, closure proportion of regular sets, Pumping lemma for regular sets, decision Algorithms for regular sets, Myhell_Nerod Theory & Organization of Finite Automata.

Unit-3

Context Free Languages& Pushdown Automata: Context Free Grammars – Derivations and Languages – Relationship between derivation and derivation trees – ambiguity – simplification of CEG – Greiback Normal form – Chomsky normal forms – Problems related to CNF and GNF Pushdown Automata: Definitions – Moves – Instantaneous descriptions – Deterministic pushdown automata – Pushdown automata and CFL – pumping lemma for CFL – Applications of pumping Lemma.

Unit-4

Turing Machines: Turing machines – Computable Languages and functions – Turing Machine constructions – Storage in finite control – multiple tracks – checking of symbols – subroutines – two way infinite tape. Undecidability: Properties of recursive and Recursively enumerable languages – Universal Turing Machines as an undecidable problem – Universal Languages – Rice’s Theorems.

Unit-5

Linear bounded Automata Context Sensitive Language: Chomsky Hierarchy of Languages and automata, Basic Definition & descriptions of Theory & Organization of Linear bounded Automata Properties of context-sensitive languages.

Text/Reference Books :

Aho, Hopcroft and Ullman, Introduction to Automata Theory, Formal Languages and Computation, Narosa

Cohen, Introduction to Computer Theory, Addison

Papadimitriou, Introduction to Theory of Computing, Prentice

**Computer Graphics And Multimedia Techniques**

Unit-1

Introduction to Raster scan displays, Storage tube displays, refreshing, flicking, interlacing, color monitors, display processors, resolution, Introduction to Interactive. Computer Graphics: Picture analysis, Overview of programmer’s model of interactive graphics, Fundamental problems in geometry. Scan Conversion: point, line, circle, ellipse polygon, Aliasing, and introduction to Anti Aliasing (No anti aliasing algorithm).

Unit-2

2D & 3D Co-ordinate system: Homogeneous Co-ordinates, Translation, Rotation, Scaling, Reflection, Inverse transformation, Composite transformation. Polygon Representation, Flood Filling, Boundary filling.

Point Clipping, Cohen-Sutherland Line Clipping Algorithm, Polygon Clipping algorithms.

Unit-3

Hidden Lines & Surfaces: Image and Object space, Depth Buffer Methods, Hidden Facets removal, Scan line algorithm, Area based algorithms.

Curves and Splines: Parametric and Non parametric Representations, Bezier curve, B- Spline Curves.

Unit-4

Rendering: Basic illumination model, diffuse reflection, specular reflection, phong shading, Gourand shading, ray tracing, color models like RGB, YIQ, CMY, HSV

Unit-5

Multimedia components, Multimedia Input/Output Technologies: Storage and retrieval technologies, Architectural and telecommunication considerations.

Animation: Introduction, Rules, problems and Animation techniques.

Text/Reference Books :

Foley, A. Van Dam, S. Feiner, J. Hughes: Computer Graphics- Principles and Practice, Pearson

Hearn and Baker: Computer Graphics, PHI

Multimedia Systems Design, Prabhat Andleigh and Thakkar

**Embedded Systems Design**

Unit-1

Introduction to embedded systems hardware needs; typical and advanced, timing diagrams, memories (RAM, ROM, EPROM). Tristate devices, Buses, DMA, UART and PLD’s. Built-ins on the microprocessor.

Unit-2

Interrupts basics, ISR;Context saving, shared data problem. Atomic and critical section, Interrupt latency. Survey of software architectures, Round Robin, Function queue scheduling architecture, Use of real time operating system.

Unit-3

RTOS, Tasks, Scheduler, Shared data reentrancy, priority inversion, mutex binary semaphore and counting semaphore. Inter task communication, message queue, mailboxes and pipes, timer functions, events. Interrupt routines in an RTOS environment.

Unit-4

Embedded system software design using an RTOS. Hard real-time and soft real time system principles, Task division, need of interrupt routines, shared data.

Unit-5

Embedded Software development tools. Host and target systems, cross compilers, linkers, locators for embedded systems. Getting embedded software in to the target system. Debugging techniques. Testing on host machine, Instruction set emulators, logic analysers. In-circuit emulators and monitors.

Text/Reference Books :

John Davies, MSP430 Microcontroller Basics, Elsevier,

Andrew Sloss et.al. ARM System Developers Guide, ELSEVIER

Muhammad Ali Mazidi et.al., The 8051 Microcontroller & Embedded Systems, Pearson

Embedded System Design, A Unified Hardware/Software Introduction, Frank Vahid / Tony Givargis, 2006

**Artificial Intelligence**

Unit-1

Meaning and definition of artificial intelligence, Various types of production systems, Characteristics of production systems, Study and comparison of breadth first search and depth first search. Techniques, other Search Techniques like hill Climbing, Best first Search. A* algorithm, AO* algorithms etc, and various types of control strategies.

Unit-2

Knowledge Representation, Problems in representing knowledge, knowledge representation using propositional and predicate logic, comparison of propositional and predicate logic, Resolution, refutation, deduction, theorem proving, inferencing, monotonic and nonmonotonic reasoning.

Unit-3

Probabilistic reasoning, Baye’s theorem, semantic networks scripts schemas, frames, conceptual dependency and fuzzy logic, forward and backward reasoning.

Unit-4

Game playing techniques like minimax procedure, alpha-beta cut-offs etc, planning, Study of the block world problem in robotics, Introduction to understanding and natural languages processing.

Unit-5

Introduction to learning, Various techniques used in learning, introduction to neural networks, applications of neural networks, common sense, reasoning, some example of expert systems.

Text/Reference Books :

Artificial Intelligence: Elaine Rich, Kevin Knight, Mc-Graw

Introduction to AI & Expert System: Dan W. Patterson,

Artificial Intelligence by Luger (Pearson Education)

Russel & Norvig, Artificial Intelligence: A Modern Approach, Prentice-Hall

**Human Computer Interface**

Unit-1

The Human: input-output channels, Human memory, thinking, emotions, individual differences, psychology and the design of interactive systems.

The Computer: Text entry devices with focus on the design of key boards, positioning, pointing and drawing, display devices.

The Interaction: Models of interaction, ergonomics, interaction styles, elements of WIMP interfaces, interactivity, experience, engagement and fun. Paradigms for Interaction.

Unit-2

Design Process: The process of design, user focus, scenarios, navigation design screen design and layout, iteration & prototyping. Usability Engineering

Design rules: Principles to support usability, standards, guidelines, rules and heuristics, HCI patterns.

Unit-3

Evaluation Techniques: Definition and goals of evaluation, evaluation through expert analysis and user participation, choosing an evaluation method.

User support, requirement, approaches, adaptive help systems, designing user support systems

Unit-4

Cognitive methods: Goals and task hierarchies, linguistic models, challenges of display based systems, physical and device models, cognitive architectures.

Unit-5

Communications and collaborations models: Face to Face communication, conversations, Text based communication, group working.

Task Analysis: Differences between task analysis and other techniques, task decomposition, knowledge based analysis, ER based analysis, sources of information and data collection, use of task analysis.

Text/Reference Books :

Human Computer Interaction; Alan Dix et.al, 3rd ed., Pearson

**JAVA Programming Lab**

Experiments :

1. Develop an in depth understanding of programming in Java: data types, variables, operators, operator precedence, Decision and control statements, arrays, switch statement, Iteration Statements, Jump Statements, Using break, Using continue, return.

2. Write Object Oriented programs in Java: Objects, Classes constructors, returning and passing objects as parameter, Inheritance, Access Control, Using super, final with inheritance Overloading and overriding methods, Abstract classes, Extended classes.

3. Develop understanding to developing packages & Interfaces in Java: Package, concept of CLASSPATH, access modifiers, importing package, Defining and implementing interfaces.

4. Develop understanding to developing Strings and exception handling: String constructors, special string operations, character extraction, searching and comparing strings, string Buffer class. Exception handling fundamentals, Exception types, uncaught exceptions, try, catch and multiple catch statements. Usage of throw, throws and finally.

5. Develop applications involving file handling: I/O streams, File I/O.

6. Develop applications involving concurrency: Processes and Threads, Thread Objects, Defining and Starting a Thread, Pausing Execution with Sleep, Interrupts, Joins, and Synchronization.

7. Develop applications involving Applet: Applet Fundamentals, using paint method and drawing polygons.

**Computer Graphics & Multimedia Lab**

1 Implementation of Line, Circle and ellipse attributes

2 Two Dimensional transformations – Translation, Rotation, Scaling, Reflection, Shear

3 Composite 2D Transformations

4 Cohen Sutherland 2D line clipping and Windowing

5 Sutherland – Hodgeman Polygon clipping Algorithm

6 Three dimensional transformations – Translation, Rotation, Scaling

7 Composite 3D transformations

8 Drawing three dimensional objects and Scenes

9 Generating Fractal images

10 To plot a point (pixel) on the screen

11 To draw a straight line using DDA Algorithm

12 Implementation of mid-point circle generating Algorithm

13 Implementation of ellipse generating Algorithm

14 To translate an object with translation parameters in X and Y directions

15 To scale an object with scaling factors along X and Y directions

16 To rotate an object with a certain angle about origin

17 Perform the rotation of an object with certain angle about an arbitrary point