Hello! I’m excited to teach for you 😊 Ways to reach me:

  • Send me an email at maxov@
  • If you have an administrative question, send it to cs170@ (it is much faster and easier for me and the other head TAs to answer from that email)
  • Pop into my office hours Mondays, 10am-12pm in Soda 411!
  • Feel free to let me know about anything else using this completely anonymous feedback form!
  • Please fill out the welcome form!

Morals

Here are some quick summaries of what I think are important points I made in discussion. You should also look at the worksheets for context.

Section 2 - September 5, 2019

  • The Master Theorem is very important for solving relations of the form $T(n) = a T\left(\frac{n}{b}\right) + \mathcal{O}(n^d)$.
  • For something like $T(n) = 2T(\sqrt{n}) + 3$ where the Master Theorem doesn’t work, it helps to restrict to a subset of values for which we can analyze behavior easier. For example, here whenever I see $T(\sqrt{n})$ I always ‘smell’ $2^{\left(2^k\right)}$ nearby, because $\sqrt{2^{\left(2^k\right)}} = 2^{\left(2^{k-1}\right)}$
  • The three cases of the Master Theorem are actually ordered. Non-rigorously, $\mathcal{O}(n^d) > \mathcal{O}(n^{\log_b a} \log n) > \mathcal{O}(n^{\log_b a})$. So as $d$ gets larger, so does the eventual bound on $T(n)$
  • It’s a very common technique for us to split an array into two halves when doing divide and conquer.
    • Often, this results in the recurrence \(T(n) = \underbrace{2 T(n/2)}_\text{(divide)} + \underbrace{\mathcal{O}(n)}_\text{(conquer)}\) giving a runtime of $\mathcal{O}(n \log n)$.
    • Also, the “conquer” step in divide and conquer may be nontrivial. For example, for #2 this ended up still solving some maximization problem.
  • The key trick about understanding/visualizing complex numbers on the unit circle is to understand that they are of the form $e^{2\pi i \frac{p}{q}}$, where $p/q$ is just some fraction that says how far we go around the circle. Then multiplying two numbers like these is adding the fractions together. Adding two numbers like these doesn’t correspond to adding the fractions, it actually corresponds to adding the two complex numbers as if they were 2D vectors. And if we have a fraction like $13/10$, then that “wraps around” and becomes $3/10$ instead.
    • We will be using complex numbers for FFT, and it’s important to see how we take square roots of complex numbers. Each complex number has two square roots. On the unit circle if we go $p/q$ of the way round, these are given by $p/2q$ and $p/2q + 1/2$.

Section 1 - August 29, 2019

  • We use asymptotics like $\mathcal{O}$ in this class to describe long-term growth of our algorithms.
  • To formally prove $f = \mathcal{O}(g)$, you need to show that for some constant $c$ and large enough $n$, $f(n) \leq c \cdot g(n)$.
  • The limit rules for $\mathcal{O}$ are rules, not definitions. For example, even though $x(sin x + 1) = O(x)$ (see here for a visual depiction), attempting to evaluate $\underset{x \to \infty}{\lim} \frac{x(sin x + 1)}{x}$ will result in the limit not existing (because $sin x$ oscillates).
  • But perhaps more important than $\mathcal{O}$ definitions and rules are the properties:
    • $\mathcal{O}$ only cares about leading terms in a summation. For example, $n^2 + n^3 + 2^n = \Theta(2^n)$.
    • Each polynomial degree is in its own class, ordered by degree. For example, $n^2 \neq \Theta(n^3)$ but $n^2 = \mathcal{O}(n^3)$
    • Constants grow less than logarithms, grow less than polynomials, grow less than exponential
    • Usually whenever you multiply two functions together, that produces an entirely new class. For example, $n^2 \log n$ grows strictly more than $n^2$ or $\log n$. But $n^3$ grows more than $n^2 \log n$.

  • I spent a little bit of time showing part of correctness for $\text{euclid-gcd}(a, b)$. Basically, we induct on the size of the second argument $b$ with the following statement:

    \[P(k) \colon \text{``\text{euclid-gcd}(a, b) behaves correctly if b = k''}\]

    Then I showed how based on the recursive definition, $\text{euclid-gcd}(a, b)$ will either call:

    1. If $a = b$, $\text{euclid-gcd}(0, a)$ (going to the base case)
    2. If $a < b$, $\text{euclid-gcd}(b \ (\textbf{mod } a ), a)$. But notice $a < b = k$, so we can use strong induction so that $P(k-1)$ kicks in.

    This is by no means all you need to do (you still need to show that the answer $\text{euclid-gcd}(a, b)$ returns is correct in both these cases, and also the base case), but the important point is that the input size is always decreasing, so we can still make an inductive argument using a $P(k)$. It just may be difficult to come up with a relevant $P(k)$ depending on the situation.