Back to the 2024 paper
Similar questions
Design and Analysis of Algorithms Discuss the differences between BFS and DFS in terms of traversal order, memory usage, and their applications in real-world problems.20237mDesign and Analysis of Algorithms In DFS traversal of a graph, which data structure is used to keep track of visited nodes? (i) Queue (ii) Stack (iii) Priority Queue (iv) Heap20242mSoftware EngineeringWhich of the following is not a use of a CASE tool? (i) It supports structured analysis and design (SA/SD) (ii) It maintains the data dictionary (iii) It checks whether DFDs are balanced or not (iv) It compiles with the available system.20222mSoftware EngineeringWhich of the following is not a use of a CASE tool? (i) It supports structured analysis and design (SA/SD) (ii) It maintains the data dictionary (iii) It checks whether DFDs are balanced or not (iv) It complies with the available system20202m
PreviousConsider a TSP with 4 cities A, B, C, D and the following distance matrix: | | A | B | C | D | |---|---|---|---|---| | A | 0 | 10 | 15 | 20 | | B | 10 | 0 | 35 | 25 | | C | 15 | 35 | 0 | 30 | | D | 20 | 25 | 30 | 0 | Answer the following: (i) Use the branch-and-bound algorithm to find the shortest possible route that visits all cities exactly once and returns to the starting city. (ii) Show the branching steps and calculate lower bounds for each partial solution. (iii) Identify how the bounding helps prune the search tree.NextDesign 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.