Back to the 2023 paper
Similar questions
Design and Analysis of Algorithms Write short notes on any two of the following: (i) Asymptotic Notations (ii) Clique decision problem (iii) Max-flow-min-cut theorem (iv) Union-Find Algorithm202214mDesign and Analysis of Algorithms Which algorithm is typically used in maximum flow problems? (i) Kruskal's Algorithm (ii) Floyd-Warshall (iii) Ford-Fulkerson (iv) Prim's Algorithm20242mFORMAL LANGUAGE & AUTOMATA THEORYExplain the Myhill–Nerode theorem for minimization of automata with an example.20227mDesign and Analysis of Algorithms Given the flow network below with capacities: | EDGE | CAPACITY | |---|---| | S -> A | 10 | | S -> C | 10 | | A -> B | 4 | | A -> C | 2 | | C -> D | 9 | | B -> T | 10 | | D -> B | 6 | | D -> T | 10 | Answer the following: (i) Use the Ford-Fulkerson algorithm to find the maximum flow from source (S) to sink (T). (ii) Show the augmenting paths selected, the bottleneck capacities on each path, and the updated residual capacities after each augmentation. (iii) Calculate the final maximum flow value.20247m