5EC6.2 ADVANCED DATA STRUCTURES

UNIT 1 : 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.

UNIT 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

.

UNIT 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.

UNIT 4 : 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.

UNIT 5 : 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.