Bipartite Matching And Max Flow - Tweaks And Other Observations
A look at the bipartite matching problem and some observations about solving them using max-flow.
Bellman-Ford Algorithm's Applications - Triangular Arbitrage
Using the Bellman-Ford Single Source Shortest Path algorithm to detect triangular arbitrage.
3 CNF SAT Fail.
So, at 2:00 am last night I decided I had completed my 3-CNF-SAT algorithm (which runs in polynomial time!!). Well, here is the pseudocode: ROUTINE(P): -> Make a hashtable 'h' of size 3 * no. of clauses -> For clause p in P: for each 'distinct' variable x in p: h[x] += 1 -> Find [...]
Disjoint Set Data Structure
Two implementations of a disjoint set data structure and an implementation of kruskal's algorithm.
Weirdest Analyses Ever
This semester I had the fortune of taking Dr. Greg Frederickson's CS 381 (Algorithms) class. And boy did I see weird stuff in there. Below, I have a list of analyses I say are downright the most non-obvious (and in a way beautiful to look at). Edmonds-Karp Algorithm (Max Flow in a network): This algorithm [...]