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

Use the prerequisite diagnostic to check tracing, quantifiers, finite sets, and basic arithmetic. Strategy fluency is an outcome of this module, not an entry requirement. Repair only the prerequisite that blocks you.

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:

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

---

Outputs

Keep one evidence notebook with P01–P20 from the five practice pages, four lab reports, A01–A10 assessment attempts, and the bounded project in the capstone thread. The same artifact may satisfy several competencies: use links instead of rewriting it. Preserve genuine failed or uncertain attempts; do not invent a quota of mistakes. Record assistance.

Completion Standard

Meet every C01–C10 gate in the assessment map, reproduce the labs, defend the project, and complete a changed-case recheck after 7–14 days. No average score compensates for a missing specification, invalid proof, unsupported impossibility claim, or fabricated evidence. Authored material and executable checks do not establish independently reviewed teaching quality or any percentile rank. See review status.

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 Workload and Sequence

Plan 65–95 focused hours, an author estimate awaiting learner pilots.

Phase	Hours	Exit evidence
Diagnostic, 15 lessons and selective reading	20–28	Assumptions, worked traces and retrieval notes
P01–P20 across five practice lanes	14–20	Independent attempts and checked repairs
Four runnable labs	12–18	Code, oracle comparisons and explanations
Assessment, repair and delayed recheck	7–11	Every competency demonstrated
Bounded project and defense	12–18	Contract, evidence and changed-case handoff

Proceed through clusters 1–5, interleaving their practice lanes. At ten hours per week, allow roughly 7–10 study weeks, plus any unabsorbed retention delay. Prerequisite repair and optional enrichment add time. The eight-day schedule is retired; do not compress this module to match a roadmap coordinate.

Reference

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

---

Rich Learning Pages

Worked Examples | Guided Labs | Case Studies | Mistake Clinic | Reading Guide | Capstone Thread