5002 CMD Advanced Algorithms Coursework Assignment Brief: Portfolio 2025/26

5002 CMD Assignment Task

Use of Generative AI

Red – no use of Generative AI permitted.

You can look at the teaching materials and any other references, but you should not use auto-text generation tools, AI-tools or any other tool that auto-generates any text or any programming code or attempts to solve the questions for you even partially.

Instructions:

• This coursework is individual work.
• There are 5 standard and 3 advanced assessed assignment tasks released during the module in weeks 1 to 10 inclusive. They are written in the lab materials and marked clearly with “Assessed Question x” where “x” is a number from 1 to 8, with their level (standard or advanced) stated in front of them. You must select 3 standard and 2 advanced to submit.
• Each of the questions carries independent marks.
• Codes should be written in Python programming language.
• You should create 1 single text file (Microsoft Word document, or if you are using any other text file extension, then convert it to a PDF file, no other format will be accepted) and 5 Python files, put them in a zip folder with the name “student_xxx_coursework_5002CMD” where xxx is replaced by your student ID number.
• At the beginning of the text file write which 5 questions you have selected to submit. Example: “I have selected questions 1, 2, 3, 5 and 8.”
• For each of the questions provide one single Python file, do not put codes related to two or more questions in a single dot-py file, and do not use more than one py file for a single question. If a question needs more than one python function, put all in the same file. If a question has several parts, i.e. a, b, c …, codes for all parts should be in a single file clearly declared which Python function is for which part of the question. Name the py file properly as “Q_x.py”, replacing x with the number of the question. So the python file for Question 1, should be named “Q_1.py”.
• Choose a meaningful name for your python functions and Python variables.
• Provide enough comments that clarifies what your code does. Especially what are the inputs and what you will get as the output, the data structure etc.
• Put things in a logical order, when the marker is going from top to the bottom of your code, they should understand each line without need of going forth and back in your file. For example using a variable in line 5 and then introducing what this variable is in line 50 is not a good practice and you may loose marks even if the code works.
• The non-coding parts of the questions will be solely marked based on what you provide in the text file.
• In the text file separate answers to each question clearly from the others with line and put them in the order, for example “Question 1: xxxx”,then Separating line, then “Questions 2: xxxx” and so on. If a question or part of it asks a code, write “code is provided in Q_x.py.

Questions:

Question 1 (Standard)

1. Read the following pseudocode and write a Python function that follows this pseudocode, do not optimize or change the algorithm. Do not use any Python module or command that is not necessary. The only extra command that you would need is “randint” from “random” module (see Python Random randint() Method). (Python)
2. What will be the output for the input “4”? (text)
3. Modify your code to use recursive call to only one step before. Note that we didn’t say to convert recursion to iteration! (Python)

a- convert recursion to iteration! (Python)

Question 2 (Standard )

a-Write a Python function, name it ‘fun’, that receives two inputs:

1.A list of ordered pairs where an ordered pair is a list of length two.
2.A positive integer, name it .
Then it returns the second entry of the ordered pair that its first entry is equal to .
We assume that the first entries of the ordered pairs are integers and these ordered pairs are already sorted in an increasing order with respect to their first entries. Your code should follows the binary search algorithm. 
As an example, if the input list is [ [ 5, “B”], [ 8, “O” ], [ 14, “Si” ], [ 16, “S” ], [ 19, “K” ], [ 29, “Cu” ], [ 47, “Ag” ], [ 72, “Hf” ], [ 92, “U” ] ] and the  is 14, then the output should be “Si”.
(Python)

b-Remember the complexity classes;

, , , , , ,  where  is a constant positive integer,  where , , and we went until  where . 
Let us show the length of the input list of the function ‘fun’ in part (a) with . Which of the mentioned complexity classes does the computational complexity of the binary search belong to? (text)

Question 3 (Standard)

Recall the stack and the node classes introduced in the class. Python codes for these two classes are provided below and must be used in your code. Write a Python function that receives a binary tree as an input (which is declared using the node class) and returns a list containing values stored in its nodes in the pre-order direction and your code should use stack data structure properly. (Python)

Question 4 (Advanced )

a-Write a Python function for Dijkstra’s algorithm to find the cost of the minimum cost path between two given nodes. (Python)
Note: The path itself is not asked. The input graph is assumed to be connected.
b-Explain the data structure you used, i.e. the representation of a graph that is used in your code, so a person who wants to use your function, can easily understand what to give to your function. Write only about the input and output of your algorithm, do not write about steps happening inside the algorithm. (text)

Questions 5 to 7 need the following short reading

Remember the Set Covering Problem (SCP) from the class, here is a similar type of problem called the Hitting Set Problem. Let  be a universal set (a collection of items or data). And let  be a set of subsets of , we call it “subsets list”. For example  and  as shown in Figure 1. We are interested in finding a subset of , let’s call it , such that it intersects with all subsets in the subsets list, that is for every  we should have  (there is at least one element in common for  and ). Such a set is called a hitting set. Additionally we want this set to have the minimum possible number of elements. So the problem is for a given  and , find a minimum hitting set. For the simple example of Figure 1, a minimum hitting set is . Note that a minimum hitting set is not necessarily unique, for example in our case  is also a minimum hitting set. But the size of a minimum hitting set is unique, in this example is equal to 4. Hitting set problem has applications in various topics such as data profiling, model-based diagnosis, biology, transportation, sensor networks etc.

Figure 1: An example of a hitting set problem with universal set containing 8 elements and the subsets list containing 6 subsets.

