5EC6.2 ADVANCED DATA STRUCTURES

  Units    Contents of the subjects
I
ADVANCED TREES: -Definitions and operations on weight balanced trees(Huffman trees), 2-3 trees and Red-Black trees. Augmenting Red-Black trees todynamic order statistics and interval tree applications. Operations on disjoint sets and its Union-Find problem. Implementing sets, discitionerics, priority queues and concatenable queues using 2-3 trees.
II

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.

III
GRAPH THEORY DEFINITIONS: -Elements of telephone transmission networks, symmetrical and Asymmetrical two port networks. Different Attenuators, p-section & Tsection attenuators, stub matching, Transmission equalizers Filters, constant K-section, Ladder type, p-section, T-section filter, m-derived filter sections, Lattics filter section.
IV
GRAPH THEORETIC ALGORETHMS:-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.
V
APPLICATION OF GRAPHS:-Single source shortest path and all pair shortest path algorithms. Min-Cut Max-Flow theorem of network flows, Ford-Fulkerson Max Flow algorithms.
Text/References:
• “ Data Structures using C” by A.M. Tanenbaum.
• “The C Programming Language” by Kerninghan.
• “An introduction to data structures with applications: by Trembly and Sorenson.
• “Fundamentals of Data structures” by Horowitz and Sahani.