1. [10 points] Design a data structure that has the following properties (assume n elements in the data structure, and that the data structure properties need to be preserved at the end of each operation):
• Find median takes O(1) time
• Insert takes O(logn) time
Do the following:
(a) Describe how your data structure will work.
(b) Give algorithms that implement the Find-Median() and Insert() functions.
3. [14 points] A new startup FastRoute wants to route information along a path in a communication network, represented as a graph. Each vertex and each edge represent a router and a wire between routers respectively. The wires are weighted by the maximum bandwidth they can support. FastRoute comes to you and asks you to develop an algorithm to find the path with maximum bandwidth from any source s to any destination t. As you would expect, the bandwidth of a path is the minimum of the bandwidths of the edges on that path; the minimum edge is the bottleneck. Explain how to modify Dijkstra’s algorithm to do this.
4. [20 points] Given a connected graph G = (V,E) with positive edge weights. In V , s and t are two nodes for shortest path computation, prove or disprove with explanations:
(a) If all edge weights are unique, then there is a single shortest path between any two nodes in V .
(b) If each edge’s weight is increased by k, the shortest path cost between s and t will increase by a multiple of k.
(c) If the weight of some edge e decreases by k, then the shortest path cost between s and t will decrease by at most k.
(d) If each edge’s weight is replaced by its square, i.e., w to w2 , then the shortest path between s and t will be the same as before but with different costs.
Ungraded Problems
