Brute Force, Greedy & Thuật toán ngẫu nhiênBrute Force, Greedy & Randomised Algorithms

Part of the Data Structures & Algorithms Roadmap knowledge base.

Overview

Everything up to this point in the roadmap has been about structures — how to lay data out so that a particular operation is fast. This topic is the first of the techniques: general strategies for attacking a problem you have never seen before. The roadmap groups them under “Problem Solving Techniques,” and the useful thing about that grouping is that it is small. There are roughly six strategies, they compose, and almost every algorithm you will meet is one of them or a hybrid.

The three covered here sit at the extremes of a trade-off between guaranteed correctness and cost.

Brute force enumerates every candidate solution and checks each one. It is always correct, requires no cleverness, and is very often too slow — but “very often” is not “always,” and knowing when brute force is genuinely the right answer is a real skill. It is also the reference implementation you test your clever algorithm against.

Greedy makes the locally optimal choice at each step and never reconsiders. It is fast — usually a sort plus a linear pass — but it is only correct when the problem has a specific structure. The interesting part of greedy algorithms is not writing them (they are three lines) but proving they work, and the standard tool for that is the exchange argument. A greedy algorithm applied to a problem that does not have the required structure produces answers that look plausible and are wrong, which is worse than being obviously slow.

Randomised algorithms flip coins. They give up determinism in exchange for either simplicity, speed, or immunity to adversarial input. The critical distinction is between Las Vegas algorithms (always correct, random running time) and Monte Carlo algorithms (fixed running time, small probability of a wrong answer) — because those two failure modes need completely different risk assessments in production.

Fundamentals

The catalogue of problem-solving techniques

The decision procedure that actually works in practice:

1. Write the brute force first. It is correct by construction, it clarifies what the problem actually asks, and it becomes your test oracle.
2. Ask whether greedy works. If you can state a greedy choice and prove it by exchange, you are done and the solution is fast.
3. If greedy fails, ask whether subproblems overlap. If yes, dynamic programming. If no, divide and conquer.
4. If the problem is a constraint satisfaction with a huge space, backtrack with pruning.
5. If the worst case is adversarial or the space is too large to enumerate, randomise.

Brute force

A brute-force (exhaustive search) algorithm generates every element of the candidate space and tests each against the problem’s requirements. There is no insight involved, which is exactly the point: it works on any problem whose candidate space you can enumerate.

from itertools import combinations

def subset_sum_brute(nums, target):
    """Find a subset summing to target by trying all 2^n subsets. Theta(2^n · n)."""
    for size in range(len(nums) + 1):
        for combo in combinations(nums, size):
            if sum(combo) == target:
                return list(combo)
    return None

print(subset_sum_brute([3, 34, 4, 12, 5, 2], 9))     # [4, 5]

itertools.combinations hides the enumeration, so here is the same search written with a bitmask, which shows the mechanics — each integer from 0 to 2ⁿ − 1 is a subset, with bit i meaning “include nums[i]”:

def subset_sum_bitmask(nums, target):
    """Same search, enumeration made explicit. n must be <= ~25 to be practical."""
    n = len(nums)
    for mask in range(1 << n):             # 2^n candidate subsets
        total = 0
        for i in range(n):
            if mask & (1 << i):            # bit i set -> nums[i] is in this subset
                total += nums[i]
        if total == target:
            return [nums[i] for i in range(n) if mask & (1 << i)]
    return None

Combinatorial explosion is the reason brute force usually loses. At a generous 10⁹ operations per second:

The jump from n = 40 to n = 50 for 2ⁿ — 18 minutes to 13 days — is the whole story. Exponential growth means buying a machine 1000× faster buys you about 10 more elements.

When brute force is actually the right answer:

• n is small and bounded by the problem. Eight queens, a Sudoku grid, a 3×3 puzzle, “at most 12 warehouses.” If the input can never grow, asymptotics are irrelevant.
• It is a test oracle. Your O(n log n) sweep-line has an off-by-one; the O(n³) brute force does not. Cross-check them on 10 000 random small inputs — this is the single highest-value use of brute force in real engineering.
• The clever algorithm does not exist or is not worth writing. For an internal tool run once a week on 500 rows, an O(n²) double loop that takes 0.2 s is correct engineering. Optimizing it is not.
• It is the base you then prune. Backtracking is brute force with pruning; branch and bound is brute force with a bound. Both start from the exhaustive enumeration and cut branches — you cannot write them without first knowing what the full search space is.

