xuebaunion@vip.163.com

3551 Trousdale Rkwy, University Park, Los Angeles, CA

留学生论文指导和课程辅导

无忧GPA：https://www.essaygpa.com

工作时间：全年无休-早上8点到凌晨3点

微信客服：xiaoxionga100

微信客服：ITCS521

python代写-CS 577

时间：2021-04-04

CS 577: Introduction to Algorithms Midterm 2

Out: 03/30/21 Due: 04/06/21

Name: Wisc ID:

Problem 1 [70 points]

Before Thanos gathered all the infinity stones, there was a time when he had to travel the galaxies via his spaceship.

Being the very meticulous person he is, Thanos plans to visit planets 1, 2, . . . , n in order and wants to minimize the

cost he has to spend on fuel. Being cursed with knowledge, he knows the price of fuel at each planet to plan his

itinerary with minimal cost.

Formally, let ci be the cost of fuel (per ton) at planet i and let di be the distance in light-years from planet 1 to

planet i. You may assume all the planets are on a linear path such that the distance between planet i and j is equal to

|di − dj | light-years. The spaceship can hold up to T tons of fuel and can travel one light-year for one ton of fuel.

Unfortunately, there is a flat convenience fee pi one has to pay to buy fuel. So if Thanos were to buy 5 tons on planet

i, it would cost pi + 5ci, but if he decides to skip on getting fuel here, it would cost nothing.

A. [40 points] Give a dynamic programming recurrence that returns the minimum cost Thanos has to spend on his

trip. Thanos starts his trip at planet 1 with an empty fuel tank. He shouldn’t run out of fuel between traveling planets

but he doesn’t have to fill up all T tons at once and he may even skip on getting fuel on a planet. You may assume T

and di’s are positive integers and T is large enough to travel between any two adjacent planets.

B. [30 points] Prove the correctness of the recurrence and analyze its runtime in terms of n and T .

Page 2

Problem 2 [30 points]

This question is about a reality TV show Random Idol, which runs as follows. The show has two rounds and n

contestants. In each of the rounds, the contestants participate in a lottery contest that ranks them from best to worst

uniformly at random.1 A contestant i is declared a random idol if for every other contestant j, i beats j (i.e. has a

better rank than j) in at least one of the two rounds.

Any number of participants can be declared random idols. For example, if n = 4 and the first round ordering over

participants is 1, 2, 3, 4 in order from best to worst, and the second round ordering is 3, 1, 4, 2, then participants 1 and

3 are declared random idols.2 If the orderings in the two rounds are 1, 2, 3, 4 and 4, 3, 2, 1, then all of the participants

are declared random idols.

For each of the following parts, choose one of the given options.

1. What is the probability that a particular contestant i is ranked best in both of the first two rounds?

© 1/(log n) © 1/i © 1/n © 1/n2 © 1/(n!)2

Provide a short justification.

1That is, every ranking/permutation is equally likely.

22 does not beat 1 in any of the rounds, and 4 does not beat 1 or 3.

Page 3

2. For some r in {1, · · · , n} what is the probability that the contestant ranked rth best in the first round is declared

a random idol at the end of the second round?

© 1/n © 1/r © r/n © 1/(r!) © (r!)/(n!)

Provide a short justification.

3. What is the expected number of contestants that are declared random idols?

© Θ(1) © Θ(log n) © Θ(√n) © Θ(n)

Provide a short justification.

Page 4

学霸联盟

Out: 03/30/21 Due: 04/06/21

Name: Wisc ID:

Problem 1 [70 points]

Before Thanos gathered all the infinity stones, there was a time when he had to travel the galaxies via his spaceship.

Being the very meticulous person he is, Thanos plans to visit planets 1, 2, . . . , n in order and wants to minimize the

cost he has to spend on fuel. Being cursed with knowledge, he knows the price of fuel at each planet to plan his

itinerary with minimal cost.

Formally, let ci be the cost of fuel (per ton) at planet i and let di be the distance in light-years from planet 1 to

planet i. You may assume all the planets are on a linear path such that the distance between planet i and j is equal to

|di − dj | light-years. The spaceship can hold up to T tons of fuel and can travel one light-year for one ton of fuel.

Unfortunately, there is a flat convenience fee pi one has to pay to buy fuel. So if Thanos were to buy 5 tons on planet

i, it would cost pi + 5ci, but if he decides to skip on getting fuel here, it would cost nothing.

A. [40 points] Give a dynamic programming recurrence that returns the minimum cost Thanos has to spend on his

trip. Thanos starts his trip at planet 1 with an empty fuel tank. He shouldn’t run out of fuel between traveling planets

but he doesn’t have to fill up all T tons at once and he may even skip on getting fuel on a planet. You may assume T

and di’s are positive integers and T is large enough to travel between any two adjacent planets.

B. [30 points] Prove the correctness of the recurrence and analyze its runtime in terms of n and T .

Page 2

Problem 2 [30 points]

This question is about a reality TV show Random Idol, which runs as follows. The show has two rounds and n

contestants. In each of the rounds, the contestants participate in a lottery contest that ranks them from best to worst

uniformly at random.1 A contestant i is declared a random idol if for every other contestant j, i beats j (i.e. has a

better rank than j) in at least one of the two rounds.

Any number of participants can be declared random idols. For example, if n = 4 and the first round ordering over

participants is 1, 2, 3, 4 in order from best to worst, and the second round ordering is 3, 1, 4, 2, then participants 1 and

3 are declared random idols.2 If the orderings in the two rounds are 1, 2, 3, 4 and 4, 3, 2, 1, then all of the participants

are declared random idols.

For each of the following parts, choose one of the given options.

1. What is the probability that a particular contestant i is ranked best in both of the first two rounds?

© 1/(log n) © 1/i © 1/n © 1/n2 © 1/(n!)2

Provide a short justification.

1That is, every ranking/permutation is equally likely.

22 does not beat 1 in any of the rounds, and 4 does not beat 1 or 3.

Page 3

2. For some r in {1, · · · , n} what is the probability that the contestant ranked rth best in the first round is declared

a random idol at the end of the second round?

© 1/n © 1/r © r/n © 1/(r!) © (r!)/(n!)

Provide a short justification.

3. What is the expected number of contestants that are declared random idols?

© Θ(1) © Θ(log n) © Θ(√n) © Θ(n)

Provide a short justification.

Page 4

学霸联盟