WEEK 5

SEARCH ALGORITHMS ArrayList.cpp code

#include #include "ArrayList.h"

using namespace std;

/* * Default constructor. Sets length to 0, initializing the list as an empty * list. Default size of array is 20. */ ArrayList::ArrayList() { SIZE = 20; list = new int[SIZE]; length = 0; }

/* * Destructor. Deallocates the dynamic array list. */ ArrayList::~ArrayList() { delete [] list; list = NULL; }

/* * Determines whether the list is empty. * * Returns true if the list is empty, false otherwise. */ bool ArrayList::isEmpty() { return length == 0; }

/* * Prints the list elements. */ void ArrayList::display() { for (int i=0; i < length; i++) cout << list[i] << " "; cout << endl; }

/* * Adds the element x to the end of the list. List length is increased by 1. * * x: element to be added to the list */ void ArrayList::add(int x) { if (length == SIZE) { cout << "Insertion Error: list is full" << endl; } else { list[length] = x; length++; } }

/* * Removes the element at the given location from the list. List length is * decreased by 1. * * pos: location of the item to be removed */ void ArrayList::removeAt(int pos) { if (pos < 0 || pos >= length) { cout << "Removal Error: invalid position" << endl; } else { for ( int i = pos; i < length - 1; i++ ) list[i] = list[i+1]; length--; } }

/* * Bubble-sorts this ArrayList */ void ArrayList::bubbleSort() { for (int i = 0; i < length - 1; i++) for (int j = 0; j < length - i - 1; j++) if (list[j] > list[j + 1]) { //swap list[j] and list[j+1] int temp = list[j]; list[j] = list[j + 1]; list[j + 1] = temp; } }

/* * Quick-sorts this ArrayList. */ void ArrayList::quicksort() { quicksort(0, length - 1); }

/* * Recursive quicksort algorithm. * * begin: initial index of sublist to be quick-sorted. * end: last index of sublist to be quick-sorted. */ void ArrayList::quicksort(int begin, int end) { int temp; int pivot = findPivotLocation(begin, end);

// swap list[pivot] and list[end] temp = list[pivot]; list[pivot] = list[end]; list[end] = temp;

pivot = end;

int i = begin, j = end - 1;

bool iterationCompleted = false; while (!iterationCompleted) { while (list[i] < list[pivot]) i++; while ((j >= 0) && (list[pivot] < list[j])) j--;

if (i < j) { //swap list[i] and list[j] temp = list[i]; list[i] = list[j]; list[j] = temp;

i++; j--; } else iterationCompleted = true; }

//swap list[i] and list[pivot] temp = list[i]; list[i] = list[pivot]; list[pivot] = temp;

if (begin < i - 1) quicksort(begin, i - 1); if (i + 1 < end) quicksort(i + 1, end); }

/* * Computes the pivot location. */ int ArrayList::findPivotLocation(int b, int e) { return (b + e) / 2; }

/* * Determines if an item exists in the array list using sequential (linear) * search. * * x: item to be found. * * Returns true if x is found in the list, false otherwise. */ bool ArrayList::sequentialSearch(int x) { for (int i=0; i < length; i++) if (list[i] == x) return true; // x is in the array

return false; // x is not in the array }

/* * Determines if an item exists in the array list using sorted search. * Precondition: list must be sorted. * * x: item to be found. * * Returns true if x is found in the list, false otherwise. */ bool ArrayList::sortedSearch(int x) { int i = 0; while (i < length && list[i] < x) i++;

if (i < length && list[i] == x) return true; // x is in the array else return false; // x is not in the array }

/* * Determines if an item exists in the array list using binary search. * Precondition: list must be sorted. * * x: item to be found. * * Returns true if x is found in the list, false otherwise. */ bool ArrayList::binarySearch(int x) { int first = 0, last = length - 1, pivot;

bool found = false; while (first <= last && !found) { pivot = (first + last) / 2; if (list[pivot] == x) found = true; else if (x < list[pivot]) last = pivot - 1; else first = pivot + 1; }

if (found) return true; else return false; }

SEARCH ALGORITHMS main.cpp code

#include #include "ArrayList.h" #include

using namespace std;

/* * Program to test the ArrayList class. */ int main() { srand((unsigned)time(0));

//list creation ArrayList numbers;

for (int i = 0; i<20; i++) { numbers.add(rand()%100); }

//printing the list cout << "List of numbers:" << endl <<"\t"; numbers.display();

int x;

//searching with sequential search cout << endl << "(Sequential Search) Enter a number: "; cin >> x;

if (numbers.sequentialSearch(x)) cout << "Found!" << endl; else cout << "Not found!" << endl;

//Sorting the list numbers.quicksort();

cout << endl << "Sorted list of integers:" << endl <<"\t"; numbers.display();

//searching with sorted search cout << endl << "(Sorted Search) Enter a number: "; cin >> x;

if (numbers.sortedSearch(x)) cout << "Found!" << endl; else cout << "Not found!" << endl;

//searching with binary search cout << endl << "(Binary Search) Enter a number: "; cin >> x;

if (numbers.binarySearch(x)) cout << "Found!" << endl; else cout << "Not found!" << endl;

return 0; }

Exercise 2: Study of Search Algorithms

Expand the project developed in the previous exercise to perform the following experiment: Time the sequential search and the binary search methods several times each for randomly generated values, then record the results in a table. Do not time individual searches, but groups of them. For example, time 100 searches together or 1,000 searches together. Compare the running times of these two search methods that are obtained during the experiment.

Regarding the efficiency of both search methods, what conclusion can be reached from this experiment? In addition to the source code and a screenshot of the execution window, please submit a separate document with the table and your conclusions about the experiment.

Exercise 3: Searching Applications

Design and implement an algorithm that determines whether or not a given array of integers, list1, is completely contained within another given array of integers, list2. Consider two different scenarios: (1) Both arrays are unsorted and (2) both arrays are sorted and write functions unsortedSearch and sortedSearch for (1) and (2), respectively. Your algorithm for (2) is expected to be more efficient than the one for (1).

Exercise 4: Hash Functions

Design and implement a hash function that converts a string to a hash value. Test your function by computing the hash values for the C++ keywords.

Note: You can use Sections 9.2.29.2.4 of our textbook as a reference to implement your own hash function; these sections discuss hash function design.