Design and analysis of algorithms Nptel Week 3 Quiz Answers

Are you looking for Nptel Design and analysis of algorithms Week 3 Quiz Answers?

Design and analysis of algorithms Week 3 Quiz Answers (Jan-Apr 2025)

Course link: Click here

Q1. An undirected graph G on 37 vertices has 5 connected components. What is the minimum number of edges in G?

A) 36
B) 32
C) 31
D) Depends on the sizes of the five connected components.

View Answer

Q2. Suppose we have a directed graph G = (V,E) with V = {1,2,…,n} and E presented as an adjacency list. For each vertex u in V, L(u) is a list [v1,v2,…,vk] such that (u,vi) in E for each i in {1,2,…,k}.

If we reverse the edges in G, we get a new graph GR = (V,ER) with the same set of vertices such that (u,v) in ER if and only if (v,u) in E.

We can represent GR using an adjacency list where, for each u in V, LR(u) is the list of neighbors of u with respect to ER.

Let n be the number of vertices in V and m be the number of edges in E. How long would it take to construct the adjacency lists LR(u), u in V, from the lists L(u), u in V?

A) O(m)
B) O(n + m)
C) O(n²)
D) O(n² + m)

View Answer

Q3. Suppose we obtain the following DFS tree rooted at node F for an undirected graph Gr with vertices {A,B,C,D,E,F,G,H}.

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

A) (F,G)
B) (B,C)
C) (A,F)
D) (A,H)

View Answer

Q4. We are interested in topological orderings of the following DAG that satisfy one or both of the following constraints:

4 appears before 3
8 appears after 7

How many such orderings are there?

A) 9
B) 13
C) 16
D) 18

View Answer

Q5. Assembling a laptop consists of several steps, such as fixing the motherboard, inserting the battery, putting in the keyboard, attaching the screen, etc. Suppose there are 10 steps, labeled A, B, C, D, E, F, G, H, I, J. Each step takes a day to complete and we have the following dependencies between steps.