### SET 4

Question 1

**What is the number of swaps required to sort n elements using selection sort, in the worst case? **

A : θ (n)

B : θ (n log n)

C : θ (n^{2})

D : θ (n^{2} log n)

Answer Discuss it!

.

Correct answer is :A

Solution :

Selection sort performs swap only after finding the appropriate position of the current picked element. So there are O(n) swaps performed in selection sort. Because swaps require writing to the array, selection sort is preferable if writing to memory is significantly more expensive than reading.

Question 2

**S -> aSa|bSb|a|b; The language generated by the above grammar over the alphabet {a,b} is the set of**

A : All palindromes

B : All odd length palindromes

C : Strings that begin and end with the same symbol

D : All even length palindromes

Answer Discuss it!

.

Correct answer is :B

Solution :

The possible palindrome generated by above grammar can be of odd length only as there is no rule for S -> ε. For example generated palindromes are aba, aaa, bab, ababa, aaaaa, ..

Question 3

**Which of the following statement(s)is / are correct regarding Bellman-Ford shortest path algorithm? **

P: Always finds a negative weighted cycle, if one exist s.

Q: Finds whether any negative weighted cycle is reachable from the source.

A : P only

B : Q only

C : Both P and Q

D : Neither P and Q

Answer Discuss it!

.

Correct answer is :B

Solution :

Bellman-Ford shortest path algorithm is a single source shortest path algorithm. So it can only find cycles which are reachable from a given source, not any negative weight cycle. Consider a disconnected where a negative weight cycle is not reachable from the source at all. If there is a negative weight cycle, then it will appear in shortest path as the negative weight cycle will always form a shorter path when iterated through the cycle again and again.

Question 4

**The running time of an algorithm is represented by the following recurrence relation**

if n <= 3 then T(n) = n

else T(n) = T(n/3) + cn

Which one of the following represents the time complexity of the algorithm?

(A) θ (n)

(B) θ (n log n)

(C) θ (n^2)

(D) θ (n^2 log n)

A : A

B : B

C : C

D : D

Answer Discuss it!

.

Correct answer is :A

Solution :

T(n) = cn + T(n/3)

= cn + cn/3 + T(n/9)

= cn + cn/3 + cn/9 + T(n/27)

Taking the sum of infinite GP series. The value of T(n) will
be less than this sum.

T(n) <= cn(1/(1-1/3))

<= 3cn/2

or we can say

cn <= T(n) <= 3cn/2

Therefore T(n) = θ(n)

This can also be solved using Master Theorem for solving recurrences.

Question 5

**The keys 12, 18, 13, 2, 3, 23, 5 and 15 are inserted into an initially empty hash table of length 10 using open addressing with hash function h(k) = k mod 10 and linear probing. What is the resultant hash **

A : A

B : B

C : C

D : D

Answer Discuss it!

.

Correct answer is :C

Solution :

Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. Well known probe sequences include:

linear probing in which the interval between probes is fixed–often at 1.

quadratic probing in which th

Question 6

**Consider the following graph.Which one of the following is NOT the sequence of edges added to the minimum spanning tree using Kruskal's algorithm?**

A : (b,e)(e,f)(a,c)(b,c)(f,g)(c,d)

B : (b,e)(e,f)(a,c)(f,g)(b,c)(c,d)

C : (b,e)(a,c)(e,f)(b,c)(f,g)(c,d)

D : (b,e)(e,f)(b,c)(a,c)(f,g)(c,d)

Answer Discuss it!

.

Correct answer is :D

Solution :

In the sequence (b, e) (e, f) (b, c) (a, c) (f, g) (c, d) given option D, the edge (a, c) of weight 4 comes after (b, c) of weight 3. In Kruskal's Minimum Spanning Tree Algorithm, we first sort all edges, then consider edges in sorted order, so a higher weight edge cannot come before a lower weight edge.

Question 7

**In quick sort, for sorting n elements, the (n/4)th smallest element is selected as pivot using an O(n) time algorithm. What is the worst case time complexity of the quick sort?**

A : θ (n)

