Answer the following Question :
(a) When does a problem belong to P-Class and when does belong NP Class?
(b) Give two P-Class problems, and give two NP-Class problems which no one knows belonging to P-class or not. Give time complicities of each, respectively.
(c) Suppose that A is a problem belonging to P-Class and B is a problem to NP-Class. Does A belong to NP-Class? Does B belong to P-Class?
(d) Let A be a problem satisfying the following conditions
(i) any problem in NP, Class can be reduced to A in polynomial time, and
(ii) A in an NP problem. What class dose A belong to? Answer the following questions:
(a) Selection sort and insertion sort are called force sort. What is the time complicity for each of them in the worst case?
(b) Between selection sort and inspection sort, which is better? Why?
(a) What is the time complexity of Quick sort in is wart case? What is the time complexity of Merge Soft in worst case?
(b) Can Quick Sort run faster Merge-Sort? Why?