Test 4 - Algorithms | Computer Science(CS)

Question 1 Multiple Choice (Single Answer)

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?

0(n)
0(nlog n)
0(n²)
0(n!)

Question 2 Multiple Choice (Single Answer)

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

$i-1$
$\lfloor \frac{i}{2} \rfloor$
$\lceil \frac{i}{2} \rceil$
$\frac{(i+1)}{2}$

Question 3 Multiple Choice (Single Answer)

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

f (n) = 0(g(n)) and g(n) $\ne$Y 0(f (n))
g (n) = 0(f (n)) and f (n) $\ne$Y 0(g(n))
f (n) $\ne$Y 0(g(n)) and g(n) $\ne$Y 0(f (n))
f (n) = 0(g(n)) and g(n) = 0(f (n))

Question 4 Multiple Choice (Single Answer)

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

$2^k$
$\frac{(3^{k+1}-1)}{2}$
$3^{\log_2 k}$
$2^{\log_3 k}$

Question 5 Multiple Choice (Single Answer)

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

One
Two
Three
Four

Question 6 Multiple Choice (Single Answer)

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?

$\frac{n(n-1)} {2}$
$2^n$
$n!$
$2^\frac{n(n-1)} {2} $

Question 7 Multiple Choice (Single Answer)

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.

2
3
4
$n − 2 \left[ \dfrac{n}{2} \right] + 2$

Question 8 Multiple Choice (Single Answer)

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

$\log n$
$\dfrac{n}{2}$
$\log_2 n -1$
$n$

Question 9 Multiple Choice (Single Answer)

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

n²
$\dfrac{n(n-1)}{2}$
(n-1)
$\dfrac{(n-1)(2)}{2}$

Question 10 Multiple Choice (Single Answer)

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

$\frac{n}{2}$
$\frac{(n-1)}{3}$
$\frac{(n-1)}{2}$
$\frac{(2n+1)}{3}$

Question 11 Multiple Choice (Single Answer)

To evaluate an expression without any embedded function calls

One stack is enough
Two stack are needed
As many stacks as the height of the expression tree are needed
A Turning machine is needed in the general case

Question 12 Multiple Choice (Single Answer)

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?

d(r,u) < d(r,v)
d(r,u) > d(r,v)
d(r,u) $\le$ d(r,v)
None of the above

Question 13 Multiple Choice (Single Answer)

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

0(n)
0(log n)
0(loglog n)
0(1)

Question 14 Multiple Choice (Single Answer)

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

preorder traversal
inorder traversal
depth first search
breadth first search

Question 15 Multiple Choice (Single Answer)

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?

$\log_2 n$
$\log_{\frac{4}{3}} n$
$\log_3 n$
$\log_{\frac{3}{2}} n$

Question 16 Multiple Choice (Single Answer)

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]
(2) 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?

n
n -1
2n
$\dfrac{n}{2}$

Question 17 Multiple Choice (Single Answer)

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?

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

1 only
2 only
1 and 2 only
3 and 4 only

Question 18 Multiple Choice (Single Answer)

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

n
n²
nlog n
nlog²n

Question 19 Multiple Choice (Single Answer)

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

preorder and postorder
inorder and postorder
preorder and inorder
level order and postorder

1 only
2 and 3
3 only
4 only

Question 20 Multiple Choice (Single Answer)

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

best if A is in row-major, and B is in column-major order
best if both are in row-major order
best if both are in column-major order
independent of the storage scheme

Test 4 - Algorithms | Computer Science(CS)

Questions