1) Consider the following algorithm.

// Assume that n is a positive integer (= i.e. n > 1), and A[1..n] is a global array.

// Note that the index of array A starts from one, not zero.

// And also, dont forget the array A in the algorithm is global.

Algorithm DoSomething (n)

1. if (n = 1)

2. print the current content of the whole array A on the screen;

3. else

4. for i <-- 1 to n do

5. DoSomething(n 1); // Recursive call.

6. if n is odd

7. swap A[1] and A[n];

8. else

9. swap A[i] and A[n];

10. return;

(a) Present execution result of the algorithm where an array A has 3and n is 1.

(b) Present execution result of the algorithm where an array A has 3, 5and n is 2. (Show all the stesp)

(c) Present execution result of the algorithm where an array A has 3, 5, 7and n is 3. (Show all the stesp)

(d) Based on the results of thr question (a), (b), and (c), describe the main purpose of the algorithm.

2) Solve the following recurrence relation. To solve the problem, you have to use the backward substitution and show the intermediate results. After that, you should present the time complexity of the recurrence relations.

M(n) = 2 * M (n-1) // Recurrence relation

M()) = 3 // Initial condition