Algorithms for Data Science Final 20 points #1 (4 points): Rank the following functions by order of growth into groups. Place functions f(n) and g(n) into the same group if and only if f(n) € ©(g(n)). List the group in ascending order of growth. a) n² d) 1+ 2+ 3+ + (n-1) + n g) n log(n) b) sqrt(n) e) n! h) 1 c) log(n) f) 1000n i) 2n #2 (3 points): Briefly explain why Python lists should not be used as keys for a hash table. #3 (4 points) We covered several data structures: list, stacks, queues, heaps, and hash tables. For each problem below choose the best data structure that can be used to solve the problem efficiently. (a) Given a list A of n integers, reverse the order of the elements in A. (b) Given a list A of n integers, report the ten largest integers in A. (c) Given an undirected graph G determine if G is connected. #4 (5 points): We covered several algorithm design techniques: incremental, divide-and- conquer, dynamic programming, greedy, and backtracking. For each problem below choose the most efficient technique that can be used to solve the problem efficiently. If more than one choice is available select the one that is simplest to implement. Justify your answer. (a) Given a list of n triangles, find the range (i.e., min and max) of the perimeters of the input triangles. (a) Sort a list of n triangles in decreasing order of perimeter. (c) Given a list of n items and their corresponding integer weights, maximize the total weight of items that fit in a backpack of capacity W by selecting items from the given list. (d) Given a list of n items and their corresponding integer weights, maximize the total number of items, selected from the given list, that fit in a backpack of maximum capacity W. #5 (4 points): Explain the similarities and differences between Divide-and-Conquer and Dynamic Programming. When would you use Dynamic Programming instead of Divide-and-Conquer?