Syllabus - HPD

Syllabus - HPD

510102 - High Performance Databases

UNIT I. Physical database design & Tuning

Database workloads, physical design and tuning decisions, Need for Tuning

Index selection: Guideline for index selection, Clustering & Indexing Tools for index

selection

Database Tuning: Tuning indexes, Tuning Conceptual schema Tuning Queries &views, Impact of Concurrency, Benchmarking

UNIT II. Distributed Databases

Introduction, Design Framework, Design of database fragmentation, The Allocation

of Fragments, Translation of global queries to fragment queries, Optimization of access queries, Distributed Transaction Management, Concurrency Control, Reliability.

UNIT III. Advance Transaction Processing

Transaction Processing Monitors, Transactional Workflow, Real time transaction System, Long duration Transactions, Transaction Management in Multi-databases, Distributed Transaction Management, Main Memory Databases, and Advanced Transaction Models.

UNIT IV. Semi-Structured Data and XML

Semi-Structured Data, Introduction to XML, XML hierarchical Model, DTD & XML schema, XML Namespace, XML query & Transformation: Xpath, XSLT, XQuery, Storage of XML data, XMLTechnologies : DOM &SAX Interfaces X pointer, Xlink, XHTML, SOAP, WSDL, UDDI,XML database Application.

UNIT V. Emerging Trends in Databases

Introduction, Motivation, Temporal databases, Spatial & geographic databases, Multimedia Databases, Mobility & personal Databases

UNIT VI. Advanced Application Development

Performance Tuning, Performance Benchmarks, Standardization, E-Commerce, Legacy Systems, Large-scale Data Management with HADOOP, Semi structured database COUCHDB: Introduction, Architecture and principles, features

References:

1)Database system Concept by Silberschatz And Korth 6th Edition

2)Distributed Databases principles & systems by Stefano Ceri, Giuseppe Pelagatti

3)Web Data Management, Abiteboul, Loana, Philippe Et. al Cambridge

4)publication Database Systems, Thomas Connolly, Carolyn Begg, Pearson 4th

Edition 

5)Database Management Systems by Raghu Ramakrishnan and

Johannes Gehrke

Syllabus - AA

Syllabus - AA

510101- Applied Algorithms

Unit I. Analysis of algorithms

Review of algorithmic strategies, Asymptotic analysis: upper and lower complexity bounds. Identifying differences among best, average and worst Case Behaviors. Big O, little O, omega and theta notations, Standard complexity classes. Empirical measurements of performance. Time and space trade-offs in algorithms. Analyzing recursive algorithms using recurrence relations.

Unit II. Fundamental Computing Algorithms

Numerical algorithms, Sequential and binary search algorithms. Quadratic sorting

algorithms and O (n log n) sorting algorithms. Algorithms on graphs and their complexities using Greedy Approach for --- Prim’s and Krushkal’s Algorithm for

minimum spanning tree, Single source shortest path Algorithm, all pair shortest paths in Graph

Unit III. Approximation Algorithms

Introduction, Absolute approximation, Epsilon approximation, Polynomial time Approximation schemes, probabilistically good algorithms.

Unit IV. Geometric Algorithms

Prerequisites – Basic properties of line, intersection of line, line segment, polygon,etc. Line segment properties, detaining segment intersection in time complexity (n log n),Convex full problem – formulation, solving by Graham scan algorithm, Jarvis march algorithm; closest pair of points – problem formulation, solving by divide & conquer method.

Unit V. Linear Programming

Standard and Slack forms, formulation of problems as linear programs, simplex algorithm, duality, initial basic feasible solution. Problem formulation for – single source shortest path, maximum flow problem, Vertex cover problem, Knapsack problem.

Unit VI. Probability Based Analysis

Expectations: Introduction, Moments, Expectations of functions of more than one random variable, transform methods, moments and transforms of distributions,

computation of mean time to failure, inequalities and limit theorems

Reference Books:

1. Kishore S. Trivedi, “Probability & Statistics with Reliability, Queing, and Computer Science Applications” PHI

2. Cormen, Leiserson, Rivest, “Algorithms”, PHI

3. Bressard, “Fundamentals of Algorithms”, PHI

4. Horowitz, Sahni, “Fundamentals of Computer Algorithm”, Galgotia

5. S. Baase, S and A. Van Gelder, "Computer Algorithms: Introduction to Design and

Analysis", 3rd edition. Addison Wesley,2000

6. Aho, Hopcraft, Ullman, “The Design and Analysis of Computer Algorithms”, Addison Wesley

7. Knuth, “Art of Programming”, Addison Wesley

8. C Papadimitriou and K Steiglitz, “Combinatorial Optimization”, PHI