Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due
CPT108 Data Structures and Algorithms
Semester 2, 2024-25
Assignment 1: Algorithm Analysis
|
Weighing |
Total marks available: 77, accounting for 11% of overall module marks. |
|
Release date |
3pm CST Wednesday 7 March 2025 |
|
Due date |
11:59pm CST Sunday 16 March 2025 |
|
Submission platform |
You are required to submit an electronic copy of the report (as PDF) and ALL source code that you have implemented for the assignment via Learning Mall (LM). Details can be found in the main content of this assignment. You are allowed ONE submission only. It is your responsibility to submit and upload the correct document. |
|
Assignment format |
ALL answers must be written in English. The report must: • be submitted as a PDF file • contain headings and subheadings • have 3cm margins • use a legible font (e.g., Calibri, Arial or Times New Roman) • be presented in 11 point font size with 1.5 line spacing • be paginated |
|
Late submissions |
Penalties will apply for any work submitted after the due date unless you have obtained a formal extension prior to the date for submission. The penalty applied will be 5% of the available marks for the assignment for each working day or part thereof that the assignment is late. The penalty will be capped at five working days (120hours) from the assignment deadline. Work submitted after five working days will receive a grade of zero. |
Assignment 1: Algorithm Analysis
1 Purpose
Analysis of algorithms is the area of computer science that provide tools to analyse the efficiency of different methods of solutions. Efficiency of an algorithm depends on these parameters: (i) how much time, (ii) memory space, and (iii) disk space it requires. Analysis of algorithms is mainly used to predict performance and compare algorithms that are developed for the same task, which provides guarantees for the performance and helps us to understand theoretical basis.
A complete analysis of the running time of an algorithm involves the following steps:
• Implement the algorithm completely.
• Determine the time required for each basic operation.
• Identify unknown quantities that can be used to describe the frequency of execution of the basic operations.
• Develop arealistic model for the input to the program
• Analyse the unknown quantities, assuming the modeled input.
• Calculate the total running time by multiplying the time nby the frequency for each operation, then adding all the products.
This assignment aims to develop you insight into the performance of algorithms. You will analyse the different sorting algorithms and compare their running times on a number of dataset with varying sizes.
Note that the main emphasis is not so much on coding but is on understanding the performance of the algorithms and why they perform well and poorly on different inputs. In particular, we are interested in the following aspects of performance:
• How the performance varies as the size of the input increases,i.e., the rate of growth of the performance measures;
• How the algorithms perform on special kinds of inputs, e.g., those that also already in ascending or descending order, and those in which there are few items repeated many times; and
• Without changing the default Java Virtual Machine (JVM) heap size, what is the maximum length of the list the implementations can handle.
2 Tasks
Step 1: Test data preparation
In this assignment, we are going to investigate how different types of input will affect the performance of an algorithm. In doing do, you will need to generate 4 random permutations of input, as specified below.
Task1
In this task, you are required to create a new class and implements the methods described below.
• A method to generate a list of number in ascending order.
• A method to generate a list of number in descending order.
• A method to generate lists of randomly generated numbers. To do this you may need to use the random number generator from Java (java.util.Random).
• A method to generate lists of numbers which consists of a few items repeated many times in different patterns of your choice (i.e., you can decide how the numbers in a list appear, such as {1, 1, 1, 2, 2, 4, 4, 4, 9, 9, 9, 9}, or {1, 1, 1, 0, 0, 5, 5, 9, 9, 3, 3, 2, 2}, etc.). To simplify the implementation, you can restrict the possible numbers of repeat to a small range, say from 1 to 9.
All methods above should allow users to input the size of the list to be generated.
To simplify the test scenarios, you can assume all numbers generated are to be integers.
Step 2: Performance analysis
Once you have implemented the functions above, you can then use them to generate different types of data with varying sizes, and investigate the performance of different sorting algorithms under different scenarios.
You need to select at least three sorting algorithms from the table below, with at least one algorithm from each category.
Category A Category B
Bubble sort Merge sort
Insertion sort Quicksort
Selection sort Heap sort
For the sorting algorithms selected, you can implement the algorithms yourself (using a programming language of your choice), use the code available from the module’s reference book:
• Michael T. Goodrich, Roberto Tamassia, and Michael H. Goldwasser (2014). Data Structures and Algorithms in Java. 6th ed. Wiley Publishing, Inc.
or any code available elsewhere. However, this is your responsibilities to ensure the correctness of the code that you are going to use in all tasks listed below!
Task 2
Use the functions implemented in Task 1, run each of the sorting algorithm selected on the various types of lists of increasing lengths and measure their performance. The actual lengths of the lists for realistic timing in milliseconds depend on the speed of your processor. A maximum length of 10,000 maybe appropriate, but on slower processors this maybe too large. “Experiment” is the only mean of knowing the answer!
For each type of input, create about 10 lists of lengths evenly spaced up to the maximum (of your choice), use copies of each of these data as input to each of the sorting algorithm and plot graphs of the timing of each algorithm against the size of the lists.
What conclusion can you make from the results of the experiment?
• You should be aware that the actual central processing unit (CPU) time can be affected not just by the algorithm running, but by other processes which may interrupt, so try to minimize other processes running at the sametime.
• Make sure the same set of data has been used when evaluating the performance of different sorting algorithms, including the case of randomly generated lists!
There area few ways that we can use to capture the running time of a program. Some com- monly used classes include: java.time.Duration, and java.time.Instant. Besides, the Java system functions: System.currentTimeMillis() and System.nanoTime() will return you the current time in millisecond and nanosecond, respectively, which maybe useful in measuring the execution time used.
Your work now is to design and implement your own approach(es) to measure the execution time of sorting a list and applies it to the sorting algorithms. Again, you should start by first analysing the input, output, constraints, and abstraction of the problem before starting your implementation.
Task3
In addition, try measuring the execution time of different sorting algorithms with small sizes: 5, 10, 15, ..., 100, and plot your results on another graph.
Together with the results in the Task 1, what conclusion can you make with respect to the size of the input?
Step 3: Memory usage
Task 4
Without changing the default heap size of the JVM, find the maximum size of the array that each sorting algorithms can handle on your machine before the JVM run out of memory.
What conclusion can you make from the results of the experiment?
3 Submission requirements
Your assignment has to submit to Learning Mall (LM) with the following items.
A. A report that includes the following items:
1. A cover sheet stating the student number.
2. Problem definition. You should clearly express the idea behind this assignment.
3. Technique used. Abrief description on the technique that you used to produce the datasets in Task 1.
4. Findings. You should demonstrate the results with table(s) and/orchart(s), where appropriate.
5. Discussion. Discuss the results that you have obtained from Tasks 2to 4. Based on the results that you have obtained, what conclusions you can draw about the sorting algorithms selected in terms of computational time complexity and memory usage?
B. A copy of ALL source codes that you have implemented, including the implementation of the selected sorting algorithms.
You should compress the report (as PDF file) and ALL source codes into a single “.zip” file before submission. Failure to follow this requirement will result in mark deduction.
4 Marking Scheme
|
# |
Item |
Weight |
|
1 |
Code for generating different types of lists |
20 |
|
2 |
Code for performance analysis and sorting algorithms |
15 |
|
3 |
Discussion of timing on lists of ascending and descending orders |
8 |
|
4 |
Discussion of timing on randomly generated lists |
8 |
|
5 |
Discussion of timing on lists with repeated patterns |
8 |
|
6 |
Discussion of timing when list sizes is small |
8 |
|
7 |
Discussion on memory consumption of different sorting algorithms |
10 |
|
|
Total |
77 |