Coin Changing

Goal: Given U.S, Currency denominations ${1, 5, 10, 25, 100}$, devise a method to pay amount to cusotmer using the fewest coins.

Cashier's Algorithm

Cashier's algorithm: at each itearation add coin of the largets value that does not take us past the amount to be paid:

Sort $n$ coin denominations so that $0 < c_1 < c_2 < \cdots < c_n$ S $\leftarrow \varnothing$ (multiset of coins selected).

While $x>0$,

• $k \leftarrow$ largest coin denomination $c_k$ such that $c_k \leq x$.

• If (no such $k$)

  • Return "no solution"

• Else

  • $x \leftarrow x - c_k$.
  • $s \leftarrow S \cup {k}$

Return $S$

Cashier's Algorithm is not always optimal.

The properties of any optimal solutions (for U.S. coin denominations):

• the number of pennies $\leq 4$ (proof: replace 5 pennies with 1 nickel)
• number of nickels $\leq 1$.
• number of quarters $\leq 3$
• number of nickels + dimes $\leq 2$ (proof: $\leq 1$ nickel, replace 3 dimes and 0 nickels with 1 quarter and 1 nickel; replace 2 dimes and 1 nickel with 1 quarter)

The optimality of cashier's algorithm (for U.S. coin denominations):

theorem: cashieer's algoirthm is optimal for U.S. coins $\{1,5,10,25,100\}$ proof (by induction on amount to be paid $x$)

• consider the optimal way to change $c_k \leq x \leq c_{k+1}$: greedy takes coin $k$.
• We claim that any optimal solution must take coin $k$.
  • if not, it needs enough coin of type $c_1, \cdots, c_{k-1}$ to add up to $x$.
  • table below indicates no optimal solution can do this.
• Problem reduces to coin-changing $x-c+k$ cents, which, by induction, is optimally solved by cahsier's algorithm.

Interview Scheduling

Job $j$ starts at $s_j$ and finishes at $f_i$. Two jobs are compatible if they don't overlap. Goal: find the maximum subset of mutually compatible jobs.

Earliest Finish Time First Algorithm

Earliest-finish-time-first ($n, s_1, s_2, \cdots, s_n, f_1, f_2, \cdots, f_n$)

Sort jobs by finish tmes and renumber so that $f_1 \leq f_2 \leq \cdots \leq f_n$. S $\leftarrow \varnothing$ (set of jobs selected). For $j = 1$to $n$

• If (job $j$ is compatible with $S$)
• $s \leftarrow S \cup \{j\}$

Return $S$.

Preposition: can implement earliest-finish-time first in $O(n\log n)$ time.

• keep track of job $j*$ that was added last to $S$.
• Job $j$ is compatible with $S$ iff $s_j \geq f_{j*}$
• Sorting by finish times takes $O(n \log n)$ time.

Theorem: the earliest-finish-time-first algorithm is optimal. Proof (by contradiction):

• assume greedy is not optimal, and let's see wha thappens
• Let $i_1, i_2, \cdots i_k$ denote the set of jobs selected by greedy.
• Let $j_1, j_2, \cdots, j_m$ denote thes et of jobs in an optimal solution with $i_1 = j_1, i_2 = j_2, \cdots, i_r = j_r$ for the largest possible value of $r$.

Interval Partitioning

Lecture $j$ starts at $s_j$ and finishes at $f_j$.

Goal: find minimum number of classrooms to schedule all lectures so that no two lectures occur at the same time in the same room.

Earliest-start-time-first ($n, s_1, s_2, \cdots, s_n, f_1, f_2, \cdots, f_n$)

Sort lectures by start times and renumber so that $s_1 \leq s_2 \leq \cdots \leq s_n$ $d \leftarrow 0$ (number of allocated classrooms)

For $j = 1$ to $n$,

• If (leucture $j$ is compatible with some classroom)
  • Schedule lecture $j$ in any such classroom $k$.
• Else
  • Allocate a new classroom $d+1$.
  • Schedule lecutre $j$ in classroom $d+1$
  • $d \leftarrow d+1$.
