TODO ??? (MUST CONSULT SLIDES FOR MISSING CONTENT)
We found something about the optimal binary search tree.
TODO Copy OptimalBST Pseudocode from slides.
Time Efficiency: O(n^3), but can be reduced to O(n^2) by using monoticity.
TODO What about monotonicity?
Space Efficiency: TODO
Transitive Closure: Representation of a directed graph with n vertices, as a n \times n boolean matrix where a 1 at (i,j) means there’s a nontrivial path from i \to j.
Nontrivial: Basically, if there is a path from i \to j (doesn’t need to be direct, can route through other nodes).
To do this algorithmically, we must do dynamic programming (grow the answer little-by-little).
Main Idea: A path exists between i and j iif:
TODO ???
TODO ???
TODO Matrix generation
(We use the adjacency matrix to do Washall’s algorithm. It’s something about intersections.)
TODO Copy pseudocode from the slides.
Problem: Find shortest path between each pair of verticies in a weighted digraph.
This ends up actually being pretty similar to Warshalls (using increasing subsets of vertices allowed as intermediate)