BIG C++

Cay Horstmann
& Timothy Budd

**Laboratory Notebook
Chapter 15 - Algorithms **

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.

#include <iostream> #include <vector> #include <cstdlib> using namespace std; void swap(int& x, int& y) { int temp = x; x = y; y = temp; } void bubble_sort(vector<int>& a) { int i; int j; for (i = 0 ; i < a.size() ; i++) { /* move the largest number up */ for ( j = 0 ; j < a.size() - i - 1; j++) { if (a[j] > a[j+1] ) swap(a[j], a[j+1]); } } } void print(vector<int> a) { int i; for (i = 0; i < a.size(); i++) cout << a[i] << " "; cout << "\n"; } int main() { vector<int> v(4000); int i; for (i = 0; i < v.size(); i++) v[i] = rand_int(1, 100); print(v); bubble_sort(v); print(v); return 0; }

Show the steps in which the algorithm sorts the sequence {9,7,2,3,3}.

Modify the `main()` function in bublsort.cpp to measure the time that it takes to sort 10000, 20000, 30000 and 40000 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 mergsort.cpp in the textbook to measure the time that it takes to sort
10000, 20000, 30000 and 40000 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 made faster 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

bool unique_elements(vector<int> v)

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

Use the following algorithm:

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

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

In the algorithm above, we tested:

if (v[i] occurs in v[i+1] ... v[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 `unique_elements` function.

Write a program that implements a "guess the number" game. That is, generate a random integer between 1 and 999 and 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?

Do not forget to send your answers when you are finished.