0.4. Math Background¶
0.4.1. Math Background¶
0.4.1.1. Set Notation¶
Set: A collection of distinguishable members. No concept of duplicates, no concept of order.Be familiar with the usual stuff (union intersection, membership, subset, set size.Powerset: All subsets of a set (including the set itself, and the empty set): \(2^S\) if there are \(S\) elements in the set.Bag: Elements are distinguishable even with same value, but there is no concept of order.Sequence: Distinguishable elements in some order (can have duplicates).
0.4.1.2. Set Relations¶
A relation R over set S is a set of ordered pairs from S.
\(R\) is reflexive if \(aRa\) for all \(a \in \mathbf{S}\).
\(R\) is irreflexive if \(aRa\) is not true for all \(a \in \mathbf{S}\).
\(R\) is symmetric if whenever \(aRb\), then \(bRa\), for all \(a, b \in \mathbf{S}\).
\(R\) is antisymmetric if whenever \(aRb\) and \(bRa\), then \(a = b\), for all \(a, b \in \mathbf{S}\).
\(R\) is transitive if whenever \(aRb\) and \(bRc\), then \(aRc\), for all \(a, b, c \in \mathbf{S}\).
0.4.1.3. Equivalence Relations¶
R is an equivalence relation on set S if it is reflexive, symmetric, and transitive.An equivalence relation can be used to partition a set into equivalence classes.A partition of a set \(\mathbf{S}\) is a collection of subsets that are disjoint from each other and whose union is \(\mathbf{S}\).Example: Modulus defines an equivalence relation.
0.4.1.4. Total vs. Partial Order¶
A binary relation is called a partial order if it is antisymmetric and transitive.If the relation is reflexive, it is called a non-strict partial order.If the relation is irreflexive, it is called a strict partial order.If every pair of distinct elements in a partial order are comparable, then the order is called a total order.\(<\) and \(\leq\) are total orders. Subset is a partial order.
0.4.1.5. Miscellaneous Notation¶
Factorial functionA permutation of a sequence \(\mathbf{S}\) is simply the members of \(\mathbf{S}\) arranged in some order. For \(|S|\) elements, there are \(|S|!\) permutations.Mod function: Returns the remainder of an integer division. Sometimes written \(n \bmod m\) in mathematical expressions, the syntax in many programming languages isn % m.
0.4.1.6. Logarithms¶
To store codes for \(n\) objects required \(\log n\) bits. \(n\) bits can represent \(2^n\) objectsYou can cut \(n\) objects in half \(\log n\) times\(\log (nm) = \log n + \log m\).\(\log (n/m) = \log n - \log m\).\(\log (n^r) = r \log n\).\(\log_a n = \log_b n / \log_b a\).\(n = 2^{\log_2 n}\)
0.4.1.7. Summations and Recurrences¶
\[\begin{split}\Huge \sum_{i = 1}^{n} i =& \Huge \frac{n (n+1)}{2} \\ \Huge \sum_{i = 1}^{n} \frac{1}{2^i} =& \Huge 1 - \frac{1}{2^n} \\ \Huge \sum_{i = 0}^{n} 2^i =& \Huge 2^{n+1} - 1\end{split}\]Factorial:\(n! = (n-1)! \cdot n\ \mbox{for}\ n>1; \quad 1! = 0! = 1\).
0.4.1.8. Induction Proofs¶
We use these for some proofs (of space requirements or algorithmic cost).Hopefully you are familiar with these from a Discrete Math course.If not, study the module on this.Induction and Recursion are nearly identical.The recursive call on a smaller input is exactly the same as assuming the induction hypothesis to be true for \(k < n\).
0.4.1.9. Estimation Techniques¶
Known as “back of the envelope” or “back of the napkin” calculation1. Determine the major parameters that affect the problem.2. Define an equation that relates the parameters to the problem.3. Select values for the parameters, and apply the equation to yield an estimated solution.
0.4.1.10. Estimation Example¶
How many library bookcases does it take to store books totaling one million pages?Estimate- Pages/inch- Feet/shelf- Shelves/bookcase
