(chapter4:solutions)=
# Solutions to the Practice Questions

(chapter4:solutions:orderNotation)=
## Order Notation
1. b, c, d, e, g (not a or f)
2. a, b, d, e, f (not c or g)
3. only d

[Back to Questions](chapter4:orderNotation:practice)

(chapter4:solutions:exampleDiffClasses)=
## An Example of Different Complexity Classes
1. Finding the maximum:
   ```{code-block} java
   /**
    * Returns the maximum integer in aList.
    * @param aList 1d array of integers
    * @return the maximum integer in aList.  If aList is empty this
    *         will throw an exception.
    */
    public static int findMax(int[] aList){
       int max = aList[0];
       for (int i = 0; i < aList.length; i++){
          if (aList[i] > max){
             max = aList[i];
          }
       }
       return max;
    }//findMax
    ```

2. If `aList` is of size $n$ elements, the worst number of key comparisons is $n$ (look at everything once).  This means that the run-time of `findMax` is in $θ(n)$.
3. Finding the maximum in a sorted list, ascending order:
   ```{code-block} java
   public static int findMax(int[] aList){
      return aList[aList.length - 1];
   }
   ```
4. The run-time of this algorithm is constant, i.e. in $θ(1)$.

5. We can’t do better than constant time.  Less than constant time would be zero time or negative time, but that means we are not running anything or going backwards in time.

[Back to Questions](chapter4:exampleDiffClasses:practice)

(chapter4:solutions:sevenFunctions)=
## The Seven Most Common Computing Efficiency Functions
1. a. Could figure this out by trying various values of `n`, e.g. 10, 11, 12, 13, 14. <br>
   Exact complexity is:

   $$ 
   C(n)=   \left\{
   \begin{array}{ll}
   n(\frac{n}{2}) & n \text{ is even}\\
   \frac{n(n+1)}{2} & n \text{ is odd} \\
   \end{array} 
   \right.
   =
    n \lfloor \frac{n+1}{2} \rfloor
   $$
   
   b. Order notation: $θ(n^2)$
   
2. a. Try various values of n to figure this out, e.g. n = 24, 25, 26, 124, 125, 126, 624, 625, 626. <br>
   Exact complexity is: $⌊\log _5 ⁡n ⌋+1+1=  ⌊\log _5⁡ n ⌋+2$ <br>
   b. Order notation: $θ(\log ⁡n)$

3. a. There are exactly two assignments to answer, each time, since $\frac{5}{n}$ is 0 for all $n > 10$. <br>
   Exact complexity is: 2 <br>
   b. Order notation: θ(1)

4. 
   ```
   Start:        [89, 12, 56, 24, 69]
   After pass 1: [12, 89, 56, 24, 69]
   After pass 2: [12, 24, 89, 56, 69]
   After pass 3: [12, 24, 56, 89, 69]
   After pass 4: [12, 24, 56, 69, 89]
   ```
5. 
   ```
   Start:        [10, 18, 21]
   After pass 1: [10, 18, 21]
   After pass 2: [10, 18, 21]
   ```
   
6. Size 10: 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 = 45 <br>
   Size n:  The first time through the inner loop, it executes n-1 times, therefore doing n-1 key comparisons.  The 2nd time it executes n-2 times, etc., until it ends with 1 key comparison.  This leads to the summation:
   
   $$
   \sum \limits_{i=1}^{n-1} i = \frac{(n-1)n}{2} = \frac{n^2 - n}{2}
   $$
   
7. One way to do this:
   ```{code-block} java
   /**
    * Returns true if the list contains a duplicate; false otherwise.
    * @param list - 1d array of integers
    * @return true if duplicate; false if unique
    */
   public static boolean hasDuplicate(int[] list){
      int current;
      for (int i = 0; i < list.length - 1; i++){
         current = list[i];
         for (int j = i + 1; j < list.length; j++){
            if (current == list[j]){
               return true;
            }//if
         }//for
      }//for
      return false;
   }//hasDuplicate
   ```
   Worst-case occurs when there are no duplicates.  The complexity is the same as for bubble sort (see question 6), which is  $\frac{(n-1)(n)}{2}$ key comparisons.  This algorithms runs in $θ(n^2)$.

8. 
   ```{code-block} java
   public static void selectionSort(int[] list){
      int len = list.length; //In Java, the length is available; no param required
      int counter = 0;
      int otherCount;
      int min;
      int minIndex;
    
      while (counter < len - 1){
         min = list[counter];
         minIndex = counter;
         otherCount = counter + 1;
        
         while (otherCount < len){
            if (list[otherCount] < min){ //new min found
               min = list[otherCount];
               minIndex = otherCount;
            }
            otherCount++;
         }
        
         // Exchange
         list[minIndex] = list[counter];
         list[counter] = min;
        
         counter++;
      }
   }
   ```
9. 
    ```
    Original: {98, 12, 32,  3,  7, 19, 54, 87}
    Pass 1:   { 3, 12, 32, 98,  7, 19, 54, 87}
    Pass 2:   { 3,  7, 32, 98, 12, 19, 54, 87}
    Pass 3:   { 3,  7, 12, 98, 32, 19, 54, 87}
    Pass 4:   { 3,  7, 12, 19, 32, 98, 54, 87}
    Pass 5:   { 3,  7, 12, 19, 32, 98, 54, 87}
    Pass 6:   { 3,  7, 12, 19, 32, 54, 98, 87}
    Pass 7:   { 3,  7, 23, 19, 32, 54, 87, 98}
    ```
11. In $\theta (n^2)$
12. 
    ```{code-block} java
    public static void insertionSort(int[] list){
       int len = list.length;
       int counter = 1;
       int newElement;
       int location;
    
       while (counter < len){
          newElement = list[counter];
          location = counter - 1;
        
           while (location >= 0 && list[location] > newElement){
              list[location + 1] = list[location];
              location--;
           }
        
           list[location + 1] = newElement;
           counter++;
       }
    }
    ```
13. 
    ```
    Original: {98, 12, 32,  3,  7, 19, 54, 87}
    Pass 1:   {12, 98, 32,  3,  7, 19, 54, 87}
    Pass 2:   {12, 32, 98,  3,  7, 19, 54, 87}
    Pass 3:   { 3, 12, 32, 98,  7, 19, 54, 87}
    Pass 4:   { 3,  7, 12, 32, 98, 19, 54, 87}
    Pass 5:   { 3,  7, 12, 19, 32, 98, 54, 87}
    Pass 6:   { 3,  7, 12, 19, 32, 54, 98, 87}
    Pass 7:   { 3,  7, 12, 19, 32, 54, 97, 98}
    ```
14. In $\theta (n^2)$

[Back to Questions](chapter4:sevenFunctions:practice)

<br><br>