Algorithm Design Techniques - Algorithms - Computer Science & Information Technology Previous Year Questions

1

2007 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2007

Which of the following is the Huffman code for the letters a,b,c,d,e,f?

A

0,10,110,1110,11110,11111

B

11,10,011,010,001,000

C

11,10,01,001,0001,0000

D

110,100,010,000,001,111

Open complete paper

2

2008 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2008

Consider the Quicksort algorithm. Suppose there is a procedure for finding a pivot element which splits the list into two sub-lists each of which contains at least one-fifth of the elements. Let $T(n)$ be the number of comparisons required to sort $n$ elements. Then

A

$T(n) \le 2T(n/5) + n$

B

$T(n) \le T(n/5) + T(4n/5) + n$

C

$T(n) \le 2T(4n/5) + n$

D

$T(n) \le 2T(n/2) + n$

Open complete paper

3

2008 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2008

Statement for Linked Answer Questions 78 and 79:
Let \(x_n\) denote the number of binary strings of length \(n\) that contain no consecutive 0s.
Which of the following recurrences does \(x_n\) satisfy?

A

\(x_n = 2x_{n-1}\)

B

\(x_n = x_{\lfloor n/2 \rfloor} + 1\)

C

\(x_n = x_{\lfloor n/2 \rfloor} + n\)

D

\(x_n = x_{n-1} + x_{n-2}\)

Open complete paper

4

2008 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2008

Statement for Linked Answer Questions 80 and 81:
The subset-sum problem is defined as follows. Given a set of \(n\) positive integers, \(S = \{a_1, a_2, a_3, \dots, a_n\}\), and a positive integer \(W\), is there a subset of \(S\) whose elements sum to \(W\)? A dynamic program for solving this problem uses a 2-dimensional Boolean array, \(X\), with \(n\) rows and \(W+1\) columns. \(X[i, j]\), \(1 \le i \le n\), \(0 \le j \le W\), is TRUE if and only if there is a subset of \(\{a_1, a_2, \dots, a_i\}\) whose elements sum to \(j\).
Which of the following is valid for \(2 \le i \le n\) and \(a_i \le j \le W\)?

A

\(X[i, j] = X[i-1, j] \vee X[i, j-a_i]\)

B

\(X[i, j] = X[i-1, j] \vee X[i-1, j-a_i]\)

C

\(X[i, j] = X[i-1, j] \wedge X[i, j-a_i]\)

D

\(X[i, j] = X[i-1, j] \wedge X[i-1, j-a_i]\)

Open complete paper

5

2008 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2008

Which entry of the array \(X\), if TRUE, implies that there is a subset whose elements sum to \(W\)?

A

\(X[1, W]\)

B

\(X[n, 0]\)

C

\(X[n, W]\)

D

\(X[n-1, n]\)

Open complete paper

6

2009 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2009

The coupling between different modules of a software is categorized as follows :
I. Content coupling
II. Common coupling
III. Control coupling
IV. Stamp coupling
V. Data coupling
Coupling between modules can be ranked in the order of strongest (least desirable) to weakest (most desirable) as follows :

A

I – II – III – IV – V

B

V – IV – III – II – I

C

I – III – V – II – IV

D

IV – II – V – III – I

Open complete paper

7

2009 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2009

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

O(n)

B

O(n log n)

C

O(n²)

D

O(n² log n)

Open complete paper

8

2009 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2009

Which of the following statements are TRUE ?
I. The context diagram should depict the system as a single bubble.
II. External entities should be identified clearly at all levels of DFDs.
III. Control information should not be represented in a DFD.
IV. A data store can be connected either to another data store or to an external entity.

A

II and III

B

II, III and IV

C

I and III

D

I, II and III

Open complete paper

9

2009 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2009

Consider the following statements about the cyclomatic complexity of the control flow graph of a program module. Which of these are TRUE ?
I. The cyclomatic complexity of a module is equal to the maximum number of linearly independent circuits in the graph.
II. The cyclomatic complexity of a module is the number of decisions in the module plus one, where a decision is effectively any conditional statement in the module.
III. The cyclomatic complexity can also be used as a number of linearly independent paths that should be tested during path coverage testing.

A

I and II

B

II and III

C

I and III

D

I, II and III

Open complete paper

10

2009 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2009

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 one 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))

Open complete paper

11

2009 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2009

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 of 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.

Open complete paper

12

2010 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2010

What is the appropriate pairing of items in the two columns listing various activities encountered in a software life cycle?

P. Requirements Capture	1. Module Development and Integration
Q. Design	2. Domain Analysis
R. Implementation	3. Structural and Behavioral Modeling
S. Maintenance	4. Performance Tuning

A

P-3 Q-2 R-4 S-1

B

P-2 Q-3 R-1 S-4

C

P-3 Q-2 R-1 S-4

D

P-2 Q-3 R-4 S-1

Open complete paper

13

2010 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2010

The weight of a sequence a0, a1, ..., a_{n-1} of real numbers is defined as a0 + a1/2 + ... + a_{n-1}/2^{n-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, ..., a_{n-1} and Y the maximum possible weight of a subsequence of a1, a2, ..., a_{n-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

Open complete paper

14

2013 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2013 [Session 3]

The tester now tests the program on all input strings of length five consisting of characters ‘a’, ‘b’, ‘c’, ‘d’ and ‘e’ with duplicates allowed. If the tester carries out this testing with the four test cases given above, how many test cases will be able to capture the flaw?

A

Only one

B

Only two

C

Only three

D

All four

Open complete paper

15

2013 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2013 [Session 3]

Complete the sentence:
Universalism is to particularism as diffuseness is to _________________.

A

specificity

B

neutrality

C

generality

D

adaptation

Open complete paper

16

2013 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2013 [Session 4]

The following figure represents access graphs of two modules M1 and M2. The filled circles represent methods and the unfilled circles represent attributes. If method m is moved to module M2 keeping the attributes where they are, what can we say about the average cohesion and coupling between modules in the system of two modules?

A

There is no change.

B

Average cohesion goes up but coupling is reduced.

C

Average cohesion goes down and coupling also reduces.

D

Average cohesion and coupling increase.

Open complete paper

17

2014 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2014 [Session 2]

Which one of the following is TRUE?

A

The requirements document also describes how the requirements that are listed in the document are implemented efficiently.

B

Consistency and completeness of functional requirements are always achieved in practice.

C

Prototyping is a method of requirements validation.

D

Requirements review is carried out to find the errors in system design.

Open complete paper

18

2014 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2014 [Session 2]

Consider two strings A = "qpqqrr" and B = "pqrqrpq". Let x be the length of the longest common subsequence (not necessarily contiguous) between A and B and let y be the number of such longest common subsequences between A and B. Then x + 10y = ____.

Check answer

Open complete paper

19

2014 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2014 [Session 2]

Suppose P, Q, R, S, T are sorted sequences having lengths 20, 24, 30, 35, 50 respectively. They are to be merged into a single sequence by merging together two sequences at a time. The number of comparisons that will be needed in the worst case by the optimal algorithm for doing this is ____.

Check answer

Open complete paper

20

2014 · Computer Science & Information Technology · Algorithms · Algorithm Design Techniques

Computer Science & Information Technology (CS) 2014 [Session 3]

You have an array of n elements. Suppose you implement quicksort by always choosing the central element of the array as the pivot. Then the tightest upper bound for the worst case performance is

A

O(n^2)

B

O(n log n)

C

Θ(n log n)

D

O(n^3)

Open complete paper