Question 1 |
Given a weighted directed graph G = (V, E, w) and a shortest path p
from s to t,
Consider the following statements
S1: if we doubled the weight of every edge to produce G'= (V, E, w'), then p is also a shortest path in G'.
S2 : if we increase the weight of every edge by constant c to produce G'= (V, E, w'), then p is also a shortest path in G'.
Consider the following statements
S1: if we doubled the weight of every edge to produce G'= (V, E, w'), then p is also a shortest path in G'.
S2 : if we increase the weight of every edge by constant c to produce G'= (V, E, w'), then p is also a shortest path in G'.
S1 is True and S2 is False | |
S1 is False and S2 is True | |
S1 and S2 are False | |
S1 and S2 are True |
Question 1 Explanation:
S1 is True.
Multiplying edge weights by any positive constant factor preserves their relative order, as well as the relative order of any linear combination of the weights. All path weights are linear combinations of edge weights, so the relative order of path weights is preserved. This means that a shortest path in G will still be a shortest path in G'.
The shortest path remains same. It is like if we change unit of distance from meter to kilometer, the shortest paths don't change.
S2 is false.
consider the following counter-example.
Let a graph contain only the following 2 paths-: S-W-T and S-A-B-T.
Let the weights of the edges be -:
S-W:2
W-T:2
S-A:1
A-B:1
B-T:1
Now the shortest path between S-T is S-A-B-T. Now add a weight of 5 (c=5) to all edges, and convince yourself the new shortest path will be S-W-T.
Click to Join Our Telegram Group for Latest Update of MOCK TEST 
Click Here to Practice ALL Previous MOCK TEST FREE
Multiplying edge weights by any positive constant factor preserves their relative order, as well as the relative order of any linear combination of the weights. All path weights are linear combinations of edge weights, so the relative order of path weights is preserved. This means that a shortest path in G will still be a shortest path in G'.
The shortest path remains same. It is like if we change unit of distance from meter to kilometer, the shortest paths don't change.
S2 is false.
consider the following counter-example.
Let a graph contain only the following 2 paths-: S-W-T and S-A-B-T.
Let the weights of the edges be -:
S-W:2
W-T:2
S-A:1
A-B:1
B-T:1
Now the shortest path between S-T is S-A-B-T. Now add a weight of 5 (c=5) to all edges, and convince yourself the new shortest path will be S-W-T.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 2 |
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 so that it can offer an optimum choice instantly to customers visiting its website.
Overnight, the government has added a 13% luxury service surcharge to the cost of each. Which of the following describes the impact of this surcharge on TripGuru's computation?
TripGuru has precalculated the cheapest routes between all pairs of cities so that it can offer an optimum choice instantly to customers visiting its website.
Overnight, the government has added a 13% luxury service surcharge to the cost of each. 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 fewer sectors. TripGuru should recompute any
cheapest route where there is a shorter route in terms of number of flights. | |
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 impact is unpredictable. TripGuru should recompute all cheapest routes. |
Question 2 Explanation:
Second way of asking the question on shortest path when we multiply constant with all edge's weight.
Multiplying edge weights by any positive constant factor preserves their relative order, as well as the relative order of any linear combination of the weights. All path weights are linear combinations of edge weights, so the relative order of path weights is preserved. This means that a shortest path in G will still be a shortest path in G'.
The shortest path remains same. It is like if we change unit of distance from meter to kilometer, the shortest paths don't change.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Source : NPTEL Course Assignment
Multiplying edge weights by any positive constant factor preserves their relative order, as well as the relative order of any linear combination of the weights. All path weights are linear combinations of edge weights, so the relative order of path weights is preserved. This means that a shortest path in G will still be a shortest path in G'.
The shortest path remains same. It is like if we change unit of distance from meter to kilometer, the shortest paths don't change.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Source : NPTEL Course Assignment
Question 3 |
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 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 TripGuru's computation?
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 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 TripGuru's computation?
There is no impact. Cheapest routes between all pairs of cities remains unchanged. | |
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 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 impact is unpredictable. TripGuru should recompute all cheapest routes. |
Question 3 Explanation:
The cost per edge increases, so the price for a path with n hops increases by 300n. This means that a
shorter path incurs a smaller penalty, so a longer "shortest" path in the original graph may be superseded
by a shorter one after adding the penalty on each edge.
Accepted Answers:
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.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Source : NPTEL Course Assignment
Accepted Answers:
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.
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Source : NPTEL Course Assignment
Question 4 |
Consider a graph G. Let T be a BFS tree with root r. Let d(u,v) denote the length of the
shortest path between the nodes u and v.
If v is visited before u in the breadth first search traversal, which of the following
statements is true ?
d(r,v) > d(r,u) | |
d(r,v) = d(r,u) | |
d(r,v) < d(r,u) | |
insufficient information to comment on d(r,v) and d(r,u) |
Question 4 Explanation:
u being traversed after v does not tell us if they are on the same level or not.
The correct relation would be
d(r,v) <= d(r,u)
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Click to Join Our Telegram Group for Latest Update of MOCK TEST
Click Here to Practice ALL Previous MOCK TEST FREE
Question 5 |
Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x \in V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u,v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u)-d(v)?
-1 | |
0 | |
1 | |
2 |
There are 5 questions to complete.