Aspire's Library

A Place for Latest Exam wise Questions, Videos, Previous Year Papers,
Study Stuff for MCA Examinations - NIMCET

Previous Year Question (PYQs)

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?





Solution

Both dynamic programming and greedy algorithms use the idea of optimal substructure.

So, characterizing the structure of an optimal solution is common to both.

Therefore, $S_1$ is common.

But computing the value of an optimal solution in bottom-up fashion is mainly a dynamic programming approach.

It is not a necessary step in greedy algorithms.

So, $S_2$ is not common.


Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More

Online Test Series,
Information About Examination,
Syllabus, Notification
and More.

Click Here to
View More
Ask Your Question or Put Your Review.

loading...