CT Week 9 Graded Assignments IIT Madras

1.There is an edge between students i and j, with i $\ne$ j, if and only if:

2. Which of the following statements are true about this graph? It is a Multiple Select Question (MSQ).

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 $\ne$ 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.

colab = createMatrix(n, n)

auth1 = 0, auth2 = 0

foreach i in keys(books){

    auth1 = first(books[i])

    auth2 = last(books[i])

    colab[auth1][auth2] = colab[auth1][auth2] + 1

    colab[auth2][auth1] = colab[auth2][auth1] + 1

}

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

Procedure isClique(authors, colab)

    foreach i in authors{

        foreach j in authors{

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

            *   Fill the code   *

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

        }

    }

    return(True)

End isClique

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?

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 $\ne$ j, and returns True if i is the ancestor of j, and False otherwise. Select the correct code fragment to complete the pseudocode.

Procedure isAncestor(A, i, j)

      k = i

      flag = True

      while(flag){

           flag = False

           foreach c in columns(A){

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

                  * Fill the code *

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

           }

       }

       return(False)

 End isAncestor