Hello, if you have any need, please feel free to consult us, this is my wechat: wx91due

Assessment Proforma 2024-25

Key Information

Module Code	CMT219
Module Title	Algorithms, Data Structures & Programming
Module Leader	Dr Crispin Cooper
Module Moderator	Dr Yuhua Li
Assessment Title	Coursework
Assessment Number	2
Assessment Weighting	50%
Assessment Limits	This individual assessment consists of TWO parts to be completed.

The Assessment Calendar can be found under ‘Assessment & Feedback’ in the COMSC-ORG-SCHOOL organisation on Learning Central. This is the single point of truth for (a) the hand out date and time, (b) the hand in date and time, and (c) the feedback return date for all assessments.

Learning Outcomes

This assignment particularly addresses the following module learning outcomes:

· Write code in a given programming paradigm (for example Object-Oriented) using a high-level programming language

· Reflect upon the relationship between system and code design and implementation in the given programming paradigm

· Critically evaluate design patterns and their applicability to different scenarios

· Select and use appropriate algorithms and data structures to provide best performance in a given scenario

Submission Instructions

The coversheet can be found under ‘Assessment & Feedback’ in the COMSC-ORG-SCHOOL organisation on Learning Central.

All files should be submitted via Learning Central.  The submission page can be found under ‘Assessment & Feedback’ in the CMT219 module on Learning Central.  Your submission should consist of multiple parts.

Any deviation from the submission instructions above (including the number and types of files submitted) will result in a reduction in marks for this assessment by 20%.

If you are unable to submit your work due to technical difficulties, please submit your work via e-mail to [email protected] and notify the module leader.

Assessment Description

PART 1: ALGORITHMS

In thisindividual work, you will implement sorting algorithms and then test their performance. This part of the assignment consists of not just coding, but also testing your code and providing evidence. Note that when your code is complete, you still have a reasonable amount of work to do -- so start early!

Storing and Sorting Items

Consider a manufacturing company, XYZ that runs 24 hours and 7 days operational. The company produces a very large number of items per week. In a week from Monday to Sunday, it produces 20, 300, 4000, 50000, 75000, 100000 and 500000 items, respectively. Each item has a random integer identifier.

You are expected to create an Integer ArrayList and store the item IDs for each day of the week – so you will have 7 different ArrayList storing items accordingly. Now, you are required to randomly generate item IDs from 1000 to 600000 for each day as stated above.  

Now think about the logic of applying the Quicksort algorithm and first write its pseudocode. Once you’re done, convert your pseudocode into a Java code and run your code successfully.

Efficiency Testing

Once you have implemented your algorithm, you need to test it to see how long your sorting algorithm takes to run. You should test the speed of the algorithm on all three: random, sorted and reverse-sorted lists. You are expected to use System.currentTimeMillis() to estimate the execution time. Using currentTimeMillis only gives an accurate time estimate if the function takes a long time to run (at least a couple of seconds). Run your code a number of times and compute the average time, print the output screenshot and discuss in the report -- reflect how many iterations are sufficient to provide an accurate time of the algorithm.

Developing a Better Sorting Algorithm

Quicksort is faster when the number of items to be sorted in a list is large. But when lists are small enough, quicksort runs slower than some of the Θ(n2) algorithms. 

If you carefully notice, each time the quicksort method is recursively called, the sublist to be sorted could be either small or large. The time to sort one small sublist with a faster algorithm can be negligible. However, sorting such hundreds of small sublists can make a difference in the overall efficiency of the sort.  

Here, you will combine Quicksort with another sorting algorithm to create the fastest possible sorting algorithm. We call this “hybrid Quicksort”. You have several options -- 

· Use Quicksort until the sublist gets “small enough”, and then use selection sort to sort the small lists.

· Use Quicksort until the sublist gets “small enough”, and then use insertion sort to sort the small lists.

· Use Quicksort to "mostly" sort the list, i.e., use the Quicksort to sort any sublists larger than a cut-off size, and then stop. The list will now be mostly sorted, and you can use selection sort on the entire list to quickly complete the sorting.

· Use Quicksort to "mostly" sort the list, i.e., use the Quicksort to sort any sublists larger than a cut-off size, and then stop. The list will now be mostly sorted, and you can use insertion sort on the entire list to quickly complete the sorting.

· Use some other method of your own devising.

What does “small enough” mean?  You can try a percentage of the list (say, 5% or 10%), or an absolute number (8, 10, 15, 100 elements, etc.), or something else of your choice. What does “mostly” sort mean? A cut-off size of the items to be sorted in the list.

You should test your choices to ensure that you have the most efficient algorithm possible. You should also be sure that your hybrid Quicksort has reasonable performance on all lists: sorted and inverse sorted lists as well as random lists. Try various methods for choosing the pivot element, to try to get the best possible behaviour.

You need to complete the following tasks and submit them electronically:  

Q1-A.Source code for your hybrid sorting algorithm sorting all items in the ArrayLists for the week and performing efficiency testing for sorted and inverse sorted lists as well as random lists for each list size in these tests. [20 marks]

Q1-B.Write a 1000-word (maximum) explanation of how you developed your hybrid sorting algorithm, what combinations of the algorithms/approaches you tried, what different parameters you chose, and how much of a difference these changes made to the efficiency of your algorithm, including the run time complexity. [30 marks]

Create asingle report (.doc or .pdf) file containing the following:

(i) Screenshot of the final output for efficiency testing from Q1-A. Make sure your hybrid quicksort has reasonable performance on all lists, sorted and inverse sorted lists as well as random lists for each list size. 

(ii) Your explanation for Q1-B above.

