Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

UFCFYR-15-2

Advanced Algorithms

2022-23

Section 1: Overview of Assessment

This assignment assesses the following module learning outcomes:

1. Formulate problems as abstract models which can be solved by generic algorithms and mathematical methods.

2. Critically evaluate, the effectiveness of the design, efficiency of the applications of algorithms for processing data on a wide range of problems.

3. Execute and implement algorithms in a programming language.

The assignment is worth 50% of the overall mark for the module.

Broadly speaking, the assignment requires you to select and implement appropriate data structures to implement designed algorithms to solve the specific problems and satisfy system requirements such as high performance and reasonable memory usage.

Section 2: Task Specification

There are two tasks in total. Task 1 consists of four subtasks and Task 2 includes two mini reports and one video demonstration. The assessment weight of each task is given in the following specifications.

Note that the marking criteria are based on the efficiency and other compulsory requirements of the program rather than simply whether your program can generate the correct results or not. Please read the marking criteria carefully and thoroughly for each task before you start.

Task 1: (80%)

Task 1.1 (20%) remove duplicated elements with a special rule

You are requested to develop an algorithm to read in a large amount of numbers, remove duplicated numbers with a bespoke rule, and write it back to a new file. However, your algorithm must follow the special rule to determine which unique element will be reserved.

Rule:

The last element in the sequence of the duplicated elements can be retained only. For example, the list like [1, 2, 1, 3, 1] is processed and its output should be [2, 3, 1] because there are three ‘1’ in the list, and the red one can be retained as it’s the last one, and the first and second ones are removed.

There are more examples as follows to help you to understand the rule.

[2, 1, 2, 3, 1] -> [2, 3, 1]

[3, 2, 1] -> [3, 2, 1]

[1, 2, 3, 3, 2, 1] -> [3, 2, 1]

[3, 2, 1, 1, 2, 3, 2, 1, 3, 2] -> [1, 3, 2]

You should design an efficient algorithm to implement this removing operation or pick-up operation with the consideration of fast execution and less memory usage. The higher mark is rewarded in terms of how efficient your program is and how much memory the program uses (less is better).

A testing file with massive numbers is provided for testing the speed of the execution.

Task 1.2: (20%) Object classification

This task is for classifying the objects into categories based on the match of the features.

You are given a group of unknow objects, and each has a set of features which are represented by some natural numbers. Meanwhile, you are also provided a group of known objects with the related features. Therefore, you should develop an algorithm to classify these unknown objects into the known object categories if the features of an unknow object match 50% or above of the features of a known object. Note the same unknown object can be classified into multiple categories.

For example, an unknow object X is represented by the feature list [ 3, 1, 8, 9, 7], and a known object Y has the feature list [ 1, 2, 3, 5, 7], and then X should be classified into Y because the match rate is over 50% as 1, 3 and 7 are included in the feature list of Y.

Two testing files, one for unknown objects and the other for known objects, are provided to test the efficiency of your algorithm. Here, each object has an ID, and 6 following numbers for the feature.

Task 1.3: (20%) List processing with parallelism

You are given a list of numbers, and you should develop an algorithm to update each element of the list by the sum of its left element, the right element and itself. If an element has no left or right elements and it uses zero to replace the absent element. The update process should always use the original elements, and the updated elements cannot involve in any update for other elements. For example, the list [1 ,2, 3] should have the new list like [3, 6, 5].

A testing file is provided to test your algorithm. You should first develop a serial version as the benchmark via the execution time.

The result which contains all the names and their frequencies should be saved in a new file. The program must be a parallelized program. Then, a parallel version using Python processes should be developed and compared with the serial version.

Task 1.4: (20%)

You are bidding a railway project which uses the minimal cost to connect all cities. The connect must cover all cities. That is, one city can reach any other cities via the track.

The shareholders provide a list of connected paired cities with the related construction cost. You need to develop an algorithm to calculate the minimal cost to connect all the cities based on the provided data.

Your program should return the minimal cost and a list of pairs of cities with their cost, so that your company can build the railway system based on this connection.

Task 2 (20%)

You should produce two mini reports and one short video to demonstrate your programs.

Task 2.1 (10%)

