##### Differences

This shows you the differences between two versions of the page.

 cs-312:hw8.5 [2014/12/31 16:21]ringger cs-312:hw8.5 [2015/01/30 08:43] (current)ringger Both sides previous revision Previous revision 2015/01/30 08:43 ringger 2014/12/31 16:21 ringger 2014/12/31 15:58 ringger created 2015/01/30 08:43 ringger 2014/12/31 16:21 ringger 2014/12/31 15:58 ringger created Line 10: Line 10: ===Question 1=== ===Question 1=== - ''​For Winter 2015'':​ use lists of 40 unique elements. + Let's define a simple experiment as follows: ​ you are sorting lists of 40 unique elements ​having ​only two elements out of place. - + - Let's define a simple experiment as follows: ​ you are sorting lists of 5 unique elements ​${1,​2,​3,​4,​5}$ that only have two elements out of place. + * How many samples are in the sample space? * 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 .) (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 .) - ''​For Winter 2015'':​ split the following into a separate question. + + === 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.) 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.) 