Consider the following algorithm. 1 def alpha_min(s: str) -> int: "" Return the smallest index k such that s[k:len(s)] is sorted. Precondition: s is non-empty. i = len(s) - 1 while i > 0 and s[i-1] <= s[i]: 2 3 4 6 i = i - 1 7 return i For each n e N with n > 2, let Tn be the set that contains all strings of length n with 2 b's and (n – 2) a's, in any order. (For example, T4 = {aabb, abab, abba, baab, baba, bbaa}.) n(n-1) Note that |In| = (2) two of which are equal to a, and there are exactly (5) many different ways to c because each element of In is made up of n ind all but ns that will contain b. (a) Let n e N with n > 2, and let k be the value returned by alpha min(s), for some input sE In. Write an expression for the "exact" number of steps executed by alpha min(s), in terms of п аnd k. Show your work (explain how you count your steps and how you arrive at your answer). (b) 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). What is the exact average-case running time of alpha min over the set of inputs T4? Give (d) give an exact expression for the number of inputs s E In for which alpha min(s) returns k. In other words, calculate |{s € In | alpha min(s) returns k}|. Show your work (explain how you obtain your expression, and how it relates to the algorithm). For each n E N such that Tn is defined, and each possible return value k for alpha min, (e) Perform an average-case analysis of alpha. min, for the input set Tn 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. n E² = n(n+1)(2n + 1) (1) i=1
Consider the following algorithm. 1 def alpha_min(s: str) -> int: "" Return the smallest index k such that s[k:len(s)] is sorted. Precondition: s is non-empty. i = len(s) - 1 while i > 0 and s[i-1] <= s[i]: 2 3 4 6 i = i - 1 7 return i For each n e N with n > 2, let Tn be the set that contains all strings of length n with 2 b's and (n – 2) a's, in any order. (For example, T4 = {aabb, abab, abba, baab, baba, bbaa}.) n(n-1) Note that |In| = (2) two of which are equal to a, and there are exactly (5) many different ways to c because each element of In is made up of n ind all but ns that will contain b. (a) Let n e N with n > 2, and let k be the value returned by alpha min(s), for some input sE In. Write an expression for the "exact" number of steps executed by alpha min(s), in terms of п аnd k. Show your work (explain how you count your steps and how you arrive at your answer). (b) 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). What is the exact average-case running time of alpha min over the set of inputs T4? Give (d) give an exact expression for the number of inputs s E In for which alpha min(s) returns k. In other words, calculate |{s € In | alpha min(s) returns k}|. Show your work (explain how you obtain your expression, and how it relates to the algorithm). For each n E N such that Tn is defined, and each possible return value k for alpha min, (e) Perform an average-case analysis of alpha. min, for the input set Tn 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. n E² = n(n+1)(2n + 1) (1) i=1
Computer Networking: A Top-Down Approach (7th Edition)
7th Edition
ISBN:9780133594140
Author:James Kurose, Keith Ross
Publisher:James Kurose, Keith Ross
Chapter1: Computer Networks And The Internet
Section: Chapter Questions
Problem R1RQ: What is the difference between a host and an end system? List several different types of end...
Related questions
Question
![Consider the following algorithm.
def alpha_min(s: str) -> int:
'!' Return the smallest index k such that s[k:len(s)] is sorted.
Precondition: s is non-empty.
1.
i = len(s) - 1
4
while i > 0 and s[i-1] <= s[i]:
6
i = i - 1
7
return i
For each n e N with n > 2, let In be the set that contains all strings of length n with 2 b's and (n – 2)
a's, in any order. (For example, T4 = {aabb, abab, abba, baab, baba, bbaa}.)
Note that |In| = (C) = "("-1) because each element of In is made up of n ind
two of which are equal to a, and there are exactly () many different ways to c
all but
ns that
will contain b.
(a)
Let n eN with n > 2, and let k be the value returned by alpha min(s), for some input
sE 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) What is the exact average-case running time of alpha min over the set of inputs T4? 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).
(d)
give an exact expression for the number of inputs s e In for which alpha min(s) returns k. In
other words, calculate |{s € In | alpha min(s) returns k}.
Show your work (explain how you obtain your expression, and how it relates to the algorithm).
For each n e N such that In is defined, and each possible return value k for alpha min,
(e)
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.
Perform an average-case analysis of alpha min, for the input set In defined above. Give
HINT: You may use the following fact.
Σ
E = n(n + 1)(2n + 1)
(1)
i=1
=WI](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Fc0a416aa-90b7-478f-8c7c-e07ad14a269e%2Fab0280e2-35a8-4658-bbb0-9542a5e55a83%2F5jwsvo_processed.png&w=3840&q=75)
Transcribed Image Text:Consider the following algorithm.
def alpha_min(s: str) -> int:
'!' Return the smallest index k such that s[k:len(s)] is sorted.
Precondition: s is non-empty.
1.
i = len(s) - 1
4
while i > 0 and s[i-1] <= s[i]:
6
i = i - 1
7
return i
For each n e N with n > 2, let In be the set that contains all strings of length n with 2 b's and (n – 2)
a's, in any order. (For example, T4 = {aabb, abab, abba, baab, baba, bbaa}.)
Note that |In| = (C) = "("-1) because each element of In is made up of n ind
two of which are equal to a, and there are exactly () many different ways to c
all but
ns that
will contain b.
(a)
Let n eN with n > 2, and let k be the value returned by alpha min(s), for some input
sE 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) What is the exact average-case running time of alpha min over the set of inputs T4? 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).
(d)
give an exact expression for the number of inputs s e In for which alpha min(s) returns k. In
other words, calculate |{s € In | alpha min(s) returns k}.
Show your work (explain how you obtain your expression, and how it relates to the algorithm).
For each n e N such that In is defined, and each possible return value k for alpha min,
(e)
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.
Perform an average-case analysis of alpha min, for the input set In defined above. Give
HINT: You may use the following fact.
Σ
E = n(n + 1)(2n + 1)
(1)
i=1
=WI
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
Step by step
Solved in 2 steps with 2 images
Recommended textbooks for you
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Computer Networking: A Top-Down Approach (7th Edi…
Computer Engineering
ISBN:
9780133594140
Author:
James Kurose, Keith Ross
Publisher:
PEARSON
Computer Organization and Design MIPS Edition, Fi…
Computer Engineering
ISBN:
9780124077263
Author:
David A. Patterson, John L. Hennessy
Publisher:
Elsevier Science
Network+ Guide to Networks (MindTap Course List)
Computer Engineering
ISBN:
9781337569330
Author:
Jill West, Tamara Dean, Jean Andrews
Publisher:
Cengage Learning
Concepts of Database Management
Computer Engineering
ISBN:
9781337093422
Author:
Joy L. Starks, Philip J. Pratt, Mary Z. Last
Publisher:
Cengage Learning
Prelude to Programming
Computer Engineering
ISBN:
9780133750423
Author:
VENIT, Stewart
Publisher:
Pearson Education
Sc Business Data Communications and Networking, T…
Computer Engineering
ISBN:
9781119368830
Author:
FITZGERALD
Publisher:
WILEY