Ada Notes

C
DSA
Software Engineering
Software Architecture
Operating System
Big Data
Data Mining and Warehousing
TOC
Ada
CPP
DBMS

All Topics (7)

  • 1. Definition of Algorithm
  • 2. Characteristics (Properties) of an Algorithm
  • 3. Algorithm and Program Notes
  • 4. Definition of Pseudocode
  • 5. Comparison: Algorithm vs Pseudocode
  • 6. Steps to Design an Algorithm
  • 7: Algorithm Design Techniques:

6. Steps to Design an Algorithm

Designing an algorithm is a structured process. Here are the key steps:

1. Understand the Problem

  • Carefully read and analyze the problem.

  • Identify inputs, outputs, and the desired result.

  • Make sure the requirements are clear before proceeding.

2. Decide Computation Means & Data Structure

  • Determine how the problem will be solved:

    • Use mathematical formulas, logical operations, or iteration.

  • Choose the appropriate data structures: arrays, lists, trees, etc.

3. Select Algorithm Design Technique

Common techniques include:

  • Divide and Conquer

  • Greedy Method

  • Dynamic Programming

  • Brute Force / Iterative Methods

4. Design the Algorithm

  • Write the step-by-step instructions clearly.

  • Ensure clarity, finiteness, effectiveness, and correctness.

5. Prove Correctness

  • Check the algorithm logically or mathematically.

  • Make sure it produces correct output for all possible inputs.

6. Analyze the Algorithm

  • Determine efficiency:

    • Time complexity (how long it takes)

    • Space complexity (how much memory it uses)

  • Identify potential bottlenecks or improvements.

7. Code the Algorithm

  • Implement the algorithm in a programming language.

  • Ensure the program matches the algorithm’s logic.

  • Test with multiple inputs for correctness.

Flow Diagram: Algorithm Design Process

 
Understand the Problem
           ↓
Decide Computation Means & Data Structure
           ↓
Select Algorithm Design Technique
           ↓
Design as Algorithm
           ↓
Prove Correctness
           ↓
Analyze the Algorithm
           ↓
Code the Algorithm

7: Algorithm Design Techniques:

  1. Brute Force
  2. Divide and Conquer
  3. Greedy Technique
  4. Dynamic Programming
  5. Backtracking
  6. Branch & Bound
1. Brute Force
Solving problems based on the problem statement and definition.
  • Examples: Selection Sort, Bubble Sort, Sequential Search.
2. Divide and Conquer
Divide the problem into subproblems and find its solution.
  • Examples: Merge Sort, Quick Sort, Binary Search, Find max or min of list, Strassen's matrix multiplication.
3. Greedy Technique
Definition: Works in stages by considering one input at a time and always tries to find the optimal solution (local optimum) at each step.
  • Examples:
    • Knapsack problem (Fractional)
    • Job sequencing with deadline
    • Optimal merge patterns
    • Huffman coding
    • Minimum Spanning Tree (Prim's & Kruskal's algorithm)
    • Single source shortest path (Dijkstra's algorithm)
4. Dynamic Programming
Definition: Solving the problem by breaking it down into overlapping subproblems.
  • Examples:
    • 0/1 Knapsack problem
    • Multistage graph problem
    • Floyd-Warshall algorithm (All pairs shortest path problem)
    • Reliability design problem
5. Backtracking
Definition: A systematic method of searching for a solution to combinatorial problems with algorithms.
  • Examples:
    • N-queen's problem
    • Hamiltonian cycle
    • Graph coloring problem
6. Branch and Bound
Definition: Systematically searching for a solution in state space (usually for optimization problems).
  • Examples:
    • Travelling salesperson problem
    • Assignment problem
Page 2 of 2