Discussion 08a: Mar 9 (Wed) Version: 1.0 CS/ECE 374 A, Spring 2022
, the founding dean of the new Maximilian Q. Levchin College of Computer Science, has commissioned a series of snow ramps on the south slope of the sledding hill1 and challenged , head of the Department of Electrical and Computer Engineering, to a sledding contest. Bill and Lenny will both sled down the hill, each trying to maximize their air time. The winner gets to expand their department/college into both Siebel Center and the new ECE Building; the loser has to move their entire department/college under the Boneyard bridge next to .
Whenever Lenny or Bill reaches a ramp while on the ground, they can either use that ramp to jump through the air, possibly ying over one or more ramps, or sled past that ramp and stay on the ground. Obviously, if someone ies over a ramp, they cannot use that ramp to extend their jump.
1 Suppose you are given a pair of arrays Ramp[1 .. n] and Length[1 .. n], where Ramp[i] is the distance from the top of the hill to the ith ramp, and Length[i] is the distance that any sledder who takes the ith ramp will travel through the air.
Copyright By PowCoder代写 加微信 powcoder
Describe and analyze an algorithm to determine the maximum total distance that Lenny or Bill can spend in the air.
2 Uh-oh. The university lawyers heard about Lenny and Bill’s little bet and immediately objected. To protect the university from either lawsuits or sky-rocketing insurance rates, they impose an upper bound on the number of jumps that either sledder can take.
Describe and analyze an algorithm to determine the maximum total distance that Lenny or Bill can spend in the air with at most k jumps, given the original arrays Ramp[1 .. n] and Length[1 .. n] and the integer k as input.
3 To think about later: When the lawyers realized that imposing their restriction didn’t immediately shut down the contest, they added a new restriction: No ramp can be used more than once! Disgusted by the legal interference, Lenny and Bill give up on their bet and decide to cooperate to put on a good show for the spectators.
Describe and analyze an algorithm to determine the maximum total distance that Lenny and Bill can spend in the air, each taking at most k jumps (so at most 2k jumps total), and with each ramp used at most once.
The north slope is faster, but too short for an interesting contest.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com