1
$\begingroup$

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.


  1. 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)

$\endgroup$