Algorithm theory

What an algorithm means

An algorithm is a finite, well-defined sequence of instructions that solves a specified problem. It describes the complete method, not a particular programming language. A program implements that method. An input instance supplies the data; the output must satisfy the problem specification for every valid instance.

For example, “find the largest number” is a problem, not a complete algorithm. “Store the first element as the current maximum; inspect each remaining element; replace the maximum when a larger value is found; return the maximum” specifies an executable method for a nonempty array.

Characteristics in the introductory lecture

1. Finiteness: execution takes a finite number of steps for every valid input.
2. Input: zero or more clearly specified input values, with a defined valid range.
3. Output: at least one result related to the input and the required task.
4. Definiteness: every instruction has one precise meaning.
5. Correctness: the result solves the stated problem, not merely a few examples.
6. Unambiguous control: the order of execution, conditions, and repetition are explicit.
7. Termination: the procedure stops by itself rather than looping forever.

The handwritten note additionally calls each step effective: it must be basic enough to carry out in finite time. “Guess the correct answer” is not an effective computational instruction unless the allowed operation and its cost are defined.

Algorithm-design families

Performance, efficiency, and the input-size model

Different correct algorithms can solve the same problem. Their suitability depends on input size, input distribution, memory available, and the required result. The two main resources in the lecture are time and space. A faster method may need more memory; a memory-saving method may repeat calculations. “Efficient” therefore means an appropriate trade-off, not that one algorithm wins in every situation.

Time complexity counts elementary operations under a stated cost model rather than seconds on one computer. Examples are comparisons, additions, assignments, and array accesses. Let n denote array length or string length; for a graph, specify both V and E. Space complexity counts simultaneously live storage. Auxiliary space excludes the input, while total space includes it; state which convention is used. Recursive calls also consume stack space.

A constant-time arithmetic assumption is suitable for fixed-size machine integers. When a value may have arbitrarily many bits, arithmetic is not generally constant time. This matters for large-number algorithms and explains why a bound such as O(nW) for knapsack is called pseudo-polynomial.

Best, worst, and average case are different from asymptotic bounds

For all inputs of size n, the best-case running time is the minimum, the worst-case is the maximum, and the average-case is an expectation under a specified input distribution. In linear search, finding the key first costs Θ(1); finding it last or not finding it costs Θ(n). A uniformly distributed successful position also gives Θ(n) expected comparisons.

Big-O, Ω, and Θ instead compare functions as n grows. They can describe a best-case, worst-case, average-case, or other cost function:

Example: f(n)=3n²+2n+7. For n≥1, 3n²≤f(n)≤12n², so f(n)=Θ(n²). It is also O(n³), but that upper bound is not tight. Constant factors and lower-order terms disappear from the growth class, not from the real program's measured cost.

Reading the growth-rate charts

For sufficiently large n, the typical increasing order is 1 < log n < √n < n < n log n < n² < n³ < 2ⁿ < n!. All logarithms with fixed bases greater than 1 differ by a constant factor. Polynomial time means O(nᵏ) for a fixed constant k; nⁿ is not polynomial time. The charts describe growth, not exact timing or a guarantee that every quadratic program is unusable.

Data-structure operation table, with the missing assumptions stated

The lecture includes an overview table of common structures. An operation must be named before a cost is meaningful; “an array is O(n)” is incomplete. Here is the readable version with conditional entries clarified. Space is O(n) unless a row says otherwise.

Search and sorting comparison from the lecture

These tables are orientation material, not evidence that every listed structure received a full lecture. The taught algorithm chapters below give the actual procedures, conditions, examples, and derivations.

One complete version of the overlapping subset-sum notes

The earlier notebook and TT2 notes use the same instance: values [3,2,6,8,5], target 10. Each item may be selected at most once. Use a binary decision vector in that input order. The two solutions are 11001 ({3,2,5}) and 01010 ({2,8}).

At index k, keep current=sum of selected processed values and remaining=sum of all unprocessed values. Initially (k,current,remaining)=(0,0,24). Including or excluding A[k] always removes A[k] from remaining; only inclusion adds it to current.

Pruning and completeness

• If current>10, stop: positive remaining values cannot reduce it.
• If current+remaining<10, stop: even taking every remaining value is insufficient.
• If current=10, report the current selections and omit all later positive values.
• Otherwise explore both include and exclude branches.

search(k,current,remaining):
    if current > target or current+remaining < target: return
    if current == target:
        output choice[0..k-1] followed by n-k zeroes
        return
    if k == n: return
    choice[k] = 1
    search(k+1,current+A[k],remaining-A[k])
    choice[k] = 0
    search(k+1,current,remaining-A[k])

The entire pruned class tree in readable form

Rows are depth-first, inclusion first. Every child reduces remaining by the next item, even when that child is immediately pruned.

Correctness: every subset has a unique include/exclude path. The two pruning conditions reject only impossible completions under the positive-input assumption, so all remaining valid solutions are found. Worst-case exploration is O(2ⁿ), plus output cost; the decision array and active recursion use O(n) space. The DP alternative trades this exponential dependence for pseudo-polynomial O(nT) time.

Problem, representation, and constraints

Place n queens on an n×n board with no shared row, column, or diagonal. Assign one queen to each row and store its column in x[row]. For a candidate at (r,c), every earlier row q must satisfy x[q]≠c and |x[q]−c|≠r−q.

The notebook's C(16,4)=1820 counts all ways to choose four squares on a 4×4 board, including attacking arrangements; it is not a probability and not the number of solutions. Restricting to one queen per row gives 4⁴=256 candidates. Also requiring distinct columns leaves 4!=24 permutations before diagonal checks. Only two complete nonattacking arrangements remain.

safe(row,col):
    for q = 0 .. row-1:
        if x[q] == col or abs(x[q]-col) == row-q: return false
    return true

place(row):
    if row == n: output x; return
    for col = 0 .. n-1:
        if safe(row,col):
            x[row] = col
            place(row+1)
            x[row] = unassigned

Complete safe-prefix tree for n=4

Columns below are one-based. Unsafe candidates are excluded by the column/diagonal predicate; a dead end causes return to the previous row.

The solutions are [2,4,1,3] and [3,1,4,2], mirror images. These produce the two boards drawn in the overlapping notebook copies.

Cost and implementation choices

There are at most n! complete distinct-column arrangements, and fewer survive diagonals. A common optimized formulation iterates unused columns with constant-time column/diagonal occupancy checks. For the straightforward class implementation, every partial state loops over all n columns and each safety check can scan O(n) previous positions, so O(n²·n!) is a safe implementation-specific upper bound, excluding board-output cost.

