Algorithm Strategies

General approaches to the construction of efficient solution to problems

Some methods provide templates suited to solving broad range of diverse problem

Although more than 1 technique may be applicable to a specific problem, it is often the case that algorithm constructed by certain approach is clearly superior to equivalent solution built using alternative techniques

There are different types of Algorithmic Strategies:

1. Divide and Conquer

2. Greedy method

3. Backtracking

4. Branch and bound

5. Dynamic programming

Divide and Conquer:

Divide-and-conquer, breaks a problem into subproblems that are similar to the original problem, recursively solves the subproblems, and finally combines the solutions to the subproblems to solve the original problem.

Divide: the original problem into a set of subproblems.

Conquer: Solve every subproblem individually, recursively.

Combine: Put together the solutions of the subproblems to get the solution to the whole problem.

Divide and Conquer

Examples:

The specific computer algorithms are based on the Divide & Conquer approach:

Binary Search
Merge sort
Maximum and Minimum Problem
Quick sort
Tower of Hanoi

Greedy method:

This makes the choice that seems to be the best at that moment.
This means that it makes a locally-optimal choice in the hope that this choice will lead to a globally-optimal solution.
The Greedy algorithm has only one shot to compute the optimal solution so that it never goes back and reverses the decision.

Example: