Activity Sheet 3

Manager

name:

Recorder

name:

Speaker

name:

Section 2.3

1. The following algorithm determines if an array of numbers is sorted:

   // Input: A[0, ..., n-1]
   // Output: true or false depending on whether the array is sorted
   // Variables used: i  -- loop index
   for i = 2, ..., n-1:
     if A[i-1] > A[i]:
       return false
   return true

   1. The algorithm has one mistake in it. Correct it.
   2. Determine the input size and the basic operation for this algorithm.
   3. Compute the algorithm’s time efficiency.

Section 2.4

2. The following algorithm determines the number of ones in the binary representation of a number \(n\):

   ALGORITHM ones(n)
     // Input: n   --- a nonnegative integer
     // Output: The number of ones in the binary representation of n
     if n <= 1:
       return n       // n is 0 or 1
     else:
       lastDigit = n mod 2        // lastDigit=1 if n is odd, lastDigit = 0 if n is odd
       otherDigits = ones(n / 2)  // integer division here
       return lastDigit + otherDigits

   1. Demonstrate a run of this algorithm for n = 11, and confirm that it works in that instance.
   2. Determine the basic operation for this algorithm.
   3. Establish a recurrence relation for the running time of this algorithm.
   4. Use the method of backward substitutions on this recurrence to compute the running time.