See the criteria on Gradescope for how grades of E/S/N were assigned for each problem.

Question 1 - Conceptual

Part A: Count the objects/references

  • Part A-1 2
  • Part A-2 3

Part B 

(2, 3)
(4, 7)
(1, 1)
Part C Explain in Plain English

Option C “Removes all points from the given list which are closer to the origin than this point. Returns the number of removed points and moves this point right by the same number.”

Question 2 - Tracing

  • First call 
    [[4]]
  • Second call 
    [[2, 4],
 [5, 12]]
  • Third call 
    [[2, 4, 6],
 [4, 0, 1],
 [10, -4, 0]]

Question 3 - Debugging

There were two bugs present in this program. Technically there are many ways of solving this problem, but we just outline one potential solution and explanation below.

Bug 1: The loop increment is incorrect as the loop body adds new elemtns to the list. One potential fix: Change loop bound.

for (int i = 0; i < list.size(); i += 2) {

Bug 2: Adds two elements to the list without removing any.

One potential fix: Change the first add call to a set call.

list.set(i, n / 2 + n % 2);
list.add(i + 1, n / 2);

Another potential fix is to remove the value at index i after adding the split values.

list.add(i, n / 2 + n % 2);
list.add(i + 1, n / 2);
list.remove(i + 2);

Question 4 - Collections Programming

One possible solution is shown below.

public static Map<Integer, Set<String>> split(Set<String> set) {
    Map<Integer, Set<String>> result = new TreeMap<>();
    for (String s : set) {
        if (!result.containsKey(s.length())) {
            result.put(s.length(), new TreeSet<>());
        }
        result.get(s.length()).add(s);
    }
    return result;
}

Question 5 - Objects Programming

One possible solution is shown below.

public class Book implements Media {
    private Map<String, Integer> ratings; // Or other structure is okay
    private String name;

    public Book(String name) {
        this.name = name;
        this.ratings = new HashMap<>();
    }

    public String getName() {
        return this.name;
    }

    public void addRating(String reviewer, int stars) {
        if (stars < 1 || stars > 5 || this.ratings.containsKey(reviewer)) {
            throw new IllegalArgumentException();
        }
        ratings.put(reviewer, stars);
    }

    public void changeRating(String reviewer, int stars) {
        if (stars < 1 || stars > 5 || !this.ratings.containsKey(reviewer)) {
            throw new IllegalArgumentException();
        }
        ratings.put(reviewer, stars);
    }

    public double averageRating() {
        // Can also store in fields
        int total = 0;
        for (int rating : ratings.values()) {
            total += rating;
        }
        return (double) total / ratings.size();  // Ignore 0 case
    }

    public boolean isRatedHigher(Media other) {
        return this.averageRating() >= other.averageRating();
    }

    public String toString() {
        return this.name + " - " + this.averageRating() + " out of 5 stars";
    }
}

Question 6 - Stacks & Queues Programming

Two possible solution are shown below.

// Nested loop solution:
public static void compressDuplicates(Stack<Integer> s) {
    Queue<Integer> q = new LinkedList<>();
    while (!s.isEmpty()) {
        int count = 1;
        int val = s.pop();
        while (!s.isEmpty() && s.peek() == val) {
            count++;
            s.pop();
        }
        q.add(val);
        q.add(count);
    }

    q2s(q, s);
    s2q(s, q);
    q2s(q, s);
}

// Single loop solution:
public static void compressDuplicates(Stack<Integer> s) {
    if (s.isEmpty()) {
        return;
    }
    Queue<Integer> q = new LinkedList<>();
    int prior = s.pop();
    int count = 1;
    while (!s.isEmpty()) {
        int curr = s.pop();
        if (curr == prior) {
            count++;
        } else {
            q.add(prior);
            q.add(count);
            prior = curr;
            count = 1;
        }
    }
    q.add(prior);
    q.add(count);

    q2s(q, s);
    s2q(s, q);
    q2s(q, s);
}

If you want to check if your solution works, please use this program to test out your solution. If your solution works as you wrote it without modifying the logic of your solution and you did not receive an E and you have satisfied the requirements of the problem (e.g., only using the permitted auxiliary data structures and permitted Stack and Queue methods), you should submit a regrade request.