Description
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(logn) 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
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
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
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 w2, then the shortest path between s and t will be the same as before but with different costs.
Problem 6
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 (16 points) if your algorithm has the same run time complexity as Dijkstra’s algorithm.
Reviews
There are no reviews yet.