8

We generally talk about paradigms of programming as functional, procedural, object oriented, imperative etc but what should I reply when I am asked the paradigms of algorithms?

For example are Travelling Salesman Problem, Dijkstra Shortest Path Algorithm, Euclid GCD Algorithm, Binary search, Kruskal's Minimum Spanning Tree, Tower of Hanoi algorithmic paradigms? Or perhaps the paradigms are the data structures I would use to design these algorithms?

9

Algorithmic paradigms are:

General approaches to the construction of efficient solutions to problems

Any basic, commonly used approach in designing algorithms could be considered an algorithmic paradigm:

Divide and Conquer

Idea: Divide problem instance into smaller sub-instances of the same problem, solve these recursively, and then put solutions together to a solution of the given instance.

Examples: Mergesort, Quicksort, Strassen’s algorithm, FFT.

Greedy Algorithms

Idea: Find solution by always making the choice that looks optimal at the moment — don’t look ahead, never go back.

Examples: Prim’s algorithm, Kruskal’s algorithm.

Dynamic Programming

Idea: Turn recursion upside down.

Example: Floyd-Warshall algorithm for the all pairs shortest path problem.

The word paradigm does translate to example, but that's not how it's used in a scientific context. Your examples are all examples of algorithms (except the travelling salesman problem, which is a NP-hard problem), none of which is trivial enough to be considered an algorithmic paradigm.

  • I've never seen someone define DP in such a simple way. Thank you. – MT. Jul 7 '17 at 6:37
2

Common design Algorithmic Paradigms:

  • Divide and conquer : Recursively breaking down a problem into two or more sub-problems of the same (or related) type.
  • Dynamic programming : breaking it down into a collection of simpler subproblems. Example: Tower of Hanoi puzzle
  • Greedy algorithm : the problem solving heuristic of making the locally optimal choice at each stage. Example: traveling salesman problem
  • Backtracking : is a general algorithm for finding all (or some) solutions to some computational problems Example: Sudoku puzzle solved by backtracking.
  • Brute Force : a very general problem-solving technique that consists of systematically enumerating all possible candidates for the solution and checking whether each candidate satisfies the problem's statement.

You can find number of example on geeksforgeeks

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.