RVR & JC COLLEGE OF ENGINEERING:: GUNTUR

M.Tech(Computer Science & Technology)

Syllabus w.e.f. 2017-18

CT511 – Advanced Data Structures and Algorithms

Lecture: 4 Periods/WeekInternal: 40 Marks

Practical: --External: 60 Marks

Credits: 4

Course Learning Objectives: At the end of the Course Students will understand

1. Fundamentals of analysis of algorithm at depth.

2. Study of advanced data structures and its uses.

3. Analysis of problems from different domains.

Course Learning Outcomes: After successful completion of this course, student will be able to

1. Identify and use suitable data structures for given problem from different domains.

2. Appreciate the role of Linked List algorithms in solving variety of problems.

3. Appreciate the role of Optimization by using linear programming.

4. Analyze the various algorithms from different domains.

5. Understand the importance of advanced algorithms and techniques.

UNIT – I: [9 Periods]

Data Structures Basics: Structure and Problem Solving, Data structures, Data structure Operations, Algorithm: complexity, Time- space tradeoff. Algorithm- Complexity Notations: Introduction, Mathematical Notation and Functions, Algorithmic Notation, Control Structures, Complexity of Algorithms, Rate of Growth, Asymptotic Notations for complexity of Algorithms.

UNIT – II: [10 Periods]

Linked List: Introduction, Linked lists, Representation of linked lists in Memory, Traversing a linked list, Searching a linked list, Memory allocation and Garbage collection, insertion into linked list, Deletion from a linked list, Types of linked list. Stack and Queue: Introduction, Array Representation of Stack, Linked List Representation of stack, Application of stack, Queue, Array Representation of Queue, Linked List Representation of Queue.

UNIT – III: [10 Periods]

Sorting Techniques: Notation and Concepts, Insertion Sort, Selection Sort, Bubble Sort, Merge Sorting, Heap Sort, Radix Sort, Quick Sort. Searching Techniques: Sequential Searching, Binary Searching, Search Trees, Hash- Table Methods, hash functions and relates analysis

UNIT – IV: [10 Periods]

Trees: Definitions and Concepts, Operations on Binary Trees, Representation of binary tree, Conversion of General Trees to Binary Trees, Sequential and Other Representations of Trees, Tree Traversal. Balanced Trees: AVL- tree – structure, operations, its application, B-Tree – structure, operations, its application.

UNIT – V: [10 Periods]

Dynamic Programing: matrix chain multiplication, cutting rod problem and its analysis Graph algorithms Bellman ford algorithm, Dijkstra algorithm, Johnson’s All pair shortest path algorithm for sparse graphs

Text Books:

1. T.H. Coreman , C.E. Leiserson, R.L. Rivest, and C. Stein, “Introduction to algorithms”,2nd edition, PHI publication 2005.

2. Ellis Horowitz, SartajSahni , S. Rajsekaran. “Fundamentals of computer algorithms” University Press.

References:

  1. Robert Sedgewick Philippe Flajolet, “An Introduction to the Analysis of Algorithms”, First Edition, McGraw Hill, 1995.
  2. G.A.V. Pai, “Data Structures and Algorithms”, TMH, 2009.

CT 512 - Data Base Technologies

Lecture : 4 Periods/WeekInternal: 40 Marks

Practical: --External: 60 Marks

Credits: 4

Course Learning Objectives: At the end of the Course Students will understand

  1. Fundamental Concepts of Databases.
  2. Query Optimization, Transaction Processing, Active databases.
  3. Temporal Databases, Multimedia Databases, Ontology and Latest developments in databases.

Course Learning Outcomes: After successful completion of this course, student will be able to

  1. Use Data Models and understand the Database Context.
  2. Know the Query optimization and concurrency control techniques.
  3. Acquire the knowledge of Distributed Databases and Issues in Big Data.
  4. Know the importance of Active Database systems and Deductive databases.
  5. Know the Temporal databases, ontologies and multimedia databases.

UNIT - I : Relational Data Model , SQL, Data modelling using ER, Basics of Fundamental Dependencies and Normalization of Relational Databases.

UNIT - II: Algorithms for Query processing and Optimization, Introduction to Transaction Processing Concepts and Theory, Concurrency Control Techniques.

