这个作业是完成图算法相关的问题
CMPSC 465 Fall 2020

Problem 1 (10 points).
1. Run Kruskal’s algorithm on the graph given below: give the order of edges that are added to the
MST (whenever you have a choice, always choose the smallest edge in lexicographic order).
2. Run Prim’s algorithm on the graph given below: give the order of vertices that are added to the
MST (whenever you have a choice, always choose the smallest vertex in alphabetic order).
Problem 2 (10 points).
You are given an undirected graph G = (V,E) with edge weights w(e) for every e ∈ E. You are also given
a minimum spanning tree T of G. Let e
0 ∈ E be some edge in G. Describe an O(|E|) algorithm to find the
minimum spanning tree of the graph after removing e
0
, that is, of the graph G
0 = (V,E \ {e
0}). Prove the
correctness of your algorithm.
Problem 3 (14 points).
Let G = (V,E) be an undirected graph. Each edge e ∈ E has weight w(e) and all weights are distinct.
1. Let C be a cycle of G. Let e
∗
:= maxe∈C w(e) be the edge with largest weight in C. Prove that e
∗
cannot appear in any minimum spanning tree of G.
2. Assume the given graph satisfies that |E| = |V| + 9. Design an O(|V|) time algorithm to find the
minimum spanning tree of G, and prove the correctness of your algorithm.
Problem 4 (10 points).
You are given n intervals [Li
,Ri
], 1 ≤ i ≤ n, where Li and Ri are integers and satisfies 1 ≤ Li < Ri ≤ 10000. Now you want to find a set of integers S satisfying that for any interval [Li ,Ri ], there are at least one integer in S that is inside that interval. Design an O(nlogn) alogrithm to find the minimum size of set S. Problem 5 (10 points). You are given n items in a list L = {p1, p2,…, pn}. Item pi is assigned an importance rate wi ≥ 0; all rates are distinct. You want to buy all items subjected to the following two requirements: 1, each item must be paid at least 1 dollar; 2, item with a higher importance rate should be paid at least 1 dollar more than their neighbors in L. Design a greedy algorithm to find the minimized total money you need to spend. Your algorithm should run in O(n) time. Prove the correctness of your algorithm. For example, given a list L with 4 items; the importance rate for {p1, p2, p3, p4} are (1,0,3,2) respectively. Then the minimal total money is 6 dollars, since we pay the 4 items with 2, 1, 2, 1 dollars respectively. Bonus Problem (6 points). You are given n jobs {1,2,···,n}. Job i requires ti time to process, and job i is associated with a significance si > 0. You need to order these n jobs and process them sequentially follow that order. Let fi be the finishtime of job i, defined as the sum of the processing time of job i and the jobs before job i. For example,
assume n = 3, if the order is (3,1,2); then f3 = t3, f1 = t3 +t1, and f2 = t3 +t1 +t2. Design a greedy
algorithm in O(nlogn) time to find an order so as to minimize ∑1≤i≤n
si
· fi
, and prove its correctness.