Question

C. 7. True/False Questions. (2 points each) a. Applying Horner's Rule, an n-degree polynomial can be evaluated at a given point using only n multiplications and n additions. b. Quick Sort and Merge Sort are comparison-based sorting algorithms. Heap Sort and Distribution Counting Sort are not comparison-based sorting algorithms. An AVL tree applies four types of rotations: RIGHT, LEFT, RIGHT-LEFT, and LEFT-RIGHT. d. When an AVL tree's left sub-tree is left-heavy, a LEFT rotation is needed. e. When an AVL tree's left sub-tree is right-heavy, a LEFT-RIGHT rotation is needed. f. AVL trees and 2-3 trees are examples of balanced binary search trees. g. A 2-3 tree's leaf nodes are all on the same level. h. In a heap, the highest indexed parent node may have either one or two children. All other parent nodes must have two children. i. Building a heap using the bottom-up method is more efficient than using the top-down method. j. Given certain strings and certain sub-strings, the brute-force string matching algorithm can sometimes perform faster than Horspool's algorithm. k. Applying the Greedy design technique, greedy choices must be feasible, locally optimal, and irrevocable. 1. Dijkstra's shortest path algorithm finds the shortest path between all pairs of nodes in a graph, provided there are no negative edge weights. m. Huffman codes use a fewer number of bits to represent less frequently used characters and a greater number of bits to represent more frequently used characters. n. Greedy algorithms choose the best option available at the time in the hope that a sequence of globally optimal choices will produce a locally optimal solution. 0. The Dynamic Programming design technique suggests solving a main problem by recording solutions to smaller subproblems in a table and using the table values to obtain a solution to the main problem.

Answer 1

it can a) False bez can be evaluated using only [2/2] + 2 multiplications b) False because Heap sort is comparison based algorithm. c) Torve d) False e) True f) True Terve a) h) false Torve Toive :) ;) k) Tone e) Tove m) False n) True True 0 )