Description
FALL 2025
1. 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. Extract-Median takes O(log n) time
c. Insert takes O(log n) time
Do the following:
a) Describe how your data structure is designed. (5 points)
b) Give algorithms that implement the Extract-Median() and Insert() functions. (8
points)
2. Given an undirected graph 𝐺 = (𝑉, 𝐸) where a set of data centers 𝑉 is connected by a
network of optical links 𝐸. Each link (𝑢, 𝑣) has a positive latency cost 𝑙(𝑢, 𝑣). There is a
proposal to add a new optical link to the network. The proposal specifies a list 𝐶 of
candidate pairs of data centers between which the new link may be established. Your task
is to choose the link that yields the greatest reduction in end-to-end latency between a
given source data center 𝑠 and target data center 𝑡. Design an efficient algorithm for this
problem. No proof is required. Give the runtime complexity of your algorithm. (Note that
your algorithm’s time complexity should not be worse than Dijkstra’s shortest path
algorithm.) (12 points)
3. 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. (10 points)
