For each of the algorithms that you write as part of your HW solutions, remember that you are required to:
- show the algorithm's correctness (i.e., it terminates producing the correct result), and
- analyze its time complexity in detail.
Will a greedy algorithm for this problem output an optimal solution? If so,
Show an example in which the greedy approach to solve this problem produces a suboptimal solution.
Here is Dijkstra's algorithm as discussed in class (though a little more detail has been added to the pseudo-code below to help you with this homework).
Input:
- A graph G = (V,E) with |V|=n, |E|=m.
- An array length with m positions, such length[(u,v)] = cost/length of the edge (u,v)
- A node s in G.
Output:
- An array d of size n such that d[v] = the distance of the shortest path between s and v in G
- An array Predecessor of size n such that Predecessor[v] = the node in G which preceds v
in the shortest path from s and v in G
Algorithm:
Disjkstra (G, length, s) {
Create an empty priority queue PQ
d[s] := 0
Predecessor[s] := nil
add s with key value 0 to PQ
For each node v in V different from s {
d[v] := infinity
Predecessor[v] := nil
add v with key value infinity to PQ
}
Explored := empty set
While PQ != empty {
v := ExtractMin(PQ)
Explored := Explored union {v}
For each each (v,w) adjacent to v in E {
if d[w] > d[v] + length[(v,w)] then {
d[w]:= d[v] + length[(v,w)]
change w's key value in PQ to the new value d[w]
Predecessor[w] := v
}
}
}
Return arrays d and Predecessor
}
Consider the following undirected graph. Follow by hand the
implementation of Dijkstra's algorithm discussed in class (given above)
to produce the shortest paths from the source node S to all other nodes
In the graph.
Implement the Huffman codes algorithm in your favorite programming language (java, C, C++, ...). Consider the following pseudo-code of the algorithm:
Input:
- n: the number of symbols to consider
- An array S of n positions where S[i] is the ith symbol in S, 1 ≤ i ≤ n.
- An array P of n positions where P[i] is the frequency/probability of the symbol S[i].
Output:
- An array Code of n positions where Code[i] contains the encoding of the symbol S[i].
- The average number of bits per letter/symbol used by the encoding.
Algorithm:
Huffman(S, P, n) {
create an empty priority queue Q
// Insert each symbol in S into Q as follows: //
For i := 1 to n {
create a new tree node v
v.symbol := S[i]
v.freq := P[i]
v.left := nil
v.right := nil
insert v with key value v.freq into Q
}
// Construct a binary tree with the symbols in S as follows: //
For i := 1 to n-1 {
create a new tree node z
x := ExtractMin(Q). That is, extract the tree x with the minimum frequency from Q
z.right := x
y := ExtractMin(Q). That is, extract the tree y with the minimum frequency from Q
z.left := y
z.freq := x.freq + y.freq
insert z with key value z.freq into Q
}
extract the minimum (and only) tree T remaining in Q
generate the codes for each symbol in S by following the
tree T structure in a depth-1st manner assigning "0" to the
left child of the node and "1" to the right child of the node
until all the leaves are assigned a code
(as shown in Figure 4.16 of the textbook)
Once that a code is assigned to a symbol in S, say to the symbol S[i], store such
code in the corresponding array position Code[i].
Compute "ABL", that is the average number of bits per letter/symbol.
Output the code generated for each symbol in S and also output the value "ABL"
}
WHAT TO SUBMIT FOR THIS PROBLEM:
n = 5
Symbols: a b c d e
Frequencies: .32 .25 .20 .18 .05
n = 6
Symbols: a b c d e f
Frequencies: .045 .013 .012 .016 .009 .005
n = 12
Symbols: a b c d e f g h i j k l
Frequencies: .002 .008 .022 .003 .004 .015 .001 .011 .009 .005 .007 .013
As an example of a text file you can use the short story Gift of the Magi by O. HENRY included here. Run your new function to read this file and count the frequencies of the 26 letters in the alphabet. Then use these data as input to your Huffman codes program. Include printouts of your new function, the output it generates, and also the output that your Huffman codes program generates on this input.