Exam 1 Answers: Section 03

1. T
2. F
3. F
4. C
5. C
6. A
7. C
8. B
9. 1. O(N²)
   2. O(NlogN)
   3. O(1)



10. Output:
    9
    4
    8
    17
    25
    32
    32

    
11. 1. 1. N+1
       2. N
       3. N
       4. N
       5. N(N+1)
       6. N²
       7. N
    2. O(N²)
    3. 1. N+1
       2. N
       3. N
       4. N
       5. 0
       6. 0
       7. N
    4. O(N)
    
    

12. 

    cello
    bass
    flute
    oboe
    

13.    public boolean same(LinkedStack<T> two)  {
          LLNode<T> temp = top;
          LLNode<T> tempTwo = two.top;
          boolean equal = true;
          while (temp != null && tempTwo != null) {
             if (!temp.getInfo().equals(tempTwo.getInfo())
                equal = false;
             temp = temp.getLink();
             tempTwo = tempTwo.getLink();
          }
          if (temp == null && tempTwo != null)
             equal = false;
          if (temp != null && tempTwo == null)
             equal = false;
          return equal;
       }
    

14. The worst and best case have the same big O since the method has to loop through every node in both stacks to check whether every item is the same. If there are M items in this and P items in two the stack then it has to access M + P items. M and P are the size of the stacks, so if we simplify and consider them the same size, then we get 2N, where N is the size of the stacks. This gives us O(N).

15. 1.    public String toString() {
             String disk = manufacturer + "   " + model + "   ";
             if (mag)
                disk = disk + "magnetic   " + size + "GB";
             else
                disk = disk + "SSD        " + size + "GB";
             return disk;
          }
       

    2.    public boolean isMagnetic() {
             return mag;
          }
       

    3.    ArrayBoundedStack<Disk> magStack = new ArrayBoundedStack<>();
          ArrayBoundedStack<Disk> SSDStack = new ArrayBoundedStack<>();
       

    4.    int i;
          String mfg, model, mag, dummy;
          int size;
          Disk disk;
          System.out.println("enter disk manufacturer: ");
          mfg = keybd.nextLine();
          while (!mfg.equals("done")) {
             System.out.println("enter disk model: ");
             model = keybd.nextLine();
             System.out.println("enter disk type (magnetic or SSD): ");
             mag = keybd.next();
             System.out.println("enter disk size in GB: ");
             size = keybd.nextInt();
             dummy = keybd.nextLine();
             if (mag.equals("magnetic"))
                disk = new Disk(mfg, model, true, size);
             else
                disk = new Disk(mfg, model, false, size);
             if (disk.isMagnetic())
                magStack.push(disk);
             else
                SSDStack.push(disk);
             System.out.println("enter disk manufacturer: ");
             mfg = keybd.nextLine();
          }
       

    5.    while (!magStack.isEmpty()) {
             disk = magStack.top();
             magStack.pop();
             System.out.println(disk);
          }
          while (!SSDStack.isEmpty()) {
             disk = SSDStack.top();
             SSDStack.pop();
             System.out.println(disk);
          }
       

16.    public static int lower(int[] arr, int size, int value) {
          if (size == 0)
             return 0;
          else {
             if (arr[size-1] < value)
                return 1 + lower(arr, size-1, value);
             else
                return lower(arr, size-1, value);
          }
       }
    

17. 1. There will be size+1 calls, for values size, size-1, size-2, ..., 1, 0.
    2. 3 for each recursive call, 1 for the base case (size == 0)
    3. 3*size + 1
    4. O(size) or O(N)



---

Email Me | Office Hours | My Home Page | Department Home | MCC Home Page

© Copyright Emmi Schatz 2023