Topics in Algorithms

---

Topics in Algorithms will cover a bunch of advanced algorithms like:

• Spanning trees and network design
  • We would study Fibonacci Heaps
  • More modern algorithms for spanning trees
  • Directed spanning trees, aka Arborescences
  • Steiner trees: Where some vertices are optional to include in the tree.
• Network flows
  • Min cost flows
  • Flows with demands
  • Multi-commodity flow.
• Cuts and metrics Along with their applications which would involve discussions on techniques like:
• Amortized Analysis
• LP
• multiplicative weight update method
• scaling techniques

---

Notes

• Randomized Algorithms
• Minimum Spanning Trees
  • Properties of Minimum Spanning Trees
  • Some Algorithms for finding the Minimum Spanning Trees
    • Kruskal’s Algorithm
    • Prim’s Algorithm
      • Binary Heaps
      • Binomial Heaps
      • Fibonacci Heap
    • Boruvka’s Algorithm
    • Fredmen and Tarjan’s Algorithm
    • Karger, Klein and Tarjan’s Algorithm
      • Complexity of KKT Algorithm
      • Verification of MST
  • Steiner Trees
    • Steiner Trees are NP Complete
    • Polytime Approx Algo for Steiner Trees
    • Generalized Steiner Tree-Forest Problem
  • Arborescence
    • Algorithm for Arborescence
  • Matroids
    • Examples of Matroids
    • Representable Matroids
  • Linear Programming
    • Primal - Dual LP
    • Duality Theorems for LP
    • Urgh really don’t wanna write LP for spanning Tree and Arborescence, if someone seeing this wants to write, it will be great help!
    • Tree Packing
      • Fractional Tree Packing
• Multi-way Cuts

---

MOCs

• Data Structures
• Complexity Theory
• Combinatorial Optimisation
• Verification of MST

---

Practicle Information

Evaluation:

• midsem
• endsem
• assignment
• probably presentations

---

References