Python Programming: An Introduction To Computer Science

7m ago
17 Views
0 Downloads
4.51 MB
133 Pages
Transcription

Python Programming:An Introduction toComputer ScienceChapter 13Algorithm Design and RecursionPython Programming, 2/e1

Objectivesæ To understand the basic techniques foranalyzing the efficiency of algorithms.æ To know what searching is and understandthe algorithms for linear and binary search.æ To understand the basic principles ofrecursive definitions and functions and beable to write simple recursive functions.Python Programming, 2/eThe University of Western Australia2

Objectivesæ To understand sorting in depth and know the algorithms for selection sortand merge sort.æ To appreciate how the analysis of algorithms can demonstrate that someproblems are intractable and others are unsolvable.Python Programming, 2/eThe University of Western Australia3

Searchingæ Searching is the process of looking for a particular value in a collection.æ For example, a program that maintains a membership list for a club mightneed to look up information for a particular member – this involves somesort of search process.Python Programming, 2/eThe University of Western Australia4

A simple Searching Problemæ Here is the specification of a simple searching function:def search(x, nums):# nums is a list of numbers and x is a number# Returns the position in the list where x occurs# or -1 if x is not in the list.æ Here are some sample interactions: search(4, [3, 1, 4, 2, 5])2 search(7, [3, 1, 4, 2, 5])-1Python Programming, 2/eThe University of Western Australia5

A Simple Searching Problemæ In the first example, the function returns the index where 4 appears in thelist.æ In the second example, the return value -1 indicates that 7 is not in the list.æ Python includes a number of built-in search-related methods!Python Programming, 2/eThe University of Western Australia6

A Simple Searching Problemæ We can test to see if a value appears in a sequence using in.if x in nums:# do somethingæ If we want to know the position of x in a list, the index method can beused. nums [3, 1, 4, 2, 5] nums.index(4)2Python Programming, 2/eThe University of Western Australia7

A Simple Searching Problemæ The only difference between our search function and index is thatindex raises an exception if the target value does not appear in the list.æ We could implement search using index by simply catching the exceptionand returning -1 for that case.Python Programming, 2/eThe University of Western Australia8

A Simple Searching Problemæ def search(x, nums):try:return nums.index(x)except:return -1æ Sure, this will work, but we are really interested in the algorithm used toactually search the list in Python!Python Programming, 2/eThe University of Western Australia9

Strategy 1: Linear Searchæ Pretend you’re the computer, and you weregiven a page full of randomly ordered numbersand were asked whether 13 was in the list.æ How would you do it?æ Would you start at the top of the list, scanningdownward, comparing each number to 13? Ifyou saw it, you could tell me it was in the list. Ifyou had scanned the whole list and not seen it,you could tell me it wasn’t there.Python Programming, 2/eThe University of Western Australia10

Strategy 1: Linear Searchæ This strategy is called a linear search, where you search through the list ofitems one by one until the target value is found.æ def search(x, nums):for i in range(len(nums)):if nums[i] x: # item found, return the index valuereturn ireturn -1# loop finished, item was not in listæ This algorithm wasn’t hard to develop, and works well for modest-sizedlists.Python Programming, 2/eThe University of Western Australia11

Strategy 1: Linear Searchæ The Python in and index operations both implement linear searchingalgorithms.æ If the collection of data is very large, it makes sense to organize the datasomehow so that each data value doesn’t need to be examined.Python Programming, 2/eThe University of Western Australia12

Strategy 1: Linear Searchæ If the data is sorted in ascending order (lowestto highest), we can skip checking some of thedata.æ As soon as a value is encountered that is greaterthan the target value, the linear search can bestopped without looking at the rest of the data.æ On average, this will save us about half thework.Python Programming, 2/eThe University of Western Australia13

Strategy 2: Binary Searchæ If the data is sorted, there is an even bettersearching strategy – one you probably alreadyknow!æ Have you ever played the number guessinggame, where I pick a number between 1 and100 and you try to guess it? Each time youguess, I’ll tell you whether your guess iscorrect, too high, or too low. What strategy doyou use?Python Programming, 2/eThe University of Western Australia14

