Comprehensive Study Guide to Computational Thinking, Algorithms, and System Abstraction

Foundations of Computational Thinking and Problem Solving

• Definition of Computational Thinking (CT):

  • Computational thinking is a critical cognitive skill and universal problem-solving approach utilized across diverse fields, from chefs and builders to software engineers and computer scientists.

  • It is defined as the ability to take a request expressed in human language, extract its fundamental meaning and essence, and produce a structured, high-value solution that fulfills the requirement.

  • It is an art form and a form of practical wisdom refined over years through experiment, practice, trial, and error.

  • Human communication is inherently imprecise; people frequently express vague, illogical, or impractical ideas. Computational thinking bridges the gap between ambiguous human intent and precise computational execution.

• The Three Core Techniques of Computational Thinking:

  • Algorithmic Thinking: Establishing a step-by-step sequence of rules or instructions to solve a problem.

  • Decomposition: Breaking down complex, daunting problems into smaller, simpler, and more manageable sub-problems.

  • Abstraction: Filtering out unnecessary real-world details to focus exclusively on essential characteristics.

• Formal Definition of a Problem:

  • A problem is defined as the measurable difference between the actual (current) situation and the desired situation.

  • Under this framework, virtually every human activity constitutes problem-solving, requiring a sequence of actions to transition from the current state to the desired state.

  • Example:

  • Actual State: Shoelaces untied.

  • Desired State: Shoes tied.

  • Problem Solving Requirement: Acquiring and applying the explicit process steps for shoe-tying.

• Engineering Requirements:

  • In engineering contexts, problems presented by clients or businesses are formally designated as requirements.

  • Automated problem-solving strategies implemented on computers mimic or copy human problem-solving heuristics.

Algorithmic Thinking and Process Design

• Definition of an Algorithm:

  • An algorithm is a finite sequence of precise, step-by-step instructions designed to solve a specific problem or perform a task.

  • It functions analogously to the method in a culinary recipe.

  • Once an algorithm is defined, programmers translate it into executable program code so a computer can execute instructions sequentially.

• Inputs and Outputs of Algorithms:

  • An algorithm processes defined inputs through a transformation routine to yield specific outputs.

• Example (Pythagoras Algorithm):

  • Inputs: Lengths of two perpendicular sides, $a$ and $b$.

  • Algorithm: $c = \sqrt{a^2 + b^2}$

  • Output: Length of the hypotenuse, $c$

  • Instruction Sequence and Optimization (Tea Making Example):

• Consider the instruction set: Fill kettle, Boil water, Get Cup, Get Teaspoon, Add Teabag, Wait, Pour Water into Cup, Wait, Add sugar, Add milk, Stir.

• Instruction order can often be altered without affecting the final quality, but evaluating order helps determine the optimal procedure.

• Key analytical considerations include:

  • Swappability of instructions without impacting output quality.

  • Input variables (such as explicit duration for Wait steps).

  • Action commonalities (identifying generic operations with varying inputs/outputs).

  • Termination criteria for individual sub-actions.

  • Pattern Recognition and Routine Generalization:

• Identifying repeated instruction sequences allows algorithm simplification.

• Attempt A (Explicit Repetition):

  • Add milk to mixture

  • Add 1 teaspoon of sugar to mixture

  • Add 1 teaspoon of sugar to mixture

  • Add 1 teaspoon of sugar to mixture

  • Add 1 teaspoon of sugar to mixture

  • Add 1 teaspoon of sugar to mixture

  • Stir mixture

• Attempt B (Loop Abstraction):

  • Add milk to mixture

  • Repeat 5 times: Add 1 teaspoon of sugar to mixture

  • Stir mixture

• Generalized Procedure (addIngredient):

  • Inputs: mixture, ingredient, measure, count.

  • Routine:       $\text{Repeat } \text{count} \text{ times: Add 1 } \text{measure} \text{ of } \text{ingredient} \text{ to } \text{mixture}$

  • Reusable implementation: addIngredient(mixture, sugar, 5, teaspoon).

Data Representation and Structural Decomposition

