CS 455 Midterm 1 Solutions

1. (right)   81    B
2. (wrong) 80    F

Part A.

Part B.

1. FALSE
2. FALSE
3. FALSE
4. TRUE

5. TRUE
6. FALSE
7. TRUE
8. TRUE

Problem 3

Description of case given: General case.

Additional cases:
Note: other answers were accepted, but to get full credit the first two listed here had to be included, and all the cases had to be distinct from each other

1. text: ""
   result: []
   descr: empty string

2. text: "Hello"
   result: ["Hello"]
   descr: single word

3. "   "
   result: []
   descr: all ws

4. text: "     Hello, kitty, kitty!     "
   result: ["Hello,", "kitty,", "kitty!"]
   descr: leading and trailing ws

5. text: "Hello,      kitty,      kitty!"
   result: ["Hello,", "kitty,", "kitty!"]
   descr: multiple ws between words

Problem 4

There are a few variations on the commands to use, here are two examples:

mkdir ../ex3
cp *.java ../ex3

cd ..
mkdir ex3
cp ex2/*.java ex3

public class BankAccount {
   private int balance;
   public BankAccount() {
      int balance = 0;
   }
   public BankAccount(int initBalance) {
      int balance = initBalance;
   }
   public void deposit(int amount) {
      balance += amount;
   }
   public void withdraw(int amount) {
      balance -= amount;
   }
   public int getBalance() {
      return balance;
   }
}

Problem 6
Solution shown in bold.

//   Simulate changes in a roach population. 
public class RoachPop {
   public static final int TRAP_CAPACITY = 25;  
                     // number of roaches a trap can kill  
   public static final int SPRAY_PERCENT = 20;

   private int size;
   private int startSize;

 
   //  Creates a roach population of the given size
   //  PRE: size > 0
   public RoachPop(int initSize) {

      startSize = initSize;
      size = initSize;

   }


   //   Gets the current population size 
   public int getSize() {
      
      return size;

   }


   // The current population as a percentage of the original population.
   // (so a value < 100 means the roach population decreased)
   public int percentOfStartPop() {

      return (int) ((size / (double) startSize) * 100);

   }

   
   // The population breeds
   public void breed() {

      size *= 2;

   }

   
   //  The population gets sprayed
   public void spray() {

      size -= (int) (size * SPRAY_PERCENT / 100.0);

   }

   
   //  Set traps for the roaches. 
   //  PRE: numTraps > 0
   public void setTraps(int numTraps) {

      int reduction = TRAP_CAPACITY * numTraps;

      if (reduction > size) {
         size = 0;
         return;
      }

      size -= reduction;

   }
}

Two main solution-types shown here:

   // 2-loop solution (doesn't examine more elmts than necessary) 
   public static int maxDistance(int[] nums, int value) {

      boolean found = false;
      int first = 0;

      // find first occurrence
      while (first < nums.length && nums[first] != value) {
         first++;
      }

      // 0 occurences
      if (first == nums.length) { return 0; }

      // find last occurrence
      int last = nums.length - 1;
      while (last >= 0 && nums[last] != value) {
         last--;
      }

      return last - first + 1;  // works for >= 1 occurrence of value

   }

   // 1-loop solution (always visits every element) 
   private static int maxDistance2(int[] nums, int value) {

      int first = -1;
      int last = -1;

      for (int i = 0; i < nums.length; i++) {
         if (nums[i] == value) {
            if (first == -1) {  // first time seeing value
               first = i;
               last = i;
            }
            else {
               last = i;
            }      
         } 
      }

      if (first == -1) { return 0; }  // 0 occurrences

      return last - first + 1;

   }