• R. Inkulu     Bio    Courses    Papers
  • Discrete Mathematics
  • Data Structures
  • Algorithms
  • Theory of Computation   ← Spring '25

  • Advanced Algorithms
  • Computational Geometry

  • Introduction to Computing


  • Note -
    • Tree metrics
    • Arora's PTAS for Euclidean TSP
    • Geometry and algebra of LP
    • Computing shortest path trees in simple polygons
    • Computing a Euclidean shortest path in the plane
    • A few spanners in the Euclidean plane
    • Cluster graphs and geometric spanners

    • Tarjan's SCC finding
    • Satisfiability of a 2-CNF formula
    • Boolean product witness matrix
    • An algorithm for reachability in dynamic directed graphs
    • Computing an approximate minimum degree spanning tree
    • Boruvka's and KKT's algorithms for MST
    • A few spanners for undirected graphs
    • Uniform buy-at-bulk network design

    • Three fingerprinting techniques
    • Height-biased leftist heap
    • AVL tree
    • Amortized analysis of splay trees
    • Amortized analysis of disjoint-set forest
    • Bloom filter for set membership
    • Random treap
    • Skip list
    • LCA queries via range minima queries
    • A short note on tries

    • Lower bounding with adversary arguments
    • Well-known problems from class NP
    • NP-hardness and pseudo-polynomial time
    • The complexity class coNP
    • A few randomized complexity classes

    • A simple experiment to estimate Π
    • Proof by infinite descent
    • On the invariance principle
    • A few special numbers
    • Elementary discrete probability
    • On k-sets and k-levels
    • Dilworth's theorem on (anti)chains