• Decomposition in Everyday Tasks:

  • Decomposition divides complex systems into discrete sub-problems or components.

  • Morning Preparation Task Decomposition:

  1. Wake up

  2. Wash

  3. Dress

  4. Breakfast

  • Sub-process Refinement (Waking Up):

  1. Alarm rings

  2. Hit 'snooze'

  3. Alarm rings again

  4. Get out of bed

  5. Transition to 'Wash' sub-process

  • Robotic Kinematic Refinement (Hitting Snooze):

  • Executing 'snooze' requires target distance calculation, reachability verification, and coordinated motor movements of a robotic arm.

• Data Structures for System Organization:

  • Lists: Sequential, ordered collections where each item has a defined position (index). Order altering changes execution outcomes.

  • Example (Navigation List): 1. Walk forward 10 steps $\to$ 2. Turn left $90^\circ$ $\to$ 3. Walk forward 5 steps $\to$ 4. Turn right $45^\circ$ $\to$ 5. Walk forward 2 steps.

  • Trees: Hierarchical, non-linear structures defining parent-child relationships between elements.

- *Example (Terraced House Hierarchy)*:
  - Root: `House`
  - Branches: `Ground Floor`, `First Floor`
  - Ground Floor Leaves: `Kitchen`, `Living Room`
  - First Floor Leaves: `Master Bedroom`, `Childs Bedroom`, `Bathroom`

• Binary Abstraction and Boolean Logic:

  • Microprocessors consist physically of electronic on/off switches.

  • Voltage levels ($0\,V$ vs $5\,V$) are abstracted to binary numbers ($0$ and $1$).

  • Binary values ($0$ and $1$) are further abstracted to logical Booleans ($\text{False}$ and $\text{True}$).

  • Abstraction Mapping Spectrum:

  • Electricity: $0\,V$ | $5\,V$

  • Electronics: $\text{OFF}$ | $\text{ON}$

  • Binary Number: $0$ | $1$

  • Boolean Logic: $\text{False}$ | $\text{True}$

  • English Language: $\text{No}$ | $\text{Yes}$

  • Graphics Color: $\text{Black}$ | $\text{White}$

Top-Down Modular Design and Software Systems

• Procedural Thinking in Complex Systems (OCR H046/H466 SLR20):

  • Trivial vs. Non-Trivial Problems: Trivial tasks can be solved by a single programmer, whereas non-trivial real-world problems (such as modern smartphone operating systems) are too complex for an individual and require structured system decomposition.

  • Stepwise Refinement: The systematic process of breaking a main task down into smaller sub-tasks, continuing until each sub-task performs a single isolated function.

  • Independent Modules: Sub-tasks at the lowest level are assigned to individual developers or small teams to be written and tested in isolation before global system integration.

• Wages System Case Study:

  • Root System: Wages

  • Top-Layer Components:

  • Get employee details

  • Calculate gross pay

  • Calculate deductions

  • Calculate net pay

  • Output wage slip

  • Second-Layer Modular Decomposition:

  • Calculate gross pay $\to$ Calculate normal wages + Calculate overtime

  • Calculate deductions $\to$ Calculate tax + Calculate National Insurance

  • Agile vs. Top-Down Design: Top-down design plans the complete system architecture upfront. Agile methodologies decompose small segments iteratively over time, allowing software solutions to emerge through refinement.

• UI Component Identification Case Study ("Enter New Employee Details"):

  • Identifying graphical user interface (GUI) elements required for implementation:

  • Action controls: Cancel button, Create button.

  • Static labels: Form title (Enter new employee details), field descriptions, required field marker (*Required fields).

  • Text inputs: Emp first Name*, Emp middle Name, Emp last Name*, Salary, Department, Manager.

  • Selection widgets: Drop-down select list (Part / full time*), calendar lookup tool (Hire date).

  • Input areas: Scrollable multiline text box (Notes).

  • Software Engineering Benefits:

  • Code Reuse: Reusing standardized UI widgets (such as calendar pickers or buttons).

  • Data Validation: Implementing input checks (such as blocking empty string submissions on fields marked with *).

