Essential Algorithms Masterclass

Python
### Searching Algorithms

# 1. Linear Search - O(n)
def linear_search(arr, target):
    for i in range(len(arr)):
        if arr[i] == target:
            return i
    return -1

# 2. Binary Search - O(log n) | Requires sorted data
def binary_search(arr, target):
    low, high = 0, len(arr) - 1
    while low <= high:
        mid = (low + high) // 2
        if arr[mid] == target:
            return mid
        elif arr[mid] < target:
            low = mid + 1
        else:
            high = mid - 1
    return -1

# 3. Hashing (Hash Table Lookup) - O(1) average
def hash_lookup(data_dict, key):
    return data_dict.get(key, 'Not Found')

### Sorting Algorithms

# 4. Quick Sort - O(n log n) average
def quick_sort(arr):
    if len(arr) <= 1: return arr
    pivot = arr[len(arr) // 2]
    left = [x for x in arr if x < pivot]
    middle = [x for x in arr if x == pivot]
    right = [x for x in arr if x > pivot]
    return quick_sort(left) + middle + quick_sort(right)

# 5. Merge Sort - O(n log n) stable
def merge_sort(arr):
    if len(arr) <= 1: return arr
    mid = len(arr) // 2
    left = merge_sort(arr[:mid])
    right = merge_sort(arr[mid:])
    return merge(left, right)

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))
    return result + left + right

# 6. Heap Sort - O(n log n) in-place
import heapq
def heap_sort(arr):
    heapq.heapify(arr)
    return [heapq.heappop(arr) for _ in range(len(arr))]

# 7. Counting Sort - O(n + k) non-comparison
def counting_sort(arr):
    if not arr: return arr
    max_val = max(arr)
    counts = [0] * (max_val + 1)
    for x in arr: counts[x] += 1
    result = []
    for i, count in enumerate(counts):
        result.extend([i] * count)
    return result

Python
from collections import deque

# BFS
def bfs(graph, start):
    visited = {start}
    queue = deque([start])
    while queue:
        node = queue.popleft()
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

# DFS
def dfs(graph, node, visited=None):
    if visited is None: visited = set()
    visited.add(node)
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Python
import heapq

# Dijkstra
def dijkstra(graph, start):
    distances = {n: float('inf') for n in graph}
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d > distances[u]: continue
        for v, weight in graph[u].items():
            if d + weight < distances[v]:
                distances[v] = d + weight
                heapq.heappush(pq, (distances[v], v))

# Bellman-Ford
def bellman_ford(graph, start, nodes):
    dist = {n: float('inf') for n in nodes}
    dist[start] = 0
    for _ in range(len(nodes) - 1):
        for u, neighbors in graph.items():
            for v, w in neighbors.items():
                if dist[u] + w < dist[v]:
                    dist[v] = dist[u] + w

Python
def dfs(graph, node, visited=None):
    if visited is None: visited = set()
    visited.add(node)
    print(f"Visited: {node}")
    for neighbor in graph[node]:
        if neighbor not in visited:
            dfs(graph, neighbor, visited)

Python
import heapq

def dijkstra(graph, start):
    distances = {node: float('infinity') for node in graph}
    distances[start] = 0
    pq = [(0, start)]
    while pq:
        curr_d, curr_n = heapq.heappop(pq)
        if curr_d > distances[curr_n]: continue
        for neighbor, weight in graph[curr_n].items():
            dist = curr_d + weight
            if dist < distances[neighbor]:
                distances[neighbor] = dist
                heapq.heappush(pq, (dist, neighbor))
    return distances

Python
# 1. Fibonacci with Memoization
def fib_memo(n, memo={}):
    if n <= 1: return n
    if n not in memo: memo[n] = fib_memo(n-1) + fib_memo(n-2)
    return memo[n]

# 2. Knapsack Problem (0/1)
def knapsack(weights, values, capacity):
    n = len(weights)
    dp = [[0] * (capacity + 1) for _ in range(n + 1)]
    for i in range(1, n + 1):
        for w in range(1, capacity + 1):
            if weights[i-1] <= w:
                dp[i][w] = max(values[i-1] + dp[i-1][w-weights[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][capacity]

Python
# 1. Basic RSA Logic (Conceptual)
def rsa_concept(msg, e, n):
    # Encryption: c = (m^e) % n
    return pow(msg, e, n)

# 2. Secure Hashing (SHA-256)
import hashlib
def get_sha256(text):
    return hashlib.sha256(text.encode()).hexdigest()

Python
# 1. Gradient Descent (Simple Linear)
def gradient_descent(x, y, lr=0.01, epochs=100):
    m, c = 0, 0
    n = len(x)
    for _ in range(epochs):
        y_pred = m * x + c
        dm = (-2/n) * sum(x * (y - y_pred))
        dc = (-2/n) * sum(y - y_pred)
        m -= lr * dm
        c -= lr * dc
    return m, c

Python
# 1. Huffman Coding (Compression Logic)
def huffman_node(char, freq):
    return {'char': char, 'freq': freq, 'left': None, 'right': None}

# 2. KMP String Matching - O(n + m)
def kmp_search(text, pattern):
    # Uses failure function (LPS array) to skip unnecessary checks
    pass