**Exercise 2.22: **Let be a list of distinct numbers. We say that and are *inverted *if but . The *Bubblesort* algorithm swaps pairwise adjacent inverted numbers in the list until their are no more inversions, so the list is sorted in order. Suppose that the input to Bubblesort is a random permutation, equally likely to be any of the permutations of the distinct numbers. Determine the expected number of inversions that need to be corrected by Bubblesort.

**Solution: **Let be the expected number of swaps that need to be done by Bubblesort. With , let be random variables that take on value if , otherwise.

Observe that if and then there must be exactly one swap to correct this invertion regardless which and how other swaps are made (since swaps are only applied between adjacent elements).

Thus we have

therefore

.

Now we will calculate

Since is a – random variable,

We have

This yields .

Therefore

.

The average number of swaps needed by Bubblesort is

(we can do this cleanly thanks to the linearity of expectation. We can tell more about how efficient Bubblesort is if we know how “stable” the sort is, which is a thing we can say if we have the variance. I wonder if there is a way to calculate other than directly calculate , which is already not an easy task. )

**Exercise 2.23: ***Linear insertion* sort can sort any array of number in place. The first and second numbers are compared; if they are out of order, they are swapped so that they are in sorted order. The third number is then placed in the appropriate place in the sorted order. It is first compared with the second; if it is not in the proper order, it is swapped and compared with the first. Iteratively, the th number is handled by swapping it downward until the first numbers are in sorted order. Determine the expected number of swaps that need to be made with a linear insertion sort when the input is a random permutation of distinct numbers.

**Solution: **Let be the number of swaps that need to be made with a linear selection sort in sorting . Let be the number of swaps needed when is handled.

We have , thus

We now calculate , the expected number of swaps needed when we handle the .

Observe that when we handle , number of swaps needed is equal to the number of elements greater than in the range .

Let be a random variable takes on value if , otherwise.

Since is a – random variable, we have .

We can express in terms of as followed.

.

Thus

Therefore

(The average number of swaps of the Insertion sort is equal to that of the Bubble sort ??)

**Exercise 32: **You need a new staff assistant, and you have people to interview. You want to hire the best candidate for the position. When you interview a candidate, you can give them a score, with the highest score being the best and no ties being possible. You interview the candidates one by one. Because of your company’s hiring practices, after you interviewed the th candidate, you either offer the candidate the job before the next interview or you forever lose the chance to hire that candidate. We suppose the candidate are interviewed in a random order, chosen uniformly at random from all possible ordering.

We consider the following strategy. First, interview candidates but reject them all; these candidate give you an idea of how strong the field is. After the th candidate, hire the first candidate you interview who is better than all of the previous candidates you have interviewed.

**(a) **Let be the event that we hire the best assistant, and let be the event that th candidate is the best and we hire him. Determine , and show that

.

**(b) **Bound to obtain

.

**(c) **Show that is maximized when , and explain why this means for this choice of .

**Solution:**

**(a) **First we have .

We will calculate .

For event to happen, the following two independent events must happen:

– The best candidate of candidates is the th candidate. This event happens with probability .

– The best of the first candidates is within the the first candidates. This event happens with probability .

So .

Then

**(b) **.

In the text it has been shown that

.

Applying this inequality yields

Thus

[*not completed*]

Posted by L.G. on January 15, 2012 at 2:57 am

I calculated the variance of Bubble-sort and I have Var[X] = 2n+5/18 * E[X]. Is that plausible ?

P.S. I cannot find the solutions for other chapters (>=4) of “Pr. & Comp.” ;(. Would you continue to post the solutions here ? 🙂

Posted by thethong on January 15, 2012 at 9:33 am

Did you get the same answer for as mine in Exercise 2.22 (and 2.23)?

is expectation of a Bernoulli r.v so it is easy to calculate. so may be can be calculated (not sure). If we have and , then follows. How did you calculate ?

(The unit for E[X] is “number of swap”. So I think the unit for Var[X] is “square of number of swap”. I am not sure whether can be of the same order of as in your answer.)

Posted by L.G. on January 15, 2012 at 9:09 pm

Before I answer you, I would just like to know how can I write down here the maths environment, so that it would be easer to read for you. Is the maths environment is the same as in LaTex ?

Posted by thethong on January 15, 2012 at 11:41 pm

Yes, it is almost the same. A WordPress Latex command starts with

Posted by thethong on January 15, 2012 at 11:52 pm

sorry, Latex code starts with $ latex and ends with $ (remove the space between $ and latex)

Posted by L.G. on January 19, 2012 at 2:31 am

Sorry, for delay – I was not able to respond earlier.

So, we need to find and thus which is the main difficulty.

Let’s start from explicit writing of :

where we use the linearity of expectation, the definition of expectation of Bernoulli variables, and the fact that

So now we have to calculate those probabilities and the correspondent number of exchanges done by algorithms.

Let me stop here for a second to see if I worked latex mode properly.

Posted by L.G. on January 19, 2012 at 2:33 am

it seems like it doesn’t support \mathbb. 2nd try :

Posted by L.G. on January 19, 2012 at 2:36 am

Ok, I have some problems here with latex, and I do not want to flood your blog (you can delete the comments above) – can I send you an email with solution in pdf, please (you can post any part of it here later) ?

Posted by thethong on January 19, 2012 at 3:51 pm

I did these exercises more than 2 years ago, but stopped halfway. If you have solutions for the other chapters or unanswered exercises, it is great if you can share them in the comment or send me at thong_pham_the at gmail.com (remove all _ ). If you send an pdf, please send it together with the latex file (if you allow me to post your solution). Thanks!

Posted by Anonymous on September 30, 2016 at 12:51 am

asdf

Posted by link fun88 on December 17, 2016 at 10:21 am

You ought to be a part of a contest for one of the most useful

sites on the web. I most certainly will recommend this blog!