Program Analysis
Greedy Algorithms 2
David Weir (U of Sussex) Program Analysis Term 1, 2017 250 / 606
The Minimum Spanning Tree Problem
David Weir (U of Sussex) Program Analysis Term 1, 2017 251 / 606
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, 2017 252 / 606
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, 2017 253 / 606
MST Example
v1v2
v3v4
v5
v6
v7v8
5
8
19
4
2
2521
6 16
3
11
What is a minimum spanning tree for this weighted graph ?
David Weir (U of Sussex) Program Analysis Term 1, 2017 254 / 606
MST Example
v1v2
v3v4
v5
v6
v7v8
5
8
19
4
2
2521
6 16
3
11
Consider the path from v3 to v6 — length is more than 16
David Weir (U of Sussex) Program Analysis Term 1, 2017 255 / 606
MST Example for You
v1
v2
v3
v4
v5
2 12
106
7
9
3
Indicate nodes that are in a minimum spanning tree for this weighted
graph?
David Weir (U of Sussex) Program Analysis Term 1, 2017 256 / 606
MST Example for You
v1
v2
v3
v4
v5
2 12
106
7
9
3
Indicate nodes that are in a minimum spanning tree for this weighted
graph?
David Weir (U of Sussex) Program Analysis Term 1, 2017 256 / 606
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, 2017 257 / 606
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
v3
v4
v5
v6
5
18
6
16
3
11
this edge
must be in an MST
V1 V2
David Weir (U of Sussex) Program Analysis Term 1, 2017 258 / 606
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, 2017 259 / 606
Proof of Cut Property (cont.)
u′
u
v ′
v
6
16
V1 V2
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
David Weir (U of Sussex) Program Analysis Term 1, 2017 260 / 606
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) 6= 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, 2017 261 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Create Q and C(v) for each v ∈ V David Weir (U of Sussex) Program Analysis Term 1, 2017 262 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 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}) Remove edge {v4, v7} from Q David Weir (U of Sussex) Program Analysis Term 1, 2017 263 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v4, v6}, {v5, v2}, {v2, v1}, {v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) C(v4) 6= C(v7) so add to E ′ and combine clusters David Weir (U of Sussex) Program Analysis Term 1, 2017 264 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v4, v6}, {v5, v2}, {v2, v1}, {v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) Remove edge {v4, v6} from Q David Weir (U of Sussex) Program Analysis Term 1, 2017 265 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v5, v2}, {v2, v1}, {v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) C(v4) 6= C(v6) so add to E ′ and combine clusters David Weir (U of Sussex) Program Analysis Term 1, 2017 266 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v5, v2}, {v2, v1}, {v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) Remove edge {v5, v2} from Q David Weir (U of Sussex) Program Analysis Term 1, 2017 267 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v2, v1}, {v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) C(v2) 6= C(v5) so add to E ′ and combine clusters David Weir (U of Sussex) Program Analysis Term 1, 2017 268 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v2, v1}, {v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) Remove edge {v2, v1} from Q David Weir (U of Sussex) Program Analysis Term 1, 2017 269 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) C(v2) 6= C(v1) so add to E ′ and combine clusters David Weir (U of Sussex) Program Analysis Term 1, 2017 270 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v6, v7}, {v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) Remove edge {v6, v7} from Q David Weir (U of Sussex) Program Analysis Term 1, 2017 271 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) C(v6) = C(v7) so don’t add to E ′ David Weir (U of Sussex) Program Analysis Term 1, 2017 272 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v6, v8}, {v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) Remove edge {v6, v7} from Q David Weir (U of Sussex) Program Analysis Term 1, 2017 273 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) C(v6) 6= C(v8) so add to E ′ and combine clusters David Weir (U of Sussex) Program Analysis Term 1, 2017 274 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v4, v5}, {v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) Remove edge {v4, v5} from Q David Weir (U of Sussex) Program Analysis Term 1, 2017 275 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) C(v4) 6= C(v5) so add to E ′ and combine clusters David Weir (U of Sussex) Program Analysis Term 1, 2017 276 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v3, v1}, {v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) Remove edge {v3, v1} from Q David Weir (U of Sussex) Program Analysis Term 1, 2017 277 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) C(v1) 6= C(v3) so add to E ′ and combine clusters David Weir (U of Sussex) Program Analysis Term 1, 2017 278 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 19 4 2 2521 9 16 3 11 6 Q = ({v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) |E ′| = |V | − 1 so we have found our minimum spanning tree David Weir (U of Sussex) Program Analysis Term 1, 2017 279 / 606 Illustration of Kruskal’s Algorithm v1v2 v3v4 v5 v6 v7v8 5 12 4 2 9 3 11 Q = ({v3, v6}, {v3, v2}, {v5, v8}, {v5, v7}) All done! David Weir (U of Sussex) Program Analysis Term 1, 2017 280 / 606 An example for you v1v2 v3v4 v5 v6 v7v8 5 1 4 9 14 2 7 13 16 3 10 12 David Weir (U of Sussex) Program Analysis Term 1, 2017 281 / 606 An example for you v1v2 v3v4 v5 v6 v7v8 5 1 4 9 14 2 7 13 16 3 10 12 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, 2017 281 / 606 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, 2017 282 / 606 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) 6= 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, 2017 283 / 606 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, 2017 284 / 606 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, 2017 285 / 606 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, 2017 286 / 606 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, 2017 287 / 606 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, 2017 288 / 606 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 6∈ S David Weir (U of Sussex) Program Analysis Term 1, 2017 289 / 606 Example In this example we have E ′ = {{v5, v7}, {v5, v2}} and S = {v2, v5, v7} v1v2 v3v4 v5 v6 v7v8 15 2 17 6 7 321 5 26 9 11 16 David Weir (U of Sussex) Program Analysis Term 1, 2017 290 / 606 Example The closest vertex to (S,E ′) is v4 due to the edge {v4, v7} v1v2 v3v4 v5 v6 v7v8 15 2 17 6 7 321 5 26 9 11 16 David Weir (U of Sussex) Program Analysis Term 1, 2017 291 / 606 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 δ(v) = w(v ,u) refer to this value as β(v) Back to the example David Weir (U of Sussex) Program Analysis Term 1, 2017 292 / 606 Example Recall that we have E ′ = {{v5, v7}, {v5, v2}} and S = {v2, v5, v7} v1v2 v3v4 v5 v6 v7v8 15 2 17 6 7 321 5 26 9 11 16 David Weir (U of Sussex) Program Analysis Term 1, 2017 293 / 606 Example Consider the values δ(v6) and β(v6) given this particular (T ,S) v1v2 v3v4 v5 v6 v7v8 15 2 17 6 7 321 5 26 9 11 16 δ(v6) = 16 β(v6) = v7 David Weir (U of Sussex) Program Analysis Term 1, 2017 294 / 606 Example What happens to δ(v6) when we were to add v4 to E ′ v1v2 v3v4 v5 v6 v7v8 15 2 17 6 7 321 5 26 9 11 16 δ(v6) = 9 β(v6) = v4 David Weir (U of Sussex) Program Analysis Term 1, 2017 295 / 606 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, 2017 296 / 606 Jarnı́k’s Algorithm Jarnı́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) 6= ⊥ 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, 2017 297 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
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, 2017 298 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞
β ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥
Remove v7 from Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 299 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ ∞ ∞ ∞ ∞ ∞ ∞ 0 ∞
β ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥ ⊥
Consider the edge {v7, v4}
David Weir (U of Sussex) Program Analysis Term 1, 2017 300 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
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, 2017 301 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ ∞ ∞ ∞ 7 ∞ ∞ 0 ∞
β ⊥ ⊥ ⊥ v7 ⊥ ⊥ ⊥ ⊥
Consider the edge {v7, v5}
David Weir (U of Sussex) Program Analysis Term 1, 2017 302 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
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, 2017 303 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ ∞ ∞ ∞ 7 3 ∞ 0 ∞
β ⊥ ⊥ ⊥ v7 v7 ⊥ ⊥ ⊥
Consider the edge {v7, v6}
David Weir (U of Sussex) Program Analysis Term 1, 2017 304 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ ∞ ∞ ∞ 7 3 ∞ 0 ∞
β ⊥ ⊥ ⊥ v7 v7 ⊥ ⊥ ⊥
δ(v6) > w(v7, v6) so update δ(v6) and β(v6)
David Weir (U of Sussex) Program Analysis Term 1, 2017 305 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
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, 2017 306 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
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, 2017 307 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ ∞ ∞ ∞ 7 3 16 0 ∞
β ⊥ ⊥ ⊥ v7 v7 v7 ⊥ ⊥
Consider the edge {v5, v2}
David Weir (U of Sussex) Program Analysis Term 1, 2017 308 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
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, 2017 309 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ ∞ 6 ∞ 7 3 16 0 ∞
β ⊥ v5 ⊥ v7 v7 v7 ⊥ ⊥
Consider the edge {v5, v4}
David Weir (U of Sussex) Program Analysis Term 1, 2017 310 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
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, 2017 311 / 606 Illustrating Jarnı́k’s Algorithm v1v2 v3v4 v5 v6 v7v8 15 2 17 6 7 321 5 26 9 11 16 v1 v2 v3 v4 v5 v6 v7 v8 δ ∞ 6 ∞ 7 3 16 0 ∞ β ⊥ v5 ⊥ v7 v7 v7 ⊥ ⊥ Consider the edge {v5, v8} David Weir (U of Sussex) Program Analysis Term 1, 2017 312 / 606 Illustrating Jarnı́k’s Algorithm v1v2 v3v4 v5 v6 v7v8 15 2 17 6 7 321 5 26 9 11 16 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, 2017 313 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ ∞ 6 ∞ 7 3 16 0 21
β ⊥ v5 ⊥ v7 v7 v7 ⊥ v5
All edges from v5 considered
David Weir (U of Sussex) Program Analysis Term 1, 2017 314 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
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, 2017 315 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ ∞ 6 ∞ 7 3 16 0 21
β ⊥ v5 ⊥ v7 v7 v7 ⊥ v5
Consider edge {v2, v1}
David Weir (U of Sussex) Program Analysis Term 1, 2017 316 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
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, 2017 317 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 ∞ 7 3 16 0 21
β v2 v5 ⊥ v7 v7 v7 ⊥ v5
Consider edge {v2, v3}
David Weir (U of Sussex) Program Analysis Term 1, 2017 318 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
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, 2017 319 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 17 7 3 16 0 21
β v2 v5 v2 v7 v7 v7 ⊥ v5
All edges from v2 considered
David Weir (U of Sussex) Program Analysis Term 1, 2017 320 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
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, 2017 321 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 17 7 3 16 0 21
β v2 v5 v2 v7 v7 v7 ⊥ v5
Consider edge {v4, v6}
David Weir (U of Sussex) Program Analysis Term 1, 2017 322 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 17 7 3 16 0 21
β v2 v5 v2 v7 v7 v7 ⊥ v5
δ(v6) > w(v4, v6) so update δ(v6) and β(v6)
David Weir (U of Sussex) Program Analysis Term 1, 2017 323 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 17 7 3 9 0 21
β v2 v5 v2 v7 v7 v4 ⊥ v5
All edges from v4 considered
David Weir (U of Sussex) Program Analysis Term 1, 2017 324 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
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, 2017 325 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 17 7 3 9 0 21
β v2 v5 v2 v7 v7 v4 ⊥ v5
Consider edge {v6, v3}
David Weir (U of Sussex) Program Analysis Term 1, 2017 326 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 17 7 3 9 0 21
β v2 v5 v2 v7 v7 v4 ⊥ v5
δ(v3) < w(v6, v3) so don’t update δ(v3) and β(v3) David Weir (U of Sussex) Program Analysis Term 1, 2017 327 / 606 Illustrating Jarnı́k’s Algorithm v1v2 v3v4 v5 v6 v7v8 15 2 17 6 7 321 5 26 9 11 16 v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 9 0 21 β v2 v5 v2 v7 v7 v4 ⊥ v5 Consider edge {v6, v8} David Weir (U of Sussex) Program Analysis Term 1, 2017 328 / 606 Illustrating Jarnı́k’s Algorithm v1v2 v3v4 v5 v6 v7v8 15 2 17 6 7 321 5 26 9 11 16 v1 v2 v3 v4 v5 v6 v7 v8 δ 15 6 17 7 3 9 0 21 β v2 v5 v2 v7 v7 v4 ⊥ v5 δ(v8) > w(v6, v8) so update δ(v8) and β(v8)
David Weir (U of Sussex) Program Analysis Term 1, 2017 329 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 17 7 3 9 0 5
β v2 v5 v2 v7 v7 v4 ⊥ v6
All edges from v6 considered
David Weir (U of Sussex) Program Analysis Term 1, 2017 330 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 17 7 3 9 0 5
β v2 v5 v2 v7 v7 v4 ⊥ v6
Remove v8 from Q and add edge {v8, v6} to E
′
David Weir (U of Sussex) Program Analysis Term 1, 2017 331 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 17 7 3 9 0 5
β v2 v5 v2 v7 v7 v4 ⊥ v6
No edges from v8 need to be considered
David Weir (U of Sussex) Program Analysis Term 1, 2017 332 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 17 7 3 9 0 5
β v2 v5 v2 v7 v7 v4 ⊥ v6
Remove v1 from Q and add edge {v1, v2} to E
′
David Weir (U of Sussex) Program Analysis Term 1, 2017 333 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 17 7 3 9 0 5
β v2 v5 v2 v7 v7 v4 ⊥ v6
Consider edge {v1, v3}
David Weir (U of Sussex) Program Analysis Term 1, 2017 334 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 17 7 3 9 0 5
β v2 v5 v2 v7 v7 v4 ⊥ v6
δ(v3) > w(v1, v3) so update δ(v3) and β(v3)
David Weir (U of Sussex) Program Analysis Term 1, 2017 335 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 2 7 3 9 0 5
β v2 v5 v1 v7 v7 v4 ⊥ v6
All edges from v1 considered
David Weir (U of Sussex) Program Analysis Term 1, 2017 336 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 2 7 3 9 0 5
β v2 v5 v1 v7 v7 v4 ⊥ v6
Remove v3 from Q and add edge {v3, v1} to E
′
David Weir (U of Sussex) Program Analysis Term 1, 2017 337 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 2 7 3 9 0 5
β v2 v5 v1 v7 v7 v4 ⊥ v6
No edges from v3 need to be considered
David Weir (U of Sussex) Program Analysis Term 1, 2017 338 / 606
Illustrating Jarnı́k’s Algorithm
v1v2
v3v4
v5
v6
v7v8
15
2
17
6
7
321
5
26
9
11
16
v1 v2 v3 v4 v5 v6 v7 v8
δ 15 6 2 7 3 9 0 5
β v2 v5 v1 v7 v7 v4 ⊥ v6
All done!
David Weir (U of Sussex) Program Analysis Term 1, 2017 339 / 606
An example for you
v1v2
v3v4
v5
v6
v7v8
5
1
4
9
14
2
7
13
16
3
10
12
Start with v7
David Weir (U of Sussex) Program Analysis Term 1, 2017 340 / 606
An example for you
v1v2
v3v4
v5
v6
v7v8
5
1
4
9
14
2
7
13
16
3
10
12
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, 2017 340 / 606
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, 2017 341 / 606
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, 2017 342 / 606
Greedy Algorithms:
Huffman Codes
David Weir (U of Sussex) Program Analysis Term 1, 2017 343 / 606
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, 2017 344 / 606
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, 2017 345 / 606
A Straightforward Encoding (cont.)
Each character x in Σ can be encoded using a distinct 6 bits
We refer the encoding of x as γ(x)
x γ(x)
a 000000
b 000001
c 000010
d 000011
…
…
David Weir (U of Sussex) Program Analysis Term 1, 2017 346 / 606
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, 2017 347 / 606
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
∑
x∈Σ
p(x) = 1
David Weir (U of Sussex) Program Analysis Term 1, 2017 348 / 606
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, 2017 349 / 606
Morse Code
David Weir (U of Sussex) Program Analysis Term 1, 2017 350 / 606
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 =
∑
x∈Σ
p(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, 2017 351 / 606
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, 2017 352 / 606
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, 2017 353 / 606
Example
Compare the following two encoding:
Prefix Code Non-Prefix Code
x γ(x)
a 00
b 01
c 100
d 101
e 110
f 111
x γ(x)
a 0
b 1
c 00
d 01
e 10
f 11
Consider decoding:
0010000110
David Weir (U of Sussex) Program Analysis Term 1, 2017 354 / 606
Prefix Code Trees
Every prefix code can be expressed as a tree
0
a
0
b
1
1
0
c
0
d
1
1
e
0
f
1
x γ(x)
a 00
b 01
c 100
d 101
e 110
f 111
Characters appear only at the leaves
David Weir (U of Sussex) Program Analysis Term 1, 2017 355 / 606
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, 2017 356 / 606 Bottom-up Prefix Code Construction a 0.12 b 0.10 e 0.28 j 0.06 s 0.23 t 0.18 v 0.03 Order alphabet in increasing order of probability David Weir (U of Sussex) Program Analysis Term 1, 2017 357 / 606 Bottom-up Prefix Code Construction v 0.03 j 0.06 b 0.10 a 0.12 t 0.18 s 0.23 e 0.28 Combine first two characters David Weir (U of Sussex) Program Analysis Term 1, 2017 358 / 606 Bottom-up Prefix Code Construction x1 0.09 v 0.03 j 0.06 b 0.10 a 0.12 t 0.18 s 0.23 e 0.28 Now left with identical type of problem to solve David Weir (U of Sussex) Program Analysis Term 1, 2017 359 / 606 Bottom-up Prefix Code Construction x2 0.19 x1 0.09 v 0.03 j 0.06 b 0.10 a 0.12 t 0.18 s 0.23 e 0.28 This time we need to re-order the characters David Weir (U of Sussex) Program Analysis Term 1, 2017 360 / 606 Bottom-up Prefix Code Construction x2 0.19 x1 0.09 v 0.03 j 0.06 b 0.10 a 0.12 t 0.18 s 0.23 e 0.28 Now we combine the first two David Weir (U of Sussex) Program Analysis Term 1, 2017 361 / 606 Bottom-up Prefix Code Construction x3 0.30 x2 0.19 x1 0.09 v 0.03 j 0.06 b 0.10 a 0.12 t 0.18 s 0.23 e 0.28 Again we must re-order David Weir (U of Sussex) Program Analysis Term 1, 2017 362 / 606 Bottom-up Prefix Code Construction x3 0.30 x2 0.19 x1 0.09 v 0.03 j 0.06 b 0.10 a 0.12 t 0.18 s 0.23 e 0.28 And so on ... David Weir (U of Sussex) Program Analysis Term 1, 2017 363 / 606 Bottom-up Prefix Code Construction x3 0.30 x4 0.42 x2 0.19 x1 0.09 v 0.03 j 0.06 b 0.10 a 0.12 t 0.18 s 0.23 e 0.28 David Weir (U of Sussex) Program Analysis Term 1, 2017 364 / 606 Bottom-up Prefix Code Construction x3 0.30 x4 0.42 x2 0.19 x1 0.09 v 0.03 j 0.06 b 0.10 a 0.12 t 0.18 s 0.23 e 0.28 David Weir (U of Sussex) Program Analysis Term 1, 2017 365 / 606 Bottom-up Prefix Code Construction x5 0.58 x3 0.30 x4 0.42 x2 0.19 x1 0.09 v 0.03 j 0.06 b 0.10 a 0.12 t 0.18 s 0.23 e 0.28 David Weir (U of Sussex) Program Analysis Term 1, 2017 366 / 606 Bottom-up Prefix Code Construction x6 1 x5 0.58 x3 0.30 x4 0.42 x2 0.19 x1 0.09 v 0.03 j 0.06 b 0.10 a 0.12 t 0.18 s 0.23 e 0.28 David Weir (U of Sussex) Program Analysis Term 1, 2017 367 / 606 Bottom-up Prefix Code Construction v j ba t se x γ(x) e 00 s 11 t 011 a 010 b 101 j 1001 v 1000 David Weir (U of Sussex) Program Analysis Term 1, 2017 368 / 606 Quality of the Prefix Code Questions: What is the Average Bits per Letter (ABL) of this code? Answer: ABL = ∑ x∈Σ p(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, 2017 369 / 606 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 Σ
let z be the parent of x and y
let P(z) = P(x) + P(y)
add z to Q
David Weir (U of Sussex) Program Analysis Term 1, 2017 370 / 606
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, 2017 371 / 606 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, 2017 372 / 606 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, 2017 373 / 606 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, 2017 373 / 606 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, 2017 374 / 606 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, 2017 374 / 606 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, 2017 375 / 606 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, 2017 375 / 606