/algorithms

Primary LanguageJava

Implementations of Algorithms in Java

Derived from the Advanced Algorithms Course by Holczer Balazs.

  • Search
    • Breadth First Search (LinkedList queue)
      • Runtime: O(V+E)
      • Worst case memory: O(V)
    • Depth First Search
      • Runtime: O(V+E)
      • Worst case memory: O(V)
      • Applications
        • Stack implementation
        • Cycle detection (recursive)
        • Maze Solver (recursive)
        • Topological Ordering (recursive)
  • Shortest Path
    • Dijkstra's
      • Runtime: O(E + V*logV)
    • Bellman-Ford
      • Worst case runtime: O(E*V)
      • Best case runtime: O(E)
      • Worst case memory: O(V)
    • DAG Shortest Path
      • Runtime: O(V+E)
        • For the topological sort then an O(V) for the stack iteration.
  • Disjoint Sets
    • Kruskal's
      • Average run time: O(E*log V)
      • Worst case memory: O(E+V)
    • Prims-Jarnik
      • Eager implementation
        • Avg running time: O(E*logE)
        • Worst case running time: O(E*logV)
        • Memory: O(E)
      • Lazy implementation
        • Avg running time: O(E*logE)
        • Worst case: O(E*logV)
        • Memory: O(E)
  • Strongly Connected Components
    • Kosaraju
      • Runtime: O(V+E)
    • Tarjan
      • Runtime: O(V+E)
  • Maximum flow
    • Ford-Fulkerson
    • *Edmonds-Karp
      • Running time: O(VE^2) or O(V^2 E)
  • Traveling Salesman Problem
    • Simulated Annealing

Cool algorithm visualizations