10. Integrated Problem-Solving Practice

A Repeatable Problem-Solving Process

Programming becomes useful when separate ideas work together. A reliable solution follows a repeatable cycle instead of jumping directly into code.

1. Understand the requirements. Identify inputs, outputs, constraints, and unusual cases.

2. Represent the data. Select variables, data types, lists, mappings, or sets that fit the problem.

3. Design the algorithm. Write precise steps before implementing the full program.

4. Implement in small parts. Use functions to isolate responsibilities and make behavior easier to test.

5. Test normal and boundary cases. Consider empty input, one-item input, duplicates, extreme values, and invalid input when relevant.

6. Debug systematically. Reproduce the problem, trace the state, identify the faulty assumption, change one thing, and retest.

7. Evaluate the result. Check correctness, termination, readability, time complexity, and space complexity.

A useful design question is: “What must always be true at this point?” The answer can provide an invariant that helps explain why the algorithm works. During a search, for example, an invariant might state that every item outside the current search range has already been ruled out.

Takeaway: Define the problem, represent it carefully, build in small steps, test with evidence, and evaluate more than whether one example works.

Combining Data, Control Flow, and Functions

Small functions can combine parameters, return values, data types, expressions, conditionals, loops, and assertions.

A number classifier uses conditional branching to select exactly one result. If value > 0, it returns "positive"; if value < 0, it returns "negative"; otherwise, it returns "zero". The three corresponding tests are classify_number(8) == "positive", classify_number(-3) == "negative", and classify_number(0) == "zero".

An assertion states expected behavior. When an assertion fails, it identifies a case that needs investigation rather than proving that the entire program is wrong.

A list-processing function can combine a loop with an explicit empty-input decision. For an empty list of scores, it can return a count of 0, a total of 0, and no average. Otherwise, it can visit each score once, add the values to a running total, divide by the number of scores, and return the count, total, and average.

For $n$ scores, this traversal has running time $O(n)$ and uses $O(1)$ additional space when the input list is not counted. If the function also finds a maximum, it should initialize the current best value from the first element rather than assuming that zero is appropriate; otherwise, an all-negative list can produce a wrong result.

Takeaway: Every function should have a clear contract: what it accepts, what it returns, and what it does for empty or unusual inputs.

Boolean Logic and Data Representation

Boolean logic and explicit boundaries determine whether conditions classify data correctly.

A password validator can separate the question “does the text contain a digit?” from the question “is it long enough?” The first check scans each character and returns true when a digit is found. The second checks whether the length is at least eight. The password is valid only when both checks succeed.

The Boolean operator and requires both conditions to be true. Useful tests include a valid password such as "abc12345", a long password with no digit such as "abcdefghi", and a short password with a digit such as "a1". Short-circuit evaluation can avoid unnecessary work, but clarity should remain the priority.

Classification also depends on the order of branches and the exact boundary rules. For temperature categories, one possible set of rules is:

• Values below $32$ are below freezing.

• Values from $32$ through $80$, inclusive, are comfortable.

• Values above $80$ are hot.

The second branch is considered only when the first condition is false. With these rules, $32$ is comfortable and $80$ is also comfortable. Stating boundaries explicitly prevents overlapping or missing categories.

A frequency table uses a mapping from each item to its count. As the loop processes an item, it creates an initial count when necessary and then increases that count. For an empty list, the natural result is an empty mapping because no item has occurred.

Takeaway: Make Boolean requirements explicit, define category boundaries, and choose a data representation that matches the information being stored.

Debugging by Tracing Evidence

Debugging means reasoning from observed behavior back to the program's assumptions. Begin with an input that demonstrates the defect, then trace variables and control flow step by step.

An incorrect average might use the last value as the denominator. The denominator should instead be the number of values, represented by len(values), because an average divides the total by the count of values. An empty-list check also prevents division by zero and makes the behavior explicit.

An infinite loop can result when its controlling variable never changes. For example, a search for the first even value may begin with index = 0 and continue while index < len(values). If the first value is odd and the index is never increased, the same value is tested forever. The corrected loop increases index after the nonmatching case. Every loop needs a progress argument: some state must move toward termination.

An indexing defect can create an off-by-one error. A loop using range(1, 3) visits indexes 1 and 2, not the first three indexes 0, 1, and 2. Writing the index sequence beside the corresponding list values often makes the error visible. A concise corrected operation is the slice values[:3].

Takeaway: Reproduce the defect, inspect the state, identify the violated assumption, make one targeted change, and retest normal and boundary cases.

Searching with Preconditions and Invariants

Search algorithms illustrate how preconditions, invariants, and complexity work together.

A linear search examines items from left to right until it finds the target or reaches the end. It works whether the data is sorted or unsorted. In the worst case, it examines every element, so its time complexity is $O(n)$.

Binary search requires the values to be sorted according to the same ordering used by the comparisons. It checks the middle item and discards the half that cannot contain the target. Its key invariant is that, if the target occurs, it is within the inclusive range from low to high.

Each binary-search iteration removes about half of the remaining candidates, giving worst-case time complexity $O(\log n)$. The empty-list case works because high begins below low, so the loop is skipped and -1 is returned.

Useful binary-search tests include a target at the first position, a target in the middle, a target at the last position, an absent target, and an empty list. Binary search should not be applied to arbitrary unsorted data because discarding half of the range depends on the ordering.

For a repeated-value requirement, the algorithm must continue after finding a match. It can store the matching index in answer and then continue searching the left half by moving high leftward. The result is the first matching index, and the running time remains $O(\log n)$ with $O(1)$ additional space.

Takeaway: Use linear search for general data, binary search only when its sorted-data precondition holds, and adapt the invariant when the task asks for a special occurrence such as the first match.

Evaluating Correctness, Termination, and Efficiency

Efficiency describes how resource use changes as the input grows. Correctness, efficiency, termination, and decidability are related but answer different questions.

• Correctness: Does the algorithm produce the required answer?

• Efficiency: How much time and additional memory does it use?

• Termination: Does it eventually stop for the input?

• Decidability: Does an algorithm exist that halts on every valid input and correctly answers the yes-or-no question?

Typical time-complexity patterns are:

• $O(1)$: fixed work, such as accessing a known position.

• $O(\log n)$: repeatedly halving the problem, as in binary search.

• $O(n)$: one traversal of the input, as in linear search.

• $O(n^2)$: comparing many pairs, as in nested-loop duplicate detection.

A duplicate check using nested loops may compare approximately $n^2/2$ pairs and has worst-case time $O(n^2)$. A set can remember values already seen; this generally reduces expected running time to $O(n)$, but it uses additional memory. This is a space-time trade-off.

Complexity analysis should support measurement, not replace it. First establish correctness, then identify the dominant repeated operation and estimate how often it occurs.

To evaluate an algorithm, ask:

1. Does it handle ordinary and boundary cases?

2. Does every loop make measurable progress?

3. Is the result guaranteed for every permitted input?

4. Is the time and memory use acceptable as the input grows?

5. Are the code and assumptions clear enough to maintain?

Final takeaway: A strong integrated solution is correct, terminates, handles its stated inputs, communicates its reasoning through invariants and tests, and uses resources appropriately.