When it is a bad idea: any time n is user-controlled and unbounded. An O(2ⁿ) path that a user can trigger with a 60-element input is a denial-of-service vulnerability, not a performance problem. The classic instance is catastrophic backtracking in regular expressions — (a+)+b against a string of 30 as explores exponentially many ways to split the input.

Branch and bound is the systematic improvement on brute force for optimization problems: keep the best solution found so far, compute an optimistic bound on what any completion of the current partial solution could achieve, and abandon the branch if that bound cannot beat the incumbent. For the travelling salesperson problem, “current path cost + a lower bound on the remaining edges ≥ best tour found” prunes enormous parts of the tree while still guaranteeing the optimum. Worst case is still factorial; typical case is dramatically better.

Key Concepts

Greedy algorithms

A greedy algorithm builds a solution incrementally, at each step taking the choice that looks best right now, according to some local criterion, and never revisiting it. There is no backtracking and no table of subproblems, which is why greedy algorithms are both the fastest technique and the one most likely to be silently wrong.

Two properties must hold for a greedy algorithm to be correct:

1. Greedy choice property — a globally optimal solution can be reached by making the locally optimal choice. Formally: there exists an optimal solution that contains the greedy choice. This is the hard one, and it is what the exchange argument proves.
2. Optimal substructure — after committing to the greedy choice, the remaining problem is a smaller instance of the same problem, and an optimal solution to the whole contains an optimal solution to that remainder. (Shared with dynamic programming; DP needs it too.)

The difference from DP is worth stating precisely: DP considers all choices at each step and picks the best after evaluating the consequences; greedy commits to one choice without evaluating the alternatives. Greedy is DP where you have proved you only ever need to look at one branch.

The exchange argument — how to prove a greedy correct

The exchange argument is the standard proof technique, and it always has the same shape:

1. Let G be the greedy solution and O be any optimal solution.
2. Find the first place they differ.
3. Show you can exchange O’s choice at that point for G’s choice without making O worse (and without breaking feasibility).
4. Repeating the exchange transforms O into G without ever losing optimality, so G is optimal too.

Applied to activity selection (choose the maximum number of mutually non-overlapping intervals): the greedy rule is always take the activity that finishes earliest among those still compatible.

• Let O be an optimal set, and let a be the activity in O with the earliest finish time. Let g be the globally earliest-finishing activity.
• By definition finish(g) ≤ finish(a).
• Replace a with g in O. Every other activity in O started at or after finish(a) ≥ finish(g), so none of them conflicts with g. The set is still feasible and still has the same size.
• So there is an optimal solution containing the greedy choice. Recurse on the remaining activities that start after finish(g) — that is the optimal substructure — and induction finishes the proof.

def activity_selection(intervals):
    """Maximum number of non-overlapping intervals. Theta(n log n), dominated by the sort."""
    # Greedy criterion: earliest finish time. Sorting by START or by DURATION both fail.
    ordered = sorted(intervals, key=lambda iv: iv[1])
    chosen, last_end = [], float("-inf")
    for start, end in ordered:
        if start >= last_end:              # compatible with everything picked so far
            chosen.append((start, end))
            last_end = end
    return chosen

meetings = [(1, 4), (3, 5), (0, 6), (5, 7), (3, 9), (5, 9), (6, 10), (8, 11), (12, 16)]
print(activity_selection(meetings))
# [(1, 4), (5, 7), (8, 11), (12, 16)]  -> 4 activities

Note how easy it is to get the criterion wrong. Sorting by start time picks (0, 6) first and yields 3 activities. Sorting by shortest duration fails on [(0, 5), (4, 6), (5, 10)] — it picks the middle one and blocks both others. The greedy rule is the thing you have to prove; the code is trivial once you have it.

Canonical greedy wins

Fractional knapsack — take items by value-to-weight ratio, splitting the last one:

def fractional_knapsack(items, capacity):
    """items: list of (value, weight). Returns max value. Theta(n log n)."""
    # Greedy criterion: highest value density first. Provably optimal BECAUSE items divide.
    ordered = sorted(items, key=lambda it: it[0] / it[1], reverse=True)
    total, remaining = 0.0, capacity
    for value, weight in ordered:
        if remaining == 0:
            break
        take = min(weight, remaining)      # take all of it, or the fraction that fits
        total += value * (take / weight)
        remaining -= take
    return total

