Concepts related to problem-solving

Problem-solving in computing is the craft of turning a real-world need into a precise, testable
procedure and then a working program. Below are deeper, interconnected explanations of the
core concepts you’ll use and teach: problem, solution, algorithm (as a problem-solving strategy,
and its role and importance), and program—enriched with practical nuance, pitfalls, and
examples.

Problem

 Definition: A problem is a clearly articulated need, question, or objective with

boundaries (constraints) and success criteria (what counts as a valid answer). A good
problem statement removes ambiguity by specifying inputs, outputs, context, and limits
so different solvers reach consistent, verifiable results.

 Essential components:

o Context: The environment and purpose shape requirements (e.g., tally daily sales
vs. real-time fraud detection—both “sum totals,” but the second has latency and
accuracy constraints).

o Inputs: What data is given or must be collected, including format and quality
expectations (e.g., integers vs. floats, missing values allowed?).

o Constraints: Time, memory, legal, ethical, platform, and user experience limits
(e.g., run in O(n) time, respect privacy, run on a mobile device).

o Desired output: The exact form and properties of the result (e.g., “return a
sorted list, stable order, ascending, with duplicates preserved”).

 Why clarity matters:

o Prevents misalignment: Vague problems lead to “correct” programs that solve

the wrong task.

o Reduces rework: A precise statement exposes edge cases early.

o Enables testing: Clear inputs/outputs let you design deterministic test cases and
acceptance criteria.

Solution

 Definition: A solution is the method or outcome that meets the problem’s requirements
under its constraints. It can be conceptual (plan), procedural (step sequence), or
computational (machine-executable).
  Forms of solutions:

o Conceptual: Describes the idea (e.g., “use a running aggregate to compute

mean/variance”).

o Procedural: Outlines executable steps (e.g., “for each item, update sum, count,
then divide”).

o Computational: Precisely structured for a machine, with defined data types,

control flow, and termination.

 Quality criteria:

o Correctness: Produces expected outputs for all valid inputs; proven with
reasoning and tests.

o Completeness: Addresses all stated requirements and edge cases (e.g., empty
input, max ranges, invalid formats).

o Efficiency: Uses acceptable time and space; recognizes trade-offs (fast vs.
memory-light).

o Robustness: Handles anomalies gracefully (e.g., fallbacks, validation, safe

defaults).

 Common pitfalls and remedies:

o Solving the wrong problem: Recheck the specification; validate with examples.

o Overengineering: Prefer the simplest solution that meets constraints; optimize

only when necessary.

o Ignoring users: Consider usability, accessibility, and failure modes (e.g.,

informative errors).

Algorithm

 Definition: An algorithm is a finite, precise, step-by-step procedure that transforms

inputs into outputs and solves a class of problems, not just one instance.

 Core properties:

o Finiteness: Always terminates; infinite loops indicate an incomplete or incorrect

design.

o Definiteness: Each step is unambiguous; different implementers should produce

identical behavior.
 o Input/Output: Explicitly defined domains and ranges; validates inputs and
describes outputs.

o Effectiveness: Steps are basic enough to perform mechanically; avoids “magic” or

undefined actions.

 Algorithm as a problem-solving strategy:

o Abstraction: Separates logic from code; you reason about “what” before “how.”

o Decomposition: Breaks complex tasks into smaller, testable subproblems (e.g.,

parse → validate → compute → report).

o Generalization: Designs for categories of inputs; avoids hard-coding a single case.

 Role and importance in the process:

o Bridge from idea to execution: Converts conceptual reasoning into an

operational specification ready for review and test.

o Enables analysis: You can prove correctness, estimate complexity, and compare
alternatives before coding.

o Supports collaboration: Pseudocode/flowcharts act as shared artifacts for

feedback and iteration.

o Facilitates reuse: Well-specified algorithms can be reimplemented across

languages and platforms.

 Evaluating algorithms:

o Correctness proofs: Invariants, pre/postconditions, and loop termination

arguments.

o Complexity analysis: Time/space growth (big-O), best/average/worst case;

consider input distributions.

o Trade-offs: Readability vs. performance, generality vs. specialization; choose

based on constraints and priorities.

 Typical mistakes and better practices:

o Ambiguous steps: Replace “process data” with explicit operations.

o Unspecified edge handling: Enumerate boundary and error cases; define

behavior.

o Premature optimization: Prototype the clear version; profile before tuning.

Program

 Definition: A program is a concrete implementation of an algorithm in a programming

language that runs on hardware or a virtual machine; it adds practical considerations like
data types, memory, and interfaces.

 Key elements:

o Data representation: Pick types and structures that reflect the algorithm’s
assumptions (e.g., integer vs. decimal for currency, guarding against precision
loss).

o Control flow: Implement decisions, loops, and function calls faithfully, preserving
algorithmic invariants.

o Interfaces: Define how data enters/leaves (CLI, files, APIs, UI), including
validation and feedback.

o Error handling: Anticipate invalid states, exceptions, and recoveries; log

meaningfully.

 From algorithm to program:

o Translation: Map each step to language constructs; ensure determinism and

termination remain intact.

o Validation: Create unit and integration tests from the problem’s examples and
edge cases.

o Optimization: Profile first; optimize hot paths without changing observable

behavior.

o Maintenance: Refactor for clarity, document decisions, and design for extension
(modularity).

 Why programs differ from algorithms:

o Environment constraints: Memory, CPU, OS, libraries, and deployment influence

design choices.

o State and side effects: Real systems persist data, interact with networks, and
handle concurrency.

o Non-functional requirements: Security, reliability, portability, and usability often

define success as much as correctness.

Putting it all together (a disciplined workflow)

  Problem definition:

o Goal: State the objective in testable terms (“Compute daily average temperature
per station”).

o Inputs/outputs: Specify formats, ranges, and validation rules; provide sample

cases.

o Constraints: Time/space limits, privacy, platform, and user experience

requirements; list edge scenarios to consider.

 Design the solution as an algorithm:

o Decompose: Identify subproblems; define clear responsibilities and data

contracts for each.

o Specify: Write pseudocode/flowcharts with unambiguous steps, explicit

conditions, and termination criteria.

o Analyze: Prove correctness with invariants; estimate complexity; compare

alternatives against constraints.

 Implement as a program:

o Translate: Choose suitable data structures and control flow; preserve algorithm
semantics.

o Test: Derive tests from the specification; include boundary and failure cases;
automate.

o Iterate: Optimize based on measurements; refactor for clarity; document

interfaces and assumptions.

Practical teaching tips

 Start with clear problem statements: Provide input formats, constraints, and exact
outputs; include two edge cases and one typical case.

 Use pseudocode and flowcharts first: Separate logic from syntax; have students
peer-review for ambiguity and missing cases.

 Require edge cases: Make students explain behavior for empty input, extremes, invalid
data; grade on explicit handling.

 Tie analysis to decisions: Ask for a short justification of algorithm choice (e.g., why linear
scan over binary search given unsorted input).
 Bridge to code thoughtfully: Emphasize type choices, naming, and test coverage; show
how small changes in data representation affect correctness and performance.

 Reflect on trade-offs: Have students note one optimization they skipped (and why) and
one they implemented (and its measured impact).