Back to the 2023 paper
Similar questions
Design and Analysis of Algorithms A graph with five nodes is represented using the adjacency list as follows: | | | | | | |---|---|---|---|---| | A | -> | B (10) | C (3) | | | B | -> | C (1) | D (5) | | | C | -> | B (4) | D (8) | E (2) | | D | -> | E (7) | | | | E | -> | D (9) | | | Answer the following: (i) Draw the graph for the above adjacency list. (ii) Write the algorithm for the Breadth-First Traversal (BFS). (iii) Show the BFS traversal of the graph with the starting node as A.20247mDesign and Analysis of Algorithms An adjacency matrix representation of a graph cannot contain information of (i) nodes (ii) edges (iii) direction of edges (iv) parallel edges20222mDesign 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 Apply the Prim's algorithm and find the optimal solution for the following graph: 20257m
PreviousYou are a thief planning to rob a jewelry store. The store contains 7 items, each with a profit P and weight W as follows: | Object | 1 | 2 | 3 | 4 | 5 | 6 | 7 | |---|---|---|---|---|---|---|---| | Profit (P) | 5 | 10 | 15 | 7 | 8 | 9 | 4 | | Weight (W) | 1 | 3 | 5 | 4 | 1 | 3 | 2 | You have a knapsack with a weight capacity of 15. Apply the step-by-step greedy approach to obtain the maximum profit.NextDifferentiate between backtracking and branch & bound.