Back to the 2023 paper
Similar questions
Design and Analysis of Algorithms What is negative weight-cycle? Write Bellman-Ford algorithm to find single source shortest distance of a directed graph.20227mDesign and Analysis of Algorithms Explain how Bellman Ford algorithm can be used to detect the presence of negative weight cycles.20257mDesign and Analysis of Algorithms In the below given weighted graph W (Given in form of matrix), apply Bellman Ford's algorithm to find the shortest distances from source node 3. Write the time complexity of Bellman Ford's algorithm. | | 1 | 2 | 3 | 4 | 5 | |---|---|---|---|---|---| | 1 | 0 | 1 | 8 | 1 | 4 | | 2 | 1 | 0 | 12 | 4 | 9 | | 3 | 8 | 12 | 0 | 7 | 3 | | 4 | 1 | 4 | 7 | 0 | 2 | | 5 | 4 | 9 | 3 | 2 | 0 |20237mDesign and Analysis of Algorithms Design a system that finds the shortest paths between various locations in a city. The locations and roads are represented using a graph. What algorithm would you use if: (i) All roads have equal length (ii) Roads have varying lengths, but no negative lengths (iii) Some roads have negative lengths Justify your choices with suitable algorithms and reasoning.20247m
PreviousState Master's theorem and find the time complexity for the following recurrence: T(n) = 2T(n^{1/2}) + \log nNextFind the minimum number of operations required for the following matrix chain multiplication using dynamic programming: A(10 \times 20) * B(20 \times 50) * C(50 \times 1) * D(1 \times 100)