ProBlem 1. (20 points) Circle "true" or "false" as appropriate hen analyzing algorithm, the most important measures are the average and true al orst-case running time: A(n) and W(n). There is no need to pay attention to est-case running time B(n) b) Suppose you have a computer that requires 1 minute to solve problem instances true false f size n =100. Suppose you buy a new computer that runs 1000 times faster an the old one. Assume that T (n)-n, the problem instance size that can be olved in the new computer within 1 minute is 1003 ) d) |Given n), if Ttn) eo( nk), then it is always true that SnTn)EO(n-1). true false An array of presorted integers represents a best-case scenario for quicksort true fals when using the first item as the pivot. e) D ynamic programming method is usually implemented with recursive method true false hat solves the problem by solving the sub-problems. ) Divide and conquer method is efficient solution to problems where smaller true false g) Greedy algorithms do not always produce optimal solution; its optimality must true false h) Similar to shortest path problem, the longest path problem may also be solved true false ) Floyd's algorithm uses a dynamic programming approach to find the shortesttrue false instances are related. e formally proved. using Dynamic programming approach aths between each pair of nodes in a directed graph. true fals ) Mergesort algorithm is an example of dynamic programming algorithm