Design and Analysis of algorithms

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:

1. Black box solution for running time of you input few parameters related to the recurrence.
2. Assumptions: All recurrences are of equal size.
3. 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.

1. Divide and conquer:
1. write the base case.
2. Using recursion to solve subproblems of a problem.
3. Combine subproblems
4. Store the results of subproblems in a hashmap and use them to trim other repeating recursive paths. (Dynamic programming)
2. Randomization: Like in quick sort.
1. Decomposition principle:
3. Greedy algorithms.
4. Dynamic programming.

Problems:

Graphs:

n-num of vertices, m-num of edges

Graph partitioning: Cuts of a graph, Minimum cut

Representation:

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.