An algorithmic paradigm, algorithm design paradigm, algorithmic technique, or algorithmic strategy is a generic method or approach which underlies the design of a class of algorithms. In simple “High level approach to solving a class of problems”.
Steps in development of Algorithms
a) Problem definition
b) Development of a model
c) Specification of Algorithm
d) Designing an Algorithm
e) Checking the correctness of Algorithm
f) Analysis of Algorithm
g) Implementation of Algorithm
h) Program testing
i) Documentation Preparation
Common design paradigms
i. Divide and conquer
ii. Dynamic programming
iii. Greedy algorithm
iv. Back Tracking
v. Brute Force
vi. Branch and Bound
Divide and conquer algorithm:
Divide and conquer (D&C) is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm works by recursively breaking down a problem into two or more sub-problems of the same or related type, until these become simple enough to be solved directly. The solutions to the sub-problems are then combined to give a solution to the original problem.
Dynamic Programming:
One disadvantage of using Divide-and-Conquer is that the process of recursively solving separate sub-instances can result in the same computations being performed repeatedly since identical sub-instances may arise.
The idea behind dynamic programming is to avoid this pathology by obviating the requirement to calculate the same quantity twice.
The method usually accomplishes this by maintaining a table of sub-instance results.
Dynamic Programming is a Bottom-Up Technique in which the smallest sub-instances are explicitly solved first and the results of these used to construct solutions to progressively larger sub-instances.
In contrast, Divide-and-Conquer is a Top-Down Technique which logically progresses from the initial instance down to the smallest sub-instance via intermediate sub-instances.
Greedy Algorithms:
it is “take what you can get now” strategy algorithm.
The solution is constructed through a sequence of steps, each expanding a partially constructed solution obtained so far. At each step the choice must be locally optimal – this is the central point of this technique.
Examples:
Minimal spanning tree
Shortest distance in graphs
Greedy algorithm for the Knapsack problem
The coin exchange problem
Huffman trees for optimal encoding
Greedy techniques are mainly used to solve optimization problems. They do not always give the best solution.
Brute Force:
Brute force is a straightforward approach to solve a problem based on the problem’s statement and definitions of the concepts involved. It is considered as one of the easiest approach to apply and is useful for solving small – size instances of a problem.
Some examples of brute force algorithms are:
Computing an (a > 0, n a nonnegative integer) by multiplying a*a*…*a
Computing n!
Selection sort
Bubble sort
Sequential search
Exhaustive search: Traveling Salesman Problem, Knapsack problem.
Branch-and-bound:
Branch and bound is used when we can evaluate each node using the cost and utility functions. At each step we choose the best node to proceed further. Branch-and bound algorithms are implemented using a priority queue. The state-space tree is built in a breadth-first manner.
Example: the 8-puzzle problem. The cost function is the number of moves. The utility function evaluates how close is a given state of the puzzle to the goal state, e.g. counting how many tiles are not in place.
hellotech 