It is okay for you to discuss solutions to Part-1 with your classmates. However, no collaboration should ever involve looking at one of your classmate's source codes. It is usually fairly easy to determine that someone has copied a code, even when the individual copying the code has changed identifier names and comments.

PART 2: DESIGN PATTERNS & MULTITHREADING

Parts (a)-(c) of this question can be started after you are taught the Observer pattern, in the Design Patterns sessions. Based on content you are taught in Design Patterns, your solution to part (a) is likely to change the colour of some, but not all balls. The Multithreading session will cover additional material needed to achieve fully working code for part (a), and to answer part (d).

Download and unzip BouncingBalls.zip, which contains three java source files for a small app:

BouncingBalls.java

ColorPublisher.java

ColorSubscriber.java

Build and run the application, which launches a window containing a large number of bouncing balls. Two buttons are also present which are intended to change the colour and size of the balls, however,the buttons intentionally do not work in the app you have just downloaded:it will be your task to implement this functionality.

Note also that BouncingBalls.java contains Graphical User Interface (GUI) code which has not been covered in this course. Its purpose is explained in the comments, however you are not expected to understand the GUI code in any detail. The comments alone give sufficient detail on how the GUI works for you to complete your part of the app.

BouncingBalls.java makes use of an Observer pattern to communicate colour changes to each of the balls, when the buttons are clicked. This pattern is currently incomplete.Add code to ColorPublisher.java to complete the pattern, (i) allowing each ball to subscribe to the ColorPublisher when it calls the addSubscriber() method, (ii) allowing buttons to publish colour changes to all subscribed balls, by calling ColorPublisher’s publish() method.

· DO NOT, AT THIS STAGE, change the code in BouncingBalls.java or ColorSubscriber.java. Your edits to ColourPublisher.java should make the app work correctly while leaving the other files as they are. You should, however, read the code of BouncingBalls.java to understand how the ColorPublisher class is used there, and also ColorSubscriber.java which is used in both of the other files.

· DO test your changes by running the app.

Now, answer the following questions directly on the assessment page on Learning Central.

(a) Paste the full contents of your modified ColorPublisher.java file into the answer box on Learning Central. Make sure to paste the file contents, and do not attach the file itself. [12 marks].

(b) The Observer pattern is actually a bad choice for setting the colour and size of balls in this particular application. Why? [12 marks, max 250 words].

(c) Describe how each BallThread could obtain the correct colour and size without using an Observer pattern. To answer this question, you may wish to experiment with editing BouncingBalls.java and testing your simplified solution, but you are not required to submit code. [12 marks, max 60 words].

(d) The app uses a separate thread to process the movement of each ball. Is this a good choice of approach for the app? Why? [14 marks, max 150 words].

Assessment Criteria

Credit will be awarded against the following criteria.

PART 1:

High Distinction (80%+) –[Q1-A] Fully working codesthat demonstrate an excellent understanding of the assignment problem and scenarios using a relevant Java approach. Excellent formatting of input/output, catch exception handling, the application deals well with invalid user input and doesn’t crash for any data. Excellent and consistent code layout. Appropriate use of comments. [Q1-B] All required outputs. Clear, concise, reflective and appropriate write-up with all justified choices. 

Distinction (70-79%) –[Q1-A] Fully working codesthat demonstrate a very good understanding of the assignment problem and scenarios using a relevant Java approach. Very good formatting of input/output, catch exception handling, the application deals well with invalid user input and doesn’t crash for any data. Very good and consistent code layout. Appropriate use of comments. [Q1-B] All required outputs. Clear and appropriate write-up with all justified choices. 

Merit (60-69%) – [Q1-A] All required functionalities of the codes are met (with no runtime error)demonstrating a good understanding of the assignment problem and scenarios using a relevant Java approach. Good formatting of input/output, catch exception handling, the application may have a few errors with invalid user input. Good and consistent code layout. Good use of comments. [Q1-B] Most of the required outputs are presented. Clear and suitable write-up with mostly justified choices. 

Pass (50-59%) –[Q1-A] Some required functionalities of the codes are met (with only minor errors)demonstrating some understanding of the assignment problem and scenarios using a relevant Java approach. Some formatting of input/output, catch exception handling, the application may have some errors with invalid user input. Some and partially consistent code layout. Some use of comments. [Q1-B] Only some required outputs. Some write-up with partially justified choices.

Marginal Fail (40-49%) - [Q1-A] Faulty codes with wrong implementation (with major errors), partially demonstrating the understanding of the assignment problem and scenarios using a relevant Java approach. Bad formatting of input/output, catch exception handling, the application has major errors with invalid user input. Modest and inconsistent code layout. poor use of comments. [Q1-B] Only a few required outputs. Partially clear and rough write-up with poorly justified choices.

Fail (0-39%) - [Q1-A] Faulty codes with incorrect implementation (code does not run), poorly demonstrating the understanding of the assignment problem and scenarios using a relevant Java approach. Poor formatting of input/output, catch exception handling, the application has major errors with invalid user input, and crashes with most data. Poor and inconsistent code layout. No use of comments. [Q1-B] No or only a few required outputs. Unclear and poor write-up with no justified choices.

PART 2:

2a: 100% for fully correct, thread safe code. 50% for mostly correct code with some bugs (e.g. some, but not all balls change colour correctly). 0% for non working code.

2b-2d: 100% for correct answers covering all key points, with partial marks awarded proportionately if some points are missed.

Help and Support

Questions about the assessment can be asked during weekly lab classes, and on the departmental StackOverflow (StackOverflow questions must be tagged cmt219).

Feedback

Feedback on your coursework will address the above criteria. Feedback and marks will be returned via Learning Central. Feedback from this assignment will be useful for your development as a programmer and also your dissertation, depending on your choice of project.