Top 8 Algorithms every programmer should Know !!!

As a programmer, one should be familiar with the basics of algorithmic design and analysis. Algorithms are a set of instructions used to solve a specific problem, and having a solid understanding of various algorithms can greatly enhance a programmer's problem-solving abilities. In this article, we will discuss the top 8 algorithms every programmer should know.

1. Sorting algorithms:

Sorting algorithms are used to sort a list of items in a specific order. The most commonly used sorting algorithms are bubble sort, insertion sort, selection sort, merge sort, and quicksort. Each algorithm has its own set of advantages and disadvantages. For example, bubble sort is a simple algorithm, but it is not efficient for large datasets. In contrast, merge sort is an efficient algorithm, but it requires additional memory.

Example 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]

 arr = [64, 34, 25, 12, 22, 11, 90]

 bubble_sort(arr)

 print("Sorted array is:", arr)

Output: Sorted array is: [11, 12, 22, 25, 34, 64, 90]

2. Search algorithms:

Search algorithms are used to find a specific item in a list. The most commonly used search algorithms are linear search and binary search. Linear search is a simple algorithm that searches each item in a list until it finds the desired item. Binary search is a more efficient algorithm that only searches a specific portion of the list based on the midpoint.

Example Binary Search:

 def binary_search(arr, l, r, x):

    if r >= l:

        mid = l + (r - l) // 2

        if arr[mid] == x:

            return mid

        elif arr[mid] > x:

            return binary_search(arr, l, mid-1, x)

        else:

            return binary_search(arr, mid+1, r, x)

    else:

        return -1

 arr = [2, 3, 4, 10, 40]

 x = 10

 result = binary_search(arr, 0, len(arr)-1, x)

 if result != -1:

    print("Element is present at index", str(result))

 else:

    print("Element is not present in array")

Output: Element is present at index 3

3. Graph algorithms:

Graph algorithms are used to solve problems related to graphs, which are a collection of nodes and edges. The most commonly used graph algorithms are depth-first search (DFS) and breadth-first search (BFS). DFS is used to traverse a graph, while BFS is used to find the shortest path between two nodes.

Example Breadth First Search:

from collections import defaultdict

class Graph:

    def __init__(self):

        self.graph = defaultdict(list)

    def add_edge(self, u, v):

        self.graph[u].append(v)

    def BFS(self, s):

        visited = [False] * (max(self.graph) + 1)

        queue = []

        queue.append(s)

        visited[s] = True

        while queue:

            s = queue.pop(0)

            print(s, end=" ")

            for i in self.graph[s]:

                if visited[i] == False:

                    queue.append(i)

                    visited[i] = True

g = Graph()

g.add_edge(0, 1)

g.add_edge(0, 2)

g.add_edge(1, 2)

g.add_edge(2, 0)

g.add_edge(2, 3)

g.add_edge(3, 3)

print("Following is Breadth First Traversal (starting from vertex 2)")

g.BFS(2)

Output: Following is Breadth First Traversal (starting from vertex 2): 2 0 3 1

4. Dynamic programming:

Dynamic programming is a technique used to solve complex problems by breaking them down into smaller subproblems. Each subproblem is solved only once, and the results are stored in memory for future use. The most commonly used dynamic programming algorithms are the Fibonacci sequence and the knapsack problem.

Example Fibonacci Sequence:

 def fibonacci(n):

    if n <= 1:

        return n

    else:

        return fibonacci(n-1) + fibonacci(n-2)

 n = 10

 print("Fibonacci sequence:")

 for i in range(n):

    print(fibonacci(i), end=" ")

Output: Fibonacci sequence: 0 1 1 2 3 5 8 13 21 34

5. Greedy algorithms:

Greedy algorithms are used to solve optimization problems by making the best possible choice at each step. The most commonly used greedy algorithms are the activity selection problem and the Huffman coding algorithm.

Example Fractional Knapsack:

 def fractional_knapsack(wt, val, capacity):

    n = len(wt)

    items = []

    for i in range(n):

        items.append((wt[i], val[i], i))

    items.sort(key=lambda x: x[1]/x[0], reverse=True)

    total_value = 0

    fractions = [0]*n

    for i in range(n):

    if items[i][0] <= capacity:

        fractions[items[i][2]] = 1

        total_value += items[i][1]

        capacity -= items[i][0]

    else:

        fractions[items[i][2]] = capacity / items[i][0]

        total_value += items[i][1] * (capacity / items[i][0])

        break

 return total_value, fractions

wt = [10, 20, 30]

val = [60, 100, 120]

capacity = 50

result = fractional_knapsack(wt, val, capacity)

print("Maximum value in Knapsack =", result[0])

print("Fractions taken =", result[1])

Output: Maximum value in Knapsack = 240.0 Fractions taken = [1, 1, 0.6666666666666666]

6. Divide and Conquer:

Divide and Conquer is a technique used to solve complex problems by breaking them down into smaller subproblems. Each subproblem is solved independently, and the results are combined to solve the original problem. The most commonly used Divide and Conquer algorithms are merge sort, quicksort, and the Karatsuba algorithm.

Example Merge Sort:

def merge_sort(arr):

    if len(arr) > 1:

        mid = len(arr)//2

        left_half = arr[:mid]

        right_half = arr[mid:]

        merge_sort(left_half)

        merge_sort(right_half)

        i = j = k = 0

        while i < len(left_half) and j < len(right_half):

            if left_half[i] < right_half[j]:

                arr[k] = left_half[i]

                i += 1

            else:

                arr[k] = right_half[j]

                j += 1

            k += 1

        while i < len(left_half):

            arr[k] = left_half[i]

            i += 1

            k += 1

        while j < len(right_half):

            arr[k] = right_half[j]

            j += 1

            k += 1

arr = [64, 34, 25, 12, 22, 11, 90]

merge_sort(arr)

print("Sorted array is:", arr)

Output: Sorted array is: [11, 12, 22, 25, 34, 64, 90]

7. Backtracking:

Backtracking is a technique used to solve problems by exploring all possible solutions. If a solution is found, it is accepted, and if not, the algorithm backtracks and explores a different solution. The most commonly used backtracking algorithms are the eight queens problem and the travelling salesman problem.

Example N-Queens Problem:

def is_safe(board, row, col, n):

    for i in range(col):

        if board[row][i] == 1:

            return False

    for i, j in zip(range(row, -1, -1), range(col, -1, -1)):

        if board[i][j] == 1:

            return False

    for i, j in zip(range(row, n, 1), range(col, -1, -1)):

        if board[i][j] == 1:

            return False

    return True

def solve_n_queens(board, col, n):

    if col == n:

        for i in range(n):

            for j in range(n):

                print(board[i][j], end=" ")

            print()

        print()

        return True

    res = False

    for i in range(n):

        if is_safe(board, i, col, n):

            board[i][col] = 1

            res = solve_n_queens(board, col+1, n) or res

            board[i][col] = 0

    return res

n = 4

board = [[0 for x in range(n)] for y in range(n)]

solve_n_queens(board, 0, n)

Output:

0 0 1 0

1 0 0 0

0 0 0 1

0 1 0 0

0 1 0 0

0 0 0 1

1 0 0 0

0 0 1 0

8. Randomised Algorithm:

Randomised algorithms use a random number generator to make decisions during the algorithm's execution. These algorithms are used to solve problems that are difficult to solve deterministically. The most commonly used randomised algorithms are the quicksort algorithm and the Monte Carlo algorithm.

Example Quick Sort:

import random

def partition(arr, low, high):

    i = (low-1)

    pivot = arr[high]

    for j in range(low, high):

        if arr[j] <= pivot:

            i = i+1

            arr[i], arr[j] = arr[j], arr[i]

    arr[i+1], arr[high] = arr[high], arr[i+1]

    return (i+1)

def quick_sort(arr, low, high):

    if low < high:

        # Randomly select a pivot

        pivot_index = random.randint(low, high)

        arr[pivot_index], arr[high] = arr[high], arr[pivot_index]

        pi = partition(arr, low, high)

        quick_sort(arr, low, pi-1)

        quick_sort(arr, pi+1, high)

arr = [10, 7, 8, 9, 1, 5]

n = len(arr)

quick_sort(arr, 0, n-1)

print("Sorted array is:")

for i in range(n):

    print(arr[i], end=" ")

Output: Sorted array is: 1 5 7 8 9 10

In conclusion, understanding these 8 algorithms can greatly enhance a programmer's problem-solving abilities. Each algorithm has its own set of advantages and disadvantages, and choosing the right algorithm for a specific problem is critical for achieving optimal results. By familiarising themselves with these algorithms, programmers can improve their coding skills and become more efficient problem solvers.