Becoming a Better
Problem Solver:
A CS Perspective
Zhang Zhiyong Melvin
[Link]
School of Computing,
National University of Singapore
May 27, 2009
Becoming a Better Problem Solver:
A CS Perspective
Outline
What is problem solving?
Strategies and tactics
Getting started (Strategies)
Making progress (Tactics)
Summary
Pólya’s Mouse
Pólya’s Mouse
A good problem solver
doesn’t give up easily, but
don’t keep banging your
head on the same part of
the wall.
The key is to vary each
attempt.
References
References
What is problem solving?
Problem solving is the process of tackling
problems in a systematic and rational way.
Steps in problem solving
Understanding
the problem
Looking back Devising a plan
Carrying out
the plan
Outline
What is problem solving?
Strategies and tactics
Getting started (Strategies)
Making progress (Tactics)
Summary
Strategies, tactics and tools
Strategies
General approaches and psychological hints for
starting and pursuing problems.
Tactics
Diverse methods that work in many different
settings.
Tools
Narrowly focused techniques and ”tricks” for
specific situations.
Outline
What is problem solving?
Strategies and tactics
Getting started (Strategies)
Making progress (Tactics)
Summary
Strategy 1. Get your hands dirty
Example: Generating Gray codes
Named after Frank Gray, a researcher from Bell
Labs. Refers to a special type of binary code in
which adjacent codes different at only one position.
3-bit binary code
000
001
010
011
100
101
110
111
Example: Generating Gray codes
1-bit 2-bit 3-bit
0 00 000
1 01 001
11 011
10 010
110
111
101
100
Applications of Gray codes
Figure: Rotary encoder for angle-measuring devices
I Used in position encoder (see figure).
I Labelling the axis of Karnaugh maps.
I Designing error correcting codes.
Strategy 2. Restate the problem
The problem as it is stated may not have an obvious
solution. Try to restate the problem in a different
way.
Find the Inverse
Original Given a set of object, find an object
satisfying some property P.
Inverse Find all of the objects which does NOT
satisfy P.
Example: Invitation
You want to invite the
largest group of friends,
so that each person know
at least k others at the
party.
Invitation
Direct approach
1. For each subset of friends, check if everyone
knows at least k others.
2. Return the largest set of friends.
Looking back
Works but there are potentially 2n subsets to check,
where n is the number of friends.
Invitation
Find the Inverse
Instead of finding the largest group to invite, find
the smallest group that is left out.
Observation
A person with less than k friends must be left out.
Strategy 3. Wishful thinking
Make the problem simpler by removing the source
of difficulty!
1. Identify what makes the problem difficult.
2. Remove or reduce the difficulty.
Example: Largest rectangle
Find the largest white rectangle in an n × n grid.
There is an easy solution which checks all
rectangles. There are n2 × n2 ≈ n4 rectangles.
Example: Largest rectangle
2D seems to be difficult, how about 1D?
There are n2 segments in a row, but we can find
the longest white segment using a single scan of the
row. What is that so?
Example: Next Gray code
Given an n-bit Gray code, find the next code.
3-bit Gray code
000
001
011
010
110
111
101
100
Example: Next Gray code
Gray code is tough! What if we worked in binary?
Gray code Binary code
111 101
101 110
Outline
What is problem solving?
Strategies and tactics
Getting started (Strategies)
Making progress (Tactics)
Summary
Making progress
Record your progress
Any form of progress is good, record your workings
and keep track of interesting ideas/observations.
Sometimes, you might
have to sleep on it.
Story of RSA
Figure: Left to right: Adi Shamir, Ron Rivest, Len Adleman
Tactic 1. Extremal principle
Given a choice, it is useful to consider items which
are extreme.
I Tallest/shortest
I Leftmost/rightmost
I Largest/smallest
Example: Activity selection
Each bar represents an activity with a particular
start and end time. Find the largest set of activities
with no overlap.
Example: Activity selection
An intuitive approach is to repeatedly pick the
leftmost activity.
Does this produce the largest set of activities?
Example: Activity selection
This method may be fooled! Consider the following:
Example: Activity selection
How would you normally pick among a set of tasks?
Do the one with the earliest deadline first!
Tactic 2. Symmetry
Example: Gray code to binary code
3-bit Gray code 3-bit binary code
000 000
001 001
011 010
010 011
110 100
111 101
101 110
100 111
Some observations:
I The leftmost column is always the same.
I After a column of ones, the order flips
(reflection).
Example: Gray code to binary code
3-bit Gray code
000
001
Order 0 1 0
011
1 0 1
010
Gray code 1 1 0
110
Binary code 1 0 0
111
101
100
Tactic 3. Space/time trade-off
Instead of always computing an answer from
scratch, it may be worthwhile to precompute some
partial results.
Example: Computing segment sums
Given an array A of integers, compute the sum of
any segment A[i, j] efficiently.
6 4 -3 0 5 1 8 7
For example,
I A[1, 3] = 6 + 4 + −3 = 7
I A[3, 7] = −3 + 0 + 5 + 1 + 8 = 11
Example: Computing segment sums
Wishful thinking Computing for any segment A[i, j]
is difficult, what if we consider only
segments of the form A[1, j]?
Space/time trade-off Sums for A[1, j] can be
precomputed and stored in a another
array P
A 6 4 -3 0 5 1 8 7
P 6 10 7 7 12 13 24 31
Example: Computing segment sums
A 6 4 -3 0 5 1 8 7
P 6 10 7 7 12 13 24 31
Observation
The sum for A[i, j] can be computed as
P[j] − P[i] + A[i].
Example: Computing segment sums
Looking back
I What is special about sum?
I Does this work with max/min? If not, can the
idea be adapted?
Outline
What is problem solving?
Strategies and tactics
Getting started (Strategies)
Making progress (Tactics)
Summary
Strategies and tactics
Strategies Tactics
1. Get your hands dirty 1. Extremal principle
2. Restate the problem 2. Symmetry
3. Wishful thinking 3. Space/time trade-off
Duality of Problem and Solution
If we really understand the problem, the
answer will come out of it, because the
answer is not separate from the problem.
J. Krishnamurti