print(fractional_knapsack([(60, 10), (100, 20), (120, 30)], 50))   # 240.0

The exchange argument: if an optimal solution takes less of the highest-density item than the greedy does, swap a unit of some lower-density item for a unit of the higher-density one. Same weight, no less value. Divisibility is what makes the swap always possible — and it is exactly what the 0/1 version removes.

Huffman coding — build an optimal prefix-free code by repeatedly merging the two least frequent symbols:

import heapq
from collections import Counter

def huffman_codes(text):
    """Optimal prefix-free code. Theta(n log n) for n distinct symbols."""
    freq = Counter(text)
    if len(freq) == 1:                     # edge case: one symbol needs one bit anyway
        return {next(iter(freq)): "0"}

    # Heap entries: (frequency, tiebreak, {symbol: code_suffix_so_far})
    tiebreak = 0
    heap = []
    for symbol, f in freq.items():
        heapq.heappush(heap, (f, tiebreak, {symbol: ""}))
        tiebreak += 1

    while len(heap) > 1:
        # Greedy choice: the two rarest symbols get the longest codes, so merge them first
        f1, _, left = heapq.heappop(heap)
        f2, _, right = heapq.heappop(heap)
        merged = {s: "0" + c for s, c in left.items()}
        merged.update({s: "1" + c for s, c in right.items()})
        heapq.heappush(heap, (f1 + f2, tiebreak, merged))
        tiebreak += 1

    return heap[0][2]

codes = huffman_codes("abracadabra")
print(sorted(codes.items(), key=lambda kv: (len(kv[1]), kv[0])))
# [('a', '0'), ('b', '110'), ('c', '100'), ('d', '101'), ('r', '111')]
# 'a' (5 occurrences) gets a 1-bit code; 'c' and 'd' (1 each) get 3-bit codes

The exchange argument here: in any optimal prefix code, the two least frequent symbols can be assumed to be siblings at the deepest level — if they were not, swapping them with whatever is down there does not increase the weighted code length. Merging them is therefore safe. heapq is the right tool in production; it costs O(log n) per push/pop and O(n) to heapify — see ./12-heaps-and-priority-queues.md.

Kruskal’s MST — sort edges by weight, add each edge that does not create a cycle. Correct by the cut property: for any partition of the vertices, the minimum-weight edge crossing the cut is in some MST. See ./15-minimum-spanning-trees.md and ./16-disjoint-set-union-find.md.

Dijkstra’s shortest path — repeatedly finalise the unvisited vertex with the smallest tentative distance. The greedy choice is provably safe only because edge weights are non-negative: once a vertex is the closest unfinalised one, no later path through a farther vertex can improve it. Introduce one negative edge and the proof collapses — which is exactly why Bellman–Ford exists. See ./14-shortest-path-algorithms.md.

When greedy fails — two concrete counterexamples

0/1 knapsack. Same items as the fractional version, but now each item is all-or-nothing:

def knapsack_greedy_WRONG(items, capacity):
    """Greedy by density on the 0/1 knapsack. Fast, plausible, and incorrect."""
    ordered = sorted(items, key=lambda it: it[0] / it[1], reverse=True)
    total, remaining = 0, capacity
    for value, weight in ordered:
        if weight <= remaining:            # cannot take a fraction any more
            total += value
            remaining -= weight
    return total

def knapsack_dp(items, capacity):
    """Correct 0/1 knapsack by DP. Theta(n · capacity) time, Theta(capacity) space."""
    best = [0] * (capacity + 1)
    for value, weight in items:
        for c in range(capacity, weight - 1, -1):    # descending: each item used once
            best[c] = max(best[c], best[c - weight] + value)
    return best[capacity]

items = [(60, 10), (100, 20), (120, 30)]             # (value, weight)
print(knapsack_greedy_WRONG(items, 50))              # 160  <- wrong
print(knapsack_dp(items, 50))                        # 220  <- correct
print(fractional_knapsack(items, 50))                # 240.0 (fractional is a different problem)

Greedy takes the density-6 item (10 kg, value 60), then the density-5 item (20 kg, value 100), reaching 160 with 20 kg of capacity left — and the 30 kg item no longer fits. The optimum skips the first item entirely and takes the 20 kg and 30 kg items for 220. The greedy choice property fails: no optimal solution contains the greedy first choice. Indivisibility is the whole difference, and the fix is dynamic programming.

