Differences

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

Link to this comparison view

Both sides previous revision Previous revision
cs-312:hw8.5 [2014/12/31 23:21]
ringger
cs-312:hw8.5 [2015/01/30 15: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 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.)
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