DT Q16
Common Data for Q. 16 & Q. 17
We are given 9 tasks T1, T2… T9. The execution of each task requires one unit of time. We can execute one task at a time. Ti has a profit Pi and a deadline di profit Pi is earned if the task is completed before the end of the dith unit of time.| Task | T1 | T2 | T3 | T4 | T5 | T6 | T7 | T8 | T9 |
| Profit | 15 | 20 | 30 | 18 | 18 | 10 | 23 | 16 | 25 |
| Deadline | 7 | 2 | 5 | 3 | 4 | 5 | 2 | 7 | 3 |
- Option : C
- Explanation : In order to find minimum size of X capable of
storing any kind of binary tree, the worst case
size of the tree has to be taken.
In the worst case size of the tree has to be taken.
In the worst case only a single node will contain
the data at each level of the tree.
For example, for 4 data items, the worst case
binary tree will be as follows
Generalizing the concept, for n vertices, the levels
of tree that are required will be n.
Memory required at each level (starting from root)
will be 20, 21, 22, .... 2n-1
∴ Minimum size = 20 + 21 + 22, .... 2n-1
= 20(2n-1)/(2-1) = 2n-1
