Lab 9

Problem 1

Github Link

Write a program to find and compare the number of comparisons using the binary search and sequential search algorithms as follows:
Create a vector of 100,000 integers.
a. Use a random number generator to fill vector. You can generate random number with:

 /* initialize random seed: */
  srand (time(NULL));

 /* generate random number between 0 and 10,000,000: */
 int iRand = rand() % 10000000;Code language: PHP (php)


b. Use the STL sort algorithm to sort the array (STL:sort).
c. Write two different search functions:

  1. A sequencial search:
    int seq_search(vector<int> keys, int key, int &numCmp);
  2. A binary search:
    int bin_search(vector<int> keys, int key, int &numCmp);
  3. An enhanced binary search:
    int bin2_search(vector<int> keys, int key, int &numCmp);

Where the searches return the index of the number found, or -1 and numCmp is the number of comparisons made.

The enhanced search changes to a sequential search if the remaining span of the search is less then 15. (You could make a sequential search version with the start and end points specified, e.g.:
int seq_search(vector<int> keys, int key, int start, int stop, int &numCmp);

Write a test program that picks 50 random numbers from the test data above, and generates 50 more random numbers (that may more may not be in the data above), and searches for each numer using each of the 3 search methods. The output should be as follows:

Problem 2

Github Link

a. Some of the attributes of a state in the United States are its name, capital, GDP, Motto, Flower, and Area. Design the class stateData to keep track of the information for a single state. Your class must include appropriate functions to manipulate the state’s data, such as the functions setStateInfo, getStateInfo, and so on. Also, overload the relational operators to compare two states by their name. For easy input and output, overload the stream operators.

b. Use the class hashT as described in the section, ‘‘Hashing: Implementation Using Quadratic Probing,’’ which uses quadratic probing to resolve collision, to create a hash table to store all state’s information. Use the state’s name as the key to determine the hash address. You may assume that a state’s name is a string of no more than 15 characters. DO initial Test your program by searching for and removing certain states from the hash table.
c. Use AI (ChatGPT) to create a test program that makes up new fake states and adds and removes at least 1,000 states in a random pattern. The program should output a log of the states added an removed, and report any errors (such as a full table). The goal it to really test ALL possible boundary conditions of this system.

int hashFunc(string name) {
  int i, sum;
  int len;
  i = 0;
  sum = 0;
  len = name.length();
  for (int k = 0; k < 15 - len; k++)
    name = name + ' '; // increase the length of the name
  // to 15 characters
  for (int k = 0; k < 5; k++) {
    sum = sum + static_cast<int>(name[i]) * 128 * 128 +
          static_cast<int>(name[i + 1]) * 128 + static_cast<int>(name[i + 2]);
    i = i + 3;
  }
  return sum % HTSize;
}

Teams:
Lab9-Pair-01: Djordje Dragojlovic, Nora Archer
Lab9-Pair-02: Hoan Nguyen, Lucas Waite
Lab9-Pair-03: Eden Cohen, Cloris (Zongyu) Liu
Lab9-Pair-04: Peter Dunson, Yaw Oppongkrampah
Lab9-Pair-05: Luke Galik, Ella Rigoli
Lab9-Pair-06: Joey (Jiayin) Liu, Shadia Amado-Aguad
Lab9-Pair-07: Moe Belghith, Leo Xie
Lab9-Pair-08: Davelle Ampofotwumasi, Sariyah Sintayehu
Lab9-Pair-09: Westley (Kelly) Kailus, Trang Nguyen
Lab9-Pair-10: Calvin Deka, Khanh Mai

Lab9-Solo-11: Adam Khan
Lab9-Solo-12: Kuba Kopczuk

Scroll to Top