Nptel Design And Analysis Of Algorithms Week 4 Quiz Solutions

-: IMPORTANT NOTICE :-

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

Please click on Learn More on any one ad for help us.

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?

 O(n2)

 O(nm)

 O(m)

 O(n)

The most accurate description of the complexity of computing the list of vertices pointing into each vertex in terms of n, the number of vertices, and m, the number of edges, is:

O(m)

This is because for each vertex, you need to iterate through its incoming edges, and the total number of incoming edges across all vertices is equal to the number of edges in the graph, which is represented by 'm'. Therefore, the complexity of this operation is proportional to the number of edges, O(m).

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. Consider the following 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.

 The claim is not true in general.

 The claim is not true in general for graphs with cycles.

 The claim is true for connected acyclic graphs.

 The claim is true for all graphs.

The correct statement is:

**The claim is true for all graphs.**

Explanation:

The given strategy effectively eliminates negative edge weights by adding a constant 'k+1' to each edge weight. This ensures that all edge weights become non-negative. The strategy works correctly for both graphs with cycles and connected acyclic graphs, ensuring that Dijkstra's algorithm can be applied on the modified graph to compute the shortest paths and then subtracting the added weights will provide the original distances.

Here's why:

1. **Adding Constant to All Edge Weights:** By adding 'k+1' to each edge weight, you ensure that all edge weights are non-negative. This transformation preserves the order of distances, meaning the shortest paths in the modified graph are equivalent to the shortest paths in the original graph with respect to their order.

2. **Dijkstra's Algorithm:** Dijkstra's algorithm works correctly on graphs with non-negative edge weights. When the edge weights are transformed as described, the algorithm can be applied to find the shortest paths in the modified graph.

3. **Subtracting Added Weights:** Once you've found the shortest paths in the modified graph, subtracting the added weights ('k+1') from the path distances will result in the original distances in the original graph. This is because you've effectively canceled out the adjustments made to the edge weights.

In summary, this claim is indeed true for all types of graphs, whether they contain cycles or are acyclic. The strategy of adding a constant to all edge weights and then subtracting the added weights after applying Dijkstra's algorithm successfully converts the problem of finding shortest paths in a graph with negative edge weights to a problem with non-negative edge weights.

3. Consider the following algorithm on a connected graph with edge weights.

Sort the edges as [e1,e2,...,em] in decreasing order of cost.

Start with the original graph. Consider each edge ej. If this edge is part of a cycle delete it.

Which of the following is not true.

 At most n-1 edges will be deleted.

 After processing all m edges, the resulting graph is connected.

 What remains at the end is a minimum cost spanning tree.

 Exactly m-n+1 edges will be deleted.

Explanation:-

1. **At most n-1 edges will be deleted:** This statement is **true**. In any connected graph, a minimum spanning tree consists of exactly 'n-1' edges. Since you are removing edges that are part of cycles, at most 'n-1' edges can be deleted while maintaining the connectivity of the graph.

2. **After processing all m edges, the resulting graph is connected:** This statement is **true**. The algorithm starts with a connected graph and only removes edges that are part of cycles. Removing edges within cycles does not disconnect the graph, so the resulting graph will remain connected after processing all edges.

3. **What remains at the end is a minimum cost spanning tree:** This statement is **not necessarily true**. While the algorithm's process of removing edges maintains connectivity and eliminates cycles, it does not guarantee that the remaining edges will form a minimum cost spanning tree. The algorithm does not consider the global optimality of the spanning tree; it only looks at cycles and removes edges from them.

4. **Exactly m-n+1 edges will be deleted:** This statement is **not true**. The number of edges deleted depends on the number of cycles in the graph. The exact number of edges deleted will not necessarily be 'm-n+1'. The number of edges deleted will be at most 'n-1' in order to form a minimum spanning tree.

In summary, while the algorithm ensures that the resulting graph remains connected and contains at most 'n-1' edges, it does not guarantee that the remaining edges form a minimum cost spanning tree. The exact number of edges deleted will depend on the presence and arrangement of cycles in the graph.

4. Consider the following strategy to solve the single source shortest path problem with edge weights from source s.

Replace each edge with weight w by w edges of weight 1 connected by new intermediate nodes

Run BFS(s) on the modified graph to find the shortest path to each of the original vertices in the graph.

Which of the following statements is correct?

 This strategy will solve the problem correctly and is as efficient as Dijkstra's algorithm.

 This strategy will solve the problem correctly but is not as efficient as Dijkstra's algorithm.

 This strategy will only work if the graph is acyclic.

 This strategy will not solve the problem correctly.

Explanation:

The strategy of replacing each edge with multiple unit-weight edges and then running BFS will correctly find the shortest paths from the source vertex 's' to all other vertices. However, it is not as efficient as Dijkstra's algorithm.

Here's the breakdown:

1. **Correctness:** The strategy will work correctly because BFS explores the graph level by level, which guarantees that the shortest paths are found before longer paths.

2. **Efficiency:** While BFS is effective for finding shortest paths in unweighted graphs, it becomes less efficient when applied to graphs with weighted edges. Replacing edges with multiple unit-weight edges leads to duplicate exploration, which results in extra work during the BFS traversal.

3. **Duplicate Exploration:** When you replace an edge with multiple unit-weight edges, BFS will explore each of these edges separately, even though they have the same weight. This can lead to redundant exploration and additional computational overhead.

4. **Intermediate Nodes Overhead:** The introduction of intermediate nodes and multiple edges per original edge increases the complexity of the graph, making it more cumbersome to process during the BFS traversal.

5. **Dijkstra's Algorithm:** Dijkstra's algorithm is designed to efficiently handle graphs with different edge weights. It uses a priority queue to explore edges with lower weights first, which results in more efficient path-finding than BFS, especially when dealing with weighted graphs.

In summary, the strategy described will indeed find the correct shortest paths, but it's not as efficient as Dijkstra's algorithm. Dijkstra's algorithm is a more optimized approach for finding shortest paths in graphs with weighted edges, as it takes into account the specific weights of the edges and efficiently explores the graph using a priority queue.

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?

 Kruskal's algorithm will identify the same spanning tree on the new graph as on the old graph.

 Minimum cost spanning trees in the original graph will not correspond to minimum cost spanning trees in the new graph.

 Prim's algorithm will not work on the modified graph but will work on the original graph.

 There are more minimum cost spanning trees in the modified graph than in the original graph.