WEEK 9-10

SOLUTION
• CT
• MATHS 1
• STATS 1
FOR MORE SUCH
DOCUMENTS
JOIN OUR GROUP
CLICK HERE

BY-DARK LUCIFER
Week-9, Graded Solution
Week-9, Graded Solution
Question-(1 to 2) [4 Marks]
Statement
Question-1 [2 Marks]
Statement
Options
(a)
(b)
(c)
(d)
Answer
Solution
Question-2 [2 Marks]
Statement
Options
(a)
(b)
(c)
(d)
(e)
Answer
Solution
Question-3 [2 Marks]
Statement
Options
(a)
(b)
(c)
(d)
Answer
Solution
Question-(4 to 11) [8 Marks]
Statement
Question-4 [1 Mark]
Statement
Answer
Question-5 [1 Mark]
Statement
Answer
Solution
Question-6 [1 Mark]
Statement
Answer
Question-7 [1 Mark]
Statement
Answer
Solution
Question-8 [1 Mark]
Statement
Answer
 Question-9 [1 Mark]
Statement
Answer
Solution
Question-10 [1 Mark]
Statement
Answer
Question-11 [1 Mark]
Statement
Answer
Solution
Question-12 [4 Marks]
Statement
Options
(a)
(b)
(c)
(d)
(e)
Answer
Solution
Question-13 [3 Marks]
Statement
Options
(a)
(b)
(c)
(d)
Answer
Solution
Question-14[4 Marks]
Statement
Options
(a)
(b)
(c)
(d)
Answer
Solution

Question-(1 to 2) [4 Marks]
Statement
Consider a graph generated from the "Scores" table that is represented by a matrix B. Each node
in the graph corresponds to a student from the table. SeqNo is used to label the nodes in the
graph. Study the given pseudocode and answer the following questions.

1 A = {}
2 while(Table 1 has more rows){
3 Read the first row X in Table 1
4 A[X.SeqNo] = [X.CityTown, X.Gender]
5 Move X to Table 2
 6 }
7 n = length(keys(A))
8 B = createMatrix(n, n)
9 foreach i in keys(A){
10 foreach j in keys(A){
11 if(i != j and isRelated(A[i], A[j])){
12 B[i][j] = 1
13 }
14 }
15 }
16
17 Procedure isRelated(x, y)
18 if(first(x) == first(y) and last(x) == last(y)){
19 return(True)
20 }
21 else{
22 return(False)
23 }
24 End isRelated

Question-1 [2 Marks]
Statement
There is an edge between students i and j, with i j, if and only if:

Options
(a)

they are from the same city/town

(b)

they have the same gender

(c)

they are from the same city/town and have the same gender

(d)

they are from the same city/town or have the same gender

Answer
(c)

Solution
From the above pseudocode, we notice that there is an edge between i and j if and only if the
procedure isRelated(A[i], A[j]) returns True. isRelated(A[i], A[j]) will return the value True, when i
and j have the same gender and are from the same city/town. To see why this is true, consider the
procedure's definition.
We are passing two lists to isRelated. x will have [CityTown, Gender] of some row in the table,
likewise y will have [CityTown, Gender] of some other row in the table. We make sure that we do
not pass the same row, thanks to the condition i j in the if condition that is present inside the
nested foreach. The procedure returns True only if both the following conditions are satisfied:

CityTown of both rows are the same

The Gender of both rows are the same
Question-2 [2 Marks]
Statement
Which of the following statements are true about this graph? It is a Multiple Select Question
(MSQ).

Options
(a)

There are two cliques in this graph, one for each gender

(b)

In every clique, there is at least a pair of students having different genders

(c)

All students in a given clique have the same gender

(d)

All students in a given clique are from the same city/town

(e)

There are no cliques in this graph

Answer
(c), (d)

Solution
We will go through option by option.
First option: This option is incorrect because there can be more than two cliques. Each
CityTown-Gender combination will have a clique associated with it. For example, Chennai-
male, Chennai-female, Madurai-male, Madurai- female, all represent separate cliques.
Second option: This option is incorrect. There cannot be two nodes with different genders in
a clique for this particular graph. This is because, there is an edge between two nodes in this
graph only if they have the same gender and are from the same city/town.
Third and fourth option: The gender of all nodes in a given clique will be the same. Likewise,
the city/town of all nodes in a given clique will be the same. This is because of the way we
dene the graph's connections.
Fifth option: From above arguments there will be some cliques. So this is an incorrect option.
Question-3 [2 Marks]
Statement
The following table contains information regarding books in a library. Each row in the table
corresponds to a book and is authored by exactly two authors, with equal contributions from
both. There is a pool of n authors, each author being assigned a unique index between 0 and
. There are M books in total.

S.No Author-1 Author-2

0 4 0

... ... ...

5 33

The table is represented by a dictionary named books, with the keys as serial numbers and values
as the corresponding list of authors. Assume that books has already been computed. For
example, we have:

books[0] = [4, 0]

A graph G is generated from this table. Each node corresponds to an author. There is an edge
between authors i and j if and only if they have collaborated on a book. Given a pair of authors (i,
j), with i j, what does the value colab[i] [j] represent at the end of execution of the following
pseudocode? Assume that the number of authors, n, is given to you.

Options
(a)

It represents the number of books published by authors i or j

(b)

It represents the number of books in which authors i and j have collaborated

(c)

It represents the number of books published by author i + number of books published by author j
(d)

It represents the number of books published by author i in which he has not collaborated with
author j

Answer
(b)

Solution
colab[i] [j] represents the number of books published together by authors i and j. This is the
same as saying that it represents the number of books in which i and j have collaborated. How do
we arrive at this answer?

Each key in the dictionary corresponds to a book. In the foreach loop, we pick up a book from the
dictionary books. Let us say that the key is i. books[i] corresponds to a list of authors who have
collaborated on that book. We unpack the list of authors into auth1 and auth2.

Usually, when there is an edge between two nodes i and j in a graph, we update the
corresponding matrix, say A, by setting A[i] [j] = 1. Here, we are doing it differently. The matrix
colab keeps track of edges and also the labels associated with it. In this case, the edge-label is
defined by how frequently two authors have collaborated.

So, if colab[auth1] [auth2] is zero, then the two authors have never collaborated. If colab[auth1]
[auth2] is 5, then the two authors have written five books together. This is exactly what the
foreach loop tries to do. Whenever it sees a book written by a list of authors, it increments the
corresponding cell in the matrix by 1.
Question-(4 to 11) [8 Marks]
Statement
Using the matrix colab computed from the previous problem, answer the following questions. For
each question, what do the variables aVar and bVar represent at the end of execution of the
pseudocode? Pick the correct option from the table given below.

Answer Option

Maximum number of collaborators among all authors 1

An author with the maximum number of publications 2

A pair of authors who have collaborated most often 3

An author who has the maximum number of collaborators 4

Maximum number of books published by any pair of authors 5

The list of authors who have just one collaborator 6

Number of authors who have exactly one collaborator 7

Maximum number of books published by any author 8

Question-4 [1 Mark]
Statement

What is the correct option for variable aVar?

Answer
5

Question-5 [1 Mark]
Statement
What is the correct option for variable bVar?

Answer
3

