## Description

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