5EC6.2 ADVANCED DATA STRUCTURES |
|
---|---|
Units | Contents of the subjects |
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. | |
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. |
|
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. | |
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. | |
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. |