DSBS-FN-30.01.2024

The first step in the naïve greedy algorithm is?

• adding flows with higher values
• reversing flow if required
• analysing the zero flow
• calculating the maximum flow using trial and error

Suppose you have coins of denominations 1,3 and 4. You use a greedy algorithm, in which you choose the largest denomination coin which is not greater than the remaining sum. For which of the following sums, will the algorithm produce an optimal answer?

• 100
• 10
• 6
• 14

Dijkstra’s Algorithm is the prime example for ___________

• Dynamic programming
• Back tracking
• Branch and bound
• Greedy algorithm

With what data structure can a priority queue be implemented?

• Array
• List
• Heap
• Tree

What is the time complexity to insert a node based on key in a priority queue?

• O(nlogn)
• O(logn)
• O(n)
• O(n2)

Which of the following is not an advantage of a priority queue?

• Easy to implement
• Processes with different priority can be efficiently handled
• Applications with differing requirements
• Easy to delete elements in any case

Descending priority queue can be implemented using ______

• max heap
• min heap
• min-max heap
• trie

The ascending heap property is ___________

• A[Parent(i)] =A[i]
• A[Parent(i)] <= A[i]
• A[Parent(i)] >= A[i]
• A[Parent(i)] > 2 * A[i]

Time complexity of the code? int fun(int n, int m, int o) { if (n <= 0) printf("%d, %d\n",m, o); else { fun(n-1, m+1, o); fun(n-1, m, o+1); }

• Quadratic
• O (log n)
• O (n log m)
• Exponential

What is the time complexity of the following code? int fun(int x) { if (x <= 0) return 1; return 1 + fun(x-1); }

• O(n)
• O (log n)
• O (n log n)
• O (log log n)