UNIT - III: Distributed Database Concepts, NOSQL Databases and Big Data Storage Systems, Big Data Technologies based on MapReduce and Hadoop.

UNIT - IV: Active database systems: Basic concepts, Issues, Architectures, Research relational prototypes—the Starburst Rule System, Commercial relational approaches.Deductive Database systems- Architectural approaches, Research prototypes, Updates in deductive databases, Integration of deductive database and object database technologies, Constraint databases.

UNIT - V : The Latest Developments: Temporal databases - Basic concepts, Temporal data models, Temporal query languages, Ontologies - Ontology theoretical foundations, Environments for building ontologies, Structured, semi-structured and unstructured data, Multimedia databases.

Text Books:

1. , Ramez Elmasri, Shamkant B. Navathe, "Fundamentals of Database Systems, 7th Edition, Pearson Edn., 2016.(UNIT - I to UNIT - III).

2. Elisa Bertino, Barbara Catania, GianPieroZarri, “Intelligent Database Systems “, Addison Wesley Publications, 2001(UNIT - IV & UNIT - V).

References:

  1. Database Systems, Ramez Elmasri and Shamkant B.Navathe, Pearson Education, 6th edition.
  2. Data base Management Systems, Raghurama Krishnan, Johannes Gehrke, TATA McGrawHill, 3rd Edition.
  3. Database Systems: The Complete Book by Hector Garcia-Molina, Jeff Ullman, and Jennifer Widom, Pearson Prentice Hall, 2009, 2nd edition.
  4. Introduction to Data Mining, Pang-Ning Tan, Michael Steinbach, and Vipin Kumar, Addison Wesley.
  5. Database systems: A Practical approach to design, implementation and management, Connoly/Begg, Addison Wesley, 3rd edition.

CT513 – Advanced Operating Systems

Lecture : 4 Periods/WeekInternal: 40 Marks

Practical: --External: 60 Marks

Credits: 4

Course Learning Objectives: At the end of the Course Students will understand

  1. Fundamentals of Operating System, Process Scheduling and Synchronization.
  2. Concepts of Memory management, File management and Device management.
  3. Concepts of Distributed Operating systems.

Course Learning Outcomes: After successful completion of this course, student will be able to

  1. Design and implement inter process communication mechanisms.
  2. Analyze, Design and implement Different CPU Scheduling algorithms and classical problems of synchronization.
  3. Design and implement Memory management and Page replacement algorithms.
  4. Know the concepts of Distributed Operating system.
  5. Use files and files systems in different Operating Systems environment.

UNIT – I:[10 Periods]

Introduction: Operating System, types of Operating Systems, Operating System Structure, Services, System Calls, Virtual Machines, Operating System Design And Implementation.

Process Management: Process Concepts, Operations on Processes, Cooperating Processes, Threads, Inter Process Communication.

UNIT – II:[10 Periods]

Process Scheduling: Scheduling Algorithms, Multiple -Processor Scheduling, Thread Scheduling.

Process Synchronization & Deadlocks: The Critical Section Problem, Semaphores and Monitors, Classical Problems of Synchronization,Deadlocks,Methods For Handling Deadlocks: Deadlock- Prevention, Avoidance, Detection,& Recovery.

UNIT – III: [10 Periods]

Memory Management & File System Implementation: Paging and Segmentation, Virtual Memory, Demand Paging, Page Replacement Algorithms, Thrashing, File System Implementation -Access Methods, Directory Structure, Protection, Allocation Methods, Free Space Management, Directory Management, Device Drivers.

UNIT – IV: [10 Periods]

Distributed Operating Systems: Distributed System Goals, Types Of Distributed Systems, Styles & Architecture Of Distributed Systems, Threads, Virtualization, Clients, Servers, Code Migration, and Communication in Distributed Systems.

UNIT – V: [10 Periods]

Distributed Systems & Synchronization: Clock Synchronization, Logical Clocks, Mutual Exclusion, Global Positioning Of Nodes, Data-Centric Consistency Models, Client-Centric Consistency Models, Consistency Protocols.

Case Study: Over View Of UNIX, LINUX, Windows NT , Android And IOS Operating systems.