• Return schedule

Lower bound on optimal solution: the depth of a set of open intervals is the maximum number of intervals that contain any given point.

• the number of classrooms needed $\geq$ depth.

Q: does the minimum number of classrooms needed always equal depth? A: Yes! Moreover, earliest-start-time-first algorithm finds a schedule number of classroom equals the depth.

Analysis: the earliest-start-time-first algorithm never schedules two incompatible lectures in the same classroom.

• Theorem: earliest-start-time-first algorithm is optimal.
• Proof:
  • let $d =$ number of classrooms that the algorithm allocates.
  • Classroom $d$ is opened because we needed to schedule a lecture, say $j$, that is incompatible with a lecture in each of $d-1$ other classrooms.
  • Thus, these $d$ lectures each end after $s_j$.
  • Since we sorted by start time, each of these incompatible lecture in each of these incompatible lectures start no later than $s_j$.
  • Thus, we have $d$ lectures overlapping at time $s_j + \varepsilon$.
  • Key observation $\rightarrow$ all schedules use $\geq d$ classrooms.

Scheduling to minimize lateness.

Single resource processes one job at a time. Job $j$ requires $t_j$ units of processing time and is due at $d_j$. If $j$ starts at time $s_j$, it finishes at time $f_j = s_j+t_j$. Lateness = $\ell = max \{ 0, f_j - d_j \}$. Goal: schedule all jobs to minimize maximum lateness $L=max_j \ell_j$.

Earliest-Deadline-First ($n,t_1, t_2,\cdots, t_n, d_1, d_2, \cdots, d_n$): Sort jobs by due times and renumber so that $d_1 \leq d_2 \leq \cdots \leq d_n$. $t \leftarrow 0$. For $j=1$ to $n$:

• Assign job $j$ to interval [$t, t+t_j$]
• $s_j \leftarrow t$; $f_j \leftarrow t + t_j$.
• $t \leftarrow t+ t_j$

Return intervals $[s_1, f_1],[s_2, f_2],\cdots,[s_n, f_n]$

We want no idle time.

• Observation 1: there exists an optimal schedule with no idle time.
• Observation 2: the earliest-deadline-first schedule has no idle time.

Inversions: given a schedule $S$, an inversion is a pair of jobs $i$ and $j$ such that: $i < j$ but $j$ is scheduled before $i$.

Observation 3: the earliest-deadline-first schedule is the unique idle-free schedule with no inversions.

Observation 4: if an idle-free schedule has an inversion, then it has an adjacent inversion (two inverted jobs scheduled consecutively). The proof is as follows:

• let $i-j$ be a closeset inversion
• let $k$ be element immediately to the rght of $j$.
• case 1: $[j>k]$ then $j-k$ is an adjacent inversion
• case 2: $[j<k]$ then $i-k$ is a closer inversion since $i < j< k$.

Key claim: exchanging two adjacent, inverted jobs $i$ and $j$ reduces the number of inversions by 1 and does not increase the max lateness.

Proof: let $\ell$ be the lateness before the swal and let $\ell'$ be it afterwards.

• $\ell'_k = \ell_k$ for all $k \neq i, j$
• $\ell'' \leq \ell_i$
• If job $j$ is late, $\ell'_j = f'_j - d_j$ (by definition)
  • $\ell'_j = f_i - d_j$ ($j$ now finishes at time $f_i$)
  • $\ell'_j \leq f_i - d_i$ ($i<j \rightarrow d_i \leq d_j$)
  • $\ell'_j \leq \ell_i$ (by definition)

Analysis

Theorem: the earliest-deadline-first schedule $S$ is optimal. Proof by contradiction: Define $S*$ to be an optimal schedule with the fewest inversion (optimal schedule can have inversions).

• Can assume $S*$ has no idle time (by observaion 1)
• Case 1: [$S*$ has no inversions] then $S=S*$ (by observation 3)
• Case 2: [$S*$ has an inversion]
  • Let $i-j$ be an adjacent inversion (by observation 4)
  • Exchanging jobs $i$ and $j$ decreases the number of inversions by 1 without increasing max lateness (key claim)
  • contradicts "fewest inversions" part of the definition of $S*$.

Greedy Analysis Strategy

Greedy algorithm stays ahead. Show that after each step of the greedy algorithm, its solution is at least as good as any other algorithm's.

Structural: discover a simple "structural" bound asserting that every possible solution must have a certain value. Then show that your algoirthm always achieves this bound.

Exchange argument: gradually transofrm any solution to the one you found by the greedy algirhtm without hurting its quality.

The other greedy algorithms: gale-shapley, kruskal, prim, dijkstra, huffman,...

Dijkstra's Algorithm

The Problem

The Single-pair shortest path problem: Given a diagraph $G = (V,E)$, edge lengths $\ell_e \geq 0$, source $s \in V$, and destination $t \in V$, find a shortest directed path from $s$ to $t$.

The Single-source shortest path problem: Given a diagraph $G = (V,E)$, edge lengths $\ell_e \geq 0$, source $s \in V$, and find a shortest directed path from $s$ to every node.

Dijkstra's Algorithm (for single-source shortest paths problem): The greedy approach: maintain a set of explored nodes $S$ for which algorithm has determined $d[u]=$ length of a shortest $s\rightsquigarrow u$ path.

• initialize $S \leftarrow \{s\}$, $d[s] \leftarrow 0$.
• repeatedly choose unexplored node $v \notin S$ which minimizes $\pi (v) = \underset{e = (u,v): u \in S}{\min} d[u] + \ell_e$ (the length of a shortest path from $s$ to some node $u$ in explored part $S$, followed by a single edge $e = (u,v)$). add $v$ to $S$, and set $d[v] \leftarrow \pi(v)$.
• To recover path, set $pred[v] \leftarrow e$ that achieves min.

Proof of correctness:

Invariant: for each node $u \in S: d[u]$ = length of a shortest $s\rightsquigarrow u$ path. Proof by induction on $|S|$:

• base case: $|S| = 1$ is easy since $S = \{s\}$ and $d[s]=0$
• inductive hypothesis: assume true for $|S| \geq 1$
  • let $v$ be the next node added to $S$, and let $(u,v)$ be the final edge.
  • a shortest $s\rightsquigarrow u$ path plus $(u,v)$ is an $s\rightsquigarrow v$ path of length $\pi(v)$.
  • Consider any other $s\rightsquigarrow v$ path $P$. We show that it is no shorter than $\pi(v)$.
  • Let $e = (x,v)$ be the first edge in $P$ that leaves $S$, and let $P'$ be the subpath from $s$ to $x$.
  • The length $P$ is already $\geq \pi(v)$ as soon as it reaches $y$.