A column-position array needs O(n) storage plus O(n) recursion. The class program stores a full n×n board, so its auxiliary storage is O(n²). With occupancy arrays, the two diagonal identifiers are row−col+(n−1) and row+col. There is one solution for n=1, none for n=2 or 3, and two for n=4. Full class code.

Columns:   1 2 3 4            Columns:   1 2 3 4
Row 1:     . Q . .            Row 1:     . . Q .
Row 2:     . . . Q            Row 2:     Q . . .
Row 3:     Q . . .            Row 3:     . . . Q
Row 4:     . . Q .            Row 4:     . Q . .

Positions: [2,4,1,3]          Positions: [3,1,4,2]

Branch, bound, and incumbent

Branch and bound is an exact optimization method. A search node encodes a partial candidate; branching extends it. The incumbent is the best complete feasible solution found so far. An optimistic bound estimates the best objective value any completion of a node could achieve. If even that optimistic value cannot improve the incumbent, the whole subtree may be discarded.

For minimization, a partial state's lower bound is compared with the incumbent's upper bound. For maximization, reverse the roles: compare an optimistic upper bound with the best known feasible value. A bound that is too optimistic may waste work; a bound that incorrectly rules out a better solution destroys correctness.

Classroom shortest-path example

The undirected graph has S–A(3), S–B(6), A–D(2), A–C(7), B–D(3), B–E(6), D–E(2), D–G(4), C–G(2), E–G(1). Start at S and seek G. The trace first obtains S–A–D–G with cost 9, then improves it to S–A–D–E–G with cost 8. Paths already costing 10 or 12 cannot improve either bound because all edge weights are nonnegative.

bestCost = infinity; bestPath = none
Q = FIFO queue containing ([S],0)
while Q not empty:
    (path,cost) = Q.popFront()
    if cost >= bestCost: continue
    u = last vertex of path
    if u == G:
        bestCost = cost; bestPath = path
        continue
    for each neighbor v of u:
        if v not already in path and cost+w(u,v) < bestCost:
            Q.pushBack((path followed by v, cost+w(u,v)))
return bestPath,bestCost

A FIFO queue implements the breadth-first scheduling in the heading. A priority queue ordered by bounds gives a best-first variant; a stack gives depth-first search. The scheduling policy and the correctness of the pruning bound are separate decisions.

Branch and bound can still explore exponentially many candidates when bounds are weak. FIFO storage can be exponential because many live nodes coexist; a depth-first variant saves frontier memory but may find a useful incumbent later. Backtracking normally prunes violated constraints; branch and bound additionally prunes candidates that cannot improve an objective.

What makes an algorithm randomized?

A randomized algorithm deliberately samples random choices during execution. For a fixed input, its running time, output, or both may depend on those choices. This differs from average-case analysis of a deterministic algorithm, where the probability is over input instances rather than internal random bits.

The source page is a sparse topic list (“polynomial”, “exponential”, “approximation”, “randomized”), not a full derivation. The definitions and explanation below complete that topic; they are not claimed to be a verbatim handwritten lecture.

Two guarantee types

For independent trials with failure probability at most p<1, a procedure whose error requires every trial to fail can reduce that probability to at most pᵏ after k repetitions. This multiplication requires independence and the appropriate one-sided/combination rule; it is not automatic for every randomized algorithm.

Randomized quicksort

Choose a pivot uniformly from the current segment, move it to the partition position, partition, and recurse. For distinct keys, each pivot rank is equally likely, so an adversary cannot force bad ranks merely by supplying sorted input. The expected time is Θ(n log n), while worst-case time remains Θ(n²).

One way to see the expected bound is to sort the keys conceptually. Keys of ranks i<j are compared only when one is the first pivot selected from ranks i through j; that probability is 2/(j−i+1). Summing these probabilities over pairs gives Θ(n log n) expected comparisons.

Randomized and approximation algorithms solve different concerns. Randomization describes how choices are made; approximation describes a quality guarantee relative to optimum. An algorithm may be both, either, or neither.

Approximation ratio

Let C be the objective value of a feasible answer returned by an algorithm and C* the optimum. For a minimization problem the ratio is C/C*; for a maximization problem it is C*/C. Under positive objectives the ratio is at least 1, and 1 means optimal. A ρ-approximation proves that the relevant ratio is at most ρ on every valid instance, not just on one example.

The zero-optimum case requires separate handling rather than division by zero. In vertex cover, an edgeless graph has optimum zero and the algorithm below correctly returns the empty set.

Minimum vertex cover

For an undirected graph G=(V,E), a vertex cover C⊆V contains at least one endpoint of every edge. Minimize |C|. This is not a set that merely touches every vertex, nor a path visiting vertices.

The classroom graph has edges AB, BC, CD, DG, CE, EF, DE, DF. A minimum cover is {B,D,E}: B covers AB/BC, D covers CD/DG/DE/DF, and E covers CE/EF. It is optimal because the three disjoint edges AB, CE, DG require at least three distinct selected endpoints.

Maximal-matching 2-approximation

C = empty set
remaining = all graph edges
while remaining is not empty:
    choose any edge (u,v) in remaining
    add u and v to C
    remove every remaining edge incident to u or v
return C

In the class graph, choose BC first: add B,C and remove AB,BC,CD,CE. Then choose DE: add D,E and remove all remaining edges. The returned cover {B,C,D,E} has size 4, while optimum is 3, so this instance's ratio is 4/3. Different arbitrary-edge choices may return different valid covers.

Proof of the factor two

1. The selected edges share no endpoints: once an edge is selected, all incident edges disappear. They form a matching M.
2. Every vertex cover must pick at least one endpoint of each edge in M. Because those edges are disjoint, |C*|≥|M|.
3. The algorithm selects both endpoints of every edge in M, giving |C|=2|M|.
4. Thus |C|≤2|C*|.

The matching only needs to be maximal—no more edge can be added—not maximum-cardinality. A linear scan selecting an edge only when both endpoints are still unselected implements the same construction in O(V+E) time, with O(V) selection state in addition to the graph.

selected[v] = false for every vertex v
cover = []
for each undirected edge (u,v) in the chosen edge order:
    if not selected[u] and not selected[v]:
        selected[u] = selected[v] = true
        append u and v to cover
return cover

Coloring a graph with at most m colors

Assign a color from {1,…,m} to each vertex of an undirected simple graph so that endpoints of every edge receive different colors. The decision problem asks whether such an assignment exists; an enumeration version prints all assignments. It is not necessary that every available color be used.

The class graph is the cycle A–B–C–D–A with diagonal A–C, using colors red, green, blue. The triangle A–B–C requires three distinct colors. Since D is adjacent to A and C but not B, D can have B's color.

