Problem Solving: Where does the “aha!” come from?Slide 2Relax …….Relax, I am just going to ask you a Microsoft interview question.Do You Understand The Question?You have one minute to solve this problemSo what is the answer?Intuitive, But FalseKeep track of what you actually know – remember what you merely suspect.Tagging StrategySlide 11“even If we use the fastest guy to shuttle the others, they take too long.”Slide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19Slide 20PROBLEM SOLVING POWERCERTAINTY AND COMPOSITIONBE OF TWO CLEAR MINDS!INTUITION and COMPOSITION?Slide 25Martial Arts 101Violin, piano, tennis, magic, programming, singing, . . .Scanning the brains of master problem solversSlide 29Value SimplicityThe Dirty Little SecretBE OF TWO, SIMPLE MINDSSlide 33The future belongs to the computer scientist who haswww.discretemath.comSlide 36Slide 37Slide 38Slide 39Slide 40Slide 41Representation: Understand the relationship between different representations of the same information or ideaSlide 43Exemplification: Try out a problem or solution on small examples.Abstraction: Abstract away the inessential features of a problemInduction has many guises. Master their interrelationship.Modularity: Decompose a complex problem into simpler subproblemsImprovement: The best solution comes from a process of repeatedly refining and improving solutions and proofs.Slide 49Slide 50Slide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Bracketing: What are the best lower and upper bounds that I can prove?Slide 63Slide 64Slide 65Slide 66Slide 67Pk(X) = an Xk + an-1 Xk-1 + … + an-k+1 X + an-k Goal: Compute Pn(X)Slide 69Slide 70Problem Solving:Where does the “aha!” come from?Great Theoretical Ideas In Computer ScienceSteven RudichCS 15-251 Spring 2005Lecture 15 March 1, 2005 Carnegie Mellon UniversityA volunteer, please.Relax …….Relax, I am just going to ask you a Microsoft interview question.Do You Understand The Question?Four guys want to cross a bridge that can only hold two people at one time. It is pitch dark and they only have one flashlight, so people must cross either alone or in pairs (bringing the flashlight). Their walking speeds allow them to cross in 1, 2, 5, and 10 minutes, respectively. Is it possible for them to all cross in 17 minutes?You have one minute to solve this problemFour guys want to cross a bridge that can only hold two people at one time. It is pitch dark and they only have one flashlight, so people must cross either alone or in pairs (bringing the flashlight). Their walking speeds allow them to cross in 1, 2, 5, and 10 minutes, respectively. Is it possible for them to all cross in 17 minutes?So what is the answer?Four guys want to cross a bridge that can only hold two people at one time. It is pitch dark and they only have one flashlight, so people must cross either alone or in pairs (bringing the flashlight). Their walking speeds allow them to cross in 1, 2, 5, and 10 minutes, respectively. Is it possible for them to all cross in 17 minutes?Intuitive, But False“10 + 5 + 2 + 1 = 18, so the four guys just can’t cross in 17 minutes”“Even if the fastest guy is the one to shuttle the others back and forth – you use at least 10 + 5 + 2 + 1 > 17 minutes”Keep track of what you actually know – remember what you merely suspect.“10 + 5 + 2 + 1 = 18, so it would be weird if the four guys could cross in 17 minutes”“even If we use the fastest guy to shuttle the others, they take too long.”Tagging StrategyAs you talk to yourself, make sure to tag assertions with phrases that denote degrees of convictionKeep track of what you actually know – remember what you merely suspect.“10 + 5 + 2 + 1 = 18, so it would be weird if the four guys could cross in 17 minutes”“even If we use the fastest guy to shuttle the others, they take too long.”“even If we use the fastest guy to shuttle the others, they take too long.”No faster than 18 solution can use the same “shuttle” guy for every trip. This gives me the idea of trying a solution with 2 shuttle guys.Any solution must involve more than one guy doing the return trips: it must be that someone gets deposited on one side and comes back for the return trip later!Intuitively, if we use two shuttles, they should be 1 and 2.Can I prove that?Intuitively, if we use two shuttles, they should be 1 and 2.Can I prove that? Yes, each shuttle make 3 trips. Thus, he 10 can’t be a shuttle. The 5 would use 15 minutes for 2 trip, plus 5 extra for when the 10 goes. 5 can’t be a shuttle1 and 2 must be shuttles.Let’s try a solution with 1 and 2 as the first move….1 2 5 10 5 102 5 1021 22 111 5 105 101 2 5 10A different intuitive approach to the same problem:Load Balancing5 and 10Load Balancing:Handle our hardest work loads in parallel! Work backwards by assuming 5 and 10 walk together.1 2 5 10 5 102 5 1021 22 111 5 105 101 2 5 10PROBLEM SOLVING POWER•UNDERSTAND what the problem is asking.•TAG thoughts to distinguish between intuition and certainty.•TRANSFORM/CLEAN-UP intermediate intuitions by pushing them to certainty (theorems).CERTAINTY AND COMPOSITIONMathematical statements and inferences are CERTAIN – they compose to make arbitrarily long and completely correct CHAINS of DEDUCTIVE reasoning.Intuitions are fantastic, but necessarily build on each other inductively to make correct statements. INTUITION are ENABLING, but they are only approximate.BE OF TWO CLEAR MINDS!Your intuitive, associative, narrative, conjectural mind.Your “what do I really know for sure?” – mathematical, logical, and unambiguous mind.INTUITION and COMPOSITION?INTUITCLEAN-UP •by PROVING a LEMMA•By giving the right qualifiersCOMBINE lemmas at will.A volunteer, please.Martial Arts 101•The The novicenovice makes a makes a hugehuge motionmotion•The The black beltblack belt makes a makes a smallsmall motion motion•The The mastermaster makes a makes a tiny tiny motionmotionViolin, piano, tennis, magic, programming, singing, . . .•The The novicenovice makes a makes a hugehuge motionmotion•The The black beltblack belt makes a makes a smallsmall motion motion•The The mastermaster makes a makes a tiny tiny motionmotionScanning the brains of master problem solversThe better the The better the problem solver, the problem solver, the less brain activity is less brain activity is evident. The real evident. The real masters show masters show almost
View Full Document
Unlocking...