Show that the given algorithm is a 2-approximation algorithm

Assignment Help Computer Engineering
Reference no: EM132142180

Question :

Suppose that you have a set of n files that have to be copied on 1GB USB drives. You can assume that the file sizes are known and always less than or equal to 1GB.

The objective is to use the minimum possible number of USB drives. Suppose that you use the following algorithm: if the file fits in the current USB drive, add the file to the drive, otherwise, put this USB drive aside and start a new one.

The algorithm is simple in that it does not pre-arrange the files according to their sizes and it never tries to revisit previously closed USB drives to scavenge for additional space.

a. Show an example in which the algorithm uses n/2 drives but the optimum file arrangement uses only n/4 + 1.

b. Show that the given algorithm is a 2-approximation algorithm.

Reference no: EM132142180

Questions Cloud

What is the equilibrium value of a share of jones inc today : The required return on the cash flows of Jones' dividends is 14% per year. a) What is the equilibrium value of a share of Jones Inc today?
How many sandwiches do you make : Suppose you are planning a party for 10 friends. You decide to make sandwiches to serve at the party, no more than one sandwich per person.
What is the effective yield to maturity : Use Appendix B for an approximate answer but calculate your final answer using the formula and financial calculator methods.
Find sum of firms profits in the subgame perfect equilibrium : Firm 1 must decide whether to enter an industry in which firm 2 is an incumbent. To enter this industry, firm 1 must choose to build either a plant with a small
Show that the given algorithm is a 2-approximation algorithm : Show an example in which the algorithm uses n/2 drives but the optimum file arrangement uses only n/4 + 1.
Develop preliminary prototype of proposed e-commerce website : CIS5101 Management of Business Online - Describe the website structure and the purpose of each element (include snapshots and diagrams where appropriate)
Is the firm making profits or losses : A firm is currently producing 30 units of output. At this level of output produced: Its average total cost is 110 (ATC =110) The market price per unit of output
What does that indicate and how do you fix it : Suppose you are in the process of drawing the DFDs, and you have found that one of your Level 1 DFD describing a process in level 0.
Calculate the quantity of units : A firm has demand equation Q = 10 - 2P. The firm must sell an integer quantity of product and charge the same price per unit of product for all units sold.

Reviews

Write a Review

Computer Engineering Questions & Answers

  What are some of benefits of building a cross-cultural team

What are some of the ways that cross-cultural teams are distinguished from other types of teams? What are some of the benefits and difficulties of building.

  Write down english narrative that converts currency

Using the C compiler, write down a C program that contains your narrative from broken down into one line sentences, that have been commented out.

  What is the difference between a clock cycle and a bus cycle

The 68000 has three interrupt request inputs, IPL0*--IPL2*, that indicate the level of the interrupt request. Because peripherals have a single interrupt.

  What is the problem that can be solved by business analytics

What is the problem that can be solved by business analytics. Provide a specific example where this applies.What kind of data would you need to do this. Where can you find such datasets. Provide an URL if the datasets are available publicly.

  How an intrusion detection system actively respond to attack

What is a Null session problem? How can an intrusion detection system actively respond to an attack?

  Choose third-party control available for visual basic.net

choose a third-party control available for Visual Basic.NET. Discuss how this control is used in an application. What are the advantages and disadvantages of using third-party controls in your applications.

  Terminate and cause the zombie tasks to be deallocated

while a child process is fork()ed, a parent may wait for the successful completion of the child via the wait() service (or one of its variants) so that the return result of that application can be read from the process descriptor block.

  Create an xml document with three instances of car element

Create an XML document with at least three instances of the car element defined in the XML schema of above problem.

  How important is it to keep the site current

How important is it to keep the site current.According to "Putting Business Online Isn't Always Easy" (2005), "the biggest mistake people make is failing to know the commitment a Web site demands."

  Define global security describe how they are involved

ntify Organizations involved in Global Security describe how they are involved

  Write down a program called tripper.cgi

Write down a program called tripper.cgi that will ask the user the number of miles he has driven and the amount of gas he used. In the tripper script, write a subroutine called mileage that would calculate and return the user's mileage (miles per ..

  Explain the low benefit and cost of pollution control

Assume there are two types of communities in the US, those in which there is a high benefit of pollution control and a high cost of pollustion control.

Free Assignment Quote

Assured A++ Grade

Get guaranteed satisfaction & time on delivery in every assignment order you paid with us! We ensure premium quality solution document along with free turntin report!

All rights reserved! Copyrights ©2019-2020 ExpertsMind IT Educational Pvt Ltd