Strategy 2: Binary Searchæ Young children might simply guess numbers at random.æ Older children may be more systematic, using a linear search of 1, 2, 3, 4, until the value is found.æ Most adults will first guess 50. If told the value is higher, it is in the range51-100. The next logical guess is 75.Python Programming, 2/eThe University of Western Australia15

Strategy 2: Binary Searchæ Each time we guess the middle of the remaining numbers to try to narrowdown the range.æ This strategy is called binary search.æ Binary means two, and at each step we are diving the remaining group ofnumbers into two parts.Python Programming, 2/eThe University of Western Australia16

Strategy 2: Binary Searchæ We can use the same approach in our binarysearch algorithm! We can use two variablesto keep track of the endpoints of the range inthe sorted list where the number could be.æ Since the target could be anywhere in thelist, initially low is set to the first location inthe list, and high is set to the last.Python Programming, 2/eThe University of Western Australia17

Strategy 2: Binary Searchæ The heart of the algorithm is a loop that looks atthe middle element of the range, comparing it tothe value x.æ If x is smaller than the middle item, high ismoved so that the search is confined to thelower half.æ If x is larger than the middle item, low is movedto narrow the search to the upper half.Python Programming, 2/eThe University of Western Australia18

Strategy 2: Binary Searchæ The loop terminates when either x is found There are no more places to look(low high)Python Programming, 2/eThe University of Western Australia19

Strategy 2: Binary Searchdef search(x, nums):low 0high len(nums) - 1while low high:mid (low high)//2item nums[mid]if x item:return midelif x item:high mid - 1else:low mid 1return -1# There is still a range to search# Position of middle item# Found it! Return the index######x is in lower half of rangemove top marker downx is in upper half of rangemove bottom marker upNo range left to search,x is not therePython Programming, 2/eThe University of Western Australia20

Comparing Algorithmsæ Which search algorithm is better, linear orbinary? The linear search is easier to understand andimplement The binary search is more efficient since it doesn’tneed to look at each element in the listæ Intuitively, we might expect the linear search towork better for small lists, and binary search forlonger lists. But how can we be sure?Python Programming, 2/eThe University of Western Australia21

Comparing Algorithmsæ One way to conduct the test would be to codeup the algorithms and try them on varying sizedlists, noting the runtime. Linear search is generally faster for lists of length 10or less There was little difference for lists of 10-1000 Binary search is best for 1000 (for one million listelements, binary search averaged .0003 secondswhile linear search averaged 2.5 second)Python Programming, 2/eThe University of Western Australia22

Comparing Algorithmsæ While interesting, can we guarantee that theseempirical results are not dependent on the typeof computer they were conducted on, theamount of memory in the computer, the speedof the computer, etc.?æ We could abstractly reason about the algorithmsto determine how efficient they are. We canassume that the algorithm with the fewestnumber of “steps” is more efficient.Python Programming, 2/eThe University of Western Australia23

Comparing Algorithmsæ How do we count the number of “steps”?æ Computer scientists attack these problems by analyzing the number of stepsthat an algorithm will take relative to the size or difficulty of the specificproblem instance being solved.Python Programming, 2/eThe University of Western Australia24

Comparing Algorithmsæ For searching, the difficulty is determined by thesize of the collection – it takes more steps tofind a number in a collection of a millionnumbers than it does in a collection of 10numbers.æ How many steps are needed to find a value in alist of size n?æ In particular, what happens as n gets very large?Python Programming, 2/eThe University of Western Australia25

Comparing Algorithmsæ Let’s consider linear search. For a list of 10 items, the most work we might have to dois to look at each item in turn – looping at most 10 times. For a list twice as large, we would loop at most 20 times. For a list three times as large, we would loop at most 30times!æ The amount of time required is linearly relatedto the size of the list, n. This is what computerscientists call a linear time algorithm.Python Programming, 2/eThe University of Western Australia26

