Algorithms Beginner Course

An algorithm is a step-by-step procedure to solve a problem — like a recipe, but for computation. Sorting your contacts, finding the shortest route on a map, compressing a photo: all algorithms. The skill you're learning isn't memorizing code — it's breaking problems into clear, repeatable steps. This is the foundation every programmer and data scientist builds on.

# A simple algorithm: find the largest number
def find_max(arr):
    max_so_far = arr[0]
    for num in arr:
        if num > max_so_far:
            max_so_far = num
    return max_so_far

print(find_max([3, 7, 2, 9, 5]))

def find_min(arr):
    min_so_far = arr[0]
    for num in arr:
        if num < min_so_far:
            min_so_far = num
    return min_so_far

Big O notation describes how an algorithm's time or space grows as input grows. O(1) is constant — instant regardless of size. O(n) is linear — doubles with input. O(n²) is quadratic — 100 items means 10,000 operations. This is THE language for comparing algorithms: an O(n) algorithm beats an O(n²) one as data grows, no matter the constant factors.

def constant_time(arr): return arr[0]        # O(1)
def linear_time(arr):                       # O(n)
    for x in arr: print(x)
def quadratic_time(arr):                    # O(n²)
    for i in arr:
        for j in arr: print(i, j)

O(n) — linear.

Time complexity measures how long an algorithm takes; space complexity measures how much memory it uses. They're often a trade-off: caching results uses more memory but saves time. A hash table gives O(1) lookup but uses O(n) space. Understanding both helps you pick the right tool for your constraints — mobile apps care about memory, servers about speed.

# Time-efficient but space-heavy: hash lookup
def has_pair(arr, target):
    seen = set()  # O(n) space
    for x in arr:
        if target - x in seen:
            return True
        seen.add(x)
    return False
# Time: O(n), Space: O(n)

O(n) — the set stores n items.

Linear search checks each element one by one until it finds the target. It's O(n) — slow for large data, but simple and works on ANY list, sorted or not. It's the baseline every faster search improves on. When data is small or unsorted, linear search is perfectly fine.

def linear_search(arr, target):
    for i, value in enumerate(arr):
        if value == target:
            return i
    return -1

print(linear_search([4, 2, 9, 7], 9))

def search(arr, t):
    for i, v in enumerate(arr):
        if v == t: return i
    return -1

Binary search repeatedly halves the search space — check the middle, eliminate half, repeat. It requires SORTED data but runs in O(log n): a billion items needs only ~30 steps. This is the most famous efficient algorithm, and the 'divide and conquer' thinking it teaches powers merge sort, quicksort, and tree algorithms.

def binary_search(arr, target):
    left, right = 0, len(arr) - 1
    while left <= right:
        mid = (left + right) // 2
        if arr[mid] == target: return mid
        if arr[mid] < target: left = mid + 1
        else: right = mid - 1
    return -1

print(binary_search([1, 3, 5, 7, 9], 7))

It relies on knowing which half the target is in based on comparison.

Bubble sort repeatedly compares adjacent elements and swaps them if out of order — the largest 'bubbles up' to the end each pass. It's O(n²), slow for real use, but the clearest introduction to how sorting works. Learning bubble sort first makes merge sort and quicksort's improvements obvious. It's a teaching tool, not a production algorithm.

def bubble_sort(arr):
    n = len(arr)
    for i in range(n):
        for j in range(n - 1 - i):
            if arr[j] > arr[j + 1]:
                arr[j], arr[j + 1] = arr[j + 1], arr[j]
    return arr

print(bubble_sort([5, 2, 8, 1, 3]))

1 swap.

Selection sort finds the smallest element and swaps it to the front, then repeats for the rest. It makes fewer swaps than bubble sort (O(n) swaps vs O(n²)), but still O(n²) comparisons. It's simple, in-place, and teaches the 'select the best remaining' pattern. Like bubble sort, it's for learning, not production.

