Problem 1. Consider the problem of planning the fastest plane trip from Sacramento to Shamb- hala. Assume that you know for each airport the time...

that airport and the time it is scheduled to arrive.

Problem 1. Consider the problem of planning the fastest plane trip from Sacramento to Shamb-hala. Assume that you know for each airport the time each flight is scheduled to leave fromthat airport and the time it is scheduled to arrive. You may further assume that each flightwill be exactly on schedule and that all flights are for one 24 hour period. (a) Describe an eflicient algorithm to find the route which gets you to Shambhala in theleast time assuming you arrive at the Sacramento airport at 10AM. You may assume that ifyou arrive at an airport at time 73, you can depart on any flight leaving after time t. (b) If there are a. airports and fi flights leaving airport 2', what is the run time of yoursolution to part a)? Problem 2. Suppose we have a directed graph G and a weight matrix W such that W[i, j] is thetime in seconds it takes to traverse arc (i, j). In addition, suppose that each time you gothrough an intermediate node there is a delay of 2 seconds. Thus the path 2' — j — k — r takestime W[i,j] + 2 + W[j,k] + 2 + W[k,r] to go from i to 3'. We want to find the path withsmallest delay from node as to all other nodes. We assume all values in W are positive. (3) Describe how to modify Dijkstra’s algorithm to find the least delay path from a startnode a: to all other vertices. Specifically, when we process a vertex 1) describe how to updatethe labels of all the neighbors of t). (b) What is the running time of your algorithm on a graph with n nodes and m arcs whichis stored using adjacency lists? (0) What is the running time of your algorithm on a graph with n nodes and m arcs whichis stored using an adjacency matrix? Problem 3. Describe a constant-time algorithm, an improvement of the Cashier’s algorithm, that,given an input of m dollars, returns q (quarters), d (dimes), n (nickels) and p (pennies) togive change with the fewest coins. You may assume (somewhat unrealistically) that you cando standard arithmetic operations on any size numbers in 0(1) time. Also, assume there isno $1 denomination (i.e., the largest coin returned is a quarter).