What are Algorithms and Their Types?

Watch the Video: Introduction to Algorithms

What is an Algorithm?

An algorithm is a set of step-by-step instructions designed to perform a specific task. It can be as simple as adding two numbers or as complex as sorting a large dataset. Algorithms are the foundation of problem-solving in computer science and are typically written in a way that can be translated into programming languages.

Example: Algorithm to Add Two Numbers

Let's look at a simple example of adding two numbers:

def add_two_numbers(num1, num2):
    # Step 1: Add the two numbers
    sum = num1 + num2
    # Step 2: Return the result
    return sum

# Example Usage
result = add_two_numbers(5, 7)
print("The sum is:", result)

This is a simple implementation in Python that illustrates how algorithms work.

Types of Algorithms

Below are some common types of algorithms with examples:

1. Simple Recursive Algorithm

These algorithms solve smaller instances of the same problem and combine the results.

def factorial(n):
    # Base Case
    if n == 1:
        return 1
    # Recursive Case
    return n * factorial(n - 1)

# Example Usage
result = factorial(5)
print("Factorial:", result)

2. Divide and Conquer Algorithm

These algorithms divide the problem into smaller subproblems, solve them recursively, and then combine their results. Examples include Merge Sort and Quick Sort.

def merge_sort(arr):
    if len(arr) <= 1:
        return arr

    mid = len(arr) // 2
    left_half = merge_sort(arr[:mid])
    right_half = merge_sort(arr[mid:])

    return merge(left_half, right_half)

def merge(left, right):
    result = []
    while left and right:
        if left[0] < right[0]:
            result.append(left.pop(0))
        else:
            result.append(right.pop(0))
    result.extend(left or right)
    return result

# Example Usage
arr = [6, 3, 8, 5, 2]
sorted_arr = merge_sort(arr)
print("Sorted Array:", sorted_arr)

3. Dynamic Programming Algorithm

Dynamic programming remembers past results and uses them to find new results. Example: Finding the nth Fibonacci number.

def fibonacci(n, memo={}):
    if n in memo:
        return memo[n]
    if n <= 2:
        return 1

    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo)
    return memo[n]

# Example Usage
result = fibonacci(10)
print("10th Fibonacci Number:", result)

4. Greedy Algorithm

These algorithms make the optimal choice at each step in the hopes of finding the global optimum.

def coin_change(coins, amount):
    coins.sort(reverse=True)
    count = 0
    for coin in coins:
        while amount >= coin:
            amount -= coin
            count += 1
    return count

# Example Usage
result = coin_change([1, 5, 10, 25], 63)
print("Coins Used:", result)

5. Brute Force Algorithm

These algorithms try all possible solutions to find the best one. Example: Finding the maximum number in an array.

def find_maximum(arr):
    maximum = arr[0]
    for num in arr:
        if num > maximum:
            maximum = num
    return maximum

# Example Usage
arr = [3, 5, 7, 2, 8]
result = find_maximum(arr)
print("Maximum Number:", result)

6. Randomized Algorithm

These algorithms use random numbers to make decisions during execution. Example: Quick Sort with a random pivot.

Conclusion

Understanding algorithms and their types is crucial in solving computational problems efficiently. Mastering these algorithms will enhance your problem-solving skills and prepare you for real-world challenges.

Nandi Vardhan
Data Scientist, content creator, and passionate educator in the field of machine learning and data science.