Contents

• 1. Advanced Trees

  ---

  Objectives, Introduction, Weighted Balanced Tree, Type of Weighted Balanced Tree, Augmenting Red-Black Tree, Dynamic Order Statistics, Dynamic Order Statistics Notation, Order Statistic Tree, Interval Tree, Interval Tree Properties, Interval Trichotomy, Interval Tree Operation, Application of Interval Tree, Dictionary, Dictionary Examples, Dictionary Operations, Review Questions.
   
  2. Mergable Heaps

  ---

  Objectives, Introduction, Mergable Heap, Binomial Tree, Definition, Recursive Definition of Binomial Tree (Based on Height k), Building a Binomial Tree, Properties of Order k Binomial Tree Bk, Binomial Heap, Definition and Properties of Binomial Heap, Binomial Heap Representation, Binomial Heap Operation, 2-3-4 Tree, Properties of 2-3-4 Tree, Representation of 2-3-4 Tree, 2-3-4 Tree Operations, 2–3–4 Heap, Amortized Analysis and Potential Function of Fibonacci Heap, Fibonacci Heap, Structure of Fibonacci Heap, Node Structure of Fibonacci Heap, Operation of Fibonacci Heap, Difference between Binomial Heap and Fibonacci Heap, Review Questions.
   
  3. Graph

  ---

  Objectives, Introduction, Definition of Graph, Basic Terms used in Graph, Application of Graph Theory, Types of Graph, Graph Representation, Adjacency Matrix, Edge List, Adjacency List, Graph Operations, Union, Intersection, Product of the Two Graph, Ring-Sum of Two Graph, Difference of Two Graph, Isomorphic Graph, Types of Isomorphism, Fundamental Circuit, Spanning Tree, Cut Set, Cut-Vertices, Finding Articulation Points in a Given Graph, Planar and Dual Graph, Planar Graph, Dual Graph, Kuratowski’s Two Graph, Algorithm of Connectedness, Minimum Spanning Tree, Minimum Spanning Tree (MST) Properties, Application of Minimum Spanning Tree, Construction of MST, The Minimum Spanning Tree Algorithm, Graph Planarity, Euler’s Formula, Planarity Testing, Graph Traversal, Breadth First Search, Depth-First-Search, Difference between BFS and DFS, Topological Sort, Strongly Connected Component (SCC), Maximum Flow, Flow Network, Residual Network, Augmenting Path, Max-Flow-Min-Cut Theorem, Ford-Fulkerson Algorithm, Review Questions.
   
  4. Sorting Network

  ---

  Objectives, Introduction, Comparison Network, Representation of Comparator, The Zero-One Principle, Bitonic Sorting Network, The Half Cleaner, Bitonic Sorter, Merging Network, Priority Queue, Types of Priority Queue, Priority Queue Operations, Priority Queue Application, Concatenable Queue using 2-3 Tree, Concatenable Segment Tree Operation, Disjoint Sets, Disjoint–Set Data Structure, Implementation of Disjoint-Sets, Union-Find Problem of Disjoint-Sets, Disjoint Set Applications, Implementing Sets, Review Questions.
   
  5. Number Theoritic Algorithm

  ---

  Objectives, Introduction, Number Theoretic Notations, Divisibility and Divisor, Prime and Composite Numbers, Division Theorem, Common Divisor, Greatest Common Divisors, Least Common Multiply, Greatest Common Divisor, Euclid Algorithm, Extended – Euclid Algorithm, Modular Arithmetic, Modular Arithmetic Useful Facts, Modular Arithmetic Operations, Modular Arithmetic Properties, Modular Arithmetic Applications, Solving Modular Linear Equation, A Linear Equation in One Variable, Mathematics for Linear Modular Equations, Chinese Remainder Theorem, Theorem of Chinese Remainder Theorem, Applications of Chinese Remainder Theorem, Power of an Element, Power of an Element with Repeated Squaring Method, Fermat’s Little Theorem, Computation of Discrete Logarithms, Coppersmith’s Algorithm, Primality Testing, The Simplest Primality Test, Fermat Primality Test, Miller Rabin Primality Test, Integer Factorization, Integer Factorization Algorithms, Review Questions.
   
  P. Papers