Module 5: Problem-Solving Strategies

Primary text: How to Solve It by Computer (Dromey), using Polya's four-phase framework as the backbone Selective support: Mathematics for Computer Science proof sections, Introduction to Probability story-proofs, and Linear Algebra and Its Applications worked examples only where they sharpen a heuristic

This guide is the primary teacher. You do not need to read a full problem-solving textbook to complete this module. You do need to develop operational fluency in Polya's four phases, a small set of high-leverage heuristics (working backwards, special cases, patterns, invariants, contradiction, construction, divide-and-conquer, dynamic programming), and the meta-cognitive habits that turn solved problems into transferable technique.

Scope of This Module

This module is not "read about problem solving." It is where you change the way you approach unfamiliar problems.

What it covers in depth:

Polya's four phases (understand, plan, execute, look back) as an executable protocol, not a poster
working backwards, special cases, and pattern recognition as search-space reducers
contradiction, invariants, and monovariants as tools for impossibility and termination
constructive reasoning that produces both a proof and an algorithm
divide-and-conquer and dynamic programming as problem-structure strategies, not just algorithm categories
debugging mathematical and algorithmic reasoning when a step or a plan fails
generalization, transfer, and research-level patience for problems that resist first attempts
translating informal prompts into formal specifications, reading other people's code as a problem-solving activity, and triaging under deadline pressure -- the bridge from textbook problems to real engineering work

What it deliberately does not try to finish here:

a full course in competition mathematics or contest training
cognitive-science treatment of expertise development
a complete catalogue of algorithm-design paradigms (those arrive in Semester 2)
philosophy of mathematics or formal proof theory

This is an in-depth strategy module. If you can compute answers on familiar problem types but stall on unfamiliar ones, you are not done.

Before You Start

Answer these closed-book before starting the main path:

Why is restating a problem in your own words different from re-reading the prompt?
What is the difference between a plan and a solution, and why does the plan come first?
Why is a solved small case often more useful than a half-written general proof?
What does "invariant" mean, and how does an invariant rule out a goal?
What is the difference between verifying the final answer and verifying the argument?

Diagnostic Interpretation

4-5 solid answers

You are ready for the full path. Focus on fluency and transfer.

2-3 solid answers

Continue, but plan to write explicit plan-and-verification blocks for every problem this module.

0-1 solid answers

Before starting, revisit Module 1 proof discipline and Module 2 counting models. Strategic thinking depends on structural reasoning habits that the earlier modules already trained.

What This Module Is For

Strategic problem solving is the habit of deciding how to attack a problem before you attack it, then extracting maximum value once the problem is solved.

Later CS work repeatedly asks questions like:

how do I attack a problem I have never seen before without thrashing?
how do I decide whether my plan is wrong, or my execution is wrong?
how do I generalize a specific solution into a reusable technique?
how do I debug a proof, an algorithm, or a system when the obvious thing fails?
how do I know when to switch strategies versus when to push harder?

This module builds the problem-solving discipline needed for:

algorithm design and analysis in Semester 2
debugging and verification in systems programming (Semester 4)
proof obligations and protocol reasoning in distributed systems (Semester 6)
architectural decision-making under constraints (Semester 7)
research-level engineering work where the right question is unclear

You are learning to reason about reasoning.

Concept Map

How To Use This Module

Work in order. The heuristics cluster assumes Polya discipline is stable; the structural reasoning cluster assumes you already know how to pick and adapt a heuristic; the meta-cognition cluster assumes you have enough solved problems to reflect on.

Cluster 1: Polya's Four-Phase Framework

Order	Concept	Type	Focus
1	Problem-Solving Begins with Understanding, Not Computing	PRIMARY	Turning an informal prompt into a precise specification with explicit assumptions
2	Devising a Plan Converts Random Attempts into Experiment	PRIMARY	Strategy selection, related-problem recall, and subgoal definition
3	Carrying Out the Plan Requires Per-Step Verification	SUPPORTING	Disciplined execution, margin justifications, and knowing when to re-plan
4	Looking Back Is Where the Compounding Happens	PRIMARY	Verification, alternative derivations, generalization, and transfer notes

