Skip to content
AyoKoding

Overview

Prerequisites

  • Prior topics: 4 · Just Enough Python -- every script in this topic is fully type-annotated Python, and you should already be comfortable reading functions, classes, and list/dict/set literals the way that primer taught them; 7 · Data Structures & Algorithms Essentials gives the stack/heap and Big-O vocabulary this topic deepens into the theory underneath it.
  • Tools & environment: a macOS/Linux terminal; Python 3.13.12; a REPL for following along with the number/representation demos. Every example is standard-library-only (struct, sys, itertools, re, heapq, zlib, hashlib, array, time, math) -- no pip install is required anywhere in this topic.
  • Assumed knowledge: reading and writing typed Python functions and classes; comfort with arithmetic and simple algebra. No formal computer-science or discrete-math background is assumed -- this topic builds that background from first principles.

Why this exists -- the big idea

The problem before the solution: skip the bedrock and you hit a ceiling you can't explain -- why 0.1 + 0.2 != 0.3, why one loop runs 10x faster than an equivalent-looking one, why some problems have no fast solution at all no matter how clever the code. The one idea worth keeping if you forget everything else: everything you write runs on a finite machine built in layers from logic gates upward -- knowing the layers below lets you explain the anomaly you hit instead of just fearing it or copy-pasting a fix you don't understand.

Cross-cutting big ideas, taught here and then reused for the rest of this curriculum: layering-and-leaks -- the whole computing stack is abstraction stacked on abstraction over physical gates, and its leaks (float rounding error, cache-unfriendly access patterns, a stack that overflows) are exactly what this topic demystifies; abstraction-and-its-cost -- every layer you add buys convenience at a real, sometimes surprising, cost that only becomes visible once you understand the layer beneath it.

Confirm your toolchain

Every example in this topic is standard-library-only:

$ python3 --version
Python 3.13.12
$ python3 -c "import struct, sys, itertools, re, heapq, zlib, hashlib, array, time, math; print('stdlib CS-foundations primitives OK')"
stdlib CS-foundations primitives OK

Every example is a complete, self-contained, fully type-annotated (DD-39) runnable file colocated under learning/code/, actually executed to capture its documented output -- every printed value, bit pattern, and timing number on this topic's pages is a genuine, captured transcript, never a fabricated one.

How this topic's examples are organized

  • Beginner (Examples 1-18) -- positional number systems and base round-tripping, two's-complement negative integers, IEEE-754 floats and the 0.1 + 0.2 != 0.3 rounding error, endianness, UTF-8's variable-length encoding, boolean algebra and De Morgan's laws, truth tables and logic gates (including building AND/OR/NOT from NAND alone), the combinational-vs-sequential distinction via a half-adder and a clocked counter, set operations, relation properties (reflexive/symmetric/transitive), and the propositional-logic implication truth table.
  • Intermediate (Examples 19-40) -- predicate-logic quantifiers via all()/any(), permutations and the birthday-paradox collision probability, graph adjacency and cycle detection, proof by induction, a tiny register machine and ALU model, the memory-hierarchy latency survey and a real cache-friendly-vs-hostile timing measurement, the call stack and heap (including a live RecursionError), and finite automata through DFAs, NFAs, regex-to-FA equivalence, context-free grammars, pushdown automata, and the four nested Chomsky-hierarchy classes.
  • Advanced (Examples 41-55) -- Turing machines (a binary incrementer and a unary adder), the halting problem's diagonalization contradiction and a real "busy beaver" machine, P vs. NP (poly-time sorting, poly-time certificate verification, exponential brute-force SAT, an actual 3-SAT-to-Clique reduction, and factorial-growth brute-force TSP), Shannon entropy (a biased coin and real English text), lossless Huffman compression vs. lossy quantization, and checksums/hashing (CRC32 corruption detection and the SHA-256 avalanche effect).
  • Capstone -- a small "CS foundations toolkit": an int/float representation converter with an IEEE-754 bit inspector, a finite-automaton simulator run against a hand-traced regular language, and a real, measured row-major-vs-column-major cache-traversal timing demonstration.

