Problem Solving, Abstraction and Algorithm Correctness

1. Understanding the Problem

Programming begins with a precise problem rather than a preferred data structure or piece of code. State:

• the inputs and their representation;
• the required outputs;
• constraints on size and values;
• assumptions and invalid cases;
• correctness requirements;
• resource limits;
• examples that expose boundaries.

“Find a customer” is incomplete. Does the input contain a unique identifier or a name? Should all partial matches be returned? Can the dataset be empty? Is case significant? The algorithm cannot be judged until the required relationship between input and output is known.

2. From Situation to Computational Problem

A real situation contains details that may not affect computation. Abstraction keeps facts relevant to the requested decision and removes incidental detail.

For route planning, intersections and roads may become vertices and weighted edges. Building color may be irrelevant, while one-way direction, distance, closure and travel time matter.

A model is useful when it preserves every property needed to answer the question. An oversimplified model can produce a fast algorithm for the wrong problem.

3. Identifying Inputs and Outputs

Define input domains precisely:

Input: an array a of n integers, where n >= 1
Output: the greatest value occurring in a

This contract states that empty input is outside the algorithm's accepted domain. Another interface may return an optional result or throw an exception for an empty sequence.

Output may include more than a value. A path algorithm may need the path and total cost. A search may return an index or a distinguished not-found result. Ambiguity at the output boundary spreads through implementation and tests.

4. Constraints Shape Solutions

Input size and value limits determine feasible approaches. Comparing every pair may be acceptable for n = 100 but impossible for n = 10 million. A value range of 0 through 100 may permit counting, while arbitrary objects require comparison or hashing.

Other constraints include:

• available memory;
• whether input is already sorted;
• whether updates occur;
• required response time;
• stability or ordering requirements;
• streaming versus random access;
• concurrency and persistence.

Do not choose an algorithm from n alone. Data distribution and operations over the structure also matter.

5. Algorithms

An algorithm is a finite, unambiguous, effective procedure that solves a specified class of problems.

It needs:

• defined inputs;
• defined outputs;
• steps that can be carried out;
• termination for every accepted input;
• correctness with respect to its specification.

Source code is one implementation of an algorithm. The same binary-search algorithm can be expressed in Java, pseudocode or mathematics. Conversely, a source file may contain no correct terminating algorithm.

6. Pseudocode

Pseudocode communicates logical steps without language syntax:

maximum(a):
    require length(a) > 0
    best = a[0]
    for i from 1 to length(a) - 1:
        if a[i] > best:
            best = a[i]
    return best

Good pseudocode states meaningful operations, decisions and data access. It should be detailed enough to analyze but not filled with language-specific declarations that obscure the idea.

7. Decomposition

Decomposition divides a complex problem into responsibilities with clear contracts. A text-analysis system might separate input decoding, tokenization, normalization, frequency counting and result formatting.

Each component should have:

• a single clear purpose;
• defined inputs and outputs;
• stated preconditions;
• hidden implementation details;
• tests independent of unrelated components.

Decomposition reduces the amount of reasoning needed at once. It also exposes repeated subproblems that can become reusable operations.

8. Data Structures

A data structure organizes values and relationships so operations can be performed effectively.

Linear structures include arrays, linked lists, stacks and queues. Nonlinear structures include trees, heaps and graphs. Hash tables organize access through computed bucket locations.

The same abstract behavior can have several representations. A queue can use a circular array or linked nodes. The correct representation follows required capacity, access, memory and performance guarantees.

9. Abstract Data Types

An abstract data type or ADT, defines a set of values and permitted operations independently of representation.

A stack ADT includes:

• push an element;
• pop the most recently pushed remaining element;
• inspect the top;
• test emptiness;
• possibly report size.

Its last-in, first-out behavior is part of the abstraction. Whether it uses an array, linked list or library collection is an implementation choice.

10. Interfaces and Representations

An ADT interface states what clients can do. Its representation invariant states what must be true internally.

For an array stack:

0 <= size <= elements.length
valid stack elements occupy elements[0 .. size-1]

For a linked stack:

size equals the number of nodes reachable from top
the final node points to null
no reachable-node cycle exists

Both can meet the same public stack contract while requiring different internal proofs.

11. Encapsulation

Encapsulation hides representation behind operations. Clients call push rather than changing an internal array and size counter separately.

This protects invariants and allows implementation changes without rewriting clients. Exposing a mutable internal array would let a caller corrupt element order or place data outside the logical size.

Encapsulation does not mean hiding the behavioral contract. Clients need clear error, ordering, mutation and complexity expectations.

12. Preconditions

A precondition must hold before an operation is called. Binary search requires a sequence sorted by a compatible ordering. The maximum algorithm above requires nonempty input.

An interface can:

• document the precondition and assign responsibility to the caller;
• validate and reject invalid input;
• redesign the return type to represent absence.

