python代写-CS 577
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