Are you looking for Nptel Design and analysis of algorithms Week 4 Quiz Answers? Get Nptel assignment answers of this course
Table of Contents
Design and analysis of algorithms Week 4 Quiz Answers
Design and analysis of algorithms Week 4 Quiz Answers (July-Dec 2025)
Question 1. We are given a directed graph, represented as an adjacency list, in which each vertex has at least one incoming edge and one outgoing edge. We would like to print out for each vertex j the list of vertices pointing into j. What is the most accurate description of the complexity of computing these quantities in terms of n, the number of vertices, and m, the number of edges?
Question 2. Consider the following strategy to convert an undirected graph with negative edge weights to one that does not have negative edge weights. Let the maximum magnitude negative edge weight in the graph be –k. Then, for each edge in the graph with weight w, update the weight to w + k + 1.
Claim: To solve the shortest path problem in the original graph, we can run Dijkstra’s algorithm on the modified graph and subtract the added weights to get the original distances.
Which of the following is not correct?
a) The claim is not true in general. b) The claim is not true in general for graphs with cycles. c) The claim is true for connected acyclic graphs. d) The claim is true for all graphs.
Question 3. Consider the following algorithm on a connected graph with edge weights:
Sort the edges as [e₁, e₂, …, eₘ] in decreasing order of cost.
Start with the original graph. Consider each edge eⱼ. If this edge is part of a cycle, delete it.
Which of the following is not true?
a) At most n–1 edges will be deleted. b) After processing all m edges, the resulting graph is connected. c) What remains at the end is a minimum cost spanning tree. d) Exactly m–n+1 edges will be deleted.
a) This strategy will solve the problem correctly and is as efficient as Dijkstra’s algorithm. b) This strategy will solve the problem correctly but is not as efficient as Dijkstra’s algorithm. c) This strategy will only work if the graph is acyclic. d) This strategy will not solve the problem correctly.
These are Design and analysis of algorithms Week 4 Quiz Answers
Question 5. Suppose we have a graph with negative edge weights. We take the largest magnitude negative edge weight –k and reset each edge weight w to w + k + 1. Which of the following is true?
a) Kruskal’s algorithm will identify the same spanning tree on the new graph as on the old graph. b) Minimum cost spanning trees in the original graph will not correspond to minimum cost spanning trees in the new graph. c) Prim’s algorithm will not work on the modified graph but will work on the original graph. d) There are more minimum cost spanning trees in the modified graph than in the original graph.
Q1. 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?
a) We can use BFS, DFS or Dijkstra’s algorithm to compute this. b) We can use BFS or Dijkstra’s algorithm to compute this, but not DFS. c) We can use DFS or Dijkstra’s algorithm to compute this, but not BFS. d) We can only use Dijkstra’s algorithm to compute this, not BFS or DFS.
These are Design and analysis of algorithms Week 4 Quiz Answers
Q2. 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?
a) There is no impact. Cheapest routes between all pairs of cities remains unchanged. b) 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. c) 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. d) The impact is unpredictable. TripGuru should recompute all cheapest routes.
These are Design and analysis of algorithms Week 4 Quiz Answers
Q3. 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 traveling 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?
a) There is no impact. The IT company can retain the same subset of routes. b) The surcharge favors hopping flights with more sectors. The IT company should reconsider including routes where there may be a longer route, with more hops. c) The surcharge favors hopping flights with fewer sectors. The IT company should reconsider including routes where there may be a shorter route, with fewer hops. d) The effect of the surcharge is unpredictable. The IT company should recompute its preferred subset of routes afresh.
These are Design and analysis of algorithms Week 4 Quiz Answers
Q4. Suppose we have a weighted undirected graph with negative edge weights. Which of the following is correct?
a) Neither Kruskal’s algorithm nor Prim’s algorithm can be used to compute an MCST. b) Kruskal’s algorithm will compute a valid MCST but Prim’s algorithm will not. c) Prim’s algorithm will compute a valid MCST but Kruskal’s algorithm will not. d) Both Kruskal’s algorithm and Prim’s algorithm can be used to compute an MCST.
These are Design and analysis of algorithms Week 4 Quiz Answers
Q5. How can we use the Floyd-Warshall algorithm for all-pairs shortest paths to detect whether a graph has a negative cycle?
a) Check if any shortest path entry A[i][j] is negative. b) Check if any shortest path entry A[i][i] on the diagonal is negative. c) Check if any shortest path entry A[i][j] reduces from one iteration to the next. d) The Floyd-Warshall algorithm cannot be used to detect negative cycles.
