Algorithms Overview

Union Find

Methods:

Union: Join 2 graph nodes
Find: Are 2 nodes connected?
[Root]: (for quick algos) find root of connection tree

Naive: O(n^2) Brute force solution must recursively check each node

Optimizations:

Quick Find: Store Ids in 'connections' subarray (N)
Quick Union: Use a Tree to join formed subarrays (N)
Weighted QU: Compare trees, put smaller below (Log N)
Path Compression: Set tree merges to point at root (Log* N)

Stack / Queue

Can be implemented with Linked List OR Array
O(1) add and remove / O(n) iteration
Iterate with *[Symbol.iterator]

Sorting

Merge Sort

Guaranteed O(n log n)
Split Recursively until array length 1, build up by merging
Stable sort (retains position on multiple key sorts)

Bottom-Up Merge Sort

Iterative approach: Two for loops, second is n * 2 intervals
Compare in place by twos, fours, etc until merged

Quick Sort

Shuffle, partition from pivot, recurse left, recurse right
Avg O(1.3n log n) - faster than merge sort
Worst case is O(n^2) - when already sorted
Not stable

Priority Queues

Binary Heap

Starts at index 1
Max: O(1)
Del Max: O(log n) Swap with end, pop, and sink down
Add: O(log n) Push to end and bubble up

Heap Sort

In place with O(n log n) worst case
No use of cache memory
Not stable

Elementary Symbol Tables

Symbol Table

(Key, Value) Like an object, but ordered
Implemented with 2 sorted arrays (one keys, one values)
Retrieve in O(log n) with binary search
Insert O(n) - major flaw

Set

A collection of unique keys
Can be used for exception filters blacklisting / whitelisting

Binary Search Tree

A binary tree in symmetric order (left smaller, right larger)
Search / insert average case O(log n) / worst case O(n)
Pre order / In order / Post order traversals
Removal options: tombstone (leave key, rm value)
Or: Hibbard Deletion (replace with right's lesser child) - leads to asymmetrical O(sqrt(n)) operations tree
Validate recursively with min/max

Balanced Search Trees

Guaranteed O(log n)

2-3 Search Trees

Each node 1 key (2 child) / 2 key (3c) => if 3 key, new parent

Red-Black Trees

2-3 trees, 2 key trees represented as red path
Default red path on insertion, then adjustment, rules:
Red path must lean left, only 1 red path per node
To follow rules, perform operations:
Flip colors, rotate left, rotate right

Hash Tables

Best for short keys, unordered values

Hashing Function

Hashing functions should give all indices equally
One way is Horner's method (character * 31) % 2
Birthday problem: Collisions are inevitable
Coupon Collector / Load Balancing: Evenly distributed

Separate Chaining

Dealing with Collisions using a LinkedList
Constant time lookup avg, worst case linear

Linear Probing

'Open addressing' using array, try next (i + 1) if full
Forms clusters that must searched on retrieval, kept small
Can be prevented by 'Two probe' or 'Double hashing'

Undirected Graphs

Use 'marked' and 'edgeto' properties to search

DFS

DFS: Maze Exploration of possible paths - recursion or stack

Connected Components - Are 2 components in connected subgraph?

BFS

BFS: Branching search - queue

find path between 2 nodes

Challenges

Bipartite Graph: Is every (red) connected to only (blacks) O(n)
Eulerian Cycle: Traverse every edge exactly once O(n)
Hamiltonian Cycle: Visit each vertex exactly once (intractable)
Graph isomorphism: Are 2 graphs identical despite vertex names? (unknown)
No overlap layout: Extremely complex but O(n)

Directed Graphs (dirGraphs)

Vertex has indegree (arrows in) and outdegree (arrows out)

Program flow is always a digraph
Garbage collection is a digraph of pointers

DFS + BFS

DFS code same as undirected (marked, edgeTo, arrays)
BFS code same as undirected (marked, edgeTo, distTo arrays)
Web crawler (BFS)

Topological Sort

How can you schedule tasks with precedence constraints?
Draw DAG (directed acyclic graph) so all the edges point up
Solve with DFS (create reverse postOrder stack)

Strong(ly Connected) Components

Points directed at each other - can be through other points
Works similar to connected component subarrays

Kosaraju-Sharir Algorithm

Used to find all strongly connected components

FIRST topological sort => on reverse() version of graph
THEN iterate normal graph in order of rev pOs - group DAG kernel

Minimum Spanning Trees

Definition: Shortest way to connect edge weighted graph - acyclic

Greedy Algorithm

Cut: A partition of the graph into two non-empty sets Crossing edge: connects a vertex in one set to one in the other

Continually cut, find minimum edge (black) until no more cuts w/o black
While (vertex count - 1 black edges), continue cutting
Graph not connected? Minimum spanning forest

Kruskal's Algorithm

Sort edges by shortest first, keep adding until there's a cycle

Use queue, min heap, union find
Repeat until (V - 1) edges
worst O(n log n)

Prim's Algorithm

Start with vertex 0, add min weight edge to MST -> (a queue)

Re evaluate min weight edge which connects to the tree
Use priority queue (min heap) to hold all edges (Lazy solution)
Repeat until (V - 1) edges
(Eager) - What is the best way to get to the tree, considering current edges? (Need INDEXED priority queue)

Shortest Paths

For edge weighted digraphs - how do we get from one vertex to every other vertex?

Iterate through weighted edges branching from origin, in increasing length

Dijkstra's Algorithm

Computes a SPT (Shortest Path) in any edge weighted digraph with non-negative weights

Relaxing paths always decreases length
Use Indexed PQ (with decrease keys) -> makes an asymptotic difference with fibonacci heap

McZenith/all-algorithms