Great Theoretical Ideas In Computer Science Steven Rudich Lecture 15 CS 15 251 March 1 2005 Spring 2005 Carnegie Mellon University Problem Solving Where does the aha come from A 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 problem 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 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 Strategy As you talk to yourself make sure to tag assertions with phrases that denote degrees of conviction 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 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 shuttle 1 and 2 must be shuttles Let s try a solution with 1 and 2 as the first move 1 2 5 10 5 10 2 5 10 2 12 2 1 1 5 1 1 5 10 10 2 5 10 A different intuitive approach to the same problem Load Balancing 5 and 10 Load Balancing Handle our hardest work loads in parallel Work backwards by assuming 5 and 10 walk together 1 2 5 10 5 10 2 5 10 2 12 2 1 1 5 1 1 5 10 10 2 5 10 PROBLEM 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 COMPOSITION Mathematical 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 INTUIT CLEAN UP by PROVING a LEMMA By giving the right qualifiers COMBINE lemmas at will A volunteer please Martial Arts 101 The novice makes a huge motion The black belt makes a small motion The master makes a tiny motion Violin piano tennis magic programming singing The novice makes a huge motion The black belt makes a small motion The master makes a tiny motion Scanning the brains of master problem solvers The better the problem solver the less brain activity is evident The real masters show almost no brain activity Simple and to the point Scanning the brains of master problem solvers The expert represents his her state as simply as possible Value Simplicity The root of effective thinking effective science effective mathematics effective engineering is to keep the issues simple The Dirty Little Secret Even the smartest people have limited brains that work with simple representations and pictures BE OF TWO SIMPLE MINDS That really was a Microsoft question Why do you think that they ask such questions as opposed to asking for a piece of code to do binary search 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 com 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 Content 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 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 Two Minds Representation Induction Modularity Exemplification Improvement Abstraction Toolkit Representation Understand the relationship between different representations of the same information or idea 1 2 3 Toolkit Name abstract objects and ideas and put them …
View Full Document
Unlocking...