NPTEL Design and Analysis of Algorithms Assignment Answer

1. An algorithm has two phases. The first phase, initialization, takes time O(n³). The second phase, which is the main computation, takes time O(n²). What is the most accurate description of the complexity of the overall algorithm?

O(n⁶)
O(n⁵)
O(n³)
O(n²)

Answer :- O(n³)

2. We are using a computer that performs 10⁸ basic operations per second. We are trying to determine the worst case time complexity of a library function that is provided to us, whose code we cannot read. We test the function by feeding large numbers of random inputs of different sizes. We find that for inputs of size 50 the function always returns well within one second, for inputs of size 500 it sometimes takes a couple of seconds and for inputs of size 5,000 it sometimes takes over 15 minutes. What is a reasonable conclusion we can draw about the worst case time complexity of the library function?

O(n⁴)
O(n³)
O(n² log n)
O(n²)

Answer :- O(n3)

3. Suppose f(n) is 2n²+4n+5 and g(n) is 7n³ + 5n² + 12. Let h(n) be a third, unknown function. Which of the following is not possible.

h(n) is O(f(n)) and h(n) is also O(g(n))
h(n) is not O(f(n)) and h(n) is also not O(g(n))
h(n) is O(f(n)) but h(n) is not O(g(n))
h(n) is O(g(n)) but h(n) is not O(f(n))

Answer :- h(n) is O(f(n)) but h(n) is not O(g(n))

4. How many times is the comparison i <= n performed in the following program?int i = 60, n = 300; main(){ while (i <= n){ i = i+2; n = n-3; } }

Answer :- 50

5. If T(n) is O(n^4/3) which of the following is false?

T(n) is O(n log n)
T(n) is O(n²)
T(n) is O(n² log n)
T(n) is O(n³)

Answer :- T(n) is O(n log n)

6. Having collected Aadhaar information for each SIM card, a government agency wants to check that all the Aadhaar numbers entered in SIM card applications are actually valid, by comparing SIM card applications against the list of registered Aadhaar numbers. Which of the following is likely to be the best strategy for this?

Use a nested loop. For each SIM card application S, and for each Aadhaar number A, check if the Aadhaar number listed in S is the same as A.
Sort the SIM card applications and use binary search to speed up the process.
Sort the registered Aadhaar numbers and use binary search to speed up the process.
Sort both the SIM card applications and registered Aadhaar numbers and merge the two lists.

Answer :- Sort the registered Aadhaar numbers and use binary search to speed up the process.

7. Suppose our aim is to sort an array in descending order. Which of the following statements is true?

Input in ascending order is worst case for both selection sort and insertion sort.
Input in ascending order is worst case for insertion sort but not for selection sort.
Input in descending order is worst case for both selection sort and insertion sort.
Input in ascending order is worst case for selection sort but not for insertion sort.

Answer :- Input in ascending order is worst case for both selection sort and insertion sort.

8. Suppose we want to sort an array in ascending order. We have a stable implementation of quicksort that alternately chooses the first and last element of the array as the pivot with each recursive call. Which of the following is not true for this implementation?

The worst case behaviour is O(n log n).
The average case behaviour is O(n log n).
The worst case behaviour is O(n²).
The average case behaviour is asymptotically better than the worst case behaviour.

Answer :- The worst case behaviour is O(n log n).

9. Which of the following statements is not true?

Quicksort and merge sort are both examples of divide and conquer algorithms.
If we randomly choose a pivot element each time, quicksort will always terminate in time O(n log n).
For every fixed strategy to choose a pivot for quicksort, we can construct a worst case input that requires time O(n²).
If we could find the median in time O(n), quicksort would have worst case complexity O(n log n).

Answer :- If we randomly choose a pivot element each time, quicksort will always terminate in time O(n log n).

10. We have a list of pairs [(“Shweta”,71),(“Sunita”,85),(“Tariq”,71),(“Brinda”,85), (“Salma”,72),(“Uday”,60)], where each pair consists of a student’s name and his/her marks in a course. We sort these pairs in ascending order of marks. Which of the folllowing corresponds to a stable sort of this input?

[(“Uday”,60),(“Tariq”,71),(“Shweta”,71),(“Salma”,72).(“Sunita”,85),(“Brinda”,85)]
[(“Uday”,60),(“Shweta”,71),(“Tariq”,71),(“Salma”,72),(“Sunita”,85),(“Brinda”,85)]
[(“Uday”,60),(“Tariq”,71),(“Shweta”,71),(“Salma”,72),(“Brinda”,85),(“Sunita”,85)]
[(“Uday”,60),(“Shweta”,71),(“Tariq”,71),(“Salma”,72),(“Brinda”,85),(“Sunita”,85)]

Answer :- [("Uday",60),("Shweta",71),("Tariq",71),("Salma",72),("Sunita",85),("Brinda",85)]

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

