Part I
1)
Input: W
items[n] weightSum = 0
while i < n
if items[i].weight + weightSum < W
weightSum += items[i].weight else
mark i as dividing point
weightSum = items[i].weight i += 1
2)
while there is passable parts uncovered
place a new watchtower
3)
# intervals is a list of intervals with nondecreasing finish time def process(intervals):
resultSet = {} lastFinish = -1
for i = 0 to len(intervals)
if intervals[i].start > lastFinish
resultSet.add(intervals[i])
lastFinish = intervals[i].finish return resultSet
def main(intervals):
sort intervals using finish time as key, from smaller to larger candidateSolutions = {}
for every interval v that contains mid-night:
inters = remove from intervals that overlap with v resultSet = process(inters)
add resultSet U {v} to candidateSolutions
inters = remove from intervals that contain mid-night resultSet = process(inters)
add resultSet to candidateSolutions
return best solution in candidateSolutions
Running time: O(N^2). Sort the intervals is O(nlog(n)).
The for loop runs at most n iterations, inside the for loop, remove overlap intervals and process(intervals) is O(n). So the running time is O(nlog(n)) + O(n*n) = O(n^2).
Correctness:
For every interval that contains mid-night, select it, for the
remaining non-overlapping intervals, we can use normal interval
scheduling greedy algorithm. If the optional have interval contain mid-night, then it must be one of them.
If the optional chosen intervals don’t have interval contain
mid-night, then run normal interval scheduling greedy algorithm
on intervals that remove intervals which contains mid-night will
get the optional result.
4)
Input: graph G algorithm:
for every vertex u in G,
invoke Dijkstra’s algorithm to compute distance from u to every other vertex construct a complete graph newG with same vertices as G, and the weight of (u, v) in newG is the distance of shortest path from u to v in graph G.
compute the minium spanning tree T of newG using Prim’s algorithm
result = {}
for each edge (u,v) in T
using Dijkstra to find shortest path P from u to v in G if P have more than 1 vertex already in result
suppose vi and vj is the first and the last vertex already in T
add subpath from u to vi and vj to v to result else
add P to result
return result
running time: using Dijkstra compute all pair shortest path: V* O(E + VlogV) spanning-tree using prim: O(VlogV + V^2) = O(V^2)
The for loop: V*O(E + VlogV).
So the overall running time is: O(VE + V^2 logV).
not optimal Case:
(a) is the input graph (b) is the optimal solution (c) is the solution of the above greedy algorithm
Apart from middle vertex , the other 4 are destination vertices.
5)
adapt Kruskal algorithm for minimum-spanning-tree def find-maximum-bandwidth-spanning-tree(G):
tree = {}
sort the edges of G into nondecreasing order by link bandwidth for each vertex v in G
make-set(v) for each edge (u,v) i G
if find-set(u) != find-set(v) tree.add( (u,v) )
union(u, v)
return tree
The resulting algorithm’s running time doesn’t change, same with Kruskal which is O(Elog(V)), E is the number of edges and V is the number of vertices.
Part II
cases that don’t need recomputing
1) going down when the edge is already down
2) going up when the edge is already up
3) going down, but the edge is not in the shortest path tree rooted
at V0, so the shortest path from V0 to other vertex doesn’t change