Cluster mastery check: Can you run Polya's loop explicitly, in writing, on a fresh problem without prompting?

Cluster 2: Core Heuristics for Reducing Search

Order	Concept	Type	Focus
5	Working Backwards from the Goal Shrinks the Search	PRIMARY	Reverse reasoning, reversible steps, and forward write-up
6	Special Cases and Simplification Generate Reliable Data	PRIMARY	Controlled retreat, smallest-interesting-case selection, and lifting
7	Patterns and Analogies Port Solutions Across Domains	SUPPORTING	Structural abstraction versus surface similarity

Cluster mastery check: Can you name which heuristic a problem is inviting, in one sentence, before touching formulas?

Cluster 3: Structural Reasoning and Construction

Order	Concept	Type	Focus
8	Contradiction and Invariants Prove That Something Cannot Happen	PRIMARY	Non-constructive arguments, preserved quantities, and impossibility proofs
9	Construction Turns Existence Claims into Procedures	PRIMARY	Finiteness, definiteness, effectiveness, and the proof-as-algorithm habit
10	Divide-and-Conquer and Dynamic Programming as General Strategies	SUPPORTING	Structural decomposition, overlapping subproblems, and strategy selection

Cluster mastery check: Can you explain, for a specific problem, whether you are trying to build something or rule it out, and why?

Cluster 4: Meta-Cognition and Growth as a Solver

Order	Concept	Type	Focus
11	Debugging Mathematical and Algorithmic Reasoning Is Its Own Skill	PRIMARY	Bug taxonomy, isolation, minimal counterexamples, and rubber-ducking
12	Generalization, Transfer, and Research-Level Problems	PRIMARY	Multiplying the value of each solution through transfer notes and sustained exploration

Cluster mastery check: Can you describe a specific reasoning bug you have caught in your own work, and name the heuristic that caught it?

Cluster 5: Problem-Solving as the Bridge to Computing

Order	Concept	Type	Focus
13	Translating Informal Problems into Formal Specifications	PRIMARY	Turning under-specified product prompts into input/output types, invariants, tie-breaking rules, and failure modes
14	Reading Code as Problem-Solving: Decoding Intent from Implementation	PRIMARY	Boundary tracing, invariant recovery, hypothesis-test cycles, and the same skill applied to proofs
15	Problem-Solving Under Deadlines: Triage Under Partial Information	SUPPORTING	Information-per-minute ordering, reversibility analysis, and shipping defensible partial answers

Cluster mastery check: Given an ambiguous prompt, can you produce a formal spec, read an unfamiliar function that claims to solve it, and deliver a defensible partial result under a deadline?

Then work these practice pages:

Order	Practice path	Focus
1	Polya Framework Workshop	Running the four phases explicitly on problems from Modules 1-4
2	Heuristic Selection Lab	Classifying problems by heuristic and defending the choice
3	Structural Reasoning and Challenge Clinic	Invariants, construction, divide-and-conquer on contest-flavored problems
4	Code Katas	Implementation drills that exercise each strategy
5	Cluster 5: Bridge to Computing	Spec-writing, code-reading, and deadline-triage drills

Use Module Quiz after the concept and practice path. Use Book Exercise Lanes, Learning Resources, and Reference and Selective Reading only for targeted reinforcement.

Learning Objectives

By the end of this module you should be able to:

