Summary of selected chapters:

# Chapter 3

- is a sandwich bound ( = )
- is a tight upperbound ( ≤ )
- is a tight lowerbound ( ≥ )
- is a loose upperbound ( )
- is a loose lowerbound ( )

e.g. but , and ,

# Chapter 4

How to prove an recurrence formula?

- Substitution method: Guess the anser and proof it by mathematical induction
- Recursion tree: Build a tree with the nodes denoting the fixed cost and children denotes recurred functions. Then sum up all nodes after the tree is complete
- Using master theorem: For solving

Master theorem: Let where and . The term in the formula can also be and . is defined on non-negative integers. Then,

- If then
- If then
- If and then

Interpretation of the master theorem: The recursion gives . Thus if the recursion part dominates, the solution is this. But if the part dominates, the result is as . If both parts weigh equally, both appears in the result. The proof is in section 4.4.

# Chapter 5

## Calculating probability using indicator variable

Let be an indicator (0 or 1) of event happened. Then the expected value of equals to the probability of .

Example: To interview n random persion in sequential order, how many times we see the best-candidate-so-far? If we are interviewing the -th persion, it is the best so far in probability of . Defining to be the indicator of best-so-far, the count satisfies . Indeed, .

## Birthday paradox

In bins and balls, each ball falls in a bin randomly. Find the probability that no bin contains ≥2 balls.

For , the probability is and the probability of not is . For , the probability of not is (first ball second ball third ball)

Thus for general (), it is . In case , we have thus

For probability of , what is the marginal ?

Solving gives , then

## Bibliographic data

```
@book{
title = "Introduction to Algorithms",
edition = "2nd",
author = "Thomas H. Cormen and Charles E. Leiserson and Ronald L. Rivest and Clifford Stein",
publisher = "MIT Press",
year = "2002",
}
```