Text Books:

  1. Silberschatz & Galvin, “Operating System Concepts”, Wiley.
  2. Andrew S.Tanenbaum, Maarten Van teen, “DISTRIBUTED SYSTEMS”, Second edition,.

References:

  1. William Stallings-“Operating Systems”- 5th Edition – PHI.
  2. Charles Crowley, ‘Operating Systems: A Design-Oriented Approach’, Tata Hill Co.,1998 edition.
  3. Andrew S.Tanenbaum, ‘Modern Operating Systems’, 2nd edition, 1995, PHI.
  4. Advanced Concepts in Operating systems.Distributed, Database and Multiprocessor operating systems, Mukesh singhal, Niranjan G.Shivaratri, Tata McGraw Hill Edition.
  5. Dhamdhere, “Operating Systems - A concept based approach”, 2nd Edition, TMH, 2006.
  6. Pradeep K. Sinha, “Distributed Operating Systems - Concepts and Design”, 2nd Edition, IEEE 1997.
  7. Daniel P Bovet and Marco Cesati, “Understanding the Linux Kernel “, 3rd Edition,’ Reilly, 2005.

CT521 – Cryptography & Network Security

Lecture: 4 Periods/WeekInternal: 40 Marks

Practical: --External: 60 Marks

Credits: 4

Course Learning Objectives: At the end of the Course Students will understand

  1. Network security attacks and Symmetric Ciphers.
  2. Concepts on Asymmetric ciphers like RSA and Elliptic curve algorithms.
  3. Cryptography data integrity algorithms and network security.

Course Learning Outcomes: After successful completion of this course, student will be able to

  1. Identify common network security vulnerabilities/attacks, classical and symmetric encryption schemes.
  2. Know the cipher modes of operations and Public-key Cryptography.
  3. Design Hash techniques and Digital signatures schemes.
  4. Know the concepts of key management schemes and know the web security SSL/TLS .
  5. Analyze wireless and IP Security technologies.

UNIT-I:[10 Periods]

Introduction: Computer Security Concepts, The OSI Security Architecture, Security Attacks, Security Services, Security Mechanisms, A Model for Network Security.

Classical Encryption Techniques: Symmetric Cipher Model, Substitution Techniques, Transposition Techniques, Rotor Machines, Steganography.

Block Ciphers and the Data Encryption Standard: Block Cipher Principles, The Data Encryption Standard (DES), A DES Example, The Strength of DES, Differential and Linear Cryptanalysis, AES Structure, AES Round Functions, AES Key Expansion.

UNIT-II:[10 Periods]

Block Cipher Operation: Multiple Encryption and Triple DES, Electronic Codebook Mode, Cipher Block Chaining Mode, Cipher Feedback Mode, Output Feedback Mode, Counter Mode.

More Number Theory: Prime Numbers, Fermat’s and Euler’s Theorems, Testing for Primality, The Chinese Remainder Theorem, Discrete Logarithms.

Public-Key Cryptography and RSA: Principles of Public-Key Cryptosystems, The RSA Algorithm.

Other Public-Key Cryptosystems: Diffie-Hellman Key Exchange, ElGamal Cryptosystem, Elliptic Curve Arithmetic, Elliptic Curve Cryptography.

UNIT-III:[10 periods]

Cryptographic Hash Functions: Applications of Cryptographic Hash Functions, Two Simple Hash Functions, Requirements and Security, Hash Functions Based on Cipher Block Chaining, Secure Hash Algorithm (SHA), SHA-3.

Message Authentication Codes: Message Authentication Requirements, Message Authentication Functions, Message Authentication Codes, Security of MACs, HMAC.

Digital Signatures: Digital Signatures, Digital Signature Standard (DSS)

UNIT-IV:[10 periods]

Key Management and Distribution: Symmetric Key Distribution Using Symmetric Encryption, Symmetric Key Distribution Using Asymmetric Encryption, Distribution of Public Keys, X.509 Certificates, Public Key Infrastructure.

User Authentication Protocols: Remote User Authentication Principles, Remote User Authentication Using Symmetric Encryption, Kerberos, Remote User Authentication Using Asymmetric Encryption.

Transport-Level Security: Web Security Issues, Secure Sockets Layer (SSL), Transport Layer Security (TLS).

UNIT-V:[10 periods]

