Q4: Answer the following [5*3]

1. Define P and NP classes.
2. What is the space complexity of adjacency lists?
3. How much time it would take to search for a particular edge in both adjacency list and matrix?
4. How dynamic programming is different from simple recursion?
5. Differentiate between spanning trees and minimum spanning tree.
6. What is meant by solvable intractable problem? Explain with example.