Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: THEend8_
MARKING:You will be interviewed during your lab or at another time as arranged
by your demonstrator who will ask you a series of questions to assess your under-
standing of this exercise, and gauge how you implemented it. It is required that you
implement this exercise strictly using Python programming language. Practical
work is marked on the complexity of your program and also on your understand-
ing of the program. A perfect program with zero understanding implies you will get
zero marks! \Forgetting" is not an acceptable explanation for lack of understanding.
Demonstrators are not obliged to mark programs that do not run or that crash.
You will lose all marks for a given task if your algorithm does not produce correct
results for the task. Also, heavy penalties are applied if your complexity is worse
than the required complexity and you may lose all marks if the complexity is similar
to that of the naive algorithm. This is because our focus is on developing ecient
algorithms and data structures. Also, do not assume that each task carries equal
marks.
SUBMISSION REQUIREMENT: You will need to submit a zipped le contain-
ing your Python program (named cameradetector.py) as well as a PDF le brie
y
describing your solution and its space and time complexity. The PDF le must give
an outline of your solution (e.g., a high level idea of how did you solve it) and the
worst-case space and time complexity of your solution. Penalties will be applied if
you fail to submit the PDF le. The zipped le is to be submitted on Moodle before
the deadline.
Important: The assignments will be checked for plagiarism using an advanced pla-
giarism detector and the students will be interviewed by tutors to demonstrate the
understanding of their code. Last year, many students were detected by the plagia-
rism detector and almost all got zero mark for the assignment and, as a result, many
failed the unit. \Helping" others is NOT okay. Please do not share your solutions
with others. If someone asks you for help, ask them to visit us during consultation
hours for help.
1 Assessed Task: Red-light Camera Detector
Alice bursts into your room and is visibly upset. She waves a paper and screams, \I cannot
believe this. They sent me a ticket for violating the trac lights. I am sure the light was amber
when I crossed the intersection. This is unfair."
She then takes a long deep breath and rmly says, \Okay, I have decided that I will never
drive through an intersection with red-light cameras again. Never! Can you please help me to
write an app to detect the red-light cameras?".
By now, you know that you cannot say NO to Alice. So you respond: \Of course, Alice!
But give me some more information."
\Aaaww! You have always been such a good friend!" Alice happily says. \I also have a
small gift for you which I will give you later1. But let me give you details of what I need for
my camera detector app."
\Basically, I will provide you two text les named vertices.txt and edges.txt. The le
vertices.txt contains the IDs of the vertices/intersections that have red-light cameras. The
le edges.txt contains the information of edges corresponding to the road segments connecting
the intersections. Some of the edges (road segments) are toll roads. I want the application to
take as input a source vertex v and a value k; it must return me the k closest cameras from
the vertex v and the shortest paths to each of these cameras. I do not want to travel on a toll
road or drive through an intersection that has a red-light camera. Therefore, none of the paths
must contain a toll road or pass through a red-light camera. "
\hmmmm, okay I think I get it. But could you give me a more formal denition", you ask.
Alice: \Sure! A path from a vertex s to a vertex t is NOT safe if the source vertex s
contains a camera. Otherwise, the path is called a safe path if 1) none of the edges on the
path is a toll road; and 2) none of the vertices on the path (except the target vertex t) contains
a camera (the target vertex t may or may not have a camera). Safe distance from vertex s to
vertex t is the total length of the shortest safe path from s to t. Given an input vertex v, the
goal is to nd k-closest cameras considering only the safe paths.".
1.1 Input
The input les vertices.txt and edges.txt can be downloaded from Moodle2. The total
number of vertices are 6105 and you can assume that their IDs are in the range 0 to 6104.
Below are the rst 5 lines from vertices.txt denoting that the vertices 1; 5; 12; 16 and 20
have red-light cameras.
Below are some lines from edges.txt. The rst two values in each row correspond to the
vertices that the edge connects and the third value corresponds to the distance between the
vertices (i.e., the length of the edge). Some rows in edges.txt have four values where the
fourth value is TOLL denoting that this edge is a toll road. For example, the third line below
1Alice's reward is on page 5!
2This is a real data set corresponding to the road network in a German city Oldenburg.
2
shows that there is an edge between vertices with IDs 124 and 138. The length of this road
segment is 544:010193 and this is a toll road.
122 127 526.950012
123 125 228.396591
124 138 544.010193 TOLL
125 126 259.437286
1.2 Output
The program must ask the user to enter their location (vertex ID) and the value of k. It must
then display k-closest cameras considering only the safe paths. It must also display the safe
path to each of these cameras. Below is a sample output.
Enter your location: 1609
Enter k: 3
Camera 1 : 1595 Distance from your location: 89.02904600000001
Shortest path: 1609 --> 1600 --> 1593 --> 1595
Camera 2 : 1624 Distance from your location: 143.87629700000002
Shortest path: 1609 --> 1600 --> 1607 --> 1624
Camera 3 : 1648 Distance from your location: 170.821331
Shortest path: 1609 --> 1622 --> 1616 --> 1625 --> 1627 --> 1636 --> 1648
Note that there is a camera at vertex 1580 with distance 166:19017100000002 but it is not
returned in the above output because the shortest path to this camera passes through another
camera (at intersection 1595), i.e., the path is not a safe path. Below are the details of the
camera (and the shortest path to it) that must be ignored by your algorithm.
Camera : 1580 Distance from your location: 166.19017100000002
Shortest path: 1609 --> 1600 --> 1593 --> 1595 --> 1578 --> 1580
Below is another sample output.
Enter your location: 2011
Enter k: 2
Camera 1 : 1999 Distance from your location: 21.692297
Shortest path: 2011 --> 1999
Camera 2 : 1991 Distance from your location: 302.152092
Shortest path: 2011 --> 2016 --> 4563 --> 2003 --> 1985 --> 1976 --> 1991
There is a path to camera at intersection 4529 with distance 238:061092 but it is ignored
because the path contains a toll road. Below is a path to this camera which is invalid (i.e., not
safe) because it contains a toll road.