CSCI570 Homework4 Solution

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):
a. • Find median takes O(1) time
b. • Insert takes O(log n) time Do the following:
1. Describe how your data structure will work.
2. Give algorithms that implement the Find-Median() and Insert() functions.
3. [15 points] Prove or disprove the following:
• T is a spanning tree on an undirected graph G = (V, E). Edge costs in G are NOT guaranteed to be unique. If every edge in T belongs to SOME minimum cost spanning trees in G, then T is itself a minimum cost spanning tree.
• Consider two positively weighted graphs G = (V, E, w) and G′ = (V, E, w′) with the same vertices V and edges E such that, for any edge e in E, we have w′(e) = w(e)2 For any two vertices u, v in V, any shortest path between u and v in G′is also a shortest path in G.
4. [15 points] A new startup FastRoute wants to route information along a path in a communication network, represented as a graph. Each vertex represents a router and each edge a wire between routers. 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.
5. [10 points] There is a stream of integers that comes continuously to a small server. The job of the server is to keep track of k largest numbers that it has seen so far. The server has the following restrictions:
• It has enough memory to store up to k integers in a simple data structure (e.g. an array), and some extra memory for computation (like comparison, etc.).
• The time complexity for processing one number must be better than O(k). Anything that is O(k) or worse is not acceptable. Design an algorithm on the server to perform its job with the requirements listed above.
Note: you will receive 10 points if your algorithm is efficient. This means your method must do better than the naive solution, where the weight of each node is set to 0 per time and the Dijkstra’s algorithm is applied every time for lowest-cost path searching. You will receive full points (15 points) if your algorithm has the same run time complexity as Dijkstra’s algorithm.
7. [10 points] When constructing a binomial heap of size n using n insert operations, what is the amortized cost of the insert operation? Find using the accounting method.