Wireless Network Security: IEEE 802.11 Wireless LAN Overview, IEEE 802.11i Wireless LAN Security.

Electronic Mail Security: Pretty Good Privacy (PGP), S/MIME.

IP Security: IP Security Overview, IP Security Policy, Encapsulating Security Payload, Combining Security Associations.

Text Book:

  1. William Stallings, “Cryptography and Network Security” 5th Edition, Pearson Education.

Reference Books:

  1. Behrouz A.Forouzen, Debdeep Mukhopadhyay, “Cryptography & Network Security”, 2nd Edition, TMH.
  2. Atul Kahate, “Cryptography and Network Security”, 3rd Edition.
  3. Chalie Kaufman, Radia Perlman, Mike Speciner, “Network Security”, 2nd Edition, (PHI / Eastern Economy Edition)
  4. Wade Trappe & Lawrence C.Washington, “Introduction to Cryptography with Coding Theory”, 2/e, Pearson.

CT 522 – Distributed Systems

Lecture: 4 Periods/WeekInternal: 40 Marks

Practical: --External: 60 Marks

Credits: 4

Course Learning Objectives: At the end of the Course Students will understand

1. challenges and issues of incorporating distributed OS concepts

2. operating system principles, Distributed Computing techniques,

3. Synchronization, Processes and Shared Data access files.

Course Learning Outcomes: After successful completion of this course, student will be able to

  1. Develop, test and debug RPC based client-server programs in Unix.
  2. Design and build application programs on distributed systems.
  3. Improve the performance and reliability of distributed programs.
  4. Know newer distributed file systems for any OS.
  5. Build and Use Distributed System

UNIT : I: (9 Periods)

INTRODUCTION & COMMUNICATION OF DISTRIBUTED SYSTEMS: Introduction & Goals - Hardware Concepts - Software concepts - Design issues - layered protocols - ATM Networks - client server model - Remote Procedure calls - Group Communication

UNIT 2: (10 Periods)

SYNCHRONIZATION IN DISTRIBUTED SYSTEMS: Clock synchronization - mutual exclusion - Election algorithms - Atomic transactions - Transaction model - Implementation and Concurrency control – Deadlocks.

UNIT 3: (10 Periods)

PROCESSES AND PROCESSORS IN DISTRIBUTED SYSTEMS: Threads - Threads design issues and implementation - System models - processor allocation - Design & implementation issues - Example processor allocation algorithms and Scheduling Fault tolerance–Types - Use of redundancy - Real time distributed systems - Real time Scheduling and communication

UNIT 4: (10 Periods)

DISTRIBUTED FILE SYSTEMS AND SHARED MEMORY: Distributed File Systems Design - DFS Implementation - Example DFS - Trends - Shared memory Introduction - Consistency models - Page-based distributed shared memory - Shared-variable distributed shared memory - Object-based distributed shared memory – Comparison.

UNIT 5: (10 Periods)

CASE STUDY Introduction to amoeba - Object and Capabilities - Process Management - Memory management - Group Communication – FLIP - Amoeba Servers - Introduction to MACH - Process Management - Memory management – Communication

Text Books:

1. Andrew S Tanenbaum - Distributed Operating Systems - Pearson Education,2001.

2. MukeshSingalNiranjan G Shivrartri, -Advanced Concepts in Operating Systems - McGraw Hill

International , 1994.

Reference Books:

  1. Distributed Operating System – P.K.Sinha, PHI, 2008.
  2. Web resources

CT523 – Machine Learning

Lecture: 4 Periods/WeekInternal: 40 Marks

Practical: --External: 60 Marks

Credits: 4

Course Learning Objectives:At the end of the Course Students will understand

  1. goals and objectives of machine learning to build real-world systems.
  2. classification and prediction techniques and to buildsystems that explore unknown and changing

environments.

  1. machine learning theory and models that exhibithigh accuracies.

Course Learning Outcomes:After successful completion of this course, student will be able to

1.know the basics of machine learning.

2.use machine learning to build real-world systems.

3.apply classification and prediction techniques.

4.build systems that explore unknown and changing environments.

5.know advanced machine learning techniques.

Unit-I:[9 Periods]

