bit mesra M.Tech. Information Technology Syllabus

[sumit]

Semester-I
TIT 1101 Computability and Complexity Theory
Module-I +II

Basic background on automata and languages, Types of automata and languages, Turing machines, k-tape Turing machines, non-deterministic Turing machines, Universal Turing machine, Halting problem. Recursive enumerable languages, Recursive languages, Decidable and recognizable language, Turing-decidable languages, Turing-recognizable languages, Context Sensitive Language and Chomosky Hierarchy.


Module-III+IV
Primitive recursive function, partial recursive function, Recursive and recursive enumeration sets, Programming systems, Unsolvable problems, a non-recursive language and an unsolvable problem, Reducing one problem to another problem, Rice Theorem, More unsolvable problems, PCP.


Module-V+VI
Measuring complexity- Big Oh, small oh and other notations, Analyzing algorithms, Time and space complexity of a Turing machine, Complexity analysis of multi-tape TM Complexity classes: P, NP, NP-C, NP-Complete problem, Additional NP-complete problems- clique, vertex cover, Hamiltonian cycle, coloring problem, graph isomorphism, Reduction from NP-C problem to another problem.


Module-VII
Tractable and Intractable problems.
Text Books
1. Lewis H.R., Papadimitriou C.H.- Elements of the Theory of Computation:, PHI Publ. , 2nd edition, New Delhi
2. John Martin. Introduction to Languages and the Theory of Computation, 3rd ed. McGraw Hill, New York, NY, 2003.


Module -I
Review of basic concepts, Transaction and System Concepts, Desirable Properties of Transactions, Characterizing Schedules Based on Recoverability, Characterizing Schedules Based on Serializability, Transaction Support in SQL.

Module -II
Concurrency Control Techniques, Two-Phase Locking Techniques for Concurrency Control, Concurrency Control Based on Timestamp Ordering, Multiversion Concurrency Control Techniques, Validation (Optimistic) Concurrency Control Techniques, Granularity of Data Items and Multiple Granularity Locking, Using Locks for Concurrency Control in Indexes, Other Concurrency Control Issues.

Module -III
Recovery Concepts, Recovery Techniques Based on Deferred Update, Recovery Techniques Based on Immediate Update, Shadow Paging, The ARIES Recovery Algorithm, Recovery in Multidatabase Systems, Database Backup and Recovery from Catastrophic Failures.

Module -IV
Overview of Object-Oriented ConceptsObject Identity, Object Structure, and Type Constructors, Encapsulation of Operations, Methods and Persistence, Type and Class Hierarchies and Inheritance, Complex Objects, Overview of the Object Model of ODMG, The Object Definition Language ODL, The Object Query Language, OQL, Overview of the c++ Language Binding, Object Database Conceptual Design.

Module -V
Overview of SQL and Its Object-Relational Features Evolution and Current Trends of Database Technology The Informix Universal Server, Implementation and Related Issues for Extended Type Systems The Nested Relational Model, Active Database Concepts and Triggers Temporal Database Concepts Multimedia Databases, Introduction to Deductive Databases.

Module -VI
Distributed Databases and Client-Server Architectures, Distributed Database Concepts, Data Fragmentation, Replication and Allocation Techniques for Distributed Database Design, Types of Distributed Database Systems, Query Processing in Distributed Databases, Overview of Concurrency Control and Recovery in Distributed Databases, An Overview of 3-Tier Client-Server Architecture.

Module -VII
Data Modeling for Data Warehouses Characteristics of Data Warehouses Introduction, Definitions, and TerminologyBuilding a Data WarehouseTypical Functionality of a Data WarehouseData Warehouse Versus ViewsProblems and Open Issues in Data Warehouses, Mobile Databases Multimedia Databases Geographic Information Systems Genome Data Management