These notes and closely review Unit 3 Sections 1 through 3.4.

Quiz questions

Finish those problem sets!

Review quiz questions

We went over the best-case time analysis for mergesort, and decided that with an input of all equal values, mergesort runs in $O(n)$ time, so the best case running time function is $\Theta(n)$.

Why number theoretic algorithms? A look at simple factorization

See Unit notes.

Modular airthmetic

We saw the "integers mod $n$" ($Z_n$) as its own number system, with +, and *. We saw that we have "-" as well, because we saw that every element of $Z_n$ has an "additive inverse", and that gives us subtraction. Finally, we saw that often, but not always, we can find a multiplicative inverse of an element of $Z_n$, which means we can do division. Our next job will be to characterize when this is possible!