Computational Thinking - Preface
CMP.Preface:1 - Problem frame and the algorithmic difficulty
Use this language when you need to construct, understand, analyze or change an algorithm. The work can concern a finite answer, a continuing response, a learning rule, or several processes whose interaction matters. A practitioner may be designing the procedure, reviewing one produced by an AI agent, explaining why it works, or deciding how to divide the work among implementations and performers.
A mathematical definition can specify the desired object while leaving its obtaining procedure unknown. An algorithm can compute the right value on a small input yet require unaffordable resources on the intended inputs. A program can work in isolation while changing its neighbors’ observations when used in a larger computation. These are different difficulties; their remedies can need different mathematical constructions and execution assumptions.
The domain here is algorithmics within computer science. The methods concern effective operations, their composition, representations, meaning, correctness, termination, continuing progress and resource requirements. Symbolic manipulation, discrete search, numerical approximation, sampling and learning are branches in which those questions arise. Their worked cases show how to use a method; they supply no universal requirement to know a particular physical theory or programming technology.
Start with elementary algorithmic reasoning: inputs, operations, retained state, outputs and the ability to follow a short procedure. Individual bodies introduce their additional constructions. Recursion uses induction and a progress relation; randomized methods need the relevant probability account; a numerical update can require derivatives or an error bound. A concurrency question needs the proposed shared operations and scheduling assumptions. Obtain a missing contribution or learn it through a suitable example before relying on the result that uses it.
Use a known adequate algorithm directly when there is no construction or interpretation difficulty. If the unsettled question is what the subject model means, return to mathematical modeling. If it concerns whether a machine supplies the required operations, timing or physical resources, connect the algorithmic requirements to physical realization. These returns let the relevant specialist or agent work on the missing contribution.
CMP.Preface:2 - Forces that shape the construction
| Requirement | Choice it creates |
|---|---|
| A useful answer | A decision, one witness, every witness, an approximation and a continuing response can require different procedures. |
| Feasible resources | Conversion, preprocessing, memory, communication and output can dominate the apparent main computation. |
| Sufficient retained information | Sharing or summarizing work saves resources while potentially discarding a later-required distinction. |
| A justified conclusion | Small executions help expose a failure; a general guarantee needs an argument covering its admitted inputs and operations. |
| Useful results under uncertainty | A conditional answer, bound or heuristic candidate can be enough; stronger assurance should change the receiving choice enough to repay its cost. |
| Reuse in a changed setting | A different primitive, observation, input promise or interaction can invalidate a formerly correct construction. |
C.29.2 in FPF supplies the computational formulation: what is represented, what answer is required and which operations and resources are available. C.11.DUA helps choose how much additional inquiry or assurance the work warrants. The CMP methods construct the algorithmic contribution needed under that formulation. They do not require a proof or benchmark that cannot change the next useful action.
CMP.Preface:3 - The methods and their connections
CMP.Preface:3.1 - Construct an algorithm
CMP.1 connects a new computational problem to a solver for another one. Its conversion and answer recovery also determine the direction in which an impossibility or resource result can travel. CMP.2 constructs a recursive procedure by choosing smaller problems, sufficient returned information and a reason for progress. CMP.3 turns repeated subcomputations into a shared dependency structure, choosing evaluation order and what to store or recompute.
CMP.5 obtains a tractable relaxation and connects its bound or solution back to the original problem. CMP.4 uses such bounds, or other justified conditions, to exclude search branches without losing the requested result. A feasible candidate can be useful before search finishes; its quality claim depends on the remaining alternatives and available bound.
CMP.6 constructs an admissible iterative change from local information. The neighborhood and progress argument decide what stopping establishes. CMP.7 constructs the procedure that selects or updates a rule from examples and feedback. It separates that procedure from the resulting rule and separates successful optimization from what the rule supports on further cases. Search or iterative updating can supply its obtaining operation.
CMP.Preface:3.2 - Control error and computational cost
CMP.8 turns a permitted approximation into an effective computation with an error and stopping account. Mathematical convergence supplies part of the reasoning; the algorithm still needs usable operations and a finite return condition. CMP.9 constructs sampling and estimation, retaining the target law, dependence and stopping conditions. A random output, a sample distribution and an estimate have different uses.
CMP.10 derives a data representation from the required access and update operations. It exposes costs moved into conversion, maintenance or output. CMP.11 proves a lower bound by finding inputs that remain indistinguishable under the allowed observations but require different answers. It constrains all procedures within that model; a changed access operation or tolerated error can reopen the conclusion.
These methods can change the construction in Part A. A prohibitive shared table can motivate scaling, another representation or a weaker answer. A lower bound can redirect the question rather than motivate another attempt at the same impossible guarantee. A randomized construction remains subject to the output conditions the receiving work needs.
CMP.Preface:3.3 - Interpret, transform and compose computations
CMP.12 constructs an evaluator or a translation by specifying expression meaning, binding, primitive operations and control. The preservation relation follows what the receiving computation can observe. CMP.13 constructs a cheaper abstract computation for a selected property, with operations that justify its conclusions and a way to reconstruct or refine an apparent counterexample. CMP.14 constructs the shared-state or communication behavior needed when computations interact, including the assumptions under which progress follows.
The returned operations can themselves become objects of further work: an algorithm can interpret another algorithm’s description, a translator can transform it, and an abstract procedure can inspect its possible behavior. Mathematical Thinking supplies constructions of operations and interpretations. CMP adds effective execution and its consequences under the chosen computational model.
There is no compulsory fourteen-stage process. A reader with an adequate formulation can enter at a missing bound or representation. A representation failure can return to the recurrence; a semantic failure can return to interpretation; a communication failure can return to composition. Keep the required result and the assumptions of these connections visible when different agents supply the contributions.
CMP.Preface:3.4 - Constituent actions in ongoing work
Updating a visited set can be part of executing a graph-search algorithm while a route-finding task is under way. Changing the required answer from any route to a route with the fewest edges changes which frontier-selection discipline suffices; a successful visited-set update alone does not establish the stronger result. The practitioner needs to connect the local update, the algorithm’s invariant and the route requirement, while retaining its representation and memory conditions. Knowing set operations and the desired route can leave that intermediate algorithmic reasoning missing.
FPF B.1.5.EW helps recover these constituent–whole connections; B.1.5.RS examines a proposed replacement. Use the parts of the vertical that can change the present result. A Method described here can require additional capability, available support and compatible resources at other grains.
CMP.Preface:4 - Worked connection - One best selection becomes every best selection
Suppose a finite list contains individually identified options. Each may be chosen at most once. Costs are positive integers and values are nonnegative integers. A selection’s cost and value are the respective sums for its chosen options; total cost must not exceed capacity W. The first request is the maximum value and one selection achieving it. These are stipulated model conditions; whether they describe an actual investment, experiment or production choice is a separate modeling question.
Use three options: A costs 4 and has value 7; B costs 3 and has value 5; C costs 2 and has value 3. Capacity is 5.
Construct what a smaller problem must return. CMP.2 defines R(i,b) as the best value using the first i options with remaining capacity b. The base is R(0,b)=0. If option i costs w_i and has value p_i, its recurrence is:
R(i,b) = R(i-1,b) when w_i > b;
R(i,b) = max(R(i-1,b), p_i + R(i-1,b-w_i)) otherwise.
Every selection either excludes or includes option i, so these branches cover its possibilities. Both use a smaller i. Store a choice attaining the maximum when a witness is required. For A, B and C, the final values at capacities 0 through 5 are 0, 0, 3, 5, 7, 8; recovering the choice at capacity 5 gives B and C.
Share subproblems and compare cost. CMP.3 computes each needed pair (i,b) once in dependency order. A full table has (n+1)(W+1) cells and O(nW) updates. This is a count of table operations; arithmetic cost depends on the size of the values. Since W is encoded with about log₂(W+1) bits, this procedure can still be expensive relative to input length. Keeping just two value rows reduces storage, but recovering the selection then requires retained decisions or recomputation. CMP.10 helps compare those operations for the actual workload.
Use a cheaper bound when it settles the request. CMP.5 allows fractional choices solely to obtain an upper bound. At capacity 5, take all of A and one third of B: the relaxed value is 26/3. The corresponding fractional optimum follows by considering value per unit cost, or by the bound derived in CMP.4’s worked case. Original values are integers, so they are at most 8. The feasible B+C selection reaches 8. CMP.4 can therefore finish the optimality question without searching every remaining branch. When a bound does not settle it, the search retains the unresolved alternatives.
Change the requested answer and a supplied option. Add D, costing 4 with value 8, and request every optimal selection. The new final value row is 0, 0, 3, 5, 8, 8. D and B+C both attain 8. D cannot be combined with another option within capacity; the earlier argument bounds all selections omitting D. The old fractional bound does not cover the changed list: the new relaxation can take D and one quarter of A, giving 39/4. That bound alone leaves the integer value 9 unresolved.
A search for one optimum can discard a branch whose best possible value equals the incumbent. A search for every optimum must retain a branch that may contain a different equal-valued witness. Similarly, a table storing only the minimum cost for each value keeps D at cost 4 for value 8 and can discard B+C at cost 5. Recovering all ties in that compressed table cannot recover a selection already discarded for being heavier.
Return to the original recurrence. After computing R, recover every optimal selection by following each branch whose value equals R(i,b), retaining the distinct choices. At (4,5), both exclusion, R(3,5)=8, and inclusion, 8+R(3,1)=8, qualify. They recover B+C and D. CMP.4 supplies the changed exclusion condition; CMP.3 supplies the retained dependencies or recomputation; CMP.10 exposes what a compressed representation lost. The value calculation survives, while the witness procedure changes. Enumerating all witnesses can require exponential output even if the value table is small.
If the work later permits a near-optimal value, CMP.8 can trade a quantified rounding loss for a smaller computation. That different request does not supply every optimizer of the unrounded problem. Select the answer the work needs before choosing the shortcut.
The same connected method can be used with other finite recurrences and search constructions. Independent additivity and integer capacity belong to this example. A different problem may require different state, recurrence and bounds while preserving the need to connect answer, construction, retained information and cost.
CMP.Preface:5 - Use checks, assumptions and recurring failures
The worked cases use small inputs and explicit operations so that a reader can reconstruct the method and change a premise. A physical machine can provide different arithmetic, atomicity or memory behavior. An empirical data source can violate the probability or feedback assumptions used by an algorithmic argument. Carry those requirements to the appropriate implementation or subject inquiry when they matter to use.
For a combination of methods, check the following substantive questions:
- Does the original question require a value, a witness, complete enumeration, an approximation or a continuing behavior?
- Can each contribution actually obtain what the next one consumes, under the same input, meaning and resource conditions?
- What is retained or discarded by sharing, compression, relaxation, sampling, learning or translation, and can that change the requested answer?
- Which argument covers correctness and which covers termination or continuing progress? Are their operations and assumptions available in this setting?
- When a condition changes, which dependent conclusion must be revised and which earlier work remains useful?
Use the relevant body’s checks where its operation enters; an unchanged supplier need not be rederived. Whole-computation costs can include simultaneously retained tables, repeated conversions or shared communication, even when each local operation is affordable.
| Failure invited by the construction | Practical correction |
|---|---|
| Memoization identifies calls by visible arguments while ignoring changing state or effects | Include the consequential context or avoid that reuse. |
| An optimum value is taken to supply every optimal witness | Preserve or reconstruct every required choice; account for output size. |
| Local improvement or training fit is treated as a guarantee about a different target | Recover the actual neighborhood, feedback and performance claim. |
| A stationary sampling law is treated as a finite-run independent sample | Establish the finite-run distribution or use an applicable dependence bound. |
| A translation or composition is checked only by its final value | Include the intermediate observations, failures and progress on which its context relies. |
| A model-specific limit is treated as an unrestricted impossibility | State the access and cost model, error and input promises, then examine which change escapes the bound. |
Being able to repeat a trace is useful preparation but leaves transfer to be tried. Ask the learner or assisting agent to change an input promise, required output or execution rule and recover the affected construction. Human learning, an AI agent’s immediate performance and a learned rule’s statistical generalization are different capability questions; their assessment should fit the intended work.
CMP.Preface:6 - Consequences and Architectural Rationale
The repertoire makes a computational contribution discussable before a finished program exists. A practitioner can construct a recurrence, identify a missing return, derive a bound, change a representation or expose a failing interaction. These results support implementation, explanation, reuse and further inquiry. Their cost ranges from tracing a few states to constructing a substantial new algorithm or proof.
The organization follows recurring algorithmic work across branches. A catalogue arranged by familiar algorithms is useful when a reader already recognizes the problem and needs an implementation. A textbook organized by mathematical topics can develop deeper theory. This language serves the choice and construction between those points: what operation is missing, how its result will be obtained, and which downstream use it supports. Its fourteen methods are a selected repertoire; a specialized graph, geometric, cryptographic or other algorithm can require additional subject techniques.
Several apparent overlaps are useful distinctions of work. CMP.5 constructs a relaxation and recovery, while CMP.4 decides which search branches its bound can exclude. CMP.3 shares equivalent subcomputations, while CMP.13 deliberately summarizes possibilities for a selected conclusion. CMP.12 preserves the execution meaning needed by a translation, while CMP.14 supplies the interactions needed by the combined computation. Their outputs can be connected without making those methods interchangeable.
Mathematical Thinking supplies objects, operations, arguments and limits; Mathematical Modeling connects a subject question with those constructions. CMP develops effective obtaining procedures and their algorithmic consequences. Physical Thinking and C.29.3 connect required operations to physical interactions, preparation and readout. The computational and physical models must correspond where a claim about execution depends on both. A computational lower bound and a physical performance bound can therefore constrain different aspects of the same proposed system.
Notations and methods of work also matter. An expression can hide binding or evaluation rules that CMP.12 needs to expose. A mathematical model of a working method can use CMP.14 to compare orders and interactions, while the actual organizational roles and responsibilities still require a methodological account. FPF’s B.5.MPC coordinates the mathematical, physical and computational contributions; ME develops the corresponding changes to ways of working.
This arrangement permits several routes and several performers. An AI agent can propose code, a specialist can supply a bound and another procedure can check a property. Their contribution remains usable only with the meaning and conditions its receiver needs. A new source or capability can change one construction and the affected connections without replacing the whole language. An unsupported operation becomes a useful next inquiry when resolving it could change what the work can do.
CMP.Preface:7 - Shared sources, alternatives and relations
Erickson’s algorithm construction material and Morin’s Open Data Structures support the connection between a problem, its representations, a constructed procedure and its argument. The bodies retain explicit conversions, recurrences and operation costs. Direct use of a known algorithm remains preferable when constructing another one adds no needed capability.
The approximation and learning sources cited in CMP.5-.9 connect a deliberately weakened or data-dependent answer to the procedure that obtains it. They also expose limits: a recovered relaxed solution needs feasibility and quality arguments; an optimized training criterion leaves generalization conditions to be established. CMP.8 compares its transparent scaling construction with a stronger recent knapsack scheme. CMP.7 compares historical assessment with adaptive assessment under temporal change. Those comparisons justify reopening the corresponding method when another construction changes cost or supported use.
SICP’s evaluator and compiler construction supplies an explicit historical demonstration of programs that interpret and transform programs. CMP.12 combines that construction with current behavior-preservation distinctions. Cousot’s Principles of Abstract Interpretation develops computable summaries from the properties they must support; CMP.13 compares direct exploration, coarser abstractions and targeted refinement. These approaches answer different questions: a useful overapproximation can deliberately introduce behaviors that a meaning-preserving translation would have to treat differently.
Lamport’s A Science of Concurrent Programs and the composition, memory and crash studies discussed in CMP.14 support its separation of observable behavior, permitted interaction and progress. Sequential composition is cheaper when interference is absent. More detailed composition arguments earn their place when shared observations or failures change what the whole computation can do. Each body gives the adopted contribution, serious alternative and conditions that would reopen its selection.
The Suite Reference locates the related publications and explains their shared architecture. C.29.2 supplies computational formulation; C.29.3 physical realization; C.29.1 the transfer between mathematical accounts; C.29 the model-to-subject correspondence. B.5’s inquiry methods support the next question when a limit or failure makes the old one insufficient. Notational Engineering supplies methods of expression design as those contributions become available; the operative rules stated in CMP remain usable without an unwritten supplier.
The three Parts group the presentation. The fourteen bodies form a repertoire of related Methods, usable individually or in combinations selected for the question. A particular connected use can describe a composite way of working, but membership in this publication alone does not make every method a mandatory step of that work.