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 (house vs place for 1,000)
• 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
• Going to the movies with dirty glasses.

Math is all around us, REALLY!!

• 
• Kira and the new tooth
• Kira and 'all dads are big' (understanding quantifiers)
• Induction : Game 'I know the biggest number'
• Simaya: Why do stairs have handrails? (proof by contradiction)
• Ethan: Can dogs drive? No! Because they don't have hands. (necessary condition)
• Why does a green light mean go, a red light mean stop?
• We have mental models: Proof of this...dreams. This is also proof that you are creative.

I Understand

• Reasoning: The main tool for understanding Nonogram (or online), Minesweeper
• There is more to understand. Text books and Karate.
• 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) or find the derivative of a polynomial, find the area of a rectangle.
    1	Solution involves memory.	Write a for loop that prints the numbers 21 to 50 or what is the formulae for the area of a rectangle.

  • The above marking scheme applied to Karate.

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.
• The will to act!
• 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.
• There is always evidence!
• Be introspective
• Be willing to say "I don't understand" and then do something about it.
• Know how to test your understanding (ask questions, even to yourself).
• Take action NOW (put the problem in your brain)
• Try something AND LEARN FROM IT.
• The will to act.
• Know that there is something you can do to solve the problem, random guessing is not the only approach (ie. minesweeper)
• Know what you are doing and why.
• Doing something simple AND LEARN FROM IT!! Kids already know this.
• No matter what, there is always some evidence for...
• Understand how to reason (ie. Minesweeper, Paint By Numbers) Reasoning
• 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. Problems from the Problem Solving Diagnostic
2. How many digits to represent 999!? How many 0s are at the end of 999! (Num0s.java Num0s.pl)
3. 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.

4. I have a garden with red,green and blue flowers (all represented). I notice that if I were to choose 3 of them, I would have at least one red. I were to choose 3 of them, I would have at least one green. Prove that if I choose any 3 of them, then I would have at least one blue.
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
9. 1-50,000 1-50,000 Problem: You are given a list containing 100,000 numbers. Each of 1,2,...,50,000 appears twice in this list. Someone replaces one of the numbers with 73 and jumbles the list. Your job is to write a program to determine which number was removed.
10. 2-Colouring the plane: Given an arrangement of infinite lines in the plane, prove that the regions defined by these lines can be coloured using only two colours. Two regions that share a line segment can not have the same colour.
11. How many different ways are there to two color the regions in the above problem?
12. Write a Java program that randomly draws 100 lines on a JPanel and then two-colours the resulting region.
13. Write a recursive function isJumble(x,y) which determines if word x and y are jumbles of eachother.
14. Use recursion/function calls to print out (0,0) (1,0) (1,1) (2,0) (2,1) (2,2) ... (n,0) (n,1) (n,2) ... (n,n)
15. Become an expert at minesweeper
16. Understand and explain the proof that Sqrt(2) is irrational. Modify it so that it now proves that Sqrt(5) is irrational. Modify it in a similar way so that it proves that Sqrt(16) is irrational (oops!!!) whats wrong?
17. You have three Jugs with capacities 8,5,3 respectively. The Jug with 8 units is initially full. How can you measure 4 units? Write a java program that allows a user to play this puzzle. Use the Model View Controller architecture and a GUI front end.
18. Consider a checkerboard which has dimensions 2²⁰⁰⁰ by 2²⁰⁰⁰. Now remove 1 square. You want to tile the checkerboard with tiles that have the shape below. You must not cover the 'removed' square.
    Prove that, no matter which square you remove, you can always completely tile the resulting checkerboard.

    o
    o	o