REVIEW QUESTIONS

2.1 Write pseudocode for an algorithm for finding the square root of a number.
2.2 Write pseudocode for finding the mean of a set of numbers.
2.3 Count the primitive operations in your algorithm to find the mean. What is the order of growth of your
mean algorithm?
2.4 Write pseudocode for finding the median of a set of numbers.
2.5 What is the order of growth of your algorithm to find the median?
2.6 Suppose that your algorithm to find the mean is Θ(n), and that your algorithm to find the median is Θ(n lg n),
what will be the execution speed ratio between your algorithm for the mean and your algorithm for the
median when the number of values is 1,000,000?
2.7 A sort routine which is easy to program is the bubble sort. The program simply scans all of the elements
to be sorted repeatedly. On each pass, the program compares each element with the one next to it, and
reorders the two, if they are in inverse order. For instance, to sort the following list:
6 7 3 1 4

Bubble sort starts by comparing 6 and 7. They are in the correct order, so it then compares 7 and 3. They
are in inverse order, so bubble sort exchanges 7 and 3, and then compares 7 and 1. The numbers 7 and 1
are in reverse order, so bubble sort swaps them, and then compares 7 and 4. Once again, the order is
incorrect, so it swaps 7 and 4. End of scan 1:
6 3 1 4 7
Scanning left to right again results in:
3 1 4 6 7
Scanning left to right again results in a correct ordering:
1 3 4 6 7
Write pseudocode for the bubble sort.
2.8 What is the bubble sort T?
2.9 How will the bubble sort compare for speed with the merge sort when the task is to sort 1,000,000 social
security numbers which initially are in random order?