RTU Syllabus for CS
RTU SYLLABUS FOR CS
5CS1 COMPUTER ARCHITECTURE (Common to Comp. Engg. & Info. Tech)

Units 
Contents of the subject 
I 
Introduction to Computer Architecture and Organization. Von Neuman Architecture, Flynn Classification.
Register Transfer and Micro operations: Register transfer language, Arithmetic Microoperations, Logic Microoperations, Shift Microoperations, Bus and memory transfers. Computer Organization and Design: Instruction cycle, computer registers, common bus system, computer instructions, addressing modes, design of a basic computer 
II 
Central Processing Unit: General register organization, stack organization, Instruction formats, Data transfer and manipulation, program control. RISC, CISC characteristics.
Pipeline and Vector processing: Pipeline structure, speedup, efficiency, throughput and bottlenecks. Arithmetic pipeline and Instruction pipeline. 
III 
Computer Arithmetic: Adder, Ripple carry Adder, carry look Ahead Adder, Multiplication: Add and Shift, Array multiplier and Booth Multiplier, Division: restoring and Nonrestoring Techniques. Floating Point Arithmetic: Floating point representation, Add, Subtract, Multiplication, Division. 
IV 
Memory Organization: RAM, ROM, Memory Hierarchy, Organization, Associative memory, Cache memory, and Virtual memory: Paging and Segmentation. 
V 
InputOutput Organization: InputOutput Interface, Modes of Transfer, Priority Interrupt, DMA, IOP processor. 
Text/References:
 1. Computer Organization and Architecture – William Stallings (Pearson Education Asia)
 2. Computer Organization and Architecture John P. Hayes (McGraw Hill)
 3. Computer Organization V. Carl. Hamacher (McGrawHill)
5CS2 Digital Logic Design (Comp. Engg.)

Units  Contents of the subject 
I  Hardware Description Languages and their use in digital logic design.
VHDL: Modelling Concepts, Lexical Elements & Syntax Descriptions, Scalar Data types & Operations, Sequential Statements, Composite Data Types & Operations, Basic Modelling Constructs. Case Study: VHDL Simulation of Ripple Carry, & Look Ahead carry Adders. 
II  VHDL: Subprograms, Packages & Use Clauses, Aliases, Resolved Signals, Components & Configurations, Generate Statements, Concurrent Statements. Use of VHDL in simulation and synthesis. 
III  Clocked Sequential circuits. Design steps for synchronous sequential circuits. Design of a sequence detector. Moore and Mealy Machines. Design using JK flipflops and D flipflops. State reduction, State assignment, Algorithmic State Charts, converting ASM charts to hardware, onehot state assignment. Considerations of clock skew, setup time, holdtime and other flipflop parameters, timing constraints.
Programmable Logic Devices. Readonly memory. Boolean function implementation through ROM. PLD, PGA, PLA, PAL, FPGA. 
IV  Eventdriven Circuits. Design procedure for asynchronous circuits, stable and unstable states, races, racefree assignments. State reduction of incompletely specified machines. Compatibility and state reduction procedure. Hazards in combinational networks. Dynamic hazards, Function Hazards, and Essential Hazards. Eliminating hazards. 
V  Field Programmable Gate Arrays: Introduction, Logic Elements & programmability, Interconnect structures & programmability, Extended Logic Elements, SRAM, Flash Memory & Antifuse Configuration, Case Studies of Altera Stratix & Xilinx VirtexII pro.
Technology Mapping for FPGAs: Logic Synthesis, Lookup Table Technology Mapping. 

 Ashenden, The Designer’s Guide to VHDL, Elsevier.
 Stephen D. Brown, et.al., Field Programmable Gate Arrays, Kluwer Academic Publishers.
 Scott Hauck, Andre DeHon , Reconfigurable computing: the theory and practice of FPGAbased computation, Morgan Kauffman
 Zvi Kohavi: Switching and Finite Automata Theory. TMH.
 Parag K. Lala, Practical Digital Logic Design and Testing. PHI
 Stephen H. Unger, The essence of logic circuits. Wiatrowski & House.
