Arnold Rosenbloom arnold@cs.toronto.edu http://www.cs.toronto.edu/~arnold

Problem Solving

Why is this important

• What I tell my students
• What students currently do: Building analogy
• What students need to be able to do: Building analogy, block of knowledge
• What do we do currently: What a text book knows
• What should we do: Teach them how to get from here to there. Teach them how to teach themselves. Show them how a human solves problems.
• Does the following approach work? yes

I Understand

• Understand the question. Understand all parts of the question, are all terms familiar. What does a solution look like?
• Understand the problem. See structure, relationships. You fully understand the problem when you have the solution.
• What does it feel like to understand? People typically don't know that they don't understand or that there is something to understand.
• How do I know that I understand? Indicators:
  • Ability to simply and concisely express yourself (ie in English). Key concepts highlighted, understand these and all else follows. Not all concepts are equally important.
  • See connections.
  • Develop an aesthetic sense. A simple solution is best. A concise explanation indicates understanding. Don't be satisfied with complexities, things tend to be simple once you understand. Strip away all unnecessary data, connections, facts etc.
  • Ability to explain "WHY", justify your position. I see the reason behind everything.
  • I am certain that I am correct (since I sufficiently argued all points with myself).
  • Marking Scheme (vs the ministry one)

    Level	What you did
    5	Reason, apply, problem solve, present: Correctly applies ideas to reach a clear, concise, correct, cleanly presented solution. Can reason about ideas presented. Can apply them to different settings. etc. Minor technical flaws allowed.
    4	As in 5 but lacks some clarity, not as concise as possible, some minor flaw, not a clean presentation. Not clearly explained, does not highlight key concepts.
    3	Semantics: Demonstrates correct understanding of basic definitions, ability to correctly apply basic techniques, theorem statements etc.
    2	Some major flaw in the understanding of basic definitions, techniques, theorem statements. Examples are: Applies theorems to wrong settings. Does not understand the goal (ie tries to prove the wrong result). Solves the wrong problem.
    1	Syntax: Ability to restate given definitions, theorems, techniques.

    Level	Question Type	Example
    5	Choice of tool is not clear	How many zeroes at the end of 999!
    3	Solution involves direct application/understanding of tool. They know which tool to use.	Use for loops to print out (0,0) (1,0) (1,1) (2,0) (2,1) (2,2) ... (n,0) (n,1) (n,2) ... (n,n)
    1	Solution involves memory.	Write a for loop that prints the numbers 20 to 50

I Understand

• You are part of the problem.
• Goal: Teach yourself enough about the problem so that the solution is simple, clear and obvious.
• I am human!!
• Price to pay in order to understand.
• We only learn simple things.
• Keep your EGO out of it. No "I'm stupid" etc.

I Understand

• How do I teach myself? Know what you know, know what you don't and how to cover the difference.
• Be introspective
• Be willing to say "I don't understand."
• Take action NOW (put the problem in your brain)
• Try something AND LEARN FROM IT.
• Know what you are doing and why.
• Doing something simple
• No matter what, there is always some evidence for...
• You are always making progress if you LEARN.
• Move from firm ground to firm ground.
• Expert: Knows how to place minimal effort to obtain maximum effect
• Becoming an expert at X: Repeat X until it's easy.

Common mistakes

• Wait for answer to pop into your head.
• Don't get started early. Put problem in your head, allow your brain time to connect and understand.
• Not recognizing the cost (effort required) to obtain the solution.
• Not addressing the abilities you are lacking in order to solve the problem.
• Not checking yourself. Ask yourself "Is it correct?"
• Managing yourself poorly (getting down on yourself).
• Fear of others knowing that you are stupid. Not asking questions in class. 'stupid' is irrelevant. The winner is the one that comes out of class understanding the most.
• Not learning from your efforts.
• Not simplifying, breaking down problem.
• Not committing yourself to understanding UGLY points.
• Not knowing that you don't know.

Problems

1. Learning a new programming language
2. How many 0s are at the end of 999! (Num0s.java Num0s.pl)
3. Find the last non-zero digit in 999!
4. Locker Room problem

   A locker room has lockers numbered 0,1,2,...,1023. All lockers are initially closed.

   The first person walks in and flips every locker The 2nd person flips every other locker (starting at 0) The 3rd person flips every third locker (starting at 0) . . . The 1023 person flips every 1023 locker (starting at 0) At the end, which lockers are open and which are closed?

   Level 3 solution, Level 4 solution (no explanation given). Note the flaw at 0 in both cases.

5. Card swapping problem: 25 people in a circle, a deck of 50 cards with numbers 1,1,2,2,...,25,25 on them. Each person gets 2 randomly selected cards. At each step, each person looks at their two cards and passes a smallest card left.

   Prove that eventually some person will be holding two cards with the same number on them.

6. Write function compress(s) which returns the run length encoding of alphabetic String s. Example: compress("")="", compress("a")="1a", compress("aaaa")="4a", compress("aaaabbca")="4a2b1c1a" Many solutions
7. The Jumble Problem: Word X is a jumble of word Y if the letters in X can be rearranged to give Y. Example: backwards drawbacks. Given a dictionary as input, find the largest group of words all of which are jumbles of each other.
8. 15 puzzle Exercises (look at the source for the pages below):
   • Write from scratch (simple uncommented solution)
   • comment this