The most important principle to be an algorithm designer is not to be content.
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.
n-num of vertices, m-num of edges
Graph partitioning: Cuts of a graph, Minimum cut
- 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.
arcs – Directed edges, ordered pair.