The correct choice depends on the API boundary and cost. Internal low-level operations may rely on established invariants, while public input boundaries should usually validate.

13. Postconditions

A postcondition describes what must hold after successful completion. For stack push(x):

size increases by one
top returns x
earlier elements retain their relative order

For sorting:

output contains the same multiset of elements as input
output is ordered by the comparator

The permutation requirement is essential. Returning an empty array is sorted but is not a correct sort of a nonempty input.

14. Correctness

Partial correctness means that if the algorithm terminates, its result satisfies the postcondition. Total correctness adds proof that it terminates for every input meeting the precondition.

Testing finds defects but cannot usually prove correctness for an unbounded input domain. A proof uses the algorithm's structure and specification to cover all accepted cases.

A correct algorithm under one precondition can be incorrect for a broader one. Binary search is correct on sorted arrays and not generally correct on unsorted arrays.

15. Loop Invariants

A loop invariant is a property that holds at a chosen point before and after every iteration.

For the maximum algorithm:

before iteration i, best is the maximum of a[0 .. i-1]

This invariant connects the initialization, loop work and final result.

A useful invariant is precise enough that, together with loop termination, it implies the postcondition. “The algorithm is working correctly” is not an actionable invariant.

16. Initialization

Before the first iteration, i = 1 and best = a[0]. The processed prefix a[0 .. 0] contains one element and best is its maximum. Therefore the invariant holds initially.

Initializing best to zero would fail for an all-negative array:

[-8, -3, -10]

Zero is not an input element and incorrectly exceeds every value. Initialization should come from a valid element or use a correctly defined identity and empty-input policy.

17. Preservation

Assume before iteration i that best is the maximum of a[0 .. i-1].

If a[i] is greater, assigning best = a[i] makes it the maximum of a[0 .. i]. Otherwise the previous best is at least a[i] and remains the maximum of the enlarged prefix.

After either branch, the invariant holds for the next iteration. This reasoning covers every possible comparison outcome.

18. Termination and Postcondition

The loop advances i by one and stops when i = n. At termination, the processed prefix is a[0 .. n-1], the entire array.

By the invariant, best is then the maximum of the whole array, which is exactly the postcondition.

Termination is supported by a variant: n - i is a nonnegative integer that strictly decreases each iteration and cannot decrease forever.

19. Recursive Correctness

Recursive reasoning requires:

• base cases that solve smallest inputs;
• recursive calls on smaller or progressing instances;
• proof that combining recursive results solves the larger instance;
• a well-founded measure that guarantees termination.

For factorial, n decreases toward zero. For binary-tree traversal, each call processes a proper subtree.

Calling recursively on the same-size input without state progress may never terminate even when a base case exists somewhere in the code.

20. Counterexamples

To disprove a proposed algorithm, find one accepted input for which it fails or does not terminate.

Useful counterexample categories include:

• empty or single-element input;
• all equal values;
• already sorted or reverse-sorted data;
• all-negative values;
• duplicates;
• minimum and maximum representable values;
• missing target;
• cycles or disconnected components;
• overflow-producing arithmetic.

A small counterexample is valuable because it reveals the incorrect assumption directly.

21. Testing Strategy

Example-based tests cover representative and boundary scenarios. Property-based tests generate many inputs and verify general properties.

For sorting, useful properties are:

• output is ordered;
• output has the same length;
• every value occurs the same number of times;
• sorting again leaves the same result.

For a stack, compare operations against a trusted model. For graph algorithms, verify path edges and total cost rather than only one expected printed sequence.

22. Trace Tables

A trace table records important state across steps:

i	a[i]	best before	best after
1	-3	-8	-3
2	-10	-3	-3

Tracing helps reveal off-by-one errors, missed updates and invalid initialization. It supports understanding but is evidence for selected inputs, not a proof for all inputs.

23. Choosing a Data Structure

List required operations and their frequency:

• indexed access;
• insertion at an end or middle;
• smallest-element removal;
• membership testing;
• ordered traversal;
• relationship traversal.

Then choose a structure whose guarantees match those operations. A heap supports repeated priority removal but not fast arbitrary search. A hash table supports average membership but not sorted traversal.

Correctness comes first; complexity and engineering constraints then distinguish correct choices.

24. A Disciplined Problem-Solving Process

1. Restate the problem with inputs, outputs and constraints.
2. Work through small examples manually.
3. Identify the mathematical or structural property that drives a solution.
4. Choose abstractions and representations.
5. Write a clear algorithm.
6. state preconditions, invariants and postconditions.
7. prove partial correctness and termination.
8. analyze time and space.
9. implement with protected invariants.
10. test boundaries and counterexamples.

Optimization before correctness produces a faster wrong answer. A trustworthy solution connects every implementation step to a specified property and has evidence for both correct results and termination.