Parallel Algorithm Design Techniques - Parallel Algorithm

What are the different designing techniques of parallel algorithm?

One of the crucial and difficult task is selection of a proper designing technique for a parallel algorithm. More than one solution can be derived for most of the problem of parallel programming. The following are the designing technique for parallel algorithms -

  • Divide and conquer
  • Greedy Method
  • Dynamic Programming
  • Backtracking
  • Branch & Bound
  • Linear Programming

Divide and Conquer Method

The problem is divided into several Sub-problems. The sub-problems are solved and combined together for obtaining a solution for the original problem.

At each level, the steps involved in divide and conquer method are:

  • Divide – The problem is divided into sub-problems.
  • Conquer − The sub-problems are solved recursively.
  • Combine − The solutions of the sub-problems are combined together to get the solution of the original problem.

For the following algorithms, divide and conquer approach is applicable:

  • Binary search
  • Quick sort
  • Merge sort
  • Integer multiplication
  • Matrix inversion
  • Matrix multiplication

Greedy Method

At any moment of time, the best solution is chosen for greedy algorithm of optimizing solution. It an easy method of application for complex problems. The steps that provide the accurate solution for the next step is decided by this method.

It is named greedy as the total program is not considered as a whole when optimal solution is provided for smaller instances. A solution is considered only once by the greedy algorithm.

A group of objects is created by greedy algorithm from the smallest possible component parts. By recursion, a problem is solved where the solution to the specific problem is dependent on the solution of other smaller instance of that particular problem.

Dynamic Programming

An optimization technique under which the problem is divided into smaller sub-problems and solved is Dynamic Programming. An ultimate solution is obtained by combining all the solutions. Solutions can be reused to the sub problems any number of times as desired.

An example of dynamic programming is Recursive algorithm for Fibonacci Series.

Backtracking Algorithm

An optimization technique that solves the combinational problems is known as backtracking algorithm. Both real-life problems and programmatic problems apply this algorithm. Some of the best examples of backtracking algorithm are Eight queen problem, Sudoku puzzle and going through a maze.

A possible solution is derived in backtracking which satisfies all the required conditions. Then is moved to next level. In case the next level does not derive a satisfactory solution then is returned to one level back and starts with a new option.

Branch and Bound

An optimization technique that helps in obtaining a optimal solution to the problem is branch and bound algorithm. From the entire space of solution, the best solution for a given problem is considered. The function bounds that are to be optimized are merged with the values of the latest best solution. The parts of the solution space are identified by the algorithm.

Branch and bound algorithm focus on maintaining a lowest-cost path to a target. The solution once found, can be improved further. In cases of depth-bounded search and depth-first search, branch and bound search and algorithm are implemented.

Linear Programming

An optimization technique where the optimization criterion and the constraints are both linear functions is linear programming. Best outcome is obtained from this technique such as maximum profit, shortest path, or lowest cost.

In linear programming, a set of variables are assigned absolute values for satisfying the set of linear equations and the linear objective function is either maximized or minimized.

Parallel Algorithm Related Tutorials

Parallel Algorithm Related Practice Tests

All rights reserved © 2020 Wisdom IT Services India Pvt. Ltd Protection Status

Parallel Algorithm Topics