Randomized Algorithms

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

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

Decision Trees

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

Trees

for a red-black tree, try keeping track of $b(x)$, which is the black height, and $d(x)$, which is the number of descendants at node $x$. When you’re trying to prove the upper bound of height, you might use the inductive hypothesis that $d(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) \leq 2b(x)$, because you can’t have two red nodes in a row.

Hashing

You want to show that

where $h$ is randomly selected. You can imagine $X$ as a random variable of parameters, and $f(X)$ as being $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 $X$ WILL create a collision.

Graph algorithms, generally

Runtime analysis

In general, search algorithms take $O(m + n)$ if they touch the vertices and the edges. In a connected graph, we have $O(m)$. We add the $n$ 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

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

Cycles, trees, etc

• Odd cycles can’t be colored with two colors

• Trees are fully connected but have no cycles

• bipartite graphs are connected across the sides but have no edges that go between same-side nodes

Timing

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.

Contradiction

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

1. $d[z] = d(s, z)$

2. $d(s, z) \leq d(s, u)$

3. $d(s, u) \leq d[u]$ (the main claim of contradiction)

4. therefore, $d[z] \leq d[u]$

5. Therefore, if we picked $u$, then it must be the case that $z$ is marked as done.

6. If $z$ is done, then it would have updated its neighbor $z’$ such that $d[z’] = \min(d[z’], d[z] + w(z, z’))$

7. We are in the shortest path already, so $d[z’] = d[z] + w(z, z’) = d(s, z')$. As such, $z’$ 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

2. Try to find good moves now. This typically involves using a $\max$ operator. This is not a greedy algorithm, because it often requires you to try many things out

3. Think carefully about the base case. If you are doing something like $\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

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

2. An arbitrary cut in a graph that has an MST will cut one edge of the MST.

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