LAB 5: Search+H ash+Graph

EX1:
Implement function
int binarySearch(int arr[], int left, int right, int x)
to search for value x in array arr using recursion.
After traverse an index in array, we print out this index using cout << "We traverse on index: " << index <<
endl;
Note that middle of left and right is floor((right-left)/2)
For example:

Test Result

int arr[] = {1,2,3,4,5,6,7,8,9,10}; We traverse on index: 4

int x = 10; We traverse on index: 7
int n = sizeof(arr) / sizeof(arr[0]); We traverse on index: 8
int result = binarySearch(arr, 0, n - 1, x); We traverse on index: 9
(result == -1) ? cout << "Element is not present in array" Element is present at
: cout << "Element is present at index " index 9
<< result;

int binarySearch(int arr[], int left, int right, int x)

{
int mid = 0;
if (right >= left){
mid = left + (right-left)/2;
cout<<"We traverse on index: "<<mid<<endl;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, left, mid-1,x);
return binarySearch(arr,mid+1,right,x);
}
return -1;
}

EX2:
Given an array of distinct integers, find if there are two pairs (a, b) and (c, d) such that a+b = c+d,
and a, b, c and d are distinct elements. If there are multiple answers, you can find any of them.
Some libraries you can use in this question:
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
#include <algorithm>
#include <iostream>
#include <utility>
#include <map>
#include <vector>
#include <set>
Note: The function checkAnswer is used to determine whether your pairs found is true or not in
case there are two pairs satistify the condition. You don't need to do anything about this function.

For example:

Test Result

int arr[] = { 3, 4, 7, 1, 2, 9, 8 }; Your answer is correct.

int n = sizeof arr / sizeof arr[0];
pair<int, int> pair1, pair2;
if (findPairs(arr, n, pair1, pair2)) {
if (checkAnswer(arr, n, pair1, pair2)) {
printf("Your answer is correct.\n");
}
else printf("Your answer is incorrect.\n");
}
else printf("No pair found.\n");

int arr[] = { 3, 4, 7 }; No pair found.

int n = sizeof arr / sizeof arr[0];
pair<int, int> pair1, pair2;
if (findPairs(arr, n, pair1, pair2)) {
if (checkAnswer(arr, n, pair1, pair2)) {
printf("Your answer is correct.\n");
}
else printf("Your answer is incorrect.\n");
}
else printf("No pair found.\n");

bool findPairs(int arr[], int n, pair<int,int>& pair1, pair<int, int>&

pair2)
{
// TODO: If there are two pairs satisfy the condition, assign their
values to pair1, pair2 and return true. Otherwise, return false.
map<int, pair<int,int>> hash;
for (int i=0;i<n;++i){
for (int j=i+1;j<n;++j){
 int sum = arr[i] + arr[j];
if (hash.find(sum) == hash.end())
hash[sum] = make_pair(i,j);
else{
pair<int,int> prevPair = hash[sum];
pair1.first = arr[prevPair.first];
pair1.second = arr[prevPair.second];
pair2.first = arr[i];
pair2.second = arr[j];
return true;
}
}
}
return false;
}

EX3:
Implement function
int foldShift(long long key, int addressSize);
int rotation(long long key, int addressSize);
to hashing key using Fold shift or Rotation algorithm.
Review Fold shift:
The folding method for constructing hash functions begins by dividing the item into equal-size
pieces (the last piece may not be of equal size). These pieces are then added together to give the
resulting hash value.
For example:

Test Result

cout << rotation(600101, 2); 26

int foldShift(long long key, int addressSize)

{
string strKey = to_string(key);
size_t L = strKey.length();
int sum = 0, piece = 0;
for (size_t i=0; i<L;){
int j=0;
string strPiece = "";
while (j<addressSize){
 strPiece += strKey[i];
i++;
j++;
}

piece = stoi(strPiece);
sum += piece;
}
string strSum = to_string(sum);
size_t L1 = strSum.length();
string result = strSum.substr(L1-addressSize,addressSize);
return stoi(result);
}
int rotation(long long key, int addressSize)
{
string strKey = to_string(key);
size_t L = strKey.length();
string rotation = "";
rotation += strKey[L-1];
strKey = strKey.substr(0,L-1);
rotation += strKey;
return foldShift(stoll(rotation),addressSize);
}

EX4:
Implement function

int interpolationSearch(int arr[], int left, int right, int x)

to search for value x in array arr using recursion.

After traverse to an index in array, before returning the index or passing it as argument to recursive
function, we print out this index using cout << "We traverse on index: " << index << endl;
Please note that you can't using key work for, while, goto (even in variable names, comment).

For example:

Test Result

int arr[] = { 1,2,3,4,5,6,7,8,9 }; We traverse on index: 2

int n = sizeof(arr) / sizeof(arr[0]); Element is present at
int x = 3; index 2
int result = interpolationSearch(arr, 0, n - 1, x);
(result == -1) ? cout << "Element is not present in
array"
: cout << "Element is present at index "
<< result;

int arr[] = { 1,2,3,4,5,6,7,8,9 }; Element is not present in

int n = sizeof(arr) / sizeof(arr[0]); array
int x = 0;
int result = interpolationSearch(arr, 0, n - 1, x);
(result == -1) ? cout << "Element is not present in
array"
: cout << "Element is present at index "
<< result;

int interpolationSearch(int arr[], int left, int right, int x)

{
int pos = 0;
if (right >= left && x>=arr[left] && x<=arr[right]){
pos=left+ ((x-arr[left])*(right-left))/(arr[right]-arr[left]);
if (pos >=0)
cout << "We traverse on index: " << pos << endl;
if (arr[pos] == x)
return pos;
if (arr[pos] < x)
return interpolationSearch(arr,pos+1,right,x);
if (arr[pos] > x)
return interpolationSearch(arr,left,pos-1,x);
}
return -1;
}
 Test Expected Got

