CSC236 Data Structures - Exam 1 Answers

Exam 1 Answers:Section 02

T
F
T
A
D
B
A
C
1. O(NlogN)
2. O(N²)
3. O(1)

```
Output:
7
5
3
1
2
6
16
24
24
```
1. 1. 1
  2. N+1
  3. N(N+1)
  4. N²
  5. N²
  6. N²
  7. N²
  8. N
  9. N
2. O(N²)
3. 1. 1
  2. N+1
  3. N(N+1)
  4. N²
  5. N²
  6. N²
  7. 0
  8. N
  9. N
4. O(N²)
```
Ford
Tesla
BMW
Toyota
```

   public int diff(LinkedStack<T> two) {
      int numDiff = 0;
      LLNode<T> temp = top;
      LLNode<T> tempTwo = two.top;
      while (temp != null && tempTwo != null) {
         if (temp.getInfo().equals(tempTwo.getInfo())
            numDiff++;
         temp = temp.getLink();
         tempTwo = tempTwo.getLink();
      }
      if (temp != null)
         while (temp != null) {
            numDiff++;
            temp = temp.getLink();
         }
      if (tempTwo != null)
         while (tempTwo != null) {
            numDiff++;
            tempTwo = tempTwo.getLink();
         }
      return numDiff;
   }

The diff method must access every element of this and every element of the parm. If there are M elements in this and P elements in the parm, then it has to access M + P elements. 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).

   public String toString() {
      return title + "   " + studio + "   " + genre + "   " + length + " minutes";
   }

   public boolean isGenre(String gen) {
      if (genre.equals(gen))
         return true;
      else
         return false;
   }

   ArrayBoundedStack<Film> action = new ArrayBoundedStack<>();
   ArrayBoundedStack<Film> comedy = new ArrayBoundedStack<>();

   int i;
   String title, studio, genre, dummy;
   int length;
   Film inFilm;
   System.out.println("enter the title of the film: ");
   title = keybd.nextLine();
   while (!title.equals("done")) {
      System.out.println("enter the studio name: ");
      studio = keybd.nextLine();
      System.out.println("enter the genre: ");
      genre = keybd.nextLine();
      System.out.println("enter the length of the film: ");
      length = keybd.nextInt();
      dummy = keybd.nextLine();
      inFilm = new Film(title, studio, genre, length);
      if (inFilm.isGenre().equals("action"))
         action.push(inFilm);
      if (inFilm.isGenre().equals("comedy"))
         comedy.push(inFilm);
      System.out.println("enter the title of the film: ");
      title = keybd.nextLine();
   }

   while (!action.isEmpty()) {
      inFilm = action.top();
      action.pop();
      System.out.println(inFilm);
   }

   while (!comedy.isEmpty()) {
      inFilm = comedy.top();
      comedy.pop();
      System.out.println(inFilm);
   }

   public static int numOver(int[] arr, int size) {
      if (size == 0)
         return 0;
      else {
         if (arr[size-1] > 100)
            return 1 + numOver(arr,size-1);
         else
            return numOver(arr,size-1);
      }
   }

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