Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asterisks ($$) : def randomizedSmiles (A): n = len(A) if n ≤ 1: print ":)" return for i in {0,...,n-1}: print "" Choose a uniformly random integer p in {1, \ldots, n-1} randomizedSmiles(A[:p]) randomizedSmiles (A[p:]) For the following parts, choose the tightest big-Oh bound that applies. Based on the above data, answer the given subquestions. Figure from the original question paper

(C) Option figure from the original question paper

(A) Option figure from the original question paper

(B) Option figure from the original question paper

(D) Option figure from the original question paper

(E) Option figure from the original question paper

Advanced Algorithms · End Term · 3 Sept 2023 · May 2023 term · Set QPE1-S1

Question 28: Consider the followed randomized algorithm, which prints…

Question 28

+3 marksOne correct option

Consider the followed randomized algorithm, which prints out some number of smiley faces (:)) and some number of asterisks ( $*$ ) :

python

1def randomizedSmiles (A):
2        n = len(A)
3        if n ≤ 1:
4                print ":)"
5                return
6        for i in {0,...,n-1}:
7                print "*"
8        Choose a uniformly random integer p in {1, \ldots, n-1}
9        randomizedSmiles(A[:p])
10        randomizedSmiles (A[p:])

For the following parts, choose the tightest big-Oh bound that applies.

Based on the above data, answer the given subquestions.

Show answer

Correct answer

See the whole paper Take it as a mock test

Question 28 of 34 in the IIT Madras BS Advanced Algorithms (Advanced Algorithms) End Term paper sat on 3 Sept 2023, in the May 2023 term (IIT M DEGREE ET1 EXAM QPE1 S2 03 Sep). It carries 3 marks.

Question 28: Consider the followed randomized algorithm, which prints…

Question 28

More questions from this paper