COMP 3711 − Design and Analysis of Algorithms 2022 Spring Semester − Written Assignment # 3 Solution
Solutions 1 [30 pts] Greedy File Allocation
(a) Let L[1 · · · n] be an array listing the sizes of each file; specifically, file i has
size L[i].
Copyright By PowCoder代写 加微信 powcoder
If the files are stored in order from 1 to n, then time T (k) it takes to read
T(k) = L[i] i=1
If we change the order of the files on the tape, we change the time of reading the files; some files become more expensive to read, but others become cheaper. Different file orders are likely to result in different ex- pected time. Specifically, let π(i) denote the index of the file stored at position i on the tape. Then the expected time of the permutation π is
Observation: E[T (π)] is minimized when L[π(i)] ≤ L[π(i + 1)] for all i.
Proof: Suppose L[π(i)] > L[π(i + 1)] for some index i. To simplify notation, let a = π(i) and b = π(i+1). If we swap files a and b, then the time of reading a increases by L[b], and the time of reading b decreases by L[a].
Overall, the swap changes the expected time by (L[b] − L[a])/n. But this change is an improvement, because L[b] < L[a]. Thus, if the files are out of order, we can decrease the expected time by swapping some mis-ordered pair of files.
To show that the greedy algorithm is actually optimal, we proved that the output of any other algorithm can be improved by some sort of ex- change.
(b) Let L[1···n] be an array listing the sizes of each file, and p[1···n] be an array listing the probability of accessing each file; specifically, file i has size L[i] and probability p[i].
Suppose we sort the files by increasing size. Specifically, let π(i) denote the index of the file stored at position i on the tape after sorting by size.
Leta=π(i)andb=π(j)betwodifferentfiles. Ifweswapfilesaandb, then the time of accessing a increases by L[b], and the time of reading b decreases by L[a].
Overall, the swap changes the total time by p[a]L[b] − p[b]L[a]. If the sizes and probability of accessing files a and b satisfy the inequality p[a]L[b] − p[b]L[a] < 0, we can decrease the total time by swapping a and b. Therefore, sorting by increasing size is not optimal in the general case.
E[T (π)] = L[π(i)].
To prove that sorting by increasing size is not correct in the general case, one can give a counterexample which describe a specific input for which ordering by increasing size of the file does not give the correct solution.
Explicitly calculate the solution cost when the files are sorted by increas- ing size and then show a solution which is cheaper than that one.
(c) The rule:
Sort all files according to the ratio L/p.
Proof of Optimality: Let L[1 · · · n] be an array listing the sizes of each file, and p[1 · · · n] be an array listing the probability of accessing each file; specifically, file i has size L[i] and probability p[i].
Let π(i) denote the index of the file stored at position i on the tape after sorting according to the ratio.
Now the expected time T(k) to read the file k is
E[T (k)] = p[π(k)] L[π(i)], i=1
and expected time of the permutation π is
E[T (π)] = E[T (k)] = p[π(k)] L[π(i)] = p[π(k)]L[π(i)] k=1 i=1 k=1 i=1
Observation: E(T(π))isminimizedwhenL[π(i)]/p[π(i)]≤L[π(i+ 1)]/p[π(i + 1)] for all i.
Proof: Suppose L[π(i)]/p[π(i)] > L[π(i + 1)]/p[π(i + i)] for some index i. To simplify notation, let a = π(i) and b = π(i + 1). If we swap files a and b, then the time of accessing a increases by L[b], and the time of accessing b decreases by L[a]. Overall, the swap changes the total time by p[a]L[b] − p[b]L[a]. But this change is an improvement, because
L[a]/p[a] > L[b]/p[b] ⇔ p[a]L[b] − p[b]L[a] < 0.
Thus, if any two adjacent files are out of order, we can improve the total
time by swapping them.
Time Complexity: If we use an efficient sorting algorithm to sort the list according to the ratio, the running time is clearly O(n log n), plus the time required to actually write the files.
Solution 2 [15 pts] (a) The Huffman tree.
(b) The codebook in alphabetical order.
letter codework
Solutions 3 [25 pts] Greedy
(a) Any example that demonstrates that the matrix is not unique would suffice. For
example, the two below matrices do satisfy the requirements.
i 1234 1100 2
2 1 1 0 ROW
i 1234 1010 2
2 1 1 0 ROW
(b) We use a greedy strategy to solve this problem and store the result in the matrix MAT[j][i], where j and i indicate the row and column index, respectively. We iterate over the columns from i = 1 to i = m and fill each cell. If at position i = k COLUMN[k] = 0, then MAT[j][k] = 0 for any j. Otherwise, if at i = k COLUMN[k] > 0, we insert COLUMN[k] many 1s in the k-th column to satisfy the requirement. Specifically, we insert 1s in the row with the max
budget bj for a row j. We define bj as the number of remaining 1s we need to insert in row j. In the current column k, we set MAT[r][k] = 1, where r = argmaxj bj. To do this efficiently, we use a max heap, where we insert the elements (bj,j) for all j, where bj = ROW[j] in the beginning. Thus, at a random column i = k, we pop COLUMN[k] elements from our max heap. For each popped element (br,r), we set MAT[r][k] = 1 and insert a new element with decreased budget (br − 1, r) in the heap. This way, if a column requires all its entries to be 1s, this strategy guarantees that there is no ROW[j] = 0 for any j.
Solutions 4 [30 pts] Greedy/Dynamic Programming
To solve this problem we first check, if there is a solution. We are able to make the round trip if and only if i G[i] − C[i] ≥ 0. If we cannot complete the trip our algorithm returns -1. Otherwise, we use a greedy strategy to find a solution. The idea is that, if we find the maximum contiguous subarray, then the start of it, is a valid position for us to begin. Let the maximum contiguous subarray span from position i to j. If we initiate our trip at the gas station i, when we reach gas station j, we will have the most possible gas in our tank. Since we already know that there is a solution, then position i is a valid starting point. We define the recurrence relation for this problem. Let Vj be the sum of the maximum contiguous subarray that includes j. When j = 1, then V1 = G[1]−C[1], otherwise Vj = max(G[j]−C[j], Vj−1 +G[j]−C[j]). We also store Vj start, Vmax, and Vmax start. Vj start stores the starting index of Vj, Vmax stores the sum of the maximum contiguous subarray, and Vmax start stores the beginning of that subarray. We update Vj start = j, when G[j] − C[j] > Vj−1 + G[j] − C[j]. We also update Vmax = Vj and Vmax start = Vj start, when Vmax < Vj. Finally, we return Vmax start.
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com