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

1

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

2

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

3

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

4

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

5

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

6

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

7

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

8

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

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

In the context of modular software design, which one of the following combinations is desirable?

A

High cohesion and high coupling

B

High cohesion and low coupling

C

Low cohesion and high coupling

D

Low cohesion and low coupling

Open complete paper

9

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

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

Suppose you want to move from 0 to 100 on the number line. In each step, you either move right by a unit distance or you take a shortcut. A shortcut is simply a pre-specified pair of integers \(i, j\) with \(i < j\). Given a shortcut \(i, j\) if you are at position \(i\) on the number line, you may directly move to \(j\). Suppose \(T(k)\) denotes the smallest number of steps needed to move from \(k\) to 100. Suppose further that there is at most 1 shortcut involving any number, and in particular from 9 there is a shortcut to 15. Let \(y\) and \(z\) be such that \(T(9) = 1 + \min(T(y), T(z))\). Then the value of the product \(yz\) is ______.

Check answer

Open complete paper

10

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

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

The head of a newly formed government desires to appoint five of the six selected members P, Q, R, S, T, and U to portfolios of Home, Power, Defense, Telecom, and Finance. U does not want any portfolio if S gets one of the five. R wants either Home or Finance or no portfolio. Q says that if S gets either Power or Telecom, then she must get the other one. T insists on a portfolio if P gets one.
Which is the valid distribution of portfolios?

A

P-Home, Q-Power, R-Defense, S-Telecom, T-Finance

B

R-Home, S-Power, P-Defense, Q-Telecom, T-Finance

C

P-Home, Q-Power, T-Defense, S-Telecom, U-Finance

D

Q-Home, U-Power, T-Defense, R-Telecom, P-Finance

Open complete paper

11

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

Computer Science & Information Technology (CS) 2016 [Session 1]

Let \(a_n\) be the number of \(n\)-bit strings that do NOT contain two consecutive 1s. Which one of the following is the recurrence relation for \(a_n\)?

Check answer

Open complete paper

12

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

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

A message is made up entirely of characters from the set \(X = \{P, Q, R, S, T\}\). The table of probabilities for each of the characters is shown below:

Character	Probability
P	0.22
Q	0.34
R	0.17
S	0.19
T	0.08
Total	1.00

If a message of 100 characters over \(X\) is encoded using Huffman coding, then the expected length of the encoded message in bits is __________.

Check answer

Open complete paper

13

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

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

Assume that multiplying a matrix \(G_1\) of dimension \(p \times q\) with another matrix \(G_2\) of dimension \(q \times r\) requires \(pqr\) scalar multiplications. Computing the product of \(n\) matrices \(G_1G_2G_3 \dots G_n\) can be done by parenthesizing in different ways. Define \(G_{i+1}\) as an explicitly computed pair for a given parenthesization if they are directly multiplied. For example, in the matrix multiplication chain \(G_1G_2G_3G_4G_5G_6\) using parenthesization \((G_1(G_2G_3))(G_4(G_5G_6))\), \(G_2G_3\) and \(G_5G_6\) are the only explicitly computed pairs.
Consider a matrix multiplication chain \(F_1F_2F_3F_4F_5\), where matrices \(F_1, F_2, F_3, F_4\) and \(F_5\) are of dimensions \(2 \times 25, 25 \times 3, 3 \times 16, 16 \times 1\) and \(1 \times 1000\), respectively. In the parenthesization of \(F_1F_2F_3F_4F_5\) that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are

A

\(F_1F_2\) and \(F_3F_4\) only

B

\(F_2F_3\) only

C

\(F_3F_4\) only

D

\(F_1F_2\) and \(F_4F_5\) only

Open complete paper

14

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

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

Consider the weights and values of items listed below. Note that there is only one unit of each item.

Item number	Weight (in Kgs)	Value (in Rupees)
1	10	60
2	7	28
3	4	20
4	2	24

The task is to pick a subset of these items such that their total weight is no more than 11 Kgs and their total value is maximized. Moreover, no item may be split. The total value of items picked by an optimal algorithm is denoted by \( V_{opt} \). A greedy algorithm sorts the items by their value-to-weight ratios in descending order and packs them greedily, starting from the first item in the ordered list. The total value of items picked by the greedy algorithm is denoted by \( V_{greedy} \). The value of \( V_{opt} - V_{greedy} \) is ______.