Explain your design for Task 1 such as the choice of data structure and the logic of your algorithms. You can use pseudocode or workflow diagrams to illustrate your algorithms if necessary, and a pure and clear narrative is also accepted as long as you can make readers understand your design with ease.

You need to focus on the key algorithms only and don’t need to explain any well-known algorithm or secondary procedures. For example, if you use merge sort or binary search, you just mention the algorithm names as we all know what these algorithms are. If you import data from a csv file, you don’t need to explain how the program reads it line by line.

You also need to justify your design choices in terms of effectiveness, efficiency or memory spaces of the system that you have produced. Please check the marking criteria carefully for each task.

You should mention any unoriginal work. For example, if you use any Python library, you should address it in this task. If you use any significant code from open-source projects, you should remark it. Please feel free to use the code from the lab exercises.

The general discuss should be less than 500 words except for the pseudocode and diagrams.

Task 2.2 (5%)

Discuss any issue relating to computational sustainability that system developers should consider. Please use Task 1.4 to discuss the sustainability issue for the national railway services. Please give the reference if you use any formal definitions. This discuss should be less than 500 words.

Task 2.3 (5%)

Produce a short video (less than 8 minutes) to demonstrate your program running and implement each task in order. In the video, you can also emphasize any outstanding design in your program to the markers. Please give the verbal narration, if possible, to explain your operations.

Please produce a file that contains clear instructions about how to run your program or how to set up the environment. It’s very important when you use some Python libraries. You don’t need to give any instruction if your programs are easy to run.

Section 3: Deliverables

One folder in zip format (only) must be uploaded via the relevant link on the module’s space on Blackboard. The zipped file should be names as ‘AACoursework_Your Name_Student Number.zip’.

The link will be available two weeks before the due date and will be communicated to students via an email announcement.

You can produce an independent Python code for each sub-task. So, for this format, GUI or a simple menu is unnecessary.

The submission must contain:

· Python programs for Task 1.1 to Task 1.4

· Any non-standard Python library used in your programs should be included. Your programs must be self-contained. Note that markers won’t install non-standard Python libraries to test your system. The failure of the implementation may be marked 0. Also, you should include all input data or testing data in the folder.

· A word / PDF file for Task 2.1.

· A word /PDF file  for Task 2.2

· A short video for Task 2.3 demonstrating your software running and fulfilling each of the tasks in the correct order.

All program files are saved in Python format (above 3.0). Any other version or other program languages will not be accepted and will not be marked, which results in a zero mark for this coursework.

You are allowed to use any Python data structure or library. However, you do need to give a brief introduction what they are and why to use them. In fact, there are many powerful built-in functions in Python data structures, and you feel free to use them. Again, you must talk about it when these functions may affect the efficiency to a great extent. For example, a Python list has a built-in sort function. You can use it directly rather than write the sort algorithm yourself. But you do need to mention the efficiency of the built-in sort function. That is, you should understand well anything that you use. From another hand, we encourage you to write your own sort algorithm.

Section 4: Academic Offences

This is an individual coursework, and therefore you should individually submit your own original work. In fact, we encourage you to work as a group or cohort. You are free to discuss the solutions for the coursework, however, you should then split up and work alone to finish the work. The identical work is an offence, and the similar work with effortless changes (such as the change of variables names) is considered an offence too.

Please do not share your code with anyone. Even if you don’t share your code on purpose, you are still considered a collusion if the similar work is found. For example, your friend may request your work for a reference, and promise not to copy your code. However, very often they may take the risk when the deadline is approaching. For this case, all the involved students may get the same penalty.

You may use the open-source code and projects or examples and tutorials from YouTube. Actually, we encourage you to take advantage of these on-line sources. However, copy and paste of the on-line code is considered an offence. This is very similar to your English writing. You can use references and we do use a lot of references. However, you cannot simply copy and paste the articles, and you must change it into your own words and give the reference links if necessary. For your own code, if you just use a fragment of on-line or public code to make it accommodative for your own solution, this is totally fine. If you simply add few lines into others’ programs and then claim this is your own work, this is problematic. Please talk to your tutors if you are unsure about how to use the on-line code.

