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

Both sides previous revision Previous revision | |||

cs-312:hw8.5 [2014/12/31 16:21] ringger |
cs-312:hw8.5 [2015/01/30 08:43] (current) ringger |
||
---|---|---|---|

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.) |