CSE 551 Programming Assignment
October 21, 2020
Submission Instructions: Deadline is 11:59pm on 11/03. Late submissions will be penalized, therefore
please ensure that you submit (file upload is completed) before the deadline. Additionally, you can download
the submitted file to verify if the file was uploaded correctly. Submit your answers electronically, in a single
zip file, via Canvas. The zip file should contain your source code along with a report (PDF) of your findings.
Your source code can be any of the following: C, C++, Java, Python and/or Matlab.
Problem: In this programming assignment, you are tasked with the computation of the capacity of a
simplified model of the National Airspace System (NAS), between Source: Los Angeles (LAX) and Destination:
New York City (JFK), in a 24 hour time period, starting at 12:00AM and ending at 11:59 PM. The dataset is
based on the data available on January 6, 2020. Apart from these two airports, our simplified NAS consists of
the following airports (codes) as well - San Francisco (SFO), Phoenix (PHX), Seattle (SEA), Denver (DEN), At-
lanta (ATL), Chicago (ORD), Boston (BOS) and Washington DC (IAD). Furthermore, you can assume that our
simplified NAS consists of three airlines: American Airlines (AA), Delta Airlines (DL) and United Airlines (UA).
To compute the capacity of the NAS on that day, you should consider the following - (i) all direct (non-stop)
flights between LAX and NYC, and (ii) multi-stop flights between the two cities, provided the stops are airports
in the list above. If the stops are not airports mentioned in the list above, you can discard that itinerary. For
instance, you can discard LAX to MIA to NYC, since Miami airport (MIA) is not in our model. You can
include instances like (i) a non stop flight from LAX to NYC, and (ii) a multi-stop flight which could take you
from LAX to SFO to ATL to NYC. While considering the above two scenarios, please keep in the mind the
following: only consider flights which depart LAX on 01/06/2020 and arrive at NYC on the same day. For
multi-stop flights, the flight departing LAX may not be the same flight which arrives at NYC.
For instance, a passenger might fly from LAX to PHX on AA, PHX to ATL on DL and ATL to NYC on UA.
For the computation of capacity of such a system, you must satisfy the following:
• A passenger can only travel from LAX to NYC on January 6th, 2020.
• For multi-stop itineraries, a passenger can take any of the 3 airlines to travel between two cities (one
itinerary may have all the three airlines).
• For multi-stop itineraries, the arrival time of a flight at an intermediate stop must be less than the
departing time of the next flight from that very same intermediate stop.
If these three constraints are satisfied for at least 1 passenger, then the capacity of the system is at least 1.
Datasets: We will be uploading a sample timetable which includes flight information for all three airlines.
The first column is the source airport, the second column is the destination airport, the third column
indicates the departure time, the fourth column indicates the arrival time and the fifth column indicates
the capacity of the flight. The filename is “flights.txt”.
Hint: To accomplish this task, you might be thinking in similar lines with the process of “constructing a
directed graph with all the cities represented as nodes and directed edges from a node A to B if there is a flight
travelling from city A to city B”. However, such a graph only captures the spatial information (flights between
cities) and not the temporal information (time of the flights). Thus, such an approach is incomplete and is not
going to capture the entire picture. The graph you create should capture the temporal aspect of the task as well,
in order to accurately capture the capacity of the NAS. For further simplification, you can round the flight times
(departure and arrival) to the nearest hour.
1

欢迎咨询51作业君