The following Python functions should be used in your codes wherever needed.

Question 5 (Advanced )

a-Write a Python function that receives a list as the universal set and a list of sublists as the subsets list. Then it uses a backtracking algorithm to find the minimum hitting list. (Python)
b-Justify why your idea is a backtracking algorithm. (text)

Question 6 (Standard )

Write a Python function that solves the hitting set problem in a GRASP style. (Python)

Question 7 (Standard )

Similar to Beasley reduction rules for SCP, there are reduction rules for the hitting set problem. We bring 3 of such reduction rules below.
Rule 1: If there is a subset of size one, then pick the contained element and put it into the partial solution. Remove that subset from  too.
Rule 2: For any two subsets  and , if , then delete  from .
Rule 3: For every , define a set . The set  consists of all subsets that contain . Now for every two elements  and , if , then delete  from . Trivially those elements  for which  will be deleted in this step too, because empty set is subset of any other set.

Write a Python function that receives  and  as its inputs (described as in Question 5) and then does the preprocessing using the three mentioned rules. It should return three things, first the updated universal set, second, the updated subsets list, and third, the set of necessary elements to be in a hitting set (partial solution). (Python)

Note: By default one has reason to number actions, so it is expected that your code does these rules in the order given.

Question 8 (Advanced )

Ahmad and Bahman are trying to make a simple 2-player game where each player has 10 hiding locations in his land. At the beginning of the game if the player is still in the living world, he hides at one of his 10 hiding spots. Then he can set his missile launcher’s target to one of the 10 locations of the enemy. He launches a missile. If it hits the correct spot where the enemy is sheltered, the enemy dies. But he doesn’t want to risk coming out of his hiding spot to check the situation, so he keeps launching missiles to hit all 10 locations of the enemy. After that he will come out of his hiding spot. Setting up a new target location and launching the missile will take 1 second. The two players start their actions at the same time. 

They finished writing the initial version of their code as you can see below. To test their code they set the hiding location of Ahmad at 5 and the hiding location of Bahman at 7. Looking at the order of locations each player is targeting, they expect to see that Bahman dies at the 4th round of missiles exchange and Ahmad remains alive. But when they run their code, they end up with print messages stating that Ahmad dies and Bahman wins!

a-Use one of the two modules threading or multiprocessing to fix the problem of the above code. (Python)
b-Justify why the module you chose is suitable for fixing this problem and why the other one isn’t. (text)

Permitted commands from Python

-Only simple lists can be used in your codes unless otherwise stated in the question. For example you can not use the default ‘set’ structure of Python.

-Default Python list methods that you can use are only the followings:

• index
• remove
• append
• copy

-From ‘math’ module you can only use ‘inf’.

-From ‘random’ module you can only use ‘randint’ for question 1, and ‘choice’ for question 6.

-From ‘time’ module you can only use ‘sleep’ which is only used in question 10.

-From ‘threading’ module you can only use ‘Thread’ class and if needed ‘start’ and ‘join’ methods. From ‘multiprocessing’ module you can only use ‘Pool’, and ‘map’ and ‘starmap’ methods if needed, or ‘Process’ class and ‘start’ and ‘join’ methods if needed. ‘threading’ or ‘multiprocessing’ can only be used in question 10.

Submission Instructions:

In the Aula page go to Journey, then Assignments, there you see the submission point. Make sure to submit your coursework to the correct relevant one. 

Marking and Feedback

How will my assignment be marked?
Your assignment will be marked by the module team. 

How will I receive my grades and feedback?
For feedback on your marks please contact Dr Beate Grawemeyer.

Assessed Module Learning Outcomes

The following module learning outcomes are assessed in this task:
2. Design and implement algorithms and data structures for novel problems.
3. Specify and implement methods to estimate solutions to interactable problems.
5. Design and implement a concurrent application.

Assignment Support and Academic Integrity

If you have any questions about this assignment please see the Student Guidance on Coursework for more information. 

Spelling, Punctuation, and Grammar:

You are expected to use effective, accurate, and appropriate language within this assessment task. 

Academic Integrity:

The work you submit must be your own. All sources of information need to be acknowledged and attributed; therefore, you must provide references for all sources of information and acknowledge any tools used in the production of your work. We use detection software and make routine checks for evidence of academic misconduct.
It is your responsibility to keep a record of how your thinking has developed as you progress through to submission. Appropriate evidence could include: version controlled documents, developmental sketchbooks, or journals. This evidence can be called upon if we suspect academic misconduct. 

Definitions of academic misconduct, including plagiarism, self-plagiarism, and collusion can be found on the Student Portal. All cases of suspected academic misconduct are referred for investigation, the outcomes of which can have profound consequences to your studies. For more information on academic integrity please visit the Academic and Research Integrity section of the Student Portal.

Support for Students with Disabilities or Additional Needs:

If you have a disability, long-term health condition, specific learning difference, mental health diagnosis or symptoms and have discussed your support needs with health and wellbeing you may be able to access support that will help with your studies.
If you feel you may benefit from additional support, but have not disclosed a disability to the University, or have disclosed but are yet to discuss your support needs it is important to let us know so we can provide the right support for your circumstances. Visit the Student Portal to find out more.

Unable to Submit on Time?

The University wants you to do your best. However, we know that sometimes events happen which mean that you cannot submit your assessment by the deadline or sit a scheduled exam. If you think this might be the case, guidance on understanding what counts as an extenuating circumstance, and how to apply is available on the Student Portal.

Administration of Assessment

Assignment Category: Portfolio
Attempt Type: Standard