Greedy Algorithms 2
David Weir (U of Sussex) Program Analysis Term 1, 2015 251 / 192
The Minimum Spanning Tree Problem
David Weir (U of Sussex) Program Analysis Term 1, 2015 252 / 192
The Minimum Spanning Tree Problem
One of the most basic problems to do with graphs:
What is the “cheapest” way to interconnect objects in a network?
Model the situation as a graph where:
Assume edges have weights that give “cost” of a connection
Being interconnected means that there must be at least one path between every pair of objects in network
David Weir (U of Sussex) Program Analysis Term 1, 2015 253 / 192
Formulating the MST Problem
Given a graph G = (V , E ) and edge weight function w Find a subset E′ of E such that:
1 G′ = (V,E′) is connected
2 The total of the weights of edges in E′ is minimised
Two things to note:
G′ must be a tree
— otherwise leave edge(s) out to reduce weight
A path from u to v in G′ is not necessarily shortest paths in G
David Weir (U of Sussex) Program Analysis Term 1, 2015 254 / 192
MST Example
v4v5v 521
25
11 8
19
vv2vv 8473
21
6
3 v6
16
What is a minimum spanning tree for this weighted graph ?
David Weir (U of Sussex) Program Analysis Term 1, 2015 255 / 192
MST Example
45
v5 v2 v1
25
21
19
v8 v4 v7 v3
11 8
6
2
3
v6
16
Consider the path from v3 to v6 — length is more than 16
David Weir (U of Sussex) Program Analysis Term 1, 2015 256 / 192
MST Example for You
v2
2 12
9
v7v3v 153
6 10
v4
Indicate nodes that are in a minimum spanning tree for this weighted
graph?
David Weir (U of Sussex) Program Analysis Term 1, 2015 257 / 192
MST Example for You
v2
2 12
9
v7v3v 153
6 10 v4
Indicate nodes that are in a minimum spanning tree for this weighted graph?
David Weir (U of Sussex) Program Analysis Term 1, 2015 257 / 192
Solving the MST Problem
Turns out to be easy to solve using the greedy approach
Consider edges in order of increasing weight and include in E′ as long as no cycle created
Grow tree from arbitrary starting point, repeatedly connecting in vertices that are closest to what has been built so far
Consider edges in decreasing order of weight and exclude from G unless it disconnects the graph
Greedy approaches work because of the so-called Cut Property
David Weir (U of Sussex) Program Analysis Term 1, 2015 258 / 192
Cut Property
Given a graph G = (V,E) and edge weight function w, if V is split into two disjoint sets V1 and V2 then the least weighted edge {u,v} with u ∈ V1 and v ∈ V2 is contained in every minimum spanning tree of G.
V1 V2 16
v1 v4 5 11
v2 18
v3
6
v5
3
v6
this edge must be in an MST
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
259 / 192
Proof of Cut Property
Proof by contradiction (assumes all edge weights distinct):
Suppose that sets V1 and V2 and edge {u, v } are as in the proposition
{u,v} is not in the MST G′ = (V,E′) for the graph Consider path p in G′ from u to v
Path p must cross from V1 to V2
Let {u′,v′} be the edge that does this
Time for a picture
David Weir (U of Sussex) Program Analysis Term 1, 2015 260 / 192
Proof of Cut Property (cont.)
V1 u′
16
V2 v′
u
6
Any pair of vertices connected via {u′, v′} still connected via {u, v} We are reducing weight of E′ by substituting {u′, v′} by {u, v} Contradiction — G′ couldn’t have been a MST
v
David Weir (U of Sussex) Program Analysis Term 1, 2015 261 / 192
Kruskal’s MST Algorithm
Kruskal(G,w) :
let Q be the edges in E ordered by increasing weight initialise E′ to be the empty set
for each vertex v ∈ V
let C(v) be the singleton set containing v while |E′| < |V| − 1
remove edge {u, v } from Q if C(u) ̸= C(v) then
include {u,v} in E′
C(u) ← C(v) ← C(u) ∪ C(v) return E′
David Weir (U of Sussex) Program Analysis Term 1, 2015 262 / 192
Illustration of Kruskal’s Algorithm
v4v5v 521
25
19
vv2vv 8473
21
11
12
6 3
9
v6
16
Create Q and C(v) for each v ∈ V
David Weir (U of Sussex) Program Analysis Term 1, 2015 263 / 192
Illustration of Kruskal’s Algorithm
v4v5v 521
25
19
vv2vv 8473
21
11
12
9
6 3
16
v6
Remove edge {v4,v7} from Q
Q = ({v4, v7}, {v4, v6}, {v5, v2}, {v2, v1}, {v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex)
Program Analysis Term 1, 2015 264 / 192
Illustration of Kruskal’s Algorithm
21
v4v5v 521
25
11
v8 v4 v7 v3
6 3
16
12
19
2
9
v6
C(v4) ̸= C(v7) so add to E′ and combine clusters
Q = ({v4, v6}, {v5, v2}, {v2, v1}, {v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex) Program Analysis Term 1, 2015 265 / 192
Illustration of Kruskal’s Algorithm
21
v4v5v 521
25
11
v8 v4 v7 v3
12
19
9
2
6 3
16
v6
Remove edge {v4,v6} from Q
Q = ({v4, v6}, {v5, v2}, {v2, v1}, {v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex)
Program Analysis Term 1, 2015 266 / 192
Illustration of Kruskal’s Algorithm
21
v4v5v 521
25
11
v8 v4 v7 v3
12
19
9
2
6
3
16
v6
C(v4) ̸= C(v6) so add to E′ and combine clusters
Q = ({v5, v2}, {v2, v1}, {v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex) Program Analysis Term 1, 2015 267 / 192
Illustration of Kruskal’s Algorithm
21
v4v5v 521
25
11
v8 v4 v7 v3
12
19
9
2
6
3
v6
Remove edge {v5,v2} from Q
Q = ({v5, v2}, {v2, v1}, {v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
16
David Weir (U of Sussex)
Program Analysis Term 1, 2015 268 / 192
Illustration of Kruskal’s Algorithm
21
v4v5v 521
25
11
v8 v4 v7 v3
12
19
9
2
6
3
16
v6
C(v2) ̸= C(v5) so add to E′ and combine clusters
Q = ({v2,v1}, {v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex) Program Analysis Term 1, 2015 269 / 192
Illustration of Kruskal’s Algorithm
21
v4v5v 521
25
11
v8 v4 v7 v3
12
19
9
2
6
3
16
v6
Remove edge {v2,v1} from Q
Q = ({v2,v1}, {v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex)
Program Analysis Term 1, 2015 270 / 192
Illustration of Kruskal’s Algorithm
21
45
v5 v2 v1
25
11
v8 v4 v7 v3
12
19
2
6
3
9
v6
16
C(v2) ̸= C(v1) so add to E′ and combine clusters
Q = ({v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex) Program Analysis Term 1, 2015 271 / 192
Illustration of Kruskal’s Algorithm
21
45
v5 v2 v1 25
11
v8 v4 v7 v3
12
19
2
6
3
9
v6
Remove edge {v6,v7} from Q David Weir (U of Sussex)
16
Q = ({v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
Program Analysis Term 1, 2015 272 / 192
Illustration of Kruskal’s Algorithm
21
45
v5 v2 v1 25
11
v8 v4 v7 v3
12
19
2
6
3
9
v6
16
C(v6) = C(v7) so don’t add to E′
Q = ({v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex) Program Analysis Term 1, 2015 273 / 192
Illustration of Kruskal’s Algorithm
21
45
v5 v2 v1 25
11
v8 v4 v7 v3
12
19
2
6
3
9
v6
Remove edge {v6,v7} from Q David Weir (U of Sussex)
16
Q = ({v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
Program Analysis Term 1, 2015 274 / 192
Illustration of Kruskal’s Algorithm
21
45
v5 v2 v1 25
11
v8 v4 v7 v3
12
19
9
2
6
3
16
v6
C(v6) ̸= C(v8) so add to E′ and combine clusters
Q = ({v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex) Program Analysis Term 1, 2015 275 / 192
Illustration of Kruskal’s Algorithm
21
45
v5 v2 v1 25
11
v8 v4 v7 v3
12
19
2
6
v6
Remove edge {v4,v5} from Q
3 9
16
Q = ({v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex)
Program Analysis Term 1, 2015 276 / 192
Illustration of Kruskal’s Algorithm
21
11
45
v5 v2 v1 25
12
19
v8 v4 v7 v3
6
16
v6
C(v4) ̸= C(v5) so add to E′ and combine clusters
2
3 9
Q = ({v3,v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex) Program Analysis Term 1, 2015 277 / 192
Illustration of Kruskal’s Algorithm
21
11
45
v5 v2 v1 25
12
19
v8 v4 v7 v3
2
6
v6
Remove edge {v3,v1} from Q
3 9
16
Q = ({v3,v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex)
Program Analysis Term 1, 2015 278 / 192
Illustration of Kruskal’s Algorithm
21
11
45
v5 v2 v1 25
12
19
v8 v4 v7 v3
6
16
v6
C(v1) ̸= C(v3) so add to E′ and combine clusters
2
3 9
Q = ({v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex) Program Analysis Term 1, 2015 279 / 192
Illustration of Kruskal’s Algorithm
21
11
45
v5 v2 v1 25
12
19
v8 v4 v7 v3
6
16
v6
|E′| = |V| − 1 so we have found our minimum spanning tree
2
3 9
Q = ({v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex) Program Analysis Term 1, 2015 280 / 192
Illustration of Kruskal’s Algorithm
All done!
45
v5 v2 v1
11
12
2
v8 v4 v7 v3
3 9
v6
Q = ({v3, v6}, {v3, v2}, {v5, v8}, {v5, v7})
David Weir (U of Sussex)
Program Analysis Term 1, 2015 281 / 192
An example for you
v9v5v 521
7
vv2vv 8473
10 14 1 4
16
13
v6
3
12
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
282 / 192
An example for you
v9v5v 521
7
vv2vv 8473
16
3
12
10 14 1 4
13
v6
MST contains following edges (in order added):
{v1, v3}, {v4, v7}, {v4, v6}, {v2, v3}, {v5, v8}, {v5, v2}, {v5, v4}
David Weir (U of Sussex) Program Analysis Term 1, 2015 282 / 192
Proof of Correctness of Kruskal’s Algorithm
Follows from the Cut Property
Suppose that edge {u, v } is added by the algorithm
Let V1 be the vertices in C(u) and V2 be all the other vertices
Prior to adding {u,v} to E′ there are no paths involving edges in E′ from vertices in V1 to vertices in V2
Since edges are being considered in increasing order of weight, {u,v} must be the edge with the least weight connecting a vertex in V1 with one in V2
Hence, by the Cut Property, {u, v } is in every minimum spanning tree of the graph
David Weir (U of Sussex) Program Analysis Term 1, 2015 283 / 192
Kruskal’s MST Algorithm
Kruskal(G,w) :
let Q be the edges in E ordered by increasing weight initialise E′ to be the empty set
for each vertex v ∈ V
let C(v) be the singleton set containing v while |E′| < |V| − 1
remove edge {u, v } from Q if C(u) ̸= C(v) then
include {u,v} in E′
C(u) ← C(v) ← C(u) ∪ C(v) return E′
David Weir (U of Sussex) Program Analysis Term 1, 2015 284 / 192
Running Time of Kruskal’s Algorithm
Measure of progress:
Measure of progress is the number of edges left in Q Reduces by 1 every time through the loop
Gives upper bound on number of iterations of O(m)
David Weir (U of Sussex) Program Analysis Term 1, 2015 285 / 192
Running Time of Kruskal’s Algorithm (cont.)
Initialising Q:
Creating Q involves sorting E
E contains m elements
Sorting m elements can be done in O(m log m) steps Note that m is O(n2)
Furthermore, log n2 = 2 log n
Hence O(log m) = O(log n)
Hence the number of steps to create Q is O(m log n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 286 / 192
Running Time of Kruskal’s Algorithm (cont.)
Optimising the representation of clusters (sets)
Question: Which of set operations do we need to be particularly fast?
Answer:
Checking equality of two sets Producing the union of two sets
This is the so-called Union-Find data structure
We will look at this data structure in an exercise class
We can achieve an overall running time for the algorithm of O(m log n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 287 / 192
Another MST Algorithm
Discovered by Jarn ́ık in 1930
Rediscovered by Prim in 1957 Rediscovered (again) by Dijkstra in 1959 Most commonly known as Prim’s algorithm!
David Weir (U of Sussex) Program Analysis Term 1, 2015 288 / 192
Jarn ́ık’s Algorithm
Grows the tree E′ from an arbitrary starting point
As E′ grows, it spans an increasing number of the vertices
E′ grows by one at each iteration
Selects the edge that connects the closest vertex to the tree produced so far
Committing to this edge is safe due to the Cut Property
David Weir (U of Sussex) Program Analysis Term 1, 2015 289 / 192
The Closest Vertex
Consider a graph G = (V,E)
Suppose the algorithm has so far selected the set of edges E′ E′ spans the vertices S where S ⊆ V
In other words, G′ = (S,E′) is a spanning tree
Question: Which is the closest vertex to (S,E′)?
Answer: Vertex v which minimises w(u,v) where u ∈ S and v ̸∈ S
David Weir (U of Sussex) Program Analysis Term 1, 2015 290 / 192
Example
In this example we have E′ = {{v5, v7}, {v5, v2}} and S = {v2, v5, v7}
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
16 9
5
v6
26
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
291 / 192
Example
The closest vertex to (S, E′) is v4 due to the edge {v4, v7}
v 6 v 15 v 521
3
21
v8 v4 v7 v3
11 2 17
7
16 9
5
v6
26
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
292 / 192
Maintaining Distance from (S, E′)
Record distance of v from (S,E′) as value δ(v)
As E′ grows δ(v) may reduce
Also useful to record identify of the vertex u ∈ S where
refer to this value as Back to the example
δ(v) = w(v,u) β(v)
David Weir (U of Sussex) Program Analysis Term 1, 2015 293 / 192
Example
Recall that we have E′ = {{v5, v7}, {v5, v2}} and S = {v2, v5, v7}
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
16 9
5
v6
26
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
294 / 192
Example
Consider the values δ(v6) and β(v6) given this particular (T,S)
5
26
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
9 v6
16
δ(v6) = 16 β(v6) = v7
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
295 / 192
Example
What happens to δ(v6) when we were to add v4 to E′
v 6 v 15 v 521
3
21
v8 v4 v7 v3
11 2 17
7
16
9
5
v6
26
δ(v6) = 9 β(v6) = v4
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
296 / 192
Updating Distances
In order to maintain the values of δ as the size of E′ grows the algorithm must do the following:
When adding u into S (by adding the edge involving u into E′) must check all edges from u to some vertices v not yet in S to see if δ(v) can be reduced
As in Dijkstra’s Algorithm, we maintain a priority queue of vertices with lower δ values giving higher priority
David Weir (U of Sussex) Program Analysis Term 1, 2015 297 / 192
Jarn ́ık’s Algorithm
J a r n ́ı k ( G , w ) :
select some vertex s ∈ V and let δ(s) = 0 initialise E′ to be the set {}
for all v ∈ V − {s} let δ(v) = ∞
for all v ∈ V let β(v) = ⊥
let Q be a priority queue containing elements of V while |E′| < |V| − 1
remove u from front of priority queue Q
if β(u) ̸= ⊥ then (% i.e. u is not s)
add {u,v} to E′ where β(u) = v
for each {u,x} ∈ E where x remains in Q
if δ(x) > w(u,x) then let δ(x) = w(u,x) let β(x) = u
return E′
David Weir (U of Sussex) Program Analysis Term 1, 2015 298 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
11 2
17
vv7vv 8473
21
16 9
5
v6
26
v1 v2 v3 v4 v5 v6 v7 v8
δ∞∞∞∞∞∞0∞ β⊥⊥⊥⊥⊥⊥⊥⊥
Let s = v7, E′ = {}, and initialise δ and β as shown
David Weir (U of Sussex) Program Analysis Term 1, 2015 299 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
11 2
17
vv7vv 8473
21
16 9
5
v6
Remove v7 from Q David Weir (U of Sussex)
26
v1 v2 v3 v4 v5 v6 v7 v8
δ∞∞∞∞∞∞0∞ β⊥⊥⊥⊥⊥⊥⊥⊥
Program Analysis Term 1, 2015 300 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
11 2
17
vv7vv 8473
21
16 9
5
v6
Consider the edge {v7,v4} David Weir (U of Sussex)
26
v1 v2 v3 v4 v5 v6 v7 v8 δ∞∞∞∞∞∞0∞
β⊥⊥⊥⊥⊥⊥⊥⊥
Program Analysis Term 1, 2015 301 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
11 2
17
v8 v4 v7 v3
21
7
16 9
5
v6
26
v1 v2 v3 v4 v5 v6 v7 v8 δ∞∞∞∞∞∞0∞
β⊥⊥⊥⊥⊥⊥⊥⊥
δ(v4) > w(v7,v4) so update δ(v4) and β(v4)
David Weir (U of Sussex) Program Analysis Term 1, 2015 302 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
11 2
17
v8 v4 v7 v3
21
7
16 9
5
v6
Consider the edge {v7,v5} David Weir (U of Sussex)
26
v1 v2 v3 v4 v5 v6 v7 v8 δ∞∞∞7∞∞0∞
β ⊥ ⊥ ⊥ v7 ⊥ ⊥ ⊥ ⊥
Program Analysis Term 1, 2015 303 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
16 9
5
v6
26
v1 v2 v3 v4 v5 v6 v7 v8 δ∞∞∞7∞∞0∞
β ⊥ ⊥ ⊥ v7 ⊥ ⊥ ⊥ ⊥
δ(v5) > w(v7,v5) so update δ(v5) and β(v5)
David Weir (U of Sussex) Program Analysis Term 1, 2015 304 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
16 9
5
v6
Consider the edge {v7,v6} David Weir (U of Sussex)
26
v1 v2 v3 v4 v5 v6 v7 v8 δ∞∞∞73∞0∞
β ⊥ ⊥ ⊥ v7 v7 ⊥ ⊥ ⊥
Program Analysis Term 1, 2015 305 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
11 2
17
vv7vv 8473
16 26 9
21
5
v6
v1 v2 v3 v4 v5 v6 v7 v8 δ∞∞∞73∞0∞
β ⊥ ⊥ ⊥ v7 v7 ⊥ ⊥ ⊥
δ(v6) > w(v7,v6) so update δ(v6) and β(v6)
David Weir (U of Sussex) Program Analysis Term 1, 2015 306 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
11 2
17
vv7vv 8473
21
5
9 v6
16
26
v1 v2 v3 v4 v5 v6 v7 v8 δ ∞ ∞ ∞ 7 3 16 0 ∞
β ⊥ ⊥ ⊥ v7 v7 v7 ⊥ ⊥
All edges from v7 considered David Weir (U of Sussex)
Program Analysis Term 1, 2015 307 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
11 2
17
vv7vv 8473
21
16 9
5
v6
26
v1 v2 v3 v4 v5 v6 v7 v8 δ ∞ ∞ ∞ 7 3 16 0 ∞
β ⊥ ⊥ ⊥ v7 v7 v7 ⊥ ⊥
Remove v5 from Q and add {v5,v7} to E′
David Weir (U of Sussex) Program Analysis Term 1, 2015 308 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
16 9
5
v6
Consider the edge {v5,v2} David Weir (U of Sussex)
26
v1 v2 v3 v4 v5 v6 v7 v8 δ ∞ ∞ ∞ 7 3 16 0 ∞
β ⊥ ⊥ ⊥ v7 v7 v7 ⊥ ⊥
Program Analysis Term 1, 2015 309 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
16 9
5
v6
26
v1 v2 v3 v4 v5 v6 v7 v8 δ ∞ ∞ ∞ 7 3 16 0 ∞
β ⊥ ⊥ ⊥ v7 v7 v7 ⊥ ⊥
δ(v2) > w(v5,v2) so update δ(v2) and β(v2)
David Weir (U of Sussex) Program Analysis Term 1, 2015 310 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
16 9
5
v6
Consider the edge {v5,v4} David Weir (U of Sussex)
26
v1 v2 v3 v4 v5 v6 v7 v8 δ ∞ 6 ∞ 7 3 16 0 ∞
β ⊥ v5 ⊥ v7 v7 v7 ⊥ ⊥
Program Analysis
Term 1, 2015 311 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
16 9
5
v6
26
v1 v2 v3 v4 v5 v6 v7 v8 δ ∞ 6 ∞ 7 3 16 0 ∞
β ⊥ v5 ⊥ v7 v7 v7 ⊥ ⊥
δ(v4) < w(v4,v5) so don’t update δ(v4) or β(v4) David Weir (U of Sussex) Program Analysis
Term 1, 2015 312 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
16 9
5
v6
Consider the edge {v5,v8} David Weir (U of Sussex)
26
v1 v2 v3 v4 v5 v6 v7 v8 δ ∞ 6 ∞ 7 3 16 0 ∞
β ⊥ v5 ⊥ v7 v7 v7 ⊥ ⊥
Program Analysis
Term 1, 2015 313 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
16 9
5
v6
26
v1 v2 v3 v4 v5 v6 v7 v8 δ ∞ 6 ∞ 7 3 16 0 ∞
β ⊥ v5 ⊥ v7 v7 v7 ⊥ ⊥
δ(v8) > w(v5,v8) so update δ(v8) and β(v8) David Weir (U of Sussex) Program Analysis
Term 1, 2015 314 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
16 9
5
v6
All edges from v5 considered David Weir (U of Sussex)
26
v1 v2 v3 v4 v5 v6 v7 v8 δ ∞ 6 ∞ 7 3 16 0 21
β ⊥ v5 ⊥ v7 v7 v7 ⊥ v5
Program Analysis
Term 1, 2015 315 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
16 9
5
v6
26
v1 v2 v3 v4 v5 v6 v7 v8 δ ∞ 6 ∞ 7 3 16 0 21
β ⊥ v5 ⊥ v7 v7 v7 ⊥ v5
Remove v2 from Q and add edge {v2,v5} to E′ David Weir (U of Sussex) Program Analysis
Term 1, 2015 316 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
16 9
5
v6
Consider edge {v2,v1} David Weir (U of Sussex)
26
v1 v2 v3 v4 v5 v6 v7 v8 δ ∞ 6 ∞ 7 3 16 0 21
β ⊥ v5 ⊥ v7 v7 v7 ⊥ v5
Program Analysis
Term 1, 2015 317 / 192
Illustrating Jarn ́ık’s Algorithm
6 15
v5 v2 v1
3
21
vv7vv 8473
11 2 17
16 9
5
v6
26
v1 v2 v3 v4 v5 v6 v7 v8 δ ∞ 6 ∞ 7 3 16 0 21
β ⊥ v5 ⊥ v7 v7 v7 ⊥ v5
δ(v1) > w(v2,v1) so update δ(v1) and β(v1) David Weir (U of Sussex) Program Analysis
Term 1, 2015 318 / 192
Illustrating Jarn ́ık’s Algorithm
6 15
v5 v2 v1
3
21
vv7vv 8473
11 2 17
16 9
5
v6
Consider edge {v2,v3} David Weir (U of Sussex)
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 ∞ 7 3 16 0 21
β v2 v5 ⊥ v7 v7 v7 ⊥ v5
Program Analysis Term 1, 2015 319 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
vv7vv 8473
11 2
17
16 9
5
v6
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 ∞ 7 3 16 0 21
β v2 v5 ⊥ v7 v7 v7 ⊥ v5
δ(v3) > w(v2,v3) so update δ(v3) and β(v3)
David Weir (U of Sussex) Program Analysis Term 1, 2015 320 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
vv7vv 8473
11 2
17
16 9
5
v6
All edges from v2 considered David Weir (U of Sussex)
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 16 0 21
β v2 v5 v2 v7 v7 v7 ⊥ v5
Program Analysis Term 1, 2015 321 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
vv7vv 8473
11 2 17
16 9
5
v6
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 16 0 21
β v2 v5 v2 v7 v7 v7 ⊥ v5
Remove v4 from Q and add edge {v4,v7} to E′
David Weir (U of Sussex) Program Analysis Term 1, 2015 322 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
v8 v4 v7 v3
11 2 17
7
16 9
5
v6
Consider edge {v4,v6} David Weir (U of Sussex)
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 16 0 21
β v2 v5 v2 v7 v7 v7 ⊥ v5
Program Analysis Term 1, 2015 323 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 16 0 21
β v2 v5 v2 v7 v7 v7 ⊥ v5
11 2 17
7
16
9
5
v6
δ(v6) > w(v4,v6) so update δ(v6) and β(v6)
David Weir (U of Sussex) Program Analysis Term 1, 2015 324 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 9 0 21
β v2 v5 v2 v7 v7 v4 ⊥ v5
11 2 17
7
16
9
5
v6
All edges from v4 considered David Weir (U of Sussex)
Program Analysis Term 1, 2015 325 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
v8 v4 v7 v3
11 2 17
7
16 9
5
v6
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 9 0 21
β v2 v5 v2 v7 v7 v4 ⊥ v5
Remove v6 from Q and add edge {v6,v4} to E′
David Weir (U of Sussex) Program Analysis Term 1, 2015 326 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 9 0 21
β v2 v5 v2 v7 v7 v4 ⊥ v5
11 2 17
7
16
9
5
v6
Consider edge {v6,v3} David Weir (U of Sussex)
Program Analysis Term 1, 2015 327 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 9 0 21
β v2 v5 v2 v7 v7 v4 ⊥ v5
11 2 17
7
16
9
5
v6
δ(v3) < w(v6,v3) so don’t update δ(v3) and β(v3)
David Weir (U of Sussex) Program Analysis Term 1, 2015 328 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 9 0 21
β v2 v5 v2 v7 v7 v4 ⊥ v5
11 2 17
7
16
9
5
v6
Consider edge {v6,v8} David Weir (U of Sussex)
Program Analysis Term 1, 2015 329 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 9 0 21
β v2 v5 v2 v7 v7 v4 ⊥ v5
11 2 17
7
5
16
9
v6
δ(v8) > w(v6,v8) so update δ(v8) and β(v8)
David Weir (U of Sussex) Program Analysis Term 1, 2015 330 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 9 0 5
β v2 v5 v2 v7 v7 v4 ⊥ v6
11 2 17
7
16
9
v6
All edges from v6 considered David Weir (U of Sussex)
5
Program Analysis Term 1, 2015 331 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 9 0 5
β v2 v5 v2 v7 v7 v4 ⊥ v6
11 2 17
7
16
9
5
v6
Remove v8 from Q and add edge {v8,v6} to E′
David Weir (U of Sussex) Program Analysis Term 1, 2015 332 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 9 0 5
β v2 v5 v2 v7 v7 v4 ⊥ v6
11 2 17
7
9 5
16
v6
No edges from v8 need to be considered
David Weir (U of Sussex) Program Analysis Term 1, 2015 333 / 192
Illustrating Jarn ́ık’s Algorithm
v 6 v 15 v 521
3
21
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 9 0 5
β v2 v5 v2 v7 v7 v4 ⊥ v6
11 2 17
7
9 5
16
v6
Remove v1 from Q and add edge {v1,v2} to E′
David Weir (U of Sussex) Program Analysis Term 1, 2015 334 / 192
Illustrating Jarn ́ık’s Algorithm
6 15
v5 v2 v1
3
21
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 9 0 5
β v2 v5 v2 v7 v7 v4 ⊥ v6
11 2 17
7
16
v6
Consider edge {v1,v3} David Weir (U of Sussex)
9 5
Program Analysis Term 1, 2015 335 / 192
Illustrating Jarn ́ık’s Algorithm
6 15
v5 v2 v1
3
21
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 9 0 5
β v2 v5 v2 v7 v7 v4 ⊥ v6
11 2 17
7
9 5
16
v6
δ(v3) > w(v1,v3) so update δ(v3) and β(v3)
David Weir (U of Sussex) Program Analysis Term 1, 2015 336 / 192
Illustrating Jarn ́ık’s Algorithm
6 15
v5 v2 v1
3
21
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 2 7 3 9 0 5
β v2 v5 v1 v7 v7 v4 ⊥ v6
11 2 17
7
16
v6
All edges from v1 considered David Weir (U of Sussex)
9 5
Program Analysis Term 1, 2015 337 / 192
Illustrating Jarn ́ık’s Algorithm
6 15
v5 v2 v1
3
21
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 2 7 3 9 0 5
β v2 v5 v1 v7 v7 v4 ⊥ v6
11 2 17
7
9 5
16
v6
Remove v3 from Q and add edge {v3,v1} to E′
David Weir (U of Sussex) Program Analysis Term 1, 2015 338 / 192
Illustrating Jarn ́ık’s Algorithm
6 15
v5 v2 v1
3
11 2
17
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 2 7 3 9 0 5
β v2 v5 v1 v7 v7 v4 ⊥ v6
21
7
16
v6
9 5
No edges from v3 need to be considered
David Weir (U of Sussex) Program Analysis Term 1, 2015 339 / 192
Illustrating Jarn ́ık’s Algorithm
6 15
v5 v2 v1
3
11 2
17
v8 v4 v7 v3
26
v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 2 7 3 9 0 5
β v2 v5 v1 v7 v7 v4 ⊥ v6
21
7
16
v6
9 5
All done!
David Weir (U of Sussex)
Program Analysis Term 1, 2015 340 / 192
An example for you
v9v5v 521
7
vv2vv 8473
10 14 1 4
16
13
v6
Start with v7
David Weir (U of Sussex)
3
12
Program Analysis
Term 1, 2015
341 / 192
An example for you
v9v5v 521
7
vv2vv 8473
16
3
12
10 14 1 4
13
v6
Start with v7
MST contains following edges (in order added):
{v4, v7}, {v4, v6}, {v5, v4}, {v5, v8},‘ {v5, v2}, {v2, v3}, {v1, v3}
David Weir (U of Sussex) Program Analysis Term 1, 2015 341 / 192
Correctness of Jarn ́ık’s Algorithm
Follows from the Cut Property
Let V1 be the vertices no longer in Q
Let V2 be the vertices still in Q
Let u the vertex at the front of Q and β(u) = v
{u,v} is least weighted edge with one end in V1 and other in V2 {u,v} can safely be selected for inclusion in E′
David Weir (U of Sussex) Program Analysis Term 1, 2015 342 / 192
Running time of Jarn ́ık’s Algorithm
Analysis is identical to that for Dijkstra’s Algorithm O(m) updates to the value of δ and β
Assume Q implemented as a heap
Each update of δ takes log n time
Total running time is O(m log n)
David Weir (U of Sussex) Program Analysis Term 1, 2015 343 / 192
Greedy Algorithms: Huffman Codes
David Weir (U of Sussex) Program Analysis Term 1, 2015 344 / 192
Efficient Transmission of Messages
Message sent using an alphabet of characters
How efficiently can messages involving these characters be encoded in binary?
Efficiency determined by how many bits are needed to encode messages on average
Huffman Codes are used to find optimally efficient ways to solve this problem
David Weir (U of Sussex) Program Analysis Term 1, 2015 345 / 192
A Straightforward Encoding
Suppose we are using an alphabet Σ containing 64 characters:
26 lower case letters and 26 upper case letters
space, tab, newline
full-stop, comma, exclamation mark, question mark and dash round brackets and square brackets
David Weir (U of Sussex) Program Analysis Term 1, 2015 346 / 192
A Straightforward Encoding (cont.)
Each character x in Σ can be encoded using a distinct 6 bits
We refer the encoding of x x
a b c d .
as γ(x) γ(x)
000000
000001
000010
000011
.
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
347 / 192
Message length
Sending n characters requires 6n bits Exactly 6 bits per character
But this does not exploit differences in character frequencies
‘e’, ‘t’, ‘a’, ‘i’, ‘n’, ‘o’, ‘s’ are far more common than ‘z’, ‘j’ and ‘x’
Encoding should depend on how frequent a character is
David Weir (U of Sussex) Program Analysis Term 1, 2015 348 / 192
Character Probabilities
Associate a probability p(x) with each character x
p(x) is the probability that a randomly selected character will be x
Probabilities for all characters in alphabet total 1 p(x) = 1
x∈Σ
David Weir (U of Sussex) Program Analysis Term 1, 2015 349 / 192
Variable Length Encoding
Underlying principle:
Let more common characters have shorter encodings than less common characters
This will result in shorter messages on average Morse code takes this approach
David Weir (U of Sussex) Program Analysis Term 1, 2015 350 / 192
Morse Code
David Weir (U of Sussex) Program Analysis Term 1, 2015 351 / 192
Average Character Length
Question: When is one encoding preferable to another?
Answer: It depends on the probability distribution of the characters We want to minimise the average bits per letter
ABL = p(x) · |γ(x)| x∈Σ
The weighted average of character encoding length Weight is the probability of the character
David Weir (U of Sussex) Program Analysis Term 1, 2015 352 / 192
Common Prefix Problem
Morse Code is potentially ambiguious
Entire encoding of some characters could be the start of others Consider the transmission: – – · ·
This could be: TTEE, or TTI, or TD, etc
Morse code uses a space (pause) to separate characters
David Weir (U of Sussex) Program Analysis Term 1, 2015 353 / 192
Prefix Codes
Constraint of possible encodings:
No encoding should be a prefix of any another
Decoding can then be done without need to mark end of character
‘Eager’ decoding is safe: Consider bits from left to right
As soon as a sequence of bits γ(x) is found for some x ∈ Σ, decode that bit string as x
Consider remaining bit string starting with the next bit
David Weir (U of Sussex) Program Analysis Term 1, 2015 354 / 192
Example
Compare the following two encoding:
Prefix Code
x γ(x)
a00 b01 c 100 d 101 e 110 f 111
Consider decoding:
Non-Prefix Code
x γ(x)
a0 b1 c00 d01 e10 f 11
0010000110
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
355 / 192
Prefix Code Trees
Every prefix code can be expressed as a tree
x γ(x)
01 a00 b 01
0101 ab
c 100 d 101 e110
0 1 0 1 f111 cdef
Characters appear only at the leaves
David Weir (U of Sussex) Program Analysis Term 1, 2015 356 / 192
Efficient Prefix Code
Note that the depth of x in a prefix code tree equals |γ(x)| Property of good prefix code trees:
|γ(x)| < |γ(y)| implies p(x) ≥ p(y) Otherwise, it would be better to swap codes for x and y
David Weir (U of Sussex) Program Analysis Term 1, 2015 357 / 192
Bottom-up Prefix Code Construction
abejstv 0.12 0.10 0.28 0.06 0.23 0.18 0.03
Order alphabet in increasing order of probability
David Weir (U of Sussex) Program Analysis Term 1, 2015 358 / 192
Bottom-up Prefix Code Construction
vjbatse 0.03 0.06 0.10 0.12 0.18 0.23 0.28
Combine first two characters
David Weir (U of Sussex) Program Analysis Term 1, 2015 359 / 192
Bottom-up Prefix Code Construction
x1 batse 0.09 0.10 0.12 0.18 0.23 0.28
vj 0.03 0.06
Now left with identical type of problem to solve
David Weir (U of Sussex) Program Analysis Term 1, 2015 360 / 192
Bottom-up Prefix Code Construction
x2 atse
0.19
0.12 0.18
0.23
0.28
x1 0.09
b 0.10
vj 0.03 0.06
This time we need to re-order the characters
David Weir (U of Sussex) Program Analysis
Term 1, 2015
361 / 192
Bottom-up Prefix Code Construction
at x2 se
0.12 0.18
0.19
0.23
0.28
Now we combine the first two
x1 0.09
b 0.10
vj 0.03 0.06
David Weir (U of Sussex) Program Analysis
Term 1, 2015
362 / 192
Bottom-up Prefix Code Construction
x3 x2 se
0.30 0.19
a t x1 b 0.12 0.18 0.09 0.10
vj 0.03 0.06
0.23
0.28
Again we must re-order
David Weir (U of Sussex) Program Analysis
Term 1, 2015
363 / 192
Bottom-up Prefix Code Construction
x2 sex3 0.19 0.23 0.28 0.30
x1 b at
0.09 0.10
vj 0.03 0.06
0.12 0.18
And so on ...
David Weir (U of Sussex)
Program Analysis Term 1, 2015 364 / 192
Bottom-up Prefix Code Construction
x4 ex3
0.42 0.28
x2 s a
0.30
0.19
0.23
0.12
t 0.18
x1
0.09 0.10
vj 0.03 0.06
b
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
365 / 192
Bottom-up Prefix Code Construction
ex3 x4 0.28 0.30 0.42
at x2 s
0.12 0.18
0.19
0.23
x1 0.09
b 0.10
vj 0.03 0.06
David Weir (U of Sussex)
Program Analysis
Term 1, 2015
366 / 192
Bottom-up Prefix Code Construction
x5 x4 0.58 0.42
e x3 x2 s
0.28 0.30 0.19
a t x1 b 0.12 0.18 0.09 0.10
vj 0.03 0.06
0.23
David Weir (U of Sussex) Program Analysis
Term 1, 2015
367 / 192
Bottom-up Prefix Code Construction
x6 1
x5 0.58
e x3 x2 s
x4 0.42
0.28 0.30 0.19
a t x1 b 0.12 0.18 0.09 0.10
vj 0.03 0.06
0.23
David Weir (U of Sussex) Program Analysis
Term 1, 2015
368 / 192
Bottom-up Prefix Code Construction
x γ(x)
e 00 s 11 t 011 a 010
e b101 j 1001 v 1000
atb
s
vj
David Weir (U of Sussex) Program Analysis Term 1, 2015
369 / 192
Quality of the Prefix Code
Questions: What is the Average Bits per Letter (ABL) of this code?
Answer:
ABL = p(x) · |γ(x)| x∈Σ
0.28 · 2 + 0.12 · 3 + 0.18 · 3 + 0.03 · 4 + 0.06 · 4 + 0.10 · 3 + 0.23 · 2 = 2.58
With fixed length encoding 7 characters needs 3 bits per letter
David Weir (U of Sussex) Program Analysis Term 1, 2015 370 / 192
Huffman Code Algorithm
Huffman(Σ, P):
let Q be a priority queue of x ∈ Σ prioritized by lowest P(x) while |Q| > 1
remove the first two items x and y from Q let z be a new character not in Σ
letz betheparentofx andy
let P(z) = P(x) + P(y)
add z to Q
David Weir (U of Sussex) Program Analysis Term 1, 2015 371 / 192
Correctness of Algorithm
Algorithm terminates because Q reduces in size by 1 at each iteration
We need to achieve the following:
|γ(x)| < |γ(y)| implies p(x) ≥ p(y)
Order in which algorithm considers characters guarantees this Characters considered later cannot end up deeper in tree
David Weir (U of Sussex) Program Analysis Term 1, 2015 372 / 192
Efficiency of Huffman Code Algorithm
Let |Σ| = k
Creating Q takes O(k log k) time While loop executed k − 1 times O(log k) to remove each item from Q Assumes Q implemented as a heap Total running time O(k log k)
David Weir (U of Sussex) Program Analysis Term 1, 2015 373 / 192
Problem for you
Example scenario
x p(x)
e 0.40 i 0.20 c 0.18 f 0.15 k 0.05 z 0.02
How many bits would be needed without compression?
David Weir (U of Sussex) Program Analysis Term 1, 2015 374 / 192
Problem for you
Example scenario
x p(x)
e 0.40 i 0.20 c 0.18 f 0.15 k 0.05 z 0.02
How many bits would be needed without compression? Without compression, 6 characters uses 3 bits since
22 <6≤23
David Weir (U of Sussex) Program Analysis Term 1, 2015 374 / 192
Problem for you
Example scenario
x p(x)
e 0.40 i 0.20 c 0.18 f 0.15 k 0.05 z 0.02
Apply the algorithm to this case
David Weir (U of Sussex) Program Analysis Term 1, 2015 375 / 192
Problem for you
Example scenario
x p(x)
e 0.40 i 0.20 c 0.18 f 0.15 k 0.05 z 0.02
Apply the algorithm to this case
γ(e) = 1, γ(i) = 001, γ(c) = 000, γ(f) = 011, γ(k) = 0101,
γ(z) = 0100
David Weir (U of Sussex) Program Analysis Term 1, 2015 375 / 192
Problem for you
Example scenario
x p(x)
e 0.40 i 0.20 c 0.18 f 0.15 k 0.05 z 0.02
Find the ABL of the resulting code
David Weir (U of Sussex) Program Analysis Term 1, 2015 376 / 192
Problem for you
Example scenario
x p(x)
e 0.40 i 0.20 c 0.18 f 0.15 k 0.05 z 0.02
Find the ABL of the resulting code
0.4 × 1 + 0.2 × 3 + 0.18 × 3 + 0.15 × 3 + 0.05 × 4 + 0.02 × 4 = 2.27
David Weir (U of Sussex) Program Analysis Term 1, 2015 376 / 192