CS 455 Midterm 1 Solution

Q2

yahoo
11 6
11 6

rm code/*.class

Q4.1 Some common representations given:

1. int hour;  // valid range: [1,12]
   int minute;  // valid range: [0,59]
   boolean isAM;  // true means AM, false means PM
     

   Examples:
   1. time: 9:30am
      values: hour: 9; minute: 30; isAM: true
      
   2. time: 4pm
      values: hour: 4; minute: 0; isAM: false

2. // using a 24-hour clock (aka, military time)
   int hour;  // valid range: [0,23]
   int minute;  // valid range: [0,59]
     

   Examples:
   
   1. time: 9:30am
      values: hour: 9; minute: 30;
      
   2. time: 4pm
      values: hour: 16; minute: 0;

3. // number of minutes since midnight
   int minutesFromMidnight;  // valid range: [0 , 60*24)
   int minute;  // valid range: [0,59]
     

   Examples:
   
   1. time: 1:30am
      values: minutesFromMidnight: 90
      
   2. time: 12pm
      values: minutesFromMidnight: 720

Q4.2 The programmers who use the class don't have to make any changes to their code because the interface for the class did not change.

Q5.1 constructor, getPosition, isFacingRight

Q5.2 Solution in bold.
Here are two common solutions:

Solution 1

public class Ant {

   private int pos;
   private int dir;
   private static int LEFT = -1;  // named constant not required for full credit

   // Create an ant at position startPos, facing left
   public Ant(int startPos) {
      pos = startPos;
      dir = LEFT: 
   }

   // Move the ant by one unit in the direction it is facing.
   public void move() {
      pos += dir;  
   }

   // Turn the ant in the opposite direction
   public void turn() {
      dir = -1 * dir;  
   }

   // Get the ant's current position
   public int getPosition() {
      return pos;  
   }

   // Return true iff the ant is facing right
   public boolean isFacingRight() {
      return pos != LEFT;
   }
}

public class Ant {

   private int pos;
   private boolean isLeft;

   // Create an ant at position startPos, facing left
   public Ant(int startPos) {
      pos = startPos;
      isLeft = true; 
   }

   // Move the ant by one unit in the direction it is facing.
   public void move() {

      int moveBy = 1;

      if (isLeft) {
         moveBy = -1;
      }

      pos += moveBy;
   }

   // Turn the ant in the opposite direction
   public void turn() {
      isLeft = !isLeft;  
   }

   // Get the ant's current position
   public int getPosition() {
      return pos;  
   }

   // Return true iff the ant is facing right
   public boolean isFacingRight() {
      return !isLeft;
   }
}

For solution 2:
pos is the current position of the Ant
isLeft denotes the direction of the Ant: true if facing left; false if facing right
(note: for this solution, no representation invariant necessary, because all possible values are valid, as are all possible combinations of values of the two instance variables)

Q6.1 (many correct solutions)
nums: [20, 5, 0]
return value: true

Q6.2 (many correct solutions)
nums: [10, 5, 1]
return value: false

Q6.3

Solution 1: return false as soon as you find an adjacent pair that violates the condition

public static boolean isDecr5(int[] nums) {

   for (int i = 0; i < nums.length - 1; i++) {

      if (nums[i] - 5 != nums[i + 1]) {

         return false;

      }
   }

   return true;
}

Comment about this solution: In the future we will deduct points for similar unnecessarily slow solutions on exams. Both solutions have the same worst-case complexity, but Solution 2 also unnecessarily has O(n) best-case complexity, and takes longer in practice for many other arrays.

public static boolean isDecr5(int[] nums) {

   boolean decr5 = true;

   for (int i = 0; i < nums.length - 1; i++) {

      if (nums[i] - 5 != nums[i + 1]) {
         decr5 = false;
      }

   }

   return decr5;
}

Q7.1

Solution 1: traverse the array backwards until you find target

public static int findLast(int[] nums, int target) {

   for (int i = nums.length-1; i >= 0; i--) {
      if (nums[i] == target) {
         return i;
      }
   }

   return -1;

}

The other main solution given was one that initialized a targetLoc variable to -1 and then traversed forward through the array, and updaed targetLoc every time it encountered target. It returned targetLoc after the loop.

Like in problem 6.3, this solution is one that unnecessarily traverses the whole array on every input. Again, we will take off credit for this type of thing on future exams. (See 6.3 Solution 2 comments for details.)

Q7.2 There are several different variations of the same basic approach, depending on things such as which index you use as the loop variable, and what temporary variables you save: we'll give two of those variations here. Note: No special case code necessary for not-found or empty-array cases.

Variation 1:

public static int[] afterLast(int[] nums, int target) {

   // startLoc: location of first element to copy over
   int startLoc = findLast(nums, target) + 1;

   int resultLength = nums.length - startLoc;

   int[] result = new int[resultLength];
      
   for (int i = 0; i < resultLength; i++) {
      result[i] = nums[i + startLoc]
   }

   return result;
 
}

public static int[] afterLast(int[] nums, int target) {

   // lastLoc: location of last instance of target in nums
   int lastLoc = findLast(nums, target);

   int resultLength = nums.length - (lastLoc + 1);

   int[] result = new int[resultLength];

   int i = 0;

   for (int j = lastLoc + 1; j < nums.length; j++) {
      result[i] = nums[j];
      i++;
   }

   return result;

}