For each n N with n > 2, let Zn be the set that contains all...
Fantastic news! We've Found the answer you've been seeking!
Question:
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
Expert Answer:
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
Related Book For
Microeconomics An Intuitive Approach with Calculus
ISBN: 978-0538453257
1st edition
Authors: Thomas Nechyba
Posted Date:
Students also viewed these accounting questions
-
A bond has an annual coupon of 5%, which makes semiannual payments. The next payment is 3 months away. The bonds quoted price is 105.1 with par of $1000, what is the bond's dirty price? (Please use...
-
Planning is one of the most important management functions in any business. A front office managers first step in planning should involve determine the departments goals. Planning also includes...
-
List three specific parts of the Case Guide, Objectives and Strategy Section (See below) that you had the most difficulty understanding. Describe your current understanding of these parts. Provide...
-
Plainbank has $10 million in cash and equivalents, $30 million in loans, and $15 in core deposits. a. Calculate the financing gap. b. What is the financing requirement? c. How can the financing gap...
-
For Problems 516, please provide the following information. (a) What is the level of significance? State the null and alternate hypotheses. (b) Find the value of the chi-square statistic for the...
-
After seeing the results of the segment analysis for the Nylon Fibers division, James Cameron wants all three divisions focusing on the correct avenues for improving division performance. Refer to...
-
Graph 17; vertex \(a\) Find a Hamilton cycle of least weight for the given graph in Figure 12.362, beginning at the given vertex, and using the brute force method. What is the weight of the cycle?
-
Daytec Companys fixed budget performance report for June follows. The $440,000 budgeted expenses include $300,000 variable expenses and $140,000 fixed expenses. Actual expenses include $130,000 fixed...
-
ABC Inc. will pay a $2.00 dividend next year. It will pay a $3.00 the year after. Following this dividends will grow at an average annual rate of 8% per year forever. Assuming a 12% discount rate...
-
Jackson's Vacuum company makes two types of vacuums: Basic and Advanced. The factory is set up into 3 working departments. Both vacuums utilize process #1 to assemble the basic components. Those...
-
Ngo Corporation began operating on June 26 with no inventory on hand, It then made the purchases listed below. Ngo Corporation sold and delivered 41 units on June 30. Total Cost $ 135.00 Unit Cost $...
-
What constant of nature does the Atwood Machine measure? Why might this approach be better than just dropping a single object and timing its descent
-
One year ago you bought a stock for $38. 12. Yesterday, the stock paid you a dividend of $4.25. Today, you sold the stock for $51.89. What percentage return did you make on your investment? 1)
-
1. On November 1, 2016, GSW, Inc. authorized Steve Kerr to operate a franchisee for an initial franchise fee of P 1,500,000. Of this amount, 40% was received upon contract signing and the balance,...
-
( D 1 ) An aircraft\'s instruments measure an air temperature of 1 5 deg C and an air pressure of 8 3 kPa. What is the density altitude for these conditions? ( Use Equation 2 . 1 which is the Aero...
-
Bob's Auto manufactures cars and currently uses only 50% of its manufacturing facility to make 30,000 cars per year. Bob could rent the unused portion of its plant and receive $3,000 a month....
-
1 A drawer contains 3 black socks, 6 white socks, 1 green sock and 10 blue socks. Determine the probability of randomly selecting a sock that is not green.
-
Digital Fruit is financed solely by common stock and has outstanding 25 million shares with a market price of $10 a share. It now announces that it intends to issue $160 million of debt and to use...
-
The Equity Premium Puzzle: Investments in equities (like stocks) yield substantially higher returns than investment in bonds. By itself, this is no surprisebecause stocks are riskier than bonds. What...
-
Consider inventions such as washing machines or self-propelled vacuum cleaners. Such inventions reduce the amount of time individuals have to spend on basic household chores and thus in essence...
-
One of the conditions we identified as important to the first welfare theorem is that there are no externalities. One of the most important externalities in the real world is pollution from...
-
Expected value with additional information Refer to the data in Problem 24-7 and assume that based on past experience, the probability of demand per day has been determined as follows: Problem 24-7...
-
Use of probabilities to estimate profit Vernon Enterprises designs and manufac- tures toys. Past experience indicates that the product life cycle of a toy is 3 years. Promotional advertising produces...
-
Optimum prices and quantities in curvilinear CVP Anyway Inc. has been able to quantify its demand and cost equations as: Quantity Total cost 10,000 - 40 Price, $10,000+.20 x Quantity
Study smarter with the SolutionInn App