Solution-What is the running time of your algorithm in

What is the running time of your algorithm in terms of n

Assignment Help Data Structure & Algorithms

Reference no: EM13860806

1. Let p1; p2; :::pn be n programs to be stored on a disk. Program pi requires si kilobytes of storage, and the capacity of the disk is D, where s1 + s2 + : : : + sn > D.

(a) Give an ecient algorithm to determine which programs to store on the disk so that the total number of programs on the disk is maximized. If you give a greedy algorithm, be sure to prove that your algorithm is correct by proving both greedy choice and optimal program substructure. What is the running time of your algorithm, in terms of n?

(b) Give an ecient algorithm to determine which programs to store on the disk so that as much of the disk as possible is utilized. If you give a greedy algorithm, be sure to prove that your algorithm is correct by proving both greedy choice and optimal program substructure. What is the running time.

Reference no: EM13860806

Questions Cloud

Derive the payoff matrix and nash equilibria : Two companies are deciding at what point to enter a market. The market lasts for four periods and companies simultaneously decide whether to enter in period 1, 2, 3, or 4, or not enter at all. Thus, the strategy set of a company is {1,2,3,4,do not en..

Bradmark case description : Read the Bradmark Case located in the "Bradmark Case Description" folder and answer the following questions:

The journal entry to write off an account judged : The journal entry to write off an account judged to be uncollectible under the allowance would include a debit to

How do i display and parse a date : 1) How do I display and parse a date? 2) What is object serialization? 3) Can I persist my objects using serialization instead of using a relational or object database?

What is the running time of your algorithm in terms of n : If you give a greedy algorithm, be sure to prove that your algorithm is correct by proving both greedy choice and optimal program substructure. What is the running time of your algorithm, in terms of n?

Sojourner truth''s interpreted by cicely tyson in video form : Consider the imagery you created in your mind as you interacted with the written version of The Open Window. Describe this imagery and discuss whether it helped you understand the story. Did the imagery or imagined tone change when you listened t..

What is the probability that a plan recipientd ies before : What is the probability that a plan recipientd ies before they reach the standard retirement age of 65?

Analyze the seven types of new religious movements : Outline the development of Islam from the death of Muhammad to the end of the Ottoman Empire. Discuss some of the factors that led to the eventual stagnation of Islam in comparison with the dynamic scientific and political developments of the mode..

Create a project to detect the iris and pupil : Create a Project to do the following: Detect the Iris and pupil, Measure the location "Centroid" of iris/pupil and Measure the diameter of the iris and pupil.

User Account

All Pages

What is the running time of your algorithm in terms of n

Reference no: EM13860806

Reference no: EM13860806

Questions Cloud

Reviews

Write a Review

Data Structure & Algorithms Questions & Answers

Implement an open hash table

Use a search tree to find the solution

How to access virtualised applications through unicore

Recursive tree algorithms

Determine the mean salary as well as the number of salaries

Currency conversion development

Cloud computing assignment

Design a gui and implement tic tac toe game in java

Recursive implementation of euclids algorithm

Data structures for a single algorithm

Write the selection sort algorithm

Design of sample and hold amplifiers for 100 msps by using n

Assured A++ Grade

Academics

Major Subjects

Majors

Get In Touch

TERMS & POLICIES

HELP & SUPPORT