CITS2200 Lab 6: Tranes and Planes, Security Routing
Name: Ajay Bisnath
Student Number: 24794543
Question 1 (3 marks)
Implement your solution by filling out the method stub in trains_planes.py.
Your implementation must pass the tests given in test_trains_planes.py, which can be invoked by running python -m unittest test_trains_planes.
See trains_planes.py.
Question 2 (1 mark)
Give an argument for the correctness of your trains_planes() function.
We are given that a flight can only be replaced if there is a combination of rail services that connect the start and end locations operating at the time of the flight. My program approaches this by treating cities connected by railways as connected components of a graph, merging clusters whenever a rail line begins to operate.
All flights and railway line openings by date, with rail openings sorted before flights on the same date (ensuring that if a line opens on the same day as a flight it could replace, that it is correctly counted as available). Processing events in this order, the program builds up connected components using Union-Find. Each rail line triggers union() to merge two cities and each flight triggers find() on its departure and arrival cities. If they share the same root, the cities are connected and the flight can be replaced.
Since Union-Find’s find() returns the same root for any two cities in the same component regardless of how they are connected, the program can automatically detects if a chain of rail lines exists between two cities, even if no direct line exists.
Question 3 (1 mark)
Give an argument for the complexity of your trains_planes() function.
The overall complexity of trains_planes() is O(N log N), where N = len(trains) + len(planes). Collecting city names requires one pass throug both input lists resulting in complexity O(N). Building the two event lists is also O(N). Sorting the combined event list of N events is O(N log N) using Python’s build-in Timsort.
The sweep loop makes exactly one pass through the N events leading to O(N) complexity. Each iteration calls either union() or find() on the Union-Find structure. With path compression, each find() runs in O(α(N)) amortised time, where α is the inverse Ackermann function which is effectively constant for most input sizes giving us a cost of O(N). The sort at O(N log N) has the largest complexity which results in the total complexity of the program being O(N log N).
Question 1 (3 marks)
Implement your solution by filling out the method stub in security_routing.py.
Your implementation must pass the tests given in test_security_routing.py, which can be invoked by running python -m unittest test_security_routing.
See security_routing.py.
Question 2 (1 mark)
Give an argument for the correctness of your security_route() function.
My program models the problem as Dijkstra’s shortest-path search over a state space of (station, clearance) pairs rather than stations alone. This is necessary because two paths reaching the same station with different clearances unlock different future moves making them distinct states. At each state, the program considers two moves: travelling any outgoing segment whose required clearance matches exactly the current clearance (or requires none), or adopting the current station’s clearance for free.
Because Dijkstra always expands the cheapest unvisited state first and all weights are non-negative, it finds the true minimum time to each state. The answer is the minimum across all clearance levels at the target station, returning None if unreachable.
Question 3 (1 mark)
Give an argument for the complexity of your security_route() function.
The expanded state graph has at most 4N nodes (4 clearance levels multiplied by N stations) and at most 4M + N edges (each of M segments appears in up to 4 clearance states, plus N free upgrade edges). Dijkstra with a binary min-heap over this graph runs in O((N + M) log N). Since N = len(stations) + len(segments) and M ≤ N, this simplifies to O(N log N), matching the target complexity.