. Consider the graph below. You start at point A and wish to reach point B,...

 

Transcribed Image Text:

. Consider the graph below. You start at point A and wish to reach point B, only going downward at each step. When traveling an edge, you must pay the toll value associated with it. You wish to compute a path from A to B whose total cost is as small as possible. 4 G 2 6 2 5 3 The general problem is as follows: you are given a directed acyclic graph (DAG) with n vertices (named 1, 2,...,n), and a list of m edges (u, v) where u <v for every edge. You are also given a list of the edges' toll costs, written wuv for each edge (u, v). The goal is to compute a path of minimum cost from vertex 1 to n. The graph above gives one such example setup, but you should consider graphs with nodes that have an arbitrary number of edges. Assume that ⚫ each node v > 1 has at least an edge from a smaller node u < v to v, (u, v); • each node x <n has at least an edge to a larger node y > x, (x, y). This guarantees that there is a path from the first node to the last node. (a) Consider the following local search algorithm for this problem: start at vertex 1 and always traverse down the edge with the lowest possible cost until reaching n. What total cost will this algorithm yield for the above map? Is it optimal? (b) Describe a naïve algorithm for this problem such that the time complexity of this algo- rithm is O(2"), as a function of the number of vertices n. (c) Describe a dynamic-programming algorithm to solve this problem. Prove its correctness, and find its runtime as a function of m and n using big-O notation. . Consider the graph below. You start at point A and wish to reach point B, only going downward at each step. When traveling an edge, you must pay the toll value associated with it. You wish to compute a path from A to B whose total cost is as small as possible. 4 G 2 6 2 5 3 The general problem is as follows: you are given a directed acyclic graph (DAG) with n vertices (named 1, 2,...,n), and a list of m edges (u, v) where u <v for every edge. You are also given a list of the edges' toll costs, written wuv for each edge (u, v). The goal is to compute a path of minimum cost from vertex 1 to n. The graph above gives one such example setup, but you should consider graphs with nodes that have an arbitrary number of edges. Assume that ⚫ each node v > 1 has at least an edge from a smaller node u < v to v, (u, v); • each node x <n has at least an edge to a larger node y > x, (x, y). This guarantees that there is a path from the first node to the last node. (a) Consider the following local search algorithm for this problem: start at vertex 1 and always traverse down the edge with the lowest possible cost until reaching n. What total cost will this algorithm yield for the above map? Is it optimal? (b) Describe a naïve algorithm for this problem such that the time complexity of this algo- rithm is O(2"), as a function of the number of vertices n. (c) Describe a dynamic-programming algorithm to solve this problem. Prove its correctness, and find its runtime as a function of m and n using big-O notation.