subject

You have the task of heating up n buns in a pan. A bun has two sides and cach side has to be heated up separately in the pan. The pan is small and can hold only (at most) two buns at a time. Heating one side of a bun takes 1 minute, regardless of whether you heat up one or two buns at the same time. The goal is to heat up both sides of all n buns in the minimum amount of time. Suppose you use the following recursive algorithm for heating up (both sides) of all n buns. If n=1, then heat up the bun on both sides; if n = 2, then heat the two buns together on each side; if n > 2, then heat up any two buns together on each side and recursively apply the algorithm to the remaining n - 2 buns. a) Set up a recurrence for the amount of time needed by the above algorithm. Solve the recurrence.
b) Show that the above algorithm does not solve the problem in the minimum amount of time for all n >0.
c) Give a correct recursive algorithm that solves the problem in the minimum amount of time.
d) Prove the correctness of your algorithm (use induction) and also find the time taken by the algorithm.

ansver
Answers: 3

Other questions on the subject: Computers and Technology

image
Computers and Technology, 24.06.2019 15:30, jerry1496
If you want to delete an entire word at a time, which key should you press along with the backspace or delete key?
Answers: 1
image
Computers and Technology, 25.06.2019 12:00, jennyv191
What are the best ways to find data within a spreadsheet or database? check all that apply. sorting tools the function scrolling the search engine the search box
Answers: 1
image
Computers and Technology, 25.06.2019 23:30, nkslsj
Lisa is modifying a spreadsheet. which view will allow lisa to see how her changes will look when she prints the spreadsheet?
Answers: 1
image
Computers and Technology, 26.06.2019 03:50, yair7
4. the arduino uno analog inputs range is limited to how many bits? a. 8 b. 10 c. 12 d. 16
Answers: 1
You know the right answer?
You have the task of heating up n buns in a pan. A bun has two sides and cach side has to be heated...

Questions in other subjects:

Konu
Biology, 23.11.2020 18:00