36
32
31
Depends on the sizes of the five connected components.

Answer :- 32

12. 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 [v₁,v₂,…,v_k] such that (u,v_i) in E for each i in {1,2,…,k}.
If we reverse the edges in G, we get a new graph G_R = (V,E_R) with the same set of vertices such that (u,v) in E_R if and only if (v,u) in E.
We can represent G_R using an adjacency list where, for each u in V, L_R(u) is the list of neighbours of u with respect to E_R.

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 L_R(u), u in V, from the lists L(u), u in V?

O(m)
O(n + m)
O(n²)
O(n² + m)

Answer :- O(n + m)

13. 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?(F,G)(B,C)(A,F)(A,H)

Answer :- (A,H)

14. 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?

Answer :- 13

15. 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, labelled 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.

A must happen before H
B must happen before F
B must happen before G
C must happen before H
D must happen before E
E must happen before B
F must happen before A
F must happen before C
G must happen before F
I must happen before D
I must happen before G
J must happen before D
J must happen before I

What is the minimun number of days required to complete the interiors?

Answer :- 9

16. A regional airline serves 10 cities. It operates to-and-fro return flights between 9 pairs of cities in such a way that every city is reachable from every other city through a sequence of connecting flights.

We know the fuel consumption for the direct flights between each pair of cities. We want to compute the minimum fuel consumption from a given city to every other city in the airline network. Which of the following is true for this specific situation?

We can use BFS, DFS or Dijkstra’s algorithm to compute this.
We can use BFS or Dijkstra’s algorithm to compute this, but not DFS.
We can use DFS or Dijkstra’s algorithm to compute this, but not BFS.
We can only use Dijkstra’s algorithm to compute this, not BFS or DFS.

Answer :- We can use BFS, DFS or Dijkstra's algorithm to compute this.

17. An airline charges a fixed price for each direct flight. For each sequence of hopping flights, the ticket price is the sum of the fares of the individual sectors.

TripGuru has precalculated the cheapest routes between all pairs of cities on this airline’s route network so that it can offer an optimum choice instantly to customers visiting its website.

The government decides to impose a 3% luxury tax on each sector. Which of the following describes the impact of this surcharge on TripGuru’s computation?

There is no impact. Cheapest routes between all pairs of cities remains unchanged.
The surcharge favours hopping flights with more sectors. TripGuru should recompute any cheapest route where there is a longer route in terms of number of flights.
The surcharge favours hopping flights with fewer sectors. TripGuru should recompute any cheapest route where there is a shorter route in terms of number of flights.
The impact is unpredictable. TripGuru should recompute all cheapest routes.

Answer :- There is no impact. Cheapest routes between all pairs of cities remains unchanged.

18. An airline charges a fixed price for each direct flight. For each sequence of hopping flights, the ticket price is the sum of the fares of the individual sectors.

TripGuru has precalculated the cheapest routes between all pairs of cities on this airline’s route network. A major IT company has its offices at all the locations served by the airline, and books all official trips for its employees via TripGuru. To simplify administrative processing, the IT company has selected a subset of the airline’s routes so that all of their office locations are reachable from each other, and the total cost of travelling across all the chosen routes is minimum.

The airline has decided to become a full-service carrier and has included a meal on each sector. To account for this, the airline has added a flat “convenience fee” of Rs 300 on each sector. Which of the following describes the impact of this surcharge on the IT company’s computation of which subset of routes to use?

There is no impact. The IT company can retain the same subset of routes.
The surcharge favours hopping flights with more sectors. The IT company should reconsider including routes where there may be a longer route, with more hops.
The surcharge favours hopping flights with fewer sectors. The IT company should reconsider including routes where there may be a shorter route, with fewer hops.
The effect of the surcharge is unpredictable. The IT company should recompute its preferred subset of routes afresh.

Answer :- There is no impact. The IT company can retain the same subset of routes.

19. Suppose we have a weighted undirected graph with negative edge weights. Which of the following is correct?

Neither Kruskal’s algorithm nor Prim’s algorithm can be used to compute an MCST.
Kruskal’s algorithm will compute a valid MCST but Prim’s algorithm will not.
Prim’s algorithm will compute a valid MCST but Kruskal’s algorithm will not.
Both Krusksl’s algorithm and Prim’s algorithm can be used to compute an MCST.

Answer :- Both Krusksl's algorithm and Prim's algorithm can be used to compute an MCST.

20. How can we use the Floyd-Warshall algorithm for all-pairs shortest paths to detect whether a graph has a negative cycle?

Check if any shortest path entry A[i][j] is negative.
Check if any shortest path entry A[i][i] on the diagonal is negative.
Check if any shortest path entry A[i][j] reduces from one iteration to the next.
The Floyd-Warshall algorithm cannot be used to detect negative cycles.

Answer :- Check if any shortest path entry A[i][i] on the diagonal is negative.

Leave a Comment Cancel reply