Comparing Algorithmsæ Now, let’s consider binary search. Suppose the list has 16 items. Each time through theloop, half the items are removed. After one loop, 8items remain. After two loops, 4 items remain. After three loops, 2 items remain After four loops, 1 item remains.æ If a binary search loops i times, it can find asingle value in a list of size 2i.Python Programming, 2/eThe University of Western Australia27

Comparing Algorithmsæ To determine how many items are examined in a list ofisize n, we need to solve n 2 for i, or i log 2. næ Binary search is an example of a log time algorithm –the amount of time it takes to solve one of theseproblems grows as the log of the problem size.Python Programming, 2/eThe University of Western Australia28

Comparing Algorithmsæ This logarithmic property can be very powerful!æ Suppose you have the New York City phonebook with 12 million names. You could walk upto a New Yorker and, assuming they are listed inthe phone book, make them this proposition:“I’m going to try guessing your name. Eachtime I guess a name, you tell me if your namecomes alphabetically before or after the name Iguess.” How many guesses will you need?Python Programming, 2/eThe University of Western Australia29

Comparing Algorithmsæ Our analysis shows us the answer to thisquestion is log 2 12000000.æ We can guess the name of the New Yorker in 24guesses! By comparison, using the linear searchwe would need to make, on average, 6,000,000guesses!Python Programming, 2/eThe University of Western Australia30

Comparing Algorithmsæ Earlier, we mentioned that Python uses linear search in its built-in searchingmethods. We doesn’t it use binary search? Binary search requires the data to be sorted If the data is unsorted, it must be sorted first!Python Programming, 2/eThe University of Western Australia31

Recursive Problem-Solvingæ The basic idea between the binary search algorithm was to successfullydivide the problem in half.æ This technique is known as a divide and conquer approach.æ Divide and conquer divides the original problem into subproblems that aresmaller versions of the original problem.Python Programming, 2/eThe University of Western Australia32

Recursive Problem-Solvingæ In the binary search, the initial range is the entire list. We look at themiddle element if it is the target, we’re done. Otherwise, we continue byperforming a binary search on either the top half or bottom half of the list.Python Programming, 2/eThe University of Western Australia33

Recursive Problem-SolvingAlgorithm: binarySearch – search for x in nums[low] nums[high]mid (low high)//2if low highx is not in numselsif x nums[mid]perform binary search for x in nums[low] nums[mid-1]elseperform binary search for x in nums[mid 1] nums[high]æ This version has no loop, and seems to refer to itself! What’s going on?Python Programming, 2/eThe University of Western Australia34

Recursive Definitionsæ A description of something that refers to itself is called a recursivedefinition.æ In the last example, the binary search algorithm uses its own description –a “call” to binary search “recurs” inside of the definition – hence the label“recursive definition.”Python Programming, 2/eThe University of Western Australia35

Recursive Definitionsæ Have you had a teacher tell you that you can’t use a word in its owndefinition? This is a circular definition.æ In mathematics, recursion is frequently used. The most common example isthe factorial:æ For example, 5! 5(4)(3)(2)(1), or5! 5(4!)n! n(n 1)(n 2).(1)Python Programming, 2/eThe University of Western Australia36

Recursive Definitionsæ In other words,æ Orn! n(n 1)!if n 0 1n! n(n 1)! otherwiseæ This definition says that 0! is 1, while thefactorial of any other number is that numbertimes the factorial of one less than that number.Python Programming, 2/eThe University of Western Australia37

Recursive Definitionsæ Our definition is recursive, but definitely not circular. Consider 4! 4! 4(4-1)! 4(3!) What is 3!? We apply the definition again4! 4(3!) 4[3(3-1)!] 4(3)(2!) And so on 4! 4(3!) 4(3)(2!) 4(3)(2)(1!) 4(3)(2)(1)(0!) 4(3)(2)(1)(1) 24Python Programming, 2/eThe University of Western Australia38

Recursive Definitionsæ Factorial is not circular because we eventually get to 0!, whose definitiondoes not rely on the definition of factorial and is just 1. This is called a basecase for the rec