Algorithmic Thinking Intermediate

Decomposition means breaking a large, complex problem into smaller, more manageable sub-problems. Each sub-problem is easier to solve individually, and the solutions combine to solve the whole.

Problem: build an online shop
  → Decompose into:
      1. Display products
      2. Handle user login
      3. Manage a shopping cart
      4. Process payment
      5. Send confirmation email

Decomposition is one of the four pillars of computational thinking (alongside pattern recognition, abstraction, and algorithm design). It makes large projects tractable and allows different people or teams to work on sub-problems in parallel.

Pattern recognition is the ability to notice similarities, regularities, or trends within and between problems. By identifying a pattern, you can apply a known solution instead of solving from scratch.

• Sorting a list of names uses the same idea as sorting a list of numbers.
• Checking whether a word is a palindrome uses the same left/right comparison idea as checking whether a list is symmetric.

Patterns also appear in data: repeated structures in a sequence often suggest a loop-based approach. Recognising these patterns is what allows experienced problem-solvers to tackle new problems quickly by analogy.

Abstraction means focusing on the important details of a problem and hiding unnecessary complexity. A good abstraction lets you reason about a problem at a higher level without getting lost in low-level specifics.

• A map is an abstraction of the real world — it shows roads but not every blade of grass.
• A function name like sortList() abstracts the sorting logic so callers don't need to know how it works, only what it does.

Choosing the right level of abstraction is a key design skill. Too little abstraction leads to unmanageable complexity; too much loses important detail.

Iteration repeats a block of steps using a loop. Recursion solves a problem by having a process call itself on a smaller version of the same problem.

Iteration — count down from 5:
  SET n TO 5
  REPEAT WHILE n > 0
      PRINT n
      SET n TO n - 1
  END REPEAT

Recursion — count down from 5 (conceptually):
  PROCEDURE countDown(n):
      IF n = 0 THEN STOP
      PRINT n
      countDown(n - 1)

Both approaches can solve the same problems. Iteration is usually easier to trace manually; recursion can express certain problems (like tree traversal) more naturally. Every recursive solution needs a base case to stop — without one it loops forever.

Not all correct algorithms are equally good. Efficiency measures how many steps an algorithm takes relative to the size of its input. Fewer steps generally means faster execution, especially for large inputs.

Counting steps — finding the maximum in a list of n items:
  Look at item 1, remember it as "current max"     (1 step)
  REPEAT for each remaining item:                  (n-1 steps)
      If item > current max, update current max
  PRINT current max                                (1 step)

Total steps ≈ n  (grows linearly with input size)

Developing the habit of counting steps — even roughly — builds the intuition needed to compare algorithms and spot ones that will slow down unacceptably for large inputs.

Searching means finding whether a target value exists in a collection, and if so where. Two common strategies have very different efficiency profiles.

• Linear search: check each item one by one from the start. Works on any list. In the worst case, checks all n items.
• Binary search: only works on a sorted list. Compare the target to the middle item; if it's smaller, discard the upper half; if larger, discard the lower half. Repeat. Each step halves the remaining items.

Binary search on a sorted list of 16 items:
  Round 1: 16 items → check middle → 8 remain
  Round 2: 8 items  → check middle → 4 remain
  Round 3: 4 items  → check middle → 2 remain
  Round 4: 2 items  → check middle → found or not
  At most 4 comparisons for 16 items (log₂16 = 4)

Binary search is dramatically faster for large sorted lists; linear search is simpler and works unsorted.

Sorting means arranging items in a defined order (e.g., smallest to largest, or alphabetical). It is one of the most studied problems in computer science because sorted data enables faster searching and cleaner output.

Bubble sort idea — repeatedly compare adjacent pairs and swap if out of order:
  Pass 1: [5, 3, 8, 1] → compare 5&3 → swap → [3, 5, 8, 1]
                        → compare 5&8 → ok
                        → compare 8&1 → swap → [3, 5, 1, 8]
  Pass 2: [3, 5, 1, 8] → ...
  Continue until no swaps needed → sorted

Different sorting strategies make different trade-offs between simplicity and speed. Understanding the idea behind sorting prepares you to evaluate and choose algorithms for real tasks.

Edge cases are inputs at the boundary of what an algorithm must handle — empty lists, single items, all-identical values, the maximum allowed number. A correct algorithm must work for all valid inputs, not just typical ones.

Tracing means manually following every step of an algorithm for a specific input, recording the value of each variable at each step. This is the most reliable way to verify correctness and find bugs.

Trace — find the sum of [2, 7, 3]:
  SET total TO 0
  Step 1: total = 0 + 2 = 2
  Step 2: total = 2 + 7 = 9
  Step 3: total = 9 + 3 = 12
  PRINT 12   ✓

Always trace with at least one ordinary case, one edge case (empty list), and one boundary case (single item) before declaring an algorithm correct.