Time Left - 15:00 mins

GATE 2022: Algorithms Quiz-7

Attempt now to get your rank among 338 students!

Question 1

Consider the following sequence of elements.

Find the maximum sum of contiguous subsequence of a list S.

Question 2

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?

Question 3

Which of the following algorithms solves the all pair shortest path problem?

Question 4

Match the pairs in the following:

Question 5

Consider a sequence of 10 elements:

S = [-4, 6, -2, 3, -9,  8, -1, -7, 5]. The subsequence sum B (i, j) = . Determine the maximum of B (i. j), where 0 ≤ i < j.

Question 6

Consider the travelling salesman problem applied over a network of cites having 6 cites depicted though a graph. If we use dynamic programming approach, then the number of unique subproblems are _______.
  • 338 attempts
  • 0 upvotes
  • 0 comments
Aug 11GATE & PSU CS