Graded Assignment - (Sep 2025 - CT - Qualifier)
The due date for submitting this assignment has passed. Due on 2025-11-26, 23:59 IST. You may submit any number of times before the due date. The final submission will be considered for grading.
Last Submitted: You have last submitted on: 2025-11-26, 21:00 IST
Note: ++++++++++++++++++++++++++++++++++
Question 1
There is an edge between students i and j, with i j, if and only if:
- they are from the same city/town
- they have the same gender
- they are from the same city/town and have the same gender
- they are from the same city/town or have the same gender
Status: Yes, the answer is correct. Score: 2
Accepted Answers:
- they are from the same city/town and have the same gender
Question 2
Which of the following statements are true about this graph? It is a Multiple Select Question (MSQ).
- There are two cliques in this graph, one for each gender
- In every clique, there is at least a pair of students having different genders
- All students in a given clique have the same gender
- All students in a given clique are from the same city/town
- There are no cliques in this graph
Status: Yes, the answer is correct. Score: 2
Accepted Answers:
- All students in a given clique have the same gender
- All students in a given clique are from the same city/town
Question 3
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.
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 the execution of the following pseudocode? Assume that the number of authors, n, is given to you.
xxxxxxxxxx
1
colab = createMatrix(n, n)
2
auth1 = 0, auth2 = 0
3
4
foreach i in keys(books){
5
6
auth1 = first(books[i])
7
8
auth2 = last(books[i])
9
10
colab[auth1][auth2] = colab[auth1][auth2] + 1
11
12
colab[auth2][auth1] = colab[auth2][auth1] + 1
13
14
}
- It represents the number of books published by authors i or j
- It represents the number of books in which authors i and j have collaborated
- It represents the number of books published by author i + number of books published by author j
- It represents the number of books published by author i in which he has not collaborated with author j
Status: Yes, the answer is correct. Score: 2
Accepted Answers:
- It represents the number of books in which authors i and j have collaborated
Question 4
xxxxxxxxxx 1 aVar = 0 2 bVar = [] 3 foreach r in rows(colab){ 4 foreach c in columns(colab){ 5 if (colab[r][c] > aVar){ 6 aVar = colab[r][c] 7 bVar = [r, c] 8 } 9 } 10 }
What is the correct option for variable aVar?
Your Answer: 5
Status: Yes, the answer is correct. Score: 1
Accepted Answers:
(Type: Numeric) 5
Question 5
What is the correct option for variable bVar?
Your Answer: 3
Status: Yes, the answer is correct. Score: 1
Accepted Answers:
(Type: Numeric) 3
Question 6
xxxxxxxxxx 1 aVar = 0 2 bVar = 0 3 foreach r in rows(colab){ 4 count = 0 5 foreach c in columns(colab){ 6 if (colab[r][c] > 0){ 7 count = count + 1 8 } 9 } 10 if(count > aVar){ 11 aVar = count 12 bVar = r 13 } 14 }
What is the correct option for variable aVar?
Your Answer: 1
Status: Yes, the answer is correct. Score: 1
Accepted Answers:
(Type: Numeric) 1
Question 7
What is the correct option for variable bVar?
Your Answer: 4
Status: Yes, the answer is correct. Score: 1
Accepted Answers:
(Type: Numeric) 4
Question 8
xxxxxxxxxx 1 aVar = 0 2 bVar = 0 3 foreach r in rows(colab){ 4 count = 0 5 foreach c in columns(colab){ 6 count = count + colab[r][c] 7 } 8 if(count > aVar){ 9 aVar = count 10 bVar = r 11 } 12 }
What is the correct option for variable aVar?
Your Answer: 8
Status: Yes, the answer is correct. Score: 1
Accepted Answers:
(Type: Numeric) 8
Question 9
What is the correct option for variable bVar?
Your Answer: 2
Status: Yes, the answer is correct. Score: 1
Accepted Answers:
(Type: Numeric) 2
Question 10
xxxxxxxxxx
1
aVar = 0
2
bVar = []
3
foreach r in rows(colab){
4
count = 0
5
foreach c in columns(colab){
6
if (colab[r][c] > 0){
7
count = count + 1
8
}
9
}
10
if(count == 1){
11
aVar = aVar + 1
12
bVar = bVar ++ [r]
13
}
14
}
15
What is the correct option for variable a****Var?
Your Answer: 7
Status: Yes, the answer is correct. Score: 1
Accepted Answers:
(Type: Numeric) 7
Question 11
What is the correct option for variable bVar?
Your Answer: 6
Status: Yes, the answer is correct. Score: 1
Accepted Answers:
(Type: Numeric) 6
Question 12
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).
xxxxxxxxxx
1
Procedure isClique(authors, colab)
2
foreach i in authors{
3
foreach j in authors{
4
*********************
5
* Fill the code *
6
*********************
7
}
8
}
9
return(True)
10
End isClique
-
xxxxxxxxxx 1 if(i != j and colab[i][j] > 0){ 2 return(False) 3 } 4 -
xxxxxxxxxx 1 if (i != j and colab[i][j] == 0){ 2 return(False) 3 } 4 -
xxxxxxxxxx 1 if(i != j){ 2 if(colab[i][j] == 1){ 3 return (False) 4 } 5 } -
xxxxxxxxxx 1 if(i != j){ 2 if(colab[i][j] == 0){ 3 return(False) 4 } 5 } 6 -
xxxxxxxxxx 1 if(i != j){ 2 if(colab[i][j] == 0){ 3 return(True) 4 } 5 }
Status: Yes, the answer is correct. Score: 4
Accepted Answers:
if (i != j and colab[i][j] == 0){ return(False) }if(i != j){ if(colab[i][j] == 0){ return(False) } }
Question 13
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?
Accepted Answers:
Question 14
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.
xxxxxxxxxx
1
Procedure isAncestor(A, i, j)
2
k = i
3
flag = True
4
while(flag){
5
flag = False
6
foreach c in columns(A){
7
*********************
8
* Fill the code *
9
*********************
10
}
11
}
12
return(False)
13
End isAncestor
-
xxxxxxxxxx 1 if(A[k][c] == 1){ 2 if(c == j){ 3 return(True) 4 } 5 k = c 6 exitloop 7 } -
xxxxxxxxxx 1 if(A[k][c] == 1){ 2 if(c == j){ 3 return (True) 4 } 5 flag = True 6 exitloop 7 } -
xxxxxxxxxx 1 if(A[k][c] == 1){ 2 if(c == j){ 3 flag = True 4 return(True) 5 } 6 k = c 7 exitloop 8 } -
xxxxxxxxxx 1 if(A[k][c] == 1){ 2 if(c == j){ 3 return(True) 4 } 5 k = c 6 flag = True 7 exitloop 8 }
Status: Yes, the answer is correct. Score: 4
Accepted Answers:
if(A[k][c] == 1){ if(c == j){ return(True) } k = c flag = True exitloop }