When submitting, zip up your entire Netbeans projects (make sure you include three “ .jar” files of your File sorting, Noise removing and Maze projects) into a folder with the following structured file name:

lastname_firstname_studentID.zip (using your own name and ID)

Assingment2.zip contains:

•    Question 1 folder (for entire question 1 project)

•    Question 2 folder (for entire question 2 project)

•    Question 3 folder (for entire question 3 project)

and submit to the Assignment 2 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.

Question 1) Binary Tree and File Sorting (50%)

The purpose of this question is to have an opportunity to understand and manipulate a binary tree  and utilise the binary tree to create a program that sorts the content of a .txt file and can search the content of a .txt by a searching key.

Part 1 (30%)

Student Class (5%)

Create a Student Class which stores student’s name and student’s mark. (0.5%)

Student Class also need a generic type object named “key” . “key” is used for sorting. For example, if the key is student’s mark, the binary tree sorts students by the mark. If the key is student’s name,    then students are sorted by their name. (1%)

Student Class has a “compareTo” method. “compareTo” method takes a Student object in and calls key’s “compareto” method () to compare the Students. It returns an int 0 if the argument Student’s key equals to this Student’s key; an int value less than 0 returns if this Student’s key is numerically  less than the argument Student’s key or this Student’s key is alphabetically less than the argument  Student’s key. Otherwise, it returns an int value greater than 0. (2%)

Student Class has a “setKey” method. “setKey” method sets the value of the “key” . (1%)

Student Class has a “toString” method. “toString” method returns a String description of a student object in the form of “Name: studentName Mark: student mark” .

For example: “Name: Bob Mark: 75” (0.5%)

Node Class (5%)

Create a Node Class which has data and linkers parts. The data can be an object such as Student object and node can be linked to each other together by its linkers named “left” or “right”.

The “data” of a Node class is a generic type. It points to any types of comparable objects. The comparable object type can be String, Integer, or Student. (1%)

Node Class has a node linker named “left” which points to a node that has smaller searching key. (1%)

Node Class has a node linker named “Right” which points to a node that has greater searching key. (1%)

Node Class has a “compareTo” method. “compareTo” method takes a Node object in and calls data’s “compareto” method () to compare the Nodes. It 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. (2%)

BinaryTree Class (25%)

Create a BinaryTree Class which builds and manages a binary tree.

Do not copy the code from the chapter examples.

Do not use loop in the BinaryTree Class.

Fully comments on the methods of addNode(), findNode(), reverseOrder() and traversal().

You will lose 20% of the marks if you don’t give the comments to those methods.

BinaryTree Class has a Node object named “root” to point to the root of a binary tree. (1%)

BinaryTree Class has an int variable named “size” to store the size of a binary tree (number of nodes). (1%)

BinaryTree Class has an “add” method. It takes a generic object to create a node and add to the binary tree. (5%)

BinaryTree Class has a “findNode” method. It takes a data object and returns an object if it finds the node. Otherwise, it returns null. (5%)

For example If I wish to find a student whose name is “Bob”, I will do:

findNode method returns an object of that student if finds. Otherwise, method returns null.

BinaryTree Class has a “reverseOrder” method. It re-constructs the binary tree. By default, if we call traversal method, it displays nodes’ details in the order of from smallest key value to the largest key  value.  If reverseOrder method has been called. Then we run the traversal method, it displays nodes’ details in the order of from largest key value to the smallest key value. (4%)

The time complexity (Big O) of “reverseOrder” method must be n. Please do not rebuild your tree it would be nlog2n (4%). Comments your solution, please.

BinaryTree Class has a “traversal” method. It travels each node on the tree and display nodes’          details in the order of from smallest key value to the largest key value, or from the largest key value

to the smallest key value. (5%)

You can have more methods or

fields as you wish.

Part 2 (15%)

File content sorting

Design and create your own GUI (2%) of the file content sorting program. You must use the BinaryTree Class from part 1 to implement sorting of this program.

GUI should contain:

•    Button of loading files (2%)

•    Button of saving files (2%)

•    Button of choosing file content sorting order (You can do this by an input message box) (3%)

•    Button of searching a student (You can do this by an input message box) (3%)

•   Text Field of Student searching result to be displayed (You can do this by an output message box) (2%)

You may add more GUI components as you wish.

After you have done your code, please generate a .jar file of your program. (1%)

There is an example code of loading and saving .txt files on AUT canvas.

Question 2) Sorting: Noise Removing Application (20%)

Problem: Salt-and-pepper noise, also known as impulse noise, is a form of noise sometimes seen on digital images. This noise can be caused by sharp and sudden disturbances in the image signal. It        presents itself as sparsely occurring white and black pixels. (See more information:                                 https://en.wikipedia.org/wiki/Salt-and-                                                                                                              pepper_noise#:~:text=Salt%2Dand%2Dpepper%20noise%2C,occurring%20white%20and%20black%2 0pixels.)                                                                                                                                                                      Example (image with Salt-and-pepper noise)

An effective noise reduction method for this type of noise is a median filter .

Median Filter:

A program reads a pixel and its 8 surrounding pixels (This 3x3 block of pixels is called sliding window  in digital image processing) from an image then find the median of these 9 pixels. Finally, the median replaces the central pixel. Sliding window moves onto the next pixel and repeats this process until all pixels has been changed (To make the assignment simple, it excludes the bound pixels).

Median: the middle score when all the scores are arranged in order of size from the smallest to the  highest. If there are an even number of scores, then it is the average of the two middle scores (It will not be the case in this assignment).

The code of reading image, getting pixels, saving pixels to an image has been done for you. Your task is to find median for given pixels. In order to find the median, You need to sort an array of 9 pixels.

Example (output image after removing noise)

Your task:

Please download NoiseRemoving.zip file and extract it to a folder. The project contains two .java        files. “ImageProcess.java” and “NoiseRemoving.java” . If you run the project, it loads an image and    generates a .jpg file, named “noise_removed.jpg”, but the generated image still contains noise for     now. You need to complete the method of “cleanNoise” to clean the noise in the ImageProcess class.

“ ImageProcess.java” deals with an image. It has a method named “cleanNoise”. There is a gap in the method. You need to add your SortableArray Class to the project and fill the gap to complete the       ImageProcess Class (3%).

You need to write a “SortableArray” Class. It takes a generic Comparable type of array and sorts array in order.

SortableArray Class has an “array” field. It stores a reference of an array. (1%)

SortableArray Class has “setArray” method. It takes a reference of an array and passes the reference to the “array” field. (1%)

SortableArray Class has “quickSort” method. It runs quick sort algorithm and sorts array in order. (3%)

DO NOT COPY THE CODE FROM THE CHAPTER 3 EXAMPLES

PLEASE FULLY COMMENT YOUR CODE (3%)

Answer following questions in your Comments at the beginning of your SortableArray Class code.

1.    Is quick sort the best way of finding median? Why? (3%)

2.   What is another good way of finding median? Please provide your explanation. (3%)

Finally, you need to design a GUI of noise removing application (2%). So, the application can load an image, clean the noise, and save to a new image. And produce a .jar file of this project. (1%)

*If you are interested in image process, you may try some open-source library. OpenCV for C/C++ or JavaCV for Java.

Question 3) Maze (30%)

You are going to design a program. It loads a maze from a maze text file then program walks through the maze and finds the path from starting node to the exiting node.

Maze text file format:

Number of linkers, Number of columns, number of rows (Header of maze)

Node’s name, x position, y position, next linked node name, next linked node name

…

Node’s name, x position, y position, next linked node name, next linked node name Example:

22,7,6

START,0,2,B,A

B,1,2,C,K

C,1,3,D,E