In a heap with n elements with the smallest element at the root, the 7th smallest element can be found in time

Consider the following three claims I. (n + k)^m = O (n^m) where k and m are constants II. 2ⁿ⁺¹ = O(2ⁿ) III. 2²ⁿ⁺¹ = O(2ⁿ)

Which of these claims are correct?

The usual O(n²) implementation of Insertion Sort to sort an array uses linear search to identify the position where an element is to be inserted into the already sorted part of the array. If, instead, we use binary search to identify the position, the worst case running time will

Consider the following graph

Among the following sequences I a b e g h f II a b f e h g III a b f h g e IV a f g h b e

Which are depth first traversals of the above graph?

In a permutation a₁ ... a_n, of n distinct integers, an inversion is a pair (a_i, a_j) such that i < j and ai > aj.

If all permutations are equally likely, what is the expected number of inversions in a randomly chosen permutation of 1. . . n?

In a permutation a₁ ... a_n, of n distinct integers, an inversion is a pair (a_i, a_j) such that i < j and ai > aj.

What would be the worst case time complexity of the Insertion Sort algorithm, if the inputs are restricted to permutations of 1. . . n with at most n inversions?

Let $G= (V,E)$ be a directed graph with $n$ vertices. A path from $v_i$ to $v_j$ in $G$ is a sequence of vertices ($v_{i},v_{i+1}, \dots , v_j$) such that $(v_k, v_k+1) \in E$ for all $k$ in $i$ through $j-1$. A simple path is a path in which no vertex appears more than once.

Let $A$ be an $n \times n$ array initialized as follows.

$$A[j,k] = \begin{cases} 1 \text { if } (j,k) \in E \\ 0 \text{ otherwise} \end{cases}$$

Consider the following algorithm.

for i=1 to n
    for j=1 to n
        for k=1 to n
            A[j,k] = max(A[j,k], A[j,i] + A[i,k]);  

Which of the following statements is necessarily true for all j and k after termination of the above algorithm?

What is the weight of a minimum spanning tree of the following graph?

Let G = (V,E) be an undirected graph with a subgraph G1 = (V1, E1). Weights are assigned to edges of G as follows.

$$G= \begin{cases} 0 \text { if } e \in E_1 \\ 1 \text{ otherwise} \end{cases}$$

A single-source shortest path algorithm is executed on the weighted graph (V,E,w) with an arbitrary vertex v₁ of V₁ as the source. Which of the following can always be inferred from the path costs computed?

The following are the starting and ending times of activities A, B, C, D, E, F, G and H respectively in chronological order: “a_s b_s c_s a_e d_s c_e e_s f_s b_e d_e g_s e_e f_e h_s g_e h_e”. Here, x_s denotes the starting time and x_e denotes the ending time of activity X. We need to schedule the activities in a set of rooms available to us. An activity can be scheduled in a room only if the room is reserved for the activity for its entire duration. What is the minimum number of rooms required?

Consider the polynomial p(x) = a0 + a1x + a2x^2 +a3x^3, where ai != 0, for all i. The minimum number of multiplications needed to evaluate p on an input x is :

In a binary max heap containing n numbers, the smallest element can be found in time

To implement Dijkstra's shortest path algorithm on un weighted graphs so that it runs in linear time, the data structure to be used is:

Which one of the following in place sorting algorithms needs the minimum number of swaps?

Consider a weighted complete graph G on the vertex set {v₁, v₂,............., v_n} such that the weight of the edge (v_i, v_j) is 2 |i - j| . The weight of a minimum spanning tree of G is:

A scheme for storing binary trees in an array X is as follows. Indexing of X starts at 1 instead of 0. the root is stored at X[1]. For a node stored at X [i], the left child, if any, is stored in X [2i] and the right child, if any, in X [2i+1]. To be able to store any binary tree on n vertices the minimum size of X should be

An element in an array X is called a leader if it is greater than all elements to the right of it in X. The best algorithm to find all leaders in an array

Consider the following C-program fragment in which i, j and n are integer variables.
for( i = n, j = 0; i > 0; i /= 2, j +=i ); Let val ( j ) denote the value stored in the variable j after termination of the for loop. Which one of the following is true?

Consider the following graph:

Which one of the following cannot be the sequence of edges added, in that order, to a minimum spanning tree using Kruskal's algorithm?

The cube root of a natural number n is defined as the largest natural number m such that m³ $\le$n. The complexity of computing the cube root of n (n is represented in binary notation) is