Transcript Coursenotes

Getting Started with a Problem
• “Eighty percent of success is showing up.”
– Woody Allen
• “Success is 1% inspiration and 99% perspiration.”
– Thomas Edison.
• To successfully solve any problem, the most important
step is to get actively involved.
– The Principle of Intimate Engagement: You must commit to the
problem
– “Roll up your sleeves”
– “Get your hands dirty.”
1
Easy vs. Hard Problems
• Exercises: (e.g. compute 10! without a calculator)
• Easy problems: See the answer
• Medium problems: See the answer once you
engage
• Hard problems: You need strategies for coming
up with a potential solution, sometimes for even
getting started. Open-ended problems are
often like this. Often, multiple possible solutions,
you need a strategy to choose “the best” one.
(e.g. Estimate 2710! Why is this one hard? You can use a
calculator… )
http://en.wikipedia.org/wiki/Stirling%27s_approximation
2
Effective vs. Ineffective
Problem Solvers
Effective: Believe that problems can be solved through the
use of heuristics and careful persistent analysis
Ineffective: Believe ``You either know it or you don't.''
Effective: Active in the problem-solving process: draw
figures, make sketches, ask questions of themselves
and others.
Ineffective: Don't seem to understand the level of personal
effort needed to solve the problem.
Effective: Take great care to understand all the facts and
relationships accurately.
Ineffective: Make judgments without checking for accuracy
3
Mental Toughness
• Need the attributes of confidence and
concentration
– Confidence comes with practice
– Attack a new problem with an optimistic
attitude
• Unfortunately, it takes time
– You can’t turn it on and off at will
– Need to develop a life-long habit
4
Engagers vs. Dismissers
• Engagers typically have a history of success
with problem solving.
• Dismissers have a history of failure.
• You might be an engager for one type of
problem, and a dismisser for another.
• You can “intervene with yourself” to change your
attitude of dismissal
5
The Mental Block
• Many students do significant problem solving for
recreation
– Sodoku, computer games, recreational puzzles.
• These same students might dismiss math and
analytical computer science problems due to a
historical lack of success (the mental block)
And the other way around: dismissing verbal
problems.
• To be successful in life you will need to find
ways to get over any mental blocks you have
• Learn to transfer successful problem-solving
strategies from one part of your life to other
parts.
– Example: Writing is a lot like programming
6
Example Problem
• Connect each box with its same-letter
mate without letting the lines cross or
leaving the large box. (Actual problem used in software
company job interview)
B
A
C
C
B
A
7
Strategy (my favorite): solve a
simpler problem first.
B
A
C
C
A
C
B
A
8
Heuristic: Wishful Thinking
B
A
C
B
B
C
C
A
C
B
A
B
A
B
A
A
C
C
C
B
A
C
B
A
Engagement Example
• Cryptoarithmetic problem (base 10)
AD
+DI
--------DID
Need to start somewhere,
find a chink in the problem’s armor
10
The 9 coin problem
9 coins that look alike. One is
fake, can be heavier or lighter (not
known). Using a simple balance
scale and 3 weighing, single out
the fake one.
Hint: solve a simpler problem first. Which one?
The
solution
for
3
coins:
the weighings are:
1 against 2
1 against 3
Both of these can have three outcomes: fall to the left (l), fall to the
right (r), or balance (b). The following table gives the answer for each
of these outcomes:
outcome fake coin # why:
----------------------ll
1
too heavy
lb
2
too light
lr
(not possible)
bl
3
too light
bb
no fake coin
br
3
too heavy
rl
(not possible)
rb
2
too heavy
rr
1
too light
The solution for 9 coins:
Step 1. Divide 9 coins into 3 piles of 3 coins each.
Use the 3-coin
strategy to weigh:
pile 1 against pile 2
pile 1 against pile 3
From Step 1, you will determine: a) which pile contains the fake
and
b) if the fake is heavier or lighter.
Step 2: Weigh 2 coins from the pile that contains fake.
Total # of weighings: 2+1 = 3.
More: The 12 coins puzzle
the 9 coin interactive
Let’s get closer to the real world:
In “Gulliver’s Travels”, by Swift, Gulliver travels to distant parts of the Earth
where he meets liliputians who are mere 6 inch tall, and giants who are
72 feet tall. These people are made of the same kind of flesh, muscle
and bone; and look pretty much like like Gulliver who is 6 feet tall.
Problem 1: It takes one full liliputian glass of their good and strong wine for
the liliputian to start feeling joyous. How many such glasses does Gulliver need
for the same effect?
Problem 2: How many liliputian suites needs to be cut and and re-stitched to make
a suit to fit Gulliver?
Problem 3: According to Gulliver’s story, the giants could walk, run and jump
just like Gulliver. Why is this not really possible?
Ok, now a real real one. Use ANY source of information available,
including the web. In fact, you have to, to solve it. Start by figuring
out what is being asked. Read about it a bit.
The problem: Prove that even with the best of today’s computers
the protein folding problem can not be solved by an algorithm that performs
an exhaustive search for the minimum energy configuration of
the polypeptide chain.
f1
f2
f3
f4
Here is what a polypeptide chain looks like. Angles between links can take on
any value from 0 to 360 degrees. The set of angles { f_k } uniquely
specifies the chain. In a typical protein there are k=100 or more links. The
biologically functional folded state of the chain ( protein ) has the absolute lowest
energy of all possible configurations. Any two configurations in which angles differ
by less that 36 degrees (error margin) can be considered identical.
Solution Steps:
1.
Google for unknown terminology. Read
about the “protein folding” problem.
2.
Estimate the number of conformations that you would
need to go through (exhaustive search - all of them).
f1
f2
f4
f3
A typical protein is a chain of ~ 100 mino acids.
Assume that each amino acid can take up only 10 conformations (vast
underestimation)
Total number of possible conformations: 10100
Suppose each energy estimate is just 1 float point operation. Suppose
you have a Penta-Flop supercomputer (find out what “penta-flop” is).
An exhaustive search for the global minimum would take 1085
seconds ~ 3*1078 years. Age of the Universe ~ 2*1010 years.
Well, an exhaustive search is really bad. How about
something more clever? Tons of methods exist for
minimization of a multi-dimensional functions. But, in
the case of protein folding we have 1000-dimensional
space and very rugged landscape. Lost of local
minima. Need just one global one. Very hard.
2
Free energy
3
1
Folding coordinate
Adopted from Ken Dill’s web site at UCSF
Finding a global minimum in a
multidimensional case is easy only
when the landscape is smooth. No
matter where you start (1, 2 or 3),
you quickly end up at the bottom - the Native (N), functional state of
the protein.
Adopted from Ken Dill’s web site at UCSF
Realistic landscapes are much
more complex, with multiple
local minima – folding traps.
Proteins “trapped” in those
minima may lead to disease,
such as Altzheimer’s
Adopted from Dobson, NATURE 426, 884 2003
Intrigued?
Suggested reading:
1.“Protein Folding and Misfolding”, C.
Dobson, Nature 426, 884 (2003).
2. “Design of a Novel Globular Protein Fold
with Atomic-level Accuracy, Kuhlman et al. ,
Science, 302, 1364, (2003)
+ references therein.