4. [3 points] Sort the sequence

3, 1, 4, 5, 6, 2

in increasing order using the Selection Sort algorithm. List all the intermedi-

ate steps, i.e., the partially ordered sequences resulting from the swaps of the

algorithm.

5. [4 points] Consider the recurrence relation

Cn = 2cn-1+2" - 1.

Solve the recurrence as follows:

(a) Find the general solution of the homogeneous part of the recurrence.

(b) Find a particular solution of the form

Ck = k2k + d

(1)

where d is a constant to be determined.

(c) Add the general solution of the homogeneous equation to the particular

solution of the non-homogeneous problem to obtain the general solution of

the non-homogeneous problem. Find the unique solution of (1) satisfying

Co = 0.