Page 1 of 9

Cardiff School of Computer Science and Informatics Coursework Assessment Pro-forma

Module Code: CMT219 Module Title: Algorithms, Data Structures and Programming Lecturer: Dr Daniela Tsaneva, Neetesh Saxena Assessment Title: Algorithms Data Structures and Design Patterns Assessment Number: 2 Date Set: 25th March 2022 Submission Date & Time: 13th May 2022 at 9:30am British Summer Time Return Date: 10th June 2022

This coursework is worth 50% of the total marks available for this module. If coursework is submitted late (and where there are no extenuating circumstances):

1. If the assessment is submitted no later than 24 hours after the deadline, the mark for the assessment will be capped at the minimum pass mark;

2. If the assessment is submitted more than 24 hours after the deadline, a mark of 0 will be given for the assessment.

Your submission must include the official Coursework Submission Cover sheet, which can be found here: https://docs.cs.cf.ac.uk/downloads/coursework/Coversheet.pdf

Submission Instructions

Your coursework should be submitted through Learning Central. Your submission should include:

Description Type Name

Cover sheet Compulsory PDF (.pdf) file [student number].pdf

Part

1

ONE ZIP archive file (and no more than one) containing all the source code files for your answer to questions of Part 1

Compulsory One ZIP (.zip) archive

[student number]_Part1Code.zip

e.g., C1234567_Part1Code.zip

ONE PDF file (and no more than one) which contains a written justification for your design of the program and screen shots showing an example of the output of each application

Compulsory One PDF (.pdf) file

[student number]_Part1.pdf

e.g., C1234567_ Part1.pdf

Part

2

ONE PDF file (and no more than one) which contains the diagrams, descriptions, explanations, discussion, program listings (extracts from the code which show clearly what you did in order to complete the Tasks).

Compulsory PDF (.pdf) file [student number]_Part2.pdf e.g., C1234567_ Part2.pdf

ONE ZIP archive file (and no more than one) containing all the source code files for your answers for Part 2

Compulsory ZIP (.zip) archive file

[student number]_Part2Code.zip e.g., C1234567_Part2Code.zip

Any code submitted will be run on a university machine and must be submitted as stipulated in the instructions above.

Any deviation from the submission instructions above (including the number and types of files submitted) will result in a reduction of 20% of the attained mark.

Staff reserve the right to invite students to a meeting to discuss coursework

submissions

Page 2 of 9

Assignment

PART 1 – Algorithms and Data Structure

[Total: 50 marks]

All code must be written by you, although you can use the lecture notes (and lab exercises), textbooks, and the Oracle Java website for guidance.

A) Extracting words from a text document is the first step for many text-based

applications of artificial intelligence, e.g., detecting abusive tweets on Twitter. This task asks you to extract all valid words from the document “Input219.txt” based on a given vocabulary “google-10000-english-no-swears.txt1” (you can download both files from the Learning Central). Specifically, if a word token from “Input219.txt” matches a word in “google-10000-english-no-swears.txt” (case insensitively), you keep that word, otherwise you discard it. You should use ArrayList to store data within the Java program, so the return of this task is an ArrayList containing all valid words from “Input219.txt”. Note that these two text files are relatively big, you should consider how to make your program efficient.

[30 marks]

(Functionality: 16, Design: 10, Ease of use: 2, Presentation: 2)

B) Implement the merge sort (the pseudocode for merge sort is available in the lecture slides) in order to sort the words obtained in question (A) in alphabetical order, i.e., the output of your program will be the sorted words in alphabetical order. For the merge sort algorithm write a method e.g. mergeSort(…), measure

• time that is needed to sort the first 100 of the words, first 200 of the words, first 300 of the words, etc. up to all words by the algorithm.

• count the moves/comparisons that occur while sorting elements

(Before attempting this exercise you should work through the Algorithms lab exercises, available on Learning Central. The techniques used there will help you to work out how to approach this part of the coursework, in particular there are examples on how to time algorithms and count the moves and swaps.)

[20 marks] (Functionality: 12, Design: 4, Ease of use: 2, Presentation: 2)

1 This vocabulary contains a list of the 10,000 most common English words in order of frequency of the Google's Trillion Word Corpus.

Page 3 of 7

Criteria for Assessment of PART 1

Credit will be awarded against the following criteria.

Functionality • To what extent does the program perform the task(s) required by the question

and how efficient it is. Design

• How well designed is the code, particularly with respect to the ease with which it may be maintained or extended. In particular, consideration will be given to: • Use of appropriate types, program control structures and classes from the

core API. • Usage and structure of appropriate classes and methods. • Consideration of achieving optimised algorithms. • An ‘excellent’ design of code will carefully consider using most suitable data

structures and aiming for efficient and elegant algorithms. A ‘bad’ design of code pays little/no attention to data structure and algorithm efficiency.

Ease of use

• Formatting of input/output. • Interaction with the user. • How does the code deal with invalid user input? Will the applications crash for

certain data?

Documentation and presentation • Appropriate use of comments. • Readability of code. • Clear and appropriate screenshots.

Page 4 of 7

Criteria for Assessment of PART 1

Criteria Distinction (70-100%)

Merit (60-69%)

Pass (50-59%)

Fail (0-49%)

PART 1 – Algorithms and Data Structure

Functionality Fully working application that demonstrates an excellent understanding of the assignment problem using relevant Java approach.

All required functionality is met, and the application is working properly with some minors’ errors

Some of the functionality developed with and incorrect output major errors.

Faulty application with wrong implementation and wrong output.

Design Using most suitable data structures and efficient and elegant algorithms.

Using good data structures and suitable algorithms.

Some of the data structures are not suitable and the algorithms not efficient.

Pays little/no attention to data structure and algorithm efficiency.

