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

DataStructure : Techniques for Designing Algorithms Program List