Discuss the optimality of your algorithm

Assignment Help Computer Engineering

Reference no: EM133368713

The multimedia/mobile company you work for is currently attempting to transfer large media files from older disks to newer disks (on various servers). The task of simply copying over all of these files in any haphazard order is fairly straightforward; however, you believe that you can improve upon a haphazard approach and hope to improve the efficiency of storage space on the new disks. You have a collection of m disks, but you believe that if you smartly organize the media files onto the disks, you may not need to use all m disks.

You plan to design a greedy algorithm to efficiently transfer media to storage devices. Note that this is an optimization problem.

Optimization problems have a general structure and consist of some quantity to be maximized or minimized under some list of constraints. In this problem, you have n files (f1, ..., fn) with corresponding sizes (in MBs)

S1, ... Sn. Your goal is to store these files onto m disks, d1, .... dm, that have corresponding storages amounts t1, ..., tm.
Note that one file cannot be spread across multiple disks.

In this problem, the goal is to minimize the amount of storage that is not used on each disk (that is used). This should also minimize the total number of number of disks being used. That is, you would like to fill up each disk as much as possible while leaving a minimally small amount of unused storage. (In the perfect case, each disk would be perfectly filled, and there would be no unused storage.) If there are any disks left unused, you will be able to return them for a refund.

Part 1

Design a greedy algorithm using pseudocode that solves this optimization problem of transferring files to disk while minimizing unused storage. The inputs to this algorithm are the number of files n, corresponding sizes (in MBs) S1, ... Sm, m the number of disks, and corresponding storages amounts t1, ... tm. The algorithm should return an array map[i] which contains the disk index of which the ith media file should be stored.

* Comment your pseudocode for increased readability.

Part 2
* Discuss the optimality of your algorithm. Is it guaranteed to return an optimal result?
* What is the Big-O time complexity of this algorithm in terms of m and n? Justify your answer.

Part 3
• If you were to solve this problem using a brute force or exhaustive search method, what would be the time complexity? Justify your response.

Reference no: EM133368713

Questions Cloud

Population of russia and the eurasian republics : Which of the following has/have limited the population of Russia and the Eurasian republics? What was the goal of the European Union when it was formed?

Program will return the era in the history of the usa : Rows necessary to load the information from the UnitedStatesErastxt Download UnitedStatesErastxt file and load that file into the array

What was the firm cash flow to creditors during 2022 : What was the firm's cash flow to creditors during 2022? Note: A negative answer should be indicated by a minus sign. Do not round intermediate calculations

Dance parties depicted in the kings of the world : What function do the dance parties depicted in "The Kings of the World" by Laura Mora Ortega serve?

Discuss the optimality of your algorithm : CS 627 Colorado Technical University Discuss the optimality of your algorithm. Is it guaranteed to return an optimal result? * What is the Big-O time complexity

What is the annualized return on your investment : You buy a stock for $11,500. It annually pays a dividend of $375 per year for 10 years after which you sell the shares for $9,125. What is the annualized return

What is the most you should pay for the annuity : You have a chance to buy an annuity that pays $1,200 at the beginning of each year for 8 years. You could earn 5% on your money in other investments

Write a calculator program that inputs two numbers : CSC 600 National University College Write a calculator program that inputs two numbers, defined as text fields. Create a third text field for the output

Describe events that led to the zootsuit riot : Describe the events that led to the Zootsuit riot. Elaborate on the role the media played during the Zootsuit riots.

User Account

All Pages