int arr[] = { 1,2,3,4,5,6,7,8,9 }; We traverse on We traverse on

int n = sizeof(arr) / sizeof(arr[0]); index: 2 index: 2
int x = 3; Element is present Element is
int result = interpolationSearch(arr, 0, at index 2 present at index
n - 1, x); 2
(result == -1) ? cout << "Element is not
present in array"
: cout << "Element is
present at index " << result;

int arr[] = { 1,2,3,4,5,6,7,8,9 }; Element is not Element is not

int n = sizeof(arr) / sizeof(arr[0]); present in array present in array
int x = 0;
int result = interpolationSearch(arr, 0,
n - 1, x);
(result == -1) ? cout << "Element is not
present in array"
: cout << "Element is
present at index " << result;
Passed all tests!

EX5:
In computer science, a jump search or block search refers to a search algorithm for ordered lists. The basic idea
is to check fewer elements (than linear search) by jumping ahead by fixed steps or skipping some elements in
place of searching all elements. For example, suppose we have an array arr[] of size n and block (to be
jumped) size m. Then we search at the indexes arr[0], arr[m], arr[2m]…..arr[km] and so on. Once we find the
interval (arr[km] < x < arr[(k+1)m]), we perform a linear search operation from the index km to find the
element x. The optimal value of m is √n, where n is the length of the list.

In this question, we need to implement function jumpSearch with step √n to search for value x in array arr.
After searching at an index, we should print that index until we find the index of value x in array or
until we determine that the value is not in the array.

int jumpSearch(int arr[], int x, int n)

int jumpSearch(int arr[], int x, int n) {
 // TODO: print the traversed indexes and return the index of value x
in array if x is found, otherwise, return -1.
int step = sqrt(n);
int index = 0;
while (index < n){
cout<<index<<' ';
if (arr[index] == x) return index;
else if (arr[index] < x) index += step;
else break;
}
for (int i=index - step + 1; i<index; i++){
cout<<i<<' ';
if (arr[i]==x) return i;
}
if (arr[index]==x){
cout<<index<<' ';
return index;
}
return -1;

}
Test Expected Got

int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 0 4 8 12 9 10 0 4 8 12 9

89, 144, 233, 377, 610 }; Number 55 is 10
int x = 55; at index 10 Number 55 is
int n = sizeof(arr) / sizeof(arr[0]); at index 10
int index = jumpSearch(arr, x, n);

if (index != -1) {
cout << "\nNumber " << x << " is at index " <<
index;
}
else {
cout << "\n" << x << " is not in array!";
}

int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 0 4 8 12 0 4 8 12

89, 144, 233, 377, 610 }; Number 144 is Number 144
int x = 144; at index 12 is at index
int n = sizeof(arr) / sizeof(arr[0]); 12
int index = jumpSearch(arr, x, n);

if (index != -1) {
cout << "\nNumber " << x << " is at index " <<
index;
}
else {
cout << "\n" << x << " is not in array!";
}

int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 0 4 8 12 16 0 4 8 12 16

89, 144, 233, 377, 610, 611, 612, 613 }; 17 17
int x = 612;
 Test Expected Got

int n = sizeof(arr) / sizeof(arr[0]); Number 612 is Number 612

int index = jumpSearch(arr, x, n); at index 17 is at index
17
if (index != -1) {
cout << "\nNumber " << x << " is at index " <<
index;
}
else {
cout << "\n" << x << " is not in array!";
}

int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 0 4 8 12 16 0 4 8 12 16

89, 144, 233, 377, 610, 611, 612, 613 }; 17 18 19 17 18 19
int x = 614; 614 is not in 614 is not
int n = sizeof(arr) / sizeof(arr[0]); array! in array!
int index = jumpSearch(arr, x, n);

if (index != -1) {
cout << "\nNumber " << x << " is at index " <<
index;
}
else {
cout << "\n" << x << " is not in array!";
}

int arr[] = { 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 0 5 10 6 7 8 0 5 10 6 7 8

89, 144, 233, 377, 610, 611, 612, 613, 1000, 1002, 9 9
2000, 2003, 2004, 2005, 2006 }; 36 is not in 36 is not in
int x = 36; array! array!
int n = sizeof(arr) / sizeof(arr[0]);
int index = jumpSearch(arr, x, n);

if (index != -1) {
cout << "\nNumber " << x << " is at index " <<
index;
}
else {
cout << "\n" << x << " is not in array!";
}
Passed all tests!

EX6:
Implement three following hashing function:
long int midSquare(long int seed);
long int moduloDivision(long int seed, long int mod);
long int digitExtraction(long int seed, int* extractDigits, int size);
Note that:
In midSquare function: we eliminate 2 last digits and get the 4 next digits.
In digitExtraction: extractDigits is a sorted array from smallest to largest index of digit in seed (index starts
from 0). The array has size size.
For example:

Test Result

int a[]={1,2,5}; 223

cout << digitExtraction(122443,a,3);

cout <<midSquare(9452); 3403

long int midSquare(long int seed)

{
long int square = seed*seed;
string str = to_string(square);
size_t L = str.length();
str = str.substr(0, L-2);
str = str.substr(L-6,4);
return stol(str);
}
long int moduloDivision(long int seed, long int mod)
{
return seed%mod;
}
long int digitExtraction(long int seed,int* extractDigits,int size)
{
string res = "";
string digit ="";
string seedStr = to_string(seed);
for (int i=0; i<size;i++){
digit = seedStr[extractDigits[i]];
res += digit;
}
return stol(res);
}