*Computational Thinking week 9 graded assignment Complete Questions Are Discussed In This Blog. Access From Below Link*

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`

` Procedure isRelated(x, y)`

`17`

` if(first(x) == first(y) and last(x) == last(y)){`

`18`

` return(True)`

`19`

` }`

`20`

` else{`

`21`

` return(False)`

`22`

` }`

`23`

`End isRelated`

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

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

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 $n−1$. 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.

`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

Question-(4 to 11)

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.

`aVar = 0`

`bVar = []`

`foreach r in rows(colab){`

` foreach c in columns(colab){`

` if (colab[r][c] > aVar){`

` aVar = colab[r][c]`

` bVar = [r, c]`

` }`

` }`

`}`

4. What is the correct option for variable aVar?

**5**

5.What is the correct option for variable bVar?

**3**

`aVar = 0`

`bVar = 0`

`foreach r in rows(colab){`

` count = 0`

` foreach c in columns(colab){`

` if (colab[r][c] > 0){`

` count = count + 1`

` }`

` }`

` if(count > aVar){`

` aVar = count`

` bVar = r`

` }`

`}`

6.What is the correct option for variable aVar?

7.What is the correct option for variable bVar?

**4**

`aVar = 0`

`bVar = 0`

`foreach r in rows(colab){`

` count = 0`

` foreach c in columns(colab){`

` count = count + colab[r][c]`

` }`

` if(count > aVar){`

` aVar = count`

` bVar = r`

` }`

`}`

8.What is the correct option for variable aVar?

9. What is the correct option for variable bVar?

**2**

`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`

10.What is the correct option for variable aVar?

** 7**

*100 point*

11.What is the correct option for variable bVar?

**6**

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).

`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`

`if(i != j and colab[i][j] > 0){`

` return(False)`

`}`

`if (i != j and colab[i][j] == 0){`

` return(False)`

`}`

`if(i != j){`

` if(colab[i][j] == 1){`

` return (False)`

` }`

`}`

`if(i != j){`

` if(colab[i][j] == 0){`

` return(False)`

` }`

`}`

`if(i != j){`

` if(colab[i][j] == 0){`

` return(True)`

` }`

`}`

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 $n−1$. 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?

**correct answer**

*4 points*

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.

`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`

`if(A[k][c] == 1){`

` if(c == j){`

` return(True)`

` }`

` k = c`

` exitloop`

`}`

`if(A[k][c] == 1){`

` if(c == j){`

` return (True)`

` }`

` flag = True`

` exitloop`

`}`

`if(A[k][c] == 1){`

` if(c == j){`

` flag = True`

` return(True)`

` }`

` k = c`

` exitloop`

`}`

`if(A[k][c] == 1){`

` if(c == j){`

` return(True)`

` }`

` k = c`

` flag = True`

` exitloop`

`}`