University ofCanberra Faculty ofScienceand Technology Software Technology XXXXXXXXXX& 9073) Assignment1–Algorithms Submission date:23:55Sunday01/04/2018(Week7) Type:Individual assignment...

University ofCanberra

Faculty ofScienceand Technology

Software Technology 2 (7170& 9073)

Assignment1–Algorithms

Submission date:23:55Sunday01/04/2018(Week7)

Type:Individual assignment

Submission:A.zip file that contains the following:

•All .java filesrequiredto run programs forthe5questionslistedbelow, and•A report (MSWord file)that containstest casesfor your programs(including input, output and your comments)for the5questions listed below.

Submit this.zip fileviaUCLearn(Canvas) site of this unit.Email submission is not accepted.Tutors willrun your programsontheTutorials Point websiteor EclipseorBlueJ.

Total mark:15​​

Proportion ofunitassessment:15%

Late submission:5% of the total mark(i.e.,0.75mark)per day.

•Between 00:00and 24:00Monday 02/04/2018​​​– 0.75 mark•For each extra day after Monday, deduct additional 0.75 mark,

for example,between 00:00 and 24:00 Tuesday 03/04/2018​– 1.50 marks

Language: Java(useGoogle Java Stylehttps://google.github.io/styleguide/javaguide.html)

Question 1.[1.5 marks]

You are given two sorted arrays, A and B, and A has a large enough buffer at the end to hold B.

a.Write aJavamethod to merge B into A in sorted order.b.Write aJavaprogram to test this methodandprovide3test cases for this program.c.The file containing Java method andprogramisnamedQuestion1.java

Marking guideline

Zeromark for this question if

a.Question1.javafilenotfound for this question​​​​​b.Cannot run thesubmitted Javafile onTutorialsPointwebsiteor EclipseorBlueJ​​

Marking​​

a.Thesorted arrays A and B andmethod to merge B into Aarecorrect​​0.5markb.The Javaprogramiscorrectly implemented,and 3test casesare correct​0.5markc.Google Java Styleapplied​​​​​​​0.5mark

Question 2.[1.5 marks]

You are given two sorted arrays A and B of lengths n and m, respectively.

a.Write a Java method that returns an array C containing elements common to A and B. The array C should be free of duplicates.b.Write aJavaprogram to test this methodandprovide3test cases for this program.c.The file containing Java method and programisnamedQuestion2.java

Marking guideline

Zeromark for this question if

a.Question2.javafilenotfound for this question​​​​b.Cannot run the submitted Java file onTutorialsPointwebsite or EclipseorBlueJ​​

Marking​​

a.The sorted arrays A and B andmethodthat returns an array Carecorrect​0.5markb.The Javaprogramiscorrectly implemented,and 3test casesare correct​0.5markc.Google Java Styleapplied​​​​​​​0.5mark

Question 3.[4marks]Execution times of sorting algorithms

Develop a program that compares the execution times of 7 sorting algorithmsincludingSelection Sort,Insertion Sort,Bubble Sort,Quick Sort,Merge Sort,and Counting Sort(these 6 algorithms are presented in lecturesand tutorials), and another sorting algorithm thatis different from these above-mentionedalgorithmsand availableon a websiteor textbookabout data structures and algorithms(a reference to this website or textbook should be added toyour report).

For comparisons, use thefourdata sets containing 100000 integers as follows.

•Set 1: contains 1, 2, 3, . . ., 99999, 100000 (already sorted in ascending order)•Set 2: contains 100000, 99999, . . ., 3, 2, 1 (already sorted in descending order)•Set 3: contains 100000 random integers in the range from 0 to 99999 (unsorted set and duplicatesareincluded)•Set4: contains 100000 random integers in the range from 0 to 99999 (unsorted set andnoduplicatesareincluded)

Run your program 3 times and listallthe outputs in your report.

The file containing Java programand sorting methodsisnamedQuestion3.java

Markingguideline

Zeromark for this question if

a.Question3.javafilenotfound for this question​​​​​b.Cannot run thesubmitted Javafile onTutorialsPointwebsiteor EclipseorBlueJ​​

Marking​​

a.The ascending order data set is correctly generated​​​​0.5markb.The descending order data set is correctly generated​​​0.5markc.The random order data set is correctly generated and contains duplicates​0.5markd.The random order data set is correctly generated and no duplicates​​0.5marke.Data sets input to 7 sorting algorithms are correct​​​​0.5markf.The program runs all 7 sorting algorithms correctly​​​​0.5markg.The output is in the required format and presented in the report​​0.5markh.Google Java Styleapplied​​​​​​​0.5mark

The requiredoutputfor each time(run 3 times, notethe numbers below are in milliseconds and not the right numbers)

Ascending order set - Selection sort: 20.199

Ascending order set - Insertion sort:10.04

. . . (5 more linesfor 5 other algorithmsshould appear here)

Descending order set - Selection sort: 20.109

Descending order set – Insertion sort:10.08

. . . (5 more linesfor 5 other algorithmsshould appear here)

Random set, duplicates- Selection sort: 20.249

Random set, duplicates-Insertionsort: 0.14

. . . (5 more linesfor 5 other algorithmsshould appear here)

Random set, no duplicates- Selection sort: 20.249

Random set, no duplicates-Insertionsort: 0.14

. . . (5 more linesfor 5 other algorithmsshould appear here)

Question 4.[4marks]Sorting instances of a Java class that implements Comparable interface

You are given a list of student informationin a CSV file that contains the followinginformation:student ID, first name,last name, final mark, and final grade. Your task is to rearrange them according to theirfinal markin decreasing order. If two studentshave the samefinal mark, then arrange them according to their first name in alphabetical order. If those two students also have the same first name,then arrange them according to theirlastname in alphabetical order.If those two students also have the samelastname,then order them according to theirstudentIDin ascending order. No two students have the samestudentID.

The sorted list is output to another CSV file.

You implement a class namedStudentthat has the following fields: student ID, first name,last name, final mark, and final grade(more fields and methods can be implemented depending on your class design). This class implements theComparableinterface and you develop your sorting algorithm in thecompareTomethod.

Sample input CSV files will be given onCanvassite.

The file containing Java programisnamedQuestion4.java.The Student class is inStudent.java.

Marking guideline

Zeromark for this question if

c.Question4.javaandStudent.javafilesnotfound for this question​​​d.Cannot run thesubmitted JavafilesonTutorialsPointwebsiteor EclipseorBlueJ​​

Marking​​

a.The required CSV file is successfully read​​​​​0.5markb.The Student class is correctly implemented​​​​​0.5markc.The algorithm in thecompareTomethod in the Student class is correct​1markd.The data read from the CSV is correctly sorted​​​​0.5marke.The sorted data is successfully output to another CSV file in correct format​0.5markf.The content of the output CSV file is presented in the report​​​0.5markg.Google Java Styleapplied​​​​​​​0.5mark

Question 5.[4marks]Recursive algorithm

Arobotissitting on the upper left hand corner of anNxNgrid. The robot can only move in two directions: right and downto the lower right hand corner.There arecertain squareswhich are “off limits”such that the robot cannot step on them.

The grid size N = 2, 3,and4. LetMbe number of “off limits”, M = 0, 1,2,and3, and the location of these “off limits” are random.

Implement a Javarecursivemethodthatoutputsall possible paths for the robotfor eachvalue of M and N(for a fixed value of M, present the outputs for at least 2 different locations of the M “off limits”).

The file containing Java program and Javarecursivemethod is namedQuestion5.java.

The output for a path is in this format(x1,y1) -> (x2,y2) ->. . .-> (xt,yt). For example: the output should be(0,0) -> (1,0) -> (1,1)for the path from the origin to right cell then down cell as seen below x

y

Example: N = 2 with some off limits displayed as

Marking

Zeromark for this question if

e.Question5.javafilenotfound for this question​​​​​f.Cannot run thesubmitted Javafile onTutorialsPointwebsiteor EclipseorBlueJ​​

Marking​​

a.The recursive method without off-limits is correctly implemented​​0.5markb.The recursive method with 1 off-limit is correctly implemented​​0.5markc.The recursive method with 2 off-limits is correctly implemented​​0.5markd.The recursive method with 3 off-limits is correctly implemented​​0.5marke.The main methodis correctly implemented​​​​​0.5markf.The output formatiscorrect​​​​​​0.5markg.All12test cases (N = 2, 3, 4 and M = 0, 1, 2, 3) are presented in the report​0.5markh.Google Java Styleapplied​​​​​​​0.5mark

Plagiarism: Please review UC Student Academic Integrity Policy in the unit outline and this website to avoid plagiarismhttp://learnonline.canberra.edu.au/mod/book/view.php?id=628284&chapterid=3673

Extension: Please review UC Assessment Policy and Procedureshttps://guard.canberra.edu.au/policy/download_version.php?prev_doc_id=14. Section 9.12 is on extenuating circumstances for deferred examinations and extensions.

References:

[1] GayleLaakmann.Cracking the Coding Interview.

[2] Adnan Aziz,Tsung-Hsien LeeandAmit Prakash.Elements of Program Interviews.