Skip to content

All mock tests are FREE till 31 December — register to save your progress

Paper 2 CS · UNIT 07 · MOCK TEST

Mock 8 – Greedy & Dynamic Programming

Unit 7: Data Structures and Algorithms · 16 questions · about 19 minutes. Press End Mock any time to see your score and the correct answers.

All 11 topic-wise mocks in this unit

0 / 16 answered 00:00

Q1. The longest common subsequence of {1,2,3,2,4,1,2} and {2,4,3,1,2,1} is

A2,1,2,3 B1,3,2,1 C2,3,2,1 D2,3,1,2,1

Q2. When developing a dynamic programming algorithm, the sequence of steps followed is:
A. Construct an optimal solution from computed information.
B. Recursively define the value of an optimal solution.
C. Characterize the structure of an optimal solution.
D. Compute the value of an optimal solution, typically in a bottom-up fashion.
Choose the correct answer from the options given below:

AB, C, A, D BB, A, C, D CC, B, A, D DC, B, D, A

Q3. Arrange the following steps in the correct order to solve the Knapsack problem using Dynamic Programming.
(A) Define the base case when the capacity is zero or no items are left to consider
(B) Compute the maximum value that can be obtained using items up to the i-th item and a knapsack capacity of W
(C) Identify subproblems and their dependencies based on item weights and values
(D) Initialize a table to store results of subproblems
(E) Iterate through each item and each possible capacity to fill the table
Choose the correct answer from the options given below:

A(C), (D), (A), (E), (B) B(D), (C), (A), (E), (B) C(A), (C), (D), (E), (B) D(D), (A), (C), (E), (B)

Q4. Match List I with List II

List I	List II
A. 8-Queens problem	I. Divide and conquer
B. Closest pair of points	II. Dynamic Programming
C. String edit problem	III. Greedy Method
D. Knapsack problem	IV. Backtracking

AA-I, B-II, C-III, D-IV BA-I, B-IV, C-II, D-III CA-IV, B-I, C-II, D-III DA-II, B-III, C-IV, D-I

Directions (Q91–95): For a knapsack problem, P and W are the profits and weights of a set of 7 items:
P = {9, 5, 2, 7, 6, 16, 9}
W = {2, 5, 6, 11, 1, 9, 3}

Q5. Find the optimal solution of the fractional knapsack problem when the maximum capacity is 15.

A43 B40 C45 D44

Directions (Q91–95): For a knapsack problem, P and W are the profits and weights of a set of 7 items:
P = {9, 5, 2, 7, 6, 16, 9}
W = {2, 5, 6, 11, 1, 9, 3}

Q6. What is the maximum value of the items you can carry if the maximum weight allowed is 25 (fractional knapsack)?

A48.1 B49 C47.9 D40

Directions (Q91–95): For a knapsack problem, P and W are the profits and weights of a set of 7 items:
P = {9, 5, 2, 7, 6, 16, 9}
W = {2, 5, 6, 11, 1, 9, 3}

Q7. If a new item (P = 5, W = 2) is added, giving 8 items, and the capacity is 25, then the time of fractional knapsack in this case is ______

AO(8) BO(64) CO(24) DO(56)

Directions (Q91–95): For a knapsack problem, P and W are the profits and weights of a set of 7 items:
P = {9, 5, 2, 7, 6, 16, 9}
W = {2, 5, 6, 11, 1, 9, 3}

Q8. The most efficient solution to the fractional knapsack problem with maximum capacity 15 is obtained using ___

ADivide and Conquer BDynamic Programming CGreedy Algorithm DBacktracking

Directions (Q91–95): For a knapsack problem, P and W are the profits and weights of a set of 7 items:
P = {9, 5, 2, 7, 6, 16, 9}
W = {2, 5, 6, 11, 1, 9, 3}

Q9. Which of the following statements about the knapsack problem is correct?