Check answer

Open complete paper

15

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

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

Consider a sequence of 14 elements: A = [-5, -10, 6, 3, -1, -2, 13, 4, -9, -1, 4, 12, -3, 0]. The subsequence sum \( S(i, j) = \sum_{k=i}^{j} A[k] \). Determine the maximum of \( S(i, j) \), where \( 0 \le i \le j < 14 \). (Divide and conquer approach may be used.)
Answer: ______

Check answer

Open complete paper

16

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

Computer Science & Information Technology (CS) 2021 [Session 1]

Define \( R_n \) to be the maximum amount earned by cutting a rod of length \( n \) meters into one or more pieces of integer length and selling them. For \( i > 0 \), let \( p[i] \) denote the selling price of a rod whose length is \( i \) meters. Consider the array of prices:
\( p[1] = 1, p[2] = 5, p[3] = 8, p[4] = 9, p[5] = 10, p[6] = 17, p[7] = 18 \)
Which of the following statements is/are correct about \( R_7 \)?

Check answer

Open complete paper

17

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

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

Consider the string abbcccddddeee. Each letter in the string must be assigned a binary code satisfying the following properties:
1. For any two letters, the code assigned to one letter must not be a prefix of the code assigned to the other letter.
2. For any two letters of the same frequency, the letter which occurs earlier in the dictionary order is assigned a code whose length is at most the length of the code assigned to the other letter.
Among the set of all binary code assignments which satisfy the above two properties, what is the minimum length of the encoded string?

A

21

B

23

C

25

D

30

Open complete paper

18

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

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

Consider the following recurrence:
\[ f(1) = 1; \\ f(2n) = 2f(n) - 1, \text{ for } n \ge 1; \\ f(2n+1) = 2f(n) + 1, \text{ for } n \ge 1. \] Then, which of the following statements is/are TRUE?

A

\(f(2^n - 1) = 2^n - 1 \)

B

\(f(2^n) = 1 \)

C

\(f(5 \cdot 2^n) = 2^{n+1} + 1 \)

D

\(f(2^n + 1) = 2^n + 1 \)

Check answer

Open complete paper

19

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

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

Let A be an array containing integer values. The distance of A is defined as the minimum number of elements in A that must be replaced with another integer so that the resulting array is sorted in non-decreasing order. The distance of the array [2,5,3,1,4,2,6] is ________

Check answer

Open complete paper

20

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

Computer Science and Information Technology (CS) 2026

Consider a table \( T \), where the elements \( T[i][j], 0 \le i, j \le n \), represent the cost of the optimal solutions of different subproblems of a problem that is being solved using a dynamic programming algorithm. The recursive formulation to compute the table entries is as follows: \[ T[0][k] = T[k][0] = 1 \quad \text{for } k = 0,1,2, ..., n \] \[ T[i][j] = 2T[i - 1][j] + 3T[i][j - 1] \quad \text{for } 1 \le i, j \le n \] Consider the following two algorithms to compute entries of \( T \). Assume that for both the algorithms, for all \( 0 \le i, j \le n \), \( T[i][j] \) has been initialized to 1. Algorithm \( B_1 \): For \( i = 1, 2, ..., n \) For \( j = 1, 2, ..., n \) \( T[i][j] = 2T[i - 1][j] + 3T[i][j - 1] \) Algorithm \( B_2 \): For \( s = 2, 3, ..., 2n \) For \( i = 1, 2, ..., n \) For \( j = 1, 2, ..., n \) If \( (i + j == s) \) \( T[i][j] = 2T[i - 1][j] + 3T[i][j - 1] \) Algorithm \( B_k, k \in \{1,2\} \) is said to be correct if and only if it calculates the correct values of \( T[i][j] \), for all \( 0 \le i, j \le n \), (as per the recursive formulation) at the end of the execution of the algorithm \( B_k \). Which one of the following statements is true?

A

Both algorithms \(B_1 \) and \(B_2 \) are correct

B

Algorithm \(B_1 \) is correct, but algorithm \(B_2 \) is incorrect

C

Algorithm \(B_2 \) is correct, but algorithm \(B_1 \) is incorrect

D

Both algorithms \(B_1 \) and \(B_2 \) are incorrect

Open complete paper