Fixing A=red leaves the two valid assignments above; allowing any of the three labels for A gives six labeled assignments. The graph is not 2-colorable because it contains a triangle.

colorVertex(k):
    if k == numberOfVertices: output colors; return
    for c = 1 .. m:
        if every already-colored neighbor of k has color != c:
            colors[k] = c
            colorVertex(k+1)
            colors[k] = unassigned

The state-space tree branches on the color of the next vertex. A conflicting choice is rejected immediately; a safe partial assignment creates a child. When that child finishes, clear the color before trying the next branch. Trying all safe choices guarantees completeness.

There are at most mⁿ complete assignments. If each attempted color scans an n-entry adjacency-matrix row, an O(n·mⁿ) bound describes the usual search-tree cost for fixed m≥2, plus output costs; a loose O(n²mⁿ) bound is also safe. The matrix stores O(n²), colors O(n), and recursion O(n). A self-loop makes proper coloring impossible and must be rejected explicitly if the input is not guaranteed simple. Full class implementation.

Flow network and feasible flow

A flow network is a directed graph with nonnegative capacity c(u,v) on each edge, a source s, and a sink t. In the ordinary edge-flow convention, f(u,v) is the nonnegative amount carried by that directed edge.

1. Capacity: 0≤f(u,v)≤c(u,v) on every original edge.
2. Conservation: for every vertex u other than s,t, Σ incoming f = Σ outgoing f.
3. Flow value: |f|=Σᵥf(s,v)−Σᵥf(v,s), equal to the sink's net inflow.

When no edges enter the source or leave the sink, the value simplifies to source outflow or sink inflow, as in the class example. Conservation still includes edges incident to s or t when summing a nonterminal vertex's incident flow.

Bottleneck and residual capacity

On a path s→a→b→t with capacities 10,2,15 and zero initial flow, at most min(10,2,15)=2 units can be sent. The narrowest residual edge is the bottleneck.

After sending δ units through an edge, its forward residual capacity decreases by δ and its reverse residual capacity increases by δ. A reverse residual edge means “cancel part of a previous choice”, not that the physical network gained a new original pipe.

If opposite-direction original edges both exist, the aggregate residual capacity from u to v is c(u,v)−f(u,v)+f(v,u) in the nonnegative edge-flow convention. Use distinct residual edge records or accumulate both contributions correctly.

Cuts and the stopping certificate

An s–t cut partitions V into S and T with s∈S and t∈T. Its capacity is the sum of capacities of original edges directed S→T. Every feasible flow is at most every cut capacity: net flow across the cut equals |f| and cannot exceed that capacity. When no residual s→t path exists, let S be the vertices reachable from s in the residual graph; the resulting cut has capacity equal to the current flow. Thus the flow is maximum and the cut is minimum.

For each u ∈ V \ {s,t}:
    Σ[x ∈ V] f(x,u) = Σ[y ∈ V] f(u,y)

Source net outflow = Σ[v ∈ V] f(s,v) - Σ[v ∈ V] f(v,s)
Sink net inflow   = Σ[v ∈ V] f(v,t) - Σ[v ∈ V] f(t,v)
These two quantities are equal and define |f|.

Ford–Fulkerson method and Edmonds–Karp algorithm

Start with zero flow. Find a source-to-sink path using only positive residual capacities. Send the path's minimum residual capacity, update both forward and reverse residual capacities, and repeat. Ford–Fulkerson does not specify how to choose the path; Edmonds–Karp specifies BFS, choosing a path with the fewest edges, not the largest bottleneck or smallest total weight.

residual[u][v] = sum of original capacities from u to v, for every ordered pair
                 // zero only when no original u-to-v edge exists
                 // never erase a real opposite-direction capacity
total = 0
while findPathInResidualGraph(s,t,parent):    // BFS for Edmonds–Karp
    delta = infinity
    for each edge (u,v) on the recovered path:
        delta = min(delta,residual[u][v])
    for each edge (u,v) on the recovered path:
        residual[u][v] -= delta
        residual[v][u] += delta
    total += delta
return total

Complete class network

Augmentations in the handwritten trace

This is a valid Ford–Fulkerson path sequence. It is not the BFS path sequence: at step 3, the shorter residual path s→v₂→v₄→v₃→t already exists. Edmonds–Karp can take 7 units on that path after the first two augmentations and reach 23 in three augmentations.

Final edge-flow table and independent check

Source outflow is 16+7=23; sink inflow is 19+4=23. At v₂, inflow 7+4=11 equals its outgoing 11. At v₄, incoming 11 equals 7+4. No residual path reaches t.

The cut S={s,v₁,v₂,v₄}, T={v₃,t} has crossing capacities 12+7+4=23. This supplies an upper bound matching the feasible flow, proving optimality rather than merely reporting the last computed value.

Complexity with assumptions

For integral capacities, each Ford–Fulkerson augmentation increases the integer flow value by at least 1; with O(E) path search, time is O(E|f*|), which depends on numeric capacity. Arbitrary irrational capacities can lead to nontermination with unsuitable path choices.

Edmonds–Karp's BFS distances never decrease. When a directed residual edge becomes a bottleneck, is later reversed, and becomes a bottleneck again, the relevant distance must have increased. Each edge is critical only O(V) times, giving O(VE) augmentations. With adjacency lists, O(E) work per BFS gives O(VE²). The class matrix implementation scans V potential neighbours per visited vertex, so O(V²) per BFS gives the implementation-specific bound O(V³E); matrix storage is O(V²). Full class code.

Residual-initialization clarification. In this aggregate matrix, the initial v₁→v₂ entry is 10 and v₂→v₁ is 4. Reverse cancellation capacity starts at zero, but an existing opposite-direction original edge does not. Initializing every reverse matrix entry to zero would erase real capacity. In a tagged-edge adjacency list, by contrast, each original edge has its own separate zero-capacity cancellation partner.

FORD_FULKERSON_EDGE_FLOW(G,s,t):
    for every original edge e: f[e] = 0
    while a positive-capacity residual s-to-t path p exists:
        delta = minimum residual capacity of an arc on p
        for each tagged residual arc a on p:
            e = the original edge associated with a
            if a is the forward residual arc of e:
                f[e] = f[e] + delta
            else:                       // cancellation arc of e
                f[e] = f[e] - delta
    return f

Matching and the flow reduction

A bipartite graph splits its vertices into disjoint sets L and R, with edges only between the sets. A matching is a set of edges with no shared endpoint. A maximum matching has largest cardinality; a merely maximal matching cannot be extended by directly adding an edge but may be smaller.

Build a unit-capacity flow network: add s→u for every u∈L, orient each allowed pair u→v from L to R, and add v→t for every v∈R. All capacities are 1. Integral maximum flow selects whole pairs, and the source/sink unit edges prevent any vertex from being matched twice. The maximum-flow value equals the maximum matching size.

