5EC6.2-ADVANCED DATA STRUCTURES |
Units: I-ADVANCED TREES |
Definitions and operations on weight balanced trees (Huffman trees), 2-3
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, discitionerics,
priority queues and concatenable queues using 2-3 trees.
|
Units: 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. |
Units: III-GRAPH THEORY DEFINITIONS |
Definitions of Isomorphism, Components, Circuits,
Fundamental Circuits, Cut-sets, Cut-Vertices, Planer and dual graphs, Spanning trees, Kuratovski’s two
graphs.
|
Units: 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.
|
Units: 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.
|