Time Left - 10:00 mins
GATE 2020 : Algorithms Quiz 7
Attempt now to get your rank among 632 students!
Question 1
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?
Question 2
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 3
In a 0/1 Knapsack Problem, what is the amount of time taken to create the memory table and determine the optimal solution respectively, for K number of objects and T as the capacity of Knapsack?
Question 4
Assume that multiplying a matrix 
of dimension 
with another matrix 
of dimension 
requires scalar multiplications. Computing the product of 
matrices 
can be done by parenthesizing in different ways. Define 
as an explicitly computed pair for a given parathesization if they are directly multiplied. For example, in the matrix multiplication chain 
using parenthesization 
and 
are the only explicitly computed pairs.
Consider a matrix multiplication chain
where matrices 
and 
are of dimensions 
and 
respectively. In the parenthesization of 
that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are
of dimension with another matrix of dimension requires scalar multiplications. Computing the product of matrices can be done by parenthesizing in different ways. Define as an explicitly computed pair for a given parathesization if they are directly multiplied. For example, in the matrix multiplication chain using parenthesization and are the only explicitly computed pairs. Consider a matrix multiplication chain
where matrices and are of dimensions and respectively. In the parenthesization of that minimizes the total number of scalar multiplications, the explicitly computed pairs is/are Question 5
Consider the following graph.
Assume starting vertex is A. What is the cost of optimal tour by travelling salesperson using the dynamic programming?
Assume starting vertex is A. What is the cost of optimal tour by travelling salesperson using the dynamic programming?
Question 6
We are given 9 tasks T1, T2.... T9. The execution of each task requires one unit of time.
We can execute one task at a time.
Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the dith unit of time.
We can execute one task at a time.
Each task Ti has a profit Pi and a deadline di Profit Pi is earned if the task is completed before the end of the dith unit of time.
|
Task |
T1 |
T2 |
T3 |
T4 |
T5 |
T6 |
T7 |
T8 |
T9 |
|
Profit |
15 |
20 |
30 |
18 |
18 |
10 |
23 |
16 |
25 |
|
Deadline |
7 |
2 |
5 |
3 |
4 |
5 |
2 |
7 |
3 |
What is the maximum profit earned?
- 632 attempts
- 7 upvotes
- 4 comments
Tags :
GATE & PSU CSAlgorithmsJun 22GATE & PSU CS
