Example: Change-making problem

Given $n$: the total cents of euros

Given $v$: an array of coin, e.g. $[200,100,50,20,10,5,2,1]$.

Question: How to split $n$ by $v$, making the number of coins minimized? $$ \min\sum a[i]\text{ s.t. }(n=\sum a[i]\cdot v[i]) $$ Greedy solution: Always take the largest coin that is less than current $n$.

Does it actually minimized the number of coins?

It depends. For canonical coin system like euros, it works. But for other systems, it doesn't.

Counterexample: $n=100,v=[60,50,10]$. The greedy algorithm returns $4$, while correct answer should be $2$.

Correct solution: Dynamic Programming, BFS...

Single Source Shortest Path

Notation

A graph $G=(V,E,W)$: set of vertices $V$, set of directed edges $E$, each edge is assigned with a weight $w\in W$.

Tree: acyclic graph

Claim: Given a source vertex $v$, the shortest paths from $v$ to every other vertex form a tree $T$, aka shortest path tree.

Dijkstra's Algorithm

This algorithm works if the weights are non-negative!

Start from the source node:

Choose the nearest unvisited node, explore the graph (update the distance and parent).
Mark the node as visited.

Running time: Depend on "how to choose the nearest unvisited node"

A good approach is priority queue.

~~Pseudocode omitted~~

Different Implementation of Dijkstra

	insert $n$	extract min $n$	decrease key $m$	total cost of Dijkstra
Normal array	$O(1)$	$O(n)$	$O(1)$	$O(n^2)$
Binary heap	$O(\log n)$	$O(\log n)$	$O(\log n)	$O(m\log n)$
Fibonacci heap	$O(1)$	amortized $O(\log n)$	amortized $O(1)$	$O(m+n\log n)$

Binary heap version runs fast in sparse graphs.

Minimum Spanning Tree

Here trees are undirect and weight graph.

Spanning tree $T$: A tree contains all nodes in $G$, s.t., all edges in $T$ are in $G$, and every node is connected.

MST minimizes the sum of the edge weights of the spanning tree.

Kruskal's Algorithm

ADD EDGE.

Data structure: disjoint set.

Start from the minimal weight edge, repeat:

Select the minimal weight edge that didn't break the tree-condition, choose and discard it.

Prim's Algorithm

ADD NODE.

Start from arbitrary unvisited node, repeat:

Select the path with minimal weight that connects an unvisited node to a visited node.
Mark the unvisited node of the selected path visited.

	insert \(n\)	extract min \(n\)	decrease key \(m\)	total cost of Dijkstra
Normal array	\(O(1)\)	\(O(n)\)	\(O(1)\)	\(O(n^2)\)
Binary heap	\(O(\log n)\)	\(O(\log n)\)	$O(\log n)	\(O(m\log n)\)
Fibonacci heap	\(O(1)\)	amortized \(O(\log n)\)	amortized \(O(1)\)	\(O(m+n\log n)\)