i dont know where i got this image from lol
In programming, an algorithm is a set of instructions or a procedure for solving a specific problem or achieving a specific task. Algorithms can be expressed in any programming language and can be as simple as a sequence of basic operations or as complex as a multi-step process involving different data structures and logic. The main goal of an algorithm is to take in input, process it and provide an output that is expected. Algorithms can be classified based on the time and space complexity, the technique used for solving the problem, and the type of problem it solves. Examples of algorithm are sorting, searching, graph traversals, string manipulations, mathematical operations, and many more.
Algorithms we will be talking about:
- Sorting algorithms: Sorting is a fundamental operation in computer science and there are several efficient algorithms for it, such as quicksort, merge sort and heap sort.
- Search algorithms: Searching for an element in a large dataset is a common task and there are several efficient algorithms for it, such as binary search and hash tables.
- Graph algorithms: Graph algorithms are used to solve problems related to graphs, such as finding the shortest path between two nodes or determining if a graph is connected.
- Dynamic programming: Dynamic programming is a technique for solving problems by breaking them down into smaller subproblems and storing the solutions to these subproblems to avoid redundant computation.
- Greedy algorithms: Greedy algorithms are used to solve optimization problems by making the locally optimal choice at each step with the hope of finding a global optimum.
- Divide and Conquer: Divide and Conquer is an algorithm design paradigm based on multi-branched recursion. A divide and conquer algorithm breaks down a problem into sub-problems of the same or related type, until these become simple enough to be solved directly.
- Backtracking: Backtracking is a general algorithmic technique that considers searching every possible combination in a systematic manner, and abandons a particular path as soon as it determines that it cannot be part of the solution.
- Randomized Algorithm: Randomized algorithms use randomness to solve a problem. It can be useful to solve problems that cannot be solved deterministically or to improve the average case complexity of a problem.
These algorithms are widely used in various applications and it’s important for a programmer to have a strong understanding of them. So i will try my best to explain them.
-
Sorting algorithms:
-
Quicksort: Quicksort is a divide-and-conquer algorithm that chooses a “pivot” element from the array and partitions the other elements into two sub-arrays, according to whether they are less than or greater than the pivot. The sub-arrays are then sorted recursively.
def quicksort(arr): if len(arr) pivot] return quicksort(left) + middle + quicksort(right)print(quicksort([3,6,8,10,1,2,1]))
- Merge Sort: The merge sort algorithm is a divide-and-conquer algorithm that divides an array in two, sorts the two halves, and then merges them back together.
def merge_sort(arr): if len(arr) x: high = mid - 1 else: return mid return -1print(binary_search([1,2,3,4,5,6,7], 4))
- Hash Tables: A hash table is a data structure that maps keys to values, using a hash function to compute an index into an array of buckets or slots, from which the desired value can be found.
class HashTable: def __init__(self): self.size = 10 self.keys = [None] * self.size self.values = [None] * self.size def put(self, key, data): index = self.hash_function(key) while self.keys[index] is not None: if self.keys[index] == key: self.values[index] = data # update return index = (index + 1) % self.size self.keys[index] = key self.values[index] = data def get(self, key): index = self.hash_function(key) while self.keys[index] is not None: if self.keys[index] == key: return self.values[index] index = (index + 1) % self.size return None def hash_function(self, key): sum = 0 for pos in range(len(key)): sum = sum + ord(key[pos]) return sum % self.sizet = HashTable()t.put("apple", 10)t.put("orange", 20)t.put("banana", 30)print(t.get("orange"))
-
Graph Algorithm :
-
Dijkstra’s shortest path algorithm: Dijkstra’s shortest path algorithm is an algorithm for finding the shortest path between nodes in a graph.
import heapqdef dijkstra(graph, start): heap = [(0, start)] visited = set() while heap: (cost, v) = heapq.heappop(heap) if v not in visited: visited.add(v) for u, c in graph[v].items(): if u not in visited: heapq.heappush(heap, (cost + c, u)) return visitedgraph = { 'A': {'B': 2, 'C': 3}, 'B': {'D': 4, 'E': 5}, 'C': {'F': 6}, 'D': {'G': 7}, 'E': {'G': 8, 'H': 9}, 'F': {'H': 10}, 'G': {}, 'H': {}}print(dijkstra(graph, 'A'))
-
Dynamic Programming:
-
Fibonacci sequence: A classic example of a problem that can be solved using dynamic programming is the Fibonacci sequence.
def fibonacci(n): if n 1: left_node = priority_queue.get() right_node = priority_queue.get() combined_freq = left_node.freq + right_node.freq combined_node = HuffmanNode(None, combined_freq) priority_queue.put(combined_node) # Generate the Huffman code for each character huffman_code = {} generate_code(priority_queue.get(), "", huffman_code) # Encode the input data encoded_data = "" for char in data: encoded_data += huffman_code[char] return encoded_data, huffman_codeprint(huffman_encoding("aaaaabbbcccc"))
-
Divide and Conquer :
-
Merge Sort: already explained above
-
Backtracking:
-
The N-Queens Problem: The N-Queens problem is a classic problem that can be solved using backtracking. The goal is to place N queens on an NxN chessboard in such a way that no queen can attack any other queen.
def solveNQueens(n): def could_place(row, col): # check if a queen can be placed on board[row][col] # check if this row is not under attack from any previous queen in that column for i in range(row): if board[i] == col or abs(board[i] - col) == abs(i - row): return False return Truedef backtrack(row=0, count=0): for col in range(n): if could_place(row, col): board[row] = col if row + 1 == n: count += 1 else: count = backtrack(row + 1, count) return count board = [-1 for x in range(n)] return backtrack()print(solveNQueens(4))
This algorithm starts placing queens in the first row, and for every placed queen it checks if it is under attack from any previous queen. If not, it proceeds to the next row and repeats the process. If a queen is placed in a position where it is under attack, the algorithm backtracks and tries a different position. This continues until all queens are placed on the board without any attacking each other.
- Randomized Algorithm: — Randomized QuickSort: A variation of quicksort algorithm where pivot is chosen randomly.
import randomdef randomized_quicksort(arr): if len(arr) pivot] return randomized_quicksort(left) + middle + randomized_quicksort(right)print(randomized_quicksort([3,6,8,10,1,2,1]))
These are some of the most commonly used algorithms that every programmer should be familiar with. Understanding these algorithms and their implementation can help a programmer to make better decisions when it comes to designing and implementing efficient solutions.
More content at PlainEnglish.io. Sign up for our free weekly newsletter. Follow us on Twitter, LinkedIn, YouTube, and Discord.
Build awareness and adoption for your tech startup with Circuit.
Top 8 Algorithms Every Programmer Should Know 💯 was originally published in Python in Plain English on Medium, where people are continuing the conversation by highlighting and responding to this story.