Problem Solving Methodology

Confronting an unseen algorithmic challenge without a systematic process leads to trial-and-error debugging and brittle solutions. A structured engineering methodology decomposes ambiguity into concrete constraints, establishes a verified brute-force baseline, and applies targeted optimizations before writing production code.

By the end of this chapter, you will be able to:

• Apply the 6-Step Problem-Solving Pipeline to systematically decompose unseen algorithmic problems.
• Use the B.U.D. (Bottlenecks, Unnecessary work, Duplicated work) optimization framework to reduce asymptotic complexity.
• Author standardized line-numbered algorithmic pseudocode adhering to universal mathematical conventions.
• Map algorithm control flow to standardized ISO flowchart symbols.
• Validate algorithm logic using dry-run execution tables prior to language-specific coding.

Professional software engineers follow an intentional 6-step pipeline when solving computational problems:

Input scale immediately dictates the target algorithmic complexity under a standard 1-second CPU budget ($\approx 10^8$ operations):

• $n\le 10$: $O(n!)$ or $O(2^n)$ backtracking / permutations
• $n\le 25$: $O(2^n)$ bitmask dynamic programming or meet-in-the-middle
• $n\le 500$: $O(n^3)$ cubic algorithms (Floyd-Warshall, matrix operations)
• $n\le 5,000$: $O(n^2)$ quadratic algorithms (nested loops, dynamic programming)
• $n\le 10^5$: $O(n\log n)$ or $O(n)$ (sorting, divide and conquer, two pointers)
• $n\ge 10^9$: $O(\log n)$ binary search or $O(1)$ closed-form mathematical formula

When optimizing a working brute-force solution, systematically inspect the logic for three performance killers:

1. B — Bottlenecks: Identify which single phase dominates the total runtime.
   • Example: In an algorithm that sorts an array in $O(n\log n)$ and then performs an $O(n^2)$ verification loop, the nested loop is the bottleneck. Optimizing the sorting phase yields zero asymptotic gain until the bottleneck is eliminated.
2. U — Unnecessary Work: Avoid executing steps whose results are never consumed or could be bypassed.
   • Example: Finding the $k$ smallest elements by fully sorting an entire array ($O(n\log n)$) when maintaining a size-$k$ heap requires only $O(n\log k)$.
3. D — Duplicated Work: Eliminate recalculating identical state or subproblems.
   • Example: Repeatedly summing array ranges $A[i\dots j]$ in $O(n)$ time rather than precomputing a prefix sum array in $O(n)$ space for $O(1)$ queries.

Pseudocode provides a language-agnostic blueprint that highlights mathematical invariants while omitting memory-management boilerplate.

• Line Numbers: Every statement is numbered to facilitate dry-run references.
• Assignment: Left-arrow ← denotes assignment; = is reserved for mathematical equality.
• Comparisons: Relational operators <, ≤, >, ≥, and inequality ≠.
• Logic: Bold lowercase English words: and, or, not.
• Scoping: 4-space indentation defines nested execution blocks without braces.
• Returns: Explicit return <value> designates subroutine exit points.

ALGORITHM LinearSearch(A, target)
    Input: Array A of length n, value target
    Output: Index of target in A, or -1 if not found

1.  for i ← 0 to length(A) - 1:
2.      if A[i] = target:
3.          return i
4.  return -1

A flowchart diagrams the sequential flow of control, branching conditions, and state transitions using standardized ISO geometric shapes:

To inspect live step-by-step pointer progression, explore our interactive Linear Search Visualizer.

Tracing LinearSearch(A, 30) on input $A=[10,20,30,40]$:

• Early Exit: The search terminates in 3 iterations rather than completing the full scan of length 4.
• Worst-Case Invariant: If target is absent or at index $n-1$, exactly $n$ comparisons are performed ($O(n)$).

• Constraint Discipline: Extract input constraints first to immediately determine your target complexity class before drafting algorithms.
• The B.U.D. Filter: Accelerate brute force by systematically identifying and eliminating bottlenecks, unnecessary work, and duplicated calculations.
• Traceability: Pair pseudocode with variable trace tables to catch edge cases (such as off-by-one errors and null references) before implementation.

1. Pólya, G. (1945). How to Solve It: A New Aspect of Mathematical Method. Princeton University Press.
2. Cormen, T. H., Leiserson, C. E., Rivest, R. L., & Stein, C. (2022). Introduction to Algorithms (4th ed.), Chapter 2: Getting Started. MIT Press.
3. McDowell, G. L. (2015). Cracking the Coding Interview (6th ed.), Chapter 6: Big-O. CareerCup.