I did exercise problem from Pittsburgh university cs department.
homework.
Question 8 is somewhat exciting. Q8 is solved using greedy algorithm but I have no idea how to prove. Below is Question.
- Consider the following problem. The input consists of the lengths $l_1, \cdots, l_n, $ and access probabilities $p_1, \cdots, p_n, $ for $n$ files $F_1, \cdots, F_n.$ The problem is to order these files on a tape so as to
minimize the expected access time. If the files are placed in the order $F_{s(1)}, \cdots, F_{s(n)} $ then the expected access time is
$$\sum_{i=1}^{n} \Big\{ p_{s(i)} * \sum_{j=1}^{i}l_{s(j)}\Big\}$$
Don't let this formula throw you. The term $p_{s(i)} * \sum_{j=1}^{i}l_{s(j)}$ is the probability that you access the $i$th file times the length of the first i files.
Greedy solution to solve this problem is to order the files from smallest ratio of length over access probability to largest ratio of length over access probability. That is, $\frac{l_i}{p_i} < \frac{l_j}{p_j}$ implies that $s(i) < s(j)$.
How to prove correctness of this algorithm?
(I know I need to show Greedy choice property and optimal substructure)
