Problem 2: 2. You're trying to run through an obstacle course, but there's a twist. Each step on the course is marked either left" or "right". You're only allowed to step on squares labeled "left" with your left foot, and likewise for your right foot. Of course, you can decide which foot to take your first step with. Is it possible for you to run from your starting location to a target location while obeying the course constraints? You are given an undirected graph G = (V, E) in the form of an adjacency list, a start node s, a target node t, and a partition of E into two sets L and R. Call a path "feasible" if it alternates between edges in L and edges in R. (a) Give a linear time (i.e. O(n + m)) algorithm to compute the shortest feasible path from s to t or determine that no such path exists. Show your algorithm is correct and achieves the desired runtime. (b) You've decided that you'd be willing to hop, stepping with the same foot twice in a row, if it shortens your path. However, you aren't very coordinated so you can only hop once during the run. Call a path 1-feasible" if it alternates between edges in L and R, with the possible exception of a single pair of consecutive edges in either L or R. Note that feasible paths are necessarily 1-feasible. Give a linear time (i.e. O(n + m)) algorithm to compute the shortest 1-feasible s t path in G or determine that none exists. Show your algorithm is correct and achieves the desired runtime. (c) Suppose there are also some edges that you are allowed to step on with either foot. Give a one sentence explanation of how to modify your algorithms to work with these new edges. Problem 2: 2. You're trying to run through an obstacle course, but there's a twist. Each step on the course is marked either left" or "right". You're only allowed to step on squares labeled "left" with your left foot, and likewise for your right foot. Of course, you can decide which foot to take your first step with. Is it possible for you to run from your starting location to a target location while obeying the course constraints? You are given an undirected graph G = (V, E) in the form of an adjacency list, a start node s, a target node t, and a partition of E into two sets L and R. Call a path "feasible" if it alternates between edges in L and edges in R. (a) Give a linear time (i.e. O(n + m)) algorithm to compute the shortest feasible path from s to t or determine that no such path exists. Show your algorithm is correct and achieves the desired runtime. (b) You've decided that you'd be willing to hop, stepping with the same foot twice in a row, if it shortens your path. However, you aren't very coordinated so you can only hop once during the run. Call a path 1-feasible" if it alternates between edges in L and R, with the possible exception of a single pair of consecutive edges in either L or R. Note that feasible paths are necessarily 1-feasible. Give a linear time (i.e. O(n + m)) algorithm to compute the shortest 1-feasible s t path in G or determine that none exists. Show your algorithm is correct and achieves the desired runtime. (c) Suppose there are also some edges that you are allowed to step on with either foot. Give a one sentence explanation of how to modify your algorithms to work with these new edges