CS 455 Midterm 2 Solutions

Part A.

public class Names {
   private Set<String> namesTree;

   public Names() {
      namesTree = new TreeSet<>();
   }

   public int numNames() {
      return namesTree.size();
   }

   public boolean lookup(String target) {
      return namesTree.contains(target);
   }

   public boolean remove(String target) {
      return namesTree.remove(target);
   }

   public boolean insert(String newName) {
      return namesTree.add(newName);
   }

   public void printNames() {
      Iterator iter = namesTree.iterator();
      while(iter.hasNext()){
         System.out.println(iter.next());
      }
   }
}

Part B.

a) lookup = O(logn)
b) remove = O(logn)
c) insert = O(logn)
d) printNames = O(n)

[3, 3] [3, 3]
[3, 3] [10, 10]

1) Tyrion
2) Cersei
3) fails
4) Tyrion
5) fails
6) 5

top -> e d c b a
front -> e d c b a
top -> a b c d e

Part A.
   Sansa
   Problem with file
   Answer: 23

Part B.
   File not found
   Answer: 20

Part C.
   Answer: 20

   public static LinkedList<Integer> negativesIn(int[] nums) {
      return helper(nums, 0, new LinkedList<>());
   }

   private static LinkedList<Integer> helper(int[] nums, int start, LinkedList<Integer> result) {
      if (start >= nums.length) { return result; }
      if (nums[start] < 0) { result.add(nums[start]); }
      return helper(nums, start + 1, result);
   }