这个作业是完成图算法相关的问题

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.

**程序辅导定制C/C++/JAVA/安卓/PYTHON/留学生/PHP/APP开发/MATLAB**

本网站支持 Alipay WeChatPay PayPal等支付方式

**E-mail:** vipdue@outlook.com **微信号:**vipnxx

如果您使用手机请先保存二维码，微信识别。如果用电脑，直接掏出手机果断扫描。