## 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.