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;
}

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

Lab 9 Grading Rubric (100 Points)

Category Description Points
Problem 1:
Data Generation & Sorting Correctly creates a vector of 100,000 integers, fills it using a random number generator, and sorts it using std::sort. 10
Problem 1: Sequential Search Correct implementation of sequential search; returns correct index or -1; accurately tracks numCmp. 15
Problem 1: Binary Search Correct binary search implementation; proper bounds handling; accurate comparison counting. 15
Problem 1: Enhanced Binary Search Correctly switches to sequential search when remaining span < 15; correct bounds; numCmp correctly accumulated. 15
Problem 1: Test Program & Output Runs all three searches on 50 values from the dataset and 50 random values; output is clearly labeled and readable. 15
Problem 2: stateData Class Design Proper class design with required attributes; getters/setters; relational operators compare by name; stream operators overloaded correctly. 10
Problem 2: Hash Table with Quadratic Probing Correct use of provided hash function; supports insert, search, and remove; handles collisions and full-table cases. 10
Problem 2: Stress Test Program (≥1000 Operations) Randomized addition/removal of at least 1,000 (fake) states; logs operations; detects and reports errors. 5
Use of ChatGPT for Test Program Student clearly documents use of ChatGPT for generating the stress test and demonstrates understanding by integrating and verifying the code. 5
Code Quality & Commenting Clear structure, good naming, appropriate use of references, meaningful comments explaining logic and edge cases. 5
Total 100