Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: YSYY66

CS310: Advanced Data Structures and Algorithms

Spring 2022 Assignment 4

Questions

1. Solve the midterm exam. If your answer got the full points you can copy it as-is. Otherwise, solve it from scratch. Attach your answers as part of your submission. This means that overall this homework contains 10 questions. A soft copy of the exam is attached as a handout.

2. Given the following weighted, undirected graph:

01

7

(a) Show the process of Kruskal’s algorithm to ﬁnd its minimal spanning tree. The format of your

answer should be the following: write down the edges in the order in which they are processed, and indicate for each edge whether it appears in the ﬁ nal MST or not.

(b) Do the same with Prim’s algorithm. Start from vl .

(c) Draw the ﬁnal MST (despite possibly selecting the edges in a diﬀerent order, the MST should be the same for (a) and (b)!).

3. (Adapted from K&T, 4.2): For each of the following two statements, decide whether it is true or false. If it is true, give a short explanation. If it is false, give a counterexample.

(a) Suppose we are given an instance of the Minimum Spanning Tree Problem on a graph G, with

edge costs that are all positive and distinct. Let T be a minimum spanning tree for this instance. Now suppose we replace each edge cost c(e) by its square, c2 (e), thereby creating a new instance of the problem with the same graph but diﬀerent costs.

T r ue o r f a l se? T must still be a minimum spanning tree for this new instance.

(b) Suppose we are given an instance of the Shortest s − t Path Problem on a directed graph G. We

assume that all edge costs are positive and distinct. Let P be a minimum-cost s − t path for this instance. Now suppose we replace each edge cost c(e) by its square, c2 (e), thereby creating a new instance of the problem with the same graph but diﬀerent costs.

T r u e o r f a l se ? P must still be a minimum-cost s-t path for this new instance

4. (Adapted from K&T, 4.5) Let’s consider a long, quiet country road with houses scattered very sparsely along it. (We can picture the road as a long line segment, with an eastern endpoint and a western endpoint, so each house is a point on an interval) Further, let’s suppose that despite the bucolic setting, the residents of all these houses are avid cell phone users. You want to place cell phone base stations at certain points along the road, so that every house is within four miles of one of the base stations (this actually means that each station covers 8 miles – four to the left, four to the right). Here is a greedy algorithm that achieves this goal, using as few base stations as possible:

• Place the ﬁrst station 4 miles to the east of the westernmost house.

• Repeat, placing each station 4 miles to the east of the ﬁ rst uncovered house.

Show that this greedy algorithm gives the optimal solution (with the minimum number of stations). You can start by showing that there must be an optimal solution that places the ﬁrst station 4 miles to the east of the westernmost house. (the reasoning can be similar to what’s discussed in class about the interval scheduling).

5. (Adapted from K&T 6.1) Let G = (V , E) be an undirected graph with n nodes. Recall that a subset of the nodes is called an independent set if no two of them are joined by an edge. Finding large independent sets is diﬃcult in general; but here well see that it can be done eﬃciently if the graph is simple enough. Call a graph G = (V , E) a path if its nodes can be written as vl , v2 , · · · , vn , with an edge between vi and vj if and only if the numbers i and j diﬀer by exactly 1. With each node vi , we associate a positive integer weight wi . Consider, for example, the ﬁve-node path drawn below. The weights are the numbers drawn inside the nodes:

The goal in this question is to solve the following problem: Find an independent set in a path G whose total weight is as large as possible.

(a) Given the following greedy algorithm:

A l go r i t h m 1 T he ” hea v i e s t - ﬁ r s t ” g r eed y a l go r i t h m
1 :	S t a r t w i t h S equa l t o t he e m p t y s e t
2:	w h il e s o m e node r e m a i n s i n G do
3 :	P i ck a node v i o f m a x i m u m w e i gh t
4 :	A dd v i t o S
5:	D e l e t e v i and it s ne i g hbo r s f r o m G
6 :	e nd w h il e
7:	r e t u r n S
( b )		Sho w t ha t it ﬁ nd s t he m a x i m u m w e i gh t i ndependen t s e t f o r t he pa t h de sc r i bed abo v e . S ho w t ha t t he a l go r it h m doe s no t a l w a ys ﬁ nd t he m a x i m u m w e i gh t i ndependen t s e t f o r an y pa t h by p r ov i d i ng a coun t e r- exa m p l e .
( c)		G i ve an exa m p l e t o sho w t ha t t he f o ll o w i ng a l go r it h m a l so does no t a l w ays ﬁ nd an i ndependen t s e t o f m a x i m u m t o t a l w e i gh t.
A l go r i t h m 2 T he ” odd - e v en ” g r eed y a l go r i t h m
1 :	Le t S l be t he s e t o f		a ll	v i	w he r e i i s an odd nu m be r
2:	Le t S 2 be t he s e t o f		a ll	v i	w he r e i i s an even nu m be r { ( N o t e t ha t S 1 and S 2 a r e bo t h i ndependen t se t s ) }
3 :	D e t e r m i ne w h i c h o f		S l	o r	S 2 ha s g r ea t e r t o t a l w e i gh t
4 :	r e t u r n T ha t s e t.

(d) Give a Dynamic Programming algorithm that takes an n-node path G with weights and returns an independent set of maximum total weight. The running time should be polynomial in n, independent of the values of the weights. Remember that you ﬁ rst have to formulate the algorithm in a recursive manner, and then develop it into DP.

H i n t: First consider, for each index i, whether vi should be in the set or not. Later, consider the maximum set ending in i.

6. (K&T, 6.2): Suppose youre managing a consulting team of expert computer hackers, and each week you have to choose a job for them to undertake. Now, as you can well imagine, the set of possible jobs is divided into those that are low-stress (e.g., setting up a Web site for a class at the local elementary school) and those that are high-stress (e.g., protecting the nations most valuable secrets, or helping a desperate group of Cornell students ﬁnish a project that has something to do with compilers). The basic question, each week, is whether to take on a low-stress job or a high-stress job. If you select a low-stress job for your team in week i, then you get a revenue of li > 0 dollars; if you select a high-stress job, you get a revenue of hi > 0 dollars. The catch, however, is that in order for the team to take on a high-stress job in week i, it’s required that they do no job (of either type) in week i-1; they need a full week of prep time to get ready for the crushing stress level. On the other hand, it’s okay for them to take a low- stress job in week i even if they have done a job (of either type) in week i-1.

So, given a sequence of n weeks, a plan is speciﬁed by a choice of ”low-stress”, ”high-stress”, or ”none” for each of the n weeks, with the property that if ”high-stress” is chosen for week i > 1, then ”none” has to be chosen for week i-1. (It’s okay to choose a high-stress job in week 1.) The value of the plan is determined in the natural way: for each i, you add li to the value if you choose ”low-stress” in week i, and you add hi to the value if you choose ” high-stress” in week i. (You add 0 if you choose ”none” in week i.)

The p r ob l e m : Given sets of values ll , l2 , · · · , ln and hl , h2 , · · · , hn , ﬁnd a plan of maximum value. (Such a plan will be called optimal.)

E xa m p l e : Suppose n = 4, and the values of li and hi are given by the following table. Then the plan of maximum value would be to choose ” none” in week 1, a high-stress job in week 2, and low-stress jobs in weeks 3 and 4. The value of this plan would be 0 + 50 + 10 + 10 = 70

Week 1 2 3 4

li 10 1 10 10

hi 5 50 5 1

(a) Show that the following algorithm correctly solves this problem for the instance above: