TutorialsDestiny

Computer Algorithm

What is an Algorithm?

An algorithm is a predefined sequence of steps designed to solve a specific problem or perform a task efficiently. Algorithms are found everywhere—from daily activities like making coffee and solving a Rubik’s cube to complex computer applications such as Google Search, social media platforms, and e-commerce websites.

From brushing your teeth in the morning to following a bedtime routine at night, algorithms guide our actions. In mathematics, formulas and equations serve as algorithms, while in programming, algorithms define how input is processed to generate the desired output.

Algorithms can be represented in multiple ways, including:

  • Plain English descriptions
  • Flowcharts
  • Programming languages

Algorithm:

For Examples let us see an Algorithm to find the greatest of three numbers.

Start
Input three numbers A, B & C.
Check IF A>B 
IF Yes 
{Check IF A>C
IF Yes 
Output A is greatest
IF No 
Output C is gratest }
IF No 
{Check IF B>C
IF Yes 
Output B is greatest 
IF No
Output C Is greatest }
Stop

Flowchart of the above algorithm-

Characteristics of a Good Algorithm

  1. Well-Defined Input – An algorithm must have a clear and defined input to process.
  2. Well-Defined Output – Every algorithm should produce a meaningful and expected output.
  3. Finiteness – The algorithm must complete in a finite number of steps. Even if complex, it should eventually stop.
  4. Language Independence – A well-designed algorithm should be applicable in any programming language or even in natural language.
  5. Unambiguity – Each step in an algorithm must be clear, straightforward, and free of confusion.

Types of Algorithms

Algorithms can be categorized based on their approach to problem-solving. Below are some of the most commonly used types of algorithms, explained with examples to enhance understanding.

1. Brute Force Algorithm

A brute force algorithm is the simplest and most straightforward method for solving a problem. It systematically explores all possible solutions until it finds the correct one. While it guarantees a solution, it is often inefficient for large datasets due to its high time complexity.

Applications:

  • Password Cracking: Attempts every possible password combination.
  • Search Algorithms: Linear search scans each element in a list until the target is found.
  • Combinatorial Problems: Explores all paths in a maze to find the best route.

Example: Unlocking a 4-Digit Padlock

Imagine forgetting the combination to a 4-digit number lock. A brute force approach would involve trying every number from 0000 to 9999 until the lock opens. This requires up to 10,000 attempts in the worst case, making the method highly inefficient for large-scale problems.

Time Complexity:

  • Best-case: \(O(1)\).
  • Worst-case: , where n is the number of coin denominations.

2. Greedy Algorithm

A greedy algorithm builds a solution by making a series of choices, each selecting the best local (immediate) option in the hope of achieving the best overall (global) result. It does not revise past decisions and may not always lead to the optimal solution.

Key Characteristics:

  • Chooses the best option at each step.
  • Does not backtrack or revise earlier decisions.
  • Suitable for problems with optimal substructure and greedy choice property.

Pros and Cons:

✅ Simple to implement and efficient for specific problems.
❌ May not always lead to the optimal global solution.

Example: Coin Change Problem

Problem: Given coin denominations {10, 5, 2, 1}, find the minimum coins needed to make a sum of 37.
Solution:

  1. Choose the largest coin ≤ 37: ( 10 ).
  2. Keep adding ( 10 ) until the sum approaches 37: ( 10 + 10 + 10 = 30 ).
  3. Add ( 5 ) (next largest denomination): ( 30 + 5 = 35 ).
  4. Add ( 2 ): ( 35 + 2 = 37 ).
  5. Total coins used: 4 (( 10, 10, 10, 5, 2 )).

⚠ Note: In some cases, a greedy algorithm might not provide the optimal solution. For instance, making 8 from {5, 3, 1} requires {3, 3, 1} (optimal), but the greedy approach might choose {5, 1, 1, 1}.

Time Complexity:

  • Best-case: O(1) .
  • Worst-case: O(n) , where n is the number of coin denominations.

3. Recursive Algorithm

A recursive algorithm solves a problem by dividing it into smaller instances of the same problem, eventually reaching a base case to stop the recursion.

Key Characteristics:

  • Uses function calls to repeat tasks.
  • Requires a base condition to prevent infinite recursion.
  • Often simplifies complex problems.

Example: Factorial Calculation

The factorial of \(( n ) (( n! )\) is calculated as:
\[n! = n \times (n – 1)!\]
Recursive Function (Python Example):

def factorial(n):
    if n == 1:  # Base case
        return 1
    else:
        return n * factorial(n - 1)


For \( factorial(5) \), the function expands as:
\[ 5 \times 4 \times 3 \times 2 \times 1 \]

Time Complexity:

  • Best-case: \( O(1) \) (base case).
  • Worst-case: \( O(n) \) (maximum recursive depth).

4. Divide and Conquer Algorithm

A divide and conquer algorithm divides a problem into smaller subproblems, solves them independently, and combines their solutions to solve the original problem.

Key Steps:

  1. Divide: Split the problem into smaller subproblems.
  2. Conquer: Solve each subproblem recursively.
  3. Combine: Merge the solutions of the subproblems.

Example: Merge Sort

Steps:

  1. Divide an unsorted array into two halves.
  2. Recursively sort each half.
  3. Merge the two sorted halves to form the final sorted array.

Time Complexity:

  • Best, Worst, and Average-case:

5. Dynamic Programming (DP) Algorithm

Dynamic programming solves problems by breaking them into overlapping subproblems, storing solutions to avoid redundant calculations.

Key Characteristics:

  • Optimal Substructure: Problems can be divided into smaller independent subproblems.
  • Overlapping Subproblems: Repeated calculations are avoided using memoization or tabulation.

Example: Fibonacci Sequence

Without DP, Fibonacci calculations redundantly compute the same values:
\[ F(n) = F(n-1) + F(n-2) \]
Using DP, previously computed values are stored to optimize performance.

Time Complexity:

  • Without DP: \( O(2^n) \).
  • With DP: \( O(n) \).

6. Randomized Algorithm

A randomized algorithm incorporates randomness in its logic to improve performance or simplify implementation.

Key Characteristics:

  • Uses random numbers during execution.
  • Two types:
  • Las Vegas: Always correct but runtime varies.
  • Monte Carlo: Faster but may produce incorrect results occasionally.

Example: Randomised QuickSort

QuickSort selects a random pivot to partition the array, improving its average performance.

Time Complexity:

Best-case: \(O(nlogn)\).

Worst-case: \(O(n^2)\) (rare due to randomness).

Conclusion

Algorithms are the backbone of both daily life and computer science. Understanding different types of algorithms helps in problem-solving, programming, and optimising various tasks. Whether it’s a brute force approach, a recursive function, or dynamic programming, choosing the right algorithm can greatly improve efficiency and performance.

Would you like more examples or a deeper explanation of any algorithm? Let me know!