Solution
Here, the if-block is something we are all familiar with. It is trying to nd the maximum value
among some numbers and storing the result in aVar. A closer look at the code tell us that we are
trying to nd the maximum value in the matrix colab and storing the result in aVar. The row-col
corresponding to this maximum value is stored in bVar as a list.

We can interpret it in the following way. aVar is the maximum number of books published by any
pair of authors. bVar is nothing but a pair of authors who have collaborated most often. This is
the same as saying a pair of authors who have published the most number of books together.

Question-6 [1 Mark]
Statement

What is the correct option for variable aVar?

Answer
1

Question-7 [1 Mark]
Statement
What is the correct option for variable bVar?
Answer
4

Solution
In this part, count is being initialised to zero every time at the beginning of the outer loop. Now,
for a given author r, the inner foreach goes through each author c. If r has collaborated with c,
count is incremented by 1. So, count is keeping track of the number of collaborators of author r.

The if-block is trying to nd the maximum count. That is, it is trying to nd the maximum number of
collaborators among all authors. This result is stored in the variable aVar. The variable bVar
stores an author who has the maximum number of collaborators. Note that multiple authors may
have the same number of maximum collaborators, that is the reason we use the article "a"
instead of "the".

Question-8 [1 Mark]
Statement

What is the correct option for variable aVar?

Answer
8

Question-9 [1 Mark]
Statement
What is the correct option for variable bVar?

Answer
2
Solution
There are many similarities between this question and the earlier question. Here again, count is
initialized to zero at the beginning of the first foreach loop. For every author r, the inner foreach is
counting the number of books published by r.

aVar holds the maximum number of books published by any author. bVar holds an author who
has published the maximum number of books.

Question-10 [1 Mark]
Statement

What is the correct option for variable aVar?

Answer
7

Question-11 [1 Mark]
Statement
What is the correct option for variable bVar?

Answer
6

Solution
This is similar to questions 6 & 7 where we counted the number of collaborators for an author r.
Here again, the inner foreach is doing exactly that. But we are not finding any maximum value
here. Instead, we are counting the number of authors who have exactly one collaborator. This
result is stored in the variable aVar. The variable bVar is a list of authors who have exactly one
collaborator.
Question-12 [4 Marks]
Statement
Continuing with the previous question, authors is a list of authors. isClique is a procedure that
determines if every pair of authors in this list have collaborated at least once. It returns False if at
least one pair of authors haven't collaborated, and True if every pair of authors have collaborated
at least once. Select the correct code fragment to complete the pseudocode. It is a Multiple Select
Question (MSQ).

*********************

return(True)
10

Options
(a)

(b)

(c)

(d)
(e)

Answer
(b), (d)

Solution
We want to return True if every pair of authors have collaborated at least once. This is the same
as saying that the procedure must return True if the given list of authors forms a clique. That is
why the procedure has also been named that way.

So, given a pair of authors i and j in the list, if there is no edge between them, then they haven't
collaborated, so we must return False. This is the basic idea behind the solution.

Why do we have the i j? This is needed because, when we do the nested foreach, we will come
up with pairs of the form (i, j) where i = j. In such cases, colab[i] [j] = 0. We don't want to return
False in such cases. We want to return False only if two different authors are not connected by an
edge.

The other correct answer is just a nested variant of the above if-condition.
Question-13 [3 Marks]
Statement
A computer scientist is planning to conduct an event in the city. She has come up with a novel
scheme to invite people:

The host (computer scientist) can send out any number of invitations and does not accept any
invitation.

Each invitation is represented by a unique text message.

Each invitee can choose to either accept or reject the invitation.
If an invitee accepts the invitation, then he can invite exactly one other person by forwarding
the invitation that he received to this person, i.e., the invitee can forward the message he
received only once.
If an invitee doesn't accept the invitation, he cannot invite anyone.
If a person receives multiple invitations, he can accept at most one of them. All other
invitations must be rejected.

This situation is modeled as a graph. There is a node corresponding to every person who attends
the event. n people attend the event and the attendees are indexed from 0 to . Given a pair
of attendees (i, j), there is an edge from i to j if and only if the following conditions are satisfied:

j was invited by i
j accepted i's invitation

The graph is represented by a matrix A, such that A[i] [j] = 1 if and only if there is an edge from i
to j.

For the case of n = 5, which of the following is a possible representation of the graph?

Options
(a)

(b)
(c)

(d)

Answer
(c)
Solution
Option (a): In this graph, node 3 is the host since she is not receiving any invitations and is
inviting more than one people. When we traverse the graph we see that node 0 is accepting
more than one invitation which is against the scheme implemented by the host. Therefore
this graph is incorrect.
Option (b): In this graph, node 0 or node 3 could be the host, whereas we can have only have
one host. Few other problems with this graph: node 1 is inviting more than one person and
accepting an invitation from 0, which cannot be the case. Second, node 4 is accepting more
than one invitation, which is again not possible. Therefore due to above explained reasons,
option b is incorrect.
Option (c): In this graph, node 3 is the host since she has invited 0 and 4. None of the nodes
or edges violate any of the conditions. So this is the correct answer.
Option (d): In this graph, there is no host. This is because, every node has an incoming edge.
The host should have no incoming edges. So this graph is incorrect.

Question-14[4 Marks]
Statement
Continuing with the previous question, for a pair of attendees (i, j) other than the host, we say
that i is the ancestor of j, if their messages are identical and i has accepted the invitation before j.
Note that each invitation sent out by the host is a unique text message. Assume that the matrix A
that represents the graph has already been computed.

isAncestor is a procedure that accepts the matrix A and two attendees i and j other than the host
as input, with i j, and returns True if i is the ancestor of j, and False otherwise. Select the
correct code fragment to complete the pseudocode.

