Chapter 8 (Dynamic Programming)

Question 1

Warshalls Alg.

Answer 1

Purpose: Warshalls alg is a dynamic programming algorithm that solves for the transitive closures of a directed graph, meaning that it finds all possible paths between every pair of vertices in the graph.

Question 2

Transitive Closure

Answer 2

def: A transitive closure means there is a path between any two nodes, i.e, if one node is reachable to another via any possible path.

Question 3

True or False: Floyd algorithm is the boolean version of Warshalls algorithm

Answer 3

False.

Its the opposite. Warshalls alg is the boolean version of Floyds alg, where 1 means node j is reachable from node i, and 0 means node j is not reachable from node i

Question 4

Floyds alg.

Answer 4

Purpose: In a weighted digraph, find the shortest path between every pair of vertices.

(essentially the same as warshalls but with a slightly different recurrence relation)

Question 5

Longest common subsequence (LCS)