Give greedy algorithm to get all n people across bridge

Assignment Help Programming Languages

Reference no: EM1367707

There is a group of n people with speeds s1, ..., sn. They have a conference that starts soon and they must all cross a bridge to get there. All n people begin on the same side of the bridge. It is nighttime and there is only one flashlight. A maximum of two people can cross at one time.

Any party who crosses, either 1 or 2 people, must have the flashlight with them. The flashlight must be walked back and forth, it cannot be thrown. A pair must walk together at the rate of the slower man's race.

1) Provide a greedy algorithm to get all these n people across the bridge in a fastest way.
2) Describe the algorithm briefly
3) Prove the correctness
4) Give the optimal substructure
5) Analyze the time cost of your schedule.

Reference no: EM1367707

Questions Cloud

What is the least amount time necessary for crossing : A hunter wishes to cross a river that is 1.4km wide and flows with a speed of 5km/h parallel to its banks.

Does this index indicate market power : Zelda Manufacturing has are unique product that sells for $15 per unit and marginal cost is $7.50. Conclude Lerner index for Zelda Manufacturing. Does this index indicate market power.

Phenomenological-grounded theory and ethnographic research : The three kinds of qualitative nursing research methods are phenomenological, grounded theory and ethnographic research.

At what height will stream of water strike the building : A fireman 52 m away from a burning building directs a stream of water from a ground-level fire hose at an angle of 32° above the horizontal.

Give greedy algorithm to get all n people across bridge : Give a greedy algorithm to get all these n people across the bridge in a fastest way. Describe the algorithm briefly. Prove the correctness.

What are the frequencies of next two harmonics : A plane diving with constant speed at an angle of 51.7° with the vertical, releases a package at an altitude of 437 m. The package hits the ground 2.93 s after release. How far horizontally does the package travel.

Changing health care system : What other avenues might better educate the general public on the role and scope of nursing and also the changing health care system.

What are brand extensions : Are brand extensions an important brand-growth strategy or can they endanger brands? Perhaps start with a definition of brand extensions?

Why does inflation affect increase in social security : Why does inflation affect increase in Social Security and or profits. Is this effect a cost of inflation, as article suggests. Why or why not.

User Account

All Pages