In this quiz, you will implement the greedy algorithm discussed in class to dete

Question

In this quiz, you will implement the greedy algorithm discussed in class to determine an optimal
allocation of files in a tape to minimize the average cost to access the files.

Code should be in Python

CSC 323 Algorithm Design and Analysis, Spring 2018 Instructor: Dr. Natarajan Meghanathan Quiz 5 Implementation of the Greedy Algorithm to Determine an Optimal Allocation of Files in a Tape to Minimize the Average Cost to Access the Files In this quiz, you will implement the greedy algorithm discussed in class to determine an optimal allocation of files in a tape to minimize the average cost to access the files. You would gencrate an array of 'N' files such that the maximum size of any file is 'M and the maximum frequency of access for any file is 'F. You will get the inputs for these three values from the user. The actual size for any file would be a randomly generated integer in the range[1.. MJ and the actual frequency of access for any file is also a randomly generated integer in the ...F You need to order the files in the increasing order of () File Index, ii) File Size and iii) Size / Frequency ratio and determine the average costs to access any file for each of these strategies (as is done in the examples in the slides). You need to use an appropriate sorting algorithm that would facilitate sorting the dataset based on one of the three measures (file index, file size or size/frequency ratio) at any time. Break any tie in the ordering of the files (when ordered based on file size or size/frequency ratio) using the file index Student Name Student Name Leon Anderson Uiwal Baskota Albert Boaten Samuel A. Da James Danicl Zakeia Davis Justin E Amanuel E. Gebre 25 5025 Mel Groom 10 2550 15 25 50Antonie Hobson 20 | 25 | 50 25 25 50Justin McGuffee 30 25 50 10 50 25Keara Rogers 15 50 25 20 | 50 | 25 | | Nebivou Tadesse Yoseph H Portia Junius Ryun Moore Timothy Stewart Phat Trarn 10 25 75 15 25 75 20 | 25 | 75 25 | 25 | 75 30 25 75 10 75 25 15 75 25 20 75 25 25 75 25 30 | 50 | 25 (a) The average costs to access the files when ordered based on (i) File Index, (ii) File Size and (iii) Size/Frequency ratio. (b) The ordering of the files (i.e.. print the file index values) based on the allocation strategy (among the three strategies listed above) that results in the lowest average cost to access the files Submission (1) Your complete code (including the code for the sorting algorithm) as a .java or a.cpp file (python or C# is fine too). (2) A single screenshot of the outputs (a) and (b), as mentioned above, for the N, M, F values assigned to you.

Explanation / Answer

#program to show greedy algorithm for optimal file allocation on tape

import random

#name of student
student_name = input("Enter name of student:")
#No. of files
N = int(input("Enter no. of files:"))
#Maximum file size
M = int(input("Enter maximum file size:"))
#Maximum frequency of use
F = int(input("Enter maximum frequency of use:"))
file_indices = [] #for file indices
file_sizes = [] #for file sizes
file_frequencies = [] #for file frequencies of use

#populate lists of file sizes and file frequencies
for i in range(0,N):
    file_indices.append(i)
    file_sizes.append(random.randint(1,M))
    file_frequencies.append(random.randint(1,N))

print("Student name:"+student_name)
print("Allocation strategy: Based on File indices")
#sort based on file indices
for i in range(0,N):
    for j in range(0,N-i-1):
        if file_indices[j] > file_indices[j+1]:
            file_indices[j],file_indices[j+1] = file_indices[j+1],file_indices[j]
            file_sizes[j],file_sizes[j+1] = file_sizes[j+1],file_sizes[j]
            file_frequencies[j],file_frequencies[j+1] = file_frequencies[j+1],file_frequencies[j]

#average cost of accessing file
total_cost = 0
for i in range(0,N):
    total_cost = total_cost+ file_sizes[i]*file_frequencies[i]
average_cost = total_cost/N
print("Average cost:"+str(average_cost))

print("Allocation strategy: Based on File sizes")
#sort based on file indices
for i in range(0,N):
    for j in range(0,N-i-1):
        if file_sizes[j] > file_sizes[j+1]:
            file_indices[j],file_indices[j+1] = file_indices[j+1],file_indices[j]
            file_sizes[j],file_sizes[j+1] = file_sizes[j+1],file_sizes[j]
            file_frequencies[j],file_frequencies[j+1] = file_frequencies[j+1],file_frequencies[j]

#average cost of accessing file
total_cost = 0
for i in range(0,N):
    total_cost = total_cost+ file_sizes[i]*file_frequencies[i]
average_cost = total_cost/N
print("Average cost:"+str(average_cost))

print("Allocation strategy: Based on ratio of File size and File frequency")
#sort based on file indices
for i in range(0,N):
    for j in range(0,N-i-1):
        if (file_sizes[j]/file_frequencies[j]) > (file_sizes[j+1]/file_frequencies[j+1]):
            file_indices[j],file_indices[j+1] = file_indices[j+1],file_indices[j]
            file_sizes[j],file_sizes[j+1] = file_sizes[j+1],file_sizes[j]
            file_frequencies[j],file_frequencies[j+1] = file_frequencies[j+1],file_frequencies[j]

#average cost of accessing file
total_cost = 0
for i in range(0,N):
    total_cost = total_cost+ file_sizes[i]*file_frequencies[i]
average_cost = total_cost/N
print("Average cost:"+str(average_cost))

Related Questions

Navigate

• Browse (All)
• Browse I
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.