1、Introduction to Problem Solving,Clifford A. Shaffer Department of Computer Science Virginia TechCopyright 2007,Goals of This Course,Make you a better problem solver in general Understand how you operate Recognize limitations and pitfalls Learn techniques that you can apply to solve problems Improve
2、your ability to successfully complete the CS degree,What Motivated This Course?,We designed this course in hopes of: Improving students ability to design Improving students ability to develop algorithms Improving students ability to plan (projects) Improving students ability to test and debug Improv
3、ing students performance on tests Improving students analytical abilities Improving students ability to “argue” (proving) Improving students ability with personal interactions,Course Organization/Process,Learn about yourself Learn problem-solving techniques Solve a wide variety of problems, so as to
4、 learn how to apply the techniques (Levine: Descriptive vs. Proscriptive),What Kinds of Problems?,Problems “in the large”: Engineering tasks Lots of formal process, well developed Problems “in the small”: Puzzles, homework Heuristics Success as a student Interpersonal problems Take a “problem-solvin
5、g” stance Analysis, construction, organization, process, understanding,Know Yourself,Whimbey Analytical Skills Inventory (WASI) Myers-Briggs Personality Type (Homework Assignment 1) http:/ http:/ http:/ (It is good to do a couple of different MB tests, results vary somewhat. Then, read the descripti
6、ons.),WASI Problem Types,Overall: 15.6% average error rate (5.6 wrong) V: Verbal Reasoning 1.6 20% average error rate(13, 15, 16, 28, 32, 35, 37, 38) F: Following Sequential Instructions1.5 16.7% average error rate(9, 10, 17, 18, 20, 22, 23, 34, 36) A: Analogy 0.8 (2, 3, 4, 5, 12, 24, 26, 30) T: Ana
7、lysis of Trends 0.9 15% avg (8, 11, 14, 21, 25, 29) W: Writing Relationship Sentences (1, 6, 19) M: Math Word Problems (31, 33),Errors in Reasoning,Goal: Identify common types of errors and avoid them. Many of these come up in the WASI A major reason for taking it is so that you can self-identify er
8、rors that you tend to make Many points are lost on tests/homeworks in school come from errors in reasoning, not from lack of knowledge or skills. You can train yourself not to make this sort of mistake.,Types of Errors,Lack of knowledge or skill This isnt our focus, and its often not the issue Perso
9、n fails to observe and use all relevant facts of a problem This might come from poor reading comprehension (which in turn often comes from rushing) Person fails to approach the problem in a systematic manner, skips steps or jumps to conclusion Person fails to spell out relationships fully Person is
10、sloppy or inaccurate makes “simple” mistake,Error Types Checklist,Inaccuracy in Reading Inaccuracy in Thinking Weakness in Problem Analysis; Inactiveness Lack of Perseverance,Myers-Briggs Type Indicator,Four dichotomies that define sixteen categories Each is a continuum, not a binary choice This is
11、not “what you are” It is “right now, what you prefer” (and strength of preference) For example, most introverts can operate in extrovert mode when needed. Results can vary from test to test or day to day by several points.Results are generally consistent, between “adjacent” types Wikipedia has good
12、articles for some types,Why Does it Matter?,Presumably, different types are better/worse at different tasks CS needs an unusually broad range of types to get everything done Numerical analysis vs. HCI Mangers, architects, programmers, testers, documentation writers How do you best learn and work? In
13、teract in organizations? Type/type interpersonal interactions Team building,What Type Am I?,Depending on which test you take/ your current mood, you might end up assigned to different categories on different attempts. Testers often defer to the person on “best fit” category. Be careful when reading
14、the descriptions They tend to be general They tend to be a bit flattering (which category type is for scatterbrained people? For couch potatoes?) In general, readers tend to agree with any generic assignment that they are given (Forer effect),Potential Failings,Is it accurate? Unstable: Lots of vari
15、ation in results between instruments and over time Does it make sense to say there are 16 personality types? Does it actually predict anything?,Four Dichotomies,The words used for the poles on each of the four dichotomies have technical meanings You cant interpret what these mean using the everyday
16、definitions of the words A person isnt “more judgmental” or “less perceptive” in these words everyday meaning,Introvert/Extravert Attitude,Defines the source and direction of energy expression for a person. Extravert has a source and direction of energy expression mainly in the external world. Act/r
17、eflect/act. Energy/motivation decline with inactivity. Introvert has a source of energy mainly in the internal world. Reflect/act/reflect. Needs downtime after action to reflect.,Introvert/Extravert (Cont),These meanings are clearly different from common use. You might prefer to curl up with a book
18、(given the choice), but can still enjoy and interact at a party without being shy An extravert might prefer parties, but that doesnt tell us whether he is a “loud” person or not,Sensing/iNtuition Function,Defines the method of information perception Sensing means that a person believes mainly inform
19、ation received directly from the external world tangible and concrete facts drive patterns. More present oriented. Methodical, precise. Intuition means that a person believes mainly information he or she receives from inside (books, memories) how facts fit into the pattern. More future oriented. “Fl
20、ash of insight.” Dislikes routine. Says what you prefer to focus on Often need to use the opposite to “check”,Thinking/Feeling Function,Defines how the person processes information (decision making). Both strive to make rational decisions. Both can be practiced/strengthened. Thinking means that a pe
21、rson makes a decision mainly through logic/reason. More detached, impersonal. Feeling means that, as a rule, he or she makes a decision based on emotion. Look at from “inside” and strive to reach balance/harmony/consensus with values. More personal, subjective. “Heart vs. Head” You will trust your p
22、referred approach better, but most have some ability to work in either mode.,Judging/Perceiving Lifestyle,Defines how a person implements the information he or she has processed. Judging means that a person organizes all his life events and acts strictly according to his plans. Prefers things decide
23、d. Prefers things on time. Might seem inflexible. Perceiving means that he or she is inclined to improvise and seek alternatives. Likes to leave things open. More likely to push deadlines.,MB Example,INTJ Strength in each dimension (ex: mild I vs. E, mild N vs. S, moderate-strong T, strong J) Occurr
24、ence in population (this one is 1-2%) While I tend toward INTJ, on any given day/test I might register as ENTJ or ISTJ. But the descriptions make me clearly self-identify.,What is the CS Personality?,What is the “public perception”? What is your perception?,Type Distribution,Class Preferences,Releva
25、nce to Education,Different types prefer various teaching/testing styles Sensing and Judging types prefer memorization and recall iNtuition types prefer hypothesis/essay Most in population are sensing Most faculty are intuition Engineering students are split evenly N/S, but these groups have differen
26、t needs,Learning a Skill,In general, to learn a skill (golf, driving car): Skill is demonstrated to student Student is directed and guided while practicing What about analytical reasoning skills? It goes on inside the head hard to demonstrate Hard to direct and guide student,Thinking Aloud,The most
27、effective way to expose the process is to verbalize our thinking process This is hard work! Not our normal mode Need to be careful to explain every step Demonstrate analytical reasoning by watching problem solvers solve problems while thinking aloud Practice problem solving by thinking aloud to a pa
28、rtner,Pairs Problem Solving,We will use the technique of Whimbey & Lochhead The partners have distinct roles: One partner should read and think aloud. The other partner is the listener Continually check accuracy Demand constant vocalization Thinking is a skill but it is largely invisible So we need
29、to do everything possible to make it visible during this process,Problem 1,If the circle below is taller than the square and the triangle is shorter than the square, put a K in the circle. However, if this is not the case, put a T in the second tallest figure.,Problem 2,If the word sentence contains
30、 less than 9 letters and more than 3 vowels, circle the first vowel. Otherwise circle the consonant which is farthest to the right in the word.,Characteristics of Good Problem Solvers,Positive attitude Belief that academic reasoning problems can be solved through persistence, as opposed to believing
31、 “either you know it or you dont” Engage a confusing problem Concern for accuracy Actively work to check your understanding Break the problem into parts Avoid guessing And dont jump to conclusions Active in problem solving Do more things as part of the process,Problem 3,Bill, Judy, and Sally have th
32、e occupations of teacher, plumber, and teamster but not necessarily in that order. Bill is shorter than Judy but taller than Sally. The plumber is the tallest and teamster is the shortest. What is Judys occupation?,Role of the Listener,Crucial role, hard work. Continually check accuracy Catch errors
33、 Must work along/understand every step Dont let solver get ahead of him/herself Point out errors, do not correct Demand constant vocalization Solver must spell out EVERY step Not a passive role!,Problem 4,If the second letter in the word west comes after the fourth letter in the alphabet, circle the
34、 letter A below. If it does not, circle the B.A B,Getting Started with a Problem,“Eighty percent of success is showing up.” Woody Allen To successfully solve any problem, the most important issue to get actively involved. The Principle of Intimate Engagement: You must commit to the problem “Roll up
35、your sleeves” “Get your hands dirty.”,Easy vs. Hard Problems,Easy problems: See the answer Medium problems: See the answer once you engage Hard problems: You need strategies for coming up with a potential solution, sometimes for even getting started,Effective vs. Ineffective Problem Solvers,Effectiv
36、e: Believe that problems can be solved through the use of heuristics and careful persistent analysis Ineffective: Believe You either know it or you dont.Effective: Active in the problem-solving process: draw figures, make sketches, ask questions of themselves and others. Ineffective: Dont seem to un
37、derstand the level of personal effort needed to solve the problem.Effective: Take great care to understand all the facts and relationships accurately. Ineffective: Make judgments without checking for accuracy,Mental Toughness,Need the attributes of confidence and concentration Confidence comes with
38、practice Attack a new problem with an optimistic attitude Unfortunately, it takes time Need to develop a life-long habit,Engagers vs. Dismissers,Engagers typically have a history of success with problem solving. Dismissers have a history of failure. You might be an engager for one type of problem, a
39、nd a dismisser for another. You can “intervene with yourself” to change your attitude of dismissal,The Mental Block,Many students do significant problem solving for recreation Sodoku, computer games, recreational puzzles. These same students might dismiss math and analytical computer science problem
40、s due to a historical lack of success (the mental block) To be successful in life you will need to find ways to get over any mental blocks you have Learn to transfer successful problem-solving strategies from one part of your life to other parts. Example: Writing is a lot like programming,Example Pr
41、oblem,Connect each box with its same-letter mate without letting the lines cross or leaving the large box.,Engagement Example,Cryptoarithmetic problemA D + D I - D I D,“Real World” Engagement Examples,Repairing something (dryer, toaster, etc.) Dryer example: Clean it out Table example: Look for the
42、loose parts Car seat example: Reattach spring wire “Taking the time” You can screw something up or do something dangerous. But often you are not faced with such a prospect. Some domains require that you study/practice/build expertise to be effective The act of engagement can help you build domain kn
43、owledge,Overcoming Procrastination,Writing/programming/project) procrastination Just sit down and write, dont care about quality to start Write whatever part of the document/program appeals. Dont do it start to finish. Schedule to work. Milestones, etc. Commit to someone outside if that helps Invent
44、 deadlines if you are deadline driven Do part of it at a time, over time People dont write books, they write sections or pages People dont write programs, they write functions, etc.,Learning Styles: Class Results,Intuitors might need to be careful not to miss points from careless mistakes.,Verbal Re
45、asoning Problems,For this type of problem, we need to parse the text into the proper steps Then we need to sort out the steps Since they can get long and complicated, we usually need to resort to a diagram (externalize the information),VR Problem 1,Jose is heavier than Fred but lighter than Marty. W
46、rite their names in order of weight.,VR Problem 1 Solution,For these problems, as we work in pairs to solve them, we need to spell out the steps involved. We will try having the solver take notes during the process Step 1: Jose is heavier than Fred He would be placed above Fred on the diagram. Step
47、2: but lighter than Marty. So Marty is placed above Jose in the diagram.,VR Problem 2,Jack is slower than Phil but faster than Val. Val is slower than Jack but faster than Pete. Write the names in order of speed.,VR Problem 2 Solution,Step 1: Jack is slower than Phil He would be placed below Phil. S
48、tep 2: but faster than Val. This says Jack is faster than Val. Val is added below Jack. Step 3: Val is slower than Jack We already knew this. Step 4: But faster than Pete. Val is faster than Pets, so Pete comes below Val.,VR Problem 3,If Dumani and Fred are both richer than Tom, and Hal is poorer th
49、an Dumani but richer than Fred, which man is the poorest and which one is the next poorest? Write the names of all 4 men in order.,VR Problem 3 Solution,Step 1: If Dumani and Fred are both richer than TomThe problem does not indicate whether Dumani and Fred are actually equal to each other. So they can be represented at the same level for now, both above Tom. Step 2: while Hal is poorer than Dumani but richer than FredThis means that Dumani and Fred are not equal; Hal is between them with Dumani richest.Tom is poorest and Fred is next poorist.,
