DOC PREVIEW
UNI CS 1520 - Lecture Notes

This preview shows page 1 out of 4 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 4 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

1) Consider the following linear search (sequential search) code:def linearSearch(target, aList): """Returns the index position of target in aList or -1 if target is not in aList""" for position in xrange(len(aList)): if target == aList[position]: return position return -1a) What is the basic operation of a search?b) For the following aList value, which target value causes linearSearch to loop the fewest (“best case”) numberof times?aList: 10 15 28 42 60 69 75 88 90 93 97 0 1 2 3 4 5 6 7 8 9 10c) For the following aList value, which target value causes linearSearch to loop the fewest (“worst case”) numberof times?d) For a successful search (i.e., target value in aList), what is the “average” number of loops?def linearSearchOfSortedListA(target, aList): """Returns the index position of target in sorted aList or -1 if target is not in aList""" breakOut = False for position in xrange(len(aList)): if target <= aList[position]: breakOut = True break if not breakOut: return -1 elif target == aList[position]: return position else: return -1e) The above version of linear search assumes that aList is sorted in ascending order. When would this versionperform better than the original linearSearch at the top of the page?Data Structures Lecture 2 Name:_____________________Page 12) Consider the following binary search code:def binarySearch(target, lyst): """Returns the position of the target item if found, or -1 otherwise.""" left = 0 right = len(lyst) - 1 while left <= right: midpoint = (left + right) / 2 if target == lyst[midpoint]: return midpoint elif target < lyst[midpoint]: right = midpoint - 1 else: left = midpoint + 1 return -1a) For binary search, what is the best-case time complexity B ( )?b) What is the basic operation for binary search?c) “Trace” binary search to determine the total number of worst-case basic operations?1 20 n-1. . . target151 midpoint midpoint10020010# ofbasicoperations#elementsworst-caseloop1 2 "n"... leftright #d) If the list size is 1,000,000, then what is the maximun number of comparisons of list items on a successful search?e) If the list size is 1,000,000, then how many comparisons would you expect on an unsuccessful search?Data Structures Lecture 2 Name:_____________________Page 2All simple sorts consist of two nested loops where: the outer loop keeps track of the dividing line between the sorted and unsorted part with the sorted part growingby one in size each iteration of the outer loop.  the inner loop's job is to do the work to extend the sorted part's size by one. Initially, the sorted part is typically empty. The simple sorts differ in how their inner loops perform their job.3) Selection sort is an example of a simple sort. Selection sort’s inner loop scans the unsorted part of the list to findthe minimum item. The minimum item in the unsorted part is then exchanged with the first unsorted item to extendthe sorted part by one item. At the start of the first iteration of the outer loop, initial list is completely unsorted:102035 40 456025 5090Empty Sorted PartUnsorted Part0 41 52 63 7 8The inner loop scans the unsorted part and determines that the index of the minimum item, minIndex = 6.102035 40 456025 5090 Sorted PartUnsorted Part0 41 52 63 7 8minIndex = 6firstUnsortedIndex = 0After the inner loop (but still inside the outer loop), the item at minIndex is exchanged with the item atfirstUnsortedIndex. Thus, extending the Sorted Part of the list by one item. 10 2035 40 4560 25 5090 Sorted PartUnsorted Part0 41 52 63 7 8minIndex = 6firstUnsortedIndex = 0a) Write the code for the outer loopb) Write the code for the inner loop to scan the unsorted part of the list to determine the index of the minimum itemc) Write the code to exchange the list items at positions firstUnsortedIndex and minIndex. Data Structures Lecture 2 Name:_____________________Page 34) Bubble sort is another example of a simple sort. Bubble sort’s inner loop scans the unsorted part of the listcomparing adjacent items. If it finds adjacent items out of order, then it exchanges them. This causes the largestitem to “bubble” up to the “top” of the unsorted part of the list.At the start of the first iteration of the outer loop, initial list is completely unsorted:102035 40 456025 5090Empty Sorted PartUnsorted Part0 41 52 63 7 8The inner loop scans the unsorted part by comparing adjacent items and exchanging them if out of order.101010101010202020202020353535353535404040404040454545454545606060606060252525252525505050505050909090909090 Sorted Part Sorted PartUnsorted PartUnsorted Part000000444444111111555555222222666666333333777777888888lastUnsortedIndex = 8in order, so don't exchangein order, so don't exchangein order, so don't exchangeout of order, so exchangeout of order, so exchangeout of order, so exchangeout of order, so exchangeout of order, so exchangeAfter the inner loop (but still inside the outer loop), there is nothing to do since the exchangesoccurred inside the inner loop.a) What would be the worst-case complexity of bubble sort?b) What would be true if we scanned the unsorted part and didn’t need to do any exchanges?Data Structures Lecture 2 Name:_____________________Page


View Full Document

UNI CS 1520 - Lecture Notes

Download Lecture Notes
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Lecture Notes and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Lecture Notes 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?