Suppose each set is represented as a linked list with elements in arbitrary order. Which of the operations among union, intersection, membership, cardinality will be the slowest?

Suppose we run Dijkstra's single source shortest-path algorithm on the following edge-weighted directed graph with vertex P as the source.

In what order do the nodes get included into the set of vertices ofr which the shortest path distances are finalized?

How many distinct binary search trees can be created out of 4 distinct keys?

The time complexity of the following C function is (assume n > 0)

A priority-Queue is implemented as a Max-Heap, Initially, it has 5 elements. The level-order traversal of the heap is given below: 10, 8, 5, 3, 2 Two new elements '1' and '7' are inserted in the heap in that order. The level-order traversal of the heap after the insertion of the elements is

In a complete k-ary, every internal node has exactly k children. The number of leaves in such a tree with n internal nodes is

Suppose T(n) = 2T(n/2) + n,T(0) = T(1) = 1 Which one of the following is FALSE?

Suppose there are log n sorted lists of n/ log n elements each. The time complexity of producing a sorted list of all these elements is:

A program takes as input a balanced binary search tree with n leaf modes and computes the value of a function g(x) for each node x . If the cost of computing g(x) is min (number of leaf-nodes in learsubtree of x , number of leaf-nodes in right-subtree of x) then the worst case time complexity of the program is

The time complexity of computing the transitive closure of a binary relation on a set of n elements is known to be

Let G (V,E) an undirected graph with positive edge weights. Dijkstra's single source-shortes path algorithm can be implemented using the binary heap data structure with time complexity?

Let A[1,....n] be an array storing a bit (1 or 0) at each location, and f (m) is a function whose time complexity is è(m). Consider the following program fragment written in a C like language:

The complexity of this program fragment is

The recurrence equation T(1) = 1 T(n) = 2T(n − 1) + n, n ^$\le$ 2 evaluates to

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 di profit P_i is earned if the task is completed before the end of the d₁^th unit of time.

What is the maximum profit earned?

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 di profit P_i is earned if the task is completed before the end of the d₁^th unit of time.

Are all tasks completed in the schedule that gives maximum profit?

Consider the following C-function:

The space complexity of the above function is

A undirected graph G has n nodes. Its adjacency matrix is given by by an n x n square matrix whose

1. diagonal elements are O's, and
2. non-diagonal elements are 1's. Which one of the following is TRUE?

Consider the following C-function:

The space complexity of the above function is foo O and store the values of foo (i),0 <= i < n, as and when they are computed. With this modification, the time complexity for function fooO is significantly reduced. The space complexity of the modified function would be: