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",
}