Coin change with awkward denominations. Greedy “take the largest coin that fits” is optimal for US and Euro coin systems, which is why it feels universally right. It is not:

def coin_change_greedy(coins, amount):
    """Take the largest coin that fits. Optimal only for 'canonical' coin systems."""
    count, remaining = 0, amount
    for coin in sorted(coins, reverse=True):
        take = remaining // coin
        count += take
        remaining -= take * coin
    return count if remaining == 0 else None

def coin_change_dp(coins, amount):
    """Correct minimum-coin count for ANY denominations. Theta(len(coins) · amount)."""
    INF = float("inf")
    best = [0] + [INF] * amount
    for value in range(1, amount + 1):
        for coin in coins:
            if coin <= value and best[value - coin] + 1 < best[value]:
                best[value] = best[value - coin] + 1
    return None if best[amount] == INF else best[amount]

print(coin_change_greedy([1, 3, 4], 6))   # 3   -> 4 + 1 + 1
print(coin_change_dp([1, 3, 4], 6))       # 2   -> 3 + 3
print(coin_change_greedy([1, 7, 10], 15)) # 6   -> 10 + 1*5
print(coin_change_dp([1, 7, 10], 15))     # 3   -> 7 + 7 + 1

With coins {1, 3, 4} and amount 6, greedy takes 4 then two 1s — three coins — while 3 + 3 is two. The greedy is not just suboptimal, it is confidently suboptimal, and it will pass every test written with real-world denominations. This is the practical danger of greedy: the failure mode is a wrong answer that looks right, not a crash or a timeout. Determining whether a coin system is “canonical” (greedy-optimal) is itself a non-trivial problem, and the safe engineering answer is to use DP unless the denominations are fixed and you have verified greedy against DP on the whole range.

Nearest-neighbour TSP rounds out the picture: always visiting the nearest unvisited city produces tours that can be a Θ(log n) factor worse than optimal, and on adversarial inputs arbitrarily worse. It is still useful — as a fast starting tour for a local-search algorithm — which is the honest role of a failed greedy: a heuristic, clearly labelled as such.

Randomised algorithms

A randomised algorithm uses random numbers as part of its logic, so the same input can produce different execution paths on different runs. The reason to accept that non-determinism is usually one of three:

• To defeat adversarial input. A deterministic algorithm has a fixed worst case, and an attacker who knows the code can construct it. A randomised one has no input that is reliably bad.
• To simplify. Randomised algorithms for problems like min-cut or primality are dramatically simpler than their deterministic counterparts.
• To sample. When the space is too large to enumerate, sampling is the only option.

Las Vegas vs Monte Carlo

The distinction matters operationally. A Las Vegas algorithm that occasionally takes 3× longer is a latency problem you can measure and cap with a timeout. A Monte Carlo algorithm that is wrong 1 in 10⁶ times is a correctness problem that will not show up in testing and will show up in production. Before shipping a Monte Carlo algorithm, work out the actual error probability, decide whether the consequence of a wrong answer is acceptable, and repeat the algorithm enough times to push δ below that threshold. Miller–Rabin with k independent bases has error ≤ 4^(−k); at k = 40 that is below the probability of a cosmic-ray bit flip, which is why it is used for real cryptographic key generation.

Randomised quicksort — the archetypal Las Vegas algorithm

Deterministic quicksort with a fixed pivot rule (always take the first element) is Θ(n²) on already-sorted input — the single most common shape of real data. Choosing the pivot at random makes the expected time Θ(n log n) for every input, because the randomness lives in the algorithm rather than the data.

import random

def quicksort_random(arr):
    """Expected Theta(n log n) on ANY input. Worst case Theta(n^2) but probability ~0."""
    if len(arr) <= 1:
        return arr[:]
    pivot = random.choice(arr)                       # the only random decision
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]
    return quicksort_random(less) + equal + quicksort_random(greater)

Why the expectation works out: a random pivot splits the array at least 25/75 with probability 1/2, and a run of 25/75 splits still gives O(log n) depth (log_{4/3} n). Summing the expected comparisons gives 2n ln n ≈ 1.39 n log₂ n. The worst case is still Θ(n²), but reaching it requires the random number generator to conspire — probability roughly 1/n! — rather than requiring the input to be unlucky. That shift is the entire point: randomisation converts a worst case over inputs into a worst case over coin flips, and you control the coins.

