Reference no: EM13332686

Part 1 - Ulam

Given the following function:
public static int Ulam(int num)
{
if (num < 2)
return 1;
else
{
if (num % 2 == 0)
return Ulam(num/2);
else
return Ulam(3*num + 1);
}
}

1) What problems come up in verifying this function?
2) How many recursive calls are made by the following initial calls?
a. Ulam(22);
b. Ulam(16);
c. UIam(46);

Part 2 - Bubblesort

Consider your textbook's implementation of bubblesort from chapter 8. The method is included below for your convenience.

3) What is the time complexity of running the below bubblesort on an array of random integers?
4) What is the time complexity of running the below bubblesort on an array of sequential integers (1,2,3,4,5,..)?
5) Show a simple modification that can be made to the below bubblesort that significantly improves the time complexity for an array of sequential integers.
6) What is the new time complexity in the array of sequential integer's condition? Explain why this modification improved the run-time.

Part 3 - Quicksort

Consider your textbook's implementation of quicksort from chapter 8. The corrected findPartition method is included below for your convenience.

7) What is the time complexity of running quicksort using this partition method on an array of random integers?
8) What is the time complexity of running quicksort using this partition method on an array of sequential integers (1,2,3,4,5,..)?
9) Robert Sedgewick suggests using the median of the first, last and middle elements as the partition element. Explain why this modification is important.
10) Show what modifications are needed to convert the findPartition method to use the median element as the partition.