Sale!

Writing Assignment 5 CMPSC 465 solution

\$30.00

Writing Assignment 5 CMPSC 465
INSTRUCTIONS:
1. Include the name and PSU access ID of every member in your group in your solution.
3. Your always need to explain the running time of your algorithm.
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).

Category:

Description

Writing Assignment 5 CMPSC 465
INSTRUCTIONS:
1. Include the name and PSU access ID of every member in your group in your solution.
3. Your always need to explain the running time of your algorithm.
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
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.
1
Writing Assignment 5 CMPSC 465 Fall 2020 (Instructor: Mingfu Shao) Due: Nov. 29, 11:59pm
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.
2