The teaching team is professional about programming and marking. You might be invited for an interview to demonstrate and explain your program if the markers and the module leader doubt the originality of your work.

Section 5: Marking Criteria

The following table (please see next page) gives details of the marking criteria for this coursework. Marks will be awarded for clear rationale justifying design choices.

Clarification in the system design submitted for Task 2.1 can help the markers to map the full logic of the solution into the correct marking section.

Code must be well structured, appropriately commented, neat and efficient. Clear use of functions and reduced repetitions of blocks of code are expected.

The marking band is incremental. For example, the claim of 70-85 means your work has satisfied any precedent band.

NOTE – No hard coded data will be allowed. Hard coded data in the submitted work will result in the work marked at zero.

Section 6: Feedback mechanisms

Formative / Verbal will be provided during practical sessions. Written feedback will be provided on blackboard when the mark is published.

Marking Criteria Table

	0-29	30-39	40-49	50-59	60-69	70-84	85-100
Task 1.1 20%	The program does not run or does not deliver a complete solution.	The program runs and can input or read in some numbers, however the duplicated elements preserve in the output.	No duplicated elements in the output, but the correct order is not reserved.	No duplicated elements and the correct order in the output. However, the algorithm is inefficient.	The output preserves the correct order with a reasonably efficient algorithm. Also, it does not use memory wisely and efficiently.	Suitable Data structure is applied with an efficient algorithm and least memory usage.	The design is beyond the requirement.  The program is elegant and professional.
Task 1.2 20%	The program does not run or does not deliver a complete solution.	The program runs and does deliver a complete solution. However, the output is not always correct for the testing operations.	The program can return the correct results but not efficient.	The program can return the correct results with the reasonable efficiency and data structure	The program can return the correct results with the high efficiency and suitable data structure.	The program can return the correct with the extremely high efficiency and most suitable data structure.	The design is beyond the requirement.  The program is elegant and professional.
Task 1.3 20%	The program does not run or does not deliver a complete solution.	The program does run and try hard to provide parallel processing. However, it delivers a serial process with incorrect output.	The program does run and try hard to provide parallel processing. However, it delivers a serial process with correct output.	The program provides a parallel processing. However, the number of the processes is fixed for any size of the input.	The program provides a parallel processing. However, the number of the processes can be set up before dealing with the input.	The program can analyse the input to dynamically decide the number of the processes.	The design is beyond the requirement. E.g., dynamically allocate workload
Task 1.4 20%	The program does not run or does not deliver a complete solution.	The program runs and does deliver a complete solution. However, the output is incorrect at all.	Data are imported and stored well. The correct algorithm is used, but the output is not always correct.	Data are imported and stored well. The correct algorithm is used, but the cost is correct, but the route is not provided.	The program is elegant and professional such as good comments, meaning variable names and useful functions. The output satisfies the requirement.	Extra features are provided to help the user experience.	The design is beyond the requirement.
Task 2.1 10%	The justification of the design choices is none or minimal.	The justification of the design choices is minimal and up to 40% of the tasks. Clarification and discussion are shallow.	The justification and clarification of the design choices are reasonable and cover up to 60% of the tasks.	The justification and clarification of the design choices are reasonable and cover up to 80% of the tasks.	The justification and clarification of the design choices are reasonable and cover all the tasks.	The justification and clarification of the design choices are excellent and profound and cover all the tasks.	An excellent discussion, fully evidenced and very well supported by relevant references.
Task 2.2 5%	The report is none or minimal for computational sustainability	The report discusses few points for computational sustainability, but they are irrelevant.	The report discusses some points for computational sustainability, but with minimal clarity	The report discusses some points for computational sustainability with reasonable clarity	The report gives comprehensive discussion, however, it isn’t related to the recommended or certain task>	The report gives comprehensive discussion with the combination of the tasks.	An excellent discussion, fully evidenced and very well supported by relevant references.
Task 2.3 5%	Video demo is none or minimal	Video demonstrates up to 40% of the tasks	Video demonstrates up to 60% of the tasks	Video demonstrates up to 80% of the tasks	Video demonstrates up to all the tasks	Clarification is clear and concise, and data structure and algorithms are explained, and main features are emphasised.	Professional video presentation