Chapter 2
1: Use recursive Binary Search to search for the integer 120 in the following list (array)
of integers.
#include <iostream>
using namespace std;
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l)/2;
if (arr[mid] == x)
return mid;
if (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
int main(void) {
int array[] = {12, 34, 37, 45, 57, 82, 99, 120, 134};
int n = sizeof(array)/ sizeof(array[0]);
int x = 120;
int result = binarySearch(array, 0, n-1, x);
cout << "Result: " << result << endl;
return 0;
}
2: Suppose that, even unrealistically, we are to search a list of 700 million items
using recursive Binary Search. What is the maximum number of comparisons that this
algorithm must perform before finding a given item or concluding that it is not in the
list?
log2(700,000,000) = 30
3: Let us assume that we always perform a successful search. That is, the item x can
always be found in the list S. Improve Algorithm 2.1 by removing all unnecessary
operations.
int binarySearch(int arr[], int l, int r, int x) {
if (r >= l) {
int mid = l + (r - l)/2;
if (arr[mid] == x)
return mid;
else (arr[mid] > x)
return binarySearch(arr, l, mid-1, x);
else
return binarySearch(arr, mid+1, r, x);
}
return -1;
}
4: Show that the recurrence equation for W(n) is given by
W(n) = 1 + W((n/2))
W(1) = 1.
To do this, consider even and odd values of n separately. Then use induction to solve
the recurrence equation.
The array is split into two equal subarrays of size m = n/2 each. The mid is
(low+high)/2, which is the right-most element of the left array. When you have the
worst case scenario, there will be n/2 elements for the next level of the recursion.
So n/2 + 1
If n = 1, there will only be the comparison (x=S[mid]) (W(1)=1)
5: Suppose that, in Algorithm 2.1 (line 4), the splitting function is changed to
mid = low. Explain the new search strategy. Analyze the performance of this strategy
and show the results using order notation.
int binarySearch(int array[], int first, int last, int x) {
int middle;
if (first > last) {
return 0;
}
else {
middle = first;
if (x == array[middle])
return middle;
else if (x < array[middle])
return array(first, middle-1, x);
else
return array(middle+1, last, x);
}
}
This algorithm turns into an Linear Search.
6: Write an algorithm that searches a sorted list of n items by dividing it into three
sublists of almost n/3 items. This algorithm finds the sublist that might contain the
given item and divides it into three smaller sublists of almost equal size. The
algorithm repeats this process until it finds the item or concludes that the item is
not in the list.
int search(int array[], int first, int last, int location) {
int x, x2;
if (first > last)
return 0;
else {
x = first + (last-first)/3;
x2 = first + 2*(last-first)/3;
if (location == array[x]) {
return x;
}
else if (location < array[x]) {
return search(array, first, x-1, location);
}
else if (location < array[x2])
return search(array, x+1, x2-1, location);
else if (location == array[x2])
return x2;
else
return search(array, x2+1, last, location);
}
}
7: Use the divide-and-conquer approach to write an algorithm that finds the largest item
in a list of n items.
int findMax(int array[], int first, int last) {
if (first==last)
return array[first];
int middle = (first+last)/2;
int x = findMax(first, last);
int x2 = findMax(middle + 1, last);
if array[x] > array[x2]
return x;
else
return x2;
}
8: Use Mergesort to sort the following list.
123 34 189 56 150 12 9 240
#include <iostream>
using namespace std;
void mergeSort(int *, int, int);
void merge(int *, int, int, int);
int main(int argc, const char * argv[]) {
int size = 6;
int i;
int arr[] = {123, 34, 189, 56, 150, 12, 9, 240};
mergeSort(arr, 0, size);
for (i = 0; i < size; i++)
cout<< arr[i] << endl;
return 0;
}
void mergeSort(int *array, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
mergeSort(array, low, mid);
mergeSort(array, mid+1, high);
merge(array, low, high, mid);
}
}
void merge(int *array, int low, int high, int mid) {
int i, j, k;
int A[high-low+1];
i = low;
k = 0;
j = mid + 1;
while (i <= mid && j <= high) {
if (array[i] < array[j])
{
A[k] = array[i];
k++;
i++;
}
else
{
A[k] = array[j];
k++;
j++;
}
}
while (i <= mid) {
A[k] = array[i];
k++;
i++;
}
while (j <= high) {
A[k] = array[j];
k++;
j++;
}
for (i = low; i <= high; i++) {
array[i] = A[i-low];
}
}
9: Give the tree of recursive calls in Exercise 8
(low=1, high=8)
/ \
/ \
/ \
(low=1, high=4) (low=5, high=8)————(low=7,high=8) ——— (8,8)
/ \ / \
/ \ / \
/ \ (low=5, high=6) (7,7)
(low=1, high=2) (low=3, high=4) / \
/ \ / \ / \
/ \ / \ (1,2) (6,6)
(1, 2) (2,2) (3,3) (4,4)
11: Write an Mergesort algorithm
#include <iostream>
using namespace std;
void mergeSort(int *, int, int);
void merge(int *, int, int, int);
int main(int argc, const char * argv[]) {
int size = 6;
int i;
int arr[] = {12, 13, 3, 9, 4, 1};
mergeSort(arr, 0, size);
for (i = 0; i < size; i++)
cout<< arr[i] << endl;
return 0;
}
void mergeSort(int *array, int low, int high)
{
int mid;
if (low < high)
{
mid=(low+high)/2;
mergeSort(array, low, mid);
mergeSort(array, mid+1, high);
merge(array, low, high, mid);
}
}
void merge(int *array, int low, int high, int mid) {
int i, j, k;
int A[high-low+1];
i = low;
k = 0;
j = mid + 1;
while (i <= mid && j <= high) {
if (array[i] < array[j])
{
A[k] = array[i];
k++;
i++;
}
else
{
A[k] = array[j];
k++;
j++;
}
}
while (i <= mid) {
A[k] = array[i];
k++;
i++;
}
while (j <= high) {
A[k] = array[j];
k++;
j++;
}
for (i = low; i <= high; i++) {
array[i] = A[i-low];
}
}
12: Show that the recurrence equation for the worst-case time complexity for MergeSort is
given by W(n) = W(n/2) + W(n/2) + n - 1
Merge Comparisons
The time to sort an local array in merge is W(A).
The time to sort another local array is W(B)
The time to merge is high+middle-1
W(n) = W(A) + W(B) + high+middle-1
Since we are splitting the array in half we get
high = n/2 (One half)
m = n-h = n/2
h+m = n/2+n/2 = n
So W(n) = W(n/2) + W(n/2) + n-1
13: Given the recurrence relation
T(n) = 7T(n/5)+10n for n>1
T(1) = 1
Find T(625)
7*625*(n/5)+10n
4375*(n/5)+10n
14: Consider algorithm solve given below. This algorithm solves problem P by finding the
output (solution) O corresponding to any input I.
void solve(input I, output& O) {
if (size(1) == 1)
find solution O directly;
else {
partition I for 5 inputs I1, I2, I3, I4, I5, where
size(Ij) = size(I)/3 for j = 1,…, 5;
for (j = 1; j <= 5; j++)
solve(Ij,Oj);
combine O1, O2, O3, O4, O5 to get O for P with input I;
}
}
Assume g(n) basic operations for partitioning and combining and no basic operations
for an instance of size 1.
(a) Write a recurrence equation T(n) for the number of basic operations needed
to solve P when the input size is n.
15: Suppose that, in a divide-and-conquer algorithm, we always divide an instance of size
n of a problem into 10 substances of size n/3, and the dividing and combining steps
take a time in Theta(n^2). Write a recurrence equation for the running time T(n),
and solve the equation for T(n).
10 instances of T(n/3)
T(n) = 10*T(n/3) + cn^2
n is a power of 3
n = 3^k
T(3^k) = 10*T((3^k)/3) + c9^k
T(3^k) = 10*T(3^(k-1)) + c9^k
Roots: 9, 10
x_k=T(3^k)
x_k=10*x_(k-1) + C*9^K
k = 1
C9^k = 9C
x_k = 9C(10^k-9^k)
16: Write a divide-and-conquer algorithm for the Towers of Hanoi problem. The Towers of
Hanoi problem consists of three pegs and n disks of different sizes. The object
is to move the disks that are stacked, in decreasing order of their size, on one of
the three pegs to a new peg using the third one as a temporary peg. The problem should
be solved according to the following rules:
(1) When a disk is moved, it must be placed on one of the three pegs
(2) Only one disk may be moved at a time, and it must be the top disk on one of the
pegs;
(3) A larger disk may never be placed on top of a smaller disk.
(a) Show for your algorithm that S(n)=2^n - 1.(Here S(n) denotes the number of steps
(moves), given an input of n disks.)
void Hanoi(int n, int x, int y, int z) {
if (n > 0) {
Hanoi(n-1, x, y, z);
cout << x << “moves to ” << y << ends;
Hanoi(n-1, z, y, x);
}
}
T(n) = 2T(n-1) + 1, T(1) = 1
If you start substituting you will get T(n) = 2^(n-1) + 2^(n-2) + 2^(n-3)
By using the sum of the geometric series you get 2^n - 1
(b) Prove that any other algorithm takes at least as many moves as given in part (a).
To move the largest disk, an algorithm must first place disks 1 to n-1 on the
middle peg, then at least move the large disk on the destination peg. Then move
the disks on destination peg.