$\ell (P) \geq \ell(P') \geq d[x] + \ell _e \geq \pi(y) \geq \pi (v)$

• explanation for each $\geq$ sign:
  • non-negative lengths
  • induction hypothesis
  • definition of $\pi(y)$
  • dijkstra chose $v$ instead of $y$.

Efficient Implementation

Critical optimization 1: for each unexplored node $v \notin S$: explicitly maintain $\pi[v]$ instead of computing directly from definition: $\pi (v) = \underset{e = (u,v): u \in S}{\min} d[u] + \ell_e$

• For each $v \notin S:pi(v)$ can only decrease (because set $S$ increases).
• More specifically, suppose $u$ is added to $S$ and there is an edge $e = (u,v)$ leaving $u$. Then, it suffices to update: $\pi[v] \leftarrow min \{\pi[v], \pi[u] + \ell_e\}$ (recall: for each $u \in S$, $pi[u] = d[u] =$ length of shortest $s\rightsquigarrow u$ path).

Critical optimization 2: use a min-oriented priority queue (PQ) to choose an unexplored node that minimizes $\pi[v]$.

Implementation:

• Algorithm maintains $\pi[b]$ for each node $v$.
• Priority queue stores unexplored nodes, using $\pi[\cdot]$ as priorities.
• Once $u$ is deleted from the PQ, $\pi[u] =$ length of a shortest $s\rightsquigarrow u$ path.

Dijkstra $(V, E, \ell, s)$: For each $v \neq s: \pi[v] \leftarrow \infty$, $pred[v] \leftarrow null$; $\pi[s] \leftarrow 0$.

• Create an empty priority queue $pq$. For each $v \in V$: insert $(pq, v, \pi[v])$. While (is-not-empty($pq$)):
• $u \leftarrow$ del-min$(pq)$
• Foreach edge $e = (u,v) \in E$ leaving $u$:
  • If ($\pi[v] > \pi[u] + \ell_e$)
    • Decrease-key ($pq, v, \pi[u] + \ell_e$)
    • $\pi[v] \leftarrow \pi[u] + \ell_e$; $pred[v] \leftarrow e$

Minimum Spanning Trees

A path is a sequence of edges which connects a sequence of nodes.

A cycle is a path with no repeated nodes or edges other than the starting and ending nodes.

Example Path $P = \{ (1,2), (2,3), (3,4),(4,5),(5,6)\}$

A cut is a partition of the nodes into two nonempty subsets $S$ and $V-S$. The cutset of a cut $S$ is the set of edges with exactly one endpoint in $S$.

Cycle-cut intersection proposition: a cycle and a cutset intersect in an even number of edges.

• A cycle and a cutset intersect in an even number of edges.

Let $H = (V,T)$ be a subgraph of an undirected graph $G = (V,E)$. $H$ is a spanning tree of $G$ if $H$ is both acyclic and connected.

Some properties of spanning trees. Proposition: Let $H = (V,T)$ be a subgraph of an undirected graph $G=(V,E)$. Then, the following are equivalent:

• $H$ is a spanning tree of G
• $H$ is acyclic and connected
• $H$ is connected and has $|V|-1$ edges
• $H$ is acyclic and has $|V|-1$ edges
• $H$ is minimally connected: removal of any edge disconnects it
• $H$ is maximally acyclic: addition of any edge creates a cycle.

Given a connected, undirected graph $G = (V,E)$ wih edge costs $c_e$, a minimum spanning tree $(V,T)$ is a spanning tree of $G$ such that the sum of the edge costs in $T$ is minimized.

Cayley's Theorem: the complete graph on $n$ nodes has $n^{n-2}$ spnaninng trees (can't be solved by brute force).

Fundamental cycle: Let $H=(V,T)$ be a spanning tree of $G =(V,E)$.

• for any non tree-edge $e \in E: T \cup {e}$ contains a unique cyce, say $C$.
• for any edge $f \in C:(V,T \cup {e} - {f})$ is a spanning tree

Observation: if $c_e < c_f$, then $(V,T)$ is not an MST.

Fundamental cutset: let $H=(V,T)$ be a spanning tree of $G = (V,E)$.

• for any tree edge $f \in T: (V, T-{f})$ has two connected components.
• Let $D$ denote corresponding cutset.
• For any dge $e\in D:(V,T- {F} \cup {e})$ is a spanning tree.

In any cutset, the edge with minimum weight must be in every MST.

The Greedy MST Algorithm

• red rule:
  • let $C$ be a cycle with no red edge.
  • select an uncolored edge of $C$ of max cost and color it red.
• blue rule:
  • let $D$ be a cutset with no blue edges
  • select an uncolored edge in $D$ of min cost and color it blue.
• greedy algorithm:
  • apply the red and blue rules (nondeterministically), until all edges are colored. The blue edges form an MST.
  • note: can stop once $n-1$ edges colored blue.

Greedy algorithm: proof of correctness Color invariant: the exists an MST $(V, T*)$ containing every blue edge and no red edge Proof by indction on number of iterations.

