Homework 1

This assignment is due Tuesday, September 16, by the start of class.

Exercises from Chapter 9 of the text (pp. 477-479):

• Exercise 1, parts (a), (b), (e), and (g). For part (g), assume that the array is already sorted.

• Exercise 2.

• Exercise 3.

• Exercise 9. For each sort and each array of numbers, count the number of comparisons between array elements and the number of times a value from the array is copied from one location to another (so each swap involves three copy operations: copy a to the temp, copy b to a, and copy the temp to b). Comment on the relative performance of the algorithms.

• Exercise 10.

Additional problems:

1. Write two program fragments labeled (A) and (B) such that (A) has a "better" run-time when expressed in big-oh notation but takes longer to run for a small input (say an input size of 10).

2. What is the run-time of the following fragment expressed in big-oh notation as a function of its input n?

   cin >> n;
   for (int i=1; i <=n+6; i++)
      for (int j=1; j<=n+10; j++)
         cout << i * j << endl;
   for (int k=1; k <= n+1000; k++)
         cout << "Hello" << end;
   

3. If a piece of code runs in time O(N²) and takes 2 minutes to run when N is 10,000 how long would you estimate the fragment would take to run when N=40,000? Why is your answer only an estimate?

4. If a piece of code runs in time O(N³) and takes 2 minutes to run when N is 10,000 how long would you estimate the fragment would take to run when N=30,000?

5. What is the run-time of the following fragment expressed in big-oh notation as a function of its input n?

   cin >> n;
   for ( i=1; i<=n; i++ )
   {  temp = n;
      while ( temp > 0 )
      {  cout << n * temp << endl;
         temp = temp / 2;
      }
   }