A Brief Introduction to Algorithm

What is an Algorithm?

An algorithm is a set of instructions that a computer program or a human follows to solve a particular problem. Algorithms can be thought of as recipes for solving problems. They can be as simple as adding two numbers together or as complex as searching through millions of records in a database.

Here’s a step-by-step tutorial on how to create an algorithm:

  • Define the problem: Before you can create an algorithm, you need to understand the problem you are trying to solve. What is the input? What is the expected output? What are the constraints?
  • Plan your approach: Once you understand the problem, you need to plan your approach. What steps do you need to take to solve the problem? What data structures and algorithms will you use?
  • Write the algorithm: Now it’s time to write the algorithm. Start by breaking the problem down into smaller, more manageable tasks. Write out each step in plain English, without worrying about syntax.
  • Test your algorithm: Once you have written your algorithm, you need to test it. Use sample inputs to make sure that your algorithm produces the correct output. If it doesn’t, go back and revise your algorithm.
  • Optimize your algorithm: Finally, you may want to optimize your algorithm to make it more efficient. Look for ways to reduce the number of steps or to use more efficient data structures.

Here’s an example of an algorithm that adds two numbers:

  1. Define the problem: Add two numbers together.
  2. Plan your approach: Create a variable to hold the sum. Add the two numbers together.
  3. Write the algorithm:
    Input: num1, num2
    Output: sum
    sum = num1 + num2
    return sum

  1. Test your algorithm:
    Input: num1 = 2, num2 = 3
    Output: sum = 5
  2. Optimize your algorithm: This algorithm is already very efficient, so there’s no need to optimize it further.

The articles in this Algorithm series are listed below.

Sorting Algorithms

Sorting algorithms are used to sort a list of elements in a particular order. There are various sorting algorithms such as Bubble Sort, Quick Sort, Merge Sort, etc.

Python
#[Bubble sort]
def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(0, n-i-1):
            if arr[j] > arr[j+1]:
                arr[j], arr[j+1] = arr[j+1], arr[j]


#[Quick sort]
def quick_sort(arr):
    if len(arr) <= 1:
        return arr
    else:
        pivot = arr[0]
        left = [x for x in arr[1:] if x <= pivot]
        right = [x for x in arr[1:] if x > pivot]
        return quick_sort(left) + [pivot] + quick_sort(right)

Search Algorithms

Search algorithms are used to find a specific element in a list of elements. Binary search and linear search are two common search algorithms.

Python
#[Binary search]
def binary_search(arr, x):
    low = 0
    high = len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] < x:
            low = mid + 1
        elif arr[mid] > x:
            high = mid - 1
        else:
            return mid
    return -1

#[Linear search]
def linear_search(arr, x):
    for i in range(len(arr)):
        if arr[i] == x:
            return i
    return -1

Graph Algorithms

Graph algorithms are used to solve problems related to graphs. These include algorithms for finding the shortest path between two nodes, algorithms for finding cycles in a graph, and algorithms for traversing a graph.

Python
#[Dijkstra's Algorithm]
import heapq

def dijkstra(graph, start):
    distances = {node: float('inf') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        (curr_distance, curr_node) = heapq.heappop(pq)
        if curr_distance > distances[curr_node]:
            continue
        for (next_node, weight) in graph[curr_node].items():
            distance = curr_distance + weight
            if distance < distances[next_node]:
                distances[next_node] = distance
                heapq.heappush(pq, (distance, next_node))
    return distances

Encryption Algorithms

Encryption algorithms are used to encode messages in such a way that only the intended recipient can decode them. Examples of encryption algorithms include RSA and AES.

Python
#[RSA Encryption]
from Crypto.PublicKey import RSA
from Crypto.Cipher import PKCS1_OAEP

key = RSA.generate(2048)
private_key = key.export_key()
public_key = key.publickey().export_key()

cipher = PKCS1_OAEP.new(key)
message = b'This is a secret message'
ciphertext = cipher.encrypt(message)

Compression Algorithms

Compression algorithms are used to reduce the size of data. Examples of compression algorithms include Gzip and Zip.

Python
#[Gzip compression]
import gzip

with open('file.txt', 'rb') as f_in, gzip.open('file.txt.gz', 'wb') as f_out:
    f_out.writelines(f_in)

Machine Learning Algorithms

Machine learning algorithms are used to train models to make predictions or classifications based on input data. Examples of machine learning algorithms include decision trees, neural networks, and support vector machines.

Python
#[Decision Tree]
from sklearn.tree import DecisionTreeClassifier

X = [[0, 0], [1, 1]]
y = [0, 1]

clf = DecisionTreeClassifier()
clf = clf.fit(X, y)

Pathfinding Algorithms

Pathfinding algorithms are used to find the shortest path between two points. Examples include Dijkstra’s algorithm and A* algorithm.

Python
#[A* Algorithm]
import heapq
from math import sqrt


def heuristic(a, b):
    return sqrt((a[0] - b[0]) ** 2 + (a[1] - b[1]) ** 2)


def astar(start, goal, graph):
    frontier = [(0, start)]
    came_from = {}
    cost_so_far = {start: 0}

    while frontier:
        current_cost, current = heapq.heappop(frontier)
        if current == goal:
            path = []
            while current in came_from:
                path.append(current)
                current = came_from[current]
            path.append(start)
            path.reverse()
            return path

        for next_node in graph[current]:
            new_cost = cost_so_far[current] + graph[current][next_node]
            if next_node not in cost_so_far or new_cost < cost_so_far[next_node]:
                cost_so_far[next_node] = new_cost
                priority = new_cost + heuristic(goal, next_node)
                heapq.heappush(frontier, (priority, next_node))
                came_from[next_node] = current

    return None


Pattern Searching Algorithms

Pattern-searching algorithms are used to find patterns in a given string or text. Examples include the Knuth-Morris-Pratt algorithm and the Boyer-Moore algorithm.

Python
#[Knuth-Morris-Pratt (KMP)]
def kmp(text, pattern):
    # Compute the prefix function
    prefix = [0] * len(pattern)
    j = 0
    for i in range(1, len(pattern)):
        while j > 0 and pattern[j] != pattern[i]:
            j = prefix[j-1]
        if pattern[j] == pattern[i]:
            j += 1
        prefix[i] = j

    # Perform pattern matching using the prefix function
    j = 0
    for i in range(len(text)):
        while j > 0 and pattern[j] != text[i]:
            j = prefix[j-1]
        if pattern[j] == text[i]:
            j += 1
        if j == len(pattern):
            return i - j + 1
    return -1


#[Boyer-Moore algorithm]
def boyer_moore(text, pattern):
    # Preprocess the pattern
    last = {}
    for i in range(len(pattern)):
        last[pattern[i]] = i

    # Search for the pattern in the text
    i = len(pattern) - 1
    j = len(pattern) - 1
    while i < len(text):
        if text[i] == pattern[j]:
            if j == 0:
                return i
            else:
                i -= 1
                j -= 1
        else:
            if text[i] in last:
                i += len(pattern) - min(j, 1 + last])
            else:
                i += len(pattern)
            j = len(pattern) - 1
    return -1


These are just a few examples of the many types of algorithms that exist. Each type of algorithm is designed to solve a specific problem, and different algorithms may be more or less efficient depending on the problem at hand.

Share The Tutorial With Your Friends
Twiter
Facebook
LinkedIn
Email
WhatsApp
Skype
Reddit

Check Our Ebook for This Online Course

Advanced topics are covered in this ebook with many practical examples.