5CS6.1 ADVANCED DATA STRUCTURE (Common to Comp. Engg. & Info. Tech) |
|
|---|---|
| Units | Contents of the subjects |
| ADVANCED TREES: Definitions, Operations on Weight Balanced Trees (Huffman Trees), 2-3 Trees and Red- Black Trees. Dynamic Order Statistics, Interval Tree; Dictionaries. | |
| MERGEABLE HEAPS: Mergeable Heap Operations, Binomial Trees, Implementing Binomial Heaps and its Operations, 2-3-4. Trees and 2-3-4 Heaps. Amortization analysis and Potential Function of Fibonacci Heap, Implementing Fibonacci Heap. | |
| GRAPH THEORY DEFINITIONS: Definitions of Isomorphic Components. Circuits, Fundamental Circuits, Cut-sets. Cut- Vertices Planer and Dual graphs, Spanning Trees, Kuratovski's two Graphs. GRAPH THEORY ALGORITHMS: Algorithms for Connectedness, Finding all Spanning Trees in a Weighted Graph, Breadth First and Depth First Search, Topological Sort, Strongly Connected Components and Articulation Point. Single Min-Cut Max-Flow theorem of Network Flows. Ford-Fulkerson Max Flow Algorithms. | |
| SORTING NETWORK: Comparison network, zero-one principle, bitonic sorting and merging network sorter. Priority Queues and Concatenable Queues using 2-3 Trees. Operations on Disjoint sets and its union-find problem, Implementing Sets. | |
| NUMBER THEORITIC ALGORITHM: Number theoretic notions, Division theorem, GCD, recursion, Modular arithmetic, Solving Modular Linear equation, Chinese Remainder Theorem, power of an element, Computation of Discrete Logarithms, primality Testing and Integer Factorization. | |
Text/References:
1. Cormen, Leiserson, Rivest: Introduction to Algorithms, Prentice Hall of India.
2. Horowitz and Sahani: Fundamental of Computer algorithms.
3. Aho A.V , J.D Ulman: Design and analysis of Algorithms, Addison Wesley
4. Brassard : Fundamental of Algorithmics, PHI.