Homework Assignment #8.5


To gain experience with computing the expected value of random variables using probability distributions of interest for average-case analysis.


Show all work. i.e., justify your answers.

Question 1

Let's define a simple experiment as follows: you are sorting lists of 40 unique elements having only two elements out of place.

  • How many samples are in the sample space?

(The idea of “combination” will come in handy here. How many ways can one choose $k$ items from $n$? Reminders are to be found here: http://en.wikipedia.org/wiki/Binomial_coefficient#Combinatorics_and_statistics .)

Question 2

Now assume a uniform distribution over samples. Also assume that you have a sorting algorithm “Trouble-sort” that can find the two elements out of place in a list of length $n$ and put them back in order in time $2n+2$. (Thus, if the list were to contain 3 elements, then Trouble-sort always requires 8 steps to put the list back in order.)

Define a random variable $X$which assigns to each sample in our sample space the running time of Trouble-sort on that sample.

  • What is the expected value of our random variable $X$ with respect to the given distribution? i.e., what is the average case analysis of this algorithm under the given assumptions?
cs-312/hw8.5.txt · Last modified: 2015/01/30 15:43 by ringger
Back to top
CC Attribution-Share Alike 4.0 International
chimeric.de = chi`s home Valid CSS Driven by DokuWiki do yourself a favour and use a real browser - get firefox!! Recent changes RSS feed Valid XHTML 1.0