CSE 102 Introduction to Analysis of Algorithms
Winter 2022 Profs. Kolla/ W 7
Due March 4 at 11:59 pm
(3 questions, 180 points total)
Copyright By PowCoder代写 加微信 powcoder
1. (50 pts.) Shortest-Leg Spanning Trees
Imagine we want to build a water distribution network as in the MST problems we¡¯ve seen before, but we¡¯re limited not by the total length of pipe we can build but rather the length of the longest single pipe. Formally, given a connected weighted undirected graph G = (V,E), let¡¯s say that a shortest-leg spanning tree (SLST) of G is a spanning tree whose largest edge weight is as small as possible (so it minimizes the longest pipe needed). It turns out that we don¡¯t need a new algorithm to find such a tree: every MST is also an SLST! Prove this (you may assume G has distinct edge weights to simplify the argument).
(Hint: Take any MST T and SLST T¡ä, and use the cut property to show that T¡ä must contain an edge of weight at least as large as the largest-weight edge of T .)
2. (70 pts.) Rock Climbing
Suppose you are in a rock climbing competition, where the goal is to find a route on the climbing wall that uses as many different holds as possible, using only transitions that have been explicitly allowed by the route-setter.
Say the climbing wall has n holds. You are given a list of m pairs (x, y) of holds, each indicating that moving directly from hold x to hold y is allowed; however, moving directly from y to x is not allowed unless the list also includes the pair (y,x). You need to figure out a sequence of allowed transitions that uses as many holds as possible, since each new hold increases your score by one point. The rules allow you to choose the first and last hold in your climbing route. The rules also allow you to use each hold as many times as you like; however, only the first use of each hold increases your score. So for example, if the legal transitions are (1,2), (2,1), and (3,1), then (3,1,2,1,2,1) would be a valid sequence of holds getting a score of 3.
(a) (10 pts.) Define the natural graph representing the input.
(b) (10 pts.) Describe and analyze an algorithm to solve the climbing problem when the input graph is a
(c) (50 pts.) Describe and analyze an algorithm to solve the climbing problem with no restrictions on the input graph.
(Hint: use the linear-time algorithm for finding all SCCs.)
3. (60 pts.) Road Construction
Suppose we have an undirected graph G = (V,E) representing a set of towns and roads connecting them, with roads weighted by the time to drive along them. We are given two towns s,t ¡Ê V and are interested in building new roads to decrease the driving time between them as much as possible. We have a list P = ((a1,b1),…,(ak,bk)) of possible new roads we could build (each represented as a weighted edge as above), but we only have funding to build 2 of them. We want to find which 2 roads in P would reduce the driving time between s and t by as much as possible when added to G.
CSE 102, Winter 2022, HW 7 1
(a) (50 pts.) Describe an efficient algorithm for this problem. Your algorithm¡¯s runtime must be less than quadratic in k (i.e., it should be faster than the brute-force approach of testing all possible pairs of roads to build).
(b) (10 pts.) What is the asymptotic runtime of your algorithm in terms of n = |V|, m = |E|, and k?
CSE 102, Winter 2022, HW 7 2
程序代写 CS代考 加微信: powcoder QQ: 1823890830 Email: powcoder@163.com