Homework #7 solutions

CIS3151 Spring 1998

[24.2-3] Prim, Fibonacci: O(n log n + m), Binary Heap: O((n+m) log n). Does not matter when m=O(n). The former is faster when m=O(n^2).This is always the case when n =o(m). [3pts.]
[24.2-4] Distributing edge weights into the array of n entries takes O(m+n), the same for accessing them in a non-decreasing order. Hence the complexity of Kruskal's algorithm is bounded by O(n+m log*n). When the range of edge weights is constant, the priority queue can be maintained by keeping entries in the constant length array, with constant time operations. Hence, both weight restrictions allow O(n+m log*n) implementation of Kruskal's algorithm. [3pts.]
[24.2-5] O(n) range of edge weights does not allow fast DeleteMin in a priority queue implementation. For constantly bounded edge weights, an array implementation of priority queue will allow constant time operations, for an O(m+n) implementation of Prim's algorithm.[3pts.]
[25.2-5] The largest key value d(u) is O(WV). One can implement priority queue in an array of WV entries, with the index of the minimum non-zero entry never decreasing in the priority queue's life time. Hence the postulated upper bound on the complexity of Dijkstra's algorithm. [4pts.]
[25.4-3] Instead of RELAX in line 5, one would use "if d[u]+weight(v)>d[v] then d[v]:=d[u]+weight(v)" (having initialized all keys to -infty and the sources key, d[s], to weight(s)). [3pts.]