Reading
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!