Problem
Consider the Longest Path problem: find a simple path (no repeated vertices) of maximum weight in a graph.
1. Explain why the problem is considered intractable.
2. Explain why a similar problem, the Shortest Path Problem, is tractable.
3. Provide pseudocode that uses magic coin (non-deterministic) to solve the problem.
4. Analyze the complexity of your code.
5. Explain how use of the magic coin 'reduces' (or hides) the complexity.