Exact class graph

Why reverse residual edges matter

At step 2, 1→A is a reverse residual edge. It cancels A–1, freeing 1 for B, while A moves to 2. A greedy algorithm that permanently fixed A–1 would incorrectly leave B unmatched.

The alternate notebook first chooses D–5 and later uses s→E→5→D→4→t to reroute D. That produces the same final matching. These are compatible traces, not conflicting answers.

The answer is 5, with A→2, B→1, C→3, D→4, E→5. Five is also an upper bound because there are only five vertices on each side. Hence the matching is maximum. For unit-capacity augmenting-path search, at most min(|L|,|R|) augmentations are needed; straightforward DFS/BFS augmentation takes O(VE) time on the bipartite graph.

Minimum vertex-disjoint path cover in a DAG

A path cover is a collection of directed paths containing every vertex exactly once across the collection. A single vertex is allowed as a path. The objective is the number of paths, not their total length. The reduction below requires a directed acyclic graph and vertex-disjoint coverage.

1. Make two copies of every vertex: u_L (outgoing role) and u_R (incoming role).
2. For each original edge u→v, add bipartite edge u_L→v_R.
3. Find a maximum matching M, using a unit-capacity source/left/right/sink network if desired.
4. The answer is |V|−|M|.

Why the formula is correct

Initially each vertex is its own path, giving |V| paths. Every selected matching edge joins a predecessor to a successor and reduces the count by one. The matching ensures at most one selected incoming and outgoing edge per original vertex. Acyclicity prevents these links from forming a cycle, so they form disjoint paths. Conversely, a cover of k paths uses |V|−k links, which form a matching in the split graph. Maximizing links is therefore equivalent to minimizing paths.

Five-vertex class example

Edges are A→B, A→C, B→D, C→D, D→E. Choose matching edges A_L–B_R, B_L–D_R, D_L–E_R. The matching has size 3, so the minimum cover has 5−3=2 paths: A→B→D→E and the singleton C. Another optimum is A→C→D→E plus singleton B.

Both B→D and C→D cannot be chosen together because they share D's right copy. This explains why no one path can cover both incoming branches in the original graph.

Seven-vertex example in the alternate notebook

Edges A→B→C split into C→D→E and C→F→G. Two minimum covers are {A→B→C→D→E, F→G} and {A→B→C→F→G, D→E}. Each uses five matching links, so 7−5=2 paths.

Recovering the paths

For every matched edge u_L–v_R, set successor[u]=v and predecessor[v]=u. Start at vertices with no selected predecessor and follow successors until none remains. Do not print the artificial source, sink, or L/R copies in the final original-graph paths.

for each original vertex v:
    predecessor[v] = NONE; successor[v] = NONE
for each matched pair (u_L,v_R):
    successor[u] = v
    predecessor[v] = u
for each original vertex start with predecessor[start] == NONE:
    path = []
    v = start
    while v != NONE:
        append v to path
        v = successor[v]
    output path

Plaintext, ciphertext, encryption, and decryption

Plaintext is the original message; encryption transforms it into ciphertext; decryption recovers the message using the appropriate key. The notebook first illustrates a one-letter shift: RAG→SBH and then SBH→RAG. That example is a Caesar shift, not RSA. It introduces the vocabulary before the RSA key-generation steps.

RSA is an asymmetric/public-key construction. A sender encrypts using the recipient's public key; the recipient decrypts using its corresponding private key. Classroom “textbook RSA” operates on an integer message m in the range 0≤m<n.

Key generation, with every quantity defined

1. Choose distinct primes p and q.
2. Compute the modulus n=pq.
3. Compute Euler's totient φ(n)=(p−1)(q−1), the number of residues from 1 through n that are coprime to n.
4. Choose e with 1<e<φ(n) and gcd(e,φ(n))=1.
5. Find the modular inverse d of e modulo φ(n): ed≡1 (mod φ(n)).
6. The public key is (e,n); the basic private-key pair is (d,n). The primes and private exponent are kept secret.

The inverse exists precisely because e and φ(n) are coprime. Writing ed=kφ(n)+1 gives d=(kφ(n)+1)/e. Trying k is manageable for tiny class examples, while extended Euclid computes the inverse systematically.

Exact classroom key calculation

Extended Euclid gives the same result: 120=17·7+1, so 1=120−17·7. Thus 7⁻¹≡−17≡103 (mod 120).

Encryption and decryption

Encryption: c = m^e mod n
Decryption: m' = c^d mod n
Class message: m=83
c = 83^7 mod 143 = 8
m' = 8^103 mod 143 = 83

The numerical encoding 83 is the classroom plaintext integer. A longer string requires an encoding and appropriate block/padding construction; a whole string cannot simply be substituted into an integer exponent expression. The next lesson expands both modular powers completely.

Why decryption works

Since ed=1+kφ(n), if gcd(m,n)=1, Euler's theorem gives m^φ(n)≡1 (mod n), hence m^ed=m·(m^φ(n))ᵏ≡m (mod n). For a message divisible by p or q, reason modulo each prime: if m≡0 modulo that prime the equality is immediate; otherwise Fermat's theorem applies because ed−1 is divisible by p−1 and q−1. The two congruences combine modulo pq, so decryption also works for those message residues.

What the small example does not establish

The tiny primes are for arithmetic practice, not security. The note's suggestion that five-digit primes are sufficient in real life is incorrect. The value 65537 is commonly discussed as a public exponent e, not as an adequately large RSA prime. Raw textbook RSA is deterministic and lacks the protections required in real encryption/signature schemes; use vetted cryptographic libraries and standardized constructions rather than this classroom formula as an application protocol.

Reduce while multiplying

To compute aᵉ mod m, do not first construct the enormous integer aᵉ. The identities (a mod m) mod m=a mod m and (ab) mod m=((a mod m)(b mod m)) mod m allow reduction after every multiplication.

Write e in binary: every 1 bit selects a power a^(2ⁱ). Compute those powers by repeatedly squaring modulo m, then multiply only the selected ones.

Class encryption: 83⁷ mod 143

Since 7=1+2+4, multiply residues: 83·25=2075≡73 (mod143), then 73·53=3869≡8 (mod143). Thus the ciphertext is 8.

Class decryption: 8¹⁰³ mod 143

103=64+32+4+2+1, or binary 1100111₂. The 16 and 8 bits are zero.

Compute 8·64≡83; then 83·92≡57; then 57·53≡18; then 18·92≡83, all modulo 143. This recovers the plaintext. Equivalently, the notebook's reverse multiplication order gives the same residue.

