Resources
Algorithms
- n choose k
- Algorithm Visualization
- Red Black Tree Visualization
- Red Black Tree Visualization
- Matroid - planetmath.org (pdf)
- Matroid
- The following definition of a matroid is my English language interpretation of the definition taken from CLRS, page 437. The hard part for me to understand was the last axiom.
- 3. If $A \in {\cal I}, B \in {\cal I}$, and $|A| < |B|$, then there exists some element $x \in B - A$ such that $A \cup \left\{ x \right\} \in {\cal I}$. We say that M satisfies the exchange property.
- This says that if we have two sets that have only independent elements and one set is larger, there must be an element in the larger set that is independent of the smaller set. If we remember that matroids are an extension of the concept of independence in the context of a matrix, this axiom captures the idea that if we have a set of independent rows, A, and a different set of independent rows, B, and B is larger than A, then there must exist a row from B that is independent of A. Thus, we can take that row and add it to A and A will still be independent.
- Rod cutting code