1. Solve the following recurrence equations. Be sure to show all your work . Tn)-2T(n/2)+n .T(n)-4T(n/3)+ nlgn 2. Discuss the diferences and commonalities between dynamic programming algorithms and divide and conquer algorithms. Consider sorting n numbers stored in array A by first finding the smallest element of A and exchanging it with the element in AlI)]. Then find the second smallest element of A, and exchange it with A[2]. Continue in this manner for the first n-1 elements of A. Write pseudocode for this algorithm, which is known as selection sort. Why does it need to run for only the first n 1 elements rather than for all n elements? Give the best-case and worst-case running times of selection sort in O notation. 3