The 28 concepts this topic covers

  • co-01 · Positional number systems -- binary/hex/decimal are positional systems; convert between bases by repeated division/multiplication, and every base's string round-trips through Python's own int(s, base). Examples 1-2, and the capstone's represent.py.
  • co-02 · Two's complement -- negative integers invert every bit and add 1, letting one adder circuit handle both addition and subtraction with no separate "subtract" hardware. Examples 3-4, and the capstone's represent.py.
  • co-03 · IEEE-754 floats -- a float is a sign/exponent/mantissa bit layout (IEEE 754-2019); the famous 0.1 + 0.2 != 0.3 rounding error is structural, not a bug. Examples 5-6, and the capstone's represent.py.
  • co-04 · Endianness -- byte order (big-endian vs. little-endian) in which a multi-byte value is stored or transmitted; struct.pack's </> prefixes and int.to_bytes's byteorder parameter make the order explicit. Examples 7-8.
  • co-05 · Unicode & UTF-8 -- Unicode assigns each character a code point; UTF-8 (RFC 3629) is the ASCII-compatible, variable-length encoding dominant on the wire, so len(str) and len(str.encode()) diverge the moment non-ASCII characters appear. Examples 9-10.
  • co-06 · Boolean algebra -- AND/OR/NOT (and derived XOR/NAND) form a complete algebra; De Morgan's laws let any expression be rewritten, and NAND alone is provably enough to build every other gate. Examples 11-13.
  • co-07 · Truth tables and gates -- a truth table enumerates every input combination's output; logic gates are the physical (or simulated) realization of a boolean function. Examples 11, 14.
  • co-08 · Combinational vs. sequential -- combinational circuits are pure functions of current inputs (a half-adder); sequential circuits add memory (state) via feedback, so the same call can return a different answer depending on what happened before (a clocked counter). Examples 14-15.
  • co-09 · Sets and relations -- sets, subsets, and relations (reflexive/symmetric/transitive) formalize "belongs to" and "is related to," directly mapped onto Python's own set type and hand -classified relation-property checks. Examples 16-17.
  • co-10 · Propositional logic -- propositions combine via AND/OR/NOT/implication/biconditional; a truth table decides validity, and material implication p -> q is false in exactly one of its four rows. Example 18.
  • co-11 · Predicate logic -- quantifiers universal (for-all) and existential (there-exists) extend propositional logic to statements over an entire domain's members, modeled directly by Python's own all() and any(). Example 19.
  • co-12 · Combinatorics and counting -- permutations, combinations, and counting principles that size a search space or a collision risk, including the counter-intuitive birthday-paradox threshold. Examples 20-21.
  • co-13 · Graph theory basics -- vertices/edges, directed/undirected, degree/path/cycle vocabulary underlying data structures and, later in this topic, automata themselves. Examples 22-23.
  • co-14 · Proof by induction -- a base case plus an inductive step proves a property for all naturals; the reasoning template recursion itself mirrors. Example 24.
  • co-15 · CPU registers and the ALU -- the fetch-decode-execute cycle; registers as fast local storage; the ALU as the arithmetic/logic execution unit, exposing status flags alongside its result. Examples 25-26.
  • co-16 · Memory-hierarchy intuition -- registers -> cache -> RAM -> disk trade capacity for latency (survey depth here; full treatment in a later architecture topic), made concrete by a real, measured cache-friendly-vs-hostile traversal timing. Examples 27-28, and the capstone's memory.py.
  • co-17 · Stack and heap -- the call stack holds frames with automatic lifetime that push then pop in strict LIFO order; the heap holds dynamically allocated data that can outlive the frame that created it, bounded by a real, catchable RecursionError. Examples 29-31.
  • co-18 · Finite automata -- a DFA/NFA (states, alphabet, transition function, start, accept states) recognizes a regular language; an NFA's epsilon-moves let it track multiple live states at once. Examples 32-34, and the capstone's automaton.py.
  • co-19 · Regex-to-FA equivalence -- Kleene's theorem: a language is regular if and only if a regex describes it, if and only if a finite automaton accepts it -- verified here by running Python's own re engine against a hand-built DFA on the exact same inputs. Examples 35-36, and the capstone's automaton.py.
  • co-20 · Context-free grammars and pushdown automata -- a CFG's productions generate a context-free language; a pushdown automaton (a finite automaton plus one stack) accepts exactly the context-free languages, including the classic non-regular aⁿbⁿ. Examples 37-39.
  • co-21 · Chomsky hierarchy -- four nested classes (regular subset-of context-free subset-of context-sensitive subset-of recursively-enumerable), each tied to a grammar restriction and a matching automaton. Examples 39-40.
  • co-22 · Turing machines -- an infinite-tape read/write/move state machine is the formal model of "what is computable" (the Church-Turing thesis), demonstrated with a real binary incrementer and a real unary adder. Examples 41-42.
  • co-23 · Halting problem -- no algorithm can decide, for every program/input pair, whether that program halts; proved by diagonalization (Turing, 1936), and illustrated by a real "busy beaver" machine whose halting behavior can only be learned by running it. Examples 43-44.
  • co-24 · P vs. NP -- P is the class of poly-time-solvable problems; NP is the class of poly-time-verifiable problems; whether P equals NP is open, contrasted here with genuinely measured polynomial (sorting) vs. exponential (SAT) growth. Examples 45-46, 49.
  • co-25 · NP-completeness and reductions -- an NP-complete problem is in NP and every NP problem reduces to it in polynomial time (Cook-Levin, SAT); a real reduction from 3-SAT to Clique is built and cross-checked here. Examples 47-49.
  • co-26 · Shannon entropy -- entropy quantifies the average number of bits needed to describe an outcome given its probability distribution (Shannon, 1948), measured here for a biased coin and for real English prose. Examples 50-51.
  • co-27 · Lossless vs. lossy compression -- lossless coding (Huffman, zlib) reconstructs the exact input; lossy coding (quantization) discards information for a smaller representation, and only one of the two paths round-trips exactly. Examples 52-53.
  • co-28 · Checksums and hashing -- a checksum (CRC32) detects accidental corruption; a cryptographic hash (SHA-256) is a fixed-size, effectively-irreversible digest that changes by roughly half its bits for even a one-character input change (the avalanche effect). Examples 54-55.

Examples by level

Beginner (Examples 1-18)

Intermediate (Examples 19-40)

Advanced (Examples 41-55)

← Previous: 18 · Technical Communication Drilling · Next: Beginner Examples →

Last updated July 15, 2026

Command Palette

Search for a command to run...