Quickselect — expected linear-time selection

def quickselect(arr, k):
    """k-th smallest element, 0-indexed. Expected Theta(n), worst case Theta(n^2)."""
    if len(arr) == 1:
        return arr[0]
    pivot = random.choice(arr)
    less = [x for x in arr if x < pivot]
    equal = [x for x in arr if x == pivot]
    greater = [x for x in arr if x > pivot]

    if k < len(less):
        return quickselect(less, k)                  # recurse into ONE side only
    if k < len(less) + len(equal):
        return pivot
    return quickselect(greater, k - len(less) - len(equal))

data = [7, 10, 4, 3, 20, 15]
print(quickselect(data, 2))      # 7  -> the 3rd smallest

The complexity argument is the geometric series: expected work is n + n/2 + n/4 + … = 2n = Θ(n), because unlike quicksort it recurses into only one partition. Beating the obvious sort-then-index Θ(n log n) by a log n factor. The deterministic alternative — median of medians — is Θ(n) worst case, but its constant factor is large enough that randomised quickselect wins in practice. See ./12-heaps-and-priority-queues.md for the heap-based approach when you want the top k rather than the k-th.

Reservoir sampling — uniform sampling from a stream of unknown length

You are reading a log stream and want k uniformly random lines, but you do not know how many lines there are and cannot hold them all in memory. Reservoir sampling solves this in one pass with O(k) memory:

def reservoir_sample(stream, k):
    """k uniform samples from a stream of unknown length n. O(n) time, O(k) space."""
    reservoir = []
    for i, item in enumerate(stream):
        if i < k:
            reservoir.append(item)                   # fill the reservoir first
        else:
            j = random.randrange(i + 1)              # uniform in [0, i]
            if j < k:                                # keep with probability k/(i+1)
                reservoir[j] = item                  # evict a uniformly chosen incumbent
    return reservoir

print(reservoir_sample(range(1_000_000), 5))         # 5 uniform samples, one pass, O(1) memory

The invariant, proved by induction: after processing i items, every one of them is in the reservoir with probability exactly k/i. Item i+1 enters with probability k/(i+1); an incumbent survives with probability 1 − k/(i+1) · 1/k = 1 − 1/(i+1) = i/(i+1), and k/i · i/(i+1) = k/(i+1). The invariant is preserved. This is the algorithm behind distributed-trace sampling, shuf -n on huge files, and A/B test bucketing over unbounded event streams.

Monte Carlo estimation

The other meaning of “Monte Carlo” is numerical estimation by random sampling — approximating a quantity you cannot compute exactly by averaging over random draws.

def estimate_pi(samples):
    """Fraction of random points in the unit square that land inside the quarter circle
       is pi/4. Error shrinks as O(1/sqrt(samples)) -- 100x more samples, 10x accuracy."""
    inside = 0
    for _ in range(samples):
        x, y = random.random(), random.random()
        if x * x + y * y <= 1.0:
            inside += 1
    return 4.0 * inside / samples

print(estimate_pi(1_000_000))    # ~3.1416, differing run to run

The O(1/√N) convergence is the defining characteristic and the reason Monte Carlo integration is used for high-dimensional problems: that rate is independent of dimension, whereas grid-based numerical integration costs O(N^d). It is why Monte Carlo dominates in finance (option pricing), physics (particle transport), and rendering (path tracing), and why it is a poor choice for a 1-D integral where Simpson’s rule converges far faster.

Randomisation as a defence against adversarial worst cases

This is the deepest practical reason to randomise, and it shows up in production systems constantly:

