2.1. DP! We said in class that finding a longest path is NP-hard. (a) This result is very conter-intuitive. It seems like we should be able to just take the DPs we wrote for Floyd- Warshall or Bellman-Ford and flip the mins to maxes! This idea does not work because of cycles (we want a path that does not repeat vertices, but if we can repeat vertices we can always go along a positive weight cycle repeatedly, and the recurrences don't explicitly prevent that). Think about why the recurrences fail when there are cycles (you might want to do an example or two). You do not have to write anything for this part [0 points) (b) Write a formula for a recurrence for finding the length of the longest path in a weighted directed acyclic graph. (There's no need to totally reinvent the wheel! You might want to start with the recurrence on slide 7 here) (10 points) (c) Describe what the recurrence calculates in 1-2 sentences of English. Be sure to describe what any parameters represent. [3 points] (d) What would a return statement look like in a method to calculate the longest path in the whole graph (e.g. what input(s) to the recurrence would you look up? If you look up more than one value, what is your overall answer?) [2 points] (e) Describe an evaluation order to evaluate your recurrence (you do not have to write the actual code). I.e. tell us which values to calculate first and which to calculate last. (Our explanation is 1 sentence). [3 points] (f) Wait! Finding longest paths is NP-hard, have you shown P = NP? Describe why or why not in 1-3 sentences [2 points]