GATE CS Algorithm Design: Dynamic Programming questions

Consider a table

T

, where the elements

T[i][j], 0 \leq i, j \leq 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: …

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 G_{i+1}

as an explicitly computed pair for a given …

Let

A_{1}, A_{2}, A_{3}

and

A_{4}

be four matrices of dimensions

10 \times 5, 5 \times 20, 20 \times 10

and

10 \times 5

, respectively. The minimum number of scalar multiplications required to find the product

A_{1}A_{2}A_{3}A_{4}

using the basic matrix multiplication method is _________.

The Floyd-Warshall algorithm for all-pair shortest paths computation is based on

Consider two strings

A

= "qpqrr" and

B

= "pqprqrp". 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=

___.

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 \:\text{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)

…

Consider the following recursive C function that takes two arguments. unsigned int foo(unsigned int n, unsigned int r) { if (n>0) return ((n%r) + foo(n/r, r)); else return 0; } What is the return value of the function

\text{foo}

when it is called as

\text{foo(513, 2)}

?

Consider the following recursive C function that takes two arguments. unsigned int foo(unsigned int n, unsigned int r) { if (n>0) return ((n%r) + foo(n/r, r)); else return 0; } What is the return value of the function

\text{foo}

when it is called as

\text{foo(345, 10)}

?

Four Matrices

M_1, M_2, M_3

and

M_4

of dimensions

p \times q, \:\:q \times r, \:\:r \times s

and

s \times t

respectively can be multiplied in several ways with different number of total scalar multiplications. For example when multiplied as

((M_1 \times M_2) \times (M_3 \times M_4))

, the total number of scalar multiplications is …

An algorithm to find the length of the longest monotonically increasing sequence of numbers in an array

A[0:n-1]

is given below. Let

L_i

, denote the length of the longest monotonically increasing sequence starting at index

i

in the array. Initialize

L_{n-1} = 1

. For all

i

such that

0 \leq i \leq n-2

…

What is the value printed by the following C program? #include<stdio.h> int f(int *a, int n) { if (n <= 0) return 0; else if (*a % 2 == 0) return *a+f(a+1, n-1); else return *a - f(a+1, n-1); } int main() { int a[] = {12, 7, 13, 4, 11, 6}; printf("%d", f(a, 6)); return 0; }

The weight of a sequence

a_0,a_1, \dots, a_{n-1}

of real numbers is defined as

a_0+a_1/2+ \dots + 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

a_o,a_1, \dots, a_{n-1}

and …

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 …

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 …

Consider the program below: #include <stdio.h> int fun(int n, int *f_p) { int t, f; if (n <= 1) { *f_p = 1; return 1; } t = fun(n-1, f_p); f = t + *f_p; *f_p = t; return f; } int main() { int x = 15; printf("%d/n", fun(5, &x)); return 0; } The value printed is:

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 positive integer

W

, is there a subset of

S

whose elements sum to

W

? A dynamic program for solving this problem uses a

\text{2-dimensional}

Boolean array,

X

, with

n

rows and

W+1

columns. …