Run Polya's four phases explicitly and in writing on any unfamiliar mathematical or algorithmic problem.
Restate a problem in your own words with input/output types, constraints, and stated assumptions.
Write a one-paragraph plan that names the heuristic, a related problem, and a subgoal before executing.
Verify execution step-by-step with a margin justification and know when to re-plan rather than retry.
Extract at least one alternative derivation and one transfer note from every non-trivial solved problem.
Select among working-backwards, special cases, and analogy based on problem shape rather than random choice.
Use invariants and contradiction to rule out impossibilities cleanly.
Produce constructive proofs that double as algorithms with termination and correctness arguments.
Recognize divide-and-conquer or dynamic-programming structure when a problem has optimal substructure.
Debug reasoning systematically: isolate the failing step, build a minimal counterexample, decide plan-vs-execution-vs-model.
Translate an informal prompt into a formal specification that another engineer could implement without ambiguity.
Read unfamiliar code as problem solving: pin boundaries, recover invariants and termination measures, and form hypothesis-test cycles.
Triage under a deadline: order sub-problems by information-per-minute, separate reversible from irreversible decisions, and deliver a defensible partial writeup.

Outputs

a problem-solving portfolio with at least 20 problems worked using explicit Polya blocks
one plan-ledger file showing plans written before execution for at least 10 problems, with a post-hoc note on whether the plan was right
one heuristic-selection sheet where at least 15 problems are classified and the chosen heuristic is defended in writing
one invariant and contradiction notebook with at least 6 impossibility arguments
one construction notebook with at least 5 "proof-as-algorithm" solutions including termination arguments
one divide-and-conquer or DP reflection memo comparing at least 3 problems where the strategy fits and 2 where it does not
one mistake log naming at least 12 reasoning errors such as wrong problem statement, skipped verification, pattern after 2 examples, invariant not preserved, termination unstated, plan confused with execution bug
one transfer-notes file where at least 10 solved problems are paired with a short "this technique also applies to..." note
one short memo connecting Module 5 habits to upcoming algorithm design work in Semester 2

Completion Standard

You have completed Module 5 when all of these are true:

you can run Polya's four phases without reminders, in writing, on unfamiliar problems
you produce a written plan before executing, and you revise the plan (not just the execution) when a step fails
you verify steps individually and you catch your own errors before asking for help
you recognize when a problem invites contradiction, invariants, construction, divide-and-conquer, or dynamic programming
you leave transfer notes: a solved problem is not filed away until at least one related problem class is recorded
you can debug reasoning in yourself and explain what went wrong, not just patch the output

If you can compute answers on familiar problem types but still thrash on unfamiliar ones, the module is not complete.

Reading Policy

Concept pages are the main path.
The Dromey chunks in books/How To Solve It By Computers/contents/ are the selective reinforcement lane, not a second syllabus.
Read only if stuck means try the concept page, self-check, and drill first.
Optional deep dive means additional nuance or contest-flavored exercise volume, not required progression.
Because this is a habit-building module, written plans, ledgers, and transfer notes are required, not optional.

Suggested Weekly Flow

Day	Work
1	Concepts 1-2 and one Polya block on a Module 1 proof problem
2	Concepts 3-4 and one fully looked-back problem (four review questions in writing)
3	Concepts 5-6 and four problems attacked with special-cases and working-backwards
4	Concept 7 and one analogy-mapping sheet for three different problems
5	Concepts 8-9 and one invariant argument plus one constructive proof written as an algorithm
6	Concept 10 and one divide-and-conquer problem, one DP problem, with structural analysis
7	Concepts 11-12 and one reasoning-debug log with minimal counterexamples
8	Concepts 13-15 (bridge to computing), cluster 5 practice page, module quiz, and mistake-log cleanup

Reference

If you need exact links into the local chunked books, use Reference and Selective Reading.

Rich Learning Pages

Scope of This Module​

Before You Start​

Diagnostic Interpretation​

What This Module Is For​

Concept Map​

How To Use This Module​

Cluster 1: Polya's Four-Phase Framework​

Cluster 2: Core Heuristics for Reducing Search​

Cluster 3: Structural Reasoning and Construction​

Cluster 4: Meta-Cognition and Growth as a Solver​

Cluster 5: Problem-Solving as the Bridge to Computing​

Learning Objectives​

Outputs​

Completion Standard​

Reading Policy​

Suggested Weekly Flow​

Reference​

Rich Learning Pages​