Again, we skip the proof of correctness of this algorithm. (d) What is the worst-case running time of Find-Index-2(A[1 : n)? What about its worst-case expected running time? Remember to prove your answer formally.
Again, we skip the proof of correctness of this algorithm. (d) What is the worst-case running time of Find-Index-2(A[1 : n)? What about its worst-case expected running time? Remember to prove your answer formally.
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
![Again, we skip the proof of correctness of this algorithm.
(d) What is the worst-case running time of Find-Index-2(A[1 n])? What about its worst-case
expected running time? Remember to prove your answer formally.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Ff26fda3f-4323-495f-b28b-f131dcfa5992%2Fff58d872-b400-42b1-8ba4-8f801019e3ae%2Fjwfpof_processed.jpeg&w=3840&q=75)
Transcribed Image Text:Again, we skip the proof of correctness of this algorithm.
(d) What is the worst-case running time of Find-Index-2(A[1 n])? What about its worst-case
expected running time? Remember to prove your answer formally.
![Problem 2. Suppose we have an array A[1 : n] which consists of numbers {1,...,n} written in some
arbitrary order (this means that A is a permutation of the set {1,...,n}). Our goal in this problem is to
design a very fast randomized algorithm that can find an index i in this array such that A[i] mod 8 € {1,2},
i.e., the reminder of dividing A[i] by 8 is either 1 or 2. For simplicity, in the following, we assume that n
itself is a multiple of 8 and is at least 8 (so a correct answer always exist).
For instance, if n = 8 and the array is A = [8,7, 2,5, 4, 6,3, 1], we want to output either of indices 3 or 8.
(a) Suppose we sample an index i from {1,...,n} uniformly at random. What is the probability that i is
a correct answer, i.e., A[i] mod 8 E {1,2}?
(b) Suppose we sample m indices from {1,...,n} uniformly at random and with repetition. What is the
probability that none of these indices is a correct answer?
Now, consider the following simple algorithm for this problem:
Find-Index-1(A[1: n]):
• Let i = 1. While A[i] mod 8 ¢ {1,2}, sample i e {1,...,n} uniformly at random. Output i.
The proof of correctness of this algorithm is straightforward and we skip it in this question.
(c) What is the worse-case expected running time of Find-Index-1(A[1 : n])? Remember to prove your
answer formally.
The problem with Find-Index-1 is that in the worst-case (and not in expectation), it may actually never
terminate! For this reason, let us consider a simple modification to this algorithm as follows.
Find-Index-2(A[1 : n]):
• For j = 1 to n:
- Sample i e {1,...,n} uniformly at random and if A[i] mod 8 € {1,2}, output i and terminate;
otherwise, continue.
• If the for-loop never terminated, go over the array A one element at a time to find an index i with A[i]
mod 8 € {1,2} and output it as the answer.
Again, we skip the proof of correctness of this algorithm.](/v2/_next/image?url=https%3A%2F%2Fcontent.bartleby.com%2Fqna-images%2Fquestion%2Ff26fda3f-4323-495f-b28b-f131dcfa5992%2Fff58d872-b400-42b1-8ba4-8f801019e3ae%2Fb9yfks8_processed.jpeg&w=3840&q=75)
Transcribed Image Text:Problem 2. Suppose we have an array A[1 : n] which consists of numbers {1,...,n} written in some
arbitrary order (this means that A is a permutation of the set {1,...,n}). Our goal in this problem is to
design a very fast randomized algorithm that can find an index i in this array such that A[i] mod 8 € {1,2},
i.e., the reminder of dividing A[i] by 8 is either 1 or 2. For simplicity, in the following, we assume that n
itself is a multiple of 8 and is at least 8 (so a correct answer always exist).
For instance, if n = 8 and the array is A = [8,7, 2,5, 4, 6,3, 1], we want to output either of indices 3 or 8.
(a) Suppose we sample an index i from {1,...,n} uniformly at random. What is the probability that i is
a correct answer, i.e., A[i] mod 8 E {1,2}?
(b) Suppose we sample m indices from {1,...,n} uniformly at random and with repetition. What is the
probability that none of these indices is a correct answer?
Now, consider the following simple algorithm for this problem:
Find-Index-1(A[1: n]):
• Let i = 1. While A[i] mod 8 ¢ {1,2}, sample i e {1,...,n} uniformly at random. Output i.
The proof of correctness of this algorithm is straightforward and we skip it in this question.
(c) What is the worse-case expected running time of Find-Index-1(A[1 : n])? Remember to prove your
answer formally.
The problem with Find-Index-1 is that in the worst-case (and not in expectation), it may actually never
terminate! For this reason, let us consider a simple modification to this algorithm as follows.
Find-Index-2(A[1 : n]):
• For j = 1 to n:
- Sample i e {1,...,n} uniformly at random and if A[i] mod 8 € {1,2}, output i and terminate;
otherwise, continue.
• If the for-loop never terminated, go over the array A one element at a time to find an index i with A[i]
mod 8 € {1,2} and output it as the answer.
Again, we skip the proof of correctness of this algorithm.
Expert Solution
This question has been solved!
Explore an expertly crafted, step-by-step solution for a thorough understanding of key concepts.
This is a popular solution!
Trending now
This is a popular solution!
Step by step
Solved in 2 steps
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