Answer Happy

Question 1: (1) Consider a map that is discretized into n by n squares. Each square has a number that represents the altitude. This map is represented by a 2D array A. Specifically, A[i, j] contains the altitude of the square (i,j). Suppose one can only go from a square to an adjacent square with a lower altitude. Design an algorithm and state the running time (in terms of n) that outputs whether it is possible to go from the top left square to the bottom right square. The algorithm should be as efficient as possible. (2) Design an algorithm, as efficient as possible, that outputs all the squares that can reach the bottom right square (again, assume that one can only go from a square to an adjacent square with a lower altitude). In particular, the algorithm should output a list of squares that if you start there, it is possible to reach the bottom right square. (3) Suppose now that it is always possible to go from a square to its adjacent squares. However, the required energy for such a move is the absolute difference between the altitudes of the two squares. In other words, going from square (1,1) to an adjacent square (i'.j') requires (A[i,j] - A[1'.j unit of energy. Design an algorithm that find the path (if there is one) from the top left
Question 2: Suppose we are given a graph whose edge weights are integers in the set {1,2,...,100} and a source vertex s. Show how to find the shortest paths from s to all other vertices in 0(E] + V) time. • Question 3: Given an array of numbers A[1...n]. provide an algorithm that rearranges the entries of A so that after the rearrangement, the sum A is maximized. Make sure you prove the correctness. Question 4: Suppose we are given a rooted binary tree. Furthermore, each node v in the tree has a number Wu) associated with it. Design an algorithm that finds the path from the root to a leaf such that the sum of the associated numbers of the nodes in the path is maximized. Hint: use dynamic programming/divide and conquer approach.