III B.E. (Computer Engg.)

V SEMESTER

5CP6.3 ADVANCED DATA STRUCTURES

1. ADVANCED TREES: Definitions and Operations on Weight Balanced Trees (Huffman Trees), 2-3 Trees and Red-Black Trees. Augment Red-Black Trees to Dynamic Order Statics and Interval Tree Applications. Operations on Disjoint Sets and its Union-Find Problem Implementing Sets. Dictionaries, Priority Queues and Concatenable Queues using 2-3 Trees.

2. MERGEABLE HEAPS: Mergeable Heap Operations, Binomial Trees Implementing Binomial Heaps and its Operations, 2-3-4. Trees and 2-3-4 Heaps. Structure and Potential Function of Fibonacci Heap, Implementing Fibonacci Heap.

3. GRAPH THEORY DEFINITIONS: Definitions of Isomorphism Components, Circuits, fundamental Circuits. Cut-sets, Cul - Vertices, Planer and Dual graphs. Spanning Trees. Kuratovski's two Graphs.

4. GRAPH THEORY ALGORITHMS: Algorithms for Connectness, Finding all Spanning Trees in a Weighted Graph and Planarity Testing Breadth First and Depth First Search, Topological Sort, Strong Connected Components and Aritculation Point. Single Source Shortest Path and All Pair Shortest Path Algorithms. Min-Cut Max-Flow theorem of Network Flows. Ford-Fulkerson Max Flow Algorithms.

Recommended Books:

1. Narsingh Deo -Graph Theory with Application to Engineering and Computer Science. Prentice Hall of India.

2. Baase -Computer Algorithms, pearson Education.

3. Cormen -Introduction to Algorithms. Prentice Hall of India.

4. Aho A.V., Hopcrptt J.E. and Ullman J.D. -The Design and Analysis of Computer Algorithms. Pearson Education.

5. Horowitz and Sawhni -Fundamentals of Data Structures. Galgotia Book Source