Randomized quick sort is an extension of quick sort where the pivot is chosen randomly. What is the worst case complexity of sorting n numbers using randomized quick sort?

Consider any array representation of an n element binary heap where the elements are stored from index 1 to index n of the array. For the element stored at index i of the array $(i \leq n)$, the index of the parent is

Let f (n) = n2 logn and g(n) = n(logn)10 be two positive functions of n. Which of the following statements is correct?

The solution to the recurrence equation $T(2^k) = 3T(2^{k-1})+1, T(1) =1$ is

What is the minimum number of stacks of size n required to implement a queue to size n?

How many undirected graphs (not necessarily connected) can be constructed out of a given set $V={v_1, v_2, \dots v_n}$ of $n$ vertices?

The minimum number of colours required to colour the vertices of a cycle with n nodes in such a way that no two adjacent nodes have same colour is.

In the worst case, the number of comparisons needed to search a single linked list of length n for a given element is

Maximum number of edges in a n-node undirected graph without self loops is

The number of leaf nodes in a rooted tree of n nodes, with each node having 0 or 3 children is:

To evaluate an expression without any embedded function calls

Consider the undirected unweighted graph G. Let a breadth-first traversal of G be done starting from a node r . Let d(r,u) and d(r,v) be the lengths of the shortest paths form r to u and v respectively in G. If u is visited before v during the breadth-first traversal, which of the following statements is correct?

The running time of the following algorithm Procedure A(n) If n <= 2 return (1) else return (A($|\sqrt n|$)); Is best described by

Level order traversal of a rooted tree can be done by stating from the root and performing

A weight-balanced tree is a binary tree in which for each node, the number of nodes in the let sub tree is at least half and at most twice the number of nodes in the right sub tree. The maximum possible height (number of nodes on the path from the root to the furthest leaf) of such a tree on n nodes is best described by which of the following?

Consider the following algorithm for searching for a given number x in an unsorted array A[1.....n] having n distinct values : (1) Choose an i uniformly at random from 1....n If A[i] = x then stop else Goto 1;

Assuming that x is present A, What is the expected number of comparisons made by the algorithm before it terminates?

Given the following input(4322,1334,1471,9679,1989,6171,6173,4199) and the hash function x mod 10, which of the following statements are true?

1. 9679,1989,4199 hash to the same value
2. 1471,6171 hash to the same value
3. All element hashes to a different value

The tightest lower bound on the number of comparisons, in the worst case, for comparision-based sorting is of the order of

Consider the label sequences obtained by the following pairs of traversals on a labeled binary tree. Which of these pairs identify a tree uniquely?

1. preorder and postorder
2. inorder and postorder
3. preorder and inorder
4. level order and postorder

Two matrices M₁ and M₂ are to be stored in arrays A and B respectively. Each array can be stored either in row-major or column major order in contiguous memory locations. The time complexity of an algorithm to compute M₁x M₂ x will be