5CS3 TELECOMMUNICATION FUNDAMENTALS (Common to Comp. Engg. & Info. Tech)
Class: V Sem. B.Tech. 
Evaluation 
Branch: Computer Engg. Schedule per Week Lectures: 3  Examination Time = Three (3) Hours Maximum Marks = 100 [Midterm (20) & Endterm (80)1 
I  Data Transmission: Terminology, Frequency, spectrum, bandwidth, analog and digital transmission, Transmission impairments, channel capacity including sampling theorem and Fourier series.
Transmission Media: Transmission of signals through Twisted pair, Coaxial cable, optical fibre (SM, MM, Graded Index). Wireless Transmission: Antenna and antenna gain, introduction to terrestrial and satellite microwave, Propagation of wireless signals, free space loss for LOS communication. Review of Line Encoding Schemes. Concept of bit period, effect of clock skew, Synchronous and Asynchronous communication Network Reference Models (OSI/ISO and TCP/IP) 
II  Data Link Layer: Functions performed by data link layer, Data link Layer design issues Error Control Coding: Error Detection, Two Dimensional Parity Checks, Internet Checksum. Polynomial Codes, Standardized polynomial codes, error detecting capability of a polynomial codes. Linear codes, performance of linear codes, error detection & correction using linear codes. Flow Control: Flow control in loss less and lossy channels using stopandwait, sliding window protocols. Performance of protocols used for flow control. 
III  Data Link Control: HDLC & PPP including frame structures, MAC sublayer: Pure and slotted Aloha, CSMA, CSMA/CD, collision free multiple access. Throughput analysis of pure and slotted Aloha, delay & throughput analysis of CSMA and CSMA/CD 
IV  Multiplexing: Frequency division, time division (Synchronous and statistical) multiplexing. ADSL, DS1 and DS3 carriers. Multiple Accesses: Performance of FDMAFMFDMA, Single channel per carrier. TDMA frame structure, TDMA Burst Structure, TDMA Frame efficiency, TDMA Superframe structure, Frame acquisition and synchronization, Slip rate and in digital terrestrial networks. Switching: Qualitative description of Space division, time division and spacetimespace division switching. 
V  Spread Spectrum Techniques: Direct sequence(DSSS) & frequency hopping(FHSS); Performance consideration in DSSS & FHSS; Code division Multiple access (CDMA): frequency & channel specifications, forward & reverse CDMA channel, pseudo noise(PN) sequences, msequence, gold sequence, orthogonal code, gold sequences, Walsh codes synchronization, power control, handoff, capacity of CDMA system, IMT2000, WCDM 
Text/References: 
 1. Stallings, Data and computer communication, 8^{th} ed. Pearson
 2. Tri.T.Ha, Digital Satellite Communications, 2/e, Tata McGraw Hill
 3. Alberto LeonGarcia, Indra Widjaja, COMMUNICATION NETWORKS, 2^{nd} ed., TMH
 4. Wireless Communications, 2/e, Rappaport, PHI
 5. Analysis of Computer and Communication Networks, ISBN: 0387744363, Fayez Gebali, 2008, Springerverlag, 1st Ed.
5CS4 DATABASE MANAGEMENT SYSTEMS (Common to Comp. Engg. & Info. Tech)
Class: V Sem. B.Tech. 
Evaluation 

Branch: Computer Engg. Schedule per Week Lectures: 3  Examination Time = Three (3) Hours Maximum Marks = 100 [Midterm (20) & Endterm (80)1  
Units 
Contents of the subject  
I 
Introduction: Applications, Purpose, File System v/s DBMS, Data Abstraction (views), Structure of a DBMSQuery Processor, Database Users and Administrator, Data Dictionary, Transaction Manager, Storage Manager. Data Models IntroductionNetwork Model, Hierarchical Model, Relational Model, Entity Relationship Model and Object Oriented Model. [1]
Entity Relationship Model: Structure of RDMS and Database Schema, Entities, Attributes and Entity Sets, Relationship and Relationship Sets, Key Constraints, Participation Constraints (Mapping Cardinalities), Integrity Constraints, Weak Entity Set, Design issues, Extended Features Aggregation, Generalization and Specialization, case study of an Enterprise. [1] 

II 
Relational Algebra: Operations: Selection, Projection, Set, Renaming, Joints, Division. Relational calculus Tuple Relational Calculus, Domain Relational Calculus. [2]
Query Languages: Procedural and Non Procedural, DDL, DCL and DML. SQLClauses, Nested Queries, SQL Functions Single Row Function, Multigroup Functions, Set Operations, Aggregate Operators, Null Values, Embedded SQL, Dynamic SQL. [2] 

III 
Schema Refinement And Normal Forms: Introductions to Schema Refinement, Functional Dependencies, BoyceCodd Normal Forms, Third Normal Form, NormalizationDecomposition into BCNF Decomposition into 3NF, Denormalization, Triggers. [2]
Transaction Processing: IntroductionTransaction State, Transaction properties, Concurrent Executions. Need of Serializability, Conflict vs. View Serializability, Testing for Serializability, Recoverable Schedules, Cascadeless Schedules. [2] 

IV 
Concurrency Control: Implementation of Concurrency: Lockbased protocols, Timestampbased protocols, Validationbased protocols, Deadlock handling,
[1] Database Failure and Recovery: Database Failures, Recovery Schemes: Shadow Paging and Logbased Recovery, Recovery with Concurrent transactions. [1] 

V 
Indexing and Hashing: Basic Concepts, Ordered Indices, B+ Tree Index Files, BTree Index Files, Multiple Key Access, Static Hashing, Dynamic Hashing, Comparison of Ordered Indexing and Hashing, Bitmap Indices, Index Definition in SQL. [1]  
Text/References:
 1. H.f. Korth and Silberschatz: Database Systems Concepts, McGraw Hill
 2. Almasri and S.B. Navathe: Fundamentals of Database Systems,
 3. Ramakrishnan and Gehrke: Database Management System, McGraw Hill
 4. C.J. Date: Data Base Design, Addison Wesley
 5. Hansen and Hansen : DBM and Design, PHI
5CS5 OPERATING SYSTEMS (Common to Comp. Engg. & Info. Tech)
Class: V Sem. B.Tech. 
Evaluation 
Branch: Computer Engg. Schedule per Week Lectures: 3  Examination Time = Three (3) Hours Maximum Marks = 100 [Midterm (20) & Endterm (80)1 
Units  Contents of the subject 
I  Introduction and need of operating system, layered architecture/logical structure of operating system, Type of OS, operating system as resource manager and virtual machine, OS services, BIOS, System Calls/Monitor Calls, Firmware BIOS, Boot Strap Loader.
Process management Process model, creation, termination, states & transitions, hierarchy, context switching, process implementation, process control block, Basic System calls Linux & Windows. Threads processes versus threads, threading, concepts, models, kernel & user level threads, thread usage, benefits, multithreading models. 
II  Interprocess communication Introduction to message passing, Race condition, critical section problem, mutual exclusion with busy waiting disabling interrupts, lock variables, strict alteration, Peterson’s solution, TSL instructions, busy waiting, sleep and wakeup calls, semaphore, monitors, classical IPC problems.
Process scheduling Basic concepts, classification, CPU and I/O bound, CPU scheduler short, medium, longterm, dispatcher, scheduling: preemptive and nonpreemptive, Static and Dynamic Priority, Cooperative & Noncooperative, Criteria/Goals/Performance Metrics, scheduling algorithms FCFS, SJFS, shortest remaining time, Round robin, Priority scheduling, multilevel queue scheduling, multilevel feedback queue scheduling, Fair share scheduling. 
III  Deadlock System model, resource types, deadlock problem, deadlock characterization, methods for deadlock handling, deadlock prevention, deadlock avoidance, deadlock detection, recovery from deadlock.
Memory management concepts, functions, logical and physical address space, address binding, degree of multiprogramming, swapping, static & dynamic loading creating a load module, loading, static & dynamic linking, shared libraries, memory allocation schemes first fit, next fit, best fit, worst fit, quick fit. Free space management bitmap, link list/free list, buddy’s system, memory protection and sharing, relocation and address translation. 
IV  Virtual Memory concept, virtual address space, paging scheme, pure segmentation and segmentation with paging scheme hardware support and implementation details, memory fragmentation, demand paging, prepaging, working set model, page fault frequency, thrashing, page replacement algorithms optimal, NRU, FIFO, second chance, LRU, LRU approximation clock, WS clock; Belady’s anomaly, distance string; design issues for paging system local versus global allocation policies, load control, page size, separate instruction and data spaces, shared pages, cleaning policy, TLB ( translation look aside buffer) reach, inverted page table, I/O interlock, program structure, page fault handling, Basic idea of MM in Linux & windows. 
V  File System concepts, naming, attributes, operations, types, structure, file organization & access(Sequential, Direct ,Index Sequential) methods, memory mapped files, directory structures one level, two level, hierarchical/tree, acyclic graph, general graph, file system mounting, file sharing, path name, directory operations, overview of file system in Linux & windows.
Input/Output subsystems concepts, functions/goals, input/output devices block and character, spooling, disk structure & operation, disk attachment, disk storage capacity, disk scheduling algorithm FCFS, SSTF, scan scheduling, Cscan schedule. 
Text/Reference Books:
 1. A. Silberschatz and Peter B Galvin: Operating System Principals, Wiley India Pvt. Ltd.
 2. Achyut S Godbole: Operating Systems, Tata McGraw Hill
 3. Tanenbaum: Modern Operating System, Prentice Hall.
 4. DM Dhamdhere: Operating Systems – A Concepts Based Approach, Tata McGraw Hill
 5. Charles Crowly: Operating System A Design – Oriented Approach, Tata McGraw Hill.
5CS6.1 ADVANCED DATA STRUCTURE (Common to Comp. Engg. & Info. Tech)
Class: V Sem. B.Tech. 
Evaluation 
Branch: Computer Engg. Schedule per Week Lectures: 3  Examination Time = Three (3) Hours Maximum Marks = 100 [Midterm (20) & Endterm (80)1 
Units  Contents of the subject 
I 
ADVANCED TREES: Definitions, Operations on Weight Balanced Trees (Huffman Trees), 23 Trees and Red Black Trees. Dynamic Order Statistics, Interval Tree; Dictionaries. 
II 
MERGEABLE HEAPS: Mergeable Heap Operations, Binomial Trees, Implementing Binomial Heaps and its Operations, 234. Trees and 234 Heaps. Amortization analysis and Potential Function of Fibonacci Heap, Implementing Fibonacci Heap. 
III 
GRAPH THEORY DEFINITIONS: Definitions of Isomorphic Components. Circuits, Fundamental Circuits, Cutsets. Cut Vertices Planer and Dual graphs, Spanning Trees, Kuratovski’s two Graphs.
GRAPH THEORY ALGORITHMS: Algorithms for Connectedness, Finding all Spanning Trees in a Weighted Graph, Breadth First and Depth First Search, Topological Sort, Strongly Connected Components and Articulation Point. Single MinCut MaxFlow theorem of Network Flows. FordFulkerson Max Flow Algorithms. 
IV 
SORTING NETWORK: Comparison network, zeroone principle, bitonic sorting and merging network sorter.
Priority Queues and Concatenable Queues using 23 Trees. Operations on Disjoint sets and its unionfind problem, Implementing Sets. 
V 
NUMBER THEORITIC ALGORITHM: Number theoretic notions, Division theorem, GCD, recursion, Modular arithmetic, Solving Modular Linear equation, Chinese Remainder Theorem, power of an element, Computation of Discrete Logarithms, primality Testing and Integer Factorization. 
Text/References:
1. Cormen, Leiserson, Rivest: Introduction to Algorithms, Prentice Hall of India.

5CS6.2 DIGITAL SIGNAL PROCESSING (Comp. Engg.)
Class: V Sem. B.Tech. 
Evaluation 
Branch: Computer Engg. Schedule per Week Lectures: 3  Examination Time = Three (3) Hours Maximum Marks = 100 [Midterm (20) & Endterm (80)1 
Units  Contents of the subject 
I 
INTRODUCTION : Discrete time signals and systems, properties of discrete time systems, Linear time invariant systems – discrete time. Properties of LTI systems and their block diagrams. Convolution, Discrete time systems described by difference equations. 
II 
Fourier Transform: Discrete time Fourier transform for periodic and aperiodic signals. Properties of DTFT. Ztransform: The region of convergence for the Z transform. The Inverse Ztransform. Properties of Z transform. 
III 
SAMPLING: Mathematical theory of sampling. Sampling theorem. Ideal & Practical sampling. Interpolation technique for the reconstruction of a signal from its samples. Aliasing. Sampling in freq. domain. Sampling of discrete time signals. 
IV 
THE DISCRETE FOURIER TRANSFORMS (DFT): Properties of the DFT, Linear Convolution using DFT. Efficient computation of the DFT: Decimation inTime and Decimationin frequency FFT Algorithms. 
V 
FILTER DESIGN TECHNIQUES: Structures for discretetime systems Block diagram and signal flow graph representation of LCCD (LCCD – Linear Constant Coefficient Difference) equations, Basic structures for IIR and FIR systems, Transposed forms. Introduction to filter Design: Butterworth & Chebyshev.IIR filter design by impulse invariance & Bilinear transformation. Design of FIR filters by Windowing: Rectangular, Hamming & Kaiser. 
Text/References: 
 1. Oppenheim, DiscreteTime Signal Processing, 2/e, Pearson Education
 2. Proakis, Digital Signal Processing, 4/e, Pearson Education
 3. S.K.Mitra, Digital Signal Processing, 2/e, Tata McGraw Hill
5CS6.3 INFORMATION THEORY & CODING (Comp. Engg.)
Class: V Sem. B.Tech. 
Evaluation 
Branch: Computer Engg. Schedule per Week Lectures: 3  Examination Time = Three (3) Hours Maximum Marks = 100 [Midterm (20) & Endterm (80)1 
Units  Contents of the subject 
I 
Introduction to information theory. Uncertainty, Information and Entropy, Information measures for continuous random variables, source coding theorem. Discrete Memory less channels, Mutual information, Conditional entropy. 
II 
Source coding schemes for data compaction: Prefix code, Huffman code, ShanonFane code & HempelZiv coding channel capacity. Channel coding theorem. Shannon limit. 
III 
Linear Block Code: Introduction to error connecting codes, coding & decoding of linear block code, minimum distance consideration, conversion of non systematic form of matrices into systematic form. 
IV 
Cyclic Code: Code Algebra, Basic properties of Galois fields (GF) polynomial operations over Galois fields, generating cyclic code by generating polynomial, parity check polynomial. Encoder & decoder for cyclic codes. 
V 
Convolutional Code: Convolutional encoders of different rates. Code Tree, Trllis and state diagram. Maximum likelihood decoding of convolutional code: The viterbi Algorithm fee distance of a convolutional code. 
Text/References
 1. Digital Communication, Simon Haykin, Wiley.
5CS7 DATABASE LAB (Common to Comp. Engg. & Info. Tech)

 Stating a database design & application problem.
 Preparing ER diagram
 Finding the data fields to be used in the database.
 Selecting fields for keys.
 Normalizing the database including analysis of functional dependencies.
 Installing and configuring the database server and the front end tools.
 Designing database and writing applications for manipulation of data for a stand alone and shared data base including concepts like concurrency control, transaction roll back, logging, report generation etc.
 Get acquainted with SQL.
In order to achieve the above objectives, it is expected that each students will chose one problem. The implementation shall being with the statement of the objectives to be achieved, preparing ER diagram, designing of database, normalization and finally manipulation of the database including generation of reports, views etc. The problem may first be implemented for a standalone system to be used by a single user.
All the above steps may then be followed for development of a database application to be used by multiple users in a client server environment with access control. The application shall NOT use web techniques.
One exercise may be assigned on creation of table, manipulation of data and report generation using SQL.
Suggested Tools:
For standalone environment, Visual FoxPro or any similar database having both the database and manipulation language may be used.
For multiuser application, MYSql is suggested. However, any other database may also be used. For front end, VB.Net, Java, VB Script or any other convenient but currently used by industry may be chosen.
Indicative List of exercises:
 Student information system for your college.
 Student grievance registration and redressal system.
RAJASTHAN TECHNICAL UNIVERSITY Detailed Syllabus B.Tech. (Comp. Engg.) VVI Sem. 201011
 A video library management system for a shop.
 Inventory management system for a hardware/ sanitary item shop.
 Inventory management system for your college.
 Guarantee management system for the equipments in your college.
5CS8 SYSTEM DESIGNS in UML LAB (Comp. Engg.)

 The students shall be able to use following modules of UML for system
description, implementation and finally for product development.
– Capture a business process model.
– The User Interaction or Use Case Model – describes the boundary and interaction between the system and users. Corresponds in some respects to a requirements model.
– The Interaction or Communication Model – describes how objects in the system will interact with each other to get work done.
– The State or Dynamic Model – State charts describe the states or conditions that classes assume over time. Activity graphs describe the workflows the system will implement.
– The Logical or Class Model – describes the classes and objects that will make up the system.
– The Physical Component Model – describes the software (and sometimes hardware components) that make up the system.
– The Physical Deployment Model – describes the physical architecture and the deployment of components on that hardware architecture.
The students are expected to use the UML models, prepare necessary documents using UML and implement a system. Some hardware products like digital clock, digital camera, washing machine controller, air conditioner controller, an elctronic fan regulator, an elementary mobile phone etc. may also be chosen.
The students shall be assigned one problem on software based systems and another involving software as well as hardware.
5CS9 OPERATING SYSTEMS SIMULATION LAB (Common to Comp. Engg. & Info. Tech)
Class: V Sem. B.Tech.  Evaluation 
Branch: Computer Engg. Schedule per Week Practical Hrs : 3  Examination Time = Four (4) Hours Maximum Marks = 100 [Sessional/Midterm (60) & Endterm (40)1 
Objectives: 
> Understand the basic functions of operating systems.
> In depth knowledge of the algorithms used for implementing the tasks performed by the operating systems.
> Understand & simulate strategies used in Linux & Windows operating systems.
> Develop aptitude for carrying out research in the area of operating system. Suggested Tools:
Operating system simulator MOSS preferably on Linux platform (Available for free download from http://www.ontko.com/moss/).
Recommended Excercises:
 Exercises shall be given on simulation of algorithms used for the tasks performed by the operating systems. Following modules of the simulator may be used:
> Scheduling
> Deadlock
> Memory Management Systems
> File system simulator
Algorithms described in the text may be assigned. The simulation results such as average latency, hit & Miss Ratios or other performance parameters may be computed.
 One exercise shall be on simulation of algorithms reported in the recent conferences/ journals and reproducing the results reported therein.
5CS10 DIGITAL HARDWARE DESIGN LAB (Common to Comp. Engg. & Info. Tech)
Class: V Sem. B.Tech.  Evaluation 
Branch: Computer Engg. Schedule per Week Practical Hrs : 3  Examination Time = Four (4) Hours Maximum Marks = 75 [Sessional/Midterm (45) & Endterm (30)] 
Objectives: At the end of course, the students shall be able to
 Should be able to design datapath for digital systems
 Create a digital system using discrete digital ICs
 Design a hard wired / microprogrammed control circuit
 Simulate a digital datapath in Hardware Description Language
 Understand IC descriptions and select proper IC in a given circuit based on its timing characteristics
Suggested Methodology and tools: Hardware description language like Verilog /VHDL can be used for simulation.
The exercise shall involve design of datapath, its simulation and finally realization on breadboard. Library of digital ICs have to be built. Similarly, manuals of Digital IC families have to be placed in the laboratories for reference by students.
Suggested Execises
 Create a microprocessor from ALU 74181. For this, the students may design a small instruction set and attach necessary registers and suitable control unit to realize a microprocessor.
 Simulate and realize a Cordic calculator.
 Simulate & realize a Four bit Adder
o Design and simulation of a 4bit Adder o VHDL/V erilog HDL (Hardware description language) o Interfacing 7segment decoder
 Combinational Multiplier
o 4×4bit multiplier o BinarytoBCD conversion o Timing Constraints
 CRC checksum generator & verifier
 Realizing a carry look ahead adder
6CS1 COMPUTER NETWORKS (Common to Comp. Engg. & Info. Tech)
Class: VI Sem. B.Tech. 
Evaluation 
Branch: Computer Engg. Schedule per Week Lectures: 3  Examination Time = Three (3) Hours Maximum Marks = 100 [Midterm (20) & Endterm (80)1 
NOTE: The first 2 lectures shall be devoted to review of the basis architectures and responsibilities of different layers.

Text/References: 
 1. Tanenbaum; Computer Network, 4th Ed., Pearson.
 2. Kurose; Computer Networking, 3rd Ed., Pearson.
 3. Peterson, Davie; Computer Networks, 4rd Ed., ELSEVIER 6CS2 DESIGN AND ANALYSIS OF ALGORITHMS (Common to Comp. Engg. &
Info. Tech.)
Class: VI Sem. B.Tech. 
Evaluation 
Branch: Computer Engg. Schedule per Week Lectures: 3  Examination Time = Three (3) Hours Maximum Marks = 100 [Midterm (20) & Endterm (80)] 
Units 
Contents of the subject 
I 
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. 
II 
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. 
III 
PATTERN MATCHING ALGORITHMS: Naive and Rabin Karp string matching algorithms, KMP Matcher and Boyer Moore Algorithms.
ASSIGNMENT PROBLEMS: Formulation of Assignment and Quadratic Assignment Problem. 
IV 
RANDOMIZED ALGORITHMS. Las Vegas algorithms, Monte Carlo algorithms, randomized algorithm for MinCut, randomized algorithm for 2 SAT. Problem definition of Multicommodity flow, Flow shop scheduling and Network capacity assignment problems. 
V 
PROBLEM CLASSES NP, NPHARD AND NPCOMPLETE: Definitions of P, NPHard and NPComplete Problems. Decision Problems. Cook’s Theorem. Proving NPComplete Problems – Satisfiability problem and Vertex Cover Problem. Approximation Algorithms for Vertex Cover and Set Cover Problem. PROBLEM CLASSES NP, NPHARD AND NPCOMPLETE: Definitions of P, NPHard and NPComplete Problems. Decision Problems. Cook’s Theorem. Proving NPComplete Problems – Satisfiability problem and Vertex Cover Problem. Approximation Algorithms for Vertex Cover and Set Cover Problem. 
Text/References: 
 1. Cormen, Leiserson, Rivest: Introduction to Algorithms, Prentice Hall of India.
 2. Horowitz and Sahani: Fundamental of Computer algorithms.
 3. Aho A.V , J.D Ulman: Design and analysis of Algorithms, Addison Wesley
6CS3 THEORY OF COMPUTATION (Common to Comp. Engg. & Info. Tech)
Class: VI Sem. B.Tech. 
Evaluation 
Branch: Computer Engg. Schedule per Week Lectures: 3, Tutorial: 1  Examination Time = Three (3) Hours Maximum Marks = 100 [Midterm (20) & Endterm (80)] 
Units  Contents of the subject 
I 
Finite Automata & Regular Expression: Basic Concepts of finite state system, Deterministic and nondeterministic finite automation and designing regular expressions, relationship between regular expression & Finite automata minimization of finite automation mealy & Moore Machines. 
II 
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. 
III 
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. 
IV 
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. 
V 
Linear bounded Automata Context Sensitive Language: Chomsky Hierarchy of Languages and automata, Basic Definition & descriptions of Theory & Organization of Linear bounded Automata Properties of contextsensitive languages 
Text/References 
 1. Aho, Hopcroft and Ullman, Introduction to Automata Theory, Formal Languages and Computation, Narosa
 2. Cohen, Introduction to Computer Theory, Addison Wesley.
 3. Papadimitriou, Introduction to Theory of Computing, Prentice Hall.
6CS4 PROGRAMMING IN JAVA (Common to Comp. Engg. & Info. Tech)
Class: VI Sem. B.Tech. 
Evaluation 

Branch: Computer Engg. Schedule per Week Lectures: 3  Examination Time = Three (3) Hours Maximum Marks = 100 [Midterm (20) & Endterm (80)1  
Units  Contents of the subject  
I 
JAVA: Introduction to Object Orientated Programming, Abstraction, Object Oriented Programming Principles, Features of JAVA, Introduction to Java byte code, Java Virtual machine.
PROGRAM ELEMENTS: Primitive data types, variables, assignment, arithmetic, short circuit logical operators, Arithmetic operators, bit wise operators, relational operators, Boolean logic operators, the assignment operators, operator precedence, Decision and control statements, arrays. 

II 
CONTROL STATEMENTS: Java’s Selection Statements, if statement, switch statement, Iteration Statements, while, dowhile, for, foreach, Nested Loops, Jump Statements, Using break, Using continue, return.
OBJECTS AND CLASSES: Objects, constructors, returning and passing objects as parameter, Nested and inner classes, Single and Multilevel Inheritance, Extended classes, Access Control, usage of super, Overloading and overriding methods, Abstract classes, Using final with inheritance. 

III 
PACKAGE AND INTERFACES: Defining package, concept of CLASSPATH, access modifiers, importing package, Defining and implementing interfaces.
STRING HANDLING: String constructors, special string operations, character extraction, searching and comparing strings, string Buffer class. 

IV 
EXCEPTION HANDLING: Exception handling fundamentals, Exception types, uncaught exceptions, try, catch and multiple catch statements. Usage of throw, throws and finally .FILE HANDLING: I/O streams, File I/O.  
V 
CONCURRENCY: Processes and Threads, Thread Objects, Defining and Starting a Thread, Pausing Execution with Sleep, Interrupts, Joins, Synchronization. APPLET: Applet Fundamentals, using paint method and drawing polygons.  
Text/References 
 1. Herbert Schildt: JAVA 2 – The Complete Reference, TMH, Delhi
 2. Deitel: How to Program JAVA, PHI
 3. U.K. Chakraborty and D.G. Dastidar: Software and Systems – An Introduction, Wheeler Publishing, Delhi.
 4. Joseph O’Neil and Herb Schildt: Teach Yourself JAVA, TMH, Delhi.
Text Books:
 1. John Davies, MSP430 Microcontroller Basics, Elsevier, 2008.
 2. Andrew N. Sloss et.al. ARM System Developers Guide, ELSEVIER
 3. Muhammad Ali Mazidi et.al., The 8051 Microcontroller & Embedded Systems, Pearson
 4. Embedded System Design, A Unified Hardware/Software Introduction, Frank Vahid / Tony Givargis, 2006 reprint, John Wiley Student Edition.
 5. An Embedded Software Primer, David .E. Simon, Fourth Impression 2007, Pearson Education.
Text/References:
 1. Embedded Microcomputer Systems, Valvano, Thomson.
 2. Performance Issues of an Embedded System http://embedded.com.
 3. Computers As Components: Principles of Embedded Computing System Design, 2^{nd} Edition. Morgan Kauffman.
 4. Multicore Embedded Systems,” edited by Prof. Georgios Kornaros , CRC Press
 5. MSP430 Teaching CDROM, Texas Instruments, 2008 (Includes Power Point foils for Instructors.
 6. can be requested from http://www.uniti.in )
 7. Documentation from www.msp430.com
 8. Course materials on MSP 430 available from Rice University’s “Connexions” system (http://cnx.org)
6CS6.1 ADVANCE TOPICS IN OPERATING SYSTEMS (Common to Comp. Engg. & Info. Tech)
Class: VI Sem. B.Tech. 
Evaluation 
Branch: Computer Engg. Schedule per Week Lectures: 3  Examination Time = Three (3) Hours Maximum Marks = 100 [Midterm (20) & Endterm (80)1 
Units 
Contents of the subject 
I 
Operating system structures – policies & mechanism, Structures monolithic, layered, virtual machines, micro kernel, exokernels, client server model. Examples from Linux & Windows.
Threads Advance Concepts Libraries Pthreads, Win32 threads, Java threads, Introduction to threading issues, system calls, cancellation, signal handling, thread pool, thread specific data, window threads, Linux threads, Solaris Threads. Massage Passing System – Need of Message Passing Systems, design issues, naming, synchronization, Implementationbuffering and delivery; mailboxes; RPC & RMI. Examples Systems – Linux, Windows. 
II 
File System file system layouts, file system implementation, contagious allocation, link list allocation, indexed allocation, file allocation table, virtual file system, directory implementation linear list and hash table. File System reliability and integrity.
I/O system: device drivers/ controllers, busses and interfaces USB, IDE, SCSI, IEEE1394, RAID system, disk caching and buffering, disk managementdisk formatting, RAID Structure, boot block, bad block, swapspace management. System Security: Security Problems, Program Threats, System Network Threats, Cryptography as a Security Tool, User Authentication, Implementing Security Defenses, Firewalling to Protect Systems and Network, Computer Security Classifications. Overview of security in Windows. [4] 
III 
The Linux OS: Unix Vs Linux, Design Principles, Kernel Structure, components Kernel Modules, Shell usage, types; An overview of Process Management, Thread Management and Scheduling, Memory Management, Process Scheduling in Linux, File System structure & implementation, I/O Management, Network File System, Interprocess Communications, Booting and login process, security.[3] 
IV 
The Window OS: Design Principles, System Components Hardware Abstraction layer, Kernel, Executives; Environmental Subsystems MSDOS Environment, 16bit Windows Environment, Win32 API, POSIX subsystem; Exception and Interrupts; An overview ofmemory management, process management and thread; Process Scheduling in Windows; File Systems: Internal Layout, recovery, Volume Management and Fault Tolerance, FAT and NTFS, Security features, window registry, OS organizations.[3] 
V 
Multiprocessor Operating Systems: Architecture of Multiprocessor Systems, Overview of Multiprocessor OS, Kernal Structure and Multiprocessing support in Linux & Windows, Process Synchronization Queued Lock, Spin Lock, Sleep Lock; Process Scheduling.
Multimedia Operating System Introduction to Multimedia & Data Compression concepts, common graphics file formats, common audio file formats; Video server, Process management real time scheduling; Multimedia file systems, Multimedia file storage mechanisms, Video sever organization.[2] Mobile Operating System Windows CE, Palm OS, Symbian OS, JAVA card, Multos. 
Text/Ref 
erence Books: 
Text/Reference Books:
 1. DM Dhamdhere: Operating Systems – A Concepts Based Approach, Tata McGraw Hill
 2. Achyut S Godbole: Operating Systems, Tata McGraw Hill
 3. Tanenbaum: Modern Operating System, Prentice Hall
 4. A. Silberschatz and Peter B Galvin: Operating System Principals, Wiley India Pvt. Ltd.
 5. Charles Crowly: Operating System A Design – Oriented Approach, Tata McGraw Hill.
 6. Bach, Design of Unix Operating Systems.
6CS6.2 ARTIFICIAL INTELLIGENCE (Comp. Engg.)

Units  Contents of the subject 
I  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. 
II  Knowledge Representation, Problems in representing knowledge, knowledge representation using propositional and predicate logic, comparison of propositional and predicate logic, Resolution, refutation, deduction, theorem proving, 