CSCI 570  - HW 4

CSCI 570  - HW 4
Section 1: Heaps
Reading Assignment: Kleinberg and Tardos, Chapter 2.5.
Problem 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):
• Find median takes O(1) time
• 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.
Section 2: MST
Reading Assignment: Kleinberg and Tardos, Chapter 4.5.
Problem 2
[10 points] Let us say that a graph G = (V, E) is a near tree if it is connected
and has at most n+8 edges, where n = |V |. Give an algorithm with running time
O(n) that takes a near tree G with costs on its edges, and returns a minimum
spanning tree of G. You may assume that all edge costs are distinct.
Problem 3
[12 points] Considering the following graph G:
1. [4 points] In graph G, if we use Kruskal’s Algorithm to find the MST,
what is the third edge added to the solution? Select all correct answers
a. E-F
1
A
B G
E D
F
C
3
8 4
6
6
1
2
2
5
6 4
5
Figure 1: Graph G.
b. D-E
c. A-B
d. C-F
e. D-F
2. [4 points] In graph G, if we use Prim’s Algorithm to find MST starting
at A, what is the second edge added to the solution?
a. B-G
b. B-E
c. D-E
d. A-D
e. E-F
3. [4 points] What is the cost of the MST in the Graph?
a. 18
b. 19
c. 20
d. 21
e. 22
Problem 4
[10 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
2
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.
Section 3: Shortest Path
Reading Assignment: Kleinberg and Tardos, Chapter 4.4.
Problem 5
[20 points] Given a connected graph G = (V, E) with positive edge weights.
In V , s and t are two nodes for shortest path computation, prove or disprove
with explanations:
1. If all edge weights are unique, then there is a single shortest path between
any two nodes in V .
2. If each edge’s weight is increased by k, the shortest path cost between s
and t will increase by a multiple of k.
3. If the weight of some edge e decreases by k, then the shortest path cost
between s and t will decrease by at most k.
4. If each edge’s weight is replaced by its square, i.e., w to w
2
, then the
shortest path between s and t will be the same as before but with different
costs.
Problem 6
[16 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
3
for lowest-cost path searching. You will receive full points (16 points) if your
algorithm has the same run time complexity as Dijkstra’s algorithm.
4