1. Set Theory Program (50 marks)

Assume that there are three sorted sets as follows:

A = [1 2 5 6 7 9]

B = [3 5 6 7 8 10]

C = [1 3 4 5 6 8]

1.1 Firstly place the sets into three arrays called A, B and C. Write a Java program called Union_Array.java to create a new array including the union of the three sets without repetition. The Big-O of your algorithm must be O(n). For instance, the output should be [1 2 3 4 5 6 7 8 9 10]. (10 marks)

1.2 Firstly place the sets into three singly linked list called A, B and C. Write the exercise

1.1 with Linked List with the same conditions, called Union_LinkedList.java (15 marks)

1.3 Use the singly linked list representation of all the three sets. Write a Java program called Intersect_LinkedList.java to intersect the sets into a new list without repetition. The Big-O of your algorithm must be O(n). For instance, the output should be [5 6]. (15 marks)

1.4 Implement the exercise 1.3 with Array called Intersect_Array.java with the same conditions described at exercise 1.3. (10 marks)

Important Notes:

1. Add useful comments to some points of your codes for understandably of your code design.

2. Since the sets A, B and C are sorted, you need to add some stopping criteria in your program to break the program once the problem is successfully solved