Appendix – I:
Study and Evaluation Scheme
UPTU M. Tech. - CS/IT
SEMESTER-1 |
|
S.N.
|
Course Code
|
Subject
|
Periods
|
Evaluation Scheme
|
Subject Total
|
|||||
Sessional |
ESE
|
|
||||||||
|
|
|
Theory
|
L
|
T
|
Lab
|
CT
|
TA
|
Total
|
Total
|
|
|
1.
|
CS/IT
11
|
Foundations
of Computer Science
|
3
|
1
|
|
20
|
30
|
50
|
100
|
150
|
|
2.
|
CS/IT
12
|
Computer
Organization and Architecture
|
3
|
1
|
|
20
|
30
|
50
|
100
|
150
|
|
3.
|
CS/IT
13
|
OS
and DBMS
|
3
|
1
|
2
|
20
|
30*
|
50
|
100
|
150
|
|
4.
|
CS/IT
14
|
Data
Networks
|
3
|
1
|
2
|
20
|
30*
|
50
|
100
|
150
|
|
|
|
Total
|
12
|
4
|
4
|
|
|
200
|
400
|
600
|
* 30
marks are kept for tutorials, assignments, quizzes and lab
UPTU M. Tech. – CS/IT
SEMESTER-II |
|
S.N.
|
Course Code
|
Subject
|
Periods
|
Evaluation Scheme
|
Subject Total
|
|||||
Sessional |
ESE
|
|
||||||||
|
|
|
Theory
|
L
|
T
|
Lab
(*)
|
CT
|
TA
|
Total
|
Total
|
|
|
1.
|
CS/IT
2xy **
|
Elective
– 1
|
3
|
1
|
|
20
|
30*
|
|
100
|
150
|
|
2.
|
CS/IT
2xy **
|
Elective
– 2
|
3
|
1
|
|
20
|
30*
|
|
100
|
150
|
|
3.
|
CS/IT
2xy **
|
Elective
- 3
|
3
|
1
|
|
20
|
30*
|
|
100
|
150
|
|
4.
|
CS/IT
2xy **
|
Elective
- 4
|
3
|
1
|
|
20
|
30*
|
|
100
|
150
|
|
|
|
Total
|
12
|
4
|
|
|
|
200
|
400
|
600
|
* 30 marks are kept for tutorials,
assignments, quizzes and lab
** Refer the list of streams and their
respective courses for the values of x and y
(*) The existence of 2 periods of lab for
elective will be decided as per the nature of the elective
UPTU M. Tech. – CS/IT
SEMESTER-III |
|
S.N.
|
Course Code
|
Subject
|
Periods
|
Evaluation Scheme
|
Subject Total
|
|||||
Sessional |
ESE
|
|
||||||||
|
|
|
Theory
|
L
|
T
|
Lab
(*)
|
CT
|
TA
|
Total
|
Total
|
|
|
1.
|
CS/IT
3xy **
|
Elective
– 5
|
3
|
1
|
|
20
|
30*
|
50
|
100
|
150
|
|
2.
|
CS/IT
3xy **
|
Elective
– 6
|
3
|
1
|
|
20
|
30*
|
50
|
100
|
150
|
|
3.
|
CS/IT
31
|
Professional
Aspects in Software Engineering
|
2
|
-
|
-
|
50
|
-
|
50
|
-
|
50
|
|
4.
|
CS/IT
32
|
Seminar
|
-
|
-
|
-
|
-
|
-
|
50
|
-
|
50
|
|
5.
|
CS/IT
33
|
Dissertation
|
-
|
-
|
|
-
|
-
|
100
|
-
|
100
|
|
|
|
Total |
8
|
2
|
|
-
|
-
|
300
|
200
|
500
|
* 30
marks are kept for tutorials, assignments, quizzes and lab
** Refer the list of streams and their
respective courses for the values of x and y
(*) The existence of 2 periods of lab for
elective/dissertation will be decided as per the nature of the
elective/dissertation
UPTU M. Tech. – CS/IT
SEMESTER-IV |
|
S.N.
|
Course Code
|
Subject
|
Periods
|
Evaluation Scheme
|
Subject Total
|
|||||
Sessional |
ESE
|
|
||||||||
|
|
|
Theory
|
L
|
T
|
Lab
(*)
|
CT
|
TA
|
Total
|
Total
|
|
|
1.
|
CS/IT
41
|
Dissertation
|
-
|
-
|
|
-
|
-
|
100
|
200
|
300
|
|
|
|
Total |
|
|
|
|
|
100
|
200
|
300
|
(*) The existence and duration of lab will be
decided as per the nature of the dissertation
Stream |
Subject |
Value of xy for subject code |
PrerequisiteElective Subject |
Distributed Systems |
Distributed Computing
|
11
|
|
|
|
Mobile Computing
|
12
|
|
|
|
Analysis & Design
of Real-Time Systems
|
13
|
|
|
|
Dedicated System
Design
|
14
|
|
|
|
VLSI Design
|
15
|
|
|
|
|
|
|
Software Engineering |
Engineering and
Testing Structured
Systems
|
21
|
|
|
|
Object-Oriented
Programming
|
22
|
|
|
|
Engineering Object
Oriented Systems
|
23
|
OOP
|
|
|
Multimedia System
|
24
|
|
|
|
Internet Programming
and Web Service Engineering
|
25
|
|
|
|
|
|
|
Information Systems |
Conceptual Modeling
|
31
|
|
|
|
Requirements
Engineering
|
32
|
ETSS/CM
|
|
|
Method Engineering
|
33
|
ETSS/CM
|
|
|
Process Engineering
|
34
|
ETSS
|
|
|
Simulation and
Modeling
|
35
|
|
|
|
|
|
|
Data Management |
Distributed DBMS
|
41
|
|
|
|
Data Warehousing
|
42
|
|
|
|
Multimedia Databases
|
43
|
|
|
|
|
|
|
|
AI
|
AI
|
51
|
|
|
|
Data Mining
|
52
|
AI
|
|
|
Knowledge Based
System
|
53
|
AI
|
|
|
Natural Language
Processing
|
54
|
AI
|
|
|
|
|
|
|
Theoretical CS
|
Parallel Algorithms
|
61
|
|
|
|
Randomized Algorithms
|
62
|
|
|
|
Approximation
Algorithms
|
63
|
|
|
|
Complexity Theory
|
64
|
|
|
|
Computational
Geometry
|
65
|
|
|
|
|
|
|
|
Security
|
Cryptography
|
71
|
|
|
|
Network and System
Security
|
72
|
Cryptography
|
|
|
Digital Forensic
|
73
|
Cryptography
|
NOTE: The
students are required to select courses from at least three streams.
CS students have to select at least one course each
from Theoretical CS and from Distributed Systems.
IT students have to select at least one course each
from Software Engineering, Information Systems and Data Management.
CS/IT 11 FOUNDATIONS OF COMPUTER SCIENCE
SECTION A: Discrete Mathematical Structure
15 Hours
Algebraic Structures:
Semigroups, Monoids, Groups, Substructures and
Morphisms, Rings, Fields, Lattices, distributive, modular and complemented
lattice, Boolean Algebras.
Formal Logic:
Propositional logic: Predicate
logic, limitations of predicate logic, universal and existential
quantification; modus ponens and modus tollens. Proof technique: Notions of
Implication, converse, inverse, contra positive, negations and contradiction
Introduction to Counting
Basic counting techniques, principles of inclusion and
exclusion, permutations, combinations, summations, probability, Recurrence
Relations, Generating Functions.
Introduction to Graphs:
Graphs and their basic properties,
Eulerian and Hamiltonian walk, graph colouring, planar graph, enumeration,
vector graph
References
- Kenneth Rosen, Discrete Mathematics and its application, TMH
- C.L. Liu , Element of Discrete mathematics ,TMH
- D.B. West ,Introduction to Graph Theory ,PHI
- J.P.Trebley and R.Manohar , Discrete Mathematical Structure with Applications to computer science, TMH
SECTION B: Data Structures and Algorithm
15 Hours
Algorithm and Complexity,
Notation of complexity. Sorting and Divide and Conquer Strategy: Merge-Sort,
Quick Sort with average case analysis. Heaps and heap sort. Lower bound on
comparison –based sorting
Advanced search Structures:
Representation, Insertion and Deletion operations on Red-Black trees, B-Trees,
Hashing
Dynamic programming , matrix
multiplications, longest common subsequence, Greedy method, Knapsack Problem, 8
queens Problems , Backtracking, branch and bound , Fibonacci Heap
Graph Algorithm
Graphs and their representation.
BFS, DFS, Minimum spanning trees, shortest paths Kruskal and Prim’s algorithms,
connected components.
References
1.Coreman ,Leiserson and Rivest,
Algorithm , MIT Press
2.E. Horowithz and S. Sahni , Fundamentals of Computer Algorithm, Galgottia
3.Donald Knuth,, The Art of
Computing Programming –vol-1 and 3 ,Pearson
4.V.Aho, J.E.Hopcroft and Ullman,
Design and Analysis of Computer Algorithm ,Addison Wesley
5.K. Melhorrn, Datastructures and
Algorithms, Vol II Springer Verlag
SECTION C: Theory of Computation
15 Hours
Regular Languages
Alphabet Langauges and grammars,
Regular grammars, regular expressions and finite auotomata, deterministic and
non-deterministic. Closure and decision properties of regular sets. Pumping
lemma of regular sets. Minimization of finite automata.
Context free Language
Context free grammars and pushdown
automata. Chomsky and Griebach normal forms. Cook, younger and Kasami
Algorithm, Ambiguity and properties of context free languages pumping lemma.
Deterministic pushdown automata. Closure properties of deterministic context
free languages.
Turing Machine
Turing machines and variation of
turing machine model, Halting problem, Universal turing machine, Type 0
Languages. Linear bounded automata and context sensitive languages. Turing
Computable functions, Church Turing hypothesis. Recursive and recursively
enumerable sets, Universal Turing machine and undecidable problems, Rice’s
Theorems for RE sets, Undecidability of Post correspondence problem. Valid and
invalid computations of Turing machines, undecidable properties of context free
language problems, Basics of Recursive function theory.
References
1. C. Papadimitrou and C.L. Lewis
Elements of Theory of Computation,PHI
2. J.E. Hopcroft and J.D. Ullman,
Introduction to Automata Theory,Languages of Computations, Addison-Wesley
CS/IT 12 COMPUTER ORGANIZATION & ARCHITECTURE
Computer Organization
Unit I 10
Hours
Basic Computer Organization and design: Instruction set Principles: Classifying
Instruction set Architectures, Memory Addressing , Type and Size of operands,
Operations in the instruction set; Instruction Codes, Computer Register,
Register , Register Transfer Language, time and Control , Instruction Cycle,
Memory references instructions, Input Output and Interrupt, Design of Basic
Computer and Arithmetic and Logic Unit.
Micro programmed Control: Control Memory, address Sequencing,
Design of Control unit
Central Processing Unit: General Register Organization, Stack Organization, Instruction
format, Data Transfer and manipulations program control.
Unit 2 8
Hours
Computer Arithmetic: Addition, Subtraction, Multiplication and
Division Algorithms. Floating point arithmetic operation, IEEE-754, Decimal
arithmetic unit and Decimal Arithmetic operations.
Unit 3
Input- Output Organization: Peripheral Devices, Input–Output Interface,
Asynchronous data transfer, Modes & Transfer, Priority interrupt, Direct
Memory access, I/O Performance Measures, Benchmarks of Storage Performance and
Availability.
Memory Organization: Memory Hierarchy, Main Memory, Auxiliary
Memory, Associative Memory, Shared Cache memory
Cache Memory and its performance,
Reducing Cache Miss Penalty, Reducing Miss Rate, Reducing cache Miss Penalty or
Miss Rate via Parallelism, Reducing Hit Time, Virtual Memory
Computer Architecture
Unit 4
Principle of Scalable Performance: Performance metric and measures, speedup
performance laws, scalability analysis and approaches. Parallel processing and
application
Advanced Processor Technology: Design space of processors,
Instruction set architectures, CISC, RISC
Pipelining: Linear and Non-Linear pipeline processors, Instruction
pipeline design, arithmetic pipeline design, super scalar and super pipeline
design, Superscalar and Vector processors.
Unit 5
Multiprocessor system
Interconnects, Cache coherence and synchronization and mechanisms, message
passing mechanism
System Interconnect Architecture: network property and routing,
static connection network and dynamic connection network.
REFERENCES
1. Mano M: computer System
Architecture –PHI 3rd Edition
2. Henessy J L, Patterson D A:
Computer Architecture: A Quantitative approach – 3rd (Elsevier)
3. Kai Hwang: Advanced Computer
Architecture TMH
4. Hamacher V C, et al: Computer
Organization – 4 Edition (McGraw Hill)
CS/IT 13 OPERATING SYSTEM AND DATABASE MANAGEMENT SYSTEM
Unit I 10
Hours
Operating System: Structure,
Components and Services, Time Sharing and Real-Time System, process Management,
Concurrency Critical Section, Semaphores, InterProcess Communication, Process
scheduling producer/ consumer and reader writer problem, Concept of Distributed
and Real-Time operating system.
Unit II 8
Hours
CPU Scheduling: Concept and Scheduling algorithm, multiprocessor
scheduling, deadlock prevention, avoidance and detection, recovery from
deadlock.
Memory Management: Multiprogramming with fixed partition,
multiprogramming with variable partition, segmentation virtual memory and
demand paging. Page Replacement Policies Thrashing and pre-paging
Unit III 10
Hours
I/O Management, File System: File
organization and access mechanism, file sharing and file directories, Case
Study of Linux Kernel- File Management, Memory Management and Process
Management
Unit IV 10
Hours
Overview of Database Management
System, Data Model- Relational Algebra,
Relational Calculus –Tuple Relation Calculus and Domain Relation Calculus,
Normal Forms
SQL, DDL, DCL DML, PL/SQL
Unit V 7
Hours
Deadlock – Prevention and avoidance, Transaction and Data Recovery
Method. Introduction of Object Oriented DBMS, Object Relational DBMS,
Distributed DBMS and Data mining & Data warehousing
References:
1. A.S. Tanenbaum: “Modern Operating System” , Prentice Hall
2. William Stalling: “Operating System” Maxwell McMellon
3. J. Peterson ,A. Silberschatz and P. Galvin: Operating System Concepts,
Addison Wesley ,3rd edition
4. Milenkovic :Operating System Concept ,TMH
5. Korth and Silberschatz :Database System Concept; Second
Edition, Tata McgrawHill,1991
6. R. Elmasri and N.Navathe :Benjamin Cumming, Fundamental
of Database System , 2nd 1994
7. Boveti et al:Understanding the Linux Kernel 3rd
O’Reilly
8.C.J. Date Database management Systems.
PCS/IT 14 DATA NETWORK
Unit-I Overview of Wired and
Wireless DataNetworks 8
Hours
Review of Layered Network
Architecture ,ISO-OSI and TCP/IP Network Model Datagram Networks and Virtual
Circuit Networks, Point to Point and Point to Multipoint Networks
Layer 2 Switches.
IEEE 802.3U(Fast Ethernet) and IEEE 802.3Z(Gigabit Ethernet)
Virtual LAN
Wireless LAN: IEEE 802.11,
Bluetooth
Broadband Wireless LAN : 802.16,
WIMAX
Unit-II Internetworking 10
Hours
Review of IP Addressing and
Routing
Internet Architecture :Layers 3
Switch, Edge Router and Core Router
Overview of Control Plane, Data
Plane ,Management Plane
Internet Routing Protocols: OSPF, BGP
Broadcast and Multicast Routing: Flooding, Reverse Path Forwarding, Pruning,
Core based trees, PIM
Mobility Issues and Mobile IP
Adhoc Routing: Dynamic Source Routing, Destination Sequenced
Distance Vector Routing, Hierarchial Routing
Signalling :Introduction
,ICMP,LDP and MPLS Architecture
Unit III Transport Layer Protocols 7
Hours
Process to Process Delivery
Review of UDP, TCP
SCTP Protocol: Services, Features, Packet Format, Association,
Error Control Wireless TCP and RTP, RTCP
Real Time Application: Voice and Video over IP
Unit-IV Traffic Control and Quality of Service 12 Hours
Flow Control: Flow Model, Open Loop: Rate Control, LBAP, Closed
Loop: Window scheme, TCP and SCTP Flow Control
Congestion Control: Congestion Control in packet networks, ECN and
RED Algorithm, TCP and SCTP Congestion Control
Quality of Service: IP Traffic Models, Classes and Subclasses,
Scheduling: GPS, WRR, DRR, WFQ, PGPS, VC Algorithm; Integrated Services
Architecture, Differentiated Services Architecture, RSVP and RSVP- TE
Traffic Management Framework: Scheduling, Renegotiation, Signaling,
Admission Control, Capacity Planning
Unit-V 8
Hours
Security Issues,
Symmetric Encryption: DES ,
TripleDES ,Modes, AES
Public Key Encryption: RSA , Diffie
Hellman, Elliptic Curve
Hashing :MDS , SHA-1 , DSA
Protocols: Kerberos,SSL/TLS,
IPSec
Reference
- Srinivasan Keshav” An Engineering Approach To Computer Networking “,Pearson
- W. Richard Stevens “TCP/IP ILLustrated “-Vol1 Pearson
- D. Bertsekas , R Gallagar ,”Data Networks and Internets” PHI
- W. Stalling “High Speed Networks and Internets”, Pearson
- W. Stallings, “ Wireless Communication and Networks” Pearson
- W. Stallings,” Cryptography and Networks Security”,Pearson
- A. Tanenenbaum, “ Computer Network”,PHI
Appendix II:
Streams and their Courses
1. Distributed
Stream
Distributed Computing
Basic Concepts 6 Hours
Characterization, Resource Sharing, Internet Implementations, Name
Resolution, DNS
Computation: Full Asynchronism and Full Synchronism, Computation on
Anonymous Systems, Events, Orders, Global States, Complexity
Distributed Synchronization 8
Hours
Processes and Threads, IEEE POSIX.1c
Mutual Exclusion: Classification, Algorithms,
Mutual Exclusion in Shared Memory; Clock Synchronization, NTP
Distributed Deadlock: Detection Methods, Prevention
Methods, Avoidance Methods
BSD Sockets 8 Hours
TCP/IP Model, BSD Sockets Overview, TCP Sockets and Client/Server, UDP
Sockets and Client/Server, Out of Band Data, Raw Sockets, PING & TRACEROUTE
Programs, Routing, Multicasting using UDP Sockets
Distributed OS 10
Hours
Communication between distributed objects, RPC Model and Implementation
Issues, Sun RPC, Events and Notifications, Java RMI and its Applications
CORBA Architecture: Introduction and Applications
Distributed File System Design and Case Studies: NFS, Coda, Google FS
Distributed Databases 8 Hours
Introduction, Structure, Data Models, Query
Processing, Transactions, Nested Transactions, Atomic Commit Protocols,
Transaction Recovery, Transactions with replicated data, Concurrency Control
Methods, Distributed Deadlocks
References:
1. Tanenbaum, “Distributed Systems”, Pearson
2 W Richard
Stevens, “UNIX Network Programming Vol 1 & 2”, Pearson
3. Sinha, ”Distributed Operating Systems”, Prentice
Hall of India/ IEEE Press
4. Barbosa, “Distributed Algorithms”, MIT Press
5. Ceri, Palgatti,”Distributed Databases”,
McGraw-Hill
Mobile Computing
Introduction 8 Hours
Basic Concepts, Principles of Cellular
Communication, Overview of 1G, 2G, 2.5G, 3G and 4G technologies, GSM and CDMA
Architecture, Mobility Management, Mobile Devices: PDA, Mobile OS: Palm OS,
Mobile Linux Initiative, Symbian.
Process
Migration 8
Hours
Kernel Support for Migration: Mobility Enhancement
in modern UNIX Systems, Transparent Process Migration Design Alternatives,
Removing Process Migration Bottlenecks, Task Migration Issues
User Space support for Migration: Checkpointing,
Process Migration
Data Issues 8
Hours
Workload Balancing Strategies in migration, Process
lifetime distributions for dynamic load balancing, Disconnected Operations in
Coda File System, Weak Connectivity for Mobile File Access, Weakly Connected
Replicated Storage System.
Mobile Data
Networking 8 Hours
Mobile IPv4 and Mobile IPv6, Mobile
Internetworking Architecture, Internet Mobility Issues, Route Optimization,
Performance of Wireless TCP, GPRS Services, IP over CDMA
Mobile
Agents 8 Hours
Basic Concepts, OS support for Mobile Agents, Java
Aglet API, AGENT TCL, Network Aware Mobile Programs, Mobile Objects and Agents,
OMG MASIF Framework, Mobile Agent Security Issues
References:
1. Richard Wheeler, ”Mobility:
Processes, Computers and Agents”
2. Charles Perkins
et.al.,”Mobile IP: Design Principles and Practices”, Pearson
3. Tomasz Imielinski, “Mobile Computing”,
Springer Verlag
Analysis and Design of Real-Time Systems
Basic Concepts 6 Hours
IEEE Definition of Real-Time Systems,
Characterization of Real-Time Systems, Process, IEEE POSIX.1c Threads, Tasks
and Priorities, Pre-emptive and Non-Preemptive Tasks, Soft and Hard Real-Time
Systems
Scheduling 10 Hours
Scheduling Paradigms: Priority Driven, Time Driven,
and Share Driven
Priority Driven Scheduling of Periodic, Aperiodic
and Sporadic tasks
Static Priority Scheduling: Rate Monotonic
Scheduling Algorithm and its exact analysis using Response Time Test
Dynamic Priority Scheduling: Analysis of EDF and
LLF Algorithms and their open issues
Specification
and Verification
10 Hours
Modeling
Real-Time System, Requirement Specification, Assumptions, Design, Basic
Duration Calculus, Specification of Scheduling Policies, Probabilistic Duration
Calculus, Applications of Duration Calculus
RTOS 8
Hours
Introduction, Requirement of Real-Time Guarantees in
industrial applications, Soft and Hard RTOS, Commercial RTOS Examples
IEEE POSIX.1b: Priority Scheduling, Real-Time Signals, Timers, Binary Semaphores, Counting Semaphores, MUTEX operations and usage, Message Passing, Message Queues operations and usage, Shared Memory, Synchronous and Asynchronous I/O, Memory Locking
RTOS Services, Case Studies of Real Time
Capabilities of Linux Kernel 2.6, RTLinux and VxWorks
Applications 6 Hours
Real-Time Application Design, Real-Time Application
Interface (RTAI), Real-Time Java, Real-Time Communications and Networking
References:
1. JWS Liu, “Real-Time
Systems”, Pearson
2. Mathai Joseph, ”Real-Time
Systems: Specification, Verification and Synthesis”, Prentice-Hall
3. Qing Li, “Real-Time
Concepts for Embedded Systems”, CMP Books
4. Krishna,
Shin, “Real-Time Systems”, TMH
5. Burns, Wellings,
“Real-Time Systems and Programming Languages”, Pearson
Dedicated System Design
Review of
Digital Computer & Digital Arithmetic 8
Hours
Algorithm and Algorithmic Notation, Timing,
Synchronization and Memory, Fixed and Floating point Arithmetic
operations, Arithmetic primitives, Sequential and Distributed Arithmetic.
Hardware
Elements and Hardware Design using VHDL 8 Hours
Gates, Flip-Flops, Registers, Synchronization
Signals, Power Consumption and related design rules, Pulse generation and
Interfacing, Chip Technology: Semiconductor Memories, Processors and
Configurable Logic, Chip Level and Board Level Design Considerations
Hardware Design Languages, Simulation of Hardware
Elements using VHDL, Timing Behavior and Simulation, Test Benches, Synthetic
Aspects
Sequential
Control Circuits and Processors 8 Hours
Mealy
and Moore
Automaton, Designing the Control Automaton, Implementing Control Flow and
Synchronization
Designing for ALU efficiency, Memory Subsystems,
Simple Programmable Processor Design, Interrupt Processing and Context
Switching, Interfacing Techniques, Standard Processor Architectures
System
Level Design
10
Hours
Aspects of System Design, Scalable System
Architecture, Regular Processors, Network Architecture, Integrated Processor
Networks, Static Application Mapping and Dynamic Resource Allocation, Resource
Allocation on Crossbar Networks and FPGA Chips, Communication Data and Control
Information, P(Pi)-nets Language for
Heterogeneous Programmable Systems
Digital
Signal Processors 8 Hours
DSP Elements and Algorithms, Integrated DSP Chips,
Floating Point Processors, DSPs on FPGA, Typical Applications
References:
1. Mayer, Lindenberg,
”Dedicated Digital Processors”, Wiley
2. R Gupta, “Co-Synthesis of
Hardware and Software for Embedded Systems”, Kluwer
3. “Digital Signal
Processing”, IEEE Press
VLSI
Design & Testing
Manipulation
of Boolean expressions 10
Hours
Two level realizations with NAND or NOR gates,
Standard form of Boolean functions, Minterm & maxterm designation of
functions, simplification of functions on Karnaugh Maps, Map minimization of
product-of-sums expression, incompletely specified functions, logic Hazards,
Elimination of Hazards.
Algorithms for optimization of combinational logic,
impact of logic synthesis, cubical representation of Boolean functions,
determination of prime implicants selection of optimum set of prime implicates,
multiple output circuit, programmed logic array, minimization of multiple
output function, Tabular determination of prime implicats, field programmable
logic arrays.
VLSI Realizations of Combinational Logic 10 Hours
Introduction, pass transistor network realization,
Steering of 0,1,X & X to the output, tree networks, negative gate
realization, logic design with CMOS standard cells, pre charged clocking of
CMOS PLA.
Multilevel logic using complex (MSI) ports &
cells:- The place for complex parts & cells, decoders, ROM as a logic
element, binary adder, design with multiplexers, more than two level
realizations with basic primitives, combinational MSI parts & cells,
multilevel logic manipulation & optimization.
Sequential
circuits 8 Hours
Sequential activity, memory elements, general model
for Sequential circuits, clock mode Sequential circuits., Synthesis of clock
mode Sequential circuits: Analysis of a sequential circuit, design procedure,
synthesis of state diagrams, equivalent state & circuits, simplification by
implication tables, state assignment & memory element input equations.
VLSI Realization of
Digital Systems 8 Hours
Alternative Structural descriptions, levels of
descriptions, Standard cell CMOS layout & delay model, Timing analysis
& simulation, Event driven gate level simulations, Switch level simulation,
PLD & programmable gate arrays
Test Generation for VLSI 10 Hours
Fault
detection & diagnosis, Stuck at fault model, test generation strategy, test
generation by evaluation & search, modeling CMOS, Stuck-open faults, fault
simulation in sequential systems, boundary scan, built-in-self test. Fault Tolerant Design: Hardware
redundancy, Information redundancy, time redundancy, software redundancy,
system level Fault Tolerance. Self-checking sequential
circuit Design: Faults in state machines, self checking state
machines design Techniques, Synthesis of redundant fault-free state machines.
References:
1. Parag K. Lala , “Fault-Tolerant
& Fault Testable Hardware” , B-S-Publication Hyderabad
2. Parag K. Lala ,“Self
checking & Fault-Tolerant Digital Design”, Morgan Kaufman Publishers
3. Frederick J. Hill and Gerald
R. Peterson, “Computer Aided Logical Design with Emphasis on VLSI”, John Wiley
& Sons Inc.
2. Software
Engineering Stream
Engineering and Testing Structured Systems
10 hours
Scope
of Software Engineering, The Software Crisis, The functional approach.
Structuring a problem. Notion of analysis. Design as synthesis.
The
Yourdon method: need for Event Partitioning, Context Diagram, Event typology,
converting from events to software system functions
14 hours
Data
Flow diagrams, Constraints, Data Dictionary, Process specification techniques.
Construction
Design: Coupling and Cohesion. Afferent and Efferent modules, Design Heuristics
for Module Design
12 Hours
Maturity
levels of testing, Unit, Module, Sub-System and System Testing Interaction.,
Top down and bottom up testing, Constructing Stubs and Drivers. Notion of a test
case, test design approach to software design
White
box testing: Testing Hypotheses, Statement testing, branch testing, branch and
statement testing, Path, predicate path, path interpretation, Cyclomatic
complexity, condition testing, loop testing.
5 Hours
Black
box testing: Cause-effect technique
Implications
of software systems on underlying IT infrastructure
References:
1. Yourdon,
“Modern Structured Analysis”, Pearson
2. Beizer,
“Software Testing”, Van Nostrand Reinhold CO.
3. Pressman,
“Software engineering”, McGraw-Hill
4. Sommerville,
“Software Engineering”, Pearson
Object –Oriented Programming
10
Hours
The
OO manifesto for Programming Languages. Definition of Object, representing an
object, Object classes: constructor, destructor, copy constructor and their
defaults, public and private protection.
15 Hours
Complex
Objects and complex classes, their constructors and destructors and policies
for these. Privacy for complex objects. Inheritance: simple, multiple,
repeated. Resolving inheritance conflicts. Rules for constructors, destructors.
Protection policies for Inheritance.
10 Hours
Notion
of Late Binding. Polymorphism and its forms. Abstract classes and their use,
Meta-classes and templates.
5
Hours
Special
language features like friend functions, type casting etc. Separation of
specification from implementation.
Object-orientation for reuse and maintenance.
All the above to be
introduced through C++.
References:
1. Bjarne Stroustrap, “The C++ Programming Language”,
Pearson
2. Parimala N. “Object orientation Through C++”,
MacMillam
3. Lippman, Lajoie, and Moo, “C++ Primer”, Addison
Wesley
4. Robert Lafore, “Object Orientation in C++”,
Galgotia
Engineering OO Systems
5
Hours
OO manifesto for OO Analysis.
Object modeling and difference with data-oriented, process-oriented and
behaviour modeling.
15 Hours
Object modeling: classes,
complex object classes, inheritance. Sub systems and systems in OO modeling.
State transition diagrams.
10
Hours
Dynamic Modeling: Modeling an
event. Event typology, event as trigger
10
Hours
Functional Modeling: Review
of Structured techniques, Cross model constraints and linkages. Conversion to
OO implementation, UML notation
References:
1.
Rumbaugh et al, “Object Oriented Modeling and Design”, Prentice Hall
2.
Odell and Martin, “Object Oriented Analysis and Design”, Prentice Hall
Multimedia Systems
15 Hours
Components of multimedia,
multimedia and hypermedia, Multimedia authoring: metaphor, production,
presentation, automatic authoring, VRML,
10 Hours
Graphics and Image data
representation, Colour in Image and Video- colour science, colour models in
image and video, Fundamentals of video: types of video signals, analog and
digital video,
10 Hours
Basics of Digital Audio:
digitization, quantization, MIDI, multimedia
data compression: lossy compressions; Image compression standards, basic video
compression techniques, MPEG video coding, MPEG audio compression,
5 Hours
Multimedia communication:
quality of multimedia transmission, multimedia over IP, video delay in ATM,
multimedia, across DSL
References:
1.
Ze-nian and Drew, “Fundamentals of Multimedia”, Prentice Hall
2.
Rao, K.R. et al., “Multimedia Communication Systems. Techniques, Standards, and
Networks”, Pearson
3.
Y. Ramesh, “Multimedia Systems Concepts Standards and Practice, Kluwer
Internet Programming and Web Service Engineering
10 Hours
Notion of mark up. HTML and
XHTML. Style sheets, Cascading style sheets. Javascript, Dynamic HTML.
15
Hours
SGML. XML, DTD, XML schema.
ASP.Net, Perl/CGI and Python
15
Hours
Notion of a web service.
Service Oriented Architecture, SOAP, UDDI, WSDL, WSQM. Issues in providing QoS.
Elements of Service oriented software engineering.
References:
1.
Deitel, Deitel and Goldberg, “Internet & World Wide Web How to Program”, Pearson
2.
W3 SOAP Standard
3.
UDDI Standard
4.
WSDL standard
3. Information Systems Stream
Conceptual Modeling
12 Hours
Why conceptual modeling,
ANSI/SPARC framework, 100 % principle, conceptualization principle
12
Hours
Data-oriented Models: ER,
SHM, SHM+.
6 Hours
Translation of into
relational schemata
10 Hours
Behaviour-oriented Models:
Why these models? Interpretations of an Event, Remora model
Benefits of Conceptual
Modeling
References:
1. Batini, Ceri,
Navathe,” Conceptual Database Design: An Entity-Relationship Approach”, The Benjamin- Cummings Pub
2. Loucopoulos and Zicari,” Conceptual
Modeling, Databases, and Case: An Integrated View
of Information Systems Development”, John Wiley
& Sons
Requirements Engineering
10 Hours
Why requirements engineering?
Difference between Conceptual Modeling and RE. Context Diagram and RE.
Organizational versus Technical requirements,
Preparing IEEE SRS document
7 Hours
Stakeholders and their
identification. Designing and conducting interviews, questionnaires,
brainstorming sessions
7 Hours
RE in functional systems:
Types of goals, goal satisfaction and satisficing, Goal modeling and
decomposition, Goal operationalizing.
7 Hours
Scenario modeling. Scenario classification.
Goal-scenario coupling. Handling RE
problems like conflicts
9 Hours
RE in decisional systems: the
changed role of RE. notions of goals, decisions, and information. Informational
scenarios.
References:
1. Hull, Jackson, and Dick, “Requirements Engineering”,
Springer
2. Macaulay: Requirements Engineering,
Springer
3. Jackson M., “Software requirements &
specifications: a lexicon of practice, principles and prejudices”, ACM
Press/Addison-Wesley
Method Engineering
7 Hours
Notion of a method. Method
models, meta-models, and generic models. CAME, CASE, meta CASE and their differences.
8
Hours
Product oriented meta-models:
The OPRR model, the GOPRR model, Product-Process meta-models: The fragment
model
8
Hours
Integrated meta-models: The
contextual approach, the decisional approach
6 Hours
The generic method model:
Engineering methods for diverse domains
10
Hours
Situational method engineering.
SDLC for method engineering. Intentional approach to method engineering. Method
engineering processes. Open Issues
References:
1.
Brinkkemper et al, “Method Engineering”, Chapman and Hall, 1996
2.
Jolita R.et al, “Method Engineering”, Chapman and Hall, 2007
Process Engineering
10
Hours
SDLC in S/W and IS
engineering, Relationship of SDLC to process models, Classical process models:
Code and Fix, Waterfall, Prototype, Spiral, V, Fountain. Iterative and
Incremental process models
12
Hours
Process meta-models: Activity
based models, IBIS, Contextual model, and Map model, Tracing, Backtracking, and
Guidance
10
Hours
The personal process and team
process, CMM and its variants, ITIL, Six Sigma, ISO9000
8 Hours
Workflow Modeling
References:
1.
Pressman, “Software Engineering”, Mcgraw-Hill
2.
Sommerville, “Software Engineering”, Pearson
3.
Pfleegar, “Software Engineering Theory and Practice”, Pearson
Simulation and Modeling
10 Hours
Basic
Simulation Modeling: The Nature of simulation system, models and simulation,
discrete-event simulation, simulation of a single-server queuing, alternative
approaches to modeling and coding simulations, network simulation, parallel and
distributed simulation, simulation across the internet and web based
simulation, steps in a sound simulation study, other types of simulation:
continuous simulation, combined discrete-continuous simulation, Monte Carlo
simulation, advantages, disadvantages and pitfalls of simulation.
7 Hours
Modeling
Complex Systems: Introduction, list processing in simulation, approaches to
stering lists in a computer linked storage allocation
Simulation
examples using any simulation language: Single-server Queuing simulation with
time-shared computer model, job-shop model, and event-list manipulation.
7 Hours
Discrete System Modeling:
Classification of simulation models the simulation process, system
investigation validation and translation, simulation of complex discrete-event
systems with application in industrial and service organization tactical
planning and management aspects, Random variable generation and analysis.
8 Hours
Simulation
Software: Comparison of simulation packages with programming languages
classification of simulation software, general-purpose simulation packages,
object-oriented simulation, building valid, credible and appropriately detailed
simulation models, experimental design, sensitivity analysis and optimization
simulation of manufacturing systems.
9 Hours
Embedded
System Modeling: Embedded systems and system level design, models of
computation, specification languages, hardware/software code design, system
partitioning, application specific processors and memory, low power design.
Real-Time
system modeling, Fixed Priority scheduling, Dynamic Priority Scheduling
Data
Communication Network modeling, IP network intradomain (e.g. OSPF, RIP) routing
simulation.
References:
1.
Law Kelton,”Simulation Modeling and Analysis”, McGraw-Hill
2.
Geoffrey Gordon,”System Simulation”, PHI
4. Data Management Stream
Distributed DBMS
6 Hours
Review of computer networks
and centralized DBMS, Why distributed databases, basic principles of DDBMS,
distribution, heterogeneity, autonomy,
6 Hours
DDB architecture:
client-server, peer-to-peer, federated, multidatabase,
15 Hours
DDB design and
implementation: fragmentation, replication and allocation techniques,
6 Hours
Distributed query processing
and optimization,
7 Hours
Distributed transaction
management, concurrency control and reliability, DDB interoperability
References:
1.
Ceri and Pelagatti, “Distributed Data Base Systems”, Addison
2.
Ozsu,Valduriez, “Distributed Data Base Systems”, Pearson
Data Warehousing
14
Hours
The
organizational perspective, the technical perspective, Dimensional Modeling:
facts, dimensions, slowly and rapidly changing dimensions, Data Warehouse operations
8
Hours
Aggregation,
historical information, Query facility, OLAP functions and Tools, Data Mining
interfaces,
8
Hours
Relational
representation, Multidimensional representation, Meta-data and CWM, DW process
and architecture.
10
Hours
SDLC
of a Warehouse project: business process driven, Information systems product
driven and goal driven approaches.
Design
approaches: data driven design, user driven design. Information Package, Diagram
driven design.
Physical
design: clustering, partitioning etc.
References:
1. Ponnaih, “Data Warehouse Fundamentals”, Wiley
2. Inmon, “Building the Data Warehouse”, Wiley
3. Kimball and Ross, “The Data Warehouse Toolkit”
Wiley
4. Murray,
“Data Warehousing in the Real World”, Wiley
5. Imhoff C., “Mastering Data Warehouse Design” Wiley
Multi-media Databases
8 Hours
Relational
versus multimedia databases, Handling object data, Multidimensional structures:
insertion, deletion, search in 2-d trees, point quadtrees, MX-quadtrees, and
R-trees
6 Hours
Image
databases: Raw and compressed images, Discrete Fourier transform and Discrete
Cosine transform, segmentation, similarity based and spatial layout retrieval,
image representation in relations and R-trees
4 Hours
Document
databases: precision and recall, Latent semantic indexing, operating on TV
trees, inverted indices and sequential files.
8
Hours
Video
databases: organization of video content, querying content of video libraries,
video segmentation, video standards
4
Hours
Audio
databases: general model, metadata, signal based audio content, discrete
transformations for audio content, indexing techniques
6
Hours
Multimedia
databases: Principle of Uniformity, media abstractions, query languages,
indexing, query relaxation/expansion
4
Hours
Physical
storage and retrieval: retrieving form disk, CD-ROM, Tapes: recording and
placement methods, retrieval techniques.
Open
issues: security, compression for special data bases e.g. in medicine.
References:
1. Subrahmaniam VS, “Principles of Multimedia
Systems”, Morgan Kaufman
2. Apers et al, “Multimedia Databases in Perspective, Springer
3. Dunckley, “Multimedia Databases: An Object Relational Approach”,
Holborn
5. AI STREAM
Artificial
Intelligence
8 Hours
Knowledge:
Introduction, definition and importance, knowledge base system, representation
of knowledge, organization of knowledge, knowledge manipulation, knowledge
acquisition, introduction to PROLOG.
8
Hours
Formalized
symbolic Logics, Syntax and Semantics for FOPL, Inference rules, The resolution
principle, No deductive inference methods, Bayesian probabilistic informer,
Dimpster-Shafer theory, Heuristic Reasoning Methods.
8
Hours
Search
and Control strategies: introduction, concepts, uniformed or blind search,
informal search, searching and-or graphs, Matching techniques, structures used in
retrieval techniques, integrating knowledge in memory, memory organization
system.
8 Hours
Fuzzy
Logic: Basic concepts, Fuzzy sets, Membership Function, Types of membership
Function, Basic operations in Fuzzy sets, Intersection & Union-Complementary,
Subsethood, Properties of Fuzzy sets.
8
Hours
Expert
System architectures: Rule-Based system architectures, Non production system
architecture, dealing with uncertainty, knowledge organization and validation.
References:
1. Dan W Patterson, “Introduction to Artificial
Intelligence and Expert System”. PHI
2. Peter Jackson, “Introduction to Expert System”,
Pearson
3. A Gonzalbz and D.Dankel, “The Engineering Knowledge Base System”, PHI
4. Stuart Russell and Peter nerving, “Artificial
Intelligence: A Modern approach”, PHI
5. John Yen & Reza Langari , “Fuzzy: Intelligence,
Control and Information” , Pearson
Learning
Systems
8 Hours
Introduction:
Definition, Human Brain, Model of Neuran, Feed back, Network Architectures,
Knowledge Representation, AI & Neural Networks.
Learning Processes:
Introduction, Error-correction Memory-Based Learning, Hebbian Learning,
Competitive Learning, Boltzmann Learning, Learning with a teacher, Learning
without a teacher, Memory Adaptation.
8 Hours
Single
Layer Perceptrons: Concepts, Adaptive Filtering, Unconstrained optimization,
Steepest Descent Method, Newton’s
Method, Perceptron, Perceptron Convergence Theorem.
Multilayer
Perceptrons: Preliminaries, Back-propagation algorithm, activation function,
Rate of learning.
8 Hours
Neurodynamics:
Introduction Associative Memory, Linear Associater, Dynamical Systems,
Stability of Equilibrium States, Attractros, Hopfied models, Brain-state-in-a-box
model.
8 Hours
Genetic
Algorithms: Basics of genetic algorithms, binary GA implementation, Real coded
GA, Design issues in GA, Choice of encoding, selection probability, mutation
and cross over probabiltity, fitness evaluation function.
References:
1.
Simon Haykin, “Neural Networks”, Pearson
2.
Mohamad H. Hassoun, “Fundamentals of Artificial Neural Networks”, PHI
3.
James A. Anderson , “An Introduction to Neural Networks”, PHI
4.
Melanie Mitchall, “An Introduction to Genetic Algorithm”, PHI
Data Mining
8 Hours
Overview, types of
mining, Mining operations, introduction of statistical Data Mining, Heuristic
Mining, Introduction of mining in data
warehousing , Stages of DM
process. Decision-Tree based classifiers: infomation gain, decision tree
learning.
7
Hours
Data Mining
Techniques: Association- Rule mining methodes, supervised neural network,
perceptron, back propagation, bayesian methods, cross-validation, Time sequence
discovery.
7 Hours
Clustering: Similarity
and distance measures, hierarchical algorithms, partitional algorithms,
clustering large databases, clustering with categorical attributes. K - means.
10 Hours
Introduction
to information retrieval, Query optimization, Unstructured and semi-structured
text, Text encoding, Tokenization, Steaming, Lemmatization, Index Compression,
Lexicon Compression, Gap encoding, gamma codes, Index constructions, Dynamic indexing,
Positional indexes, n-gram indexes, real-world issues, Vector-Space Scoring,
Nearest neighbor techniques.
10 Hours
Introduction to
information retrieval , Inverted indices and Boolean queries, Query
optimization, Unconstrained and semi constrained text, Text encoding,
Tokenization, Stemming, Lemmatization, Tolerant retrieval: Spelling correction and synonymes, permuterm
indices, n-gram indices, Edit distance, Index compression, Lexicon compression,
Gap encoding, Gamma codes, Web structure,the user, search engine,
optimization/spam,web characteristic, web size measurement, near duplicate
detection, crawling and web indexes, link analysis.
References:
1. M.H. Dunham, “Data mining:
Introductory and Advanced Topics”, Pearson
2. J. Han and M. Kamber, “Data
Mining: Concept and Techniques”, Morgan Kaufman
3. Mallach, "Data Warehousing
System”, McGraw-Hill
4. Rechard J. Roiger and michal W.
Greatz, “Data Mining: A Tutorial based primer”, Pearson
5. Tom Mitchell, “Machine Learning”,
McGraw-Hill
Natural Language Processing
10 Hours
Context Free grammars,
Lexical analysis, Introduction to parsing, Context Sensitive grammars
10 Hours
Linguistics of English:
Review of English Grammar, Morphology, syntax, semantics, structure of
discourse. Words and the lexicon: word classes.
12 Hours
Semantic Grammars, TN,
ATN, Case grammars, Paninian Grammars, Parsers of NL statements, Determiners
and quantifiers, Noun-noun modification, pronoun resolution, relative clauses
8
Hours
Deep structure, shallow
structure, Differences between English and Hindi Application
(a)
MT
(b)
ASR
(c)
IR
(d)
Q & A
References:
1.Manning,C.D,
Schutze H, “Foundations of statistical natural language processing”, MIT press
2.Jurafsby
D. Martin J.H, “Speech and language processing” , PHI
3.Allen
, J., “Natural language understanding.”, Benjamin/ Cummins Publishing
4. Wall
L. et W, ”Programming PERL”, O’Reilly
6. SECURITY STREAM
Cryptography
Number Theory 10 Hours
Prime
numbers, Euler’s Totient function, Fermat’s and Eulers Theorem, Primality
Testing, Chinese Remainder Theorem, Discrete Logarithms, Group, Rings, Fields,
Modular Arithmetic, Euclidean Algorithm, Finite Fields of the form GF(p),
Polynomial Arithmetic, Fields of the form GF(2n), Random Number
Generation and Testing
Public Key Encryption 10 Hours
RSA
System, Implementing RSA, Attacks on RSA, Rabin Crypto System, Factoring
algorithms. The (p-1) method, Dixon’s
algorithm and Quadratic sieve
Elliptic
Curve Cryptography: Elliptic curves over GF(p), Elliptic curves over GF(2m),
Elliptic curve cryptography, factoring with ECC, Key Management and Diffie
Hellman Key Exchange,
Symmetric Encryption 8 Hours
Block
Cipher and DES, The strength of DES, Differential and Linear Cryptanalysis of
DES, Advanced Encryption Standard, Stream Ciphers and RC4,
Hash Functions 8 Hours
Hash
Functions, Security of hash functions, MD5, Secure Hash Algorithm, Whirlpool,
HMAC, CMAC, The birthday attack problem.
Digital
Signatures, Requirement, Authentication protocols, Digital Signature Standard,
ECDSA
Finite Automata and Ciphers 6 Hours
Finite
Automata and Ciphers, Structure of Ciphers, Selection of the Ma, h and g
functions, Cipher Design using Automata
References:
1.
Douglas R Stinson, “Cryptography Theory and practice”, CRC Press
2.
William Stallings, “Cryptography and Network Security 4e”, Pearson
3.
Simon J Shepherd, “Cryptography: Diffusing the Confusion”, Research press
studies
Network and System Security
Network Security 6 Hours
AH and ESP Protocols,
Security associations, Key management, Web security Considerations, secure
socket layer and Transport layer security.
PKI Infrastructure 8 Hours
Concept
of an infrastructure, application enables secure single sign-on, comprehensive
security, defining PKI, LDAP and X500.
Core PKI Services:
Authentication, Integrity and confidentiality, Mechanism required to create PKI
enabled services X-509 certificate.
8 Hours
System Security:
Intrusion Detection, Password Management, Base Rate Fallacy.
Malicious Software: Virus
and related threats, virus countermeasures, Distributed Denial of Service
attacks.
Firewalls: Design
principles, Trusted Systems common criterion for IT security evaluation
OS and Database Security 10 Hours
Structure
of an OS and application, application and OS security, security in Unix and
Linux Pluggable Authentication Modules, Access Control Lists, SELinux.
Database
Security:Database Security Evolution,
Role-based an object-oriented encapsulation procedural extension to SQL,
Security through Restrictive Clauses.
Secure Applications 8 Hours
PGP
and SMIME, Kerberos version IV and V, Security in Cellular Communication
System, Secure Electronic Transaction.
References:
1. William Stalling, “Cryptography and Network
Security 4e”, PHI
2. C Adams, Steve Lloyd, “Understanding PKI”, Addison
Wesley
3. Jay Ram Chandran, ”Designing Security
Architecture”, Wiley Computer Publishing
4. C Kaufman, Radia Perlman and Mike, “Network
Security 2e”, Pearson.
Digital Forensic
8 Hours
Transform Methods: Fourier Transformation, Fast Fourier
Transformation, Discrete Cosine Transformation, Mellin-Fourier Transformation,
Wavelets, Split
Images in Perceptual Bands, Applications of Transformation in Steganography.
8 Hours
Biometrics: Overview
of Biometrics, Biometric Identification, Biometric Verification, Biometric
Enrollment, Biometric System Security.
Authentication and
Biometrics: Secure Authentication Protocols, Access Control Security Services,
Authentication Methods, Authentication Protocols, Matching Biometric Samples,
Verification by humans.
Common biometrics: Finger Print Recognition, Face
Recognition, Speaker Recognition, Iris Recognition, Hand Geometry, Signature
Verification, Positive and Negative of Biometrics.
Matching: Two kinds of
errors, Score distribution, Estimating Errors from Data, Error Rate of Match
Engines, Definition of FAR and FRR
8 Hours
Introduction to Information
Hiding: Technical Steganography,
Linguistic Steganography, Copy Right Enforcement, Wisdom from Cryptography
Principles of Steganography: Framework for Secret Communication,
Security of Steganography System, Information Hiding in Noisy Data , Adaptive
versus non-Adaptive Algorithms, Active and Malicious Attackers, Information
hiding in Written Text.
8 Hours
Survey of Steganographic
Techniques: Substitution systems and
Bit Plane Tools, Transform Domain Techniques: - Spread Spectrum and Information
hiding, Statistical Steganography, Distortion Techniques, Cover Generation
Techniques.
Steganalysis: Looking for Signatures: - Extracting
hidden Information, Disabling Hidden Information.
10 Hours
Watermarking and Copyright Protection: Basic Watermarking, Watermarking Applications,
Requirements and Algorithmic Design Issues, Evaluation and Benchmarking of
Watermarking system.
References:
- Katzendbisser, Petitcolas, “ Information Hiding Techniques for Steganography and Digital Watermarking”, Artech House.
- Peter Wayner, “Disappearing Cryptography: Information Hiding, Steganography and Watermarking 2/e”, Elsevier
- Bolle, Connell et. al., “Guide to Biometrics”, Springer
7. THEORETICAL CS STREAM
Parallel Algorithms
8 Hours
Sequential
model, need of alternative model , parallel computational models such as PRAM ,
LMCC , Hypercube , Cube Connected Cycle , Butterfly , Perfect Shuffle Computers
, Tree model , Pyramid model , Fully Connected model , PRAM-CREW , EREW models
, simulation of one model from another one.
8
Hours
Performance
Measures of Parallel Algorithms , speed-up and efficiency of PA , Cost-optimality
, An example of illustrate Cost-optimal algorithms- such as summation , Min/Max
on various models.
8 Hours
Parallel
Sorting Networks , Parallel Merging Algorithms on CREW/EREW/MCC/ , Parallel
Sorting Networks on CREW/EREW/MCC/, linear array
8 Hours
Parallel
Searching Algorithm , Kth element , Kth element in X+Y on PRAM , Parallel Matrix
Transportation and Multiplication Algorithm on PRAM , MCC , Vector-Matrix Multiplication
, Solution of Linear Equation , Root finding.
8
Hours
Graph
Algorithms - Connected Graphs , search and traversal , Combinatorial
Algorithms- Permutation , Combinations , Derrangements.
References:
1.
M.J. Quinn, “Designing Efficient Algorithms for Parallel Computer” by Mc Graw Hill.
2.
S.G. Akl, “Design and Analysis of Parallel Algorithms”
3.
S.G. Akl, ”Parallel Sorting Algorithm” by Academic Press
Randomized Algorithms
8 Hours
Introduction: Basic Probability Theory, Probability Spaces; Bayes' Rule; Independence; Expectation; Moments; Common Distributions , Randomized Algorithm: General concepts and definitions, Quicksort , Min-Cut, Random Partitions, Probabilistic recurrences , Randomized Complexity Classes: RP, PP, BPP
Game Theoretic Techniques and Lower Bounds: Game theory concepts;
Applications to lower bounds, Examples: Sorting and Game tree evaluation
8 Hours
Moments and Deviations: Random sampling/bucketing, Tail bounds : Markov
and Chebyshev inequalities, High confidence selection, Pairwise
independence, Applications : The stable
marriage problem
Tail Inequalities : Chernoff bounds; Applications: Network routing and
gate-array wiring
7 Hours
Markov
Chains and Random Walks: A 2-SAT
Example, Markov Chains, Random Walks on Graphs, Graph Connectivity, Expanders ,
Probability Amplification by Random Walks on Expanders
Algebraic methods: Fingerprinting and Freivald's
technique, Verifying polynomial identities, Randomized pattern matching
6 Hours
Data
Structures:
Random treaps; Skip lists
Randomized Graph Algorithm: Shortest paths; Minimum
spanning tree
7 Hours
Parallel
and Distributed Algorithms: The PRAM
Model, Sorting on a PRAM, Maximal Independent Sets, Perfect Matchings,
Number Theory and Algebra: Elementary number
theory, Quadratic residues, Primality
testing, RSA cryptosystem
References:
1. R. Motwani and P. Raghavan, “Randomized Algorithms”,
Cambridge University Press
2. Michael Mitzenmacher, Eli Upfal , “Probability and
Computing”, Cambridge University Press
Approximation Algorithms
7 Hours
Introduction, Overview of Complexity Theory: Class NP, NP-Completeness, reductions, Randomized Complexity Classes, Basics of Probability Theory, Expectation and moments, basic distributions
7 Hours
Vertex/set cover, Greedy algorithm, Hardness of approximating Traveling Salesman Problem (TSP), Set cover, layering algorithm, shortest superstring,
Steiner tree, Metric Steiner tree, Metric TSP; Minimum weight multiway cut
minimum weight k-cut , k-center
8 Hours
Knapsack problem, Pseudo polynomial time algorithms PTAS, Fully polynomial time approximation scheme FPTAS, Strong NP-hardness, Bin packing, Asymptotic PTAS, Euclidean TSP, Proof of correctness
6 Hours
LP Duality, LP Duality Theorem, Dual-fitting -based analysis for the greedy set cover algorithm
Rounding Algorithm: set cover, randomized rounding
7 Hours
Half-integrality of vertex cover; Primal-dual Schema: set cover
Scheduling on Unrelated Parallel Machines, Primal-Dual algorithms, Facility Location and the k-Median Problem, Steiner Network Design
References:
1. Vijay V.Vazirani,
“Approximation Algorithm”, Springer
2. D. S. Hochbaum, “Approximation Algorithms for
NP-Hard Problems”, PWS 1997
Complexity Theory
8 Hours
Models of Computation, resources (time and space),
algorithms, computability, complexity;
8 Hours
Complexity classes, P/NP/PSPACE, reductions, hardness,
completeness, hierarchy, relationships between complexity classes
8 Hours
Randomized computation and complexity; Logical characterizations,
incompleteness; Approximability
8 Hours
Circuit complexity, lower bounds; Parallel computation
and complexity; Counting problems; Interactive proofs;
8 Hours
Probabilistically checkable proofs; Communication
complexity; Quantum computation.
References:
1. Christos H.
Papadimitriou, “Combinatorial Optimization: Algorithms and Complexity”
2. Sanjeev Arora and Boaz
Barak , “Complexity Theory: A Modern Approach”
3. Steven Homer, Alan L.
Selman, Computability and Complexity Theory , Springer
Computational Geometry
8 Hours
Convex hulls: construction in 2d and 3d, lower bounds;
Triangulations: polygon triangulations, representations, point-set
triangulations, planar graphs;
8 Hours
Voronoi diagrams:
construction and applications, variants; Delayney triangulations: divide-and-conquer,
flip and incremental algorithms, duality of Voronoi diagrams, minmax angle
properties.
8 Hours
Geometric searching:
point-location, fractional cascading, linear programming with prune and search,
finger trees, concatenable queues, segment trees, interval trees; Visibility: algorithms
for weak and strong visibility, visibility with reflections, art-gallery
problems;
8 Hours
Arrangements of lines:
arrangements of hyper planes, zone theorems, many-faces complexity and
algorithms; Combinatorial geometry: Ham-sandwich cuts
8 Hours
Sweep techniques: plane
sweep for segment intersections, Fortune's sweep for Voronoi diagrams,
topological sweep for line arrangements; Randomization in computational geometry:
algorithms, techniques for counting; Robust geometric computing; Applications
of computational geometry
References:
1. Franco
P. Preparata, Michael Ian Shamos, “Computational
Geometry: An Introduction” SpringerVerlag.
2.
Mark Berg, Marc van Kreveld, Mark Overmars, and Otfried Schwarzkopf, “Computational Geometry, Algorithms and Applications”. Springer.
COMPULSORY COURSE FOR SEM III
Professional Aspects in Software Engineering (1/2 Unit)
Intellectual Property rights 5 Hours
Confidential
Information, Copyright, Infringement of Copyright, Acts permitted in Relation
to Copyright Works, Licensing and Assignment of Copyright, Moral Rights,
Designs, Trademarks, The tort of passing off, Domain Names, Patents.
Software Licenses 5 Hours
Copyright, Contract,
Patent, Free Software and Open Source Software, MIT License, BSD License, GNU
General Public License, GNU Lesser General Public License, Q Public License, Proprietary
License, Sun Community License,
Software Contracts: 5 Hours
Basics of Software Contracts, Extent of liability, Contract
for the supply of custom-built software at a fixed price, other types of
software service Contract, Liability for defective software.
Software Crime
Prevention 5 Hours
Computing and criminal
Activity, Reforms of Criminal Law, Categories of Misuse, Computer Fraud,
Obtaining Unauthorized Access to Computer, Unauthorized Alteration or Destruction
of Information, Denying Access to an Authorized user, Unauthorized Removal of
Information Stored in a Computer.
Data Protection Regulations
5 Hours
Data Protection
and Privacy, The impact of the Internet, Factors Influencing the Regulation of
Data Processing, Convergence of Data Protection Practice, Defamation and the
protection of Reputation.
References:
1. Andrew M. St. Laurent, “Open Source and Free Software Licensing”, O’Reilly
Publications
2. Frank Bott, et. al, “Professional Issues in Software Engineering”,
Taylor & Francis
Appendix III
Thesis Requirements for M.Tech. Courses in Computer Science
and Information Technology
The work reported in the thesis
shall be an extension of the state of the art to demonstrate the capability of
the student to do creative work, develop the idea, prove its efficacy, report
it in a convincing manner and finally, defend it. The work must have scientific
and/ or industrial relevance.
The thesis shall be done in two
parts. During the third semester, the student shall carry out literature survey
and develop the necessary background (familiarity with tools, techniques) for
the work to be carried out in the fourth semester. At the end of the third
semester, the student shall submit a synopsis clearly stating the problem to be
addressed, report on the background developed, and layout a concrete project
plan for the fourth semester. A Pre-thesis examination consisting of a
presentation and viva shall be conducted after the synopsis has been submitted.
Passing the Pre-thesis
examination is a pre-requisite for continuing with the thesis in the fourth
semester.
The thesis shall be submitted
following the format of UPTU. It shall be examined by an external expert
decided by UPTU. After a written report is received expressing satisfaction
with the thesis, a viva voce examination shall be conducted in the presence of
the external expert. The thesis requirement shall be fulfilled upon the student
passing the viva examination.
