Assignment1 Instructions

Assignment1%20instructions

Assignment1%20instructions

Assignment1%20instructions

Assignment1%20instructions

Assignment1%20instructions

User Manual: Pdf

Open the PDF directly: View PDF PDF.
Page Count: 4

DownloadAssignment1 Instructions
Open PDF In BrowserView 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                      : 4
EXIF Metadata provided by EXIF.tools

Navigation menu