Back to the 2024 paper
Similar questions
Design & Analysis of AlgorithmsThe choice of polynomial class has led to the development of an extensive theory called: - (i) computational complexity - (ii) time complexity - (iii) problem complexity - (iv) decision complexity20222mDesign and Analysis of Algorithms What is P, NP, NP hard, and NP complete? Write the relationship between all of them.20237mDesign and Analysis of Algorithms What is the relationship between NP and P complexity classes? (i) P is a subset of NP (ii) NP is a subset of P (iii) P and NP are equivalent (iv) P and NP are disjoint sets20232mDesign and Analysis of Algorithms Which complexity class contains problems for which a given solution can be verified in polynomial time by a deterministic Turing machine? (i) Class P (ii) Class NP (iii) Class NP-Hard (iv) Class Undecidable20252m
PreviousGiven 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.NextAnswer the following: (i) What is polynomial-time reduction? (ii) How is it used to prove that a problem is NP-complete? (iii) Explain the process of reducing 3-SAT to Vertex Cover.