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.
2. Submit your solution to Gradescope. Make sure only one of your group members submits. After
submitting, make sure to add your group members.
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

5/5 - (3 votes)

Writing Assignment 5 CMPSC 465
INSTRUCTIONS:
1. Include the name and PSU access ID of every member in your group in your solution.
2. Submit your solution to Gradescope. Make sure only one of your group members submits. After
submitting, make sure to add your group members.
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
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.
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