I don''t know if anyone here is good at proving algorithms, but anyways, I''m having trouble solving this problem. We are given n keys x1, x2, ... , xn to be placed in a dictionary, and the corresponding distinct probabilities p1, p2, ... , pn with which we will subsequently search for these keys. You may assume that p1 > p2 > ... > pn, and that p1 + p2 + ... + pn = 1. a) Suppose the keys are to be inserted into a linked list. Prove that the list in which keys appear in order of decreasing probability, i.e., x1, x2, ... , xn, minimises the expected number of nodes examined to find a key. State the sample space, probability distribution and random variable used in your proof. b) Suppose the keys are to be inserted into a binary search tree. Prove or disprove: Every binary search tree that minimises the expected number of nodes examined to find a key has in its root a key of maximum probability. I just don''t know how to start this thing. Any help would be great.

I smell a homework question, but I''ll try to help you out a bit, or at least get you started

quote:

---

a) Suppose the keys are to be inserted into a linked list. Prove that the list in which keys appear in order of decreasing probability, i.e., x1, x2, ... , xn, minimises the expected number of nodes examined to find a key. State the sample space, probability distribution and random variable used in your proof.

---

Well, it makes sense If you knew that x1 was going to have the highest probability of being looked up, you''d put it first, right? And if you knew x2 was going to be have the second highest probability, you''d put it in there second. A standard distribution curve will be able to prove this. But I''ll leave that up to you

quote:

---

b) Suppose the keys are to be inserted into a binary search tree. Prove or disprove: Every binary search tree that minimises the expected number of nodes examined to find a key has in its root a key of maximum probability.

---

Just keep in mind two things - how a binary tree search operates, and that they only want to know about the key of maximum probability - and you should do fine

This is a homework, isn''t it? You should read the forum FAQ. Anyway, for some clues, to the best of my knowledge:

a) It is optimal because you can''t change the solution without getting a worse result.

b) I think that it''s true, and the same argument can be used. The fact that it is a binary tree is irrelevant here (as far as I can tell)

Asking us to do your homework won''t bring you anything. Ask your teachers for help.

Cédric

Please review the Forum FAQ with regards to asking homework questions in this forum.

Since you indicate that you are not sure where to start, I''ll offer the following advice: Look at the relationship between the probability of searching for each key and the number of nodes required to find that key in each of the structures.

Timkin

Well, this is an interesting topic nonetheless

It''s important that it be a binary tree because they''re talking about the root Can''t have a root without a tree!

Well, you have p1>p2>p3>...>pn. So if n=2 then p1>p2, p1+p1>p1+p2, p1+p1+p2>p1+p2+p2, 2*p1+p2>p1+2*p2 and since you are trying to minimize you would want p1+2*p2. Then suppose it is true for some n so you have 1*p1+2*p2+...+n*pn is less than any other combination. Then you have to show that if you add one more term it would have to be added to the end to minimize the function. If you can do that then you proved it true for all values of n since you already proved it for n=1 and n=2, i.e. i*pk+k*pi>k*pk+i*pi where k<=n and i=n+1.

quote:

---

Original post by Zipster
Well, this is an interesting topic nonetheless

---

Yeah, there aren''t enough of these for my taste

quote:

---

It''s important that it be a binary tree because they''re talking about the root Can''t have a root without a tree!

---

Umm... Yeah, now that you''re saying it, I didn''t even make the effort of thinking about how a binary tree worked.

So... The theorem would be false?

Arrr! I want to discuss it! Timkin, can''t you ban LordG so that we can talk about it?

(obviously, joking)

Cédric

Yep, because of what you are minimizing, i.e. nodes examined. If you were minimizing level times probability, i.e. huffman encoding, it would be true.

Oops, I didn''t realize that. Anyways, it won''t happen again.

a)X  = sum( k=1..n, k * pk ) number of nodes examined.for some i, j with i<j, swap pi and pjX'' = sum( k=1..i-1, k * pk )   + i * pj   + sum( k=i+1..j-1, k * pk )   + j * pi   + sum( k=j+1..n, k * pk )X'' - X = ( i * pj + j * pi ) -          ( i * pi + j * pj )       = (j - i) * (pi - pj)j-i > 0 ⇒ X'' - X < 0 ⇔ pi - pj < 0                     ⇔ pi < pj∴ X minimal ⇔ ∀ i,j / i<j, pi>pj. b) similar proof with a binary search instead of a linear search 

Documents [ GDNet | MSDN | STL | OpenGL | Formats | RTFM | Asking Smart Questions ]
C++ Stuff [ MinGW | Loki | SDL | Boost. | STLport | FLTK | ACCU Recommended Books ]