while(flag){

*********************

*********************
10
11
12 return(False)
13

Options
(a)

(b)

(c)

(d)

Answer
(d)
Solution
The basic idea behind this solution is that i is an ancestor of j if we can start from i in the
graph and reach j by moving along the edges.
Since i is not the host, there will be at most one outgoing edge from i.
In the procedure isAncestor, k is initially set to i and flag is initialized to True. Next, the code
inside the while loop will be executed since flag is True. The value of flag is updated to False
immediately after entering the loop. Next, in the foreach loop, we are going to check for all
the outgoing edges for k.
In every step of the foreach, we are checking if there is an edge from k to c. If there is an
edge, we check whether c is equal to j or not. If c is equal to j, it returns True. So far so good.
Now if c is not equal to j then, we update k to c. This means that we continue our journey of
traversing the graph by moving on to the next node. Since, we are not yet done walking
along the edges, we update flag to True and then exit the loop.
In subsequent iterations, we keep looking at the outgoing edges of k and keep traveling
along them until we hit node j.
If we never find j, then i is not the ancestor of j, so we return False at the end.
1. A discrete random variable X can take the values 1, 2, 3, · · · , n. For these values the
cumulative distribution 2function is defined by:
x +k
F (x) = P (X ≤ x) =
m ; x = 1, 2, 3, · · · , n
Find the value of k.
Answer: k = m − n2
Solution:
F (n) = P (X ≤ n) = 1
n2 + k
=⇒ =1
m
Hence, k = m − n2
Suppose, we substitute values of n and m as 3 and 40 respectively, then
32 + k
=1
40
k = 31

2. An organization in Texas organizes a lucky draw this month. n thousand tickets are
sold for m$ each. Each has an equal chance of winning. x tickets will win a$, y tickets
will win b$ and z tickets will win c$. Let, the random variable X denote the net gain
from purchase of one ticket. What is the probability that X takes a value less than b?
(Enter the answer correct to 4 decimal place)
n × 1000 − x
Answer:
n × 1000
Solution:
X can take values −m, c − m, b − m and a − m
P (X < b) = P (X = b − m) + P (X = c − m) + P (X = −m)
y z n × 1000 − x − y − z
P (X < b) = + +
n × 1000 n × 1000 n × 1000
n × 1000 − x
P (X < b) =
n × 1000
Suppose, we substitute values of n, m, x, a, y, b, z and c as 5, 1, 1, 1000, 2 500,
10 and 100 respectively, then
2 10
P (X < 500) = P (X = 499) + P (X = 99) + P (X = −1) = + + 4987
4999 5000 5000 5000
Therefore, P (X < 500) = = 0.9998
5000

1
3. In a group of n people, x are photographers and n − x are journalists. m people are
randomly picked from a group of these n people. Let, Y be a random variable which
represents the number of photographers. How many possible values can the random
variable Y take?
Answer: m + 1
Solution:
Possible values of Y are 0, 1, 2, ..., m.
Hence, the number of possible values Y can take is m + 1.
Suppose, we substitute values of m, x and n as 8, 240 and 15 respectively, then
possible values of Y are 0, 1, 2, ..., 8
Hence, the number of possible values Y can take is 9.

4. Which of the following is/are discrete random variables?

a. Number of tires produced in an automotive tire factory every 30 minutes.

b. The number of kernels(pieces) of popcorn in a 1 kg container.
c. The time between customers entering a checkout lane at a retail store.
d. The amount of rain recorded at an airport one day.
e. The amount of liquid in a 2 litres bottle of soft drink.
f. The number of no-shows for every 1000 reservations made with a commercial airline.

Answer: a, b, f
Solution:
The number of tires produced in an automotive tire factory every 30 minutes can have
countable possible values, and hence it denotes a discrete random variable.
Hence, option (a) is correct.

The number of kernels of popcorn in a 1 kg container also have countable possible val-
ues, it cannot take all values between some interval and hence it is a discrete random
variable. So option (b) is correct.

The time between customers entering a checkout lane at a retail store can take any
values between some interval. Hence, it is a continuous random variable.
So, option (c) is incorrect.

Again, the amount of rain recorded at an airport one day and the amount of liquid in
a 2 litres bottle of soft drink can take any values between some interval. Hence, they
are continuous random variable.
So, option (d) and (e) are incorrect.

2
 The number of no-shows for every 1000 reservations made with a commercial airline
can have countable possible values, and hence it denotes a discrete random variable.
Hence, option (f) is correct.

5. A biased coin with probability of heads 0.75 is tossed three times. Let X be a random
variable that represents the number of head runs, a head run being defined as a con-
secutive occurrence of at least two heads. Then the probability mass function of X is
given by:
(
a. 0.375
P (X = x) = for x = 0
0.625 for x = 1
(
b. 0.297
P (X = x) = for x = 0
0.703 for x = 1
c.
0.016 for x = 0
0.140 for x = 1
P (X = x) =
0.422 for x = 2
0.422 for x = 3

d.
0.016 for x = 0
P (X = x) = 0.844 for x = 1
0.140 for x = 2

Answer: b
Solution:

Possible outcomes X P (X = x)
HHH 1 0.422
HHT 1 0.141
HTH 0 0.141
HTT 0 0.047
THH 1 0.141
THT 0 0.047
TTH 0 0.047
TTT 0 0.016

Table 9.1

3
 Hence, the probability mass function of X is given by:
(
0.297 for x = 0
P (X = x) =
0.703 for x = 1

6. Nina has n music sessions in a week. She attends the sessions n days a week x% of
the time, n − 1 days y% of the time, one day z% of the time, and no days p% of the
time. Let, X be a discrete random variable representing the number of sessions she
attends in a week. Suppose one week is randomly selected, what is the probability that
the random variable X takes the value at most n − 1?(Enter the answer correct to 2
decimal places)
x
Answer: 1 −
100
Solution:
The pmf of random variable X is given by:
x
for k = n
100
y
for k = n − 1
100
P (X = k) =
z
for k = 1
100

p
for k = 0
100

P (X ≤ n − 1) = P (X = 0) + P (X = 1) + P (X = n − 1)
p z
= + + y
100 100 100
p+y +z
=
100
x
= 1−
100

Suppose, we substitute values of n, x, y, z and p as 5, 50, 20, 10 and 20 respectively,

then
The pmf of random variable X is given by:

0.5 for k=5

0.2 for k=4
P (X = k) = 0.1 for k=1
0.2 for k=0

4
 P (X ≤ 4) = P (X = 0) + P (X = 1) + P (X = 4)
= 0.2 + 0.1 + 0.2
= 0.5

m x
7. Find the value of k for which k ( x = 0, 1, 2, ...) is a pmf. (Enter the answer
n
correct up to 2 decimal places)
n−m
Answer:
Solution: n
m 0 m 1 m 2
For pmf: k + + + ··· = 1
n n n
1
=⇒ k. = 1
m
1−
n
n
=⇒ k. =1
n−m
n−m
Therefore, k = .
n
For example: " #
0 1 2
3 3 3
Take m = 3 and n = 8. For pmf: k + + +··· = 1
8 8 8
1
=⇒ k. =1
3
1−
8
8
=⇒ k. = 1
5
5
Therefore, k = .
8

8. Using the information in the previous question, calculate P (X = 2). (Enter the answer
correct up to 2 decimal places)
(n − m) m 2
Answer: .
n n
Solution:
(n − m) m 2
P (X = 2) = . .
n n
For example: " #
0 1 2
3 3 3
Take m = 3 and n = 8. For pmf: k + + +··· = 1
8 8 8

5
 1
=⇒ k. = 1
3
1−
8
8
=⇒ k. = 1
5
5
Therefore, k = .
8 2
5 3
And, P (X = 2) = . = 0.09.
8 8

9. From a box A containing 3 white and 6 black balls, 5 balls are transferred into an
empty box B. Let X be a random variable that represents the number of white balls
which are transferred from A to B. What value of random variable will have the least
probability?
Answer: 0
Solution:
Let us define the following cases:
Transfer of 0 white and 5 black balls.
Transfer of 1 white and 4 black balls.
Transfer of 2 white and 3 black balls.
Transfer of 3 white and 2 black balls.
Probabilities for all cases:
6
C5
(i) P (X = 0) = 9 = 0.048
C5
3
C1 6C4
(ii) P (X = 1) = 9 = 0.357
C5
3
C2 6C3
(iii) P (X = 2) = 9 = 0.476
C5
3
C3 6C2
(iv) P (X = 3) = 9C = 0.119
5
.
Thus, X = 0 has the least probability.

10. The probability mass function of a random variable X is given by:

3k2 − 3k for x = 0
P (X = x) = 2k2 − 1 for x = 1
0 otherwise

Determine the value of k given k > 0.

Answer:1
Solution:

6
From properties of pmf,

p(0) + p(1) = 1
3k 2 − 3k + 2k 2 − 1 = 1
5k2 − 3k − 2 = 0
5k2 − 5k + 2k − 2 = 0
5k(k − 1) + 2(k − 1) = 0
(5k + 2)(k − 1) = 0
−2
k= or k = 1
5
As k > 0, therefore k = 1.

7
Week-10, Graded Assignment Solution
Week-10, Graded Assignment Solution
Question (1-4)
Statement
Question-1 [5 Marks]
Statement
Options
(a)
(b)
(c)
(d)
Solution
Question (2) [5 Marks]
Statement
Options
(a)
(b)
(c)
(d)
(e)
Solution
Question 3 [5 Marks]
Statement
Options
(a)
(b)
(c)
(d)
(e)
Solution
Question 4 [4 Marks]
Statement
Options
(a)
(b)
(c)
(d)
Solution
Question (5-8)
Statement
Question 5 [5 Marks]
Statement
Options
(a)
(b)
(c)
(d)
Solution
Question (6) [5 Marks]
Statement
Options
 (a)
(b)
(c)
(d)
Solution
Question (7) [5 Marks]
Statement
Options
(a)
(b)
(c)
(d)
Solution
Question (8) [5 Marks]
Statement
Options
(a)
(b)
(c)
(d)
Solution
Question (9-10)
Statement
Explanation
Question 9 [5 Marks]
Statement
Options
(a)
(b)
(c)
(d)
Answer
Solution
Question (10) [5 Marks]
Statement
Options
(a)
(b)
(c)
(d)
Answer
Solution

Question (1-4)
Statement
The following pseudocode is executing using the “Scores” table. At the end of the execution,
matrix represents the adjacency matrix of the graph generated from the “Scores” table.

1 D = {}
2 while(Table 1 has more rows){
3 Read the first row X in Table 1
 4 D[X.SeqNo] = {"P": X.Physics, "C": X.Chemistry, "M": X.Mathematics}
5 Move X to Table 2
6 }
7
8 matrixPh = getAdjMatrix(D, "P")
9 matrixCh = getAdjMatrix(D, "C")
10 matrixMa = getAdjMatrix(D, "M")
11
12 Procedure getAdjMatrix(D, Subject)
13 n = length(keys(D))
14 matrix = createMatrix(n, n)
15 foreach i in rows(matrix){
16 foreach j in columns(matrix){
17 if(i != j){
18 diff = D[i][Subject] - D[j][Subject]
19 if(10 <= diff and diff <= 20){
20 matrix[i][j] = 1
21 }
22 }
23 }
24 }
25 return(matrix)
26 End getAdjMatrix

Question-1 [5 Marks]
Statement
If matrixPh[i][j] = 1, then

Options
(a)

i scored at most 10 and at least 20 more marks in Physics than j

(b)

i scored at least 10 and at most 20 more marks in Physics than j

(c)

j scored at least 10 and at most 20 more marks in Physics than i

(d)

j scored at most 10 and at least 20 more marks in Physics than i

Solution
Consider the procedure getAdjMatrix. For each pair of keys i and j in D, matrix[i] [j] is initialized
with value 0 using the createMatrix procedure. For each pair of values i and j with i 6 = j, D[i]
[Subject] - D[j] [Subject] is stored in diff . If diff is at least 10 and at most 20 then an edge is
added from i to j in the graph by setting the corresponding cell with value 1. Therefore, matrix[i]
[j] is set to 1 if i scored at most 10 and at least 20 more marks than j in the subject which is
passed as the second parameter. matrixPh is constructed based on the Physics marks of the
students. Therefore, i scored at least 10 and at most 20 more marks in Physics than j.

Therefore, the correct option is (b).

Question (2) [5 Marks]
Statement
Choose the correct statement based on above pseudocode.

Options
(a)

For all i, j with i j, matrixPh[i][j] + matrixPh[j][i] = 1

(b)

For all i, j with i j, if matrixPh[i][j] = 1 then matrixPh[j][i] = 0

(c)

For all i, j with i j, if matrixPh[i][j] = 0 then matrixPh[j][i] = 1

(d)

For all i, j with i j, if matrixPh[i][j] = 1 then matrixPh[j][i] = 1

(e)

For all i, j with i j, if matrixPh[i][j] = 0 then matrixPh[j][i] = 0

Solution
Recall the construction of the matrix matrixPh. For each i and j with i j,

i scored at least 10 and at most 20 more marks in Physics than j.

(a) This is False because there can be a pair of students who scored with mark difference at least
21 (Say 90 and 60 marks in Physics) or at most 9 (say same marks in Physics). In this case, both
matrixPh[i][j] = 0 then matrixPh[j][i] = 0.

Therefore, matrixPh[i][j] + matrixPh[j][i] 1.

(b) Suppose matrixPh[j][i] = 1, then

D[j] [“P ”] + 10 ≤ D[i] [“P ”] ≤ D[j] [“P ”] + 20.

That is, D[j] [“P ”] < D[i] [“P ”]. Therefore, There will be no edge from j to i. Thus,

For all i, j with i j, if matrixPh[i][j] = 1 then matrixPh[j][i] = 0

(c) Consider the case that both i and j scored the same marks in Physics. Then, both matrixPh[i]
[j] = 0 and matrixPh[j][i] = 0. This is a counterexample to show that the option is False.

(d) We show that if matrixPh[i][j] = 1 then matrixPh[j][i] = 0. Therefore, this is the negation of the
True statement.

(e) Consider the case that i is scored 10 less than j in Physics. Then, there will be an
edge from j to ibut not from i to j. This is a counterexample for this option.

Therefore, the correct option is (b).

Question 3 [5 Marks]
Statement
Consider the dictionary D, and the matrices matrixPh, matrixCh and matrixMa computed in the
previous question. The following pseudocode generate the adjacency matrix matrixHelp.

Let i and j be indices of two students. Choose the correct statement(s) from the given options. It is
a Multiple Select Question (MSQ)

Options
(a)

0 <= matrixHelp[i][j] <= 3

(b)

matrixHelp[i][j] + matrixHelp[j][i] <= 3

(c)

matrixHelp[i][j] matrixHelp[j][i]

(d)

if matrixHelp[i][j] = 0, then matrixHelp[j][i]] = 3

(e)

if matrixHelp[i][j] = 3, then matrixHelp[j][i] = 0

Solution
Observe that the graph represented by the matrix matrix in the procedure getAdjMatrix shows
the help-relationship between the students on a specific subject. For all three subjects Physics,
Chemistry and Mathematics, we created three matrices matrixPh, matrixCh and matrixMa,
respectively. For each i and j, matrixHelp[i][j] is the sum of the corresponding cells in the three
matrices. Therefore, based on the definition of the edges, matrixHelp[i][j] denotes the number of
subjects that i can help j, where the mark difference is bounded between 10 and 20.

(a) Since there are exactly three subject, a student can help the other one in at most three
subjects. Therefore, the following statement is True:

0 <= matrixHelp[i] [j] <= 3

(b) For any subject Subject, either one of them can help to other or none of them can help each
other. Therefore, the following statement is True:

matrixHelp[i] [j] + matrixHelp[j] [i] <= 3

(c) Consider the following case: D[i] = {“P”: 60, “C”: 70, “M”: 80} and D[i] = {“P”: 70, “C”: 60, “M”: 80}. i
can help j in one subject (Physics). Similarly, j can help i in one subject (Chemistry). None of then
can help each other in Mathematics. That is matrixHelp[i] [j] = matrixHelp[i] [j] = 1. Therefore,
the following statement is False:

matrixHelp[i] [j] matrixHelp[j] [i]

(d) Consider the case that both i and j scored the same marks in all three subjects. Then,
matrixHelp[i] [j] = matrixHelp[i] [j] = 0. This is a counterexample for the following statement:

if matrixHelp[i] [j] = 0, then matrixHelp[j] [i] = 3

(e) Suppose i can help j in all three subjects, then i scored at least 10 and at most 20 more marks
than j in all three subjects. That is, j cannot help i in any subject. Therefore, the following
statement is True:

if matrixHelp[i] [j] = 3, then matrixHelp[j] [i] = 0

Therefore, the correct options are (a), (b) and (e).

Question 4 [4 Marks]
Statement
At the end of the following pseudocode, A captures the number of distinct pairs of students who
can help each other in at least one subject, and B captures the number of distinct pairs of
students where one can help the other in all subjects. Choose the correct code fragment to
complete the pseudocode.

***********************

Options
(a)

(b)

(c)
(d)

Solution
When to update A: if both i and j can help each other in at least one subject, then A shoul be
incremented by one. The following code fragment can do it. Observe

that the variable A will be incremented twice for each such pair i and j. To avoid the over
counting, we have to consider either i <= j, or j <= i.

When to update B: if both i can help j in all three subject, then B shoul be incremented by one.
The following code fragment can do it. By combining the above code fragments,

we get the suitable code as given in option (d) as follows:

Therefore, the correct option is (d).

Question (5-8)
Statement
The following table contains information regarding books in a library. Each entry in the table
corresponds to a book and is authored by at least two authors. There is a pool of n authors, each
author being assigned a unique index between 0 and n − 1. There are M books in total.

S.No. Authors List

0 [0, 2, 3]

... ...

M-1 [1, 5, 8, n-1]

The table is represented by a dictionary named books, with the keys as serial numbers and values
as the corresponding list of authors. Assume that books has already been computed. For
example, we have: books[0] = [0, 2, 3]. Consider the followig question.

Question 5 [5 Marks]
Statement
The following pseudocode generates a graph G from books. Each node corresponds to an author.
There is an edge between two different authors i and j if they have co-authored a book, and the
edge is labeled with the number of books they have co-authored. Choose the correct code
fragment to complete the following pseudocode.

***********************

***********************

10

Options
(a)
(b)

(c)

(d)

Solution
Our aim is to construct a graph where authors are denoted by vertices and the co-authoring
relationship is denoted by edges. For each book i, books[i] is the list of authors who co-authored
i. For each j and k in books[i], we have add the co-author relationship. Therefore,

Observe that if i and j are the same during the iteration, then we should skip the matrix update.
Therefore, the following code fragment completes the pseudocode:

Therefore, the correct option is (b).

Question (6) [5 Marks]
Statement
The following pseudocode creates adjacency matrix matrix2 of another graph H from books. For
two different authors i and j, what does the value matrix2[i] [j] represent at the end of the
execution?

Options
(a)

List of authors who have co-authored a book with both i and j

(b)

List of authors who have co-authored a book with either i or j

(c)

List of authors who have co-authored at least two book with both i and j

(d)

List of authors who have co-authored at least two book with either i or j

Solution
Note that the matrix matrix2 is indexed by pair of authors, and the cells are initialized with an
empty list. Therefore, each edge of the representing graph is labeled with a list. In the three levels
of iteration over books[i], j, k and h are denoting any three authors in the list. The following
condition,
captures that the three authors must be a distinct authors. The following condition

captures that the h should not exists in matrix2[j] [k]. Observe that all three authors are co-
authored the book i. Therefore, the matrix2[i] [j] captures the list of authors who have co-
authored a book with both j and k.

Therefore, the correct option is (a).

Question (7) [5 Marks]
Statement
Which of the following combinations of entries in matrix and matrix2 is possible for
two different authors i and j? It is Multiple Select Question (MSQ).

Options
(a)

matrix[i] [j] = 0 and matrix2[i] [j] = [ ]

(b)

matrix[i] [j] = 0 and matrix2[i] [j] []

(c)

matrix[i] [j] > 0 and matrix2[i] [j] = [ ]

(d)

matrix[i] [j] > 0 and matrix2[i] [j] []

Solution
Here we relate matrix and matrix2. The matrix captures the number of books co-authored by a
pair of authors whereas the matrix2 captures the number authors who have co-authored a book
with a pair of authors.

(a) If i and j have not co-authored any book then we will have

(b) If i and j have not co-authored any book then the common third co-authors list will be empty.
On the other hand, if the common third co-authors list is not empty then i and j have co-authored
at least one book. Therefore, the following combination is not possible:

(c) If i and j have co-authored with books where all such books are only co-authored by only i and
j.

(d) If i and j have co-authored with books where some books are co-authored at least
one more author other than i and j.

Therefore, the correct options are (a), (c) and (d).

Question (8) [5 Marks]
Statement
Consider the matrices matrix and matrix2 constructed in the previous questions.

findAuthor(matrix) finds an author who has the maximum number of co-authors. Choose the
correct implementation of the procedure findAuthor. It is a Multiple Select Question.

Options
(a)

(b)
(c)

(d)

Solution
We want to find an author who has the maximum number of co-authors. For any two authors i
and j, matrix[i] [j] stores the number of books co-authored by both i and j. The number of
authors who are co-authored a book with an i can be computed as follows:
We cans witch the role of i and j since the matrix is symmetric. Based on the pseudocodes in the
options, Max captures the maximum number of co-authors for any author, and A captures such
an author. For each customer i, Sum captures the number of shopping partners of i. Once Sum is
computed for i, we have to check i has more co-authors than the current maximum. By
combining all the above logic, we can obtain the following pseudocode:

As we mentioned above, the matrix, matrix is a symmetric matrix. That is,

Also note that the lists columns(matrix) and rows(matrix) are the same. Therefore, we can
obtain another equivalent pseudocode from the above.

Therefore, the correct options are (a) and (c).

Question (9-10)
Statement
The following pseudocode is executing using the "Shopping bills" dataset. Each customer is being
assigned a unique index between 0 and n − 1. Dictionary D has already been computed with keys
as index and values as list of distinct shops visited by the corresponding customer. Assume that
there exists a procedure intersection which takes two lists as input and outputs another list
which contains the common elements in the input lists.

Explanation
As the customers are indexed between 0 to n-1, i and j are the index number of two customers.
From Line 3 and line 4 it is cleared that each and every customer is being compared with each
other customer.

Line 5: i != j means if the customers are not same, then matrix[i][j] = intersection(D[i], D[j]). As D[i]
is the list of shops visited by customer i and D[j] is the list of shops visited by customer j.
intersection(D[i], D[j]) will return the list of the common elements between D[i] and D[j] which
means intersection(D[i], D[j]) returns the list of common shops visited by both the customers i
and j.

Therefore, whenever the different customers let us say i and j, matrix stores the list of common
shops visited by i and j.

Line 8-10: else block will be executed when if block does not get executed. This means when i == j,
matrix[i][j] stores the empty list for the same customer.

Question 9 [5 Marks]
Statement
Consider the adjacency matrix matrix constructed above. Assume that there exists a procedure
removeDuplicate which receives a list as input and removes all duplicate elements in the list.
When will findGoodSet(matrix) return True?

1 Procedure findGoodSet(M)
2 foreach i in rows(M){
3 foreach j in columns(M){
 4 foreach h in rows(M){
5 list1 = []
6 if(length(M[i][j]) == 1 and member(D[h], first(M[i][j]))){
7 list1 = list1 ++ M[i][j]
8 }
9 if(length(M[i][h]) == 1 and member(D[j], first(M[i][h]))){
10 list1 = list1 ++ M[i][h]
11 }
12 if(length(M[j][h]) == 1 and member(D[i], first(M[j][h]))){
13 list1 = list1 ++ M[j][h]
14 }
15 list1 = removeDuplicate(list1)
16 if(length(list1) == 1){
17 return(True)
18 }
19 }
20 }
21 }
22 return(False)
23 End findGoodSet

Options
(a)

If there exists three customers who have visited all three shops.

(b)

If there exist three customers such that every pair of customers among them have visited only
one and the same shop in common.

(c)

If there exists three customers who have visited exactly one shop.

(d)

If there exists three customers where each pair among them have visited exactly one shop in
common.

Answer
(b)

Solution
Fix some values for i, j, and h from 0 to n-1.

Line 5: list1 is initialized with an empty list.

Line 6: There are two condition added by "and". Therefore to get executed this if block, both the
conditions should be True. The first condition is
As M[i][j] stores the list of shops visited by both the customers and if the length is 1, then
customers i and j have visited only one common shop.

The second condition is given as

As D[h] is the list of shops visited by the customer h, and first(M[i][j]) is the first element of list
store by M in i, j cell. M[i][j] is the list of shops visited by both i and j and from previous condition if
the length is 1 then M[i][j] contains only one shop if it is in D[h] then i, j have visited only one
common shop (pair-wise) and that shop is also visited by h.

Line 7: The common shop will be appended in list1.

Line 9 - 11: list1 will append the a shop, if this shop is the only one common shop visited by i and
h, and it is also visited by j.

Line 12 - 14: list1 will append the a shop, if this shop is the only one common shop visited by j and
h, and it is also visited by i.

Line 15: All the duplicates will be removed from list1.

If length(list1) == 1, then i, j, and h have visited only one common shop pairwise and only one
shop common overall too.

The correct option is (b).

Question (10) [5 Marks]
Statement
For a pair of customers i and j, j is said to be shopping partner of i if i and j have visited at least
two shops in common. findTopCustomer(matrix) finds a customer who has the maximum
shopping partners. Choose the correct implementation of findTopCustomer.

Options
(a)

(b)
(c)

(d)

Answer
(b)

Solution
We want to find the customer who have the maximum shopping partner. As per definition of the
shopping partner, i and j should have visited at least two common shops. This can be captured
using the following conditional statement:

length(M[i] [j]) >= 2 or length(M[i] [j]) > 1

Based on the pseudocodes in the options, Max captures the maximum number of shopping
partners for any customer, and A captures the customer who has maximum shopping partner.
for each customer i, C captures the number of shopping partners of i. Once C is computed for i,
we have to check i has more partner than the current maximum. By combining all the above logic,
we can obtain the following pseudocode:

The correct option is (b).

 Week 10

1 MULTIPLE CHOICE QUESTIONS:

1. The maximum number of non-zero entries in an adjacency matrix of a simple graph
having n vertices can be [option: d]

(a) n2
(b) n(n−1)
2
(c) n(n−1)
4
(d) n(n − 1)

Solution:
Number of non zero entry means number of ones in the adjacency matrix which is
equal to the sum of the degrees of all vertices. In a graph a vertex can have maximum
n − 1 degree. In at most case if each vertex has the degree n − 1, then the sum of
degrees of all vertex will be (n − 1) + (n − 1) + n times which means n × (n − 1).
2. We have a graph G with 6 vertices. We write down the degrees of all vertices in G in
descending order. Which of the following is a possible listing of the degrees? [option:
c]

(a) 6,5,4,3,2,1
(b) 5,5,2,2,1,1
(c) 5,3,3,2,2,1
(d) 2,1,1,1,1,1

Solution:
Step 1:
Any vertex in a graph can have maximum degree (n-1).
Here n-1 = 6-1 = 5, therefore we do not need to check option 1.
Step 2:
Sum of degree of all vertices always be even therefore option 4 can not be correct
option.
Step 3:
If two vertices in a graph have (n-1) degree it means there will be no vertex with degree
1 (shown in figure ). Vertices A and F have degree 5.

Step 4:
Option 3 satisfies all the possible conditions therefore the correct option is option 3.

Page 2
Page 3
3. We are trying to find the correct path in a maze. We start at the entrance. At some
points, we have to choose a direction to explore. If we reach a dead end, we come
back to the most recent intersection where we still have an unexplored direction to
investigate. What is a good data structure to keep track of the intersections we have
visited? [option: b]

(a) List
(b) Stack
(c) Queue
(d) Array

Solution:
This is a recursive exploration of the maze, so intermediate stages should be stored on
a stack.

Page 4
4. Below table shows the adjacency list w.r.t outgoing edges of a directed graph G.

1 {2,4}
2 {3,5,6}
3 {7}
4 {3,5,6}
5 {6,7}
6 {1}
7 {1,2,6}

Table 1: adjacency list w.r.t forward edges

Which of the following tables shows the adjacency list w.r.t incoming edges of the
graph G? [option: c]

1 {6,7}
2 {1,6}
3 {2,4}
4 {1}
5 {2,7}
6 {2,4,5,7}
7 {3,5}

(a)

1 {6,7}
2 {1,7}
3 {2,4}
4 {1,5}
5 {2,4}
6 {2,4,7}
7 {3,5}

(b)

Page 5
 1 {6,7}
2 {1,7}
3 {2,4}
4 {1}
5 {2,4}
6 {2,4,5,7}
7 {3,5}

(c)

1 {6,7}
2 {1,4}
3 {2,7}
4 {1,5}
5 {2,4}
6 {2,4,7}
7 {3,5}

(d)

Page 6
5. Suppose we obtain the following BFS tree rooted at node 1 for an undirected graph
with vertices (1,2,3,4,5,. ..... 14).

5 4 10

6 11 3 12

7 2 9 13

8 14

Which of the following cannot be an edge in the original graph? [option: A]

(a) (8,11)
(b) (3,10)
(c) (4,5)
(d) (6,9)

Page 7
 2 MUTIPLE SELECT QUESTIONS:
6. Which of the following graphs satisfies the below properties:
1. |V C(G)| = 3, where V C(G) is the minimum vertex cover of a graph G.
2. |PM (G)| = 3, where PM (G) is the perfect matching of a graph G.
3. The graph is a 3-colouring. [option: c,d]

Page 8
 3 NUMERICAL ANSWER TYPE:
0 1 0 1 0 0 0
1 0 1 1 0 1 0
0 1 0 0 0 0 0
8. If A = 1 1 0 0 1 1 1 represents adjacency matrix of a graph G, then the
0 0 0 1 0 0 0
0 1 0 1 0 0 0
0 0 0 1 0 0 0
cardinality of the maximum independent set of the graph G is [Answer: 5]

Page 11
9. A company manufactures 10 chemicals x1, x2, x3, ....x10. Certain pairs of these chem-
icals are incompatible and would cause explosions if brought into contact with each
other. Below graph shows the incompatibility of the chemicals, each vertex represents
the chemical and each edge between a pair of chemicals represents that those two
chemicals are incompatible. As a precautionary measure the company wishes to par-
tition its warehouse into compartments, and store incompatible chemicals in different
compartments. What is the least number of compartments into which the warehouse
should be partitioned?
[Answer: 3]
10. An incomplete undirected graph is given below and the numbering on each vertex
denotes the colouring of the graph(‘1’ denotes color 1, ‘2’ denotes color 2, and ‘3’
denotes color 3). Find the number of maximum edges that can be added to the given
graph such that the colouring is retained and the graph is planar.
NOTE: Planar graph is a graph that can be drawn on the plane in such a way that its
edges intersect only at their endpoints. [Answer: 6]

1 2 3

3
1
2
1
1. There are 2n numbered cards in a deck among which nCi cards bear the number i
; i=0,1,2,...,n. From the deck, m cards are drawn with replacement. What is the
expectation of the sum of their numbers? (Enter the answer correct to one decimal
accuracy)
mn
Answer:
2
Solution:
Let, Xj; i=1,2,...,m be the random variable representing the number on the jth card
drawn.

Xj 0 1 2 ... n
n n n n
Number of cards C0 C1 C2 ... Cn
n n n n
C0 C1 C2 Cn
P (Xj = x) ...
2n 2n 2n 2n

Table 10.1
nC
Σn Σn x
E(X j) = x=0 xP (X j = x) = x=0 x ×
1 n
2n n n
E(X j) = × [(0 ×n C0 ) + (1 × C1 ) + (2 × C2 ) + ... + (n × C n)]
21n n(n − 1) n(n − 1)(n − 2) ........
E(X j) = × [0 + (1 × n) + 2 × + 3× + (n × 1)]
2n 2! 3!
n (n − 1)(n − 2)
E(X j) = × [1 + (n − 1) + + ... + 1]
2nn 2!
E(X j) = × [n−1 C 0 + n−1C 1 + n−1C 2 + ... + n−1C n−1 ]
2n n
n n−1
E(X j) = ×2 = 2
2n
Therefore, Expectation of the sum of their numbers is given by:
Σm
= j=1 E(Xj)
Σm n
= j=1
2
mn
=
2
Suppose, we substitute values of n and m as 4 and 7 respectively, then

1
 Let, Xj; i=1,2,...,7 be the random variable representing the number on the jth card
drawn.

Xj 0 1 2 3 4
4 4 4 4 4
Number of cards C0 C1 C2 C3 C4
4 4 4 4 4
C0 C1 C2 C3 C4
P (Xj = x)
24 24 24 24 24

Table 10.1
4C
Σ4 Σ4 x
E(X j) = x=0 xP (X j = x) = x=0 x ×
1 4
24 4 4 4
E(X j) = × [(0 ×4 C0 ) + (1 × C1 ) + (2 ×
C2 ) + (3 × C 3) + (4 × C 4)]
214
4(4 − 1) 4(4 − 1)(4 − 2)
E(X j) = × [0 + (1 × 4) + 2 × + 3× + (4 × 1)]
24 2! 3!
4 (4 − 1)(4 − 2)
E(X j) = × [1 + (4 − 1) + + 1]
244 2!
3 3 3
3
E(X j) = × [ C0 + C1 + C 2 + C 3]
24
4 3 4
E(X j) = × 2 =
24 2=2
Therefore, Expectation of the sum of their numbers is given by:
Σ7 Σ7
= j=1 E(Xj) = j=1 2 = 14

An unbiased die is thrown n+2 times. After each throw a ’+’ is recorded for 2 or 5 and
’-’ is recorded for 1,3,4 or 6, the signs forming an ordered sequence. To each, except the
first and last sign, a random variable Xi; i=1,2,...,n is associated which takes the value
1 if both of its neighbouring sign differs from the one between them and 0 otherwise.
Σ
If the random variable Y is defined as Y = aS + b where, S = n i=1 Xi, then use the
given information to answer question (2) and (3).
2. Find the expected value of Y .
2n
(a) a× +b
9
2n
(b) a ×
9
2n
(c) +b
9
2n
(d)
9

2
 Answer: a
Solution:
(
1 if the pattern is either ’+ - +’ or ’- + -’
Xi =
0 otherwise
E(Xi) = 1 × P (Xi = 1) + 0 × P (Xi = 0) = P (Xi = 1)
Now,
P (Xi = 1) =P(Pattern = ’+ - +’) + P(pattern=’- + -’)
2 2
4 2 4 2 2
P (Xi = 1) = × + × =
6 6 6 6 9
Σ Σ
E(S) = E( ni=1 Xi) = ni=1 E(Xi)
2n
E(S) =
9
Therefore, E(Y ) = aE(S) + b
2n
E(Y ) = a × +b
9
Suppose, we substitute values of n, a and b as 10, 9 and 1 respectively then,
Σ Σ
E(S) = E( 10i=1
Xi) = 10 i=1 E(Xi)

Σ10 2 20
E(S) = i=1 9 =
9
20
Therefore, E(Y ) = 9E(S) + 1 = 9 × +1
9
E(Y ) = 20 + 1 = 21
3. Which of the following statement(s) is/are true?

a. V (Y ) = a2V (S) + b
b. V (Y ) = a2V (S)
c. V (Y ) /= a2V (S)
d. E(Y ) = a2E(S) + b
e. E(Y ) = aE(S) + b

Answer: b,e
By the property of Expectation and Variance, we get:
V (Y ) = a 2V (S)
E(Y ) = aE(S) + b (always)
Hence, option (b) and (e) is correct.
Suppose, we substitute values of a and b as 9 and 1 respectively then,

3
 V (Y ) = (9)2 × V (S) = 81V (S)
E(Y ) = 9E(S) + 1 (always)

Amandeep is in the middle of a bridge of infinite length. He takes the unit step to
the right with probability p and to the left with probability 1— p. Assume that the
movements are independent of each other.
Hint: Consider the random variable Xi associated with the ith step defined as:
(
1 if the step of Amandeep is towards the right
Xi =
−1 if the step of Amandeep is towards the left

Using this information, answer question (4) and (5).

4. What is the expected distance between the starting point and end point of Amandeep
after n steps?

(a). 2p − 1
(b). n(2p − 1)
(c). 1 − 2p
(d). n(1 − 2p)

Answer: b
Solution:
Let us associate a random variable Xi with the ith step.
(
1 if ith step of Amandeep is towards the right
Xi =
−1 if i th step of Amandeep is towards the left
E(Xi) = 1 × P (Xi = 1) + (−1) × P (Xi = −1)
E(Xi) = 1 × p − 1 × (1 − p) = 2p − 1
S = X1 + X2 + ... + Xn represents the random distance moved from the starting point
after n steps.
Σ
Therefore, E(S) = n i=1 E(Xi) = n(2p − 1)
Hence, expected distance between the starting point and end point of Amandeep after
n steps is n(2p − 1)
For example: p=0.6 , n=7
Let us associate a random variable Xi with the ith step.
(
1 if ith step of Amandeep is towards the right
Xi =
−1 if i th step of Amandeep is towards the left
E(Xi) = 1 × P (Xi = 1) + (−1) × P (Xi = −1)
E(Xi) = 1 × 0.6 − 1 × 0.4 = 0.2

4
 S = X1 + X2 + ... + X7 represents the random distance moved from the starting point
after 7 steps.
Σ7
Therefore, E(S) = i=1 E(Xi) = 7(0.2) = 1.4
Hence, the expected distance between the starting point and end point of Amandeep
after 7 steps is 1.4.
5. What is the variance distance between the starting point and end point of Amandeep
after n steps?
(a). 4np(1 − p)
(b). 4p(1 − p)
(c). 1
(d). n2(2p − 1)2 − 1
Answer: a
Solution:
E(Xi)2 = 12 × P (Xi = 1) + (−1)2 × P (Xi = −1)
E(Xi)2 = p + (1 − p) = 1
V (Xi) = E(Xi)2 − [E(Xi)]2
V (Xi) = 1 − (2p − 1)2 = 4p(1 − p)
Σ
Therefore, V (S) = n V (Xi) (because, movements of steps are independent)
i=1
Σn
Hence, V (S) = i=1 4p(1 − p) = 4np(1 − p)
For Example: p=0.6 , n=7
E(Xi)2 = 12 × P (Xi = 1) + (−1)2 × P (Xi = −1)
E(Xi)2 = 0.6 + 0.4 = 1
V (Xi) = E(Xi)2 − [E(Xi)]2
V (Xi) = 1 − (0.2)2 = 0.96
Σ
Therefore, V (S) = 7 i=1 V (Xi)
Because, movements of steps are independent.
Σ
Hence, V (S) = 7i=1(0.96) = 7 × (0.96) = 6.72
6. A box contains a white and b black balls. c balls are drawn at random without replace-
ment. Find the expected value of the number of white balls drawn?(Enter the answer
correct to 2 decimal places).
Solution:
Let X denote the number of white balls drawn. The probability distribution of X is
obtained as follows:

X 0 1 2 ... c
b
Cc a C1 × Cc−1b aC2 × Cc−2b a
Cc
p(x) a+b ... a+b
Cc a+b
Cc a+b
Cc Cc

5
 Then expected number of white balls drawn is :
b
Cc aC1 × bCc−1 aC2 × bCc−2 a
Cc
E(X) = 0 × a+b + 1 × a+b + 2 × a+b + ... + c ×
Cc Cc Cc a+b
Cc
For example: a=7, b=4, c=2
Let X denote the number of white balls drawn. The probability distribution of X is
obtained as follows:

X 0 1 2
4C
2
= 6 7
C1 × 4C1 = 28 7C
2
= 21
p(x) 11
C2 55 11
C2 55 11
C2 55

Then expected number of white balls drawn is :

6 28 21 70
E(X) = 0 × +1× +2× = = 1.27.
55 55 55 55

7. Rohit wants to open his door with 5 keys(out of which 1 will open the door) and tries
the keys independently and at random. If unsuccessful keys are eliminated from further
selection, then Find the expected number of trials required to open the door.
(Hint: Suppose Rohit gets the first success at xth trial, i.e., he is unable to open the
1 1
door in the first (x− 1) trials. And, P(he gets first success at second trial)=(1− )× )
5 4
(a). 1
(b). 9
(c). 3
(d). 2

Answer:c
Solution:

If unsuccessful keys are eliminated from further selection, then the random variable X
will take the values from 1 to n. In this case, we have
1
Probability of success at the first trial=
5
1
Probability of success at the second trial=
4
1
Probability of success at the third trial=
3
1
Probability of success at the fourth trial=
2
Probability of success at the fifth trial=1 and so on.
1 1 1
Hence probability of 1st success at the 2nd trial = (1 − ) × =
5 4 5

6
 1 1 1 1
probability of 1st success at the 3rd trial = (1 − ) × (1 − ) × =
5 4 3 5
and so on. In general,
1
p(x)= probability of 1st success at the xth trial= ; x = 1, 2, 3, 4, 5
5
Therefore,
Σ5 1 1 1 1 1
E(X) = xp(x) = 1 × +2× +3× +4× +5× = 3
x=1
5 5 5 5 5

8. X and Y are independent random variables with means m 1 and m2, and variances v1
and v2 respectively. Find the variance of aX + bY ?
Answer: a2× v1 + b2 × v2
Solution:
Since X and Y are independent random variables.
Therefore, V (aX + bY ) = a2 × V (X) + b2 × V (Y ) = a2 × v1 + b2 × v2
For example: m1 = 10, m2 = 20, v1 = 2 and v2 = 3
Since X and Y are independent random variables.
Therefore, V (3X + 4Y ) = 9 × V (X) + 16 × V (Y ) = 9 × 2 + 16 × 3 = 18 + 48 = 66
9. Let X be a random variable with the following probability distribution:

X a b c
1 1 f
P (X = x)
d e g
Calculate the value of E(2X + 1)2.(Enter the answer correct to 2 decimal places)
1 1 1 1 1 1
Answer: 4 × a2 × + b2 × + c2 × +4× a× +b× +c× +1
d e f d e f
Solution: 1 1 1
E(X) = Σxp(x) = a × +b×
+c× .
d f e
1 1 1
E(X2) = Σx2p(x) = a2 × + b2 × + c2 ×
d e f
2 2 2
E(2X + 1) = E(4X + 4X + 1) = 4E(X ) + 4E(X) + 1
For example: a = −3, b = 6, c = 9, d = 6, e = 2 and f = 3

X -3 6 9
1 1 1
P (X = x) 6 2 3
1 1 1 11
E(X) = Σxp(x) = (−3) × +6× +9× = .
6 2 3 2

7
 1 1 1 93
E(X2) = Σx2p(x) = 9 × + 36 × + 81 × =
6 2 3 2
93 11
E(2X + 1)2 = E(4X2 + 4X + 1) = 4E(X2) + 4E(X) + 1 = 4 × +4× + 1 = 209
2 2

10. Suppose that X is a random variable for which E(X) = m and V ar(X) = v. Find the
positive values of a and b such that Y = aX − b, has expectation 0 and variance 1.
−1 −m
a. √ , √
v v
1 m
b. , √
v v
1 m
c. √ , √
v v
d. 1, m

Answer: c
Solution:
E(Y ) = aE(X) − b = 0 =⇒ ma − b = 0 =⇒ ma = b 1...(1) 1
2 2 2
Now,V (Y ) = a V (X) = 1 =⇒ a × v = 1 =⇒ a = =⇒ a = √
v v
m
Now putting value of a in equation(1) , we get b = √
v
Hence, option(c) is correct.
For example: m=10 and v=25
E(Y ) = aE(X) − b = 0 =⇒ 10a − b = 0 =⇒ 10a = b ...(1)
1 1
Now,V (Y ) = a2V (X) = 1 =⇒ a2 × 25 = 1 =⇒ a2 = =⇒ a =
25 5
Now putting value of a in equation(1) , we get b = 2