• Base case: no edge colored -> every MST satisfies invariant
• Induction step (blue rule): suppose color invariant true before blue rule
  • let $D$ be a chosen cutset, and let $f$ be edge colored blue.
  • if $f \in T*$, then $T*$ still satisfiies invarant
  • otherwise, consider fundamental cycle $C$ by adding $f$ to $T*$.
  • let $e \in C$ be another edge in $D$.
  • $e$ is uncolored and $c_e \geq c_f$ since
    • $e \in T* \rightarrow e$ not red
    • blue rule $\rightarrow e$ not blue and $c_e \geq c_f$
  • Thus, $T* \cup {f} - {e}$ satisfies invariant
• Induction step (red rule): suppose color invariant true before red rule
  • let $C$ be chosen cycle, and let $e$ be edge colored red
  • if $e \notin T*$, then $T*$ still satisfies invariant
  • Otherwise, consider fundamental cutset $D$ by deleting $e$ from $T*$.
  • let $f \in D$ be another edge in $C$
  • $f$ is uncolored and $c_e \geq c_f$ since
    • $f \notin T* \rightarrow f$ not blue
    • red rule $\rightarrow f$ not red and $c_e \geq c_f$
  • Thus, $T* \cup {f} - {e}$ satisfies invariant.

Theorem: the greedy algorithm termiantes. Blue edges form an MST. Proof: we need to show that either the red or blue rule (or both) applies.

• suppose edge $e$ is left uncolored
• blue edge form a forest
• Case 1: both endpoints of $e$ are in the same blue tree $\rightarrow$ apply red rule to cycle formed by adding $e$ to blue forrest.
• Case 2: both endpoints of $e$ are in different blue trees. $\rightarrow$ apply blue rule to cutset induced by either of two blue trees.

Special cases are the Prim, Kruskal, reverse-delete, and more.

Prim's Algorithm

Initialize $S=\{s\}$ for any ndoe $s$, $T = \varnothing$ Repeat $n-1$ times:

• add to $T$ a min-cost edge with exactly one endpoint in $S$.
• Add the other endpoint to $S$.

Theorem: Prim's algorithm computes an MST. Proof: special case of greedy algorithm (blue rule repeatedly applied to S) (by construction, edges in cutset are uncolored).

Implementation

Theorem: prim's algorithm can be implemented to run in $O(m \log n)$ time. Proof: implementation almost identical to Dijkstra's algorithm.

Prim (V,E,c): $S \leftarrow \varnothing, T \leftarrow \varnothing$ $s \leftarrow$ any node in V.

Fo each $v \neq s: \pi[v] \leftarrow \infty$, $pred[v] \leftarrow null$; $\pi[s] \leftarrow 0$. Create an empty priority queue $pq$. For each $v \in V:$ insert($pq, v, \pi[v]$) While (is-not-empty($pq$))

• $u \leftarrow$ del-min($pq$)
• $S \leftarrow S \cup \{u\}, T \leftarrow T \cup \{pred[u]\}$
• For each edge $e=(u,v) \in E$ with $v \notin S$:
  • If ($c_e < \pi[v]$)
    • Decrease-key($pq, v, c_e$)
    • $\pi[v] \leftarrow c_e$; $pred[v] \leftarrow e$.

Kruskal's Algorithm

Consider edges in ascending order of cost: add to tree unless it would create a cycle.

Theorem: kruskal's algorithm computes an MST. Proof: special case of greedy algorithms.

• Case 1: both endpoints of $e$ in same blue tree, $\Rightarrow$ color $e$ red by applying red rule to unique cycle (all other edges in cycle are blue).
• Case 2: both endpoints of $e$ in different blue trees $\Rightarrow$ color $e$ blue by applying blue rule to cutset defined by either tree (no edge in cutset has smaller cost since Kruskal chose it first)

Implemetation

Theorem: Kruskal's algorithm can be implemented to run in $O(m \log m)$ tme.

• Sort edges by cost
• Use union-find data structure to dynamically maintain connected commponents.

The algorithm:

Kruskal (V,E,c) Sort $m$ edges by cost and renumber so that $c(e_1) \leq c(e_2) \leq \cdots \leq c(e_m)$. $T \leftarrow \varnothing$. For each $i=1$ to $m$:

