Python Algorithms: From Basics to Proofs

1. Foundations

We use \(\tilde{O}\) to hide log factors. Master theorem in Ch.4 handles recurrences like \(T(n)=2T(n/2)+O(n) \Rightarrow O(n\log n)\).

2. Sorting

Bubble Sort — \(O(n^2)\), stable

Invariant: after k passes, last k elements are in final position.

def bubble_sort(a):
    n = len(a)
    for i in range(n):
        swapped = False
        for j in range(0, n - i - 1):
            if a[j] > a[j+1]:
                a[j], a[j+1] = a[j+1], a[j]
                swapped = True
        if not swapped:
            break
    return a

Insertion Sort — \(O(n^2)\) worst, \(O(n)\) best, stable

Proof sketch: Invariant keeps prefix sorted; inserting preserves order.

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

Selection Sort — \(O(n^2)\), not stable

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

Merge Sort — \(O(n \log n)\), stable

Correctness: merge combines two sorted lists; induction on size.

def merge_sort(a):
    if len(a) <= 1:
        return a
    mid = len(a)//2
    left = merge_sort(a[:mid])
    right = merge_sort(a[mid:])
    return merge(left, right)

def merge(l, r):
    i = j = 0
    out = []
    while i < len(l) and j < len(r):
        if l[i] <= r[j]:
            out.append(l[i]); i += 1
        else:
            out.append(r[j]); j += 1
    out.extend(l[i:]); out.extend(r[j:])
    return out

Quicksort — \(O(n \log n)\) avg, \(O(n^2)\) worst, not stable

