CS 112 Summer I, 2017-- Homework Three -- Part A Solutions

 

  1. For each function f from the following list of functions, determine which g makes the equality f(x) = ϴ(g(x)) true. The point of representing a function in this form is to create the simplest possible function g(x), e.g., do not include a coefficient in g(x), since it does not matter. Represent your answer as an equality (e.g., p(x) = ϴ(n2)). To be clear, the correct answer to the first function is shown.

    a(x) = 8x + 3 = ϴ(x)
    b(x) = 12x + x2 + 64
    c(x) = 2log(x) + x
    d(x) = log(x) + 2
    e(x) = sqrt(2x)

    Solution:
    a(x) = 8x + 3           = ϴ(x)     // already given
    b(x) = 12x + x^2 + 64   = ϴ(x^2)
    c(x) = 2log(x) + x      = ϴ(x)
    d(x) = log(x) + 2       = ϴ(log(x))
    e(x) = sqrt(2x) = sqrt(2) * sqrt(x)   = ϴ(sqrt(x))
      
  2. Using ϴ(....) notation, determine the number of times the count() function is called when the following code fragment runs, in terms of the variable n.

    for (int i = 0; i < n; i++)
        for (int j = 0; j < n; j++)
            for (int k = 0; k < j; k++)
                count();
    

    Include a short explanation of your answer by explaining how many times each loop iterates.

        Solution:
        
        The inner two for loops are essentially the same as in Selection sort (upper triangle of a 
        square with side n), so Theta(n^2); the outer loop runs n times, so Theta(n^2) * n = Theta(n^3). 
        
  3. Using ϴ(....) notation, determine the number of times the count() function is called when the following code fragment runs, in terms of the variable n.

    for (int i = n; i > 0; i /= 2)
       for (int j = 0; j < n; j++)
           for (int k = 0; k < 1000; k++)
               count();
    

    Include a short explanation of your answer by explaining how many times each loop iterates.

        Solution:
        
        The outer loop divides i in half each time, and you can divide a number in half at most Theta( log(n) ) times;
        The second loop runs n times;
        The inner loop runs 1000 times;
        So Theta( log(n) ) * n * 1000  =   Theta( n * log(n) ) 
        
  4. Perform this code for insertion sort on the following input array, showing the array after every swap.

    public static void insertion(int[] arr) {
        for (int i = 1; i < arr.length; i++) {
            for (int j = i; j > 0; j--) {
                if (arr[j] < arr[j - 1])
                    swap(arr, j, j - 1);
                    // show array here
            }
        }
    }
    

    Execute the algorithm on the following input:

  5. +-------------------+
    | 3 | 5 | 8 | 2 | 1 | 
    +-------------------+
    
    Solution:
    
    3 5 8 2 1 	        original array
                       3 < 5 < 8 so no swapping
    3 5 8 * 2 1        section to left of * is sorted, now inserting 2 into sorted part
    3 5 2 8 * 1        swap 2 and 8  
    3 2 5 8 * 1 swap 2 and 5
    2 3 5 8 * 1 swap 2 and 3; 2 is in proper place, now will insert 1
    2 3 5 1 8 * etc.
    2 3 1 5 8 *
    2 1 3 5 8 *
    1 2 3 5 8 * done!
  6. Perform selection sort on the following input array, showing the array after each swap.

    public static void selection(int[] arr) {
        int k;
        for (int i = 0; i < arr.length; i++) {
            k = i;
            for (int j = i + 1; j < arr.length; j++) {
                if (arr[j] < arr[k])                            
                    k = j;
            }
            swap(arr, i, k);
            // show array here
        }
    }
    

    Execute the algorithm on the following input:

    +-------------------+
    | 9 | 6 | 4 | 2 | 3 |
    +-------------------+
    
    Solution:
    
    9 6 4 2 3        original array
    
    2 * 6 4 9 3 find min 2, swap with 9
    2 3 * 4 9 6 find min 3, swap with 6
    2 3 4 * 9 6 find min 4, swap with 4 (ha!)
    2 3 4 6 * 9 find min 6, swap with 9
    2 3 4 6 9 * find min 9, swap with 9 (ha!
    2 3 4 6 9 done!
  7. Now perform merge sort on the following input array, showing each subarray after it is merged with another subarray (you will sort all sublists of size 1, then of size 2, and finally of size 4).

    +-------------------------------+ 
    | 9 | 5 | 3 | 2 | 1 | 8 | 7 | 4 | 
    +-------------------------------+ 
    
    Solution:
    [9, 5, 3, 2, 1, 8, 7, 4]        (input array)
     -  -  -  -  -  -  -  -         (subproblems of size 1)
    
    [5, 9,                          (subproblems of size 2)
     ---- 
           2, 3,                    
           ----
                 1, 8,
                 ---- 
                       4, 7]
                       ----  
    
    [2, 3, 5, 9,                     (subproblems of size 4)
     ---------- 
                 1, 4, 7, 8]
                 ----------
    
    [1, 2, 3, 4, 5, 7, 8, 9]         done!
     ----------------------