Time Left - 10:00 mins
GATE CS 2018 - Algorithms Quiz 7 (Dynamic Programming)
Attempt now to get your rank among 541 students!
Question 1
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; denote the length of the longest monotonically increasing sequence starting at index i in the array.
Initialize Ln-1 = 1.
For all i such that 0 ≤ i ≤ n – 2
Finally the length of the longest monotonically increasing sequence is Max (L0, L1,……., Ln-1).
Which of the following statements is TRUE?
A[0: n - 1] is given below.
Let L; denote the length of the longest monotonically increasing sequence starting at index i in the array.
Initialize Ln-1 = 1.
For all i such that 0 ≤ i ≤ n – 2
Finally the length of the longest monotonically increasing sequence is Max (L0, L1,……., Ln-1).
Which of the following statements is TRUE?
Question 2
What will be the length of LCS, when input strings 123456 and 174869 are there in time complexity algorithm?
Question 3
The subset–sum problem is defined as follows. Given a set of n positive integers, S = {a1, a2, a3 ………, an}, and a positive integer W, is there a subset of S whose elements sum to TV? 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 ≤ i ≤ n, 0 ≤ j W, is TRUE if and only if there is a subset of {a1, a2, ………, a;} whose elements sum to).
Which of the following is valid for 2 ≤ i ≤ n and a1 ≤ j ≤ W?
Which of the following is valid for 2 ≤ i ≤ n and a1 ≤ j ≤ W?
Question 4
Given two arrays of numbers a1, …,an and b1,…,bn where each number is 0 or 1, the fastest algorithm to find the largest span (i, j) such that ai + a i+1 + ….+ aj = bi + bi+1 + …+bj, or report that there is not such span
Question 5
In the following C function, let n ≥ m.
int gcd(n,m)
{
if (n%m ==0) return m;
n = n%m;
return gcd(m,n);
}
How many recursive calls are made by this function?
int gcd(n,m)
{
if (n%m ==0) return m;
n = n%m;
return gcd(m,n);
}
How many recursive calls are made by this function?
- 541 attempts
- 6 upvotes
- 6 comments
Tags :
GATE & PSU CSAlgorithmsJul 5GATE & PSU CS
