ISCP 04 Tuesday slot 1 (09:00 - 11:00) CSE A&C

In dynamic programming, the technique of storing the previously calculated values is called ___________

• Saving value property
• Storing value property
• Memoization
• Mapping

The following sequence is a fibonacci sequence: 0, 1, 1, 2, 3, 5, 8, 13, 21,….. Which technique can be used to get the nth fibonacci term?

• Recursion
• Dynamic programming
• single for loop
• Recursion, Dynamic Programming, For loops

Find the length of the longest increasing subsequence for the given sequence: {-10, 24, -9, 35, -21, 55, -41, 76, 84}

• 5
• 4
• 3
• 6

What is the worst case for linear search?

• O(nlogn)
• O(logn)
• O(n)
• O(1)

Longest increasing subsequence problem can be optimally solved by

• Greedy method
• Divide & conquer
• Dynamic programming
• None of these

Given items as {value, weight} pairs {{60,20},{50,25},{20,5}}. The capacity of the knapsack=40. Find the maximum value output assuming items to be divisible and non-divisible respectively.

• 100, 80
• 110, 80
• 130, 110
• 110, 70

Consider the below table for Jobs given with profit and deadline. Job J1 J2 J3 J4 J5 J6 J7 J8 J9 Profit 20 25 35 23 23 15 28 21 30 Deadline 7 2 5 3 4 5 2 7 3 Find the maximum profit earned?

• 185
• 182
• 170
• None

The time and space compexitites of longest common subsequence problem of two strings with lengths m, n respectively using dynamic programming?

• O(m! * n!), O(1)
• O(m**2), O(n**2)
• O(m * n), O(m * n)
• O(2**m), O(1)

You are given a rod of length 5 and the prices of each length are as follows: length price 1 2 2 5 3 6 4 9 5 9 What is the maximum value that you can get after cutting the rod and selling the pieces?

• 10
• 11
• 12
• 13

You are given a knapsack that can carry a maximum weight of 60. There are 4 items with weights {20, 30, 40, 70} and values {70, 80, 90, 200}. What is the maximum value of the items you can carry using the knapsack?

• 160
• 200
• 170
• 90