Square-and-multiply algorithm

modPower(a,e,m):                 // e >= 0, m > 0
    result = 1 mod m
    a = a mod m
    while e > 0:
        if e is odd: result = (result*a) mod m
        a = (a*a) mod m
        e = e//2
    return result

Loop invariant: result·aᵉ is congruent to the original base raised to the original exponent. On an odd exponent, extract one a into result; squaring a and halving the remaining even exponent preserves the product. When e reaches zero, result is the desired residue.

The loop has Θ(log e) iterations for e>0, O(log e) modular multiplications, and O(1) stored machine words. Large-integer bit complexity also depends on the multiplication/modular-reduction method. In C++, a*a can overflow before the modulus is applied; choose a sufficiently wide type or an overflow-safe modular multiplication routine.

For exponent zero, return 1 mod m; for m=1 every result is zero. Negative exponents require a modular inverse and are outside this routine's stated domain.

8^103 mod 143
 = (92 * 53 * 92 * 64 * 8) mod 143
92 * 53 = 4876 = 34*143 + 14
14 * 92 = 1288 =  9*143 + 1
 1 * 64 =   64
64 *  8 =  512 =  3*143 + 83
Therefore 8^103 mod 143 = 83.

Convexity and the convex hull

A set is convex when the segment joining any two of its points lies entirely inside or on its boundary. For a simple polygon, this corresponds to no inward dent and no interior angle greater than 180°. A concave simple polygon has at least one reflex interior angle greater than 180°.

The convex hull of a finite point set is the smallest convex set containing all the points. In the nondegenerate planar case, it is a polygon whose vertices are selected input points. Imagine tightening a rubber band around the set: interior points do not become hull corners.

Orientation, without needing an angle measurement

cross(A,B,C) = (B.x-A.x)*(C.y-A.y) - (B.y-A.y)*(C.x-A.x)
positive: A→B→C is counterclockwise (C is left of directed A→B)
negative: clockwise (C is right of A→B)
zero: collinear

For example, A=(0,0), B=(2,0), C=(1,1) gives cross=2, a left turn. This numerical example explains the predicate; the class drawing itself supplies labels, not numerical coordinates.

Gift wrapping / Jarvis march

1. Choose the point with minimum x, breaking a tie by minimum y. It must be on the hull.
2. At current hull point p, choose any other point q as a temporary candidate.
3. Scan every other point r. If cross(p,q,r)>0, replace q by r. If the cross product is zero, keep the farther point from p.
4. After the scan, append q as the next hull point and repeat from it.
5. Stop when the next point is the starting point.

points = distinct input coordinates
if number of points <= 1: return points
start = leftmost-lowest distinct point
p = start; hull = []
repeat:
    hull.append(p)
    q = any distinct point other than p
    for r in all points:
        if cross(p,q,r) > 0 or
           (cross(p,q,r) == 0 and distanceSquared(p,r) > distanceSquared(p,q)):
            q = r
    p = q
until p == start

With this sign convention the chosen directed hull edge has the other points on its right, so this version traverses the boundary clockwise. Reversing the sign produces the opposite orientation; both can be correct if used consistently.

Full labeled class trace

The sketch has exterior labels C,E,F,H,A,B and interior points D,G. Starting at C, the notes initially test candidate D. G,F,H lie to the right of C→D, while E lies to the left, so E replaces D. The remaining tests retain E.

The hull is C→E→F→H→A→B→C; D and G are excluded. The source stack can be read in reverse depending on which end is drawn on top, but it describes this same boundary.

Cost and degeneracies

Every selected hull vertex requires scanning all n input points. For h hull vertices, time is O(nh), hence O(n²) worst case. Output uses O(h); the selection variables use O(1) beyond stored points/output. Remove duplicate coordinates or handle them deliberately. With all points collinear, a vertices-only hull contains the two extremes; one point gives a point and two distinct points give a segment. Choosing the farthest collinear point prevents an interior boundary point from prematurely becoming the next corner.

Full class Jarvis C++ code is retained, including its particular output conventions.

Boundary completion. The explicit initial guard returns an empty hull for no points and the point itself for one distinct coordinate. For two distinct points, the loop visits both and returns to the start. Farthest-collinear selection likewise returns just the two extremes for an all-collinear set. This is the vertices-only convention; repeated input coordinates do not create extra hull corners.

Graham scan: sort once, then maintain a convex stack

Graham scan constructs the same planar convex hull as gift wrapping but first orders the points around a pivot. The notebook chooses minimum y, breaking a tie with minimum x. This differs from Jarvis march's leftmost starting convention; either algorithm's stated choice should be followed consistently.

1. Select the lowest-leftmost pivot A.
2. Order all other distinct points by increasing polar angle around A.
3. For equal angles, retain the farthest point if the required output contains only hull corners.
4. Push A and the first remaining point.
5. For each next point Z, let Y be the stack top and X the next-to-top. While X→Y→Z is not a strict counterclockwise turn, pop Y and reconsider the new last two points.
6. Push Z. The stack at the end contains the hull in boundary order.

points = distinct input coordinates
if number of points <= 1: return points
pivot = point with minimum (y,x)
sort other points by increasing polar angle around pivot,
    breaking equal-angle ties by increasing distance from pivot
stack = empty
for point p in that order, including pivot first:
    while stack.size >= 2 and cross(stack[-2],stack[-1],p) <= 0:
        stack.pop()
    stack.push(p)
return stack

The repeated while is essential: one incoming point can invalidate several earlier candidates. An if that pops only once can leave a concave turn. The ≤0 rule excludes collinear interior boundary points; a different boundary-output convention needs deliberate tie handling.

The stack invariant and why a pop is safe

After each insertion, the stack follows the convex boundary of the points processed in angular order, with strict counterclockwise turns. If X→Y→Z turns clockwise or is collinear with Y between the extremes, Y cannot be a required extreme corner once Z is considered. Removing Y restores the possibility of a convex boundary; testing again handles an entire chain of newly internal points.

Readable version of the labeled notebook drawing

The clearer alternate drawing orders candidates B,J,D,E,G,F,C,H,I around pivot A. The visible final boundary is A→B→J→G→H→I→A; C,D,E,F are interior. The sketch has no numerical coordinates, so the labels and stack decisions—not invented cross-product numbers—are the source trace.

A stack printed by popping gives the reverse order I,H,G,J,B,A. Reversing boundary orientation does not change the set of hull corners.

Complexity and robust comparisons

Pivot selection is O(n), sorting is O(n log n), and the stack pass is O(n): each point is pushed once and popped at most once. Total time is O(n log n), auxiliary/output storage O(n). Comparing polar directions via cross products avoids floating-point atan2, but integer arithmetic must be wide enough. Widen coordinates before subtraction; casting only after a narrow subtraction cannot repair overflow.

