Transcription
Chapter 7Ch.7 Problem Solvingand Algorithms
Problem SolvingHow to Solve It: A New Aspect of MathematicalMethod by George Polya, 1945"How to solve it list" written within the contextof mathematical problemsBut the list is quite generalWe can use it to solve computerrelated problems!2
1. Understand the problem– What are the hypotheses? Data? Unknowns?2. Devise a plan– Can we find a related problem? A sub-problem?– Can we strengthen or relax the hypotheses toobtain an easier problem?3. Carry out the plan4. Look back– Check result– Find shortcuts and alternate solutions– Generalize to related problems3
StrategiesAsk questions!– What do I know about the problem?– What is the information that I have to process inorder the find the solution?– What does the solution look like?– What sort of special cases exist?– How will I recognize that I have foundthe solution?4
StrategiesNever reinvent the wheel!Similar problems come up again and again indifferent guisesA good programmer recognizes a task or subtaskthat has been solved before and plugs in thesolutionCan you think of two similar problems wesolved in Python?5
StrategiesDivide and Conquer!Break up a large problem into smaller subproblems and solve each separately– Applies the concept of abstraction– The divide-and-conquer approach can be appliedover and over again until each subtask ismanageable6
Polya’s 4 steps can be applied toComputer Problem-SolvingAnalysis and Specification PhaseAnalyzeSpecificationAlgorithm Development PhaseDevelop algorithmTest algorithmImplementation PhaseCode algorithmTest algorithmMaintenance PhaseUseMaintain7
QUIZ: Match the steps in Polya’s methodto the ones in the computer method forproblem solvingDevise a planAnalysis and SpecificationLook backImplementationUnderstandAlgorithm DevelopmentCarry out the planMaintenance8
Phase Interactions9
AlgorithmsAlgorithmA set of unambiguous instructions for solving aproblem or subproblem in a finite amount of timeusing a finite amount of dataAbstract StepAn algorithmic step containing unspecified detailsConcrete StepAn algorithm step in which all details are specified10
7.2 Algorithms with simple variablesVariable a means of storing intermediateresults from one task to the next.At the hardware level, a simple variable is justone or several adjacent Bytes in the computermemory.Q: How many Bytes does a simple variable havein PEP/8?11
Algorithms with SelectionStatements (a.k.a. decision or if)Flow of control of if statement12
Algorithm with SelectionProblem: Write the appropriate dress for a giventemperature.Algorithm Determine Dress v.1Write "Enter temperature"Read temperatureDetermine DressWhich statements are concrete?Which statements are abstract?Computer language isPythonfrom now on!13
Algorithm Determine Dress v.2Write “Enter temperature”Read temperatureIF (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”ELSEWrite “Stay inside”Is this concrete enough forimplementation in Python?14
Algorithms with Loops (a.k.a.repetition)Flow of control of while statement15
QUIZ: In Ch.6 we distinguished between loopsthat can execute 0 times and loops that executeat least 1 time.Which type is this?16
Event-controlled LoopsThey are the most general type of loopsSet sum to 0Set allPositive to trueWHILE (allPositive)Read numberIF (number 0)Set sum to sum numberELSESet allPositive to falseWrite "Sum is " sum17
Counter-controlled LoopsThey are a particular case of event-controlledloops: the event is that a counter variable hasreached a predetermined limitSet sum to 0Set limit to 42Set count to 1While (count limit)Read numberSet sum to sum numberIncrement countWrite "Sum is " sum18
Important aplication of looping:Successive approximationalgorithmsAlgorithm Calculate Square Root v.1Read in squareCalculate the square rootWrite out square and the square rootWhich steps are abstract and which concrete?19
Algorithm Calculate Square Root v.2A more appropriatename for guesswould beapproximationSet epsilon to 1WHILE (epsilon 0.001)Calculate new guessSet epsilon to abs(square - guess * guess)In Python usemath.fabs( )Which steps are abstract and which concrete?20
Algorithm Calculate Square Root - Refinements in v.2What’s the mathematical formula for the new approximation?Set newGuess to(guess (square/guess)) / 2.0How do we get the loop started?Set guess to square/4Set epsilon to 121
Algorithm Calculate Square Root v.3Read in squareSet guess to square/4Set epsilon to 1WHILE (epsilon 0.001)Set guess to (guess (square/guess)) / 2.0Set epsilon to abs(square - guess * guess)Write out square and guessWhich steps are abstract and which concrete?22
Extra-credit:Implement algorithm Calculate square root inPython, using the while command.Check the result using math.sqrt().Due next time (Mon) at the beginning of class.The full pseudocode is on pp.208-9 of our text.23
Read Sections 7.1 and 7.2To do in notebook for next time:End-of-chapter questions1-10 and 16 – 2424
Solutions for Exam 225
7.3 Composite Data TypesAre these the lists fromPython? Why not?RecordsA named heterogeneous collection of items in whichindividual items are accessed by name. For example,we could bundle name, age and hourly wage items intoa record named EmployeePython strings are arrays ofcharacters!ArraysA named homogeneous collection of items in which anindividual item is accessed by its position (index) withinthe collection26
Composite Data TypesLists (will be covered in next chapter)A named heterogeneous collection of items in whichindividual items are accessed by position (index).We have them in Python, e.g. myList [“dog”, 42, 51.375, [1,2]] myList[1]4227
Composite Data Types - RecordsEmployeenameagehourly/WageAlgorithm to store values into the fields of record:Employee employee// Declare an Employee variableSet employee.name to “Frank Jones”Set employee.age to 32Set employee.hourlyWage to 27.5028
Composite Data Types - Arraysnumbersnumbers[0]numbers[4]29
Some items in an array may beunused at a given timenumbers?firstlast?30
Useful Algorithms on Arrays Initializing all itemsPrinting all itemsSearching for an itemSorting the array31
Initializing arraysFill an array numbers with length valuesthat are being input from the keyboardinteger data[20]Write “How many values?”Read lengthSet index to 0WHILE (index length)Read data[index]Set index to index 132EoL
QUIZModify this pseudocode to print the valuesafter initializing them.integer data[20]Write “How many values?”Read lengthSet index to 0WHILE (index length)Read data[index]Set index to index 133
An Unsorted Arraydata34
Sorted ArraysReality check: In a real-lifeproblem it’s very commonto encounter repeated keys! The values stored in an array have unique keysof a type for which the relational operators aredefined. Sorting rearranges the elements into eitherascending or descending order within the array.35
A Sorted Arraydata36
8.4 Search algorithms37
Sequential Search inUnsorted ArrayA sequential search examines each item in turn andcompares it to the one we are searching.If it matches, we have found the item. If not, we look atthe next item in the array.We stop either when we have found the item or whenwe have looked at all the items and not found amatch.Thus, we have a loop with two ending conditions.38
The array’s name is numbersThe value we’re searching for is stored in searchItemSet position to 0Set found to FALSEWHILE (position length AND NOT found )IF (numbers[position] equals searchItem)Set found to TRUEELSESet position to position 139
QUIZ: When the loop exits, what do we need to do?Set position to 0Set found to FALSEWHILE (position length AND NOT found )IF (numbers[position] equals searchItem)Set found to TRUEELSESet position to position 140
Sequential Search in Sorted ArrayIdea:If items in an array are sorted, we can stoplooking when we pass the place where theitem would be it were present in the arrayIs this better?41
Sequential Search in Sorted ArrayRead in array of valuesWrite “Enter value for which to search”Read searchItemSet found to TRUE if searchItem is thereIF (found)Write “Item is found”ELSEWrite “Item is not found”Which steps are abstract and which concrete?42
Sequential Search in Sorted ArrayThis was explained before –see array initializationRead in array of valuesWrite “Enter value for which to search”Read searchItemSet found to TRUE if searchItem is thereIF (found)Write “Item is found”ELSEWrite “Item is not found”43
Sequential Search in Sorted ArraySet found to TRUE if searchItem is thereSet index to 0Set found to FALSEWHILE (index length AND NOT found)IF (data[index] equals searchItem)Set found to TRUEELSE IF (data[index] searchItem)Set index to lengthELSESet index to index 144
QUIZ:End-of-chapter question 6645
Binary Search in Sorted ArraySearch begins at the middle and finds the itemor eliminates half of the unexamined items; theprocess is then repeated on the half where theitem might be24 30 31 42 44 90 92 94 9946
Binary Search AlgorithmSet first to 0Set last to length-1Set found to FALSEWHILE (first last AND NOT found)Set middle to (first last)/ 2IF (item equals data[middle]))Set found to TRUEELSEIF (item data[middle])Set last to middle – 1ELSESet first to middle 1RETURN foundIntegerDivision!47
Binary Search exampleratFigure 7.10 Trace of the binary search48
QUIZ Binary SearchSearching for deerratFigure 7.10 Trace of the binary search49
Binary Search ConclusionBinary search algorithms have average and worst-casecost of O(log2N), but the array must be sorted.50
Search ConclusionSequential search: O(N), sorted or unsortedBinary search:O(log2N) , only sorted.51
8.5 Sorting algorithms52
SortingSortingArranging items in a collection so that there is anordering on one (or more) of the fields in the itemsSort KeyThe field (or fields) on which the ordering is basedSorting algorithmsAlgorithms that order the items in the collection basedon the sort keyWhy is sorting important?53
Selection SortGiven a list of names, put them in alphabetical order– Find the name that comes first in the alphabet,and write it on a second sheet of paper– Cross out the name off the original list– Continue this cycle until all the names on the original listhave been crossed out and written onto the second list, atwhich point the second list contains the same items but insorted order54
Selection SortA slight adjustment to this manual approachdoes away with the need to duplicate space– As you cross a name off the original list, a freespace opens up– Instead of writing the value found on a second list,exchange it with the value currently in theposition where the crossed-off item should go55
Selection SortFigure 7.11 Example of a selection sort (sorted elements are shaded)56
QUIZ Selection SortShow the swapped elements with arrows.Show the sorted elements with shading.2410111235201257
Selection SortSelection SortSet firstUnsorted to 0WHILE (not sorted yet)Find smallest unsorted itemSwap firstUnsorted item with the smallestSet firstUnsorted to firstUnsorted 1Not sorted yetcurrent length – 158
Selection SortFind smallest unsorted itemSet indexOfSmallest to firstUnsortedSet index to firstUnsorted 1WHILE (index length – 1)IF (data[index] data[indexOfSmallest])Set indexOfSmallest to indexSet index to index 1Set index to indexOfSmallest59
Selection SortSwap firstUnsorted with smallestSet tempItem to data[firstUnsorted]Set data[firstUnsorted] to data[indexOfSmallest]Set data[indexOfSmallest] to tempItem60
To do in notebook for next time:End-of-chapter questions 30, 31, 32, 6761
Quiz1. What are the 4 fundamental types ofalgorithms used to manipulate arrays?2. What control structure is normally used toaccess the elements of an array?3. Which is faster, sequential search or binarysearch?– How much faster? (use “Big-Oh” notation)4. What is the downside of binary search?62
SKIP Bubble Sort and Insertion Sort63
7.6 Recursive AlgorithmsCan we do sorting with less thanO(N2)comparisons?Yes, but it involves a new concept (recursion) and a new control structure! (subprogram)64
Subprogram StatementsWe can give a section of code a name and usethat name as a statement in another part of theprogramWhen the name is encountered, the processingin the other part of the program halts while thenamed code is executedWhen execution is finished, the first part of theprogram resumes executionThat section of code is called a subprogram65
Subprogram StatementsFigure 7.14 Subprogram flow of control66
We already used subprograms inPython! but we called them FunctionsDo you rememberwhat each of themdoes?– int() float() ord() chr() str() open()etc. Methods– list.append() string.upper() file.close() etc.67
Subprogram StatementsWhat if the subprogram needs data from the callingunit? This data is called input.ParametersIdentifiers listed in parentheses beside the subprogramdeclaration; sometimes called formal parametersArgumentsIdentifiers listed in parentheses on the subprogramcall; sometimes called actual parameters68
Parameters and arguments inPythondef printer(a, b):print a, 'and', bx, y 1, 2printer(x, y)69
What if the subprogram needs to give data back to thecalling unit? This data is called output.Void subprogramsThey do not return a value, just perform certain actions print(“Enter a positive integer”) printer(3, 4)Value-returning subprograms a input(“Enter a positive integer”)The keyword RETURN is used in many programming languages70
Value-returning function in Pythondef sum(a, b):return a bx, y 1, 2print sum(x, y)71
QUIZdef sum(a, b):return a bWrite a Python function that multiplies three numbers72
Value-returning and void SubprogramsEoL73
Subprogram StatementsSubprograms are very important tools for abstraction.Other popular names for subprograms: sub subroutine function procedure module method74
RecursionRecursionThe ability of a subprogram to call itselfBase caseThe case to which we have an answerGeneral caseThe case that expresses the solution in terms of a callto itself with a smaller version of the problem75
RecursionThe factorial of a positive integer is defined as theinteger times the product of all the integers between itselfand 0:N! 1 2 3 NBut an alternate resursive definition is possible:N! N (N 1)!Base caseFact(0) 1General CaseFact(N) N Fact(N-1)(0! is 1)(for N 1)76
QUIZN! N * (N 1)!Base caseFacto(0) 1General CaseFact(N) N * Fact(N-1)(0! is 1)(for N 1)Calculate:0! 1! 2! 5! 77
Recursive Factorial algorithmWrite “Enter n”Read nSet result to Factorial(n)Write result “ is the factorial of “ nFactorial(n)IF (n equals 0)RETURN 1ELSERETURN n * Factorial(n-1)78EoL
Recursive Binary SearchBinarySearch (first, last)IF (first last)RETURN FALSEELSESet middle to (first last)/ 2IF (item equals data[middle])RETURN TRUEELSEIF (item data[middle])BinarySearch (first, middle – 1)ELSEBinarySearch (middle 1, last)79
Quicksort algorithmImagine having to sort a stack of exams alphabeticallyby the students’ names.To avoid the “wild swings” we’ve seen in Selection Sort,we’re going to split the stack into two smaller stacks,such that no exam will have to cross from one stackto another in the future.How to split? In the case of names, we know that, onaverage, half of the names will start with A L andhalf with M Z.80
QuicksortOrdering a listusing the Quicksort algorithmIt is easier to sort a smallernumber of items: Sort A F,G L, M R, and S Z andA Z is sorted81
Quicksort algorithmIn the general case, when we don’t know much aboutthe nature of data elements, the array is divided at asplitting value, splitVal, which we choose at randomfrom the array itself.The process continues recursively until the small stacksdo not need to be divided further (the base case).82
The variables first and last indicate the part ofthe array (sub-stack) that is currently beingprocessedQuicksort(first, last)IF (first last)There is more than one itemSelect splitValSimplest to choose firstSplit (splitVal)We split into the two sub-stacksQuicksort (first, splitPoint - 1)Quicksort (splitPoint 1, last)83
QuicksortInitialarrayAftersplittingSwap splitvalue tobring it atthe splitpoint84
Quicksort – how to split the arraySplit(splitVal)Set left to first 1Set right to lastWHILE (left right)Increment left until data[left] splitVal OR left rightDecrement right until data[right] splitVal OR left rightIF(left right)Swap data[left] and data[right]Set splitPoint to rightSwap data[first] and data[splitPoint]Return splitPoint85
Detailed operation of the split() function86
87
7.7 Important ThreadsInformation HidingThe practice of hiding the details of a module with thegoal of controlling access to itAbstractionA model of a complex system that includes only thedetails essential to the viewerInformation Hiding and Abstraction are two sides ofthe same coin88
Three types of abstractionData abstractionSeparation of the logical view of data fromtheir implementationProcedural abstractionSeparation of the logical view of actions fromtheir implementationControl abstractionSeparation of the logical view of a controlstructure from its implementationUnsigned integers canbe implemented on 8,16, 32, or 64 bits!Subprogramsdo this!A for loop is the samein pseudocode, but canhave different syntaxdetails in differentlanguages!89
for loops in Python, C and FORTRANfor i in range(m, n, p):.for (i m; i n; i p){.}10do 10 i m, n-1, p.continue90
Important ThreadsIdentifiersNames given to data and actions, by which– we access the data andRead firstName, Set count to count 1– execute the actionsSplit(splitVal)Giving names to data (variables) and actions(subprograms) is a form of abstraction91
Chapter review questions Describe the computer problem-solving process and relate itto Polya’s How to Solve It list Distinguish between a simple type and a composite type Distinguish between a void subprogram and a value-returningsubprogram Recognize a recursive problem and write a recursive algorithmto solve it Distinguish between an unsorted array and a sorted array Describe the Quicksort algorithm Apply the linear search, binary search, selection sort andQuicksort to an array of items by hand92
Read and take notes:Ethical IssuesOpen-Source Software DevelopmentWhat are the advantages and disadvantagesof open-source software?What does the success of Linux suggestabout the future of open-source software?Should open-source software be licensedandsubject to standard copyright laws?93
Read and take notes: Tony HoareMy wife Jill andI are holdingthe medal Ireceived whenI was knighted.What universitydid I retire fromand where amI working now?94
Who am I?I am amathematician.Why is mypicture in abook aboutcomputerscience?95
Do you know?What writing system did the Rosetta stoneserve as a key to translating?What are some of the adverseconsequences of piggybacking for freeoff someone else’s paid Wi-Fi connection?What, if any, legal privacy protections does ablogger have to resist an employer seeking tofire an anonymous blogging employee?96
Homework for Ch.7Due Friday, April 20End of chapter11 through 1533 through 36636597
Algorithms Algorithm A set of unambiguous instructions for solving a problem or subproblem in a finite amount of time . Python strings are arrays of characters! Composite Data Types Lists (will be covered in next chapter) A named heterogeneous collection of items in whichFile Size: 1MB
