0
$\begingroup$

I have the following homework question that I am struggling with. I have read the corresponding chapter from the book, but no guidance there.

Consider a linked list $X: X_1 \to X_2 \to X_3 \ldots$. Assume that the cost of examining a particular element $X_i$ is $C_i$. Note that to examine $X_i$, one needs to scan through all elements in front of $X_i$. Let $P_i$ be the probability of searching for element $X_i$, so the total cost for all searches is $$ \sum_{j=1}^{n} \left( P_j \cdot \sum_{i=1}^{j} C_i \right) $$

  1. Show that storing elements in non-increasing order of $P_i/C_i$ does not necessarily minimize the total cost.

  2. Show that storing elements in non-decreasing order of $P_i$ does not necessarily minimize the total cost.

Any help and direction how to approach the problem will be highly appreciated.

$\endgroup$
  • 2
    $\begingroup$ You need to try a few examples until you hit one in which the orders in 1 and 2 are not optimal. Keep trying. $\endgroup$ – Yuval Filmus Mar 4 '14 at 14:35
  • $\begingroup$ Brute force sounds wrong approach to me! $\endgroup$ – setlio Mar 4 '14 at 16:25
  • $\begingroup$ I never saw that problem, and I have no a priori idea about the proof. But the use of the words "non-increasing" or "non-decreasing" is somehow attracting my attention. So, for each question, I would try with two elements that have the same ranking, but different values for $C_i$, and check what happen for the 2 possible orders. $\endgroup$ – babou Mar 4 '14 at 18:19
  • 1
    $\begingroup$ @setlio It's a general approach for finding counterexamples. You try a few examples, see why they don't work, and then try to compose an example that does work. Alternatively, try to prove that what they ask is impossible, see where the proof fails, and use this to guide your construction. $\endgroup$ – Yuval Filmus Mar 4 '14 at 18:53
  • $\begingroup$ try to find out about the following: what would be the motivation for the suggested ordering? what could cause that motivation to fail (general idea: there are other factors beyond those that motivated the ordering which affect optimality) ? identify degrees of freedom in the construction of samples - how do different realizations thereof affect optimality? furthermore, identify any special cases the assumptions comprise ( general idea: try to re-phrase the problem in simpler terms. what cases will be excluded? investigate them. do the formulae involved simplify for the special cases ? ). $\endgroup$ – collapsar Mar 6 '14 at 14:04
0
+50
$\begingroup$

I'm assuming costs are strictly positive. Otherwise it doesn't make much sense to consider the quantity $P_i/C_i$.

Regarding 1: Consider any order, and suppose that for some $i$, $P_i/C_i < P_{i+1}/C_{i+1}$. Suppose that we switch the elements $i$ and $i+1$. Say that we switched between $\ldots,A,B,\ldots$ and $\ldots,B,A\ldots$. Let $\Delta$ be the difference in average search cost (new cost minus old cost). When looking for $A$, which happens with probability $P_i$, we have to pay $C_{i+1}$ more. When looking for $B$, which happens with probability $P_{i+1}$, we have to pay $C_i$ less. So $$ \Delta = P_i C_{i+1} - P_{i+1} C_i = (P_i/C_i - P_{i+1}/C_{i+1}) C_i C_{i+1} < 0. $$ In other words, the switch was beneficial. We conclude that the optimal arrangement is to store the elements in non-increasing order.

How I found this proof: I tried to construct a counterexample by trying a few examples on two elements, but I didn't work. So I decided to write the inequalities enjoyed by such a counterexample, and solve them in order to find one. The solution showed that in fact no counterexample is possible.

Regarding 2: This is quite easy to construct, especially in view of part 1, which gives a condition for optimality in case there are only two elements. I'm sure you can handle this part yourself.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.