Name of Subject  :

ADVANCED DATA STRUCTURES (5 IT 6.1)

Unit

Contents

s

ADVANCED TREES:

Definition

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

I

on Disjoint sets and its union-find problem Implementing Sets. Dictionaries, 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. Amortization analysis and Potential Function of Fibonacci Heap

II

Implementing Fibonacci Heap. SORTING NETWORK

:

Comparison network, zero-one principle, bitonic sorting and

merging network sorter.

GRAPH THEORY DEFINITIONS:

Definitions of Isomorphic Components. Circuits, Fundamental Circuits, Cut-sets.

III

Cut-Vertices Planer and Dual graphs, Spanning Trees, Kuratovski's two Graphs.

:

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

IV

Components and Articulation Point. Single Min-Cut Max-Flow theorem of Network Flows. Ford-Fulkerson Max

Flow Algorithms

NUMBER THEORITIC ALGORITHM:

Number  theoretic notation,  Division theorem, GCD recursion, Modular

V

arithmetic, Solving Linear equation, Chinese remainder theorem, power of an element, RSA public key Crypto