Problem 3 Any decrease by one algorithm can be viewed as having three parts: 1. Extracting a problem of size (n1) from a problem of size n by removing some element 2. Solving the problem of size (n1), usually by applying the same algorithm recursively, until the solution is trivial, and 3. Recombining the solution to the problem of size (n1) with the removed element, thus obtaining a solution to the original problem of size n. For example, in a decrease-by-one topological sort, part (1) involves removing a source or sink node, part (2) involves topologically sorting the remaining nodes, and part (3) involves attaching the source or sink note to the appropriate end of the sorted list. Insertion sort and selection sort can both be viewed as "decrease by one" algorithms. This is true in spite of the fact that Levitin classifies selection sort as a brute force algorithm. This does not this mean that Levitin is wrong in his classification - the algorithm can be viewed both ways. For both Insertion sort and Selection sort, do the following. 1. (10 points) Explain how a problem of size (n1) is extracted from a problem of size n. - Insertion Sort: - Selection Sort: 2. (10 points) State the asymptotic efficiency of the process of extracting the problem of size (n1). - Insertion Sort: - Selection Sort: 3. (10 points) Explain how the solution from applying the algorithm recursively (for the problem of size (n1)) is extended to construct a solution for the original problem of size n. - Insertion Sort: - Selection Sort: 4. (10 points) Calculate the asymptotic efficiency of the process of extending the solution to the problem of size (n1) to the solution of the problem of size n. - Insertion Sort: - Selection Sort