Fall 2021 [Bono]

CS 455 Midterm 2 Solution

Problem 1

Part A

1 2 3

Part B

front à 4 5 6

Problem 2

A: O(n)

B: O(n)

C: O(n)

D: O(n^2)

Problem 3

Part 1: Flynn

Marie, Gus, Flynn

or

Marie, Hank, Gus, Flynn

Part 2 : Walter

Marie, Saul, Skyler, Walter

or

Marie, Skyler, Walter

Part 3 : Jane

Marie, Gus, Hank, Jesse

or

Marie, Hank, Jesse

Problem 4:

Reason 1: ElmtType does not implement Comparable and we cannot modify ElmtType to make it Comparable.

Reason 2: We want to sort ElmtType objects in a different order than their natural ordering.

Problem 5:

public static void expand(ArrayList<Point> points) {

points.forEach(new ExpandConsumer());

}

class ExpandConsumer implements Consumer<Point> {

public void accept(Point p) {

p.translate(p.getX(), p.getY());

}

}

Problem 6:

public class Sights {

private Map<Point, String> locToLabel;

private Map<String, ArrayList<Point>> labelToLoc;

public Sights() {

locToLabel = new HashMap<Point, String>();

labelToLoc = new HashMap<String, ArrayList<Point>>();

}

public boolean add(Point loc, String label) {

if (locToLabel.containsKey(loc)) {

return false;

}

locToLabel.put(loc, label);

if (!labelToLoc.containsKey(label)) {

labelToLoc.put(label, new ArrayList<Point>());

}

labelToLoc.get(label).add(loc);

return true;

}

public String getLabel(Point loc) {

return locToLabel.get(loc);

}

public ArrayList<Point> getPoints(String label) {

return labelToLoc.get(label);

}

}

Problem 7:

public static boolean isIncr(int[] nums) {

return isIncrH(nums, 0);

}

// isIncrH: recursive helper method

// returns true iff the part of the array from nums[start] to

// the end of the array is in non-decreasing order

private static boolean isIncrH(int[] nums, int start) {

if (start >= (nums.length - 1) ) {

return true;

}

if (nums[start] > nums[start + 1]) { return false; }

return isIncrH(nums, start + 1);

}