A submarine is ordered to patrol between two ports. Assume the locations along the patrol route are identified by consecutive integers between 0 (for the first port) and n (for the other port). One way for the submarine to hide is to settle on the bottom in a "sea valley" where the depth at that location is greater than the depths of both adjacent locations. The submarine may determine the depth at its current location by performing a "depth survey" that is somewhat expensive. The returned depth for the location will be a non-negative number, with larger numbers indicating deeper depths. Since the ports have adjacent locations on only one side, they do not qualify as "sea valleys". Furthermore assume e the depth at both ports is 0 e the depth at the other locations is positive . adjacent locations always have different depths First (9 pts): Create a divide and conquer algorithm for finding a "sea valley" (a location whose depth is greater than the adjacent locations) that requires only O(log n) depth surveys in the worst case (any sea valley will do, it need not be the first or deepest). State your algorithm, argue that it is correct, derive the recurrence for the number of depth surveys needed, and then bound the recurrence. Measure the cost of your algorithm in "depth surveys" and ignore the time to sail between locations. Second (1 pt): Assume that the submarine starts out at location 0, and runs your algorithm by sailing to each requested depth survey location in turn, and the locations are evenly spaced at one unit apart. Get a good asymptotic bound on how far the submarine might have to sail (as a function of n) when using your algorithm