Data Structures and Algorithms: Assignment 1 When submitting, please zip up your entire Netbeans project (make sure you include a .jar file of Virus Simulation project) into a folder with the following naming structure: lastname_firstname_studentID.zip (using your own name and ID) and submit to the Assignment 1 zipped folder on AUT Canvas BEFORE the due date and time. Late submissions will incur a penalty. Antiplagiarism software will be used on all assignment submissions, so make sure you submit YOUR OWN work and DO NOT SHARE your answer with others. Any breaches will be reported and will result in an automatic fail and possible removal from the course. Assignment 1 project contains (see the image on the side): • Question 1 package • Question 2 package Do NOT change the packages' names. Question 1) Linked List & Bracket Evaluator (50%) The purpose of this question is to utilise a linked list to create an application to efficiently evaluate whether opening and closing bracket and brace pairs match up inside any given string in O(n) time, where n is the length of the string. All other content in the string can be ignored. Linked list must be built, and you must use your linked Projects X Files Services Assignment_1_S1_Release Source Packages Question_1 DataAnalysis.java LinkedList.java LinkedListTest.java Node.java Queue.java Stack.java Question 2 Panel.java Phone.java RepairShop.java VirusSimulation.java Test Packages Libraries Test Libraries list to implement a Stack and Queue to complete the application of Bracket Evaluator. Node Class (5%) Create a Node Class which has data and linker parts. Data part stores any type of data and nodes can be linked to each other together by their linkers named "next". Node class has a generic object named "data". which references to any types of object (the object type may be String, Integer, Float or Character). Node Class has a node object named “next” which references to another node. Node Class has an “equals” method. “equals” method takes a Node object in and returns true if the content of argument (node)'s data equals to content of current node's data. Otherwise, it returns false. Node Class has an “compareTo" method. “compareTo" method takes a Node object in and returns an int 0 if the argument node's data equals to this node's data; an int value less than O returns if this node's data is numerically less than the argument node's data or this node's data is alphabetically less than the argument node's data. Otherwise, it returns an int value greater than 0. Members Node <E extends Comparable> compareTo(Node node): int equals(Node node): boolean data : E next: Node<E> an object of data (String, Integer...) an object of data (String, Integer...) an object of data (String, Integer...) ககக data next data next data next LinkedList Class (23%) Create a LinkedList Class which builds and manages a linked list. Extra 10 marks will be given if no loops are used in this Class. LinkedList Class has a Node reference named "head" to reference to the head of a linked list. LinkedList Class has an int variable named "size" to store the size of a linked list (number of nodes). LinkedList Class has an "add" method. It takes a generic object to create a node and add to the end of the linked list. LinkedList Class has an “addHead" method. It takes a generic object to create a node and add to the head of the linked list. LinkedList Class has an “addInOrder" method. It takes a generic object to create a node and add to a linked list following the ascending numerical order if the generic object is a number. It follows alphabetical order if the generic object is a char or String. LinkedList Class has a "contains" method. It takes an element (data of a node) and returns true if the linked list contains this element (data). Otherwise, it returns false. LinkedList Class has an "getNode" method. It takes an index of a node to be retrieved and returns the node. LinkedList Class has an "getData" method. It takes an index of a node to be retrieved and returns the node's data. LinkedList Class has a “printLinkedList" method. It prints all the contains of the linked list to the console. LinkedList Class has a "remove" method. It takes an element (data of a node) as an argument and remove a node which has the same data that is passed to the method. LinkedList Class has a "remove" method. It takes an index of a node to be removed and removes the node. LinkedList Class has a "removeFromHead" method. It removes the first node from the linked list. LinkdedList Class has a "removeFromTail" method. It removes the last node from the linked list. Members LinkedList<E extends Comparable> add(E data) add(Node head, Node node) addHead(E data) addInOrder (E data) <empty> addInOrder (Node currentNode, Node newNode) contains(E data): boolean contains(Node head, Node node): boolean getData(int index): E getData(int index, Node head): E getHead: Node getNode(int index): Node getNode(int index, Node head): Node printLinkedList() printLinkedList(Node node) remove(E data) remove(int position) removeByIndex(Node head, int position) removeFromBody(Node head, Node node) removeFromHead0: Node removeFromTail: Node removeFromTail(Node node) : Node head: Node<E> size: int Part 2 Queue and Stack(10%) Queue Class (5%) Queue class manages a linked list as a queue. Queue class has an “enqueue” method. It takes a generic object and enqueues the object to a queue. Queue class has a “dequeue” method. It dequeues and returns an element from a queue. Queue class has a "getSize" method. It returns the size of the queue. Queue class has a "printQueue" method. It prints the contains of the queue to the console. Members 曰: Queue<E extends Comparable> dequeue(): E enqueue(E data) getSize(): int printQueue( queue: LinkedList<E> Stack Class (5%) Stack class manager a linked list as a stack. Stack class has an "push" method. It takes a generic object and push the object to a stack. Stack class has a "pop" method. It pops and returns an element from a stack. Stack class has a "getSize" method. It returns the size of the stack. Stack class has a "printStack" method. It prints the contains of the stack to the console. Members Stack <E extends Comparable> getSize() : int pop0: E printStack() push(E data) stack: LinkedList<E> Part 3 Bracket Evaluator (12%) Data Analysis Class DataAnalysis class checks whether brackets of a string are valid (you may use Queue, Stack or both). DataAnalysis class has an “bracketEvaluator" method. It returns true whether opening and closing bracket and brace pairs match up inside any given string. Members Data Analysis <E extends Comparable> Data Analysis (E] data) bracketEvaluator: boolean data : E All the private methods are for the students who wish to use recursion. If you may ignore those private methods. You can add more fields or methods if you need. you don't use recursion, When you finish the question 1, please run LinkedListTest to test your program. LinkedListTest will generate a report which show you your marks for question 1. Question 2) Thread: a mobile phone virus transmission simulation (50%) You need to design a virus transmission simulation. You are going to draw some icons instead of mobile phones in your simulation. The number of mobile phones can be increased during the simulation by clicking a key from a keyboard. Each phone runs as a thread. A virus starts in a random phone, and it transmits to the others in the range of 20 pixels. Infected phone needs to take to a repair shop to get repaired. Only one phone can be repaired at a time. You need to design and write "synchronized" algorithm to handle it. If the phone cannot be repaired within 500 frames, the phone will die (the phone is removed from the simulation). Design YOUR OWN GUI of the simulation. • Phone's behaviours ○ You may use the linked list from question 1 to store all the phones or you may use array to store all the phones. • ○ Mobile phones are drawn on the simulation application. (3%) Repair shop is drawn. (3%) ○ Mobile phones move randomly (2%) о Each phone runs as a thread. (5%) O о ○ An "up" arrow key is used to increase the number of phones in the simulation. (3%) Different colours for three different states of a phone (health phone, infected phone and moving to repair shop). You choose your own colour for the phones. (2%) Press "v" key to set one phone to get virus randomly. (2%) The virus transmits through network within a certain distance (distance is about 20 pixels in this simulation) (3%) After a phone get infection, simulation counts down the life span of the phone from 500 to 0. When it gets to 0, the phone will be removed from the simulation. (2%) Synchronized о You can synchronize your block of code or method. (5%) ○ о only one phone is in the repair shop at a time. (NO race conditions) (5%) You need to select an object for synchronize. (5%) O Answer the following question as comments in your Phone class (put question and your answer on the first line of your code). (8%) Question: "Which object(s) have you chosen for the synchronize? Why?"