Programmer Technique
In an algorithm design there is no one 'silver bullet' that is a cure for all computation problems. Different problems require the use of different kinds of techniques. A good programmer uses all these techniques based on the type of problem. Some commonly-used techniques are:
- Divide and conquer.
- Randomized algorithms.
- Greedy algorithms (This is not an algorithm, it is a technique).
- Dynamic programming.
Divide and Conquer
Divide means break the problem into some subproblem, while conquer means recursively solves these subproblems.
Randomized algorithms
An algorithm that uses random numbers to decide what to do next anywhere in its logic is called Randomized Algorithm.
- Monte Carlo
- Cryptography
- Probability Test
Greedy algorithms
A greedy algorithm, as the name suggests,always makes the choice that seems to be the best at that moment. This means that it makes a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution.
- Kruskal MST
- Prim MST
- Djikstra shortest path
- Huffman Coding
Dynamic programming
Dynamic programming approach is similar to divide and conquer in breaking down the problem into smaller and yet smaller possible sub-problems. But unlike, divide and conquer, these sub-problems are not solved independently. Rather, results of these smaller sub-problems are remembered and used for similar or overlapping sub-problems.
In contrast to greedy algorithms, where local optimization is addressed, dynamic algorithms are motivated for an overall optimization of the problem.
- Fibonacci number series
- Knapsack problem
- Tower of Hanoi
- All pair shortest path by Floyd-Warshall
- Shortest path by Dijkstra
- Project scheduling