int BB(int n){
	if (n == 0) return 0;
	if (n == 1) return 1;
	if (n % 2) return 1 + BB(n / 2);
	return BB(n / 2);
}

n in Decimal	n in Binary	BB(n)
2	10	1
5	101	2
8	1000	1
13	1101	3
31	11111	5

b. What does BB compute?

BB(n) counts the number of ones in the binary expansion of n.

Problem 2: Consider the following code

void main(){
	int N = 100;
	int* A = new int[N];        		//a.
	for (int i = 0; i < N; i++)     	//b.
		A[i] = RandomLong(1, 1000); 

	cout << Search(A, 100, 500);     	//c.
}

int Search(int A[], int size, int key){  	//d.
	for (int i = 0; i < size; i++)
	if (A[i] == key) return i;
	return -1;
}

• a.( 2 points) What is A and why is it declared this way?
  A is a dynamic array of N integers. The memory is allocated from the heap at run-time so that N can be computed by the program. Here N is set in the previous line which is rather dull.

• b.( 2 points) What is the purpose of this loop?
  This loop sets each of the N items in the array A to a random integer between 1 and 1000.

• c.( 2 points) What possible values might be printed by this statement?
  What do they mean?
  -1 The number 500 is not a value in the array, A.
  0 .. 99 The number 500 is found as a value in A and it's first occurrence is at the position returned.

• d.(9 points) What are the minimum, maximum, and average number of compares executed when this function is called?

Explain your answers.

• minimum
  1 if A[0] = 500
  0 if size < 1, impossible with the call: Search(A, 100, 500);

• maximum
  100 or size if 500 is not a value in A
  or if the first occurrence of 500 is A[99].

• average
  50 or size/2 are acceptable answers

If we know that the values are chosen at random from 1 .. 1000, Brian Ciccolo points out that the following analysis applies:

The probability that 500 is not in A is (999/1000)¹⁰⁰ which is approximately 0.90
The probability that 500 is in A is 1 - (999/1000)¹⁰⁰ which is approximately 0.10
Then expected (average) number of compares is then:

1. 90*100 + 0.10*50 = 95.
   
   

Last Updated: April 27, 1997 10:15 pm by