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