Include pseudo-code for your algorithms, a run-time analysis and a proof of correctness.

You are the owner of a truck that delivers goods to cities, based in city 1. If the truck visits city 1 lessthanorequalto i lessthanorequalto n, then the profit made is p_i. If the truck travels from city i to city j, it costs C_ij > 0. Your goal is to find a cyclic route in which the ratio of profit to cost is maximization. Consider a directed graph G = (V, E) whose nodes are cities, and which has edges between every pair of cities. For any cycle C in this graph, the profit-to-cost ratio is r(C) = sigma_(i, j)Element C P_j/sigma_(i, j)Element C c_ij. Let r* be the maximum ratio achievable by a simple cycle. One way to determine r* is by binary search, guessing some ratio r, and then testing whether it is too large or too small. Consider any positive r > 0. Give each edge (i, j) a weight of W_ij = rc_ij - p_j. Show that if there is a cycle of negative weight, then r r*. Give an efficient algorithm that takes as input a desired accuracy Element > 0 and returns a simple cycle in which r(C) greaterthanorequalto r* - Element. Justify the correctness of your algorithm and analyze its running time in terms of n, Element and R = max (i, j) Element E P_ij/c_ij. You are the owner of a truck that delivers goods to cities, based in city 1. If the truck visits city 1 lessthanorequalto i lessthanorequalto n, then the profit made is p_i. If the truck travels from city i to city j, it costs C_ij > 0. Your goal is to find a cyclic route in which the ratio of profit to cost is maximization. Consider a directed graph G = (V, E) whose nodes are cities, and which has edges between every pair of cities. For any cycle C in this graph, the profit-to-cost ratio is r(C) = sigma_(i, j)Element C P_j/sigma_(i, j)Element C c_ij. Let r* be the maximum ratio achievable by a simple cycle. One way to determine r* is by binary search, guessing some ratio r, and then testing whether it is too large or too small. Consider any positive r > 0. Give each edge (i, j) a weight of W_ij = rc_ij - p_j. Show that if there is a cycle of negative weight, then r r*. Give an efficient algorithm that takes as input a desired accuracy Element > 0 and returns a simple cycle in which r(C) greaterthanorequalto r* - Element. Justify the correctness of your algorithm and analyze its running time in terms of n, Element and R = max (i, j) Element E P_ij/c_ij