Skip to content

14.md

Latest commit

 

History

History
47 lines (27 loc) · 1.38 KB

14.md

File metadata and controls

47 lines (27 loc) · 1.38 KB
title
TODO

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

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).

Warshall's Algorithm

Main Idea: A path exists between $i$ and $j$ iif:

  • There's an edge from i to j; or
  • There's a path from $i$ to $j$ going through intermediate verticies from from set ??? TODO
  • There's a path TODO

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.

Floyd's Algorithm

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)

  • Difference is we also want to find the minimum (???)