## Computing Concepts with Java Essentials Laboratory Notebook Chapter 15 - Algorithms

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

• 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

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

```class BubbleSort
{  public static void sort(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])
ArrayUtil.swap(a, j, j + 1);
}
}
}
}
public class BubbleSortTest
{  public static void main(String[] args)
{  int[] a = ArrayUtil.randomIntArray(20, 100);
ArrayUtil.print(a);
BubbleSort.sort(a);
ArrayUtil.print(a);
}
}```

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

Modify the main() function in BubbleSortTest.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 MergeSortTest.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
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.

Using the big-Oh notation, 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 (a[i] occurs in a[0] ... a[i-1] or a[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 algortithm?