Randomized Algorithms

Try representing success as a geometric random variable with some probability pp. The expected runtime is therefore 1/p1/p

Remember: you want E[T]E[T], not T(E[])T(E[])

Decision Trees

Remember the tips on constructing a decision tree. Also, Stirling’s approximation can be your friend here


for a red-black tree, try keeping track of b(x)b(x), which is the black height, and d(x)d(x), which is the number of descendants at node xx. When you’re trying to prove the upper bound of height, you might use the inductive hypothesis that d(x)2b(x)1d(x) \geq 2^{b(x)} - 1, which yields the correct inductive step

You finish the height proof by taking the log of both sides and using the fact taht h(x)2b(x)h(x) \leq 2b(x), because you can’t have two red nodes in a row.


You want to show that

P(h(i)=h(j))1nP(h(i) = h(j)) \leq \frac{1}{n}

where hh is randomly selected. You can imagine XX as a random variable of parameters, and f(X)f(X) as being 1{hX(i)=hX(j)}1\{h_X(i) = h_X(j)\}. So, essentially given the worst possible adversarial example, the chance of collision is still essentially random. It doesn’t mean that there is no collision; in fact, certain selections of XX WILL create a collision.

Graph algorithms, generally

Runtime analysis

In general, search algorithms take O(m+n)O(m + n) if they touch the vertices and the edges. In a connected graph, we have O(m)O(m). We add the nn to account for cases where you have more vertices than edges, which can happen. Intuitively, you “touch” a vertex on your way to another vertex. If you have to start at a new vertex, you don’t traverse an edge but you should still count this starting as contributing to the complexity.


Induction is a popular choice for proving things. You might build things up, which is a common way of doing things.

Cycles, trees, etc


Remember that if a node finishes after another node in the same connected component, then that second node must be a descendant of the first node.


In djikstra’s algorithm, we showed that when a vertex is marked done, d[v]=d(s,v)d[v] = d(s, v). We show this by contradiction. We propose that zz is the last vertex such that d[z]=d(s,z)d[z] = d(s, z). More specifically, let’s consider the shortest path.

  1. d[z]=d(s,z)d[z] = d(s, z)
  1. d(s,z)d(s,u)d(s, z) \leq d(s, u)
  1. d(s,u)d[u]d(s, u) \leq d[u] (the main claim of contradiction)
  1. therefore, d[z]d[u]d[z] \leq d[u]
  1. Therefore, if we picked uu, then it must be the case that zz is marked as done.
  1. If zz is done, then it would have updated its neighbor zz’ such that d[z]=min(d[z],d[z]+w(z,z))d[z’] = \min(d[z’], d[z] + w(z, z’))
  1. We are in the shortest path already, so d[z]=d[z]+w(z,z)=d(s,z)d[z’] = d[z] + w(z, z’) = d(s, z'). As such, zz’ has the equality, and it contradicts our original assumption.

Dynamic Programming

The proof is typically the root of your work, because you want to essentially create an inductive definition. So proving it is often trivial.

Here are some DP tricks

  1. If you are given limited resources, you should consider creating a subproblem that has even more limited resources. For example, you might have a knapsack with a lower limit, etc
  1. Try to find good moves now. This typically involves using a max\max operator. This is not a greedy algorithm, because it often requires you to try many things out
  1. Think carefully about the base case. If you are doing something like maxA[iq]\max A[i - q], if you provide a nonsensical base case, the whole thing will collapse

Greedy Algorithms

The proof is typically the hardest part. I like to think of it as a two-fence system, where you want to show that you can swap out the current optimal choice with the greedy choice and it still makes sense

Start with the greedy and optimal agreeing up to this time step

  1. First fence is some kind of bound on what the optimal algorithm can choose, because the greedy algorithm typically maximizes something
  1. Second fence is some kind of bound on optimality

If you did it correctly, you will end up with some sort of “soft” area in which you can switch things around until you get to the greedy choice

Example: picking the most events in a time block. The greedy algorithm picks the next viable activity with the smallest finish time. Therefore, the optimal algorithm can’t pick an activity with a smaller finish time. By definition, we can just swap out the greedy algorithm’s choice, as it doesn’t overlap (it just makes a larger gap). In this example, the first fence is that the greedy algorithm’s choice fits inside the optimal algorithm’s choice. The second fence is that we make an equivalent swap so optimality is kept.

Graph cuts

To prove facts about MST, use these facts

  1. Trees are connected
  1. An arbitrary cut in a graph that has an MST will cut one edge of the MST.
  1. You can switch out any edge that spans the cut for this one MST edge, which means that the MST edge must be the light edge

To prove facts about flow, use these facts

  1. Maximum flow is equivalent to minimum cut