This exam consists of two problems. You should create two separate projects for this exam, one project for each of the two problems.

This exam is an open book, open note exam. You are welcome to refer to the textbook and the course web site in this exam.

Problem One

Write a program that can read two lists of integers from files named "one.txt" and "two.txt" and construct a list of all the numbers that appear in both lists. The numbers in the two files are not in order, and neither of the two lists contain any duplicate numbers. The result list will contain all of the numbers that appear in both list one and list two.

For example, if one.txt contains the list of numbers [7,2,12,15,4,8,9] and two.txt contains the list of numbers [1,14,3,12,2,7,4] your program should print the list [2,4,7,12].

As part of your solution you should write and use a method

public static int[] inBoth(int A[],int B[])

that returns an array of integers that appear in both array A and array B.

You should make no assumptions about how many numbers will appear in the result array. Instead, your inBoth() method should determine how many numbers appear in both arrays, then make an array with that size and fill it with the appropriate numbers.

Problem Two

Here is a list of coordinates for a set of points. In this problem you are going to find a set of rectangles that can together cover all of the points in the list. Here is the list of rectangles you will be working with. Each rectangle is described by five data items:

<id> <x> <y> <width> <height>

where <id> is the integer id number of the rectangle, (x,y) gives the coordinates of the lower left hand corner of the rectangle, and <width> and <height> give the width and height of the rectangle.

Here is an algorithm that can determine a set of rectangles which together manage to contain all of the points in the list of points:

  1. Read all of the points from the file and put them in a list of points.
  2. Read all of the rectangles and put them in a list of rectangles
  3. While points remain in the points lists do:
    1. Find the rectangle that contains the largest number of points in the points list.
    2. Remove all of the points that this rectangle covers from the list of points.
    3. Record the id number of the rectangle, then remove that rectangle from the list of rectangles.
  4. Print the list of the id numbers of the rectangles you found.

Write a program that implements this algorithm.

Given the set of points and rectangles I provided, your program should print this list of rectangle ids:

38
9
25
5
41
35
12
31
1
39
21
4
6
7
14

Helpful hint To do the step where you remove all of the points that a rectangle covers from your list of points I recommend that you add a method

public ArrayList<Point> filter(ArrayList<Point> points)

to your Rectangle class. This method constructs and returns a new ArrayList that contains all of the points in the points list that are not inside the rectangle.