III B.E. (Information Technology)

V SEMESTER

5 IT6.4 ADVANCED DATA STRUCTURES

  1. Advanced Trees: Definitions and Operations on Weight Balanced Trees (Huffman Trees), 2-3 Trees and Trees and Red Black Trees. Augmenting Red Black Trees to Dynamic Order Statistics 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. Structures and Potential Function of Fibonacci Heap. Implementing Fibonacci Heap.

  3. Graph Theory Definitions: Definitions of Isomorphism, Components, Circuits, Fundamental Circuits, Cut Sets, Cut-Vertices, Planer and Dual graphs, Spanning Trees, Kuratovski’s two Graphs.

  4. Graph Theory Algorithms: Algorithms for Connectedness, Finding all Spanning Trees in a Weighted Graph and Planarity Testing. Breadth First and Depth First Search. Topological Sort, Strongly Connected Components and Articulation Point. Single Source Shortest Path and All Pair

  5. shortest Path Algorithms Min Cut Max Flow Theorem of network. Flows ford Fulkerson Max Flow Algorithms.

Recommended Books:

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

  2. Base – Computer Algorithms, Pearson Education.

  3. Cormen – Introduction to Algorithms, Prentice Hall of India.

  4. Aho A.V. Hopcrpft. J.E. and Ullman J.D. – The Design and Analysis of Computer algorithms, Pearson Education.

  5. Horowitz and Sawhni – Fundamentals of Data structure, Galgotia Book Source.