CSE 102 Introduction to Analysis of Algorithms
Winter 2022 Profs. Kolla/ W 8
Due March 11 at 11:59 pm
(3 questions, 160 points total)
Copyright By PowCoder代写 加微信 powcoder
1. (60 pts.) Shortest Paths with Mostly-Positive Weights
You are given a directed graph G = (V,E) where each edge e has a length/cost ce and you want to find shortest-path distances from a given node s to all the nodes in V . Suppose there is at most one edge f = (u, v) that has negative weight and the rest have non-negative weights. The Bellman-Ford algorithm for shortest paths with arbitrary weights takes ¦¨(nm) time where n = |V| and m = |E|. Let¡¯s show that you can take advantage of the fact that there is at most one negative-weight edge to find all shortest-path distances from s in only O(m + n log n) time: the same asymptotic running time as Dijkstra¡¯s algorithm.
(a) Describe an O(m+nlogn)-time algorithm which outputs either that the graph has a negative cycle reachable from s, or the shortest-path distances from s to all the nodes v ¡Ê V .
(b) Give a short argument why your algorithm is correct.
(Note: As a more challenging exercise [definitely optional, and not something we¡¯re expecting you to know], you could think about how to solve this problem when there are k negative edges. You want an algorithm that is faster than Bellman-Ford if k is sufficiently small.)
2. (60 pts.) Pursuit
You are a velociraptor minding your own business, when some Neanderthals waltz up, insult your plumage, and run off. You are so shocked at seeing a hominid in the Cretaceous Period that the Neanderthals get a 20 meter head start. You could easily catch them on open ground, since you can run twice as fast and so catch up 5 meters for every 10 meters you travel. Unfortunately, between you and the time warp the Neanderthals are trying to get back to, there are a bunch of rivers: see Figure 1. There are N places (marked by black lines) shallow enough to cross, but since the Neanderthals have much longer legs, you¡¯ll get 5 meters further behind for every 10 meters of river you cross. Assume the Neanderthals are too terrified to consider moving back towards the left side of the map.
Given the starting and ending locations, and the positions of (both ends of) the N crossings, describe an algorithm to find whether it is possible for the Neanderthals to escape, i.e., to reach the end location before you catch up. Briefly argue why your algorithm is correct, and analyze its asymptotic runtime in terms of N. For full credit, your algorithm¡¯s runtime should be O(N2).
3. (40 pts.) Robust Communications
Suppose you are designing a sensor network with sensors s1,…,sn, which are positioned at different points in the 2D plane and continuously transmit data. You also have antennas a1,…,am at various locations, which can receive signals from sensors within 1 km. However, antenna i only has enough bandwidth to connect to mi sensors at a time, so if a sensor is in the range of multiple antennas, you need to be careful about which one to connect to. Furthermore, for redundancy, you want to make sure that every sensor is connected to at least 2 different towers. So the problem is: given the positions of the sensors and antennas,
CSE 102, Winter 2022, HW 8 1
Figure 1: Santa Cruz, 75 million years ago.
is it possible to assign each sensor to 2 (or more) antennas within 1 km so that every antenna i is connected to at most mi sensors?
Show how to solve this problem by encoding it as an instance of the maximum-flow problem. You should describe both how you build your flow network and how you extract from a maximum flow the assignment of sensors to antennas (or decide one doesn¡¯t exist).
(Note: If you wish, you may use the fact that a flow network with integer capacities always has a maximum flow which assigns integer flow to each edge; the Ford-Fulkerson algorithm finds such a flow.)
CSE 102, Winter 2022, HW 8 2
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com