Techniques for Designing Algorithms
Techniques for Designing Algorithms
Two commonly used techniques for designing algorithms are:
- Divide and conquer approach
- Greedy approach
Divide and conquer is a powerful approach for solving conceptually difficult problems.
Divide and conquer approach requires you to find a way of:
- Breaking the problem into sub problems
- Solving the trivial cases
- Combining the solutions to the sub problems to solve the original problem
Algorithms based on greedy approach are used for solving optimization problems, where you need to maximize profits or minimize costs under a given set of conditions.
Some examples of optimization problems are:
- Finding the shortest distance from an originating city to a set of destination cities, given the distances between the pairs of cities.
- Finding the minimum number of currency notes required for an amount, where an arbitrary number of notes for each denomination are available.
- Selecting items with maximum value from a given set of items, where the total weight of the selected items cannot exceed a given value.
Recursion:
Refers to the technique of defining a process in terms of itself
Is used to solve complex programming problems that are repetitive in nature
Is implemented in a program by using a recursive procedure or function. A recursive procedure or function is a function that invokes itself
Is useful in writing clear, short, and simple programs