Laboratory Notebook

Chapter 12 - Algorithms

Geof Pawlicki

Your name: | |

Your email address: | |

Your student ID number: |

Once this form has been customized for your
institution, you can use this button

To gain experience with

- bubble sort, merge sort, linear and binary search algorithms
- algorithms for the same task that differ widely in performance
- big-Oh notation
- estimating and comparing the performance of algorithms
- measuring the running time of an algorithm

Sorting is among the most fundamental operations commonly performed by computer. One sorting algorithm that is often used because it is easy to program is called Bubble Sort.

public class BubbleSort { public static void swap(int[] a, int i, int j) { int temp = a[i]; a[i] = a[j]; a[j] = temp; } public static void bubbleSort(int[] a) { int i; int j; for (i = 0 ; i < a.length; i++) { /* move the largest number up */ for (j = 0 ; j < a.length - i - 1; j++) { if (a[j] > a[j+1]) swap(a, j, j + 1); } } } public static void print(int[] a) { int i; for (i = 0; i < a.length; i++) System.out.print(a[i] + " "); System.out.println(); } public static void main(String[] args) { int[] v = new int[100]; int i; for (i = 0; i < v.length; i++) v[i] = ccj.Numeric.randomInt(1, 100); print(v); bubbleSort(v); print(v); } }

Show the steps in which the algorithm sorts the sequence {4,2,1,3}.

Modify the `main()` function in BubbleSort.java to measure the
time that it takes to sort 1000, 2000, 3000 and 4000 random elements.
Print out a table of the amount of time required to sort each of these
sets and place the results here:

Modify the `main()` function in MergeSort.java in the textbook
to measure the time that it takes to sort 1000, 2000, 3000 and 4000 random
elements. Print out a table of the amount of time required to sort each of
these sets and place the results here:

How does this compare with the previous results using bubble sort?

How do you describe the performance of bubble sort using the big-Oh notation? Explain your analysis.

Bubble sort can be speeded up with the following test: If during one pass through the array, no pairs of elements had to be swapped, then the array is already sorted. Implement this improvement.

Repeat your measurements of random inputs. Feed the random inputs to both the old and the new bubble sort. How much faster is the improved algorithm?

How do you describe the performance of the improved bubble sort using the big-Oh notation? Explain your analysis.

A palindrome is a string that reads the same forward as backward, Some examples are:

radar Madam, I'm Adam I Able was I ere I saw Elba Go hang a salami, I'm a lasagna hog

Write a program that accepts a user input string and tests to see if it is a palindrome.

Give an estimate of your program's running time for an input that is a palindrome (in terms of the length of the input string).

Give an estimate of its running time for an input that is not a palindrome.

Write a function

boolean uniqueElements(int[] a)

that tests whether all elements in `a` occur exactly once. For
example, if `a` contains the numbers 4 9 4 5 6 3 1, then `uniqueElements`
returns `false`. If `a` contains the numbers 11 9 35 6 8 4
5, then `uniqueElements` returns `true`.

Use the following algorithm:

int n = a.length; for (i = 0; i < n; i++) if (a[i] occurs in a[i+1] ... a[n-1]) return false; return true;

Implement the `uniqueElements` function and a program that tests
it.

In the algorithm above, we tested

if (a[i] occurs in a[i+1] ... a[n-1])

At first glance, that actually seems wrong. The correct test would appear to be

if (v[i] occurs in v[0] ... v[i-1] or v[i+1] ... v[n-1])

Explain why the first test is sufficient.

Analyze the performance of this algorithm and estimate the running time using the Big-Oh notation.

Describe (but do not implement) a faster algorithm for the `uniqueElements`
function. (Hint: if the vector was sorted, it would be easier to spot
repeated elements.)

Write a program that implements a "guess the number" game. That is, generate a random integer between 1 and 999. Then give the user up to ten guesses. After each guess, display a "Too Low", "Too High" or "Got it!" message in response.

How is a guess-the-number game related to a binary search algrotithm?

Don't forget to send your answers when you're finished.