IN C++.

1. Show the following (make sure you show all the steps). (15 points)
2. n³ 2n + log₂ n (n²)
3. 4n + 2n log₂ n (n log₂ n)
4. 7log₂ n² O(log₂ n)
5. Sort the sequence of integers { 2 ,5 ,4 , 6 , 3, 7, 8, 1} (show steps, do not write code) (20 points)

Using

1. Heapsort
2. MergeSort

3. Sort the same sequence as question 2 using Quicksort. (15 points)

4. The following algorithm finds the maximum and minimum element of an array (a[ ]). (20 points)

void MaxMin (int a[ ], int n, int max, int min)

{

int maxm, minm;

maxm=minm=a[0];

for (int j=1; j < n; j++)

{

if (a[j] > maxm)

maxm = a[j];

if (a[j] < minm)

minm = a[j];

}

max = maxm; min=minm;

}

1. Find the Worst and Average cases in term of the basic operations (comparison of two elements).
2. Find the order and the worst and average cases.

5. Solve the following recurrence relation in terms of n assuming n=2^k (15 points)

W(n) = 2 W(n/2) + n/2

W(1)=0

6. Define the following Graph Theoric terms (15 points)

1. A Graph=(V,E)
2. A Subgraph G=(V,E) of a graph G=(V,E)
3. A tree T=(V,E).