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 (15marks)
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.
2. Non-linear Data Structure (50 marks)
2.1 Question [Total 30]:
a) In an algebraic expression tree, each leaf node contains an operand and a non-leaf node, including the root node, contains an operator that is applied to the results of its left and right sub-trees. (5 Points)
((((3 × (1 + (4 + 6))) + (2 + 8)) × 5) + (4 × (7 + 2)))
