Hello, dear friend, you can consult us at any time if you have any questions, add WeChat: daixieit

CS 180 Summer A9 2022 Homework Week 8

1. Dijkstra’s Algorithm.  Let G = (V,E) be a weighted, directed graph whose weights w are in the

set {0, 1, . . . ,W} for some nonnegative integer W .  Provide a modification of Dijkstra’s algorithm in the form of pseudo-code (with associated explanation, of course) which computes the weights of the shortest paths from a given source vertex s to all vertices in the graph in O(W|V | + |E|) time.          Briefly justify your modified algorithm’s correctness and asymptotic complexity.  (Note:  W may be greater than, less than, or equal to |V | and/or |E|.) You do not need to compute the paths themselves.

2. Teleporters. You wish to travel from the west-most point s to the east-most point t of a 1-dimensional segment. There are n teleporters on this 1-D segment and each teleporter has two endpoints. Whenever you reach one endpoint, it will teleport you to the other endpoint (it may transport you from east to west or west to east, depending on which endpoint you reach). All the endpoints are located strictly between s and t, and none of the endpoints are located at the same position.  When walking on a segment, you must always walk eastward.

Figure 1: An example for Problem 2. We are given an input with 4 teleporters with endpoints a1 ,a2 ; b1 ,b2 ; c1 ,c2 ; d1 ,d2 .  Starting from s, the path will be s (walk to) a1  (teleport to) a2  (walk to) c1  (teleport to) c2 (walk to) b2  (teleport to) b1  (walk to) a2  (teleport to) a1  (walk to) b1  (teleport to) b2  (walk to) t.

Prove that no matter how these teleporters are placed, you will always reach t. (Hint: Represent the problem as a directed graph.)  Assume that the input is an array of pairs [(a1 ,a2 ), (b1 ,b2 ), . . . ] and that all endpoints are given as the distance from s.