Table of Contents
Public units
| Unit | Title | Use |
|---|---|---|
| Readme | Computational Thinking - Readme | Follow worked connections between algorithmic methods. |
| Preface | Computational Thinking - Preface | Understand the connected methods, their rationale, sources and limits. |
Part A - Construct an algorithm
| § | ID & Title | Status | Keywords & Search Queries | Dependencies |
|---|---|---|---|---|
| 1 | CMP.1 - Solve One Problem through Another or Transfer a Limit (Computational Reduction) | Usable, evolving | reduction; solver reuse; input conversion; answer recovery; computability; complexity. Can this problem be solved through another one, and in which direction does a limit transfer? | C.29.2 for the required answer and computational model; MATH.17/.18 for composition and interpretation. |
| 2 | CMP.2 - Derive a Recursive Procedure from a Problem Decomposition | Usable, evolving | recursion; decomposition; induction; sufficient return; termination. What must smaller problems return so that their answers construct the required whole? | MATH.4/.12 for inductive or extracted constructions; C.29.2 for the computational formulation. |
| 3 | CMP.3 - Share and Schedule Repeated Subcomputations | Usable, evolving | memoization; dynamic programming; sharing; dependency order; effects; storage; recomputation. Which repeated subcomputations can share an answer, in what order, and what should be retained or recomputed within the memory limit? | CMP.2 for the recurrence; CMP.10 for representation and operation costs. |
| 4 | CMP.4 - Construct Computational Search with Justified Exclusions | Usable, evolving | search; branch and bound; pruning; witness; completeness; interruption. Which alternatives can be excluded while preserving the requested answer? | MATH.20 for bounds; CMP.5 for relaxation; MMP.10 for a subject constraint formulation when needed. |
| 5 | CMP.5 - Bound an Optimum or Recover a Feasible Candidate through a Relaxed Problem | Usable, evolving | relaxation; feasible recovery; upper and lower bounds; approximation. How can an easier problem improve or bound an answer to the original problem? | MATH.20 for comparison; CMP.4 for bounded search; CMP.8 for controlled approximation. |
| 6 | CMP.6 - Derive an Iterative Computational Update from Local Information | Usable, evolving | local search; iterative update; neighborhood; step choice; noisy feedback; stopping. What does an admissible local change improve, and what follows on stopping? | MATH.10/.20/.21 for variation, bounds or convergence; CMP.7 for learning that needs an update. |
| 7 | CMP.7 - Construct a Learner from Examples and Feedback | Usable, evolving | learning algorithm; rule class; inductive restriction; feedback; training fit; generalization. Which rule should examples select, and what supports its further use? | CMP.4/.6 for selection or updating; MMP.7 for a modeled data source; C.11.DUA for consequential additional inquiry. |
Part B - Control error and computational cost
| § | ID & Title | Status | Keywords & Search Queries | Dependencies |
|---|---|---|---|---|
| 1 | CMP.8 - Construct an Approximate Computation with Controlled Error | Usable, evolving | approximation; scaling; discretization; finite stopping; rounding; conditioning. How can a permitted error reduce computation while retaining the answer quality needed next? | MATH.20/.21 for bounds and convergence; CMP.3/.10 for shared computation and representation. |
| 2 | CMP.9 - Construct a Randomized Estimator or Sampling Procedure | Usable, evolving | randomized algorithm; sampling; estimator; proposal; dependence; stopping time. Which random procedure supplies the required law or finite-run estimate? | A supplied probability target, with MMP.7 where modeled; CMP.10 for access and storage. |
| 3 | CMP.10 - Choose a Computational Representation for Its Access and Update Operations | Usable, evolving | data structures; representation; queries; updates; conversion; arithmetic; memory. Which representation makes the required operations affordable? | CMP.2/.3 for compositional summaries and shared work; MATH for preserved structure. |
| 4 | CMP.11 - Derive a Computational Lower Bound from Indistinguishable Inputs | Usable, evolving | lower bound; adversary; indistinguishable inputs; decision tree; communication; error. What must every algorithm in this model observe or communicate? | MATH.19/.20 for argument and bound; CMP.1 for reduction; C.29.2 for the cost model. |
Part C - Interpret, transform and compose computations
| § | ID & Title | Status | Keywords & Search Queries | Dependencies |
|---|---|---|---|---|
| 1 | CMP.12 - Construct an Interpreter or a Meaning-Preserving Translation | Usable, evolving | interpreter; compiler; semantics; binding; environment; control; observable behavior. How does an expression execute, and what must its translation preserve? | MATH.5/.17/.18 for expression composition and interpretation; C.29.3 when realizing the primitives. |
| 2 | CMP.13 - Construct a Computational Abstraction for the Property Being Asked | Usable, evolving | abstract interpretation; reachable states; sound approximation; fixed point; refinement. Which cheaper computation supports this property, and can its counterexample occur? | MATH.2/.18 for identification and interpretation; CMP.3/.4 for scheduling and exploration. |
| 3 | CMP.14 - Compose Interacting Computations through Their Required Observations | Usable, evolving | concurrent algorithm; shared state; protocol; atomicity; interference; progress. Which interactions preserve the required whole behavior? | CMP.3/.10/.12 for dependencies, representation and semantics; C.29.3 for implementation assumptions. |