PyQdeck LogoPyQdeckSubjects
Back to the 2024 paper

Module 3: Graph and Tree Algorithms

20247m

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.

Search GoogleAsk AI

Similar questions

Design 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 Algorithm20242mDesign 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 |20237mComputer NetworksAssume that source S and destination D are connected through two intermediate routers labelled R. Determine how many times each packet has to visit the network layer and the data link layer during a transmission from S to D. ![network_diagram](image_needs_human_verification_S-R-R-D_topology)20167mOperating SystemWhich memory allocation policy allocates the largest hole to the process? (i) Best-fit (ii) Worst-fit (iii) First-fit (iv) None of the above.20222m
PreviousAnswer the following: (i) Explain the concept of a Minimum Spanning Tree (MST) in a connected, weighted, undirected graph. (ii) Compare and contrast Prim's and Kruskal's algorithms for finding the MST. (iii) Analyze the time complexity of both algorithms and discuss their advantages and scenarios where one is preferred over the other.NextAnswer the following: (i) Describe complexity classes P, NP, NP-complete, and NP-hard. (ii) State and explain Cook's Theorem. (iii) Why is it considered a foundational result in computational complexity theory?