Introduction to Analysis of Algorithms - graph and linear time algorithms

Please provide step-by-step explanation if possible also the runtime analysis of the algorithm. Thank you.

 

Transcribed Image Text:

Problem 2 (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 a to hold y is allowed; however, moving directly from y to z 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) (b) (c) Define the natural graph representing the input. Describe and analyze an algorithm to solve the climbing problem when the input graph is a DAG. 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.) Problem 2 (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 a to hold y is allowed; however, moving directly from y to z 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) (b) (c) Define the natural graph representing the input. Describe and analyze an algorithm to solve the climbing problem when the input graph is a DAG. 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.)