### SET 1

Question 1

**Which one of the following is the recurrence equation for the worst case time complexity of the Quicksort algorithm for sorting n(>= 2) numbers? In the recurrence equations given in the options below, c is a constant.**

A : T(n) = 2T (n/2) + cn

B : T(n) = T(n – 1) + T(1) + cn

C : T(n) = 2T (n – 2) + cn

D : T(n) = T(n/2) + cn

Answer Discuss it!

.

Correct answer is :B

Solution :

When the pivot is the smallest (or largest) element at partitioning on a block of size n the result yields one empty sub-block, one element (pivot) in the correct place and sub block of size n-1 Hence recurrence relation

T(n) = T(n-1)+T(1)+C_{n}

Question 2

**Match the following**

A : P - iii, Q - ii, R - iv, S - i

B : P - i, Q - ii, R - iv, S - iii

C : P - ii, Q - iii, R - iv, S - i

D : P - ii, Q - i, R - iii, S - i v

Answer Discuss it!

.

Correct answer is :C

Solution :

Prim?s algorithm always select minimum distance between two of its sets which is nothing but greedy method.

Floyd-warshall always changes it distance at each iteration which is nothing but dynamic programming

Merge sort In merge sort first we always divide and merge to perform sorting hence divide and conquer.

Hamiltonian circuit Used to reach all the vertex once, if some vertex is repeating in its path it will backtrack.

Question 3

**What are the worst-case complexities of insertion and deletion of a key in a binary search tree?**

A : ?(logn) for both insertion and deletion

B : ?(n) for both insertion and deletion

C : ?(n) for insertion and ?(logn) for deletion

D : ?(logn) for insertion and ?(n) for deletion

Answer Discuss it!

.

Correct answer is :B

Solution :

Consider a single string of binary search tree, we have to trace all the nodes for insertion or deletion in worst case hence ?(n) for both.

Question 4

**An algorithm performs (log N)**^{1/2} find operations, N insert operations,(log N)^{1/2} delete operations, and (log N)^{1/2} decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

A : Unsorted array

B : Min - heap

C : Sorted array

D : Sorted doubly linked list

Answer Discuss it!

.

Correct answer is :A

Solution :

decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

(log N)^{1/2} find operations wil

Question 5

**Let G = (V, E) be a simple undirected graph, and s be a particular vertex in it called the source. For x ∈V, let d(x) denote the shortest distance in G from s to x. A breadth first search (BFS) is performed starting at s. Let T be the resultant BFS tree. If (u, v) is an edge of G that is not in T, then which one of the following CANNOT be the value of d(u) – d(v)?**

Answer Discuss it!

.

Correct answer is :

Question 6

**The graph shown below 8 edges with distinct integer edge weights. The minimum spanning tree (MST) is of weight 36 and contains the edges: {(A, C), (B, C), (B, E), (E, F), (D, F)}. The edge weights of only those edges which are in the MST are given in the figure shown below. The minimum possible sum of weights of all 8 edges of this graph is ______________.**

Answer Discuss it!

.

Correct answer is :69

Solution :

Total sum=10+9+ 2+15+ 7 +16+ 4+ 6 = 69

Question 7

**Let a**_{n} represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for a_{n}?

A : a_{n–2} + a_{n–1} + 2^{n–2}

B : a_{n–2} + 2a_{n–1} + 2^{n–2}

C : 2a_{n–2} + a_{n–1} + 2^{n–2}

D : 2a_{n–2} + 2a_{n–1} + 2^{n–2}

Answer Discuss it!

.

Correct answer is :A

Question 8

**An unordered list contain n distinct elements. The number of comparisons to find an element in this list that is neither maximum nor minimum is**

A : Θ(nlogn )

B : Θ(n)

C : Θ(log n)

D : Θ(1)

Answer Discuss it!

.

Correct answer is :D

Solution :

Consider first three element of the list, atleast one of them will be neither minimum nor maximum

Θ(1)

Question 9

**In the context of abstract-syntax-tree (AST) and control-flow-graph (CFG), which one of the following is TRUE?**

A : In both AST and CFG, let node, N2 be the successor of node N1. In the input program, the code corres

B : For any input program, neither AST nor CFG will contain a cycle

C : The maximum number of successors of a node in an AST and a CFG depends on the input program

D : Each node is AST and CFG corresponds to at most one statement in the input program

Answer Discuss it!

.

Correct answer is :C

Solution :

Optional (A) is not true when CFG contains cycle

Option (B) is false as CFG can contain cycle

Option (D) is false as a single node can contain block of statements.

Question 10

**Given below are some algorithms, and some algorithm design paradigms.**

(1) Dijkstra?s Shortest Path (i) Divide and Conquer (2) Floyd-Warshall algorithm to compute

all pair shortest path (ii) Dynamic Progamming Binary search on a sorted array (iii) Greedy design (4) Backtracking search on a graph (iv) Depth-first search (iv) Breadth-first search

Match the above algorithms on the left to the corresponding design paradigm they follow.

A : 1-i, 2 -iii, 3-i, 4 - v

B : 1-iii, 2 -iii, 3-i, 4 - v

C : 1-iii, 2 -ii, 3-i, 4 - iv

D : 1-iii, 2 -ii, 3-i, 4 - v

Answer Discuss it!

.

Correct answer is :C

Solution :

Dijkstra shortest path algorithm find next node by choosing minimum distance hence greedy approach.

Floyd warshall always apply dynamic programming, once it saves a cost and in the next iteration it will change if this is minimum hence dynamic.

