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.
(b) Kruskal’s Algorithm.
In this case you need to define C(v) for all vertices v.
(c) Jarn ́ık’s Algorithm.
In this case you need to define δ(v) for all v that remain in the priority queue.
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
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