- August 29, 2020

COMP3506 Homework 2 – Sorting Algorithms, Linear Data Structures Weighting: 15% Due date: 7th September 2020, 11:55 pm Overview This purpose of this assignment is for you to become familiar with understanding sorting algorithms and linear data structures, and to investigate using experimental analysis to measure the practical performance of different sorting algorithms. Marks This assignment is worth 15% of your total grade. COMP3506 students will be marked on questions 1 to 3 out of 55 marks. COMP7505 are required to additionally do question 4 and will be marked out of 70 marks. Submission Instructions • Your solutions to Q1 will be submitted via Gradescope to the Homework 2 – Question 1 submission. You should only submit your completed SortingAlgorithms.java file. • Your solutions to Q2 will be submitted via Gradescope to the Homework 2 – Question 2 submission. You should submit your answer as a pdf file. • Your solutions to Q3 will be submitted via Gradescope to the Homework 2 – Question 3 submission. You should only submit your completed SimpleArrayDeque.java, SimpleLinkedDeque.java, ReversibleDeque.java files. • (COMP7505) Your solutions to Q4 will be submitted via Gradescope to the Homework 2 – Question 4 submission. You should submit your answer as a pdf file. • No marks will be awarded for non-compiling submissions, or submissions which import non-supported 3rd party libraries. You should follow all constraints laid out in the relevant questions. • Hand-written answers for questions 2 and 4 will not be marked. Late Submissions and Extensions Late submissions will not be accepted. It is your responsibility to ensure you have submitted your work well in advance of the deadline (taking into account the possibility of internet or Gradescope issues). Only the latest submission before the deadline will be marked. See the ECP for information about extensions. Academic Misconduct This assignment is an individual assignment. Posting questions or copying answers from the internet is consid- ered cheating, as is sharing your answers with classmates. All your work (including code) will be analysed by sophisticated plagiarism detection software. Students are reminded of the University’s policy on student mis- conduct, including plagiarism. See the course profile and the School web page: http://www.itee.uq.edu.au/ itee-student-misconduct-including-plagiarism. 1 Support Files Provided The following support files are provided to you: • SortingAlgorithms.java – you need to implement your question 1 sorting algorithms in this file. • SimpleDeque.java – an interface used for question 3. • SimpleArrayDeque.java – you need to implement question 3(a) in this file. • SimpleLinkedDeque.java – you need to implement question 3(b) in this file. • ReversibleDeque.java – you need to implement question 3(c) in this file. Questions 1. (20 marks) Implement the following sorting algorithms in SortingAlgorithms.java as they have been de- scribed in lectures and tutorials. • Selection Sort (in the selectionSort method) • Insertion Sort (in the insertionSort method) • Merge Sort (in the mergeSort method) • Quicksort (in the quickSort method), using the median element at bn/2c as your pivot. A stub has been provided in SortingAlgorithms.java. Each algorithm needs to be able to sort arbitrary Comparable1 objects and should be able to sort in descending order with the reversed flag. Notes and constraints: • You may use code (or implement the pseudocode) provided in lecture slides and tutorials. • Your solution will be automatically marked using Java 11. • You will be marked by a human on your code style (e.g. for following the style guide, and general readability). You should follow the CSSE2002 style guide as given on Blackboard. Importantly, you should comment your code where necessary. • You may not use anything from the Java standard library (e.g. any built in sorting algorithms). • Do not modify any of the provided method signatures. This may result in you receiving a mark of 0 for this question as it won’t work with our automated tests. • When submitting, only submit the SortingAlgorithms.java file to the Gradescope submission. • You may add private helper methods, but do not use any static or class variables. • All your algorithms should modify the resulting array and not return anything. Note that some of the sorting algorithms you need to implement are not in-place, so you might need to do a little extra work to make it eventually modify the input arrays. 1See https://docs.oracle.com/en/java/javase/11/docs/api/java.base/java/lang/Comparable.html. 2 2. (10 marks) In this question, you will be empirically testing the performance of your sorting algorithms (as implemented in Question 1) when sorting various types of arrays of various different sizes. Write a Java program to time (in milliseconds) the algorithms you wrote in question 1 for arrays of: • n random unsorted numbers • n random sorted numbers in ascending (increasing) order • n random sorted numbers in descending (decreasing) order. For each category, you should test with arrays of size n = 5, 10, 50, 100, 500, 1000, 10000. Based on the results of your program, fill out the table below for each of the three categories. Algorithm n = 5 n = 10 n = 50 n = 100 n = 500 n = 1000 n = 10000 Selection Sort Insertion Sort Merge Sort Quicksort Additionally, for each category of arrays, make a graph plotting the runtime of all four sorting algorithms with n on the x-axis (you can use Excel, pyplot, or something else). Clearly include a legend and appropriate titles/labels. You should have 3 graphs and 3 tables. Include (i.e. copy/paste) the Java code you used to time your sorting algorithms at the end of your written answer for this question. Discuss your observed results and how they compare with what you expected. You may want to reference the asymptotic complexities of the sorting algorithms. Make sure to discuss the effects of n and the sortedness of the input array. This should be no more than 300 words. Hints: • Your program should automatically generate the arrays used for testing. • The Random class and the Arrays.sort method may be useful here. • The time taken to generate these arrays should not be included when measuring a sorting algorithm’s runtime. • You must generate the test arrays and time the algorithms using Java. You may use a different pro- gram/programming language to plot the graphs, if so desired (your plotting code does not need to be included). Notes: • While the timing program’s code will not be style-marked, please use suitable variable names, spacing, and comments as appropriate. • To include code in your document, you can use the listings package if you are using LATEX. This which will format and highlight the code for you. • If you are using another word processor/typesetting system, please ensure that the code uses a monospaced font (such as Consolas or JetBrains Mono) and is appropriately formatted and indented (e.g. each level of indentation is four spaces). • Code which is not formatted appropriately may be penalized. 3 3. (25 marks) A deque data structure is a double-ended queue which supports O(1) insertion and deletion from either end. This can be thought of as both a stack and a queue at the same time. You are given a generic interface for a deque in SimpleDeque.java (note this is not the Deque from Java’s standard library). Your classes (described below) must implement all the methods from this interface. For this question, your implementation of all classes and methods should be as efficient as possible, in terms of both runtime and memory. Your Javadoc comments for methods should describe the runtime and memory complexity (using Big-O notation) of that method. Similarly, a class’s Javadoc comment should describe the memory complexity of the class as a whole. Define all variables used in your bounds. (a) (10 marks) Implement the SimpleArrayDeque class. This implements a deque with a circular array (a basic Java array, not an ArrayList). (b) (10 marks) Implement the SimpleLinkedDeque class. This implements a deque with a doubly linked list. You cannot use Java’s LinkedList and must implement the linked list yourself. (c) (5 marks) Implement the ReversibleDeque class which enables reversing a deque. This has exactly one constructor which takes a SimpleDeque data argument. ReversibleDeque should implement the usual SimpleDeque methods by modifying this internal data deque. Additionally, ReversibleDeque defines a void reverse() method which, when called, reverses the deque so items at the left are now at the right and vice-versa. Notes: • SimpleArrayDeque has two constructors: one taking a single int capacity argument and one taking int capacity and SimpleDeque extends T> otherDeque. These constructors create deques with a limited capacity (see the interface’s JavaDoc for more details). • SimpleLinkedDeque has four constructors: two which are the same as in SimpleArrayDeque, a de- fault constructor taking no arguments, and one with a single SimpleDeque extends T> otherDeque argument. These constructors without a capacity argument have unlimited capacity. • The constructors taking an otherDeque argument are copy constructors. These should initialise the new deque as a copy of the other deque, without modifying the other deque. • For ReversibleDeque, you may assume that the given data deque will not be modified externally once it is passed to the ReversibleDeque constructor. Failure to adhere to the below constraints may result in you receiving a grade of 0 for the question. • You will be marked by a human on your code style (e.g. for following the style guide, and general readability). You should follow the CSSE2002 style guide as given on Blackboard. • You will submit only SimpleArrayDeque.java, SimpleLinkedDeque.java, and ReversibleDeque.java to the relevant Gradescope submission. You should not create or submit any additional files as these will not be marked. • You should not modify any of the provided method, constructor, or class signatures. • All of your files will be marked and compiled independently. None of your classes should rely implemen- tation details of other classes (for example, ReversibleDeque should not depend on or even know about SimpleArrayDeque). • Your implementation will be automatically marked using Java 11. • You should not use any imports from the Java standard library, except for those already imported in SimpleDeque.java (e.g. Iterator and the exceptions). In particular, you may not use LinkedList or ArrayList. Ask on Piazza if you are unsure. • Any member variables, helper methods, or inner classes in your solutions should be made private (except for the constructors given in the assignment files, and the interface methods you have to implement). 4 4. (COMP7505 only) (15 marks) Sorting algorithms often have significantly different performance depending on the length of the array being sorted. Unfortunately, this is not conveyed in the asymptotic bounds. This means a Θ(n2) algorithm might be faster in practice than a Θ(n log n) algorithm for particularly small input sizes. Research (or experiment yourself) how the the performance of common sorting algorithms is affected by the length of the array. With this in mind, devise a sorting algorithm which is efficient for all lists (including random, sorted ascending, sorted descending) as well as a wide range of input lengths. Make sure to explain where the traditional algorithms fall short and how your algorithm improves on them. Insert the code into your PDF writeup for this question (you should follow the same guidelines from question 2). If you call the other sorting methods in SortingAlgorithms.java, you do not need to paste the code for those methods as well. Do an experimental analysis of your new sorting algorithm exactly like in question 2 (i.e. provide tables for your recorded times on the different inputs). Then, plot your results against the experimental analyses you did in question 2. (Note: you do not need to provide the code used for experimental analysis in this question). Discuss (in 400 words or less) how your sorting algorithm works, and how you came up with it (e.g. what did you experiment with to come up with it). Also discuss the performance of your algorithm in comparison to the other sorting algorithms (e.g. by referencing the plot). Some things you could try experimenting with are: • Making your sorting algorithm adaptive (i.e. runs in O(n) time for sorted input). • Different quicksort pivot choices. • A hybrid sorting approach—that is, making use of two or more sorting algorithms. If you make use of external research in your solution, it must be referenced. 5