Algorithmic Paradigms – Understanding Key Concepts

algorithmsparadigmsterminology

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?

Best Answer

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.

Related Solutions

Object-Oriented Paradigms – Best Practices for UI Programming

I'm not normally a proponent of OOP, but I would say that GUI programming presents some of the best opportunities to use the strong points of OOP. Implementing various widgets is made a lot easier by using OOP's polymorphism and inheritance. PLT Racket's GUI library is a good example.

Algorithms – Solving the Algorithmic Problem of Picking Cards

Here's a quick implementation in java. The idea is to find how many cards can be picked each step by counting the number of cards with a number below this step and subtracting the number of cards already picked. Of course a lot of work is unnecessarily repeated, but this should give a good idea of how to approach this problem.

public class PickCards {
public static int countLessOrEqualThanMax(int[] cards, int max) {
    int count = 0;
    for (int number : cards) {
        if(number <= max) count++;
    }
    return count;
}

public static void main(String[] args) {
    int[] cards = {0, 1, 2, 4, 3};
    int numberOfWays = 1;
    for(int i = 0; i < cards.length; i++) {
        int ways = Math.max(0, countLessOrEqualThanMax(cards, i) - i);
        numberOfWays *= ways;
    }
    System.out.println(numberOfWays);
}

}

Best Answer

Related Solutions

Object-Oriented Paradigms – Best Practices for UI Programming

Algorithms – Solving the Algorithmic Problem of Picking Cards

Related Topic