B : θ (n log n)

C : θ (n^{2})

D : θ (n^{2} log n)

Answer Discuss it!

.

Correct answer is :B

Solution :

Answer(B) The recursion expression becomes: T(n) = T(n/4) + T(3n/4) + cn After solving the above recursion, we get θ(nLogn)

Question 8

**Which of the following statements are TRUE? **

I. There exist parsing algorithms for some programming languages whose complexities are less than O(n^{3}).

II. A programming language which allows recursion can be implemented with static storage allocation.

III. No L-attributed definition can be evaluated in The framework of bottom-up parsing.

IV. Code improving transformations can be performed at both source language and intermediate code level.

A : I and II

B : I and IV

C : III and IV

D : I,III and IV

Answer Discuss it!

.

Correct answer is :B

Solution :

II is false, in recursion, compiler cannot determine the space needed for recursive calls. III is false.

Question 9

**A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n respectively, with indexes of X and Y starting from 0. We wish to find the length of the longest common sub-sequence(LCS) of X[m] and Y[n] as l(m,n), where an incomplete recursive definition for the function l(i,j) to compute the length of The LCS of X[m] and Y[n] is given below:**

l(i,j) = 0, if either i=0 or j=0

= expr1, if i,j > 0 and X[i-1] = Y[j-1]

= expr2, if i,j > 0 and X[i-1] != Y[j-1]

Which of the following options is correct?

A : expr1 = l(i-1, j) + 1

B : expr1 = l(i, j-1)

C : expr2 = max(l(i-1, j), l(i, j-1))

D : expr2 = max(l(i-1,j-1),l(i,j))

Answer Discuss it!

.

Correct answer is :C

Solution :

In Longest common subsequence problem, there are two cases for X[0..i] and Y[0..j]

1) The last characters of two strings match.

The length of lcs is length of lcs of X[0..i-1] and Y[0..j-1]

2) The last characters don't match.

The length of lcs is max of following two lcs values
a) LCS of X[0..i-1] and Y[0..j]

b) LCS of X[0..i] and Y[0..j-1]

Question 10

**A sub-sequence of a given sequence is just the given sequence with some elements (possibly none or all) left out. We are given two sequences X[m] and Y[n] of lengths m and n, respectively, with indexes of X and Y starting from 0.**

The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j) of the form given above, using an array L[M,N], where M = m+1 and N=n+1, such that L[i,j] = l(i,j).

Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i,j)?

A : All elements L should be initialized to 0 for the values of l(i,j) to be properly computed

B : The values of l(i,j) may be computed in a row major order or column major order of L(M,N)

C : The values of l(i,j) cannot be computed in either row major order or column major order of L(M,N)

D : L[p,q] needs to be computed before L[r,s] if either p < r or q < s

Answer Discuss it!

.

Correct answer is :B

Solution :

The value can be computed either in row major or column major order. We can swap the two loops without effecting the output.

Question 11

**Let G=(V, E) be a graph. Define ∈(G) = ∑**_{d} i_{d} × d , where id is the number of vertices of degree d in G. If S and T are two different trees with ∈(S) = ∈(T) , then

A : |S| = 2 |T|

B : |S| = |T| -1

C : |S| = |T|

D : |S| = |T| + 1

Answer Discuss it!

.

Correct answer is :C

Question 12

**Two alternative packages A and B are available for processing a database having 10k records. Package A requires 0.0001n**^{2} time units and package B requires 10nlog_{10}n time units to process n records.What is the smallest value of k for which package B will be preferred over A?

A : 12

B : 10

C : 6

D : 5

Answer Discuss it!

.

Correct answer is :C

Question 13

**Which languages necessarily need heap allocation in the runtime environment?**

A : Those that support recursion

B : Those that use dynamic scoping

C : Those that allow dynamic data structures

D : Those that use global variables

Answer Discuss it!

.

Correct answer is :C

Question 14

