Computer science fundamentals

Every link has two ends, and each end raises exactly one machine's link count by one. Totalling link counts therefore counts every link twice. This is the handshake lemma: the degree sum equals 2E, so it is always even.

Reject when NOT authenticated OR (NOT hasRole AND NOT isServiceCall). De Morgan's laws flip each connective as the negation moves inward: the outer AND becomes OR, the inner OR becomes AND, and every atom is negated.

One queued job that is never acknowledged refutes the claim completely; a single counterexample is a full disproof. Passing runs only fail to find one. They establish the claim only if they exhaust a finite domain.

Only the contrapositive: 'if the request succeeded, the retry budget was not exhausted'. The converse and the inverse are different claims that can be false while the original rule still holds.

A 32-bit fingerprint has only 2^32 possible values, so any 2^32 + 1 distinct keys must contain two that share one. That is the pigeonhole principle; a better function cannot avoid it, only a wider field delays it.

One fact decides it: the state the machine is left in after the final symbol. If that state is in the accepting set, the string is accepted. Passing through an accepting state earlier in the run means nothing.

Terminals are the literal symbols that appear in the generated text; nonterminals are named placeholders that some rule rewrites. A derivation starts at one designated start symbol and rewrites nonterminals until only terminals remain.

A token is one lexical unit: a class such as identifier, number, keyword, operator or punctuator, together with its text and the source span it came from. The scanner throws away whitespace and comments but keeps the spans.

A greedy quantifier takes as many repetitions as it can and gives characters back only when the rest of the pattern fails; a lazy one takes as few as possible and grows one at a time.

The Kleene star means zero or more repetitions of the subexpression it follows, joined end to end. Zero is the trap: a starred part can match the empty string, so on its own it never forces that text to be present.

Run-length encoding expands any input whose symbols rarely repeat: a single symbol still costs a count plus the symbol, so alternating bytes double in size. It pays only when the average run is longer than one pair.

Shannon entropy is the average surprisal of a field's values in bits: the sum of p times log2(1/p) over every value. It measures how uncertain the next value is, not how many distinct values exist.

Ten bits is the surprisal of an outcome with probability 1/1024, since -log2(1/1024) = 10. One bit is the uncertainty resolved by one fair yes/no answer, so rarer outcomes carry more bits and a certain one carries zero.

Lossless compression must be reversible, so distinct inputs need distinct outputs. There are more n-bit inputs than shorter strings, so no map can shrink them all; a scheme that shrinks one input must expand another.

Anything whose value is its exact bits must stay lossless: executables, archives, source, ledgers, and anything later checked by a digest or signature. Lossy fits terminal media a human tolerates approximately, never the master copy everything else is derived from.

Strip the domain nouns and restate the requirement as objects, a relation between them, and an objective. That skeleton — cover everything, pick a subset under a budget, order with no repeats — is what you match against the known catalogue.

Two colours leave no freedom: fix one vertex and propagation forces every other, so one traversal either succeeds or exposes an odd cycle. A third colour restores a choice at each vertex, and those choices interact globally.

NP membership claims only that a yes-answer has a short certificate a checker can validate in polynomial time. It says nothing about how long finding that answer takes, and it does not exclude an easy problem.

Deciding whether an arbitrary program stops is undecidable, so no checker can be always-terminating, never-wrong and complete at once. Every real loop detector therefore misses cases, raises false alarms, or sometimes fails to answer.

Polynomial time is a claim about scaling, not about one machine. A polynomial bound survives a change of machine model and stays polynomial when routines call each other; a fixed step budget expires with the next hardware or the next larger input.

A coroutine is a function that can pause partway through and resume later. Suspending saves its state, hands control back to a scheduler, and frees the underlying thread for other work. A blocked thread keeps its whole stack and OS slot while doing nothing.

An event loop is a single thread cycling forever: wait for ready events, take the next task from a queue, run its handler to completion, repeat. No handler is ever interrupted mid-way by another handler, so loop-owned state needs no locks — but a slow handler delays everything behind it.

A future is the read side of a result that is not ready yet: you await it or attach a continuation. A promise is the write side: the producer completes it once, with a value or an error. Splitting them stops consumers from completing results.

The statement is three steps: read, add one, write back. Two threads can read the same old value and both write the same new value, so one increment is lost. An atomic read-modify-write performs all three steps as one indivisible hardware operation that no other thread can interleave with.

Nothing orders the write against the read, so the reader has no obligation to observe it. The compiler may load the variable once into a register and loop on that copy, and the write may sit in the writer's store buffer. Publish the flag through a synchronization edge.

Most objects die very young — the weak generational hypothesis. Splitting the heap by age lets a collector sweep the young area often and cheaply, where almost everything is already garbage, and touch the older area rarely.

A root is a reference the collector can find without tracing anything first — a running thread's stack slot or register, a global table entry, a handle registered by code outside the collected heap. Everything the program can still touch starts at one of them.

Automatic reclamation frees only what nothing can reach. A leak there is memory that stays reachable from something live - an unbounded cache, a growing registry, a collection nobody trims - but will never be used again.

A process maps several regions with different rules: read-only code and constants, initialized static data, zero-filled static data, one growable heap, one stack per thread, and per-thread thread-local storage. Placement decides lifetime and who may write.

A call frame holds that call's return address, saved registers, local variables and spilled temporaries, plus space for outgoing arguments. Returning moves the stack pointer back past the whole frame, so release is one instruction with no bookkeeping.

Ubiquity and human readability win. A parser is already on every platform, so a partner integrates with no shared artifact; a person can read, paste and hand-edit a document; and the text diffs in review. Verbosity is the accepted price.

A text encoding writes values as readable characters you can grep, diff and hand-edit; a binary encoding packs them as raw sized bytes that are typically smaller and cheaper to parse, but unreadable without a decoder.

An in-memory value is laid out for one running process: it holds machine addresses valid only there, plus alignment holes whose contents are undefined. Another process shares none of that context, so the value must be re-expressed in a flat, self-standing form.

Absent means the sender said nothing about the field. Null means the sender said it has no value. Empty means it has a value that happens to be zero-length. Three different statements, and many encodings collapse them.

The data model survives; only the syntax is replaced. Maps, arrays, strings, numbers, booleans and null become tagged bytes instead of punctuation and decimal text, so records shrink and decode cheaper — but every key name still travels on every record.