Algorithms - Algorithm Design Techniques

Avatto > > GATE COMPUTER SCIENCE > > Practice Questions > > Computer Science And Information Technology > > Algorithms > > Algorithm Design Techniques

Common Data for Q. 16 & Q. 17

We are given 9 tasks T₁, T₂… T₉. The execution of each task requires one unit of time. We can execute one task at a time. T_i has a profit P_i and a deadline d_i profit P_i is earned if the task is completed before the end of the d_i^th unit of time.

Task	T₁	T₂	T₃	T₄	T₅	T₆	T₇	T₈	T₉
Profit	15	20	30	18	18	10	23	16	25
Deadline	7	2	5	3	4	5	2	7	3

16. To implement Dijkstra's shortest path algorithm on unweighted graphs so that it runs in linear time, then data structure to be used is

Answer
Comment
Array

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 2⁰, 2¹, 2², .... 2^n-1
∴ Minimum size = 2⁰ + 2¹ + 2², .... 2^n-1
= 2⁰(2^n-1)/(2-1) = 2^n-1

You must be logged in to post a comment.

17. Dijkstra's single source shortest path algorithm when run from vertex a in the below graph, computes the corrects shortest path distance to

Answer
Comment
Array

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

You must be logged in to post a comment.

18. Consider the directed graph shown in the figure below. There are multiple shortest paths between vertices S and T. Which one will be reported by Dijkstra's shortest path algorithm? Assume that, in any iteration, the shortest path to a vertex v is updated only when a strictly shorter path to v is discovered.

Answer
Comment
Array

Option : D
Explanation :

You must be logged in to post a comment.

19. Let G be an undirected connected graph with distinct edge weights. Let e_max be the edge with maximum weight and e_min the edge with minimum weight. Which of the following statements is false?

Answer
Comment
Array

Option : C
Explanation :
If e_max is maximum weight edge in graph, them it is possible that e_max contain’s in minimum spanning tree.
Example

cd is maximum weight edge and it must present in minimum spanning tree