Skip to content

Latest commit

 

History

History
25 lines (21 loc) · 1.24 KB

README.md

File metadata and controls

25 lines (21 loc) · 1.24 KB
Raw

Algorithms

A random collection of different Graph, Greedy, Divide-and-conquer and NP-Complete Algorithms

Graph

  • Shortest-Path: Dijkstra
  • All-Pair Shortest-Path: Floyd-Warshall APSP
  • All-Pair Shortest-Path: Bellman-Ford (Modifed) APSP
  • Max-Spacing Clusters: Max-Spacing K-Clusters
  • Min-Spanning Tree: Prim's MST
  • Mininum Cut: Karger's Randomized Min Cut
  • Strongly Connected Components: Kosaraju Two-Pass

Greedy

  • Knapsack Problem: Dynamic Programming solution
  • Optimal Binary Search Trees: Min possible average search time on BST with keys
  • Scheduler Cache-Miss Optimizer: Variation of Least Recently Used (LRU) with locality of reference

Divide-And-Conquer

  • Inversion Count: Piggy-Back on Merge-Sort counting array inversions
  • Median Maintenance: Two-Heap solution on maintaining a median of a stream of numbers
  • Two-Sum Algorithm: Hash-Table solution of 1-million entries for 20k sums

NP-Complete

  • 2-SAT: Papadimitriu's Algorithm. A randomized Local Search for the 2-Boolean Satisfiability Problem
  • Travelling Salesman: Bellman-Held-Karp Algorithm. Dynamic Programming solution of the problem