**The weight of a sequence a0, a1, ..., an-1 of real numbers is defined as a0+a1/2+...+ aa-1/2n-1. A subsequence of a sequence is obtained by deleting some elements from the sequence, keeping the order of the remaining elements the same. Let X denote the maximum possible weight of a subsequence of a0, a1, ...,an-1 and Y the maximum possible weight of a subsequence of a1, a2, ...,an-1. Then X is equal to**

A : max(Y, a0+Y)

B : max(Y, a0+Y/2)

C : max(Y, a0+2Y)

D : a0+Y/2

Answer Discuss it!

.

Correct answer is :B

Solution :

The concepts involves the Dynamic Programming in Algorithms.

Given:-

X= max weight from the sequence (a0,a1,a2,....an-1) = a0+a1/2+a2/4+....+an-1/2^(n-1)

Y= max weight from the sequence (a1,a2,....an-1) = a1 + a2/2+a3/4+...+ an-1/2^(n-2)

Here we have to find X in terms of Y.

So X = [a1+a2/2+a3/4+...+ an-1/2^(n-2)] = Y

if [a0+a1/2+a2/4+....+an-1/2^(n-1)]<[a1 + a2/2+a3/4+...+ an-1/2^(n-2)]

OR

X = [a0+a1/2+a2/4+....+an-1/2^(n-1)]

Question 15

**Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.**

What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

A : 7

B : 8

C : 9

D : 10

Answer Discuss it!

.

Correct answer is :D

Question 16

**Consider a complete undirected graph with vertex set {0, 1, 2, 3, 4}. Entry Wij in the matrix W below is the weight of the edge {i, j}.**

what is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

A : 7

B : 8

C : 9

D : 10

Answer Discuss it!

.

Correct answer is :B

Question 17

**A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.**

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

A : 46, 42, 34, 52, 23, 33

B : 34, 42, 23, 52, 33, 46

C : 46, 34, 42, 23, 52, 33

D : 42, 46, 33, 23, 34, 52

Answer Discuss it!

.

Correct answer is :C

Question 18

**A hash table of length 10 uses open addressing with hash function h(k)=k mod 10, and linear probing. After inserting 6 values into an empty hash table, the table is as shown below.**

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?

A : 10

B : 20

C : 30

D : 40

Answer Discuss it!

.

Correct answer is :C

Question 1

.

Correct answer is :A

Solution :

Selection sort performs swap only after finding the appropriate position of the current picked element. So there are O(n) swaps performed in selection sort. Because swaps require writing to the array, selection sort is preferable if writing to memory is significantly more expensive than reading.

Question 2

.

Correct answer is :B

Solution :

The possible palindrome generated by above grammar can be of odd length only as there is no rule for S -> ε. For example generated palindromes are aba, aaa, bab, ababa, aaaaa, ..

Question 3

P: Always finds a negative weighted cycle, if one exist s.

Q: Finds whether any negative weighted cycle is reachable from the source.

.

Correct answer is :B

Solution :

Bellman-Ford shortest path algorithm is a single source shortest path algorithm. So it can only find cycles which are reachable from a given source, not any negative weight cycle. Consider a disconnected where a negative weight cycle is not reachable from the source at all. If there is a negative weight cycle, then it will appear in shortest path as the negative weight cycle will always form a shorter path when iterated through the cycle again and again.

Question 4

if n <= 3 then T(n) = n

else T(n) = T(n/3) + cn

Which one of the following represents the time complexity of the algorithm?

(A) θ (n)

(B) θ (n log n)

(C) θ (n^2)

(D) θ (n^2 log n)

.

Correct answer is :A

Solution :

T(n) = cn + T(n/3)

= cn + cn/3 + T(n/9)

= cn + cn/3 + cn/9 + T(n/27)

Taking the sum of infinite GP series. The value of T(n) will be less than this sum.

T(n) <= cn(1/(1-1/3))

<= 3cn/2

or we can say

cn <= T(n) <= 3cn/2

Therefore T(n) = θ(n)

This can also be solved using Master Theorem for solving recurrences.

Question 5

.

Correct answer is :C

Solution :