Binary search always divide on two parts .Hence divide and conquer.

Backtracking uses by DFS, one it will reach to dead end it will take back track.

Question 11

**Which one of the following hash functions on integers will distribute keys most uniformly over 10 buckets numbered 0 to 9 for i ranging from 0 to 2020?**

A : h (i)= i^{2} mod 10

B : h (i)= i^{3} mod 10

C : h (i)= (11 * i^{2}) mod 10

D : h (i)=(12 * i^{2}) mod 10

Answer Discuss it!

.

Correct answer is :B

Solution :

If we take first 10 elements, number of collisions taken by the hash function given by option (B) is less when compared to others.

Question 12

**Given a has table T with 25 slots that stores 2000 elements, the load factor for T is ___________.**

Answer Discuss it!

.

Correct answer is :80

Solution :

Load factor = no of elements / no of slots = 2000/25 = 80

Question 13

**Let f(n)=n and g(n)=n**^{ (1 sin n)} , where n is a positive integer. Which of the following statement is/are correct?

I. f (n) = 0(g(n))

II. f (n) = Ω g(n))

A : Only I

B : Only II

C : Both I and II

D : Neither I and II

Answer Discuss it!

.

Correct answer is :D

Solution :

As -1<=sinx<=1, neither of them is true

Question 14

**Assume that a mergesort algorithm in the worst case takes 30 second for an input of size 64. Which of the following most closely approximates the maximum input size of a problem that can be solved in 6 minutes?**

A : 256

B : 512

C : 1024

D : 2048

Answer Discuss it!

.

Correct answer is :B

Solution :

O(n log n)=30s

n = 64 O (64 log 64) = 30

Hence will get factor of 12.8 for 6 min= 6×60 = 360s

O (256 log256) = 360

O (512 log 512) = 360

O(1024 log 1024) = 360

O (2048 log 2048) = 360

So for 512 will get 12.8 as a factor

Question 1

.

Correct answer is :B

Solution :

When the pivot is the smallest (or largest) element at partitioning on a block of size n the result yields one empty sub-block, one element (pivot) in the correct place and sub block of size n-1 Hence recurrence relation

T(n) = T(n-1)+T(1)+C

_{n}

Question 2

.

Correct answer is :C

Solution :

Prim?s algorithm always select minimum distance between two of its sets which is nothing but greedy method.

Floyd-warshall always changes it distance at each iteration which is nothing but dynamic programming

Merge sort In merge sort first we always divide and merge to perform sorting hence divide and conquer.

Hamiltonian circuit Used to reach all the vertex once, if some vertex is repeating in its path it will backtrack.

Question 3

.

Correct answer is :B

Solution :

Consider a single string of binary search tree, we have to trace all the nodes for insertion or deletion in worst case hence ?(n) for both.

Question 4

^{1/2}find operations, N insert operations,(log N)

^{1/2}delete operations, and (log N)

^{1/2}decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

.

Correct answer is :A

Solution :

decrease-key operations on a set of data items with keys drawn from a linearly ordered set. For a delete operation, a pointer is provided to the record that must be deleted. For the decrease-key operation, a pointer is provided to the record that has its key decreased. Which one of the following data structures is the most suited for the algorithm to use, if the goal is to achieve the best total asymptotic complexity considering all the operations?

(log N)

^{1/2}find operations wil

Question 5

.

Correct answer is :

Question 6

.

Correct answer is :69

Solution :

Total sum=10+9+ 2+15+ 7 +16+ 4+ 6 = 69

Question 7

_{n}represent the number of bit strings of length n containing two consecutive 1s. What is the recurrence relation for a

_{n}?

.

Correct answer is :A

Question 8

.

Correct answer is :D

Solution :

Consider first three element of the list, atleast one of them will be neither minimum nor maximum

Θ(1)

Question 9

.

Correct answer is :C

Solution :

Optional (A) is not true when CFG contains cycle

Option (B) is false as CFG can contain cycle

Option (D) is false as a single node can contain block of statements.

Question 10

(1) Dijkstra?s Shortest Path | (i) Divide and Conquer |

(2) Floyd-Warshall algorithm to compute all pair shortest path | (ii) Dynamic Progamming |

Binary search on a sorted array | (iii) Greedy design |

(4) Backtracking search on a graph | (iv) Depth-first search |

(iv) Breadth-first search |

.

Correct answer is :C

Solution :

Dijkstra shortest path algorithm find next node by choosing minimum distance hence greedy approach.

Floyd warshall always apply dynamic programming, once it saves a cost and in the next iteration it will change if this is minimum hence dynamic.

Binary search always divide on two parts .Hence divide and conquer.

Backtracking uses by DFS, one it will reach to dead end it will take back track.

Question 11

.

Correct answer is :B

Solution :

If we take first 10 elements, number of collisions taken by the hash function given by option (B) is less when compared to others.

Question 12

.

Correct answer is :80

Solution :

Load factor = no of elements / no of slots = 2000/25 = 80

Question 13

^{ (1 sin n)}, where n is a positive integer. Which of the following statement is/are correct?

I. f (n) = 0(g(n))

II. f (n) = Ω g(n))

.

Correct answer is :D

Solution :

As -1<=sinx<=1, neither of them is true

Question 14

.

Correct answer is :B

Solution :

O(n log n)=30s

n = 64 O (64 log 64) = 30

Hence will get factor of 12.8 for 6 min= 6×60 = 360s

O (256 log256) = 360

O (512 log 512) = 360

O(1024 log 1024) = 360

O (2048 log 2048) = 360

So for 512 will get 12.8 as a factor