Assessed Coursework

MA214

Algorithms and Data Structures

due: Tuesday, 23 April 2024 at 16:00 (London time)

Instructions

This set of tasks is Assessed Coursework, constituting 20% of the final mark for this course. It is due on Tuesday, 23 April 2024 at 16:00 (London time).

The work should be yours only. You may not work in groups or even discuss these problems with anyone else. You have to upload your work on Moodle at the Gradescope link that will be provided. By submitting your solutions, you are confirming that you have read and understood the School’s rules on Plagiarism and Assessment Offences, which can be found here and here. In these rules it is also explained which procedure we will follow should we suspect collusion or any other form. of assessment offence or plagiarism for your submission.

Your submission for this coursework should consist one file only: A Python file Submarines.py (which should also contain, in comments, explanations about the algorithms and data structures you chose for your imple-mentation and the resulting running times, as explained in detail in the tasks below). A template for this python file is provided on the course moodle page.

The contents of your work must remain anonymous, so do not include your name or your student number in the files. Do not submit anything directly to your lecturer or class teacher. Instead, please put your candidate number in the submitted file in a comment at the very top.

The deadline is sharp. Late work carries an automatic penalty of 5 deducted marks (out of 100) for every 24-hour period that the coursework is late.

Submission of answers to this coursework is mandatory. Without any submission, your mark for this course is incomplete, and you may not be eligible for the award of a degree.

Use of internet search, generative AI, and Python packages

In addition to all the course material provided on the course webpage and the course textbooks, you are of course allowed (and in fact encouraged) to use online documentation on the Python programming language to assist you when writing your programs, and there is no need to report this.

No other resources are necessary for completing this coursework. However, should you decide to use other resources (such as Stack Exchange or ChatGPT) to get ideas for your algorithms, their implementation, or their analysis, these need to be acknowledged and documented in order to adhere with the rules concerning plagiarism mentioned above. Please document the use of such tools at the very end of your submission file in a comment. For generative AI tools, you need to provide a transcript. of the chat, or a link to the chat. You will not gain points for answers taken from such sources, but only for your own work.

In your Python programs for this assessed coursework, you are not allowed to use any Python library functions apart from the following imports which are already contained in the template-file that is provided on moodle.

from collections import deque

from math import inf

The aim of this assessment is not to measure your proficiency in using Python packages to solve problems. The questions test your algorithm design and analysis skills, as well as your ability to implement algorithms in Python.

Coursework MA214 – Submarine journey planner

You were hired as an expert in algorithms and data structures by a company specialising in public underwater submarine lines operating between different underwater colonies. Your first project concerns the design of software for storing and obtaining information about the submarine lines that are operating and to facilitate journey planning. For this purpose you should write a Python program in a file Submarines.py with the functionality and output as specified below (see Tasks 1–4). In order to demonstrate your value as expert to the company, you are also required to justify the design of your algorithms and analyse their running time (see Task 5).

The setup is as follows. There are a number of submarine lines, each stopping at a given sequence of un-derwater terminals at specified times. For simplicity, we shall assume that the departure time of a given submarine at a terminal is the same as its arrival time at this terminal (and we simply call it the stopping time). At terminals, passengers may change between different lines A and B, as long as A arrives before or at the same time as B. In particular, we assume, again for simplicity, that changing between lines does not require any time. Also, a time is simply given as a number of minutes since the start of the day and each submarine line reaches its final destination on the same day as it started. A line does not stop at any station twice.

For completing the following tasks, you will have to consider carefully which data structures to use for storing the given information and to support your algorithms. The different tasks below will influence your design decisions. It is therefore important that you read the entire coursework description in detail before you start coding.

Use the template for Submarines.py that is provided on the course moodle page and complete the functions as specified in the tasks below. Of course, you are also encouraged to add other functions and classes to this file that you need for your implementation or for the data structures you would like to use. You can (without acknowledgement) copy code from the Python files provided on the course moodle page if this helps you. It is important that you do not change the number of arguments or the names of the functions you are asked to implement in the tasks below, so that your program will work with the autograder that is used upon submission. You are welcome (but you do not need) to change the content of the “main” block (that comes after if __name__== '__main__':), which is not used by the autograder.

The intention of the class SubmarineNetwork in Submarines.py is that it allows us to store all the information about the submarine lines and to perform. journey planning tasks. In its methods, that you are asked to implement as described below, you may assume without checking that all input arguments are provided in the correct format. For example, when a time is expected as input argument, you may assume that a non-negative integer is provided; or when a Python list of pairs is expected as input argument that such a list is provided.

Your first task is to set up a constructor for the class Submarines.py and a method for adding new subma-rine lines. (It is likely that you will need to update your implementation of the constructor once you are implementing the other functions as described below.)

Task 1.                                   4 points

Implement the constructor __init__(self) and the member function add_line(self,stops) of the class SubmarineNetwork. The constructor should set up all the member variables you need in SubmarineNetwork. The function add_line should allow us to add a submarine line to the network and gets a Python list stops as argument whose entries are pairs (name,time) specifying the schedule for this line as follows. Each pair consists of a name of a terminal and a stopping time (in minutes) at this terminal; the pairs are ordered by time (that is, first the first stop is given, then the second, and so on).

Each added submarine line should also be assigned a line id: The line that is added first gets id 0, the line that is added next gets id 1, and so on.

For example, using

network = SubmarineNetwork ()

network . add_line ([ ('South Sea ' ,12) , ('Indian Ocean ' ,52) ,

                               ('Coral Reef ' ,74) , ('Polar Lagoon ' ,123) ])

should create a submarine network with one line which has id 0 and is stopping at ‘South Sea’ at minute 12, at ‘Indian Ocean’ at minute 52, and so on.

Next, we would like to add some functionality to obtain timetable information for a given terminal.

Task 2.                                          2 points

Implement the member function

lines_stopping_at(self,terminal_name,start_time,end_time)

of the class SubmarineNetwork. This function should return a Python list of pairs (id,time) giving the ids and stopping times of lines stopping at the terminal with the provided name between start_time and end_time (both inclusive). The tuples in the python list should be ordered by time.

For example, if in the network line 0 stops at the terminal ‘South Sea’ at time 10, line 1 stops there at time 23, line 2 stops there at time 14, and line 3 stops there at time 20, then running

network.lines_stopping_at('South Sea',14,23)

should return

[(2,14),(3,20),(1,23)].

We further want to obtain information about a fastest direct connection between two submarine terminals.

Task 3.                                           4 points

Implement the member function

best_direct_connection(self,origin,destination,time)

of the class SubmarineNetwork. This function is given the name of the origin terminal where we would like to start our journey, the name of the destination terminal we would like to travel to, and a time at or after which our journey should start. This function should determine the line that we should take from the origin to the destination in order to arrive at the destination as early as possible. The function should return a triple (id,t_o,t_d) containing the id of the line we should take, the time t_o when this line stops at the origin and the time t_d when this line stops at the destination.

For example, if in the network the fastest direct connection at or after time 20 from origin ‘Mariana Trench’ to destination ‘Mid-Atlantic Fault’ uses submarine line 2, which leaves the origin at 23 minutes, and arrives at the destination at 42 minutes, then running

network.best_direct_connection('Mariana Trench','Mid-Atlantic Fault',20)

should return (2,23,42).

We also would like to be able to determine the fastest connection between two submarine terminals when changes between different submarine lines are allowed. For this purpose we can use a variant of Dijkstra’s algorithm.

Task 4.                                                     4 points

Modify Dijkstra’s algorithm suitably to implement the member function

next_fastest_connection(self,origin,destination,time)

of the class SubmarineNetwork. This function is given the name of the origin terminal where we would like to start our journey, the name of the destination terminal we would like to travel to, and a time at or after which our journey should start.

The function should return a list of triples (name,time,id), giving name of the terminals through which we pass on our journey, the time at which we leave this terminal, and the id of the line on which we leave the terminal unless it is the destination; for the destination time should be the arrival time at the destination and id should be None.

For example, assume in our network the next fastest connection from ‘South Sea’ to ‘Coral Reef’ leaving at or after time 42 uses line 2 at 58 minutes to go to ‘Polar Lagoon’, where it stops at 78 minutes, continues onwards on line 2 to ‘Brazil Basin’, where it stops at 120 minutes, then uses line 5 which leaves ‘Brazil Basin’ at 132 minutes to go to ‘Indian Ocean’, where it arrives at 159 minutes, then uses line 0 which leaves ‘Indian Ocean’ at 159 minutes and goes directly to ‘Coral Reef’, arriving there at 164 minutes. Then running

network.next_fastest_connection('South Sea','Coral Reef',42)

should return the following Python list.

[( 'South Sea ' ,58 ,2) ,('Polar Lagoon ' ,78 ,2) ,('Brazil Basin ' ,132 ,5) ,

('Indian Ocean ' ,159 ,0) ,('Coral Reef ' ,164 , None ) ]

The template-file for Submarines.py also provides a more complex example for how all the methods of SubmarineNetwork can be used together.

Remember to explain all your code well with comments. In addition, add the following comments concerning the design and analysis of your implementation. Recall that you can start and end multi-line comments in Python by using '''.

Task 5.                                                      6 points

At the start of your file Submarines.py explain the design of your program: Which data structures are you using for storing the necessary information and why? Which algorithms are you using for implementing the different functions? Which auxiliary classes and functions are you incorporating and why?

Also, at the start of each of the functions

add_line, lines_stopping_at , best_direct_connection, next_fastest_connection

explain what is the running time of your implementation. Justify your answers.

Your solutions will be marked for correctness, design, readability, efficiency, and your provided explanations. When making design decisions think carefully about which methods are likely to be used more frequently and should therefore have small running times.