CIT 108 Problem Solving Strategies (PDF)

COURSE GUIDE CIT108 PROBLEM SOLVING STRATEGIES Course Team Dr. Tola John Odule (Developer/Writer) Prof. Julius Olatunji Okesola (Content Editor) Dr. Francis B. Osang – HOD/Internal Quality Control Expert NATI...

COURSE GUIDE CIT108 PROBLEM SOLVING STRATEGIES Course Team Dr. Tola John Odule (Developer/Writer) Prof. Julius Olatunji Okesola (Content Editor) Dr. Francis B. Osang – HOD/Internal Quality Control Expert NATIONAL OPEN UNIVERSITY OF NIGERIA CIT108 COURSE GUIDE National Open University of Nigeria University Village, Plot 91 Jabi Cadastral Zone Nnamdi Azikiwe Expressway Jabi, Abuja Lagos Office 14/16 Ahmadu Bello Way Victoria Island, Lagos Departmental email: [email protected] NOUN e-mail: [email protected] URL: www.nou.edu.ng First Printed 2022 ISBN: 978-058-557-5 All Rights Reserved Printed by: NOUN PRESS January 2022 ii CIT108 COURSE GUIDE CONTENTS PAGES Introduction…………………………………………. iv Course Aim……………………………………… v Course Objectives ….………………………………..v Working through this course…………………… vii Study Units……………………………………… vii Presentation Schedule………………………………. viii Assessment……………………………………… ix Tutor-Marked Assignment (TMAs)…………….. ix Final Examination and Grading………………… ix Course Marking Scheme…………………………… x Facilitators/Tutors and Tutorials……………….. x Summary……………………………………….. xi iii CIT108 COURSE GUIDE INTRODUCTION Usually the term problem is used to refer to a situation where it is not immediately obvious how to reach the goal. Formally, a problem is defined by the following four conditions or parameters: A clearly defined 1. Initial situation. 2. Goal. 3. Set of resources that may be applicable to move from the given initial situation to the desired goal situation. There may be specified limitations on resources, such as rules, regulations, and guidelines for what is allowed to do in attempting to solve a particular problem. 4. Commitment to using some of one’s own resources, such as knowledge, skills, and energies, to achieve the desired final goal. If one or more of these components are missing, the problem is ill- defined. Critical thinking is the use of those cognitive skills or strategies that increases the probability of a desirable outcome. Problem solving consists of moving from a given initial situation to a desired goal situation. It is the process of designing and carrying out a set of steps to reach a goal, and includes answering questions, solving problems, accomplishing tasks, making decisions, using critical thinking to do all of the above. Often the problem solving that students are expected to do is to recognize, pose, clarify, and solve complex, challenging problems that they have not previously encountered. Although nowadays algorithms are primarily associated with software and computers, their origins lie much further in the past. They have been used intuitively for centuries, in the form of regulatory systems, instructions, rules for games, architectural plans and musical scores. An algorithm is a procedure for decision-making or an instruction on how to act which consists of a finite number of rules. It may also be defined as a limited sequence of unambiguous elementary instructions which exactly and completely describe the way to solve a specific problem.” This applies regardless of whether it relates to mathematics, fine art or music. However, the most well-known application of algorithms is undoubtedly their use in computer programming. A program is thus an algorithm that is formulated in a language that allows it to be processed by a computer. This course is about deploying computational approaches to the problem-solving process using algorithm as a medium to achieve the defined goal in a computer-enabled format. iv CIT108 COURSE GUIDE COURSE AIM This course has two main goals: 1. It intends to introduction the student to the logical formulation and representation of problems in computer science, using critical thinking together with the established problem-solving strategies presented and with applicable implementation approaches. It seeks to equip the learner with the required technical know-how to handle common elementary routine problems that arise in practice the use of appropriate algorithms, flowcharts and pseudocodes as tools in a way to facilitate a computer-enabled representation for solution. COURSE OBJECTIVES To achieve the aims set out, the course has a set of objectives. Each unit has specific objectives which are included at the beginning of the unit. Students may wish to refer to them during their study to check on their progress. They should always look at the unit objectives after completion of each unit. By doing so, they would know whether they have followed the instruction in the unit. Below are the comprehensive objectives of the course as a whole. By meeting these objectives, learners should have achieved the aims of the course as a whole. In addition to the aims earlier stated, this course sets to achieve some objectives. Thus, after going through the course, learners should be able to:  Understand problem solving strategies  Define algorithm and heuristic and their role in problem solving  Describe typical common problem solving strategies  Explain some common roadblocks to effective problem solving  Understand the computer as a model of computation  Explain the problem solving process in detail  Apply the problem solving paradigm to routine elementary problems  Describe the various computational approaches available for solving a problem  Classify computational approaches based on their paradigms  Evaluate a computational approach best suited for a given problem  Apply a computational approach to solve a problem  Define abstraction as a problem aid  Understand the importance of abstraction in problem solving  Describe how to perform abstraction v CIT108 COURSE GUIDE  Explain the various types of abstraction used in problem solving  Understand the concept of algorithms  Appreciate the need for algorithms  Describe the steps involved in developing an algorithm  Develop algorithms for simple problems  Evaluate different algorithms based on their efficiency  Understand the basic concepts of flowcharts  Apply basic symbols and notations to create flowcharts  Differentiate among common types of flowcharts and where they apply  Understand the conditions that apply in the design of flowcharts  Undertake simple flowcharting problems  Understand the relevance of pseudocode in problem solving  Apply the rules guiding the use of pseudocodes  Demonstrate basic skills in writing pseudocode to address simple problems  Understand and define recursion as an implementation strategy  Know where and when to apply recursion to implement a solution  Determine how to avoid circularity in recursion  Explain the inner workings of recursion and the associated overhead  Explain control structures and their importance in implementation  Apply selection control structure to implement algorithms  Implement solutions using iteration as an alternative implementation strategy  Combine control structures in ways that facilitate solution to the problem at hand  Appreciate the term “decomposition” and “modularisation”  Understand how best decomposition can be approached  Justify the motivations for modularisation  Describe the basic properties of modularisation  Discuss the advantages of modularisation  Define and classify program testing  Explain the desirable properties of program testing  Appreciate the need for and benefits of program testing  Understand the debugging process and programming errors  Apply common strategies in debugging processes vi CIT108 COURSE GUIDE WORKING THROUGH THIS COURSE To complete this course, learners are required to read each study unit, read the textbooks and read other materials which may be provided by the National Open University of Nigeria. Each unit contains self-assessment exercises and at certain point in the course learners would be required to submit assignments for assessment purposes. At the end of the course there is a final examination. The course should take you about a total of 17 weeks to complete. Below learners will find listed all the components of the course, what they have to do and how they should allocate their time to each unit in order to complete the course on time and successfully. This course entails that learners spend a lot of time reading. It is advised that learners avail themselves the opportunity of comparing their knowledge with that of others. Study Units The study units in this course are as follows: Module 1 Problem Solving Strategies Unit 1 Roadmap to Solving Problems: Typical Strategies Unit 2 The Problem Solving Process Unit 3 Computational Approaches to Problem Solving Module 2 Role of Algorithms in Problem Solving Unit 1 Abstraction as a Problem Solving Tool Unit 2 Algorithms Unit 3 Flowcharts Unit 4 Pseudocode Module 3 Implementation Strategies Unit 1 Recursion Unit 2 Control Structure: Selection and Iteration Unit 3 Decomposition and Modularisation Unit 4 Testing and Debugging Module 1 is concerned with the problem solving strategies. It discusses the typical strategies commonly employed in creative thinking. It then vii CIT108 COURSE GUIDE goes on to discuss the actual processes involved in solving typical real- life problems using the computational paradigm. The module concludes with an examination of the different computational approaches applicable to different problem classes. The central theme of Module 2 is the role of algorithms in problem solving. The use of abstraction (logical representation of ideas) as a problem-solving tool was given prominence in this module. Ways to present the abstraction step-by-step for a mechanical procedure were discussed. Two other complementary discussions meant to aid graphical representation of the abstraction as well as constructs to aid the logical flow were also presented. Module 3, the final module, focussed on the implementation strategies. Since the main goal of every problem solving approach is to produce an efficient solution, various means through which a cost-effective implementation could be achieved constitute the subject-matter of this module. Implementation strategies such as recursion, control structures involving selection and iteration, decomposition and modularisation were covered. Finally, the issue of program testing and debugging was carefully x-rayed to ensure that the learner is adequately equipped with techniques to ensure that the presented solution not only works but is guaranteed to work. Each unit consists of one or two weeks’ work and include an introduction, objectives, reading materials, exercises, conclusion, summary, tutor-marked assignments (TMAs), references and other resources. The units direct the learners to work on exercises related to the required reading. In general, these exercises are meant to test the learners on the materials they have just covered or require them to apply the knowledge gained. They are thus assisted in evaluating their progress and reinforce their understanding of the materials. Together with TMAs, these exercises will help learners in achieving the stated learning objectives of the individual units and of the course as a whole. PRESENTATION SCHEDULE The course materials have important dates for the early and timely completion and submission of the TMAs and attending tutorials. Learners should remember that they are required to submit all their assignments by the stipulated time and date. They should guide against falling behind in their schedules. viii CIT108 COURSE GUIDE ASSESSMENT There are three aspects to the assessment of the course. First is made up of self-assessment exercises. Second, consists of the tutor-marked assignments and third is the written examination/end of course examination. Learners are strictly advised to do the exercises. In tackling the assignments, they are expected to apply information, knowledge and techniques gathered during the course. The assignments must be submitted to their facilitator for formal assessment in accordance with the deadline stated in the presentation schedule and the assessment file. The work submitted to the tutor for assessment will count for 30% of the total course mark. At the end of the course, learners will need to sit for a final or end of course examination of about three hours’ duration. This examination will count for 70% of the total course mark. TUTOR-MARKED ASSIGNMENT (TMAS) The TMA is a continuous assessment component of the course. It accounts for 30% of the total score. Learners will be given four TMAs to answer. Three of these must be answered before they are allowed to sit for end of course examination. The TMAs would be assigned by the facilitator and should be returned after you have done the assignment. Assignment questions for the units in this course are contained in the assignment file. Learners will be able to complete their assignments from the information and material contained in their reading, references and study units. However, it is desirable in all degree level of education for learners to demonstrate that they have read and researched more into their references, which will give a wider view point and may provide them with a deeper understanding of the subject. Make sure that each assignment reaches your facilitator on or before the deadline given in the presentation schedule and assignment file. If for any reason you cannot complete your work on time, contact your facilitator before the assignment is due to discuss the possibility of an extension. Extension will not be granted after the due date unless in exceptional circumstances. FINAL EXAMINATION AND GRADING The end of course examination for Problem Solving Algorithm (CIT108) will be for three (2) hours and it has a value of 70% of the total course score. The examination will consist of questions, which will ix CIT108 COURSE GUIDE reflect the type of self-testing, practice exercise and tutor-marked assignment problems that were previously encountered. All areas of the course will be assessed. Use the time between finishing the last unit and sitting for the examination to revise the whole course. You might find it useful to review your self-test, TMAs and comments on them before the examination. The end of course examination covers information from all parts of the course. COURSE MARKING SCHEME Assignment Marks Assignment 1 – 4 For assignment, best three marks of the four counts at 10% each, i.e., 30% of Course Marks. End of Course 70% 0f the overall Course Marks. Examination Total 100% of Course Material. FACILITATORS/TUTORS AND TUTORIALS There are 16 hours of tutorials provided in support of this course. Learners will be notified of the dates, time, and location of these tutorials as well as the name and phone number of the facilitator, as soon as they are allocated to a tutorial group. The facilitator will mark and comment on your assignments, keep a close watch on your progress and any difficulties you might face and provide assistance to you during the course. You are expected to mail your Tutor-Marked Assignments to your facilitator before the schedule date (at least two working days are required). They will be marked by the tutor and returned as soon as possible. Do not delay to contact your facilitator by telephone or e-mail if you need assistance. The following might be circumstances in which learners may find assistance necessary, hence they have to contact their facilitator if:  They do not understand any part of the study or assigned readings  They have difficulty with self-tests x CIT108 COURSE GUIDE  They have question or problem with an assignment or with the grading of an assignment. Learners should endeavour to attend the tutorials. This is the only chance to have face- to-face contact with their course facilitator and to ask questions which may be answered instantly. They can also raise any problem encountered in the course of your study. To have more benefits from course tutorials, learners are advised to prepare a list of questions before attending them. They will learn a lot from participating actively in discussions. SUMMARY Problem solving algorithm is a course designed to acquaint the learner with the tools and techniques required to navigate the deeper waters of computer science. It prepares the learner with the knowledge needed in the application of principles and theories of other areas of information communication technology. Upon completion of this course, learners will be able to apply the techniques and knowledge gained in handling basic and rudimentary design problems in computer science. xi  MAIN COURSE CONTENT PAGE Module 1 Problem Solving Strategies…………… 1 Unit 1 Roadmap to Solving Problems: Typical Strategies……………………… 1 Unit 2 The Problem Solving Process…………. 11 Unit 3 Computational Approaches to Problem Solving……………………… 24 Module 2 Role of Algorithms in Problem Solving…………………………………34 Unit 1 Abstraction as a Problem Solving Tool…………………………...34 Unit 2 Algorithms……………………………..44 Unit 3 Flowcharts……………………………..59 Unit 4 Pseudocode…………………………….73 Module 3 Implementation Strategies…………..83 Unit 1 Recursion……………………………...83 Unit 2 Control Structure: Selection and Iteration……………………………..…96 Unit 3 Decomposition and Modularisation…112 Unit 4 Testing and Debugging………………121 CIT 108 MODULE 1 MODULE 1 PROBLEM SOLVING STRATEGIES INTRODUCTION OF MODULE Problem solving is the process of identifying an existing problem, determining the root cause or causes of the problem, deciding the best course of action in order to solve the problem, and then finally implementing it to solve the problem. Problem-solving is used to solve our everyday basic needs; and there are many ways to solve problems. The countless number of everyday solutions are as diverse and specialized as the problems themselves. Problem solving techniques are great in variation and are nearly as important as the problem solving itself. Without having proper techniques to begin the problem solving process, individuals would find it much more difficult to do effectively. It Includes: trial and error, algorithms and heuristics, means-ends-analysis, etc. This list is by no means exhaustive and exemplifies how simple problem-solving techniques can be as well as how different they are from one another at times. Choosing the correct technique for the given situation is dependent on the individual, their experience and their resourcefulness. These issues are the subject-matter of this module and are covered in greater detail in subsequent Units that follow. UNIT 1 ROADMAP TO SOLVING PROBLEM: TYPICAL STRATEGIES 1.0 Introduction 2.0 Intended Learning Outcome 3.0 Main Content 3.1 Problem-solving strategies defined 3.2 Importance of Understanding Multiple Problem-solving Strategies 3.3 Trial and Error 3.4 Algorithm and Heuristic 3.5 Means-Ends Analysis 3.6 Other Problem-solving Strategies 4.0 Conclusion 5.0 Summary 6.0 Self-Assessment Exercise 7.0 References/Further Reading 1 CIT 108 PROBLEM SOLVING STRATEGIES 1.0 INTRODUCTION People face problems every day—usually. Sometimes these problems are straightforward, however, the problems we encounter are more complex. For example, say you have a work deadline, and you must mail a printed copy of a report to your supervisor by the end of the business day. The report is time-sensitive and must be sent overnight. You finished the report last night, but your printer will not work today. What should you do? First, you need to identify the problem and then apply a strategy for solving the problem. Practicing different problem-solving strategies can help professionals develop efficient solutions to challenges they encounter at work and in their everyday lives. Each industry, business and career has its own unique challenges suggesting that employees may implement different strategies to solve them. If you are interested in learning how to solve problems more effectively, then understanding how to implement several common problem-solving strategies may benefit you. In the sections that follow, we discuss what problem-solving strategies are, why they are important and list several examples of problem-solving strategies you can try. 2.0 Intended Learning Outcome At the end of this unit, students should be able to:  Understand problem solving strategies  Define algorithm and heuristic and their role in problem solving  Describe typical common problem solving strategies  Explain some common roadblocks to effective problem solving 3.0 Main Content 3.1 Problem-solving strategies defined Given a problem—be it a complex mathematical problem or a broken printer, the main concern is mapping out a strategy to solve or fix it. Finding a solution implies that the problem must first be clearly identified. After that, one of the many problem solving strategies can be applied, hopefully resulting in a solution. A problem-solving strategy is a plan used to find a solution or overcome a challenge. Different strategies have different action plans associated with them. For example, a well-known strategy is trial and error. Each problem-solving strategy includes multiple steps to provide you with helpful guidelines on how to resolve a business problem or industry 2 CIT 108 MODULE 1 challenge. Effective problem-solving requires you to identify the problem, select the right process to approach it and follow a plan tailored to the specific issue you are trying to solve. 3.2 Importance of Understanding Multiple Problem-solving Strategies Problems themselves can be classified into two different categories known as ill-defined and well-defined problems. Ill-defined problems represent issues that do not have clear goals, solution paths, or expected solutions whereas well-defined problems have specific goals, clearly defined solutions, and clear expected solutions. Problem solving often incorporates logical reasoning and interpretation of meanings behind the problem, and also in many cases require abstract thinking and creativity in order to find novel solutions. Various methods of studying problem solving exist including introspection, simulation, computer modelling, and experimentation. It is important to have a clear understanding of how a variety of problem-solving strategies work because different problems are typically required to be approached in different ways to find the best solution. By mastering several problem-solving strategies, you can more effectively select the right plan of action when faced with challenges in the future. This can help you solve problems faster and develop stronger critical thinking skills. 3.3 Trial and Error A trial-and-error approach to problem-solving involves trying a number of different solutions and ruling out those that do not work. This approach can be a good option if you have a very limited number of options available. In terms of a broken printer for example, one could try checking the ink levels, and if that doesn’t work, you could check to make sure the paper tray isn’t jammed. Or maybe the printer isn’t connected to a laptop. When using trial and error, one would continue to try different solutions until the problem is solved. Although trial and error is not typically one of the most time-efficient strategies, it is a commonly used one. 3.4 Algorithm and Heuristic A common type of strategy is an algorithm. An algorithm is a problem- solving formula that provides you with step-by-step instructions used to achieve a desired outcome (Kahneman, 2011). You can think of an algorithm as a recipe with highly detailed instructions that produce the same result every time they are performed. Algorithms are used 3 CIT 108 PROBLEM SOLVING STRATEGIES frequently in our everyday lives, especially in computer science. When you run a search on the Internet, search engines like Google use algorithms to decide which entries will appear first in your list of results. Facebook also uses algorithms to decide which posts to display on your newsfeed. Can you identify other situations in which algorithms are used? A heuristic is another type of problem-solving strategy. While an algorithm must be followed exactly to produce a correct result, a heuristic is a general problem-solving framework. You can think of these as mental shortcuts that are used to solve problems. A “rule of thumb” is an example of a heuristic. Such a rule saves the person time and energy when making a decision, but despite its time-saving characteristics, it is not always the best method for making a rational decision. Different types of heuristics are used in different types of situations, but the impulse to use a heuristic occurs when one of five conditions is met:  When one is faced with too much information  When the time to make a decision is limited  When the decision to be made is unimportant  When there is access to very little information to use in making the decision  When an appropriate heuristic happens to come to mind in the same moment Working backwards is a useful heuristic in which you begin solving the problem by focusing on the end result. It is common to use the working backwards heuristic to plan the events of your day on a regular basis, probably without even thinking about it. Another useful heuristic is the practice of accomplishing a large goal or task by breaking it into a series of smaller steps. Students often use this common method to complete a large research project or long essay for school. For example, students typically brainstorm, develop a thesis or main topic, research the chosen topic, organize their information into an outline, write a rough draft, revise and edit the rough draft, develop a final draft, organize the references list, and proofread their work before turning in the project. The large task becomes less overwhelming when it is broken down into a series of small steps. 3.5 Means-Ends Analysis This strategy involves choosing and analysing an action at a series of smaller steps to move closer to the goal. One example of means-end 4 CIT 108 MODULE 1 analysis can be found by using the Tower of Hanoi paradigm. This paradigm can be modelled as a word problem. The actual Tower of Hanoi problem consists of three rods sitting vertically on a base with a number of disks of different sizes that can slide onto any rod. The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top making a conical shape. The objective of the puzzle is to move the entire stack to another rod obeying the following rules: 1. Only one disk can be moved at a time. 2. Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack or on an empty rod. 3. No larger disc may be placed on top of a smaller disk. With 3 disks, the puzzle can be solved in 7 moves. The minimal moves required to solve a Tower of Hanoi puzzle is 2n – 1, where 𝑛 is the number of disks. For example, if there were 14 disks in the tower, the minimum amount of moves that could be made to solve the puzzle would be 214 – 1 = 16,383 moves. There are various ways of approaching the Tower of Hanoi or its related problems in addition to the approaches listed above including an iterative solution, recursive solution, non-recursive solution, a binary and Gray-code solutions, and graphical representations. An iterative solution entails moving the smallest pieces over one, then moving the next over one and if there is no tower position in the chosen direction you are moving to, move the pieces to the opposite end, but then continue to move in the same direction. By doing this one will complete the puzzle in the minimum amount of moves when there are 3 disks. Recursive solutions represent recognizing that the puzzle can be broken down into a series of sub problems to each of which the same general solving procedures apply, and then the total solution can be found by putting together the sub solutions. Non-recursive solutions entail recognizing that the procedures required to solve the problem have many regularities such as when counting the moves starting at 1, position of the disk in the series to be moved during move 𝑚 represents the number of times 𝑚 can be divided by 2 which indicates that every odd move involves the smallest disk. This allows for the following algorithm: Move the smallest disk to the peg that it has not recently come from. Move another disk legally (there will only be one possibility). A binary and Gray solutions describe disk move numbers in binary notation (base-2) where there is only one binary digit (a bit) for each 5 CIT 108 PROBLEM SOLVING STRATEGIES disk and the most significant (leftmost bit) represents the largest disk. A bit with a different value to the previous one means that the corresponding disk is one position to the left or right of the previous one. Graphical representations, as their name imply, represent visual presentations of conditions that can be modelled in order to view the most efficient and effective solutions. A common graph for the Tower of Hanoi is represented by a unidirectional, pyramid shaped graph, where different nodes (pieces within each level of the graph) represent distributions of disks and the edges represent moves, as shown in Fig. 1- 1-1 below. Figure 1-1-1: Graphical representation of nodes (circles) and moves (lines) of Tower of Hanoi. 3.6 Other Problem-solving Strategies Here are some examples of problem-solving strategies that may equally be adopted to see which works best for you in different situations: 3.6.1 Past Experience Take the time to consider if you have encountered a similar situation to your current problem in the past. This can help draw connections between different events. Ask yourself how you approached the previous situation and adapt those solutions to the problem currently being solved. For example, a company trying to market a new clothing line may consider marketing tactics they have previously used, such as magazine advertisements, influencer campaigns or social media 6 CIT 108 MODULE 1 advertisements. By analysing what tactics have worked in the past, they can create a successful marketing campaign again. 3.6.2 Bring in a facilitator If one is trying to solve a complex problem with a group of other people, bringing in a facilitator can help increase efficiency and mediate collaboration. Having an impartial third party can help a group stay on task, document the process and have a more meaningful conversation. Consider inviting a facilitator to your next group meeting to help generate better solutions. 3.6.3 Develop a decision matrix for evaluation If multiple solutions are developed for a problem, one may need to determine which one is the best. A decision matrix can be an excellent tool to help you approach this task because it allows you to rank potential solutions. Some factors you can analyse when ranking each potential solution are:  Timeliness  Risk  Manageability  Expense  Practicality  Effectiveness After having decided which factors to include, use them to rank each potential solution by assigning a weighted value of 0 to 10 in each of these areas. For example, one solution may receive a score of 10 in the timeliness factor because it meets all the requirements, while another solution may only receive a seven. Having ranked each of the potential solutions based on these factors, add up the total number of points each solution received. The solution with the highest number of points should meet the most important criteria. 3.6.4 Ask your peers for help Getting opinions from peers can expose new perspectives and unique solutions. Friends, families or colleagues may have different experiences, ideas and skills that may contribute to finding the best solution to a problem. Consider asking a diverse range of colleagues or peers to share what they would do if they were in your situation. Even if you don't end up taking one of their suggestions, the conversation may help you process your ideas and arrive at a new solution. 7 CIT 108 PROBLEM SOLVING STRATEGIES 3.6.5 Step away from the problem Finally, if the problem being worked on does not need an immediate solution, consider stepping away from it for a short period of time. You can do this literally by taking a walk to help clear your mind or figuratively by setting the problem aside for a few days until you are ready to approach it again. Allowing yourself time to rest, exercise and take care of your own well-being can make solving the problem easier when you come back to it because you may feel energised and focused. 4.0 CONCLUSION Problem-solving is not a flawless process. There are a number of different obstacles that can interfere with the ability to solve a problem quickly and efficiently. These include functional fixedness, irrelevant information, and assumptions. When dealing with a problem, people often make assumptions about the constraints and obstacles that prevent certain solutions. Functional fixedness is the tendency to view problems only in their customary manner. It prevents people from fully seeing all of the different options that might be available to find a solution. It is important to distinguish between information that is relevant to the issue and irrelevant data that can lead to faulty solutions. When a problem is very complex, the easier it is to focus on misleading or irrelevant information. Mental set makes people to only want to use solutions that have worked in the past rather than looking for alternative ideas. It can often work as a heuristic, making it a useful problem-solving tool. However, it can also lead to inflexibility, making it more difficult to find effective solutions. 5.0 SUMMARY In this unit you learnt that:  Problem-solving strategies which may include multiple steps in order to proffer solution to business problem or industrial challenges.  Effective problem-solving requires you to identify the problem, select the right process to approach it and follow a plan tailored to the specific issue you are trying to solve  Understanding the strategies of proffering solutions to problem through trial and error, algorithm, heuristic and means-ends analysis. 8 CIT 108 MODULE 1  Applying Tower of Hanoi to solve strategy which involves choosing and analysing an action at a series of smaller steps to move closer to the goal 6.0 SELF ASSESSMENT EXERCISE 1. Identify differences between ill-defined problem and well- defined problems 2. Explain how the following methods for solving algorithmic problem: introspection, simulation, computer modelling, and experimentation. 3. Describe how the following methods: Trial and error, Algorithm, Heuristic and Means-ends analysis can be applied in proffering solution to problems 4. Use a diagram to describe the application of Tower of Hanoi in choosing and analysing an action at a series of smaller steps to move closer to the goal 5. State the factors to consider when developing a decision matrix for evaluation 7.0 REFERENCES / FURTHER READINGS Mueller, J., Beckett, D., Hennessey, E., & Shodiev, H. (2017). Assessing computational thinking across the curriculum. In Emerging research, practice, and policy on computational thinking (pp. 251-267). Springer, Cham. Saygılı, S. (2017). Examining the problem solving skills and the strategies used by high school students in solving non-routine problems. E-International Journal of Educational Research, 8(2), 91-114. Spielman, R. M., Dumper, K., Jenkins, W., Lacombe, A., Lovett, M., & Perlmutter, M. (2021). Problem Solving. Psychology-H5P Edition. Tambunan, H. (2019). The Effectiveness of the Problem Solving Strategy and the Scientific Approach to Students' Mathematical Capabilities in High Order Thinking Skills. International Electronic Journal of Mathematics Education, 14(2), 293-302. Yağcı, M. (2019). A valid and reliable tool for examining computational thinking skills. Education and Information Technologies, 24(1), 929-951. Zhao, N., Teng, X., Li, W., Li, Y., Wang, S., Wen, H., & Yi, M. (2019). A path model for metacognition and its relation to problem-solving 9 CIT 108 PROBLEM SOLVING STRATEGIES strategies and achievement for different tasks. ZDM, 51(4), 641- 653. 10 CIT 108 MODULE 1 UNIT 2 THE PROBLEM SOLVING PROCESS 1.0 Introduction 2.0 Intended Learning Outcome 3.0 Main Content 3.1 Computer as a model of computation 3.2 Understanding the Problem 3.3 Formulating a Model 3.4 Developing an Algorithm 3.5 Writing the Program 3.6 Testing the Program 3.7 Evaluating the Solution 4.0 Conclusion 5.0 Summary 6.0 Self-Assessment Exercise 7.0 References/Further Reading 1.0 INTRODUCTION Regardless of the area of study, computer science is all about solving problems with computers. Hence, it is important to first understand the computer’s information processing model. The problems that we want to solve can come from any real-world problem or perhaps even from the abstract world. We need to have a standard systematic approach to solving problems. The model shown in Fig. 1-2-1 below assumes a single CPU (Central Processing Unit). Many computers today have multiple CPUs, so it can be imagined the above model being duplicated multiple times within the computer. 11  CIT 108 PROBLEM SOLVING STRATEGIES Input devices Storage/Network devices Figure 1-2-1: Simplified Model of a Uniprocessor Computer A typical single CPU computer processes information as shown in the diagram. Problems are solved using a computer by obtaining some kind of user input (e.g., keyboard/mouse information or game control movements), then processing the input and producing some kind of output (e.g., images, text, sound). Sometimes the incoming and outgoing data may be in the form of hard drives or network devices. 12 CIT 108 MODULE 1 2.0 INTENDED LEARNING OUTCOME At the end of this unit, students should be able to:  Understand the computer as a model of computation  Explain the problem solving process in detail  Apply the problem solving paradigm to routine elementary problems 3.0 MAIN CONTENT 3.1 Computer as a model of computation In regards to problem solving, we will apply the model in Fig. 2-1 and assume that we are given some kind of input information that we need to work with in order to produce some desired output as solution. However, the above model is quite simplified. For larger and more complex problems, we need to iterate (i.e., repeat) the input/process/output stages multiple times in sequence, producing intermediate results along the way that solve part of our problem, but not necessarily the whole problem. For simple computations, the above model is sufficient. Since it is the “problem solving” part of the process that is the main focus in this unit, more attention will be devoted to this. Among the many definitions for “problem solving”, the following will be adopted in this unit: Definition 1-2-1: Problem Solving is the sequential process of analysing information related to a given situation and generating appropriate response options. In solving a problem, there are some well-defined steps to be followed. For example, consider how the input/process/output works on a simple problem: Example: Calculate the average grade for all students in a class. 1. Input: get all the grades … possibly by typing them in via the keyboard or by reading them from a USB flash drive or hard disk. 2. Process: add them all up and compute the average grade. 3. Output: output the answer to either the monitor, to the printer, to the USB flash drive or hard disk … or a combination of any of these devices. 13 CIT 108 PROBLEM SOLVING STRATEGIES It is noted that the problem is easily solved by simply getting the input, computing something and producing the output. We now examine the steps to problem solving within the context of the above example. 3.2 Understand the Problem It sounds strange, but the first step to solving any problem is to make sure that one understands the problem about to be solved. One needs to know: What input data/information is available?  What does the data/information represent?  In what format is the data/information?  What is missing in the data provided?  Does the person solving the problem have everything needed?  What output information needs to be produced?  In what format should the result be: text, picture, graph?  What are the other requirements needed for computation? In the example given above, it is understood that the input is a bunch of grades. But we need to understand the format of the grades. Each grade might be a number from 0 to 100 or it may be a letter grade from A to F. If it is a number, the grade might be a whole integer like 73 or it may be a real number like 73.42. We need to understand the format of the grades in order to solve the problem. We also need to consider missing grades. What if we do not have the grade for every student: for instance, some were away during the test? Should we be able to include that person in our average (i.e., they received 0) or ignore them when computing the average? We also need to understand what the output should be. Again, there is a formatting issue. Should the output be a whole or real number or a letter grade? Do we want to display a pie chart with the average grade? The choice is ours. Finally, one needs to understand the kind of processing that must be performed on the data. This leads to the next step. 3.3 Formulating a Model The next step is to formulate a model for the problem. A model (or formula) is thus needed for computing the average of a bunch of numbers. If there is no such “formula”, one must be developed. In order to come up with a model, we need to fully understand the information available to us. Assuming that the input data is a bunch of integers or 14 CIT 108 MODULE 1 real numbers 𝑥1 , 𝑥2 , ⋯ , 𝑥𝑛 representing a grade percentage, the following computational model may apply: 𝐴𝑣𝑒𝑟𝑎𝑔𝑒1 = (𝑥1 + 𝑥2 + 𝑥3 + ⋯ + 𝑥𝑛 )/𝑛 where the result will be a number from 0 to 100. That is very straight forward, assuming that the formula for computing the average of a bunch of numbers is known. However, this approach will not work if the input data is a set of letter grades like B-, C, A+, F, D-, etc., because addition and division cannot be performed on the letters. This problem solving step must figure out a way to produce an average from such letters. Thinking is required. After some thought, we may decide to assign an integer number to the incoming letters as follows: 𝐴+ = 12 𝐵+ = 9 𝐶+ = 6 𝐷+ = 3 𝐴 = 11 𝐵 =8 𝐶 =5 𝐷 =2 𝐹=0 𝐴− = 10 𝐵− = 7 𝐶− = 4 𝐷− = 1 If it is assumed that these newly assigned grade numbers are 𝑦1 , 𝑦2 , ⋯ , 𝑦𝑛 , then the following computational model may be used: 𝐴𝑣𝑒𝑟𝑎𝑔𝑒2 = (𝑦1 + 𝑦2 + 𝑦3 + ⋯ + 𝑦𝑛 )/𝑛 where the result will be a number from 0 to 12. As for the output, if it is to be represented as a percentage, then 𝐴𝑣𝑒𝑟𝑎𝑔𝑒1 can either be used directly or one may use (𝐴𝑣𝑒𝑟𝑎𝑔𝑒2/12), depending on the input that we had originally. If a letter grade is preferred as output, then one may need to use (𝐴𝑣𝑒𝑟𝑎𝑔𝑒1/100 ∗ 12) or (𝐴𝑣𝑒𝑟𝑎𝑔𝑒1 ∗ 0.12) or 𝐴𝑣𝑒𝑟𝑎𝑔𝑒2 and then map that to some kind of “lookup table” that allows one to look up a grade letter according to a number from 0 to 12. The main point to understand in this step is that it is all about figuring out how to make use of the available data to compute an answer. 3.4 Develop an Algorithm Having understood the problem and formulated a model, it is time to come up with a precise plan of what the computer is expected to do. Definition 1-2-2: Algorithm is a precise sequence of instructions for solving a problem. 15 CIT 108 PROBLEM SOLVING STRATEGIES Some of the more complex algorithms may be considered randomized algorithms or non-deterministic algorithms where the instructions are not necessarily in sequence and may not even have a finite number of instructions. However, the above definition will apply for all algorithms that will be discussed in this course. To develop an algorithm, the instructions must be represented in a way that is understandable to a person who is trying to figure out the steps involved. Two commonly used representations for an algorithm is by using (1) pseudocode, or (2) flowcharts. Consider the following example for solving the problem of a broken lamp. First is the example in a flowchart, and then in pseudocode, as presented in Fig. 1-2-2 and Fig. 1- 2-3 respectively. Lamp not working Lamp No plugged Plug in Lamp in? Yes Bulb Yes burned Replace Bulb out? No Buy new Lamp Figure 1-2-2: Flowchart for a broken Lamp Pseudocode 1. IF lamp works, go to step 7. 2. Check if lamp is plugged in. 3. IF not plugged in, plug in lamp. 4. Check if bulb is burnt out. 5. IF blub is burnt, replace bulb. 6. IF lamp doesn’t work buy new lamp. 7. Quit... problem is solved. Figure 1-2-3: Flowchart for a broken Lamp 16 CIT 108 MODULE 1 Note: pseudocode is a simple and concise sequence of English-like instructions to solve a problem. Pseudocode is often used as a way of describing a computer program to someone who doesn’t understand how to program a computer. Although flowcharts can be visually appealing, pseudocode is often the preferred choice for algorithm development because:  It can be difficult to draw a flowchart neatly, especially when mistakes are made.  Pseudocode fits more easily on a page of paper.  Pseudocode can be written in a way that is very close to real program code, making it easier later to write the program.  Pseudocode takes less time to write than drawing a flowchart. Pseudocode will vary according to whoever writes it. That is, one person’s pseudocode is often quite different from that of another person. However, there are some common control structures (i.e., features) that appear whenever pseudocode is written. These features are shown along with some examples:  Sequence: Listing instructions step-by-step in order (often numbered) 1. Make sure switch is turned on 2. Check if lamp is plugged in 3. Check if bulb is burned out 4. …… If lamp is not plugged in then plug it in If bulb is burned out then replace bulb Else buy new lamp  Condition: Making a decision and doing one thing or something else depending on the outcome of the decision.  Repetition: repeating something a fixed number of times or until some condition occurs 17 CIT 108 PROBLEM SOLVING STRATEGIES get a new light bulb Repeat put it in the lamp Until lamp works or no more bulbs left Repeat 3 times Unplug lamp Plug into different socket ….. Storage: storing information for use in instructions further down the list x ← a new bulb count ← 8 Transfer of Control: being able to go to a specific step when needed If bulb works then goto step 7 Note:  The bold in the above examples highlights the specific control structure.  For the condition and repetition structures, the portion of the pseudocode that is part of the condition or the repeat loop are indented a bit in order to make it clear that these kinds of inner steps that belong to that structure. Braces ({ }) may also be used to indicate what is in or out of a control structure as shown below.If (bulb is burned out) then { Replace bulb } Else { Buy a new bulb } Repeat { Get a new light bulb Put it in the lamp } until lamp works or no more bulbs left Repeat 3 times { Unplug lamp Plug into different socket } The point is that there are a variety of ways to write pseudocode. The important thing to remember is that the algorithm should be clearly explained with no ambiguity as to what order the steps are performed in. Whether using a flow chart of pseudocode, an algorithm should be tested by manually going through the steps in mentally to make sure a step or a special situation is not missed out. Often, a flaw will be found in one’s algorithm because a special situation that could arise was 18 CIT 108 MODULE 1 missed out. Only when one is convinced that the algorithm will solve the problem, should the next step be attempted. Consider the previous example of finding the average of a set of 𝑛 grades stored in a file. What would the pseudocode look like? Here is an example of what it might look like if we had the example of 𝑛 numeric grades 𝑥1 , 𝑥2 , ⋯ , 𝑥𝑛 that were loaded from a file: Algorithm: DisplayGrades 1. set the sum of the grade values to 0. 2. load all grades 𝑥1 , 𝑥2 , ⋯ , 𝑥𝑛 from file. 3. repeat n times { 4. get grade xi 5. add xi to the sum 6. compute the average to be sum / n. 7. print the average It would be wise to run through the above algorithm with a real set of numbers. Each time an algorithm is tested with a fixed set of input data, this is known as a test case. Many test cases can be created. Here are some to try: 𝑛 = 5, 𝑥1 = 92, 𝑥2 = 37, 𝑥3 = 43, 𝑥4 = 12, 𝑥5 = 71… result should be 51 𝑛 = 3, 𝑥1 = 1, 𝑥2 = 1, 𝑥3 = 1……………………….… result should be 1 𝑛 = 0…………………………………………………… result should be 0 3.5 Writing the Program Writing a program is often called "coding" or “implementing an algorithm”. So the code (or source code) is actually the program itself. Without much of an explanation, below is a program (written in processing) that implements the given algorithm for finding the average of a set of grades. Note that the code looks quite similar in structure, however, the processing code is less readable and seems somewhat more mathematical: 19  CIT 108 PROBLEM SOLVING STRATEGIES Pseudocode Processing code (Program) 1. set the sum of the grade values to 0. int sum = 0; 2. load all grades 𝑥1 , 𝑥2 , ⋯ , 𝑥𝑛 from file. byte[] x = loadBytes("numbers"); 3. repeat 𝑛 times { for (int i=0; i