For each n N with n > 2, let Zn be the set that contains all...

Transcribed Image Text:

For each n N with n > 2, let Zn be the set that contains all strings of length n with 2 b's and (n - 2) a's, in any order. (For example, I₁ = {aabb, abab, abba, baab, baba, bbaa}.) 2 Note that In] =() = (-1) because each element of In is made up of n individual characters, all but two of which are equal to a, and there are exactly (2) many different ways to choose the 2 positions that will contain b. (a) [1 mark] Let n N with n > 2, and let k be the value returned by alpha min(s), for some input $ € In. Write an expression for the "exact" number of steps executed by alpha min(s), in terms of n and k. Show your work (explain how you count your steps and how you arrive at your answer). (b) [1 mark] What is the exact average-case running time of alpha min over the set of inputs Z4? Give your answer in the form of a simplified, concrete rational number (like 17/5). Show your work (explain what you are calculating at each step). (c) [3 marks] For each nN such that I, is defined, and each possible return value k for alpha min, give an exact expression for the number of inputs s € In for which alpha min(s) returns k. In other words, calculate |{s € Zn| alpha min(s) returns k}. Show your work (explain how you obtain your expression, and how it relates to the algorithm). (d) [3 marks] Perform an average-case analysis of alpha min, for the input set I, defined above. Give an exact expression (without using Big-O/Omega/Theta). Show your work. In particular, your answer should be expressed in the form of a sum before you simplify it to a closed-form expression. HINT: You may use the following fact. 32 Σ²² = n(n+1)(2n+1) i=1 For each n N with n > 2, let Zn be the set that contains all strings of length n with 2 b's and (n - 2) a's, in any order. (For example, I₁ = {aabb, abab, abba, baab, baba, bbaa}.) 2 Note that In] =() = (-1) because each element of In is made up of n individual characters, all but two of which are equal to a, and there are exactly (2) many different ways to choose the 2 positions that will contain b. (a) [1 mark] Let n N with n > 2, and let k be the value returned by alpha min(s), for some input $ € In. Write an expression for the "exact" number of steps executed by alpha min(s), in terms of n and k. Show your work (explain how you count your steps and how you arrive at your answer). (b) [1 mark] What is the exact average-case running time of alpha min over the set of inputs Z4? Give your answer in the form of a simplified, concrete rational number (like 17/5). Show your work (explain what you are calculating at each step). (c) [3 marks] For each nN such that I, is defined, and each possible return value k for alpha min, give an exact expression for the number of inputs s € In for which alpha min(s) returns k. In other words, calculate |{s € Zn| alpha min(s) returns k}. Show your work (explain how you obtain your expression, and how it relates to the algorithm). (d) [3 marks] Perform an average-case analysis of alpha min, for the input set I, defined above. Give an exact expression (without using Big-O/Omega/Theta). Show your work. In particular, your answer should be expressed in the form of a sum before you simplify it to a closed-form expression. HINT: You may use the following fact. 32 Σ²² = n(n+1)(2n+1) i=1

Answer rating: 100% (QA)

a The algorithm alphamins aims to find the minimum number of steps required to sort a string s conta... View the full answer