Jam 5: Study Guide

Jams are open book. 40 minutes in lab.

Topics:

This quiz includes the previous topics from jams 1-4 plus

Stack diagram practice with classes
Selection sort and bubble sort
Swapping elements in an array
Runtime analysis/big-O notation
O(1) — constant time
O(log₂N) — logarithmic (ex: binary search)
O(N) — linear (ex: linear search)
O(N²) — quadratic (ex: bubble sort)

Write Java programs to check your answers. Or you can ask a TA or instructor to give feedback on your responses.

Practice questions

0) In this question, we will visualize the execution of the following program.

class Bounds {
   private int min;
   private int max;

   public Bounds(int min, int max) {
      this.min = min;
      this.max = max;
      // A) Draw the stack diagram here
   }

   public void extend(Bounds other) {
      if (other.min < this.min) {
         this.min = other.min;
      }
      if (other.max > this.max) {
         this.max = other.max;
      }
      // C) Draw the stack diagram here
   }

   public String toString() {
      return "[" + this.min + ", " + this.max + "]";
      // B) Draw the stack diagram here
   }

   public static Bounds Add(Bounds a, Bounds b) {
      int min = a.min + b.min;
      int max = a.max + b.max;
      // D) Draw the stack diagram here
      return new Bounds(min, max);
   }

   public static void main(String[] args) {
      Bounds b1 = new Bounds(-4, 7);
      Bounds b2 = new Bounds(2, 9);
      System.out.println("Bounds 1: " + b1);
      System.out.println("Bounds 2: " + b2);

      b1.extend(b2);
      System.out.println("Extended: " + b1);

      Bounds c = Bounds.Add(b1, b2);
      System.out.println("Add: " + c);
      // E) Draw the function stack here
   }
}

A) Draw the stack diagram for the first call to the Bounds constructor in main B) Draw the stack diagram for the first call to the toString() in main C) Draw the stack diagram for the call to extend() in main D) Draw the stack diagram for the call to Add() in main E) Draw the stack diagram at the end of main F) What is the output of the above program?

1) How many steps are required for each of the following? Classify each one as either O(N), O(N²), O(log₂ N), O(N log₂ N), or O(1).

int N = getInputSize();
for (int i = 0; i < N; i++)
{
    for (int j = 0; j < N; j++)
    {
        println(i, j);
    }
}

int N = getInputSize();
while (N > 1)
{
    print(N)
    N = N/2
}

int N = getInputSize();
for (int i = 0; i < N; i++)
{
    for (int j = 0; j < 10; j++)
    {
        print(i*j);
    }
}

2) Which algorithm requires time directly proportional to the size of the input list?

+ - linear search - binary search - bubble sort - selection sort

3) Consider the following function, oneLoop(int[] L), which is similar to the inner loop from bubble sort:

void oneLoop(int[] L)
{
   for (int j = 0; j < L.length()-1; j++)
   {
      if (L[j] > L[j+1])
      {
         int tmp = L[j+1];
         L[j+1] = L[j];
         L[j] = tmp;
      }
   }
}

+ Suppose we run oneLoop on the list L={17,4,19,3,11,8}. What are the new contents of L?

4) Show how the list L={17,4,19,3,11,8} would be changed after selection sort does its first 3 swaps:

5) Write code to load and parse a file with format [Name,Score,PowerUp,Role]

Ressie Rask  ,3224,Mushroom,Healer
Angelique Aust  ,1190,Mushroom,Dps
Tiny Teamer  ,3722,Mushroom,Tank
Michell Mancino  ,316,Tea kettle,Dps
Amos Ackman  ,4989,Fireball,Tank
Liz Labat  ,714,Mushroom,Healer
Lawerence Lalonde  ,3921,Mushroom,Dps
Madelyn Mcjunkin  ,1243,Fireball,Tank
Echo Eckhardt  ,4831,Mushroom,Dps

6) True/False questions:

Linear search requires a number of steps proportional to the size of the list being searched (T/F)
Binary search is an O(N²) algorithm (T/F)
The number of times N can be divided by 2 (before reaching 1) is log₂ N (T/F)

7) How many steps would it take to do binary search on a list of size 1 million, when the item you are searching for is NOT in the list?

8) How many steps would it take to do linear search on a list of size 1 million, when the item you are searching for is NOT in the list?

9) Binary search is much faster than linear search, so why don’t we use it for every search problem?