Description
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.
2. [20 points] A network of n servers under your supervision is modeled as an undirected
graph G = (V, E) where a vertex in the graph corresponds to a server in the network and
an edge models a link between the two servers corresponding to its incident vertices.
Assume G is connected. Each edge is labeled with a positive integer that represents the
cost of maintaining the link it models. Further, there is one server (call its corresponding
vertex as S) that is not reliable and likely to fail. Due to a budget cut, you decide to
remove a subset of the links while still ensuring connectivity.
That is, you decide to
remove a subset of E so that the remaining graph is a spanning tree. Further, to ensure
that the failure of S does not affect the rest of the network, you also require that S is
connected to exactly one other vertex in the remaining graph.
Design an algorithm that
given G and the edge costs efficiently decides if it is possible to remove a subset of E,
such that the remaining graph is a spanning tree where S is connected to exactly one other
vertex and (if possible) finds a solution that minimizes the sum of maintenance costs of
the remaining edges.
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 can process only one number from the stream at a time, which means it takes a
number from the stream, processes it, finishes with that number and takes the next
number from the stream. It cannot take more than one number from the stream at a time
due to memory restriction.
• 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.
6. [15 points] Consider a directed, weighted graph G where all edge weights are positive.
You have one Star, which allows you to change the weight of any one edge to zero. In
other words, you may change the weight of any one edge to zero. Propose an efficient
method based on Dijkstra’s algorithm to find a lowest-cost path from node s to node t,
given that you may set one edge weight to zero.
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.