Data Structures and Algorithms - Design Techniques
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
- Option : D
- Explanation : Dijkstra’s single source shortest path in not gives the guarantee to work on negative weight edges graph. But in this graph it gives the correct shootest path for all vertex. Shortest path for B → 1 e → –2 F → O g → 3 h → –2 d → 6 C → 3
- Option : C
- Explanation : If emax is maximum weight edge in graph, them it
is possible that emax contain’s in minimum
spanning tree.
Example
cd is maximum weight edge and it must present
in minimum spanning tree
20. What is the weight of a minimum spanning tree
of the following graph?
- Option : B
- Explanation : Minimum Spanning tree is
Total sum = 1 + 2 + 2 + 2 + 3 + 4 + 4 + 5 + 8 = 31