def selection_sort(arr):
    n = len(arr)
    for i in range(n):
        min_idx = i
        for j in range(i + 1, n):
            if arr[j] < arr[min_idx]:
                min_idx = j
        arr[i], arr[min_idx] = arr[min_idx], arr[i]
    return arr

print(selection_sort([5, 2, 8, 1, 3]))

O(n²).

Insertion sort builds the sorted array one element at a time, inserting each into its correct position — like sorting playing cards in your hand. It's O(n²) worst-case but O(n) on nearly-sorted data, making it adaptive. It's actually used in practice for small arrays inside faster algorithms (like Timsort, Python's built-in sort).

def insertion_sort(arr):
    for i in range(1, len(arr)):
        key = arr[i]
        j = i - 1
        while j >= 0 and arr[j] > key:
            arr[j + 1] = arr[j]
            j -= 1
        arr[j + 1] = key
    return arr

print(insertion_sort([5, 2, 8, 1, 3]))

O(n).

Recursion is a function calling itself with a smaller version of the problem until it hits a base case. Every recursive solution needs: (1) a base case that stops, (2) a recursive step that shrinks toward it. Recursion is the natural way to express divide-and-conquer, tree traversal, and dynamic programming. It's tricky at first, but it's the gateway to advanced algorithms.

def factorial(n):
    if n <= 1: return 1        # base case
    return n * factorial(n - 1)  # recursive step

print(factorial(5))

def sum_to(n):
    if n <= 0: return 0
    return n + sum_to(n - 1)

Stacks are Last-In-First-Out (LIFO) — like a stack of plates; queues are First-In-First-Out (FIFO) — like a line of people. Stacks power undo/redo, function calls (the call stack), and depth-first search. Queues power BFS, task scheduling, and print spoolers. These two data structures are the simplest but most fundamental — they appear everywhere.

# Stack (LIFO)
stack = []
stack.append(1); stack.append(2); stack.append(3)
print(stack.pop())  # 3

# Queue (FIFO)
from collections import deque
queue = deque()
queue.append(1); queue.append(2); queue.append(3)
print(queue.popleft())  # 1

A stack (LIFO).

A linked list is a chain of nodes, each storing data and a pointer to the next. Unlike arrays (contiguous memory), linked lists can grow and shrink freely, and insert/delete in O(1) at known positions. The trade-off: O(n) access (no indexing). They're the foundation for more complex structures like stacks, queues, and graphs.

class Node:
    def __init__(self, data):
        self.data = data
        self.next = None

class LinkedList:
    def __init__(self):
        self.head = None
    def append(self, data):
        new = Node(data)
        if not self.head:
            self.head = new
            return
        cur = self.head
        while cur.next: cur = cur.next
        cur.next = new
    def print_list(self):
        cur = self.head
        while cur:
            print(cur.data, end=' ')
            cur = cur.next

ll = LinkedList()
for x in [1, 2, 3]: ll.append(x)
ll.print_list()

O(n) — must traverse from the head.

A hash table maps keys to values by hashing the key to an index — giving O(1) average lookup, insert, and delete. Python's dict and set are hash tables. This is the single most important data structure for performance: converting O(n²) problems to O(n) with a 'seen' set. Collisions (two keys, same index) are handled by chaining or probing.

# O(1) lookups
phonebook = {'Ali': '0300-111', 'Sara': '0301-222'}
print(phonebook['Ali'])  # instant, no looping

# Set for O(1) membership
seen = set()
for x in [1, 2, 3, 1, 2]:
    seen.add(x)
print(seen)

O(1).

BFS explores level by level using a queue — first the root, then all neighbors, then their neighbors. It finds the SHORTEST path in unweighted graphs and is the backbone of many algorithms. The pattern: enqueue start, dequeue and visit, enqueue unvisited neighbors, repeat. BFS is how GPS finds routes, how social networks find connections, and how web crawlers explore.

from collections import deque

def bfs(graph, start):
    visited = set([start])
    queue = deque([start])
    while queue:
        node = queue.popleft()
        print(node, end=' ')
        for neighbor in graph[node]:
            if neighbor not in visited:
                visited.add(neighbor)
                queue.append(neighbor)

graph = {1:[2,3], 2:[4], 3:[5], 4:[], 5:[]}
bfs(graph, 1)

A queue (FIFO).

DFS explores as deep as possible before backtracking — using recursion (or an explicit stack). It's the natural traversal for trees, and solves problems like cycle detection, topological sort, and connected components. The pattern: visit a node, recursively visit each unvisited neighbor. DFS is elegant in code because recursion naturally implements the stack.

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

graph = {1:[2,3], 2:[4], 3:[5], 4:[], 5:[]}
dfs(graph, 1)

DFS.

The two-pointers technique uses two indices moving toward each other (or same direction) to solve problems in one pass. Classic example: find a pair that sums to a target in a sorted array — left pointer at start, right at end, move them based on the sum. It turns naive O(n²) into O(n). This is one of the most common patterns in coding interviews.

def two_sum_sorted(arr, target):
    left, right = 0, len(arr) - 1
    while left < right:
        current = arr[left] + arr[right]
        if current == target: return (left, right)
        if current < target: left += 1
        else: right -= 1
    return None

print(two_sum_sorted([1, 2, 4, 6, 9], 10))

O(n).

The sliding window maintains a 'window' over an array and slides it, updating results incrementally instead of recomputing from scratch. Classic example: max sum of k consecutive elements — instead of summing k elements every time (O(n·k)), add the next and subtract the previous (O(n)). It's the key pattern for subarray and substring problems.

def max_subarray_sum(arr, k):
    window = sum(arr[:k])
    max_sum = window
    for i in range(k, len(arr)):
        window += arr[i] - arr[i - k]
        max_sum = max(max_sum, window)
    return max_sum

print(max_subarray_sum([1, 4, 2, 10, 3, 1], 3))

O(n).

Dynamic programming (DP) solves problems by breaking them into overlapping subproblems and caching results — so you compute each once, not repeatedly. Naive recursive Fibonacci is O(2ⁿ); memoized DP is O(n). The pattern: recursive solution + a cache (memo) for already-computed values. DP is the hardest beginner topic, but it's THE core of algorithmic problem-solving.

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

print(fib_memo(50))

It recomputes the same subproblems exponentially many times.

Greedy algorithms make the best LOCAL choice at each step, hoping it leads to a global optimum. They're fast and simple — but only correct when the problem has 'greedy property' (local best = global best). Classic example: coin change with certain denominations, activity selection, Huffman coding. The skill is knowing when greedy applies and when you need DP instead.

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

print(coin_change([1, 5, 10, 25], 63))

Local optimal choices may not lead to the global optimum.

Divide and conquer splits a problem into smaller subproblems, solves them recursively, then combines the results. Binary search and merge sort are the canonical examples. The pattern: divide → conquer → combine. This is the thinking behind most efficient algorithms — breaking big problems into manageable halves.

def find_max_dc(arr):
    if len(arr) == 1: return arr[0]  # base
    mid = len(arr) // 2
    left_max = find_max_dc(arr[:mid])    # divide
    right_max = find_max_dc(arr[mid:])   # conquer
    return max(left_max, right_max)       # combine

print(find_max_dc([3, 7, 2, 9, 5]))

Merge sort.

Your capstone: solve a real problem using your full toolkit. Count word frequencies (hash table), find the most common word (greedy/iteration), sort results (sorting), and verify with binary search. You'll choose the right data structures and algorithms, analyze complexity, and document your choices. This is what real algorithm work looks like — pattern recognition + complexity analysis.

from collections import Counter

def top_words(text, k):
    counts = Counter(text.lower().split())  # hash table
    return counts.most_common(k)            # sort + select

result = top_words('the cat and the dog and the bird', 2)
print(result)

O(n) — one pass with O(1) hash lookups.