A0/1 knapsack can be applied to all kinds of problems, but fractional knapsack only if the problem meets certain conditions. BThere is no difference between the two; they give the same solution for any problem. CWe use the greedy algorithm for 0/1 knapsack and dynamic programming for fractional knapsack. DIn the 0/1 knapsack problem items cannot be divided into smaller portions, while in the fractional knapsack items can be divided in any proportion.

Q10.

Match List I with List II

AA-I, B-II, C-III, D-IV BA-I, B-IV, C-II, D-III CA-IV, B-I, C-II, D-III DA-II, B-III, C-IV, D-I

Directions (Q91–95): For a knapsack problem, the profits and weights of 7 items are P = {9, 5, 2, 7, 6, 16, 9} and W = {2, 5, 6, 11, 1, 9, 3}.

Q11.

What is the maximum value of items you can carry if maximum weight allowed is 25 with a fractional knapsack?

A48.1 B49 C47.9 D40 (P = 5, W = 2)

Directions (Q91–95): For a knapsack problem, the profits and weights of 7 items are P = {9, 5, 2, 7, 6, 16, 9} and W = {2, 5, 6, 11, 1, 9, 3}.

Q12.

If new item is added to the list, total items is 8 and capacity is 25 , then the best-case time of fractional knapsack for this case is _____

AO(8) BO(64) CO(24) DO(56)

Directions (Q91–95): For a knapsack problem, the profits and weights of 7 items are P = {9, 5, 2, 7, 6, 16, 9} and W = {2, 5, 6, 11, 1, 9, 3}.

Q13.

Which of the following statements is correct for a knapsack?

A0/1 knapsack can be applied for all kinds of problems but fractional knapsack can be applied only if the problem meets certain conditions. BThere is no difference between the two. They give the same solution for any problem. CWe use the greedy algorithm for 0 / 1 knapsack and dynamic programming for fractional knapsack. DIn 0/1 knapsack problem, items cannot be divided into smaller portions and in fractional knapsack we can divide the item into required proportions of weight. Directions (96-100) Read the following passage and answer the given questions. Use the following schema of the academic institution relational database: student (rollno, name, degree, year, sex, deptno, advisor) department (deptid, name, hod, phone) professor (empid, name, sex, startyear, deptno, phone) course (courseid cname, credits, deptno) enrollment (rollno, courseid, sem, year, grade) teaching (empid, courseid, sem, year, classroom) prerequisite (precourseid, courseid) deptno is foreign key in the student, professor and course relations referring to deptid of department relation; advisor is a foreign key in the student relation referring to empid of professor relation; hod is a foreign key in the department relation referring to empid of professor relation; rollno is a foreign key in the enrollment relation referring to rollno of student relation; courseid is a foreign key in the enrollment, teaching relations referring to courseid of course relation; empid is a foreign key of the teaching relation referring to empid of professor relation; precourseid and courseid are foreign keys in the prerequisite relation referring to courseid of the course relation;

Q14.

Consider the following steps : S

1 : Characterize the structure of an optimal solution S

2 : Compute the value of an optimal solution in bottom-up fashion Which of the step(s) is/are common to both dynamic programming and greedy algorithms? S

AOnly 1 S BOnly 2 S S CBoth 1 and 2 S S DNeither 1 nor 2

Q15.

Consider two sequences X = ⟨0, 1, 2, 1, 3, 0, 1⟩ and Y = ⟨1, 3, 2, 0, 1, 0⟩. The length of the longest common subsequence of X and Y is

A2 B3 C4 D5

Q16.

Match the following with respect to algorithm paradigms :

A(a) (b) (c) (d) (iv) (i) (iii) (ii) B(a) (b) (c) (d) (iv) (iii) (i) (ii) C(a) (b) (c) (d) (iii) (iv) (ii) (i) D(a) (b) (c) (d) (iv) (iii) (ii) (i)

Next: Mock 9 – Graph Algorithms (Part 1) →