CSC 122: Computer Science II, Fall 2006

Exam 1 Sample Questions and Solutions

1. Consider the following array:
   

   16

   8

   11

   4

   5

   2

   9

   13

   
   Show the results of running selection sort on this array. Show the first two passes through selection sort.
   

   2	8	11	4	5	16	9	13
   2	4	11	8	5	16	9	13

2. Show the results of running bubble sort on the original array from question #1. Show the results of the first two passes.
   

   8	11	4	5	2	9	13	16
   8	4	5	2	9	11	13	16

3. Answer the following questions about sorting. For all parts, assume that running time includes comparisons between items in the array and swaps or assignments for values in the array.
   1. Show an array that would result in the best running time for bubble sort.
      

      2

      4

      6

      8

      10

      12

   2. Show an array that would result in the worst running time for insertion sort.
      

      9

      8

      7

      6

      5

      4

4. Consider the following code fragment:

   for ( int i = 0; i < n - 1; i++ ) {
       for ( int j = 0; j < n - 1; j++ ) {
           System.out.println( "Hello!" );
       }
   }
   

   How many "Hello!"s are printed? Give an exact answer (in terms of n) as well as an answer in O( ) notation.

   Exact: (n-1)*(n-1)
   O(n²)
5. What is the O( ) of the following expressions? Explain your answers.
   1. n³ + 10n² + 100n + 1000
      
      O(n³)
   2. n lg n + n² + 10
      
      O(n²)

6. You have a problem for which you are considering two different algorithms, named A and B. It is known that the running time of A is O(n²), while the running time of B is O(n³). Running the two algorithms on some test data, where n is 1000, reveals that both take about the same amount of time. If the real data size is more like 100,000 items, which algorithm will be the better choice, and by how much?

   Increasing the size of the data by a factor of 100 will increase the running time of A by a factor of 100²=10,000, while the running time of B will go up by more like 100³=1,000,000. Therefore, algorithm B will take roughly one hundred times as long to run as the better choice, A.

7. Consider the following function.

   public void mystery( int n, int m ) {
     if ( m > n ) {
       System.out.print( m + " " );
       mystery( m – 1, n );
     }
     else if ( m < n ) {
       System.out.print( n + " " );
       mystery( m + 1, n );
     }
     else
       System.out.println( "Done" );
   }
   

   What is the output for each of the following method calls:

   1. mystery( 1, 3 )?
      3 2 Done
   2. mystery( 3, 3 )?
      Done
   3. mystery( 5, 3 )?
      5 5 Done
   4. mystery( 1, 5 )?
      5 4 4 3 Done

8. Write a Java method called printStars that takes one integer parameter called n. The method should display a single line of n stars ('*') on the screen. To receive full credit, the function must be written recursively. Little to no credit will be given for a non-recursive solution. For example, printStars( 5 ) would print ***** to the screen.

   public void printStars(int n)
   {
       if (n>0) {
           System.out.print("*");
           printStars(n-1);
       }
       System.out.println();
   }
   	

9. Write a Java method called calcProduct that takes two integer parameters, m and n. The method should return the product of all the integers from m to n inclusive. To receive full credit, the method must be written recursively. Little to no credit will be given for a non-recursive solution. For example, calcproduct( 5, 3 ) should return 60 (5 x 4 x 3). You cannot assume that the parameters are in any particular order.

   public int calcProduct(int m, int n)
   {
       int prod;
       if (m == n) {
           prod = m;
       }
       else if(m < n) {
           prod = m * calcProduct(m+1, n);
       }
       else {
           prod = n * calcProduct(m, n+1);
       }
       return prod;
   }
   	

Questions, short answer and otherwise, could also be asked about the following topics:

• Greedy algorithms
• Divide-and-Conquer algorithms
• The advantages of Unit Testing
• Searching
• O(n log n) sorting algorithms
• Loop invariant (informal)

The exam will be closed-book, closed-notes. It will be designed to be completed in 1 hour. It will be held Wednesday, September 27, in class.

DePauw University, Computer Science Department, Fall 2006
Maintained by Brian Howard (bhoward@depauw.edu). Last updated