Opening practice - continue from last class:

Try using Floyd's algorithm to find the all pairs shortest paths for this graph (credit to Susan), and create a set of Path matrices as well. Finally, use the Path matrix to trace through the shortest path from A → E.

                                          **Divide and Conquer vs. Dynamic Programming**
Situation Divide and Conquer Dynamic Programming
Finding subproblems Systematically divides in the same way Considers multiple ways to divide and chooses the best
Subproblem occurrences Subproblems are unique Recurring subproblems
Run-time improvement Polynomial time problems —> $nlogn$ or faster Exponential time problems → polynomial time problems
Priority Running time Correctness (finding optimal solution)
Subproblem size Subproblems are ~50% smaller than original Can vary - since we're considering all possible correct solutions, we can get very large subproblems

If helpful, some additional references:

https://www.tutorialspoint.com/automata_theory/context_free_grammar_introduction.htm

https://www.tutorialspoint.com/automata_theory/chomsky_normal_form.htm