Computing Concepts with Java Essentials
Laboratory Notebook
Chapter 12 - Algorithms

Cay S. Horstmann
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 send your lab work. Be sure to read the instructions before starting your work.


Lab Objectives

To gain experience with


P1. Sorting

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.


P2. Searching

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.


P3. Unique elements

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.)


P4. Binary Search

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.