Duplicate points, fewer than three distinct points, and all-collinear data require explicit output rules. The complete class C++ source and its caveats remain available separately; these conditions are part of understanding the algorithm, not reasons to omit the code.

Tie-order clarification. The pseudocode keeps equal-angle points in increasing distance order, so the ≤0 pop removes each nearer point before retaining the farthest. This implements the earlier farthest-only rule without a separate filtering pass. With the lowest-leftmost pivot all other directions lie in one half-plane, so cross-product angle comparison with the stated distance tie-break is consistent. Empty, singleton and duplicate-only input is handled before choosing the pivot.

The string-matching problem

Given a text T of length n and a pattern P of length m, find every starting index s for which T[s…s+m−1]=P[0…m−1]. Indices here are zero-based. A match starting at s ends at s+m−1. Matching is case-sensitive unless the input is deliberately normalized.

The naive method tries every possible alignment and compares corresponding characters from left to right. There are n−m+1 possible alignments when 1≤m≤n. A mismatch rejects the current alignment, not the entire search.

Complete algorithm

naiveMatch(T,P):
    n = length(T); m = length(P)
    if m == 0: return [0,1,...,n]  // explicitly chosen empty-pattern convention
    if m > n: return []
    matches = []
    for s = 0 to n-m inclusive:
        j = 0
        while j < m and T[s+j] == P[j]:
            j = j+1
        if j == m:
            append s to matches
    return matches

The test j<m must be evaluated before reading P[j]. The alignment limit s≤n−m guarantees s+j<n during each comparison. Moving the alignment by one also finds overlapping occurrences.

Worked alignment table

Using the same text and pattern as the later KMP example, T=ababcabcabababd and P=ababd, n=15 and m=5. The complete set of candidate windows is:

For s=0, a,b,a,b match and the fifth comparison c≠d fails. For s=10, all five comparisons succeed. The final answer is start index 10, end index 14. As a separate overlap example, T=aaaa and P=aa gives starts 0,1,2—not only 0 and 2.

Correctness and cost

Every possible occurrence has exactly one start s in 0…n−m. The outer loop visits all these starts. The inner loop accepts an alignment exactly when all m corresponding characters are equal. Therefore it reports every occurrence and no false occurrence.

At most m comparisons occur at each of n−m+1 alignments, so the worst-case comparison count is Θ((n−m+1)m), often written O(nm). An example is a text of all a's and a pattern a…ab, which fails only near the end of each window. If every window fails on its first comparison, the search takes Θ(n−m+1) comparisons. Working storage is O(1), excluding input and the list of k reported positions, which requires O(k).

n = length(T); m = length(P)
if m == 0: report all boundaries 0..n; return
if m > n: return
for i = 0 to n-m inclusive:
    count = 0
    for j = 0 to m-1:
        if T[i+j] == P[j]:
            count = count+1
        else:
            break
    if count == m:
        print(i, i+m-1)

Why use a hash?

Rabin–Karp compares a numerical fingerprint of the pattern with fingerprints of equally long text windows. A rolling hash updates the next window from the previous one instead of recomputing every character contribution. Unequal hashes prove unequal strings. Equal hashes only identify a candidate: compare the characters to distinguish a real match from a collision (spurious hit).

The notebook's first hash: addition

The class example searches for FUR in a text beginning ASIFUR (the two versions continue RAHMAN and ISLAM). The demonstration assigns A=1, S=2, I=3, F=4, R=5, L=6, M=7, U=8. These are illustrative symbol codes, not actual ASCII values.

With the additive hash, H(FUR)=4+8+5=17. But H(RFU)=5+4+8=17 and H(FRU)=4+5+8=17 also. Thus a hash can ignore information—in this case order—and produce many spurious hits. For a length-m window, an additive hash rolls by subtracting the outgoing code and adding the incoming code.

The notebook's positional hash, fully worked

The second demonstration assigns increasing powers of 10 from left to right: H(c₀c₁…cₘ₋₁)=code(c₀)+10·code(c₁)+…+10ᵐ⁻¹·code(cₘ₋₁). For m=3:

nextHash = (currentHash - outgoingCode)/10 + incomingCode*10^(m-1)
ASI -> SIF: (321-1)/10 + 4*100 = 432
SIF -> IFU: (432-2)/10 + 8*100 = 843
IFU -> FUR: (843-3)/10 + 5*100 = 584

The division is exact here because the outgoing symbol was the units contribution. The target hash 584 matches the fourth window, starting at index 3. Comparing F,U,R confirms the occurrence. This small integer illustration is useful for understanding rolling updates; large windows require modular arithmetic to keep fingerprints bounded.

Practical modular version: a different, explicit power convention

For the usual implementation, use descending powers from left to right: H(c₀…cₘ₋₁)=(code(c₀)dᵐ⁻¹+…+code(cₘ₋₁)) mod q. Here d is the alphabet base and q is a positive modulus, normally chosen prime. Precompute h=dᵐ⁻¹ mod q. Removing the first character, shifting the remaining contributions left by one power, and adding the new character gives:

nextHash = (d*(currentHash - outgoingCode*h) + incomingCode) mod q
if nextHash < 0: nextHash += q

This formula does not divide the current hash. The notebook's ascending-power integer formula and this descending-power modular formula are each valid for their own definitions; mixing them is not valid.

Complete verified-match algorithm

rabinKarp(T,P,d,q):                 // q > 1
    n = length(T); m = length(P)
    if m == 0: return [0,1,...,n]
    if m > n: return []
    h = d^(m-1) mod q               // computed by modular exponentiation
    patternHash = 0; windowHash = 0
    for j = 0 to m-1:
        patternHash = (d*patternHash + code(P[j])) mod q
        windowHash  = (d*windowHash  + code(T[j])) mod q
    matches = []
    for s = 0 to n-m inclusive:
        if patternHash == windowHash:
            if T[s:s+m] equals P character by character:
                append s to matches
        if s < n-m:
            windowHash = (d*(windowHash-code(T[s])*h)+code(T[s+m])) mod q
            if windowHash < 0: windowHash += q
    return matches

Why it works; complexity

Initialization computes the fingerprint of the first length-m window. The rolling identity preserves that meaning at every shift. Every real occurrence therefore has the pattern hash and reaches the verification step. Verification accepts exactly equal strings, so collisions do not affect correctness.

Preprocessing takes O(m); there are O(n−m+1) constant-time hash updates under the word-arithmetic model. If H windows have matching hashes, verification costs at most O(Hm), making the total O(n+m+Hm). With few spurious hits and few occurrences, the usual expected cost is O(n+m). Worst case is O(nm), including collision-heavy inputs or many genuine length-m matches checked separately. Auxiliary hash state is O(1), excluding output.

