Floyd-Warshall Algorithm solves the all-pairs shortest paths problem. We solve using dynamic programming.

constituents

initialization: d[u,v] = ∞ if u and v are not neighbors; d[u,v] = w(u,v) if u and v are neighbors; d[u,u] = 0.

subproblem: for all pairs \(u,v\), find the cost of the shortest path from \(u\) to \(v\) so that we only use the first \(1 … k-1\) vertices as internal “hops”.

recursion: two cases; for the \(k\) th new vertex introduced, if the shortest path does not go through \(k\) even with \(k\) added, then we can just copy the previous shortest path; if the shortest path goes through \(k\):

The Huffman Coding scheme is a coding scheme which gives the best Prefix-Free code (with the smallest Average Codeword Length) for any source with any arbitrary distribution.

Huffman Coding is Bounded

the Huffman Coding has the property that:

\begin{equation} \bar{l} \leq H(x) +1 \end{equation}

So, recall that any prefix free code for a source has at least entropy length; this gives:

\begin{equation} H(x) \leq \bar{\ell} \leq H(x)+1 \end{equation}

for source \(X\), and entropy of \(X\) given by \(H(X)\), and a Average Codeword Length returned by Huffman Coding \(\bar{\ell}\).

constituents

an undirected, conected, weighted graph

requirements

• a spanning tree is a tree that touches all of the vericies (i.e. a graph with no cycles)
• minimum spanning tree is a tree that connects all of the vertices with minimum edge cost

algorithm

Kruskal’s Algorithm

“smallest edge that doesn’t make a cycle”

TODO: create a table—algo, problem it solves, runtime, conditions. Prof lemmas?

Shortest-Path Algorithms

Dijikstra’s Algorithm

Intuition: subpaths of shortest paths are shortest paths. \(O\qty(n \log n + m)\)

Bellman-Ford Algorithm

Intuition: Dijkstra but k rounds across the whole graph

Floyd-Warshall Algorithm

All-pairs shortest path. Naive solution is \(O\qty(n)O\qty(nm) = O\qty(n^{2}m)\) by running bell

DP Problems

• fib
• shortest path
• longest common subsequence
• knapsack of all kinds
• independent set

Greedy

• activity selection
• scheduling
• DO THIS ON REVIEW: Huffman Coding is Greedy
• minimum spanning tree