Data Structures and Object

1. What five things should be placed in a header file?

   Answers:

   1. Function Prototype

   2. Variable Declaration

   3. Class Declaration

   4. Constants Definition

2. I claimed in class that Insert, Remove and Search operations for hash tables require O(1) time on average, if two conditions are met. What are the two conditions?

   Answers:

   1. We should have well defined hash function that minimizes the collision.

   2. There should be proper load factoring and resizing to ensure that hash table is kept within a reasonable range.

3. What advantage, if any, is there to writing a function’s algorithm as comments inside the function prior to writing code?

   Answers:

   1. It helps to better understand the algorithm

   2. It helps to write code faster

   3. It helps the code reader to understand the algorithm even if they do not know the programming language and want to implement the code in other language.

4. Consider Sequential Search and Forgetful Binary Search. Which is better, and why? What limitations, if any, are there on these methods?

   Answers:

   1. Forgetful Binary search is better than sequential search because it’s big O notation is log(n) but sequential search is n so, forgetful binary search is a lot faster than sequential search.

   2. Sequential Search is Inefficient for large datasets, with a time complexity of O(n). The performance degrades linearly as the number of elements increases, making it impractical for extensive lists.

   3. Forgetful Binary Search requires the dataset to be sorted beforehand, which can add overhead.

5. Given the keys 345673, 768532, 093634, 532178, 234290, and 444444, show how these keys would be hashed using either mod division or pseudorandom number generation, and by one of digit extraction, folding, rotation or midsquare. Your table must have more than 100 slots.

   Answer:

   1. Mod division:

      1. if table size is more than 100 then let it be 101.

         so,

         Table Size (m) = 101

      2. Formula = Key % table size

         Key	hash
         345673	345673 % 101 = 51
         768532	768532 % 101 = 23
         093634	093634 % 101 = 7
         532178	532178 % 101 = 9
         234290	234290 % 101 = 71
         444444	444444 % 101 = 44

   2. Digit Extraction:

      1. Since table size is set for 101.

      2. Formula = sum of digits % table size (101)

         1. key1 = 3+4+5+6+7+3 = 28 % 101 = 28

         2. key2 = 7+6+8+5+3+2 = 31 % 101 = 31

         3. key3 = 0+9+3+6+3+4 = 25 % 101 = 25

         4. key4 = 5+3+2+1+7+8 = 26 % 101 = 26

         5. key5 = 2+3+4+2+9+0 = 20 % 101 = 20

         6. key6 = 4+4+4+4+4+4 = 24 % 101 = 24

6. Using mod 101 division, the keys 137, 238, 339, 440 and 541 all collide. Use your favorite collision resolution method to show where the keys would end up.

   Answer:

   all keys % 101 = 36, so we will be using linear probing

   0	empty
   1	empty
   …..	empty
   36	137
   37	238
   38	339
   39	440
   40	541
   41	empty
   …..	empty

Here, As all the keys collide at location 36, so we are using linear probing to solve the the collision. We look for the location that is available after the position at which the keys have collided and similarly check for other spaces available for other keys.

7. Show all output

Stack<int> s;

bool bSearch(int data[], int nItems, int key) {
	int low = 0, mid, high = nItems - 1;
	
	while (low < high){
		mid = (low + high) / 2;
		s.push(mid);

		if (key > data(mid)
			low = mid + 1;
		else
			high = mid;
	}

	if (key == data[low])
		return true;
	else 
		return false;
}

int main(void) {
	int num, data[] = {1, 4, 12, 13, 15, 18, 24, 33};

	if (bSearch(data,8,19))
		cout << "found" << endl;
	else
		cout << "not_found" << endl;

	while (!s.isEmpty()){
		num = s.pop();
		cout << num << endl;
	}
	
	return 0;
}