/GraphsAlgorithms

Javascript implementation of a bunch of different graph algorithms

Primary LanguageJavaScript

This project is a website in which I present the implementations I've written in Javascript of various algorithms and data-structures. I have a couple of different visualizations in place, and some other fun experiments in related areas.

Algorithms / Data Structures / Programs Implemented

Divide and Conquer

  • Deterministic Linear Time Median Find (BFPRT)
  • Maximum Subarray
  • Element Multiplicity
  • Multiplication of Hadamard Matrices by Column Vectors
  • Finding a Majority Element (with only equality, no ordering comparisons)

Drawing / Layout

  • Knuth's Wide Tree Layout Algorithm
  • Wetherell-Shannon's Minimum Width Tree Layout Algorithm
  • Wetherell-Shannon Tree Layout Algorithm

Dynamic Programming

  • Edit Distance
  • Exam Questions
  • Arithmetic Expression Validation (Generalizable to CYK Algorithm)
  • Job Scheduling
  • Palincomplementary Subsequence
  • Viterbi's Algorithm
  • String Splitting

Graph Algorithms

  • Bellman-Ford Algorithm (INCOMPLETE)
  • Ford-Fulkerson Method (Edomnd's Karp Algorithm)
  • Kruskal's Algorithm for Minimum Spanning Tree
  • Prim's Algorithm for Minimum Spanning Tree

Greedy Algorithms

  • Huffman Coding

Linear Programming

Randomized Algorithms

  • Karger's Min Cut
  • K-th Selection

Sorting

  • Insertion Sort
  • Selection Sort
  • Quicksort

Other

  • TA Hours problem (reduction to Max Flow)
  • Hexagonal Tiling
  • Conway's game of Life Simulation
  • Elementary Cellular Automata Simulation

Data Structures

  • Splay Tree
  • Binary Tree
  • Union Find