Algorithms and Data Structures

Instructor: 

Semester: 

  • 2012 Autumn/Monsoon (Aug - Dec)

Deterministic algorithms

  • Shortest path algorithms: Bellman-Ford, Dijkstra and Fibonacci heap.
  • Minimum Spanning Tree algorithms: Prim, Kruskal and Union-Find data structure
  • Max flow algorithms: Ford-Fulkerson, Dinic, Preflow-Push, bipartite matching
  • String matching algorithms
  • FFT and Multiplying polynomials

Randomized algorithms

  • randomized quicksort
  • incremental method based algorithms for some geometric problems (2-dim LP, convex hull)
  • All-pairs distances and all-pairs SPs

Monte Carlo algorithms

  • min-cut algorithms (Karger, Karger-Stein)
  • primality testing (Miller-Rabin)