• Control Flow Algorithm Representations:

  • Flowcharts & Pseudocode: Used to map decision logic prior to coding.

  • Fish Tank Carbon Dosing Case Study:

  • Input Range: Nitrate level from $1$ to $50$.

  • Rule 1: If nitrate $> 10$, dose $3\,ml$ carbon.

  • Rule 2: If nitrate is between $2.5$ and $10$, dose $2\,ml$ carbon.

  • Rule 3: If nitrate is between $1$ and $2.5$, dose $1\,ml$ carbon.

  • Rule 4: If nitrate $< 1$, dose $0.5\,ml$ carbon.

  • Pseudocode Implementation:

Nitrate = INPUT("Enter the nitrate level: 1-50")
IF Nitrate > 10 THEN
    PRINT("Dose 3ml")
ELSEIF Nitrate > 2.5 THEN
    PRINT("Dose 2ml")
ELSEIF Nitrate > 1 THEN
    PRINT("Dose 1ml")
ELSE
    PRINT("Dose 0.5ml")
ENDIF

Principles and Levels of Abstraction

• Formal Definitions of Abstraction (OCR H046/H466 SLR18):

  • Abstraction: The process of separating mental concepts from physical reality by suppressing or removing non-essential details, leaving only critical information.

  • Procedural Abstraction: Abstracting actual values used in a calculation into a generalized procedure.

  • Functional Abstraction: Abstracting the internal computation method entirely, leaving only a function interface.

  • Data Abstraction: Isolating how a compound data object is used from the low-level details of its construct.

  • Problem Abstraction / Reduction: Removing irrelevant operational details until a complex problem reduces to a fundamental base problem that has already been solved.

• Levels of Abstraction:

  • High-Level Abstraction: Captures overall purpose with minimal detail (e.g., a driver interacting with a car's steering wheel and pedals).

  • Low-Level Abstraction: Contains precise operational detail (e.g., a mechanic analyzing internal engine combustion and gear ratios).

• Real-World Abstraction Applications:

  • File Systems: The operating system abstracts physical storage (magnetic sectors, flash memory states) so users interact solely through standard file actions (Create, Open, Move, Save, Delete).

  • Sat-Nav Systems: Renders ignore environmental noise (trees, house colors, building heights) and highlight critical spatial driving data (road geometry, current position, speed limits, directional arrows, time, signal strength).

  • House Floor Plans: Retain room dimensions, door/window placement, and spatial boundaries while omitting wallpaper patterns, carpet pile, computer hardware models, and bedding colors.

  • Delivery Routing Maps: Retain street names, house positions, and road connectivity while omitting building heights, exterior paint colors, and parked vehicle locations.

Network Theory and Spatial Abstraction

• Spatial Representation vs. Topological Graph Abstraction:

  • Geographic maps preserve accurate spatial scale, distance, and physical terrain features.

  • Internal algorithmic navigation requires reducing maps to topological graph networks containing interconnected nodes and weighted edges.

• Network Graph Terminology:

  • Graph (Network): A structure composed of discrete points connected by lines.

  • Nodes (Vertices): Points representing discrete entities, junctions, intersections, or locations.

  • Edges (Arcs / Links): Lines connecting nodes, representing relationships, pathways, or distances.

  • Distorted Geography: Techniques used in urban transit maps (such as the London Underground tube map) that discard geographical distance accuracy to maximize topological readability for passengers.

• Maze Network Abstraction Case Study:

  • Ignored Physical Information: Wall thickness, material composition, wall height, visual surface textures.

  • Retained Topological Information: Entrance (start), exit (finish), dead ends, and decision junctions.

  • Graph Conversion Process:

  • Every decision point or terminal path end is designated as a numbered node ($1$ through $11$).

  • Every connecting corridor is mapped as an undirected edge.

• Maze Network Metrics:

  • Total Nodes ($\text{Vertices}$): $11$

  • Total Edges ($\text{Arcs}$): $10$

  • Traversable Solution Path: Node sequence $1 \to 2 \to 4 \to 6 \to 8 \to 9 \to 11$.

Boolean Logic, Venn Diagrams, and Deduction

• Boolean Operators (Named after George Boole):

  • AND: Logical conjunction. Evaluates to $\text{True}$ only if all constituent conditions are $\text{True}$.

  • OR: Logical disjunction. Evaluates to $\text{True}$ if at least one constituent condition is $\text{True}$.

  • NOT: Logical negation. Inverts the truth value of a condition ($\text{True} \to \text{False}$, $\text{False} \to \text{True}$).

• Boolean Identification Expressions:

  • Multi-condition logical filter for suspect identification:     $\text{NOT } \text{hasGlasses} \land \text{hasFacialHair} \land \text{hasDarkBrownHair} \land \text{hasGreenEyes}$

• Venn Diagram Set Operations (Sets: Flying Creatures, Birds, Flying Birds):

  • All Flying Creatures: The complete area enclosed by the Flying Creatures set.

  • All Birds: The complete area enclosed by the Birds set.

  • NOT Birds: The entire universe region lying outside the Birds set.

  • Flying creatures OR birds: The union set covering all regions inside either circle.

  • Flying creatures AND birds: The intersection set (Flying Birds).

  • NOT(Flying creature OR bird): The background region outside both sets.

  • NOT flying creature AND bird: The set region containing non-flying birds.

• Formal Logical Deduction Case Studies:

  • Case 1 (Unicorn Deduction):

  • Premise 1: Unicorns are immortal $\land$ awesome.

  • Premise 2: Subject is awesome.

  • Premise 3: Subject is $\text{NOT}$ immortal.

  • Conclusion: Subject is $\text{NOT}$ a unicorn.

  • Case 2 (Penguin Deduction):

  • Premise 1: A penguin is black and white $\land$ a bird.

  • Premise 2: Entity $A$ is a bird.

  • Premise 3: Entity $A$ is black and white.

  • Conclusion: Entity $A$ is a penguin.

  • Case 3 (Football vs. Penguin Deduction):

  • Premise 1: Footballs are round $\land$ black and white.

  • Premise 2: Entity $B$ is round, black and white, but $\text{NOT}$ a bird.

  • Conclusion: Entity $B$ is a football, $\text{NOT}$ a penguin.

Algorithmic Optimization, Concurrency, and Complexity

• Optimal Questioning Strategy (Binary Search Principle):

  • To identify a specific item from a set using the minimum number of binary (Yes/No) questions, each question must bisect the remaining candidate pool in half.

  • Search resolution scales exponentially with question count $N$ ($2^N$ total items resolved with $N$ questions):

  • $1 \text{ question} \implies 2^1 = 2 \text{ suspects}$

  • $2 \text{ questions} \implies 2^2 = 4 \text{ suspects}$

  • $3 \text{ questions} \implies 2^3 = 8 \text{ suspects}$

  • $4 \text{ questions} \implies 2^4 = 16 \text{ suspects}$

  • $5 \text{ questions} \implies 2^5 = 32 \text{ suspects}$

  • $10 \text{ questions} \implies 2^{10} = 1024 \text{ suspects}$

• Binary State Indexing:

  • Attributes mapped to binary flags ($\text{No} = 0, \text{Yes} = 1$):

  • Simon: $(0, 0, 0, 0)_2 = 0$

  • Paul: $(0, 0, 0, 1)_2 = 1$

  • Pete: $(0, 0, 1, 0)_2 = 2$

  • Bill: $(0, 0, 1, 1)_2 = 3$

• Concurrent Processing and Multithreading:

  • Concurrency: Executing multiple tasks simultaneously or within overlapping time slices on a processor.

  • Divide and Conquer / Fork and Join: Splitting a computational task across parallel processing units (or agents) concurrently and joining results. Essential in graphics processing units (GPUs) and artificial intelligence.

  • Threads: Sequences of instructions executed sequentially by a CPU core. Applications running multiple concurrent threads are multithreaded.

  • System Benefits: Increases task throughput and eliminates processor idle time spent waiting for inputs.

• Algorithm Efficiency and Intractability:

  • Importance of Efficiency: Fast algorithms reduce CPU usage, lower power consumption, reduce heat generation, lower infrastructure costs, and provide responsive, buffer-free execution.

  • Causes of Inefficient Software: Increased development complexity, lack of financial incentive for efficiency in rapid development cycles, poor team communication, and business short-termism.

  • Brute Force Searching: Exhaustively testing every possible state or path (e.g., testing password dictionaries, checking all maze paths, or evaluating all chess move trees).

  • Intractable Problems: Problems that possess a theoretical algorithmic solution, but whose execution time grows exponentially as input size $n$ increases, making them practically unsolvable for large inputs.

• Time Complexity Growth Comparison Matrix:

• Execution duration comparison table across input sizes ($n = 10$ to $n = 60$):

  • Linear Complexity ($A_1 = n$):

    • $n=10$: $0.00001\,\text{sec}$

    • $n=60$: $0.00006\,\text{sec}$

  • Quadratic Complexity ($A_2 = n^2$):

    • $n=10$: $0.0001\,\text{sec}$

    • $n=60$: $0.0036\,\text{sec}$

  • Cubic Complexity ($A_3 = n^3$):

    • $n=10$: $0.001\,\text{sec}$

    • $n=60$: $0.216\,\text{sec}$

  • Polynomial Complexity ($A_4 = n^5$):

    • $n=10$: $0.1\,\text{sec}$

    • $n=60$: $13.0\,\text{min}$

  • Exponential Complexity ($A_5 = 2^n$):

    • $n=10$: $0.001\,\text{sec}$

    • $n=60$: $366\,\text{centuries}$

  • Higher Exponential Complexity ($A_6 = 3^n$):

    • $n=10$: $0.059\,\text{sec}$

    • $n=60$: $1.3 \times 10^{13}\,\text{centuries}$

Logic Puzzles and Analytical Deduction

• Puzzle 1: Sibling Age Ordering:

  • Premises:

  1. Aiden is not the oldest.

  2. Sophia is younger than Aiden.

  3. Jack is not the youngest.

  • Deduction:

  • Premise 1 indicates Aiden must be either Middle or Youngest.

  • Premise 2 states Sophia is younger than Aiden, forcing Sophia to be Youngest and Aiden to be Middle.

  • Premise 3 states Jack is not the youngest, so Jack must be Oldest.

  • Result: Sophia (Youngest) < Aiden (Middle) < Jack (Oldest).

• Puzzle 2: Three Treasure Chests:

• Premises:

  • 3 chests exist (Left, Middle, Right).

  • At least one chest contains treasure; empty chests contain deadly poison.

  • Each chest has a sign, but ALL signs are lying (False).

• Sign Statements:

  • Left Chest Sign: "The middle chest has treasure"

  • Middle Chest Sign: "All chests have treasure"

  • Right Chest Sign: "Only one chest has treasure"

• Deduction Steps:

  1. Left sign is False $\implies$ The Middle chest does NOT contain treasure.

  2. Middle sign is False $\implies$ NOT all chests contain treasure (at least one is poison).

  3. Right sign is False $\implies$ NOT only one chest has treasure (so either $0$ or $>1$ chests have treasure).

  4. Since at least one chest has treasure, there must be $>1$ treasure chests. Thus, exactly $2$ chests contain treasure.

  5. Because the Middle chest is proven empty, the $2$ chests containing treasure are the Left Chest and the Right Chest.

Key Terminology and Formal Definitions

• Abstract Data Type (ADT): A data type class defined by a set of logical values and permitted operations, independent of computer memory implementation.

• Abstraction: A core component of computational thinking where non-essential characteristics of objects or systems are removed to reduce them to essential features.

• Algorithm: A finite set of clear, step-by-step logical instructions followed to solve a problem or complete a task.

• Composition: The process of combining smaller software components or subsystems to construct a complex overall system (the inverse of decomposition).

• Computational Thinking: The cognitive process involved in formulating problems and structuring solutions so a computer can execute them.

• Concurrent Processing: A execution model where multiple tasks run concurrently on processing hardware, with time slices allocated to each task.

• Data Composition: Combining primitive data objects to build compound data structures.

• Decomposition: Breaking down a complex problem into smaller, independent sub-problems that can be analyzed and solved individually.