Description
1. Design a data structure that has the following properties: Find median takes O(1) time, Insert takes
O(lgn) time. (assume n elements in the data structure, and that the data structure properties need to be
preserved at the end of each operation).
Describe how your data structure will work and Give algorithms that implement the Find-Median() and
Insert() functions.
2. 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.(a) 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.
3.(b) 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. 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. 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.)
Design an algorithm on the server to perform its job with time complexity better than O(k)
6. 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 algorithm with same run time complexity as 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.
7. 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.
