User Manual: Pdf
Open the PDF directly: View PDF .
Page Count: 4
|Open PDF In Browser||View PDF|
CS2010: Data Structure and Algorithms - HT: Assignment 1 In this assignment you will implement a number of common sort algorithms and compare their performance for different input files. You will also write JUnit tests to test your code. Total points for this assignment: 200 (100 automatic, 100 marked by demonstrators) The following will be marked: 1. Correctness of your results (eg items are sorted), JUnit tests, and test code coverage – automatic mark through web-cat, 100 points 2. Correct implementation of sort algorithms (eg your MergeSort method implements merge sort rather than another kind of sort) and results of running time comparisons – marked by demonstrators, 100 points Submission and automatic marking is through https://webcat.scss.tcd.ie/cs2012/WebObjects/WebCAT.woa. Submission of final version both through Web-CAT and Blackboard. Deadline: February 15th 2018 23:45 . Late assignments will be deducted 40 points per day Please submit only SortComparison.java and SortComparisonTests.java in a single zip file. Do not submit input files. Assignment specification 1. Implementation Download SortComparison.java file. Write a java class SortComparison in SortComparison.java file (please do not use custom packages as web-cat will give an error) which should implement the following methods • • • • • • static double insertionSort (double a); static double quickSort (double a); static double mergeSort (double a); static double shellSort (double a); static double selectionSort (double a); static double bubbleSort (double a); In each of the methods parameter a is an unsorted array of doubles. Each method should sort the elements in ascending order and return a sorted array. Each method should implement a different sorting algorithm, specified in method name. Note that for some of the algorithms you will need to add additional methods apart from the ones listed above. 2. Testing Download SortComparisonTest.java file. Write a java class SortComparisonTest in SortComparisonTest.java file, which should implement JUnit tests for SortComparison. Your goal is to write enough tests so that: • Each method in SortComparison.java is tested at least once, • Each decision (that is, every branch of if-then-else, for, and other kinds of choices) in SortComparison.java is tested at least once, • Each line of code in SortComparison.java is executed at least once from the tests. The submission server will analyse your tests and code to determine if the above criteria have been satisfied. 3. Algorithm performance comparison Create a main method in SortComparisonTest that runs all the experiments on SortComparison described below and prints the time in milliseconds that each method execution took. This method will not run on the submission server, but you should run it locally on your computers. You need to record the results in a comment at the top of your SortComparisonTest file. Your experiments in this section should be run from within the provided main method. Do not run these experiments from within a jUnit test. The following input files are available for download from Blackboard: • • • • • • • numbers10.txt – contains 10 random decimal numbers, one per line numbers100.txt – contains 100 random decimal numbers, one per line numbers1000.txt – contains 1000 random decimal numbers, one per line numbers1000Duplicates.txt – contains 1000 random decimal numbers, one per line, but those 1000 consist of only up to 100 unique ones numbersNearlyOrdered1000.txt – contains 1000 decimal numbers, one per line, where most of the numbers are in correct ascending order, with approx. ~6% of the numbers out of place numbersReverse1000.txt – contains 1000 decimal numbers, one per line, sorted in reverse (ie descending) order numbersSorted1000.txt - – contains 1000 decimal numbers, one per line, sorted in ascending order In the comment at the top of your SortComparisonTest record the time it took to execute each of 6 methods implementing 6 different sorting algorithms, for each of 7 different input files, containing different size and type of input. Run each experiment 3 times and record the average running time. Your results should be displayed in a format that enables easy comparison per algorithm and per data type, for example, as in the table below. 10 random 100 random 1000 random 1000 few unique 1000 nearly ordered 1000 reverse order 1000 sorted Insert Quick Merge Shell Selection Bubble Also, in the comment at the top of your SortComparisonTest file please answer the following questions: 1. Which of the sorting algorithms does the order of input have an impact on? Why? 2. Which algorithm has the biggest difference between the best and worst performance, based on the type of input, for the input of size 1000? Why? 3. Which algorithm has the best/worst scalability, ie, the difference in performance time based on the input size? Please consider only input files with random order for this answer. 4. Which algorithm is the fastest for each of the 7 input files? For fun: This part will not be marked, but if you are curious you could also try the following: 1. Add counters to sort methods that count the number of value comparisons, and value swaps for each of the sort algorithms, to compare the numbers of each per algorithm, to see where the performances gains come from 2. Blackboard assignment also contains a number of files with 10,000 and 100,000 numbers (in different orders) – sorting these files with some of the algorithms takes too long to be feasible in the assignment, but if you are curious about even greater differences in scalability and performance the larger the input gets, you can play with these after submitting the assignment. 3. Implement a multi-threaded version of merge sort and compare its performance to singlethreaded one. Appendix: reminder of general assignment instructions from Semester 1 Please see a walkthrough on how to submit an assignment on Web-CAT. When you upload code for an assignment to the submission server, it compiles it and runs your JUnit tests, giving you back an automatic score. This score is part of your marks for this assignment; the other part is given manually by the teaching staff. You can improve and reupload your code to improve your score. The only limit is the submission deadline. For security reasons the submission server is only accessible from the campus network. If you want to access it from home you need to connect to the campus network via a Virtual Private Network (VPN) with your SCSS account. Instructions. Students are allowed to discuss assignments but not to share code! Sharing code will result in reduced marks for all students involved and the consequences described in the College rules. If you discuss an assignment with fellow students then you must write the names of the students in your submission. All students must complete the College's online seminar about plagiarism before submitting any assignment. If you are having trouble with assignments then you can attend both lab hours, which will give you more contact hours with teaching staff. If you are seeking support with more basic Java programming you can additionally attend the Undergraduate Programming Centre. • • • • • Write your name next to @author at the beginning of each file Write the names of people you discussed this assignment with under the @author line. Do not share code and do not write code for others! You need to adequately test each method in your source code by adding sufficient jUnit tests Do not import data structures from the java libraries. The submission server for this assignment will open shortly.
Source Exif Data:
File Type : PDF File Type Extension : pdf MIME Type : application/pdf PDF Version : 1.5 Linearized : Yes Author : Ivana Dusparic Comments : Company : Create Date : 2018:01:22 15:11:35Z Modify Date : 2018:01:22 15:11:37Z Source Modified : D:20180122151045 Subject : Language : EN-IE Tagged PDF : Yes XMP Toolkit : Adobe XMP Core 5.6-c015 84.159810, 2016/09/10-02:41:30 Metadata Date : 2018:01:22 15:11:37Z Creator Tool : Acrobat PDFMaker 15 for Word Document ID : uuid:b5a4d77e-82a3-4255-9d8c-48f108f88daa Instance ID : uuid:0900c3fc-fb3a-4d87-8dde-c560b9231272 Format : application/pdf Title : Description : Creator : Ivana Dusparic Producer : Adobe PDF Library 15.0 Keywords : Page Layout : OneColumn Page Count : 4EXIF Metadata provided by EXIF.tools