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

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

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.

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.

Miscellaneous Notation

Factorial function
A 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 is n % m.

Logarithms

To store codes for \(n\) objects required \(\log n\)
bits. \(n\) bits can represent \(2^n\) objects
You 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}\)

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

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

Estimation Techniques

Known as “back of the envelope” or “back of the napkin” calculation

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

Estimation Example

How many library bookcases does it take to store books totaling one million pages?

Estimate

- Pages/inch
- Feet/shelf
- Shelves/bookcase