COMP610 Data Structures and Algorithms: Assignment 1: Linked List & Bracket Evaluator
Data Structures and Algorithms: Assignment 1
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
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 canbe 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 0 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.
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.
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.
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.
Part 3 Bracket Evaluator (12%)
DataAnalysis 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.
All the private methods are for the students who wish to use recursion. If you don’t use recursion, you may ignore those private methods.
You can add more fields or methods if you need.
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.
Design YOUR OWN GUI of the simulation.
Phone’s behaviours
o You may use the linked list from question 1 to store all the phones or you may
use array to store all the phones.
o Mobile phones are drawn on the simulation application. (3%)
o Repair shop is drawn. (3%)
o Mobile phones move randomly (2%)
o Each phone runs as a thread. (5%)
o An “up” arrow key is used to increase the number of phones in the simulation.
(3%)
o 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%)
o Press “v” key to set one phone to get virus randomly. (2%)
o The virus transmits through network within a certain distance (distance is about
20 pixels in this simulation) (3%)
o 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
o You can synchronize your block of code or method. (5%)
o only one phone is in the repair shop at a time. (NO race conditions) (5%)
o 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?”
