Computer Problem-Solving Strategies PDF

# chapter 7-Problem solvi x ## Developing an Algorithm - Two methodologies used to develop computer solutions to a problem - **Top-down design** focuses on the tasks to be done - Object-oriented design focuses on the data involved in the solution (We will discuss this design in C...

# chapter 7-Problem solvi x ## Developing an Algorithm - Two methodologies used to develop computer solutions to a problem - **Top-down design** focuses on the tasks to be done - Object-oriented design focuses on the data involved in the solution (We will discuss this design in Ch. 9) ## Algorithms - **Algorithm** A set of unambiguous instructions for solving a problem or subproblem in a finite amount of time using a finite amount of data - **Abstract Step** An algorithmic step containing unspecified details - **Concrete Step** An algorithm step in which all details are specified ## Phase Interactions - A diagram showing the *Analysis and Specification*, *Algorithm Development*, *Implementation*, and *Maintenance* phases of problem solving that loop back to each other. The flow of the program is not linear. The diagram questions whether we should add another arrow because the problem might be revised. ## Computer Problem-Solving - *Analysis and Specification Phase* Analyze, Specification - *Algorithm Development Phase* Develop algorithm, Test algorithm - *Implementation Phase* Code algorithm, Test algorithm - *Maintenance Phase* Use, Maintain ## Strategies - **Divide and Conquer!** Break up a large problem into smaller units and solve each smaller problem - Applies the concept of abstraction - The divide-and-conquer approach can be applied over and over again until each subtask is manageable. ## Problem Solving - **How to Solve It: A New Aspect of Mathematical Method by George Polya** - "How to solve it list" written within the context of mathematical problems - But list is quite general. - We can use it to solve computer-related problems! - **Problem solving** The act of finding a solution to a perplexing, distressing, vexing, or unsettled question - **How do you define problem solving?** ## Strategies - **Ask questions!** - What do I know about the problem? - What is the information that I have to process in order to find the solution? - What does the solution look like? - What sort of special cases exist? - How will I recognize that I have found the solution? ## Binary Search - A visual representation of the data stored and accessed in a binary search. Each data point is stored in a box and an arrow points to the middle of the data and the formula: *middle=(f+L)/2* - The text for the binary search algorithm is as follows: - Set first to 0 - Set last to length-1 - Set found to FALSE - WHILE (first <= last AND NOT found) - Set middle to (first + last)/2 - IF (item equals data[middle])) - Set found to TRUE - ELSE - IF (item < data[middle]) - Set last to middle - 1 - ELSE - Set first to middle + 1 - RETURN found ## Sequential Search - **Sequential search** - Search begins at the beginning of the list and continues until the item is found or the entire list has been searched - **Binary search** (list must be sorted) - Search begins at the middle and finds the item or eliminates half of the unexamined items; process is repeated on the half where the item might be ## A Sorted Array - A visual representation of a sorted array showing the length, list, and data stored in each box. - A sorted array of integers. - Data [0] - [MAX_LENGTH-1] - The text for the algorithm is as follows: - Set found to TRUE if searchltem is there - Set index to 0 - Set found to FALSE - WHILE (index < length AND NOT found) - IF (data[index] equals searchlten) - Set found to TRUE - ELSE IF (data[index] > searchItem) - Set index to length - ELSE - Set index to index + 1 - The text for the rest of the algorithm is as follows: - Read in array of values - Write "Enter value for which to search" - Read searchItem - Set found to TRUE if searchltem is there - IF (found) - Write "Item is found" - ELSE - Write "Item is not found" ## Sorted Arrays - The values stored in an array have unique keys of a type for which the relational operators are defined. - Sorting rearranges the elements into either ascending or descending order within the array. - A sorted array is one in which the elements are in order. ## Sequential Search Algorithm - Set Position to 0 - Set found to FALSE - WHILE (position < length AND NOT found) - IF (numbers [position] equals searchitem) - Set Found to TRUE - ELSE - Set position to position + 1 ## Sequential Search of an Unsorted Array - A sequential search examines each item in turn and compares it to the one we are searching. - If it matches, we have found the item. If not, we look at the next item in the array. - We stop either when we have found the item or when we have looked at all the items and not found a match - Thus, a loop with two ending conditions des ## Composite Data Types - Fill an array numbers with limit values - integer data[20] - Write "How many values?" - Read length - Set index to 0 - WHILE (index < length) - Read data[index] - Set index to index + 1 ## An Unsorted Array - A visual representation of an unsorted array showing the length, list, and data stored in each box. - data[0]...data[length-1] is of interest - Data [0] - [MAX_LENGTH-1] ## Arrays - As data is being read into an array, a counter is updated so that we always know how many data items were stored. - If the array is called list, that with which we are working is from list[0] to list [length-1] - The image shows numbers[0] and numbers[4] boxes. - Insert 7.5 ## Composite Data Types - The image shows a box labeled *Employee*, with fields for *name*, *age*, and *hourly/Wage*. - The text for the algorithm is as follows: - Employee employee - // Declare and Employee variable - Set employee.name to "Frank Jones" - Set employee.age to 32 - Set employee.hourlyWage to 27.50 ## Composite Data Types - **Records** A named heterogeneous collection of items in which individual items are accessed by name. For example, we could bundle name, age and hourly wage items into a record named Employee. - **Arrays** A named homogeneous collection of items in which an individual item is accessed by its position (index) within the collection. ## Looping Statements - **An event-controlled loop** - Set sum to 0 - Set allPositive to true - WHILE (allPositive) - Read number - IF (number > 0) - Set sum to sum + number - ELSE - Set allPositive to false - Write "Sum is " + sum - Why is it called an event-conrolled loop? - What is the event? ## Looping Statements - **A count-controlled loop** - Set sum to 0 - Set count to 1 - While (count <= limit) - Read number - Set sum to sum + number - Increment count - Write "Sum is " + sum - Why is it called a count-controlled loop? - The image shows a flowchart where the loop continues based on the boolean expression. ## Algorithm with Selection - **Determine Dress** - IF (temperature > 90) - Write "Texas weather: wear shorts" - ELSE IF (temperature > 70) - Write "Ideal weather: short sleeves are fine" - ELSE IF (temperature > 50) - Write "A little chilly: wear a light jacket" - ELSE IF (temperature > 32) - Write "Philadelphia weather: wear a heavy coat" - ELSE - .Write "Stay inside" ## Algorithm with Selection - **Problem:** Write the appropriate dress for a given temperature. - Write "Enter temperature" - Read temperature - Determine Dress - Which statements are concrete? - Which statements are abstract? ## Selection Statements - A diagram of the Selection Statement with a boolean expression in the middle. If it evaluates to *true*, the flow continues to the right for the remainder of the statement. If it evaluates to *false*, the flow is reversed. ## Top-Down Design - A diagram showing that the top (main module) feeds into the bottom (particular) via levels 0, 1, 2, and 3. - The process continues for as many levels as it takes to make every step concrete. - The name of (sub)problem-at one level becomes a module at the next lower level. ## Summary of Methodology - **Analyze the Problem** - Understand the problem!! - Develop a plan of attack - **List the Main Tasks** (becomes Main Module) - Restate problem as a list of tasks (modules) - Give each task a name - **Write the Remaining Modules** - Restate each abstract module as a list of tasks - Give each task a name - **Re-sequence and Revise as Necessary** - Process ends when all steps (modules) are concrete