• Hash flooding. A hash table with a fixed, public hash function degrades from O(1) to O(n) per lookup if an attacker submits keys that all collide — a few thousand crafted POST parameters could pin a web server’s CPU. The fix is a randomly seeded hash (Python uses SipHash with a per-process random seed since 3.3; see PYTHONHASHSEED), so the attacker cannot precompute colliding keys. This is randomisation used purely for security, not speed.
• Quicksort killers. Introsort in C++ and the “median of three” heuristic exist because attackers published inputs that force Θ(n²) in specific library implementations. Randomised pivots remove the attack surface entirely.
• Load balancing — “the power of two choices.” Assigning each request to a randomly chosen server gives a maximum load of Θ(log n / log log n). Picking two servers at random and sending the request to the less loaded one drops it to Θ(log log n) — an exponential improvement from one extra random sample. This result underpins real load balancers and distributed caches; see ../../backend/en/11-caching.md and ../../data-engineer/en/10-big-data-and-distributed-computing.md.
• Skip lists. A skip list achieves the same expected O(log n) bounds as a balanced tree using coin flips for the level of each node, with far simpler code and no rotations. Redis uses one for sorted sets.

One caveat that matters: random is not secrets. Python’s random module is a Mersenne Twister — excellent statistical properties, completely predictable from about 624 outputs. Use it for algorithms; use secrets (or os.urandom) for anything an adversary must not predict, including hash seeds, tokens, and salts.

Best Practices

• Always write the brute force first, and keep it. It defines what “correct” means and becomes the oracle you differential-test the optimized version against on thousands of random small inputs. This catches more bugs than any amount of staring at the clever code.
• Estimate the candidate space before writing brute force in production. 2ⁿ is fine at n = 25, hopeless at n = 50. n! is hopeless past n = 12. Do the arithmetic before, not after.
• Never let an exponential-time path be reachable from unbounded user input. Cap the input size explicitly and return an error. An O(2ⁿ) endpoint is a DoS vulnerability.
• Never ship a greedy algorithm you have not proved or exhaustively tested. “It passed the examples” is not evidence — the coin-change greedy passes every test written with real-world coins. Either construct the exchange argument, or brute-force the entire input space for small n and diff.
• State the greedy criterion explicitly, in a comment. “Sort by finish time” versus “sort by start time” versus “sort by duration” are three different algorithms with three different answers, and only one is correct. The criterion is the algorithm; the loop is boilerplate.
• When greedy fails, check for overlapping subproblems before giving up. 0/1 knapsack, coin change, and longest common subsequence are all greedy-failures that DP solves in polynomial time.
• A failed greedy is still valuable as a heuristic — label it as one. Nearest-neighbour TSP makes a fine starting tour for 2-opt local search. Naming a function knapsack_heuristic rather than knapsack_solve prevents a future reader from assuming optimality.
• Distinguish Las Vegas from Monte Carlo before you deploy. Las Vegas needs a latency budget and a timeout. Monte Carlo needs an error budget and enough repetitions to meet it. Confusing the two means either an unexplained tail latency or an unexplained wrong answer.
• Quantify the error probability of any Monte Carlo algorithm you ship, and write it in the docstring. “Fails with probability ≤ 4⁻⁴⁰” is engineering; “usually right” is not.
• Seed randomness explicitly in tests, never in production. A test that fails once in fifty runs is worse than useless. Use random.Random(seed) instances in tests so failures reproduce; leave production unseeded so the adversarial protection actually works.
• Use secrets/os.urandom, not random, when an adversary must not predict the values. Mersenne Twister is reconstructible from its output; that is fine for pivot selection and fatal for a session token.
• Prefer randomised pivots to “median of three” for quicksort in any code that processes untrusted input. Median of three has published killer sequences; a random pivot does not.
• Remember that randomisation only helps when the randomness is unpredictable to the adversary. A “random” pivot from a fixed seed is deterministic and attackable. This is exactly why Python randomises its hash seed per process.

References

• roadmap.sh — Data Structures & Algorithms
• Brute-force search — Wikipedia
• Combinatorial explosion — Wikipedia
• Greedy algorithm — Wikipedia
• Matroid — Wikipedia (the algebraic structure that characterises when greedy is optimal)
• Huffman coding — Wikipedia
• Knapsack problem — Wikipedia
• Change-making problem — Wikipedia
• Randomized algorithm — Wikipedia
• Las Vegas algorithm — Wikipedia
• Monte Carlo algorithm — Wikipedia
• Reservoir sampling — Wikipedia
• Quickselect — Wikipedia
• Branch and bound — Wikipedia
• CLRS — Introduction to Algorithms, Chapter 16: Greedy Algorithms
• MIT 6.006 — Introduction to Algorithms (OpenCourseWare)
• Python Documentation — random
• Python Documentation — secrets
• Python Documentation — PYTHONHASHSEED
• cp-algorithms — Algorithms index