Nptel Design And Analysis Of Algorithms Week 3 Quiz Solutions

-: IMPORTANT NOTICE :-

CLICK HERE FOR WEEK 4 SOLUTION 

Your answer is given in the explanation section, so please read carefully the explanation section for getting 100% in on the nptel assignment.

1. A connected undirected graph G has 2775 edges. What can we say about n, the number of vertices in G?

 76 ≤ n ≤ 2775

 75 ≤ n ≤ 2775

 76 ≤ n ≤ 2776

 75 ≤ n ≤ 2776

Explanation:-

The relationship between the number of vertices (n) and the number of edges (m) in an undirected simple graph can be described using the Handshaking Lemma, which states that the sum of the degrees of all vertices in a graph is twice the number of edges: 

2m = Σ(deg(v)) for all vertices v.

Given that the graph G has 2775 edges (m = 2775), we can use this relationship to find a range for the number of vertices (n). The maximum number of edges for an n-vertex graph can be calculated using a complete graph formula:

Max edges = n(n - 1) / 2.

We can set up an inequality based on this formula:

2775 ≤ n(n - 1) / 2.

Now we solve for n:

5550 ≤ n(n - 1),

0 ≤ n^2 - n - 5550.

Using the quadratic formula to solve for n:

n = (1 ± √(1 + 4*5550)) / 2,

n = (1 ± √(1 + 22200)) / 2,

n = (1 ± √22201) / 2.

Since n must be positive, we take the positive root:

n = (1 + √22201) / 2 ≈ 75.01.

So, n is approximately 75.01, which means that n could be either 75 or 76. 

Out of the given options, the correct answer is: 75 ≤ n ≤ 2776.

2. An airline serves 1000 cities and runs 5500 direct flights each day between these cities. Which of the following is a good data structure to represent the collection of flights?

 A 1000 × 1000 array A, where A[i][j] = 1 if there is a direct flight from city i to city j and 0 otherwise.

 A stack containing values (i, j) for each pair of cities i, j for which there is a direct flight from city i to city j.

 A queue containing values (i,j) for each pair of cities i, j for which there is a direct flight from city i to city j.

 A list containing values (i, j) for each pair of cities i, j for which there is a direct flight from city i to city j.

Explanation:-

The most suitable data structure to represent the collection of flights in this scenario is:

A 1000 × 1000 array A, where A[i][j] = 1 if there is a direct flight from city i to city j and 0 otherwise.

Explanation:

1. The problem involves representing a collection of direct flights between cities, which can be modeled as a matrix.

2. The cities are labeled from 1 to 1000, and the direct flights can be thought of as connections between these cities.

3. An array (or matrix) is the most straightforward and efficient way to represent the connectivity between cities. It directly maps to the concept of a direct flight between two cities.

4. Each cell (i, j) in the array can be set to 1 if there's a direct flight from city i to city j, and 0 otherwise.

5. This approach allows for constant-time lookup to determine whether there's a direct flight between two cities.

The other options involve using different data structures, like stacks, queues, or lists, which are not as suitable for efficiently representing the direct flights between cities in this scenario.

3. Suppose we obtain the following BFS tree rooted at node J for an undirected graph with vertices {A,B,C,D,E,F,G,H,I,J,K}.

Which of the following cannot be an edge in the original graph?

 (C,G)

 (B,K)

 (B,F)

 (A,D)

Explanation:-

In a BFS (Breadth-First Search) tree, edges are selected such that they connect a node to its immediate neighbors in the order they are explored. Therefore, the edges in the BFS tree must represent edges that exist in the original graph.

Let's go through the given options one by one:

(C,G): This edge can exist in the original graph because both C and G are vertices in the original graph, and the BFS tree includes this edge.

(B,K): This edge can exist in the original graph because both B and K are vertices in the original graph, and the BFS tree includes this edge.

(B,F): This edge cannot be an edge in the original graph. The BFS tree only includes edges that connect a node to its immediate neighbors in the order they are explored. If (B,F) were an edge, it would mean that F is an immediate neighbor of B in the original graph, and B should have been explored before F in the BFS. However, based on the given BFS tree, this is not the case. So, (B,F) cannot be an edge in the original graph.

(A,D): This edge can exist in the original graph because both A and D are vertices in the original graph, and the BFS tree includes this edge.

So, the edge that cannot be an edge in the original graph is (B,F).

4. We are interested in topological orderings of the following DAG which satisfy the constraint that whenever 9 appears after 8, 2 must appear after 4. How many such orderings are there?

 12

 10

 9

 8

Explanation:-

Given Constraint:

Whenever 9 appears after 8, 2 must appear after 4.

Let's approach this systematically:

1. There are two vertices with no incoming edges: 1 and 3. These can be placed at the beginning of the topological ordering.

2. After 1 and 3, we have two options for placement:

   - Vertex 2: It must come after vertex 1.

   - Vertex 5: It must come after both vertex 1 and vertex 4.

3. After vertex 5, we have two options for placement:

   - Vertex 6: It must come after vertex 5.

   - Vertex 9: It must come after vertex 5.

4. Now, let's consider the constraint involving 8, 9, 4, and 2:

   - Vertex 8: It must come after vertex 7.

   - Vertex 9: It must come after vertex 5.

   - Vertex 4: It must come after vertex 1.

   - Vertex 2: It must come after vertex 4.

This means the valid order for these vertices is: 1, 3, 7, 8, 4, 5, 9, 2.

5. After these vertices, we have vertex 6, followed by vertex 10.

6. Finally, we add vertices 12 and 10 to the end in 2! = 2 ways.

Therefore, the total number of topological orderings that satisfy the given constraint is 2 * 2 = 4.

5. Applying for permits to put up a factory is an 11 step process. Some steps depend on others, as described below.

Step 1 must be completed before steps 3 and 4 start.

Step 2 must be completed before steps 3, 6 and 7 start.

Step 3 must be completed before step 7 starts.

Step 4 must be completed before step 5 starts.

Step 5 must be completed before step 7 starts.

Step 7 must be completed before steps 8 and 9 start.

Step 9 must be completed before steps 10 and 11 start.

Each step takes a week to complete. What is the minimum number of weeks required to get all the permits in place?

 4

 6

 8

 9

Explanation:-

To find the minimum number of weeks required to get all the permits in place, we can analyze the dependencies and sequence of steps. Let's go through the given dependencies and determine the order in which the steps should be completed:

Step 1 must be completed before steps 3 and 4 start.

Step 2 must be completed before steps 3, 6, and 7 start.

Step 3 must be completed before step 7 starts.

Step 4 must be completed before step 5 starts.

Step 5 must be completed before step 7 starts.

Step 7 must be completed before steps 8 and 9 start.

Step 9 must be completed before steps 10 and 11 start.

Based on these dependencies, we can organize the steps in the following way:

1. Steps 1 and 2 can be done in parallel in the first week.

2. In the second week, step 3 can start since both step 1 and step 2 are completed.

3. In the third week, step 4 can start after step 1 is completed.

4. In the fourth week, step 5 can start after step 4 is completed.

5. In the fifth week, step 6 can start after step 2 is completed.

6. In the sixth week, step 7 can start after steps 3, 5, and 6 are completed.

7. In the seventh week, step 9 can start after step 7 is completed.

8. In the eighth week, step 8 can start after step 7 is completed.

9. In the ninth week, steps 10 and 11 can start after step 9 is completed.

So, the minimum number of weeks required to get all the permits in place is 6 weeks.

The correct answer is: 6.