Sale!

# CSCI 570 Homework 4 solution

Original price was: \$35.00.Current price is: \$28.00.

Category:

## Description

5/5 - (1 vote)

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.