Master the essential algorithm design techniques that form the backbone of computer science. Learn when and how to apply different paradigms to solve complex computational problems efficiently.

What is an Algorithm?

An algorithm is a step-by-step finite set of instructions to solve a well-defined computational problem. It is a precise plan for performing a sequence of actions.

Example: Sum of Two Numbers

Step 1: START ADD
Step 2: Get values of a & b
Step 3: c ← a + b
Step 4: Display c
Step 5: STOP

Essential Algorithm Criteria

Essential Criteria:

Input

Zero or more quantities externally supplied

Output

At least one quantity is produced

Definiteness

Each instruction must be clear and unambiguous

Additional Requirements:

Finiteness

Algorithm terminates after finite steps for all cases

Effectiveness

Every instruction sufficiently basic to be carried out

Algorithm Design Techniques

Greedy Algorithm

Makes locally optimal choices without considering future consequences

Example:

Dijkstra's algorithm, Prim's algorithm

When to Use:

When locally optimal choice leads to globally optimal solution

Divide and Conquer

Divides problem into smaller subproblems, solves recursively, then combines

Example:

Quick sort, Merge sort, Binary search

When to Use:

When problem can be broken into similar smaller problems

Dynamic Programming

Solves overlapping subproblems by storing solutions in optimal structure

Example:

Fibonacci series, Knapsack problem

When to Use:

When subproblems overlap and optimal substructure exists

Brute Force

Tries all possible solutions until finding the optimal one

Example:

Linear search algorithm

When to Use:

When problem size is small or no better algorithm exists

Backtracking

Explores all possible solutions and backtracks when solution isn't optimal

Example:

N-Queens problem, Sudoku solver

When to Use:

When need to find all solutions or constraint satisfaction problems

Branch and Bound

Systematically explores solution space with pruning of suboptimal branches

Example:

Traveling salesman problem

When to Use:

For optimization problems where bounds can be computed

Previous: Data Structures Next: Complexity Analysis

Essential Algorithm Criteria

Essential Criteria:

Input

Zero or more quantities externally supplied

Output

At least one quantity is produced

Definiteness

Each instruction must be clear and unambiguous

Additional Requirements:

Finiteness

Algorithm terminates after finite steps for all cases

Effectiveness

Every instruction sufficiently basic to be carried out

Algorithm Design Techniques

Greedy Algorithm

Makes locally optimal choices without considering future consequences

Example:

Dijkstra's algorithm, Prim's algorithm

When to Use:

When locally optimal choice leads to globally optimal solution

Divide and Conquer

Divides problem into smaller subproblems, solves recursively, then combines

Example:

Quick sort, Merge sort, Binary search

When to Use:

When problem can be broken into similar smaller problems

Dynamic Programming

Solves overlapping subproblems by storing solutions in optimal structure

Example:

Fibonacci series, Knapsack problem

When to Use:

When subproblems overlap and optimal substructure exists

Brute Force

Tries all possible solutions until finding the optimal one

Example:

Linear search algorithm

When to Use:

When problem size is small or no better algorithm exists

Backtracking

Explores all possible solutions and backtracks when solution isn't optimal

Example:

N-Queens problem, Sudoku solver

When to Use:

When need to find all solutions or constraint satisfaction problems

Branch and Bound

Systematically explores solution space with pruning of suboptimal branches

Example:

Traveling salesman problem

When to Use:

For optimization problems where bounds can be computed