Use sufficiently wide arithmetic or overflow-safe modular multiplication: applying %q after an overflowing signed product does not repair it. Normalize a negative remainder before comparing hashes. If character verification is omitted, hash collisions can be reported as false matches. With fixed d and q this is deterministic, not automatically a randomized algorithm. A Monte Carlo error bound additionally requires a specified randomized choice of hash parameters and its collision analysis. The character-verifying version above remains exact for every valid d and q.

Further clarification reference (optional; the explanation above is complete offline): Princeton Algorithms: randomized modulus and explicit match verification

RABIN_KARP_ASCENDING(T,P,b):
    n = length(T); m = length(P)
    if m == 0: return [0,1,...,n]
    if m > n: return []
    PH = 0; TH = 0; power = 1
    for j = 0 to m-1:
        PH += code(P[j])*power
        TH += code(T[j])*power
        power *= b
    highestPower = power/b              // b^(m-1)
    matches = []
    for i = 0 to n-m inclusive:
        if PH == TH and T[i:i+m] equals P:
            append i to matches
        if i < n-m:
            TH = (TH-code(T[i]))/b + code(T[i+m])*highestPower
    return matches

What repeated work does KMP remove?

After a partial match followed by a mismatch, naive search starts the next alignment from scratch. Knuth–Morris–Pratt (KMP) uses information about the matched prefix to retain a suffix that is already known to match the beginning of the pattern. The text index never moves backward.

Prefix, suffix, and LPS

A prefix starts at the first character; a suffix ends at the last. A proper prefix is shorter than the whole string. LPS[i] is the length of the longest proper prefix of P[0…i] that is also a suffix of P[0…i]. The empty string ε has length zero and is allowed when there is no nonempty border.

For the classroom pattern abaabad, the full prefix/suffix calculation is:

The resulting array is [0,0,1,1,2,3,0]. For example, abaaba begins and ends with aba, so LPS[5]=3. The whole six-character string is excluded because the prefix must be proper.

Computing LPS in linear time

buildLPS(P):                     // nonempty P
    m = length(P)
    LPS[0] = 0
    length = 0; i = 1
    while i < m:
        if P[i] == P[length]:
            length = length+1
            LPS[i] = length
            i = i+1
        else if length > 0:
            length = LPS[length-1]   // do not advance i
        else:
            LPS[i] = 0
            i = i+1
    return LPS

Before processing i, length is a candidate border of P[0…i−1]. If P[i] continues it, the border grows by one. Otherwise the next possible border must itself be a border of that candidate prefix, so the fallback is LPS[length−1]. Subtracting one blindly misses the structural reason for skipping candidates.

Two further classroom LPS examples

For aaacaaaa, LPS=[0,1,2,0,1,2,3,3]. At the last character, length=3 first compares a with P[3]=c and fails. Falling back to LPS[2]=2 allows a match with P[2]=a; the final entry becomes 3, not 4 and not 0.

For the longer pattern acacabacacabacacac, every index and final value is shown below, followed by the complete fallback trace.

At i=17, the candidates fall from 11 to LPS[10]=5, then to LPS[4]=3. P[3]=c matches the new c, so LPS[17]=4. The repeated mismatch does not consume the new character until a valid border continuation or length-zero failure is found.

The KMP matching algorithm

KMP(T,P):
    n = length(T); m = length(P)
    if m == 0: return [0,1,...,n]
    LPS = buildLPS(P)
    i = 0; j = 0; matches = []
    while i < n:
        if T[i] == P[j]:
            i = i+1; j = j+1
            if j == m:
                append i-m to matches
                j = LPS[m-1]     // preserve possible overlapping matches
        else if j > 0:
            j = LPS[j-1]         // same text character, shorter known prefix
        else:
            i = i+1
    return matches

Complete classroom search trace

Text T=ababcabcabababd; pattern P=ababd; LPS=[0,0,1,2,0]. Each row is one character comparison; i and j are the values before that comparison.

The only occurrence starts at index 10 and ends at 14. At i=12, j=4, the mismatch a≠d does not advance i: j falls to 2, so the same a can continue the shorter border ab. This is the central saving over restarting from the beginning.

Why fallback cannot skip a valid match

When j characters have matched, the already matched text segment equals P[0…j−1]. Any next alignment that reuses part of this segment must make a suffix of that segment equal a prefix of P. LPS[j−1] gives the longest such candidate. If it fails too, following the LPS chain considers the next shorter border. Alignments not represented by a border cannot match the characters already examined, so skipping them is safe.

Complexity and boundary cases

LPS preprocessing is O(m): successful extensions advance i and increase the border length; every fallback strictly decreases that length, so the total number of fallbacks is bounded by prior increases. The same amortized argument gives O(n) matching work. Total time is O(n+m); LPS storage is O(m), plus O(k) output positions. If m>n there are no occurrences. After a full match, resetting j to LPS[m−1], not always zero, preserves overlapping matches.

Start with decision problems and input size

A decision problem asks a yes/no question: “Does this graph contain a path from s to t?” or “Is there a vertex cover of size at most k?” Complexity is measured in the length of the encoded input, not only the numerical value of a parameter. Polynomial time means a bound O(Nᶜ) for a fixed constant c and input length N.

An algorithm is a procedure for solving a problem. A complexity class is a set of problems meeting a resource bound. Sorting algorithms such as merge sort illustrate polynomial computation, but P and NP are conventionally defined for decision problems, so algorithm names alone are not formal members of these classes.

P: efficiently solvable decision problems

P is the set of decision problems solvable by a deterministic algorithm in polynomial time. Examples include reachability (run BFS/DFS and answer whether t is reached), and deciding whether a weighted undirected graph has a spanning tree of total weight at most K (compute an MST and compare). Deterministic means that the current state and input determine the next step.

NP: efficiently verifiable yes answers

NP is the set of decision problems with a deterministic polynomial-time verifier and a polynomial bound on certificate length: every yes-instance has at least one accepted certificate, and a no-instance has no accepted certificate. Both conditions are essential. A procedure that accepts every purported certificate is not a valid verifier for a problem that has no-instances. Equivalently, they are solvable by a nondeterministic machine in polynomial time. Nondeterminism is a theoretical ability to branch among possible choices; it does not mean randomization.

For a Hamiltonian-cycle decision problem, a certificate is an ordering of all vertices. Check that every vertex occurs once and that every consecutive pair, including last-to-first, is an edge. For vertex cover, a certificate is a set S of at most k vertices; check that every edge has an endpoint in S. These checks are polynomial even if we do not know how to find such a certificate efficiently for every input.

