The most important principle to be an algorithm designer is not to be content.

Asymptotic analysis:

O

Omega

Theta

**The master method** for analyzing the running time of divide and conquer algorithms:

- Black box solution for running time of you input few parameters related to the recurrence.
- Assumptions: All recurrences are of equal size.

n- original problem size

a- number of recurrences called in each instance, rate at which subproblems proliferate. (Evil)

b- The factor by which the input size is divided for calling recurrences.

d- Polynomial exponent of the remaining work needed to merge solutions for the final solution.

b^d – Rate of work shrinkage per subproblem. (good)

Case 1; Same work at each level.

Case 2: More work at the root level.

Case 3: More work at leaf level.

**Algorithm Design paradigms:**

- Divide and conquer:
- write the base case.
- Using recursion to solve subproblems of a problem.
- Combine subproblems
- Store the results of subproblems in a hashmap and use them to trim other repeating recursive paths. (Dynamic programming)

- Randomization: Like in quick sort.
- Decomposition principle:

- Greedy algorithms.
- Dynamic programming.

Problems:

Graphs:

n-num of vertices, m-num of edges

Graph partitioning: Cuts of a graph, Minimum cut

Representation:

- Adjacency matrix. O(n^2)
- Adjacency lists. O(n+m)

**Strongly connected components**: Regions where you can go from any node A to any node B in the directed graph.

**Kosaraju’s 2-pass strongly connected components algorithm**:

One of the smartest and beautiful algorithms.

**The structure of internet**:

Further reading: Networks, crowds and markets.

Glossary:

arcs – Directed edges, ordered pair.