def quicksort(a):
    if len(a) <= 1:
        return a
    pivot = a[len(a)//2]
    left = [x for x in a if x < pivot]
    mid = [x for x in a if x == pivot]
    right = [x for x in a if x > pivot]
    return quicksort(left) + mid + quicksort(right)

Heap Sort — \(O(n \log n)\), not stable

import heapq

def heap_sort(a):
    h = a[:]
    heapq.heapify(h)
    return [heapq.heappop(h) for _ in range(len(h))]

Python's Timsort

# sorted() and list.sort() use Timsort: stable, O(n log n) worst, O(n) best
data = [{"city":"Tbilisi","t":21},{"city":"Kutaisi","t":19}]
by_temp = sorted(data, key=lambda d: d["t"])  # stable

Stability: equal keys keep original order. Needed for multi-pass sorts.

3. Searching

Linear Search — \(O(n)\)

def linear_search(a, x):
    for i, v in enumerate(a):
        if v == x:
            return i
    return -1

Binary Search — \(O(\log n)\)

Proof of \(O(\log n)\): each step halves interval size \(n \to n/2 \to n/4 \dots\) After \(k\) steps \(n/2^k \le 1 \Rightarrow k \ge \log_2 n\).

def binary_search(a, x):
    lo, hi = 0, len(a)-1
    while lo <= hi:
        mid = (lo + hi)//2
        if a[mid] == x: return mid
        elif a[mid] < x: lo = mid + 1
        else: hi = mid - 1
    return -1

def binary_search_rec(a, x, lo=0, hi=None):
    if hi is None: hi = len(a)-1
    if lo > hi: return -1
    mid = (lo+hi)//2
    if a[mid] == x: return mid
    return binary_search_rec(a, x, mid+1, hi) if a[mid] < x else binary_search_rec(a, x, lo, mid-1)

4. Recursion and Divide & Conquer

def fact(n): 
    return 1 if n <= 1 else n * fact(n-1)

Fibonacci: three ways

def fib_naive(n):
    return n if n < 2 else fib_naive(n-1) + fib_naive(n-2)  # O(2^n)

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_memo(n):
    return n if n < 2 else fib_memo(n-1) + fib_memo(n-2)  # O(n)

def fib_iter(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a  # O(n), O(1) space

Master Theorem

For \(T(n)=aT(n/b)+f(n)\): if \(f(n)=O(n^{\log_b a - \epsilon})\) then \(T(n)=\Theta(n^{\log_b a})\). Merge sort: \(a=2,b=2,f(n)=O(n) \Rightarrow T(n)=\Theta(n\log n)\).

5. Dynamic Programming

Optimal substructure: optimal solution contains optimal subsolutions. Overlapping subproblems: reuse results.

0/1 Knapsack — bottom-up

def knapsack(W, wt, val):
    n = len(wt)
    dp = [[0]*(W+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for w in range(W+1):
            if wt[i-1] <= w:
                dp[i][w] = max(val[i-1] + dp[i-1][w-wt[i-1]], dp[i-1][w])
            else:
                dp[i][w] = dp[i-1][w]
    return dp[n][W]

Longest Common Subsequence

def lcs(a, b):
    n, m = len(a), len(b)
    dp = [[0]*(m+1) for _ in range(n+1)]
    for i in range(1, n+1):
        for j in range(1, m+1):
            if a[i-1] == b[j-1]:
                dp[i][j] = dp[i-1][j-1] + 1
            else:
                dp[i][j] = max(dp[i-1][j], dp[i][j-1])
    return dp[n][m]

Coin Change (min coins)

def coin_change(coins, amount):
    INF = amount + 1
    dp = [INF]*(amount+1)
    dp[0] = 0
    for c in coins:
        for x in range(c, amount+1):
            dp[x] = min(dp[x], dp[x-c] + 1)
    return dp[amount] if dp[amount] != INF else -1

6. Graph Algorithms

from collections import deque
import heapq

def bfs(graph, start):
    q = deque([start]); visited = {start}; parent = {start: None}
    order = []
    while q:
        u = q.popleft(); order.append(u)
        for v in graph.get(u, []):
            if v not in visited:
                visited.add(v); parent[v] = u; q.append(v)
    return order, parent

def dfs(graph, start):
    stack = [start]; visited = set(); order=[]
    while stack:
        u = stack.pop()
        if u in visited: continue
        visited.add(u); order.append(u)
        for v in reversed(graph.get(u, [])):
            if v not in visited: stack.append(v)
    return order

Dijkstra — \(O((V+E)\log V)\)

Greedy proof sketch: when node u is extracted with smallest distance, any alternative path must go through a node with distance ≥ dist[u], so cannot improve.

def dijkstra(graph, start):
    # graph: {u: [(v,w), ...]}
    dist = {start: 0}
    pq = [(0, start)]
    while pq:
        d, u = heapq.heappop(pq)
        if d != dist[u]: continue
        for v, w in graph.get(u, []):
            nd = d + w
            if nd < dist.get(v, float('inf')):
                dist[v] = nd
                heapq.heappush(pq, (nd, v))
    return dist

A* Search

def astar(graph, start, goal, h):
    # h(u) admissible heuristic
    pq = [(h(start), 0, start)]
    g = {start:0}; parent={start:None}
    while pq:
        _, d, u = heapq.heappop(pq)
        if u == goal: break
        for v, w in graph.get(u, []):
            nd = d + w
            if nd < g.get(v, float('inf')):
                g[v] = nd
                parent[v] = u
                heapq.heappush(pq, (nd + h(v), nd, v))
    return g, parent

7. Greedy Algorithms

Activity Selection

def activity_selection(intervals):
    # intervals: list of (start, end)
    intervals = sorted(intervals, key=lambda x: x[1])
    chosen = []; last_end = -float('inf')
    for s, e in intervals:
        if s >= last_end:
            chosen.append((s,e)); last_end = e
    return chosen  # max size set of non-overlapping

Exchange proof: Let G be greedy pick with earliest finish. Any optimal O can replace its first activity with G without losing feasibility, then induct.

Huffman Coding

import heapq
from collections import Counter

def huffman(freq):
    pq = [[w, [ch, ""]] for ch, w in freq.items()]
    heapq.heapify(pq)
    while len(pq) > 1:
        lo = heapq.heappop(pq); hi = heapq.heappop(pq)
        for pair in lo[1:]: pair[1] = '0' + pair[1]
        for pair in hi[1:]: pair[1] = '1' + pair[1]
        heapq.heappush(pq, [lo[0]+hi[0]] + lo[1:] + hi[1:])
    return dict(heapq.heappop(pq)[1:])

# example
freq = Counter("abracadabra")
codes = huffman(freq)

8. Pythonic Toolbox

from bisect import bisect_left, bisect_right
import heapq
from collections import Counter, defaultdict, deque
import itertools

# 1) bisect – maintain sorted list
nums = [10,20,30]
i = bisect_left(nums, 25)  # 2
nums.insert(i, 25)

# 2) heapq – top-k
top3 = heapq.nlargest(3, [5,1,9,3,7])

# 3) Counter – frequencies
c = Counter(["tbilisi","batumi","tbilisi"])
most = c.most_common(1)

# 4) defaultdict – grouping
by_city = defaultdict(list)
for rec in [{"city":"Tbilisi"},{"city":"Batumi"}]:
    by_city[rec["city"]].append(rec)

# 5) itertools – combos/perms
pairs = list(itertools.combinations([1,2,3,4], 2))

# 6) sorting with key, stable multi-sort
people = [{"name":"Nino","age":44},{"name":"Giorgi","age":44},{"name":"Ana","age":30}]
people.sort(key=lambda p: p["name"])  # secondary
people.sort(key=lambda p: p["age"])   # primary – stable keeps name order for ties

Interactive Demo A — Sorting Visualizer

Interactive Demo B — Binary Search Stepper

lo, hi = 0, len(a)-1
while lo <= hi:
    mid = (lo+hi)//2
    if a[mid] == x: return mid
    elif a[mid] < x: lo = mid+1
    else: hi = mid-1

Interactive Demo C — Pathfinding Playground (20×20)

# BFS core (Python)
from collections import deque
def bfs(grid, start, goal):
    q = deque([start]); parent = {start: None}; visited = {start}
    while q:
        u = q.popleft()
        if u == goal: break
        for v in neighbors(grid, u):
            if v not in visited and not wall(grid, v):
                visited.add(v); parent[v]=u; q.append(v)
    return parent