Algorithm analysis: Dynamic Programming

What does dynamic programming do, actually?

• solving recurrence problems with overlapping subproblems

• solving recurrence problems

• making the solution dynamic and flexible

• can only finding short part in graph

Which of these is the main idea of dynamic programming? Check all that applies.

• smaller instances are solved once

• Solutions are recorded in 2D array

• improves the divide and conquer techniques

• final solutions are direct from the input

What does warshall algorithm does? Check all that applies.

• to find another route in a graph in a relation

• does not calculate the distance/weight

• uses binary numbers in the table

Which are not correct about Floyd algorithm

• finding shortest path

• create shortest path

• create transitive closure

• Time efficiency is similar with warshall

The efficiency of Warshall and Floyds are same

• true

• false