7) Let S = {a1, a2, ..., a10} be a set with n = 10 activities. The start time an

Question

7) Let S = {a1, a2, ..., a10} be a set with n = 10 activities. The start time and finish time of each activity is shown below: si fi a1 9 11 a2 8 12 a3 13 17 a4 4 9 a5 1 3 a6 14 16 a7 10 15 a8 6 9 a9 4 7 a10 2 4 The objective is to find a maximum-size subset of mutually compatible activities. Apply the function GREEDY-ACTIVITY-SELECTOR learned in class. What is the subset of activity returned? Write the activities in the correct order in which they are selected by the algorithm. 8) Let T be a binary search tree (BST) with n keys. Select all the statements below which are TRUE. The height of T is O(n). PREORDER-TREE-WALK(T.root) prints the keys in monotonically increasing order. If T is a perfectly balanced BST (all leaves have the same depth), then the height of T is O(lg n). TREE-INSERT, TREE-DELETE, and TREE-SEARCH have the worst-case running time O(lg n). 9) Select all the answers below which are TRUE. A greedy algorithm makes the choice that looks best at the moment. It makes a locally optimal choice in the hope of obtaining a global optimal solution. A greedy algorithm is a top-down approach. To show that a greedy algorithm is an optimal solution, we need to show the optimal substructure property and the dynamic-programming property. A greedy algorithm always yields an optimal solution.

Explanation / Answer

Multiple QUestions : ANswering 8 and 9.

8.

If T is a perfectly balanced BST (all leaves have the same depth), then the height of T is O(lg n).
TREE-INSERT, TREE-DELETE, and TREE-SEARCH have the worst-case running time O(lg n).

9.

A greedy algorithm makes the choice that looks best at the moment.
It makes a locally optimal choice in the hope of obtaining a global optimal solution.
A greedy algorithm is a top-down approach.

Related Questions

Navigate

• Browse (All)
• Browse 7
• Subjects

---

---

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