Introduction to Machine Learning. Supervised Learning, Bayesian Decision Theory and Naïve Bayesian Approaches, Parametric Model Estimation.

Unit-II:[9 Periods]

Dimensionality Reduction Centering on PCA, Clustering1: Mixture Models, K-Means and EM, Non-Parametric Methods Centering on kNN and Density Estimation.

Unit-III:[9 Periods]

Clustering2: Density-based Approaches, Decision and Regression Trees, Comparing Classifiers, Ensembles: Combining Multiple Learners

Unit-IV[9 Periods]

Support Vector Machines, More on Kernel Methods,

Unit-V:[9 Periods]

Belief Networks, Reinforcement Learning, Neural Networks, Computational Learning Theorooks

Text Books:

  1. EthemAlpaydin, Introduction to Machine Learning, MIT Press, 2010.

References:

  1. Tom Mitchell, “Machine Learning”, Mc Graw Hill publications, 1997.
  2. Christopher. M.Bishop, “Pattern Recognition and Machine Learning”, Springer publications, October, 2007.
  3. Ethem Alpaydin, “Introduction to Machine Learning”, 2nd Edition, MIT Publisher, 2010.

CT571 – Automata and Formal Languages

Lecture : 4 Periods/WeekInternal: 40 Marks

Practical: --External: 60 Marks

Credits: 4

Course Objectives:At the end of the Course Students will understand d

  1. concepts of Finite automata theory and its applications.
  2. concepts of Regular expressions, regular languages,Context-free grammars and languages.
  3. designing principles of push-down automata, Turing machines and Undecidability.

Course Outcomes: After successful completion of this course, student will be able to

  1. design finite state machines.
  2. design ϵ-NFA, conversion between Finite automata and Regular expressions.
  3. apply pumping lemma for Regular languages, construct parse trees for CFG and ambiguous grammars.
  4. construct push-down automata and apply pumping lemma for CFL.
  5. design Turing Machines and analyze Undecidability.

UNIT – I: / (15 Periods)

Automata: Introduction to Automata, The central concepts of automatatheory - Alphabets, Strings, Languages.

Finite Automata: An Informal picture of finite automata, Deterministic finite automata (DFA) - Definition of DFA, DFA processing strings, Notations for DFA, Extended transition function, the language of DFA, Non deterministic finite automata (NFA) - Definition of NFA, Extended transition function, the language of NFA, Equivalence of DFA and NFA.

Finite Automata with ϵ-transitions: Use of ϵ-transition, notation for anϵ-NFA,ϵ-closures, extended transitions and languages, Applications, Moore and mealy machines.

UNIT– II: / (14 Periods)

Regular Expressions and Languages: Regular expressions, finite automata and regular expressions, Algebraic laws of regular expressions.

Properties of Regular Languages: Proving languages are not regular -Pumping lemma for regular languages, Applications of the pumping lemma, Closure Properties of Regular Languages, Equivalence and minimization of automata - Minimization of DFA

UNIT – III: / (14 Periods)

(Construction based treatment & proofs are excluded)

Context Free Grammars: Context Free Grammars, Parse Trees, Constructing parse trees, derivations and parse trees, ambiguous grammars.

Pushdown Automata: Definition of the Pushdown automata, the languages of PDA, Equivalences of PDA's and CFG's.

UNIT – IV: / (14 Periods)

Context free languages: Normal form's for context- Free grammars, the pumping lemma for context free languages.

Properties of Context free languages: closure properties for contextfree languages, Decision properties for CFL's.

UNIT – V: / (13 Periods)

Introduction to Turing Machines: The Turing Machine, programming techniques for Turing machines.

Undecidability: a language that is not recursively enumerable, an undecidable problem that is RE, Undecidability problems about TM, Post's Correspondence problem.

Text Book:

  1. John.E.Hopcroft, R.Motwani, & Jeffery.D Ullman, Introduction to Automata Theory, Languages and Computation, 3rdEdition, Pearson Education, 2009.

Reference Books:

  1. Daniel I.A. Cohen, Introduction to Computer Theory, 4thEdition,John Wiley & sons, 2003.
  1. KLP Mishra & N.Chandrasekharan, Theory of Computation, 3rdEdition,PHI,2006.

CT572 – Advanced Computer Architecture