NP guarantees efficient verification of yes certificates. It does not assert that every no-instance has an equally short, efficiently checkable certificate. Also, every P problem lies in NP: a verifier can solve the problem itself without needing a helpful certificate.

Polynomial-time reduction

A many-one reduction A≤ₚB transforms every input x of A, in polynomial time, into an input f(x) of B such that x is a yes-instance of A if and only if f(x) is a yes-instance of B. An algorithm for B can then solve A by transforming the input and solving the transformed instance.

To solve A using B:
    y = f(x)              // polynomial-time transformation
    return solver_B(y)    // preserves the yes/no answer

To prove a new problem X is hard:
    take a known hard problem Y
    prove Y <=p X         // reduce known-hard TO the new target, not backward

The direction matters: A≤ₚB says B is at least as hard as A in this reduction sense. Showing X≤ₚY for a known hard Y only shows that Y can solve X; it does not establish hardness of X. Polynomial reductions compose, which allows hardness to be transferred through a chain.

NP-hard and NP-complete

To prove X is NP-complete, establish both parts: (1) X∈NP by describing a certificate, its size, and its polynomial verifier; (2) NP-hardness by reducing an already known NP-complete problem Y to X with a polynomial transformation and an if-and-only-if correctness proof.

Examples and the distinction between decision and optimization

• SAT decision: is there a truth assignment satisfying a Boolean formula? An assignment is a polynomially verifiable certificate; SAT is NP-complete.
• Hamiltonian-cycle decision: does the graph contain a cycle visiting each vertex exactly once? NP-complete for general graphs.
• Vertex-cover decision: does a general graph have a vertex cover of size ≤k? NP-complete. Finding a smallest cover is the related NP-hard optimization problem.
• Traveling salesperson: the decision version asks whether a tour of cost ≤K exists; with standard finite input encoding it is NP-complete. Finding a minimum-cost tour is the NP-hard optimization version.

Restrictions can change complexity: for example, bipartite graphs admit polynomial-time minimum vertex cover. Therefore a classification must state the actual problem and graph restrictions, not just a familiar topic name.

Reading the relationship diagram correctly

P⊆NP, and NP-complete=NP∩NP-hard. Whether P=NP is unresolved. If any NP-complete problem has a polynomial-time algorithm, then every NP problem does and P=NP. A familiar diagram drawing P as a smaller region inside NP is an illustration of the hypothesis P≠NP, not a proved separation. NP-hard problems need not be inside NP.

Further clarification reference (optional; the explanation above is complete offline): Cornell complexity notes: the if-and-only-if verifier definition

Dijkstra: shortest paths from one source

Given a directed or undirected graph with nonnegative edge weights and source s, Dijkstra computes the minimum path weight from s to every reachable vertex. Set dist[s]=0 and all other distances to ∞. Repeatedly settle an unsettled vertex with the smallest tentative distance, then relax its outgoing edges.

Relaxing u→v of weight w means testing whether dist[u]+w<dist[v]. If so, replace dist[v] by that smaller value and set parent[v]=u. Parent pointers reconstruct a shortest path; unreachable vertices keep distance ∞ and no parent.

Dijkstra(G,s):
    dist[v] = infinity and parent[v] = none for every v
    dist[s] = 0
    minHeap.push((0,s))
    while minHeap is not empty:
        (du,u) = minHeap.popMin()
        if du != dist[u]: continue       // stale entry from an earlier improvement
        for every outgoing edge (u,v,w):
            if dist[u]+w < dist[v]:
                dist[v] = dist[u]+w
                parent[v] = u
                minHeap.push((dist[v],v))

Full classroom directed graph

The following edge list is the readable equivalent of the diagram. An arrow is directed; a reverse edge exists only if it is separately listed.

Every settlement and distance update

Settlement order is s,x,y,u,v. The heap can still contain old entries u(10), v(13), and v(14); these are discarded as stale, not treated as new distances.

Why the smallest tentative distance is safe

Suppose u is the unsettled vertex with smallest tentative distance, but a shorter path to u exists. On that path, consider the first unsettled vertex y and its settled predecessor x. When x was settled, relaxation made dist[y] no greater than the length of the path prefix to y. Nonnegative remaining edges mean that prefix is no longer than the full supposedly shorter path to u. This contradicts u having the minimum tentative distance. Therefore dist[u] is final when settled.

A negative edge breaks this argument: a path through a vertex with a currently larger distance may later become cheaper. Use an appropriate algorithm such as Bellman–Ford when negative weights must be supported; do not claim the Dijkstra guarantee there.

Prim: minimum spanning tree, not shortest paths

For a connected, undirected weighted graph, a spanning tree connects all vertices without a cycle using V−1 edges. An MST minimizes the sum of its edge weights. Prim starts with one vertex and repeatedly adds the cheapest edge crossing from the current tree to an outside vertex.

For each outside vertex v, key[v] is the lightest single edge connecting it to the current tree; parent[v] is the endpoint inside the tree. It is not the distance along a path from the starting vertex.

Prim(G,start):
    key[v] = infinity; parent[v] = none; inTree[v] = false for every v
    key[start] = 0
    minHeap.push((0,start))
    while minHeap is not empty:
        (k,u) = minHeap.popMin()
        if inTree[u] or k != key[u]: continue
        inTree[u] = true
        for every undirected incident edge (u,v,w):
            if not inTree[v] and w < key[v]:
                key[v] = w               // NOT key[u]+w
                parent[v] = u
                minHeap.push((key[v],v))
    if any vertex is outside the tree: graph is disconnected
    otherwise return all edges (parent[v],v) for v != start

Full classroom undirected graph

Complete Prim trace, starting at G

The MST contains GF, FE, EB, BA, BH, BC, ED, with total weight 3+8+2+4+5+9+15=46. Unlike Dijkstra distances, the sequence of selected edge weights need not increase: selecting E with key 8 reveals B with key 2.

Cut-property justification

Let S be the current tree vertices. A minimum-weight edge crossing the cut (S,V−S) is safe: take an MST containing the already selected edges. If it does not contain this crossing edge, adding it creates a cycle. The cycle contains another edge crossing the same cut. Replacing that edge by the chosen minimum crossing edge does not increase the weight, so an MST still exists containing all selected edges. Repeating the argument proves Prim's result.

Comparison, complexity, and boundary cases

The shown lazy heaps can contain O(E) entries, giving O((V+E) log(V+E)) time in general and O(V+E) storage; for simple graphs this is customarily written O((V+E) log V). Tie-breaking may choose different valid parents or different MSTs with the same total weight. A shortest-path tree is not necessarily an MST, and an MST need not contain shortest source-to-vertex paths.