answer all of part 2 variants of quicksort

CS3343 Analysis of Algorithms Fall 2018 Homework 3 Due 9/21/18 before 11:59pm (Central Time) 1. Probability (7 points) For the following problem, clearly describe the sample space and the random variables you use. Be sure to justify where you get your expected values from Consider playing a game where you roll n fair six-sided dice. For every 1 or 6 you roll you win $30, for rolling any other number you lose $3n (where n is the total mumber of dice rolled) (1) First assume n-1 (i.c., you only roll one six-sided die) (a) (1 point) Describe the sample space for this experiment (b) (1 point) Describe a random variable which maps an outcome of this experiment to the winnings you receive (c) (1 point) Computc the cxpected valuc of this random variablc (2) Now assume n = 7 (i.e., you roll 7 six-sided dice) (a) (1 point) Describe the sample space for this experiment (you don't need to list the elements but describe what is contained in it) (b) (1 point) Describe a random variable which maps an outcome of this experiment to the winnings you receive. (Hint: Express your random variable as the sum of seven random variables.) (c) (1 point) Compute the expected value of this random variable using the linearity of expectation. Based on this would you play this game? (3) (1 point) What is the largest value of n for which you would still want to play the game? Justify your answer 2. Variants of quicksort (6 points) Supposc company X has creatcd 3 new variants of quicksort but, becausc thcy are unsure which is asymptotically best, they have hired you to analyze their runtimes. Compute the asymptotic runtimes of the variants and use this to justify which is best: . Variant 1: Partitioning the array still takes (n) time but the array will always be divided into a n and a-lm portion (where x is some constant value > . Variant 2: Partitioning the array now takes 9(n1.1) ti but the array will always be divided perfectly in half Variant 3: Partitioning the array now only takes (vm) time but all of the numbers cxccpt the pivot will be partitioned into a single array. Reminder: log n E (n) for all c > 0 CS3343 Analysis of Algorithms Fall 2018 Homework 3 Due 9/21/18 before 11:59pm (Central Time) 1. Probability (7 points) For the following problem, clearly describe the sample space and the random variables you use. Be sure to justify where you get your expected values from Consider playing a game where you roll n fair six-sided dice. For every 1 or 6 you roll you win $30, for rolling any other number you lose $3n (where n is the total mumber of dice rolled) (1) First assume n-1 (i.c., you only roll one six-sided die) (a) (1 point) Describe the sample space for this experiment (b) (1 point) Describe a random variable which maps an outcome of this experiment to the winnings you receive (c) (1 point) Computc the cxpected valuc of this random variablc (2) Now assume n = 7 (i.e., you roll 7 six-sided dice) (a) (1 point) Describe the sample space for this experiment (you don't need to list the elements but describe what is contained in it) (b) (1 point) Describe a random variable which maps an outcome of this experiment to the winnings you receive. (Hint: Express your random variable as the sum of seven random variables.) (c) (1 point) Compute the expected value of this random variable using the linearity of expectation. Based on this would you play this game? (3) (1 point) What is the largest value of n for which you would still want to play the game? Justify your answer 2. Variants of quicksort (6 points) Supposc company X has creatcd 3 new variants of quicksort but, becausc thcy are unsure which is asymptotically best, they have hired you to analyze their runtimes. Compute the asymptotic runtimes of the variants and use this to justify which is best: . Variant 1: Partitioning the array still takes (n) time but the array will always be divided into a n and a-lm portion (where x is some constant value > . Variant 2: Partitioning the array now takes 9(n1.1) ti but the array will always be divided perfectly in half Variant 3: Partitioning the array now only takes (vm) time but all of the numbers cxccpt the pivot will be partitioned into a single array. Reminder: log n E (n) for all c > 0