Thinking Ahead

Thinking ahead means identifying the inputs, outputs, and pre-conditions of a problem before writing any code. A programmer who thinks ahead considers: what data will the program receive? What should it produce? What conditions must hold before the algorithm can run correctly? What might go wrong?

Preconditions

A precondition is a condition that must be true before a function or algorithm is called for it to produce correct results. Example: a binary search precondition is that the list must already be sorted. If the precondition is violated, the function's behaviour is undefined.

Pre-conditions simplify functions by letting them assume input is already in the expected state. They are part of good software specification — they form a contract between the caller and the function.

Caching and Prefetching

Caching is thinking ahead about what data will be needed next and storing a pre-computed or pre-fetched copy so it is ready immediately. CPU caches store frequently-used memory addresses. Web browsers cache downloaded resources. Memoisation in programming caches the results of expensive function calls.

Prefetching fetches data into cache before it is explicitly requested, based on prediction of what will be needed next. A CPU uses branch prediction to prefetch instructions it thinks will follow a branch.

Reusable Components

Thinking ahead also means designing code for reuse: writing functions, modules, libraries, and classes that are general enough to be used in multiple contexts. This requires planning the interface (parameters and return types) before writing the implementation. It avoids code duplication (DRY — Don't Repeat Yourself).

Thinking Procedurally

Thinking procedurally means identifying and ordering the steps required to solve a problem, then identifying which steps can be expressed as sub-procedures and combining them into a complete solution. It is the basis of procedural (imperative) programming.

Procedural thinking maps directly to structured programming concepts: sequence (steps in order), selection (if/else/case), iteration (loops), and sub-routines (procedures and functions).

Identifying Sub-procedures

A key skill is recognising when a sequence of steps is a coherent, reusable sub-task and extracting it into a named procedure. Benefits: readability (main program reads like an outline), reusability (call the same procedure from many places), testability (test each procedure independently), maintainability.

Thinking Logically

Thinking logically means identifying the conditions that determine which path through a program to take, and expressing those conditions precisely using Boolean logic. It requires being exact about what conditions must be true for each branch to execute.

Conditions and Decisions

For each decision point in an algorithm, a programmer thinking logically asks: what must be true for branch A vs. branch B? Are the conditions mutually exclusive? Do they cover all cases? Are there edge cases?

Boolean Logic in Decision Making

Conditions use Boolean operators: AND (both must be true), OR (at least one must be true), NOT (negation). Thinking logically ensures conditions are precise, non-overlapping, and cover all possible input states (exhaustive).

Proof and Verification

Thinking logically also includes trace tables (manually executing an algorithm with test data to verify correctness), dry runs, and using formal logic to prove an algorithm is correct. For exam purposes: identify conditions, express them as Boolean expressions, and verify with test cases.

Thinking Concurrently

Thinking concurrently means identifying parts of a problem that can be solved at the same time (in parallel), rather than sequentially (one after another). This is important in multi-core processors, distributed systems, and multi-threaded applications.

Concurrent vs Sequential

Identifying Concurrent Tasks

Not all problems can be parallelised. A task can be run concurrently only if it is independent of other concurrent tasks — it does not need their results as input, and they do not share mutable state.

Example: rendering the frames of a video independently. Frame 50 does not depend on frame 49's render completing first — they can be rendered on different CPU/GPU cores simultaneously.

Counter-example: summing a list sequentially. Each addition depends on the previous result. However, the list can be split and sub-sums computed in parallel, then combined — this is the parallel reduction pattern.

Problems with Concurrency

• Race condition: Two threads read/write shared data in a non-deterministic order, leading to incorrect results depending on timing.
• Deadlock: Two or more threads wait for each other to release a resource — neither can proceed.
• Starvation: A thread is perpetually denied the resources it needs because other threads keep getting priority.

Solutions include mutexes (mutual exclusion locks), semaphores, and designing algorithms to avoid shared mutable state.

Concurrency in Real Systems

• Multi-core CPUs: Run multiple threads simultaneously on different cores
• GPU computing: Thousands of cores run the same operation on different data (SIMD — Single Instruction, Multiple Data)
• Distributed computing: Different machines run different parts of a computation (MapReduce, Hadoop)
• Pipelining: CPU overlaps instruction stages (fetch, decode, execute, write-back) so multiple instructions are in different stages simultaneously