1) What is the time complexity of the function 1 point
fun given above?
l int fun (int n)
2 {
3 int count = O;
4 int i . j ;
S for ( i = O; i < n ;i ++)
6 {
7 j "' l;
8 while (j < n)
9 {
10 count .., l;
11 j ; j * 2;
12 }
13 }
14 return count;
15 }
0
0(1)
0
O(n)
0
O(n log n)
0
O(n 2 )
2) Consider the problem Reversort discussed 1 point
in the lecture. What would be the minimum and
maximum size of the input array possible for Cost 44?
0 Minimum = 8, Maximum = 44
0 Minimum = 8, Maximum = 45
0 Minimum = 9, Maximum = 45
0 Minimum = 9, Maximum = 44
3) Consider the problem Reversort discussed in the
lecture. What cost will be added in the third iteration if
the input array is [2, 4, 6, 8, 9, 7, 5, 3Jll ?
l 1 point
4) Consider the problem Reversort discussed 1 point
in the lecture. For which of the following input array of
size N = 8, Cost C is 20?
9 [2, 8, 3, 5, 1, 6, 4, 7]
D [1, 3, 5, 7, 8, 6, 4, 2]
9 [1, 7, 2, 5, 3, 8, 6, 4]
9 [5, 3, 7, 1, 2, 6, 4, 8]
D [2, 4, 6, 8, 7, 5, 3, 1]
5) Consider the problem Number Game 1 point
discussed in the lecture. Suppose now it's Arya's turn.
Which of the following is/are the winning position for
Arya?
9 A= 1, B = 26
9 A= 4, B = 16
DA= 5, B = 5
DA= 21, B = 13
■ A= 14, B = 8
Common Statement for Question 6 and 7
Consider the code given in the lecture "Will It Stop?". If
+
we replace the term 3n 3 with 3n 1, then the code +
will look like below:
1 whi l e ( n > 1)
2 {
3 if (n ~ 2 =-- 0)
4 {
s n == n/ 2;
6 }
7 else
8 {
9 n a 3 • n + 1;
10 }
11 }
6) If n = 48, how many iterations will the while loop in
the above code execute (i.e., for how many iterations will
n be greater than 1)?
]
1 point
7) Which of the following options is correct? 1 point
Consider that 1 <n< 103 ?
0
If n is odd, then the code will never stop.
0
If n is even, then the code will never stop.
0
It wi II stop for all values of n .
0
It will never stop for all values of n .
8) The game Race of 50 proceeds as follows. 1 point
There are two players, A and 8. The player A starts by
picking a number between 1 and 5 (inclusive).
The players take turns, one by one. On each turn, the
current player has to add a number between 1
and 5 to the current number. Neither player is allowed to
pass. The player who reaches 50 first, wins
the game.
If player A starts with 1 then which of the following will be
the winning strategy for the 8 player?
0 If player B always says a multiple of 5
0 If player 8 always adds 5 to the current number
0 If the player always adds 4 to the current number
0 If player 8 always says a multiple of 6
9) Consider a two-player coin game where 1 point
each Player A and Player B get the turn one by one and
neither player is allowed to pass.
0
l 2 3 4 n
There is a row of n number of places(1,2 ... n), where n is
even, and each place contains a coin with
some value and the sum of all coin's values is odd. A
player on his/her turn can pick a coin from any of
the two corners of the row. The player that collects coins
with more value wins the game.
If player ~ starts the game, which of the following is a
winning strategy for player A?
0 Always select from the corner which has the
maximum among both corners.
0 If (sum of all even-placed coin value> sum of all
odd-placed coin value), always select from the right-
hand corner, otherwise always select from the left-
hand corner.
0 If (sum of all even-placed coin value > sum of all
odd-placed coin value), always select from the
lefthand corner, otherwise always select from the
right-hand corner.
0 If (sum of all even-placed coin value> sum of all
odd-placed coin value), start choosing from the
right-hand corner and select all the even-placed
coins, otherwise start choosing from the left-hand
corner and select all the odd-placed coins.
0 If (sum of all even placed coin value > sum of all
odd-placed coin value), start choosing from th.
hand corner and select all the odd-placed coi
otherwise start choosing from the right-hand c
and select all the even-placed coins.
Common Statement for Question 10 and 11
Given a wooden piece, a grid containing n rows and m
columns, each 1 x 1 square containing O written inside it.
You can cut the original or any other rectangular piece
obtained during the cutting into two new pieces along
the grid lines. You will obtain a certain number of
rectangle pieces after doing the cutting. 1 x 1 is a
square, you cannot treat it as a rectangle.
Your task is to design each rectangular piece obtained in
such a way that any pair of adjacent cells have different
symbols. What would be the minimum number of cells
you need to put an X on in an n x m grid to achieve the
desired result?
Symbols : 0 and X
Example:- For n = 2 and m = 4, minimum number of
change O to X is 3.
01X [o
n• l
Iobol odoI
• Q Q Q Q ~
..
Minimum 3 X
m == 4
1O)What would be the minimum number of cells you
need to put an X on in a 6 x 3 grid to achieve the desired
result?
[..___
a _ _ _]
1 point
11 )What would be the minimum number of cells you
need to put an X on in a 4 x 7 grid to achieve the desired
result?
