Algorithms for Searching, Sorting, and Matrix Operations

[Document title]
|

Searching Problem:
1. Input: an array A [1...n] of n elements and a value v.
Output: an index I such that A[i] =v or the special value NIL if v does not appear in A.
Assuming that array A is sorted (in ascending order):
(a) Write pseudo-code for an iterative binary search algorithm, looking for v. Show that the
running time of your algorithm is Θ (lg n).
Answer:
#include <stdio.h>
int binarySearch(int arr[], int v, int r, int x){
while (m<= r)
{
int v = m + (r-v)/2;
if (arr[v] == x)
return v;
if(arr[v] < x)
I =v+1;
else
r = v-1;
}
return -1;
}
(b) Write pseudo-code for a recursive binary search algorithm, looking for v. Show that the
running time of your algorithm is Θ(lg n)
Answer:
#include <stdio.h>
int binarySearch(int arr[], int v, int r, int x){
if(r>v){
int mid = v+(r-v)/2;
if(arr[mid]==x)
return mid;
pg. 1

if (arr[mid]>x)
return binarySearch(arr,v,mid-1,x);
return binarySearch(arr,v,mid-r,x);
}
return -1;
}
2. Draw the 13-entry hash table that results from using the hash function h(i) = (3 I + 5) mod 13
to hash the keys 14, 42, 15, 81, 27, 92, 3, 39, 20, 16, and 5, assuming collisions are handled by:
(a) separate chaining;
(b) linear probing.
0 1 2 3 4 5 6 7 8 9 10 11 12
14 42 15 81 27 92 3 39 non
e
none 20 16 5
(c) quadratic probing (up to the point where the method fails).
pg. 2