Determine the worst-case time efficiency of ff

Assignment Help Basic Computer Science

Reference no: EM131252728

Consider the greedy algorithm for the bin-packing problem, which is called the first-fit (FF) algorithm: place each of the items in the order given into the first bin the item fits in; when there are no such bins, place the item in a new bin and add this bin to the end of the bin list.

a. Apply FF to the instance

and determine whether the solution obtained is optimal.

b. Determine the worst-case time efficiency of FF.

c. Prove that FF is a 2-approximation algorithm.

Reference no: EM131252728

Questions Cloud

Has julie been treated fairly in the newport electronics : Has Julie been treated fairly in the "Newport Electronics" case? Is this a case of "wrongful termination"? Justify your answer.

Explain the most common forms of digital crime : Determine the category of computer crimes or cyber terrorism that presents the greatest overall threat at the present time. Provide a rationale to support your response. Summarize the roles and responses that the U.S. government, court systems, an..

Who is the movie protagonist : Who is the movie's protagonist? What factors and needs motivate or complicate their actions? Can you characterize each of them according to their depth (round characters versus flat) and motivation

Find the set of nash equilibrim of the game : Find the set of Nash equilibria (mixed as well as pure) of the game in Figure 1. Show that the game is dominance solvable; - find the pair of payoffs that survives. Find an order of elimination such that more than one outcome survives.

Determine the worst-case time efficiency of ff : Determine the worst-case time efficiency of FF.

Explain any special circumstances applicable : You also may explain any special circumstances applicable to your background and elaborate on your scholarly publications, awards, achievements, abilities, and/or professional history.

What ways can the business benefit from a web site : Prepare functional specifications for the company's use of the Web and the Internet. Include links to and from other sites in your design. Prepare a list of technological specifications for implementation (e.g., what hardware and software are nec..

Analyze a passage in shakespeare : Analyze a passage in Shakespeare and translate the language into modern English. Your ability to translate Shakespeare's English, and work to understanding it on it's own merits, is instrumental to analyzing and enjoying Hamlet.

Analyze how informal groups form and how they influence : Analyze how informal groups form and how they influence the activities of public agencies. What role does organizational culture play in the forming of these informal groups?

User Account

All Pages