Open addressing, or closed hashing, is a method of collision resolution in hash tables. With this method a hash collision is resolved by probing, or searching through alternate locations in the array (the probe sequence) until either the target record is found, or an unused array slot is found, which indicates that there is no such key in the table. Well known probe sequences include:

linear probing in which the interval between probes is fixed–often at 1.

quadratic probing in which th

Question 6

.

Correct answer is :D

Solution :

In the sequence (b, e) (e, f) (b, c) (a, c) (f, g) (c, d) given option D, the edge (a, c) of weight 4 comes after (b, c) of weight 3. In Kruskal's Minimum Spanning Tree Algorithm, we first sort all edges, then consider edges in sorted order, so a higher weight edge cannot come before a lower weight edge.

Question 7

.

Correct answer is :B

Solution :

Answer(B) The recursion expression becomes: T(n) = T(n/4) + T(3n/4) + cn After solving the above recursion, we get θ(nLogn)

Question 8

I. There exist parsing algorithms for some programming languages whose complexities are less than O(n

^{3}).

II. A programming language which allows recursion can be implemented with static storage allocation.

III. No L-attributed definition can be evaluated in The framework of bottom-up parsing.

IV. Code improving transformations can be performed at both source language and intermediate code level.

.

Correct answer is :B

Solution :

II is false, in recursion, compiler cannot determine the space needed for recursive calls. III is false.

Question 9

l(i,j) = 0, if either i=0 or j=0

= expr1, if i,j > 0 and X[i-1] = Y[j-1]

= expr2, if i,j > 0 and X[i-1] != Y[j-1]

Which of the following options is correct?

.

Correct answer is :C

Solution :

In Longest common subsequence problem, there are two cases for X[0..i] and Y[0..j]

1) The last characters of two strings match.

The length of lcs is length of lcs of X[0..i-1] and Y[0..j-1]

2) The last characters don't match.

The length of lcs is max of following two lcs values a) LCS of X[0..i-1] and Y[0..j]

b) LCS of X[0..i] and Y[0..j-1]

Question 10

The values of l(i,j) could be obtained by dynamic programming based on the correct recursive definition of l(i,j) of the form given above, using an array L[M,N], where M = m+1 and N=n+1, such that L[i,j] = l(i,j).

Which one of the following statements would be TRUE regarding the dynamic programming solution for the recursive definition of l(i,j)?

.

Correct answer is :B

Solution :

The value can be computed either in row major or column major order. We can swap the two loops without effecting the output.

Question 11

_{d}i

_{d}× d , where id is the number of vertices of degree d in G. If S and T are two different trees with ∈(S) = ∈(T) , then

.

Correct answer is :C

Question 12

^{2}time units and package B requires 10nlog

_{10}n time units to process n records.What is the smallest value of k for which package B will be preferred over A?

.

Correct answer is :C

Question 13

.

Correct answer is :C

Question 14

.

Correct answer is :B

Solution :

The concepts involves the Dynamic Programming in Algorithms.

Given:-

X= max weight from the sequence (a0,a1,a2,....an-1) = a0+a1/2+a2/4+....+an-1/2^(n-1)

Y= max weight from the sequence (a1,a2,....an-1) = a1 + a2/2+a3/4+...+ an-1/2^(n-2)

Here we have to find X in terms of Y.

So X = [a1+a2/2+a3/4+...+ an-1/2^(n-2)] = Y

if [a0+a1/2+a2/4+....+an-1/2^(n-1)]<[a1 + a2/2+a3/4+...+ an-1/2^(n-2)]

OR

X = [a0+a1/2+a2/4+....+an-1/2^(n-1)]

Question 15

What is the minimum possible weight of a spanning tree T in this graph such that vertex 0 is a leaf node in the tree T?

.

Correct answer is :D

Question 16

what is the minimum possible weight of a path P from vertex 1 to vertex 2 in this graph such that P contains at most 3 edges?

.

Correct answer is :B

Question 17

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

.

Correct answer is :C

Question 18

Which one of the following choices gives a possible order in which the key values could have been inserted in the table?

How many different insertion sequences of the key values using the same hash function and linear probing will result in the hash table shown above?

.

Correct answer is :C