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)))

b) For this assignment you will write a program that parses fully parenthesized arithmetic expressions, creating an arithmetic expression tree. Build a binary tree (in memory, using a Java class) that would look like this if you could print it in a tree-like form: (25 Points)

Write a class ExpressionTree for representing binary expression trees. Have a file ExpressionTree.java with a main method, as well as additional classes and files, as you see fit.

Remember: an expression tree object is either a leaf (e.g., representing the number 3), or an internal node (e.g., +), with two subtrees for the arguments.

Include a static method stringToExpressionTree that takes a string as parameter and returns a newly constructed ExpressionTree corresponding to the string,

If possible; if the string has invalid syntax, print an error message and abort.
Public static ExpressionTree
stringToExpressionTree(String inString)
Your method may throw exceptions if you wish.
[Writing this method is the hardest part of the project.
You may assume that valid input strings contain only numbers, operators, spaces, and parentheses (but no variables), so that all leaf nodes of the expression tree will be numbers.]
Hint: think how to convert a postfix expression to a tree. You may wish to use java.util.StringTokenizer. If so, read its documentation carefully.

2.2 What is the outcome of inorder traversal on this BST? How about postorder traversal and preorder traversal? (6 Points)

2.3 Consider the following binary tree representation of a max-heap (4 Points)

(a) Give the array representation of the heap.

0	1	2	3	4	5	6	7	8	9	10	11	12

(b) Insert the key P into the binary heap above, circling any entries that changed.

0	1	2	3	4	5	6	7	8	9	10	11	12

2.4 Consider the following left-leaning red-black BST. Some of the colours and key values are suppressed.

(a) Which of the keys below could be the one labeled with a question mark? (2Points)
Circle all possibilities.
A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
(b) For each link from the left-hand column, select its possible color(s) from the right-hand column. (2 Points)
________ link between W and S                      A. red
_____________ link between ? and W             B. black
__________ link between S and Y                   C. either red or black
___________ link between Q and S
(c) How many left-rotation, right-rotation, and color-flip operations would be used to insert each key below into the original red-black BST above? (6 Points)

	H	D	B	J
rotateLeft()
rotateRight()
flipColors()

Submission
Each student is required to submit two things:
 For programing questions:
o One Eclipse project with all the source codes in a zip file named with the student id number. Please name the Java programs as requested in each exercise.
 Report: please use the assignment template as a single doc file to all the exercises accordingly. You can download the template from Moodle. Note: copy and paste all the source codes into the doc file for those questions asking Java programming.
 Self-reflection: write down one paragraph (no more than 300 words) at the end of the doc file template about your self-reflection; i.e., what did you learn from each question and what was surprisingly new thinking evoked at your end?
It is the student responsibility to produce a clear and easily understood document. To do this:
• Check the spelling and grammar in your document.
• Use clear, short, and precise language.
• Number the pages.
• Create a table of contents for your document.
• For every figure in your document use a number and a title.
• Write references/citations in a standard format.
• Explain terms, acronyms, and abbreviations.
• Review the document and check for inconsistencies, omissions, redundancies.
Plagiarism
The University defines an assessment offence as any action(s) or behaviour likely to confer an unfair advantage in assessment, whether by advantaging the alleged offender or disadvantaging (deliberately or unconsciously) another or others. A number of examples are set out in the Regulations and these include: “D.5.7.1 (e) the submission of material (written, visual or oral), originally produced by another person or persons, without due acknowledgement, so that the work could be assumed the student’s own. For the purposes of these Regulations, this includes incorporation of significant extracts or elements taken from the work of (an) other(s), without acknowledgement or reference, and the submission of work produced in collaboration for an assignment based on the assessment of individual work. (Such offences are typically described as plagiarism and collusion.)” The University's Assessment Offences Regulations can be found on our web site. Also, information about plagiarism can be found on the programme’s handbook.