ProBlem 1. (20 points) Circle \"true\" or \"false\" as appropriate hen analyzing

Question

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.

Explanation / Answer

d) An array of presorted integers represents a best-case scenario for quicksort when using the first item as the pivot -> False

e) dynamic programing methodis usually implemented with recursive method that solves the problem by solving the sub problems ->True

f) divide and conquer method is efficient solution to problems where smaller isntances are related ->True

g) greedy algorithms do not always produce optimal solutions, its optimality must be formally proved -> True

h) similar to shortest path problem, the longest path problem may also be solved using dynamic programming approach -> True

i) floyds algorithm uses a dynamic programming approach to find the shortest path between each pair of nodes in a directed graph -> True

j) Mergesort algorithm is an example of dynamic programming algorithm -> False

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

---

---

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.