Algorithm Engineering

1x5 1. a) (Write answers with single sentence only) i. Mention one example where game-theoretic approach does not achieve best possible outcome for both the players. ii. What is the meaning of expected utility in a mixed strategy game? iii. Why are multi-objective problems mostly approached to solve using heuristic approaches? iv. Why can't Johnson's algorithm solve longest path problem? v. When/ where do we need a self-balanced tree? b) Given the red-black tree below insert the key 9. Show your steps. 6.66 11 2 14 1 7 15 5 8 c) Maximum flow problem is also stated as max flow-min cut' problem. Explain. d) Comment on the complexity of Johnson's algorithm. 3 2