Syllabus Dbatu

BTCOC501 Database Systems

[Unit 1] 6 Hrs

Database system architecture: Data Abstraction, Data Independence, Data Definition

Language (DDL), Data Manipulation Language (DML).

Data models: Entity-relationship model, Relational integrity constraints, data manipulation

operations.

[Unit 2] 6 Hrs

Relational query languages: Relational algebra, Tuple and domain relational calculus,

SQL3, DDL and DML constructs, Open source and Commercial DBMS – MYSQL,

ORACLE, DB2, SQL server.

[Unit 3] 6 Hrs

Relational database design: Domain and data dependency, Armstrong's axioms, Normal

forms, Dependency preservation, Lossless design.

[Unit 4] 6 Hrs

Query processing: Evaluation of relational algebra expressions, Query equivalence, Join

strategies.

[Unit 5] 6 Hrs

File Organization and Indexing: Indices, B-trees, hashing.

[Unit 6] 6 Hrs

Transaction processing: Concurrency control, ACID property, Serializability of scheduling,

Locking and timestamp based schedulers, Multi-version and optimistic Concurrency Control

schemes, Database recovery.

Text Books:

 Henry Korth, Abraham Silberschatz & S. Sudarshan, Database System Concepts,

McGraw-Hill Publication, 6th Edition, 2011.

Reference Books:

J. D. Ullman, “Principles of Database and Knowledge – Base Systems”, Vol 1,

Computer Science Press.

BTCOC502 Theory of Computations

[Unit 1] 6 Hrs

Finite Automata and Regular Expressions: Definition of deterministic finite automata,

Non-deterministic finite automata, Moore and Mealy machines and their conversions, Regular

expressions, Recursive definition, NFA with e-moves, Inter-conversion between NFA and

DFA, Regular expression and FA, Pumping lemma.

[Unit 2] 6 Hrs

Context Free Grammars: Definition, Production rules, Ambiguous grammar, Removal of

ambiguity, Chomsky hierarchy, Context Free Grammar (CFG) – definition, Simplification of

CFG.

[Unit 3] 6 Hrs

Context Free Languages: Definition of context free languages, Regular grammar definition,

Left linear, Right linear grammar, Inter-conversion between left linear and right linear regular

grammar, Regular grammar and finite automata, CNF, GNF, Derivation graphs, Type 0 and

Type 1 grammars.

[Unit 4] 6 Hrs

Pushdown Automata: Formal definition, Pushdown automata (PDA), Deterministic

Pushdown automata (DPDA) – definition, Non-deterministic Pushdown automata (NPDA) -

definition, relative powers of DPDA and NPDA.

[Unit 5] 6 Hrs

Turing Machines and Undecidability: Definition, Computing with Turing machine,

Extensions of Turing machines, Random access Turing machines, Non-deterministic Turing

machines, Grammars, The Church’s Turing hypothesis, Universal Turing machines, The

Halting problem, Unsolvable problems about Turing machines.

Reference Books:

1. John C. Martin, Introduction to Languages and Theory of Computation, McGrawHill Publication, 4th Edition, 2010.

2. Krithivasan Kamala, Introduction to Formal Languages, Automata Theory and

Computation, Pearson Education, 1st Edition, 2009.

3. Papadimitriou, Lewis, Elements of the Theory of Computations, PHI Publication,

2

nd Edition, 1997.

4. E. V. Krishnmurthy, Introductory Theory of Computer Science, Springer-Velang

New York Inc., 1st Edition, 1985.

Text Books:

1. Hopcroft, Ullman, Motwani, Introduction to Automata Theory, Languages, and

Computation, Addison Wesley Publication, 2nd Edition, 2001.

2. Daniel I. A. Cohen, Introduction to Computer Theory, Wiley Publication, 1st Edition,

1986.