Computers and Technology, 20.06.2020 16:57 lilpetals

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.

Answers: 3

Show answers

Other questions on the subject: Computers and Technology

Computers and Technology, 23.06.2019 20:40, bobby3350

On nba 2k 19, every time i try to join a my park game, it leads ro a website telling my dad that he needs ps plus. i already have ps plus though. how do i fix this?

Answers: 2

continue

Computers and Technology, 23.06.2019 21:50, Trinhphuongtran

Description: write function lastfirst() that takes one argument—a list of strings of the format "lastname, firstname" —and returns a list consisting of two lists: (a) a list of all the last names (b) a list of all the first names

Answers: 2

continue

Computers and Technology, 23.06.2019 22:30, delawdermia27

The output voltage of a power supply is assumed to be normally distributed. sixteen observations are taken at random on voltage are as follows: 10.35, 9.30, 10.00, 9.96, 11.65, 12.00, 11.25, 9.58, 11.54, 9.95, 10.28, 8.37, 10.44, 9.25, 9.38, and 10.85

Answers: 1

continue

Computers and Technology, 24.06.2019 13:50, jaystarr9395

Write a program that performs a simple n-body simulation, called "jumping leprechauns." this simulation involves n leprechauns, numberd 1 to n. it maintains a gold value g_i for each leprechaun i, which begins with each leprechaun starting out with a million dollars worth of gold, that is, g_i = 1000000 for each i = 1,. in addition, the simulation also maintains, for each leprachaun, i, a place on the horizon, which is represented as a double-precision floating point number, x_i. in each iteration of the simulation, the simulation processes the leprachauns in order. processing a leprachaun i during its iteration begins by computing a new place on the horizon for i, which is determined by the assignment:

Answers: 3

continue

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...