Ease of use Excellent formatting of input/output, and interaction with the user, the application deals well with invalid user input and doesn’t crash for any data.

Good formatting of input/output, and interaction with the user, the application has some minor errors with invalid user input and doesn’t crash for most data.

Suitable formatting of input/output, and interaction with the user, the application doesn’t deal with invalid user input and crashes for some data.

Bad formatting of input/output, and unsuitable interaction with the user, the application doesn’t deal with invalid user input and crashes for most data.

Documentation and Presentation

Appropriate use of comments, readability of code, clear and appropriate screenshots.

Some use of comments, the code is mostly readable, reasonable screenshots.

Few comments, not good readability of code, not clear screenshots.

No comments, bad readability of code, no screenshots.

Page 5 of 7

PART 2 – Design and Implementation of Design Patterns

[Total: 50 marks]

Note: A list of files is included in the present coursework specification at the end for your convenience.

Download the ZIP file from Learning Central that contains the source code files of this task: Product.java, ProductRecommender.java, ChoiceStrategy.java, MostFuturisticStrategy.java, MostPracticalStrategy.java. This Java program creates two new products and then chooses between them, first by applying the MostFuturisticStrategy and then the MostPracticalStrategy. Futuristicness and practicality are both rated on a scale between 1(low) and 5 (high).

A) State the purpose of the Strategy design pattern. [4 marks]

B) Complete the implementation of the MostFuturisticStrategy class with a

chooseBetween (Product a, Product b) method that returns Product a if its

futuristicness is greater than or equal to the futuristicness of Product b; and

returns Product b otherwise. [8 marks]

C) Complete the implementation of MostPracticalStrategy with a chooseBetween

(Product a, Product b) method that returns Product a if its practicality is greater

than or equal to the practicality of Product b; and returns

Product b otherwise. [8 marks]

D) Modify the doExample () method in the ProductRecommender class, so that

each of the strategies can be applied, in order generate the following output:

Current strategy: choose most futuristic Chosen vehicle: DeLorean DMC-12 Strategy changed: choose most practical

Chosen vehicle: LDV Maxus [10 marks]

E) Draw a UML class diagram representing the resulting Strategy design pattern in

this program. [10 marks]

F) Explain in your own words the role of each of the classes and the changes made

in realising this design pattern as well the relationships between these classes

and the interface. [10 marks]

Criteria for Assessment of PART 2

Credit will be awarded against the following specific criteria. Ability to:

• Understand the purpose of a Java program and apply principles of good object-

oriented design in order to create a critique and/or modify the supplied programs

(check the source code files provided);

• Apply and implement design patterns that pertain to a specified programming task;

• Reflect on the application of design patterns in OO Java programs.

Page 6 of 7

Feedback on your performance will address each of the above criteria.

Criteria for Assessment of PART 2

Distinction (70-100%)

Merit (60-69%)

Pass (50-59%)

Fail (0-49%)

PART 2 – Design and Implementation of Design Patterns

An excellent implementation, showing a good degree of insight and reflection, and the code is of good quality.

The tasks have been completed, the code “works”, and some clear insight has been shown.

The tasks have been completed, the code “works”, but minimal insight has been shown.

The submitted answer only addresses the tasks to a very limited extent. Some attempt has been made to address the tasks, and the code mostly works.

Learning Outcomes Assessed This assignment particularly addresses the following module learning outcomes:

• 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

Code Reuse Your solutions may make use of any classes in the Core Java API. You may also reproduce small pieces of code from:

• The CMT219 course handouts and solutions

• java.oracle.com

• any textbooks provided:

• The section reproduced does not form the entire solution to a single question

• The source of the code is clearly referenced in your source code

• Your code is commented to demonstrate clearly that you understand how the

reproduced code works (i.e., explain why types have been selected, why other

language features have been used, etc.)

You may NOT reproduce code written by any other student or code downloaded from any other website.

If you are in any doubt about whether you may include a piece of code that you have not written yourself, ask the lecturer before submitting.

See “Referencing in code guidance” at Learning Central → COMSC-SCHOOL → Learning Materials → Referencing in code guidance.

Feedback and Suggestion for Future Learning Feedback on your coursework will address the above criteria. Feedback and marks will be returned via Learning Central. There will be opportunity for individual feedback during an agreed time.

Page 7 of 7

Appendix: Program listing for PART 2

public class ProductRecommender { ChoiceStrategy

myStrategy;

public static void main(String args[]) {

ProductRecommender recommender=new ProductRecommender();

recommender.doExample();

}

public void doExample() {

Product p1=new Product("DeLorean DMC-12", 5, 1);

Product p2=new Product("LDV Maxus", 1, 5);

System.out.println("Current strategy: choose most futuristic");

// Add code here to create a MostFuturisticStrategy and

// print out the chosen vehicle according to this strategy

System.out.println("Strategy changed: choose most practical");

// Add code here to create a MostPracticalStrategy and

// print out the chosen vehicle according to this strategy

}

}

public interface ChoiceStrategy { public Product

chooseBetween(Product a, Product b);

}

public class MostFuturisticStrategy implements ChoiceStrategy {

// Complete this with an implementation of

// chooseBetween(Product a, Product b) which returns

// Product a if its futuristicness is greater than or equal

// to that of b; and returns Product b otherwise

}

public class MostPracticalStrategy implements ChoiceStrategy {

// Complete this with an implementation of

// chooseBetween(Product a, Product b) which returns

// Product a if its practicality is greater than or equal

// to that of b; and returns Product b otherwise

}

public class Product { public String

name; public int

futuristicness;

public int practicality;

public Product(String theName, int theFuturisticness, int thePracticality) { name=theName;

futuristicness=theFuturisticness;

practicality=thePracticality;

}

}