2 Algorithms and Solution Design

From Problem to Algorithm

An algorithm is a finite, ordered set of precise steps that transforms input into the required output. Algorithmic problem solving begins before programming: first determine exactly what problem must be solved, then design and test a solution. Computational thinking supports this process through decomposition, abstraction, pattern recognition, and algorithm design.

A useful workflow is:

1. Understand and restate the problem.

2. Identify the inputs and required outputs.

3. Identify rules, assumptions, and constraints.

4. Break the problem into manageable parts.

5. Design a step-by-step solution.

6. Represent the solution with pseudocode or a flowchart.

7. Test the solution with normal, boundary, and invalid data.

8. Improve the solution if it is incorrect, unclear, or inefficient.

A computer cannot reliably solve a vague problem. The problem definition must be precise enough that two people would interpret it in the same way.

Takeaway: Clarify the problem before deciding how to code it.

Analyzing the Problem

Restating a task in your own words removes unnecessary details and reveals the central decision or calculation. For example, a store problem can be restated as follows: given a purchase amount, reduce it by $10\%$ when $\text{purchaseAmount} \ge 100$, and otherwise leave it unchanged.

Decomposition divides the task into smaller subproblems. The discount example can be divided into these parts:

1. Read the purchase amount.

2. Determine whether the amount qualifies for the discount.

3. Calculate the discount when applicable.

4. Calculate the final price.

5. Display the result.

Each part should have a clear purpose and be simple enough to describe or test independently.

An assumption is a condition accepted as true when the problem does not specify otherwise. Relevant assumptions might include that the purchase amount is nonnegative, that the discount is applied before tax, and that monetary results are rounded to two decimal places. Stating assumptions prevents different implementations from making incompatible decisions.

Abstraction focuses attention on the important features of a problem while leaving out unnecessary detail. Pattern recognition can reveal that a new task resembles a previously solved task, allowing a known strategy to be adapted carefully.

Takeaway: Restatement, decomposition, abstraction, pattern recognition, and explicit assumptions turn a broad task into a precise set of responsibilities.

Inputs, Outputs, and Constraints

A precise specification separates the information supplied to the algorithm from the result it must produce. For the discount example, the input is a nonnegative purchase amount represented as a decimal or real number, and the output is the final price after any eligible discount.

When $\text{purchaseAmount} \ge 100$, calculate:

Otherwise, calculate:

A constraint is a limit or rule that the solution must obey. Examples include a score restricted to the range from $0$ to $100$, a date required to use the format YYYY-MM-DD, a memory limit, a response-time limit, or a business rule such as a discount threshold.

Validation checks whether supplied data satisfies the constraints. For example, a purchase amount below $0$ is invalid and should be rejected or requested again. Validation is different from processing: validation determines whether data is acceptable, while processing calculates a result for valid data.

Constraints may describe data ranges, formats, resources, time, business rules, technology, safety, or privacy. They affect design choices; for example, a method suitable for a small list may not be suitable for millions of records.

Takeaway: Specify inputs, outputs, processing rules, data types, and constraints before designing the steps.

Designing the Solution

A well-designed algorithm produces the required output for every valid input. It should be correct, unambiguous, finite, ordered, general, efficient, and testable. Efficiency considers the time and memory used as the amount of input grows.

Most introductory solutions combine three control structures:

• Sequence: instructions execute in a logical order.

• Selection: a condition determines which instructions execute.

• Iteration: instructions repeat while or until a condition is satisfied.

For example, a solution can use sequence to read a value and calculate a result, selection to choose whether a discount applies, and iteration to request another value while the current value is invalid.

These structures are complementary. Sequence establishes order, selection handles alternatives, and iteration handles repetition. Combining them allows one algorithm to validate data, make decisions, perform calculations, and produce output.

A solution should also terminate appropriately. An iteration condition must eventually become false for valid inputs, unless continued repetition is an intentional part of the design.

Takeaway: Check not only what an algorithm calculates, but also whether its control flow is ordered, finite, and appropriate for all valid inputs.

Representing Algorithms

Pseudocode expresses algorithmic logic without committing to a particular programming language. Use one instruction per line, meaningful names, precise conditions, and indentation inside decisions and loops. Make the beginning, end, inputs, outputs, and repeated sections clear.

A discount solution can be described in this order:

1. Start and read the purchase amount.

2. While the amount is less than $0$, display an error and request another amount.

3. If the amount is at least $100$, calculate the final price by multiplying it by $0.90$.

4. Otherwise, keep the original amount as the final price.

5. Display the final price rounded to two decimal places.

6. End.

A flowchart presents the same logic visually. Use an oval or rounded rectangle for the start and end, a parallelogram for input or output, a rectangle for a process or calculation, and a diamond for a decision. Connect symbols with arrows and label decision branches, usually with “Yes” and “No.”

Pseudocode is often quicker to edit, while a flowchart can make paths, decisions, and loops easier to see. Both representations should express the same underlying logic.

When designing a flowchart, begin with one clearly labeled start symbol, connect symbols with arrows, place one action or calculation in each process box, put a question rather than an action in a decision diamond, label every branch, and ensure that every possible path reaches an appropriate outcome.

Takeaway: Choose a representation that makes the algorithm’s steps and control flow easy to inspect.

Dry Runs and Testing

A dry run traces an algorithm manually with sample data. Suppose the purchase amount is $120$. The validation succeeds, the condition $120 \ge 100$ is true, and the calculation is:

The expected displayed result is $108.00. Testing a second value such as $80$ checks the other branch and should produce $80.00.

A useful test set includes:

• Typical cases: ordinary valid inputs.

• Boundary cases: values at or near a limit, such as $99.99$, $100$, and $100.01$.

• Invalid cases: values that violate a constraint, such as $-5$.

• Special cases: zero, an empty collection, or the largest permitted value.

For the discount rule, expected outcomes include:

• $80$ produces $80.00.

• $100$ produces $90.00.

• $150$ produces $135.00.

• $0$ produces $0.00.

• $-5$ produces an error and requires re-entry.

A logic error occurs when an algorithm runs but produces the wrong result. A syntax error occurs when program code violates the rules of its language. Dry-running pseudocode helps find logic errors before implementation, while systematic testing checks whether the completed solution behaves as expected. Testing compares actual results with expected results and should guide improvements when discrepancies appear.

Takeaway: Test both sides of every decision and include values at, near, and outside important limits.

• boundary case