• $(u,v) \leftarrow e_i$
• If (find-set($u$) $\neq$ find-set($v$)) (are u and v in same component)
  • $T \leftarrow T \cup {e_i}$
  • Union($u,v$) (make $u$ and $v$ in the same component). Return $T$.

Reverse-Delete Algorithm

Start with all the edges in $T$ and consider them in descending order of cost: delete edge from $T$ unless it would disconnect $T$.

Theorem: the reverse-delete algorithm computes an MST. Proof: special case of greedy algorithm:

• Case 1 (deleting edge $e$ does not disconnet $T$) $\Rightarrow$ apply red rule to cycle $C$ formed by adding $e$ (no edge in $C$ is more expensive since it would already been considered and deleted) to another path in $T$ between its two endpoints
• Case 2 (deleting edge $e$ disconnects $T$) $\Rightarrow$ apply blue rule ($e$ is the only remaining edge in the cutset as all other edges in $D$ must haev been colored red / deleted) to cutset $D$ induced by either component.

Borůvka′s algorithm

Repeat until only one tree

• apply blue rule to cutset corresponding to each blue tree
• color all selected edges blue

Theorem: Borůvka′s algorithm computes the MST (assume edge costs are distinct) Proof: special case of greedy algorithm (repeatedly apply blue rule)

Implementation

Theorem: Borůvka′s algorithm can be implemented to run in $O(m \log n)$ tme. Proof:

• to implement a phase in $O(m)$ time:
  • compute connected components of blue edges
  • for each edge $(u,v) \in E$, check if $u$ and $v$ are different components; if so, update each component's best edge in cutset
  • $\leq \log_2$ phases since each phase (at least) halves total # components.

Single-Link Clustering

Clustering The goal: given a set $U$ of $n$ objects labeled $p_1, \cdots, p_n,$ partition into clusters so that objects in different clusters are far apart.

Applications:

• routing in mobile ad-hoc networks
• document cateogrization for web seraches
• similarity searching in medical image databases
• cluster celstial objects into stars, quasars, galaxies.

Clustering of maximum spacing k-clustering: divide objects into $k$ non-empty groups.

Distance function: numeric value specifying "closeness" of two obejcts:

• $d (p_i, p_j) = 0$ iff $p_i = p_j$ (identity of indiscernibles)
• $d(p_i, p_j) \geq 0$
• $d(p_i, p_j) = d(p_j, p_i)$ (symmetry)

Spacing: min distance between any pair of points in different clusters Goal: given an integer $k$, find a $k$-clustiering of maximum spacing.

Greedy Clustering Algorithm

"Well-known" algorithm in science literature for single-linkage $k$-clustering:

• form a graph on the node set $U$, crresponding to $n$ clusters.
• find the closest pair of objects such that each objet is in a different cluster, and add an edge between them
• repeat $n-k$ times (until there are exactly $k$ clusters).

Key observation: this procedure is precisely Kruskal's algorithm (except we stop when there are $k$ connected components).

Alternative: find an MST and delete the $k-1$ longest edges.

Greedy Cluster Algorithm: Analysis Theorem: let $C*$ denote the clustering $C_1* , \cdots, C*_k$ formed by deleting the $k-1$ longets edges of an MST. Then, $C*$ is a $k$-clustering of max spacing. Proof:

• Let $C$ denote any other clustering $C_1, \cdots, C_k$
• Let $p_i$ and $p_j$ be in the same cluster in $C*$, say $C*_r$, but different clusters in $C$, say $C_s$ and $C_t$.
• Some edge ($p,q$) on $p_i - p_j$ path in $C*_r$ spans two different clusters in $C$. (this is the edge kruskal would have added next had we not stopped)
• Spacing of $C* =$ length $d*$ of the ($k-1$)st longets edge in MST.
• Edge ($p,q$) has length $\leq d*$ since it was added by Krusal
• Spacing of $C$ is $\leq d*$ since $p$ and $q$ are in different clusters