Syllabus

Review of basic data structures and their realization in an object-oriented environment. The following topics will be covered with emphasis on formal analysis and design: Dynamic Data structures; 2-3 trees, Red-black trees, binary heaps, binomial and Fibonacci heaps, Skip lists, universal hashing. Data structures for maintaining ranges, intervals, and disjoint sets with applications. Basic algorithmic techniques like dynamic programming and divide-and-conquer. Sorting algorithms with analysis, integer sorting algorithms with analysis, integer selection. Graph algorithms like DFS with applications, MSTs, and shortest paths.

Database System Architecture - Data Abstraction, Data Independence, Data Definition, and Data Manipulation Languages. Data Models - Entity-Relationship, Network, Relational, and Object-Oriented Data Models, Integrity Constraints, and Data Manipulation Operations. Relational Query Languages: Relational Algebra, Tuple and Domain Relational Calculus, SQL, and QBE. Relational Database Design: Domain and Data dependency, Armstrong’s Axioms, Normal Forms, Dependency Preservation, Lossless design. Query Processing and Optimization: Evaluation of Relational Algebra Expressions, Query Equivalence, Join strategies, Query Optimization Algorithms. Storage Strategies: Indices, B-trees, Hashing; Transaction Processing: Recovery and Concurrency Control, Locking and Timestamp-based Schedulers, Multiversion and Optimistic Concurrency Control schemes. Advanced Topics: Object-oriented and Object Relational Databases, Logical Databases, Web Databases, Distributed Databases, Data Warehouse, and Data Mining.