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 problemSlide 7So what is the answer?Intuitive, But FalseKeep track of what you actually know – remember what you merely suspect.Tagging StrategyPhrase HygieneSlide 13Slide 14Slide 15Slide 16Slide 17Slide 18Slide 19The future belongs to the computer scientist who haswww.discretemath.comSlide 22Slide 23Slide 24Slide 25Slide 26Slide 27Slide 28Representation: Understand the relationship between different representations of the same information or ideaExemplification: 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.Bracketing: What are the best lower and upper bounds that I can prove?Slide 36Slide 37Slide 38Slide 39Slide 40Slide 41Slide 42Slide 43Slide 44Slide 45Slide 46Slide 47Slide 48Slide 49Slide 50Get The Problem Right!Try and remove inessential details.Conjecture Versus FactGetting To Know The ProblemChoose Your RepresentationSlide 56Slide 57Slide 58Slide 59Slide 60Slide 61Pk(X) = an Xk + an-1 Xk-1 + … + an-k+1 X + an-k Goal: Compute Pn(X)Slide 63Slide 64Slide 65Martial Arts 101Violin, piano, tennis, magic, programming, singing, . . .Scanning the brains of master problem solversSlide 69Value SimplicityProblem Solving:Where does the “aha!” come from?Great Theoretical Ideas In Computer ScienceSteven RudichCS 15-251 Spring 2004Lecture 13 Feb 24, 2004 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 ay 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 ay 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 ay 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 convictionPhrase HygieneDevelop stock phrases to classify statements. Learn from experience and eliminate ambiguous or misleading phrases like “Even if”.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.”If it is possible, there must be 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!If we are going to leave someone for a return trip later, it might as well be 1. Ok, so we start with 1 and X and then X returns.. X must be 2, since that minimized the cost 2X.1 2 5 10 5 102 5 1021 22 111 5 105 101 2 5 105 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 10Why do you think that they ask such questions, as opposed to asking for a piece of code to do binary search?That really was a Microsoft question.•Content: An up to date grasp of fundamental problems and solutions•Method: Principles and techniques to solve the vast array of unfamiliar problems that arise in a rapidly changing field The future belongs to the computer scientist who has•Content: An up to date grasp of fundamental problems and solutions•Method: Principles and techniques to solve the vast array of unfamiliar problems that arise in a rapidly changing field www.discretemath.comContent, i.e., definitions, formulas, recipes, standard manipulations, I can handle!“Method” is intimidating. What if, the plain and simple truth is that, I am not that smart?Don’t jump to unwarranted conclusions! Clever and resourceful problem solving is a skill that can be taught and refined.Yeah, but I knows lots of people who don’t need a lecture on problem solving methods. Brilliance just comes to them.So you are not a natural? – What of it? – Some world class tennis players did not start as natural backhanders. They had to be coached and developed.Bonzo, I don’t pretend to know the nature of your potential, but I am sure that if you study, practice, and refine your problem solving skills, you will become massively better at it than you are now.I get it! I can’t possibly know the capacities of my brain hardware, until I have appropriately reprogrammed my brain software.Aha! I know where the “aha!” comes from!•Representation•Induction•Modularity•Exemplification•Refinement•Abstraction•BracketingToolkit:Name abstract objects and ideas, and put them in your toolkit. Know their advantages and limitations.Representation:Understand the relationship between different representations of the same information or idea123Exemplification:Try out a problem or solution on small examples.Abstraction: Abstract away the
View Full Document
Unlocking...