CSE 101 Winter 2024 Homework 3 updated 1/27
Due: Thursday 2/1 at 11:59pm
1. Suppose Dijkstra’s algorithm is run on the following graph, starting at node A.
(a) Draw a table showing the intermediate distance values of all the nodes at each iteration of the algorithm. (5 points)
(b) Draw the shortest path tree. (5 points)
2. You are designing a flight scheduler for an airline AlgorithmAir. You will have access to a list of daily flights, [F1...Fn], each with a departure airport, departure time, arrival airport, arrival time, and cost, Fi = (DAi
, DTi
, AAi
, ATi
, ci). (Times are measured in minutes after midnight UTC time.)
A passenger can make a flight connection from (DAi
, DTi
, AAi
, ATi
, ci) to (DAj , DTj , AAj , ATj , cj ) if and only if AAi == DAj . This connection will have a total layover time of DTj − ATi
if ATi < DTj or 24 − (ATi − DTj ) if DTj ≤ ATi
, i.e., the passenger will have to wait until the next day to take flight j.
(a) Given a list of n available daily flights {F1, . . . , Fn}, a departure airport D and an arrival airport A, design an algorithm that returns the minimum cumulative layover time among all valid sequences of flights starting from airport D and ending at airport A. (You can ignore cost for this question.) (7 points for reasonably efficient correct high level algorithm description (with correctness proof), 5 points for correct time analysis, and 3 points for efficiency of your algorithm.)
(b) You notice that the route from D to A is very popular and you want to make that particular route cheaper than it is. There are n available daily flights [F1...Fn] that are already running. There are k potential future flights [P1, . . . , Pk] that the airline is considering to add. You wish to find exactly one of the potential future flights to make available that will result in the cheapest sequence of flights from D to A.
Given a list of n available daily flights [F1, . . . , Fn] and list of k potential future daily flights [P1, . . . , Pn] and a departure airport D and arrival airport A, design an algorithm that returns the index of the potential future daily flight Pi such that if Pi
is included in the list of available flights, it will result in the minimum cost among all valid sequences of flights from D to A. (7 points for reasonably efficient correct high level algorithm description (with correctness proof), 5 points for correct time analysis, and 3 points for efficiency of your algorithm.)
3. Consider the following algorithm that takes as input a directed graph G with edge weights from the set {0, 1} and a starting vertex s and populates an array dist such that dist(v) is equal to the length of the shortest path from s to v for all vertices v given that the 0 edges have length 0 and the 1 edges have length 1.
(The way the algorithm works similarly to BFS but it uses a double-ended queue queue rather than a traditional queue.)
A double-ended queue is a list of entries such that you can dequeue only from the left side of the list but you can choose to enqueueL to enqueue an entry to the left side or enqueueR to enqueue an entry to the right side of the list.
(0,1)-BFS(G, w, s) (G = (V, E) is a directed graph, w is the edge weights that are either 0 or 1 and s ∈ V .)
1. for all u ∈ V :
2. dist(u) = ∞
3. dist(s) = 0
4. D = [(s, 0)] (double-ended queue containing the ordered pair (s, 0))
5. while D is not empty:
6. (u, d) = dequeue(D)
7. for all edges (u, v) ∈ E:
8. length = w(u, v)
9. if dist(v) > dist(u) + length:
10. dist(v) = dist(u) + length
11. if length == 0:
12. enqueueL(D,(v, dist(v))
13. if length == 1:
14. enqueueR(D,(v, dist(v))
(Notes about changes: The DE-queue D holds ordered pairs (v, d) where v is the name of the vertex and d is the value of dist(v) when v enters D. Also vertices may enter the DE-queue more than once if their dist value gets updated again.)
(a) (6 points) Tracethrough this algorithm on the following input (solid edges have a weight of 1 and dashed edges have a weight of 0):
(You can fill in the following table:)
(b) (6 points) In order to analyze this algorithm, we can prove the following claim:
After every iteration, D contains a list of ordered pairs [(v1, d1), . . . ,(vk, dk)] such that there are at most 2 different di values and the di values are sorted.
Prove this claim using induction.
(c) (6 points) Show that this claim (part b) does not work if the 0 edges have length 1 and the 1 edges have length 2.
(d) (2 points) Give a brief argument as to why the claim above implies that D is a priority queue.
(e) (2 points) Give a brief argument why the runtime of this algorithm is O(|V | + |E|).
4. (12 points) Suppose we want to run Dijkstra’s algorithm on a graph whose edge weights are integers in the range: 0, 1, ..., W, where W is a relatively small number. Show how Dijkstra’s algorithm can be made to run in time O(W|V | + |E|) by coming up with an appropriate implementation of a priority queue.
(Note: in your answer, you must give a high-level description of the implementation of the priority queue and a runtime justification of why Dijkstra’s algorithm will run in O(W|V | + |E|) with this implementation.)