Program Analysis
Problem Sheet 7
You may find it useful to refer to the following algorithms:
Dijkstra(G,w,s):
let A be the empty set
let δ(s) = 0
letδ(v)=∞forv∈V −{s}
let Q be a priority queue containing elements of V while Q is not empty
remove v from front of priority queue Q add v to A
for each { v, u } ∈ E where u ̸∈ A
if δ(u) > δ(v) + w(v, u) then let δ(u) = δ(v) + w(v, u)
return δ 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′
Jarn ́ık(G, w) :
select some vertex s ∈ V and let δ(s) = 0 initialise E′ to be the empty set forallv∈V −{s}letδ(v)=∞ forallv∈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
add{u,v}toE′ whereβ(u)=v (omitthisstepforu=s) for each {u,x} ∈ E where x remains in Q
if δ(x) > w(u, x) then let δ(x) = w(u, x) let β(x) = u
Term 1, 2015
return E′
Program Analysis Term 1, 2015 1. Give loop invariants for each of the following algorithms:
(a) Dijkstra’s Algorithm.
In this case, you need to define δ(v) for all v that remain in the priority queue.
Model Answer: Suppose the algorithm is run on the graph G = (V,E) with edge weight function w and source vertex s ∈ V . Let A denote the vertices in V that are no longer in the priority queue.
At each iteration of the algorithm, for each vertex v ∈ V − A, δ(v) is equal to the weight of the shortest of the paths from s to v where all intermediate vertices are in A.
(b) Kruskal’s Algorithm.
In this case you need to define C(v) for all vertices v.
Model Answer: Suppose the algorithm is run on the graph G = (V,E) with edge weight function wm and at each iteration of the algorithm, E′ is the set of edges that have been selected so far for inclusion in the minimum spanning tree of G.
At each iteration, for each vertex v ∈ V , C(v) is the largest set V ′ ⊆ V such that there is a path from v to all vertices in V ′ involving only edges in E′. Note that there is an empty path from v it itself, hence it is always the case that v ∈ C(v).
(c) Jarn ́ık’s Algorithm.
In this case you need to define δ(v) for all v that remain in the priority queue.
Model Answer: Suppose the algorithm is run on the graph G = (V,E) with edge weight function w and source vertex s ∈ V . Let A denote the vertices in V that are no longer in the priority queue.
At each iteration of the algorithm, for each vertex v ∈ V − A, δ(v) is equal to the weight of the lightest of the edges { v, x } where x ∈ A.
Program Analysis Term 1, 2015
2. Both the Jarn ́ık and the Kruskal algorithms solve the minimum spanning tree problem. As required, adapt the Kruskal and the Jarn ́ık algorithms given below so that they find a forest of minimum spanning trees for graphs that can have more than one connected component. In each case, explain why the algorithm you have given works correctly on graphs with multiple components.
Program Analysis Term 1, 2015
Model Answer: Kruskal’s algorithm grows spanning trees by considering edges in order of increasing weight which is not disrupted by multiple connected com- ponents. We must change the while loop guard. In addition to checking that |E′| < |V | − 1, the guard needs to check that Q is not empty. When there is more than one connected component in the graph, the total number of edges in E′ will not reach |V | − 1.
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 and Q not empty
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′
The Jarn ́ık algorithm grows a minimum spanning tree from a arbitrarily chosen starting point. Given a graph with more than one component, the algorithm, will first construct a spanning tree for the component it happened to begin in. Once this spanning tree is completed, an element u where β(u) = ⊥ will be removed from the priority queue. This will be an arbitrary choice since all elements in the priority queue will have equal, infinite priority and u will be a vertex in a new connected component. The algorithm will continue as required. The guard for the while loop also needs to be corrected.
Jarn ́ık(G, w) :
select some vertex s ∈ V and let δ(s) = 0 initialise E′ to be the set { s } forallv∈V −{s}letδ(v)=∞ forallv∈V letβ(v)=⊥
let Q be a priority queue containing elements of V while |E′| < |V | − 1 and Q not empty
remove u from front of priority queue Q if β(u) ̸= ⊥ then
add{u,v}toE′ 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′
Program Analysis
3. Consider the Huffman Code Algorithm discussed in lectures. 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
Term 1, 2015
Apply this algorithm to the following input and calculate the average bits per letter.
x p(x) e 0.12702 t 0.09056 a 0.08167 o 0.07507
i 0.06966 n 0.06749 s 0.06327 h 0.06094 r 0.05987 d 0.04253 l 0.04025 c 0.02782 u 0.02758
x p(x) m 0.02406 w 0.02360
f 0.02228 g 0.02015 y 0.01974 p 0.01929 b 0.01492 v 0.00978 k 0.00772 j 0.00153 x 0.00150 q 0.00095 z 0.00074
Program Analysis Model Answer:
Term 1, 2015
p 0.01929
y 0.01974
g 0.02015
o 0.07507
a 0.08167
l 0.04025
d 0.04253
t 0.09056
v 0.00978
bp 0.03421 bpyg
yg 0.03989
ald 0. ld 0.08278
x 0.00150
xj 0.00303
j 0.00153 z 0.00074 q 0.00095 k 0.00772 f 0.02228 w 0.02360 m 0.02406 u 0.02758 c 0.02782 r 0.05987 h 0.06094 s 0.06327
xjzq zq 0.00169
wm 0.04766
uc 0.05540 ucr 0.
hs 0.12421
Program Analysis
x
e t a o i n s h r d l c u
x
e t a o i n s h r d l c u m w f g y p b v k j x q z
Term 1, 2015
γ (x) 111 011 1001 1010 1100 1101 0000 0001 0010 10000 10001 00110 00111
p(x) 0.12702 0.09056 0.08167 0.07507 0.06966 0.06749 0.06327 0.06094 0.05987 0.04253 0.04025 0.02782 0.02758 0.02406 0.02360 0.02228 0.02015 0.01974 0.01929 0.01492 0.00978 0.00772 0.00153 0.00150 0.00095 0.00074
x γ(x) m 01000 w 01001
f 01010 g 101100 y 101101 p 101110 b 101111 v 010111 k 0101100 j 010110110 x 010110111 q 010110100 z 010110101
|γ (x)| 3
3
4
4
4
4
4
4
4
5
5
5
5
5
5
5
6
6
6
6
6
7
9
9
9
9
p(x)|γ (x)| 0.38106 0.27168 0.32668 0.30028 0.27864 0.26996 0.25308 0.24376 0.23948 0.21265 0.20125 0.13910 0.13790 0.12030 0.11800 0.11140 0.12090 0.11844 0.11574 0.08952 0.05868 0.05404 0.01377 0.01350 0.00855 0.00666
The average bits per letter is ∑ p(x)|γ(x)| = 4.20502 x∈Σ