New User Special Price Expires in

Let's log you in.

Sign in with Facebook


Don't have a StudySoup account? Create one here!


Create a StudySoup account

Be part of our community, it's free to join!

Sign up with Facebook


Create your account
By creating an account you agree to StudySoup's terms and conditions and privacy policy

Already have a StudySoup account? Login here


by: Mrs. Dedric Little


Mrs. Dedric Little
GPA 3.79


Almost Ready


These notes were just uploaded, and will be ready to view shortly.

Purchase these notes here, or revisit this page.

Either way, we'll remind you when they're ready :)

Preview These Notes for FREE

Get a free preview of these Notes, just enter your email below.

Unlock Preview
Unlock Preview

Preview these materials now for free

Why put in your email? Get access to more of this material and other relevant free materials for your school

View Preview

About this Document

Class Notes
25 ?




Popular in Course

Popular in Mathematics (M)

This 9 page Class Notes was uploaded by Mrs. Dedric Little on Monday October 19, 2015. The Class Notes belongs to MTH 111 at Oregon State University taught by Staff in Fall. Since its upload, it has received 32 views. For similar materials see /class/224458/mth-111-oregon-state-university in Mathematics (M) at Oregon State University.




Report this Material


What is Karma?


Karma is the currency of StudySoup.

You can buy or earn more Karma at anytime and redeem it for class notes, study guides, flashcards, and more!

Date Created: 10/19/15
Chapter 9 Searching Ordered Collections In Chapter 8 we said that a bag was a data structure characterized by three primary operations These operations were inserting a new value into the bag testing a bag to see if it contained a particular value and removing an element from the bag In our initial description we treated all three operations as having equal importance In many applications however one or another of the three operations may occur much more frequently than the others In this situation it may be useful to consider alternative implementation techniques Most commonly the favored operation is searching We can illustrate an example with the questions examined back in Chapter 4 Why do dictionaries or telephone books list their entries in sorted order To understand the reason Chapter 4 posed the following two questions Suppose you were given a telephone book and asked to find the number for an individual named Chris Smith Now suppose you were asked to find the name of the person who has telephone number 543 7352 Which task is easier Abby Smith 954 9845 The difference in the two tasks represents the Chris SIP 1 th 2 347832 d39ff b t t l l h d Fred Smlth 435 3545 1 erence e ween a sequen 1a or mear searc an Jaimie Smith 8452395 a binary search A linear search is basically the Robin Smith 4 359834 approach used in our Bag abstraction in Chapter 8 and the approach that you by necessity need to perform if all you have is an unsorted list Simply compare the element you seek to each value in the collection element by element until either you nd the value you want or exhaust the collection A binary search on the other hand is much faster but works only for ordered lists You start by comparing the test value to the element in the middle of the collection In one step you can eliminate half the collection continuing the search with either the first half or the last half of the list Ifyou repeat this halving idea you can search the entire list in Olog n steps As the thought experiment with the telephone book shows binary search is much faster than linear search An ordered array of one billion elements can be searched using no more than twenty comparisons using a binary search Before a collection can be searched using a binary search it must be placed in order There are two ways this could occur Elements can be inserted one by one and ordered as they are entered The second approach is to take an unordered collection and rearrange the values so that they become ordered This process is termed sorting and you have seen several sorting algorithms already in earlier chapters As new data structures are introduced in later chapters we will also explore other sorting algorithms Fast Set Operations Keeping a dynamic array in sorted order allows a fast search by means of the binary search algorithms But there is another reason why you might want to keep a dynamic array or even a linked list in sorted order This is that two sorted collections can be merged very quickly into a new also sorted collection Simply walk down the two collections in order maintaining an index into each one At each step select the smallest Chapter 9 Searching and Ordered Collections 1 wing dudmpy39hswhlz mm 3911 mwca ec mn mm 3911 mder Wk are 3911 painters reachas 3911 erdarure ca ec n 511th vulqu M 3911 xemdmmg eaueeudrere capled Th2 mug apemmrbyneems samumes a gaad ennth namn a kzep a mmd callzcmn Hnwzvex mm a en hstechnlqu 5 used as awaym pmvldz fds set aperdodre Reeru dunk m dhsmconn gmddnn ebeg wnhtwu lmpumm dr erereee Fm elzmzms m a set are mqu mer xepmzd Secand a set suppdns a number areaueemr wnh ca ecnan aperdodre such as set Inmn set mtexgcnan set derrereree and set s nse wed as a moan an are de armerm m axdzxed rmereeemr Ta rdrm are mmsecunn smplyvalk xmre 212mm m are rs re emuer am m are secand advance are painter m are rs K are 212mm m are secandxs emdxer manthannthz m advance are painter m are secand Only We elzmzms are bath equal re are whiz caplzd mm are set mtnseconn A ame set aperdmre embe we callzcmns we faxexample set ddwndre m eaueemre murder Thls appmach m set apermre embe rmdememed mg enth axdzxed dyrdmre arrays ax axdzxed Imkzd has In prams axdzxed army at max dner ereaumered smee an axdzxed amycan dim be qulysemhzd mg 3911 bxmysemh alganthm lxmlzxmnh nn nf On lemd Bag using 2 smed Amy Chapter 9 Semhmg and Ordered Caueemre 2 In an earlier chapter you encountered the binary search algorithm The version shown below takes as argument the value being tested and returns in Olog n steps either the location at which the value is found or if it is not in the collection the location the value can be inserted and still preserve order int binarySearch EIeType data int size EIeType testValue int low 0 int high size int mid while low lt high mid low high 2 if LTdatamid testValue low mid 39 else high mid return low Consider the following array and trace the execution of the binary search algorithm as it searches for the element 7 2 4 5 7 I8 12 24 37 40 41 42 50 I68 I69 72 Do the same for the values 1 25 37 and 76 Notice that the value returned by this function need not be a legal index If the test value is larger than all the elements in the array the only position where an insertion could be performed and still preserve order is the next index at the top Thus the binary search algorithm might return a value equal to size which is not a legal index If we used a dynamic array as the underlying container and if we kept the elements in sorted order then we could use the binary search algorithm to perform a very rapid contains test Simply call the binary search algorithm and save the resulting index position Test that the index is legal if it is then test the value of the element stored at the position If it matches the test argument then retum true Otherwise return false Since the binary search algorithm is Olog n and all other operations are constant time this means that the contains test is Olog n which is much faster than either of the implementations you developed in the preceding chapter Inserting a new value into the ordered array is not quite as easy True we can discover the position where the insertion should be made by invoking the binary search algorithm But then what Because the values are stored in a block the problem is in many ways the opposite of the one you examined in Chapter 8 Now instead of moving values down to delete an entry we must here move values up to make a hole into which the new element can be placed Chapter 9 Searching and Ordered Collections 3 As we did with remove we will divide this into two steps The add function will nd the correct location at which to insert a value then call another function that will insert an element at a given location void orderedArrayAdd struct dyArray dy EIeType newElement int index binarySearchdygtdata dygtsize newElement dyArrayAddAt dy index newElement The method addAt must check that the size is less than the capacity calling setCapacity if not loop over the elements in the array in order to open up a hole for the new value insert the element into the hole and nally update the variable count so that it correctly re ects the number of values in the container void dyArrayAddAt struct dyArray dy int index EIeType newElement int i39 assertindex gt O ampamp index lt dygtsize if dygtsize gt dygtcapacity dyArraySetCapacitydy 2 dygtcapacity I you get to fill this in l The function remove could use the same implementation as you developed in Chapter 8 However whereas before we used a linear search to find the position of the value to be deleted we can here use a binary search If the indeX returned by binary search is a legal position then invoke the method removeAt that you wrote in Chapter 8 to remove the value at the indicated position In worksheet 26 you will complete the implementation of a bag data structure based on these ideas Fast Set Operations for Ordered Arrays Two sorted arrays can be easily merged into a new array Simply walk down both input arrays in parallel selecting the smallest element to copy into the new array Chapter 9 Searching and Ordered Collections 4 The set apemare afnman mcereeenare derrereree and s nse are eeehverysemder m a mug Tlm Is each algamhm can be expressed as a funnel wqu dawn 3911 m mpm eaueems advancing 3911 rrder mm 3911 callzcmn wnh 3911 m zsl wing and capymg whee mm a vecmx wrdmrsmmeer swcxdv nv39ml swcxdvkrvv39ngm srucxdwlrnv39mH m e u Mme m lt dy lnysxe e u LA nlt WkrvVSIEIHQMIH wlLYldyAnyeeme u dwaw sllnghull lt wee leoldvAnveex en u dv nvfsxlnv ullH mnyeddrd munwhan q u gt E459 lt p gt gt we faxexample senntzxsectmn Th2 mtexgcnancaplzsdwhz when 5 fanndm bath eaueemre Nance um mdusdbmdmamt 5 mm camenlzmm have 3911 set aperdodre ereece dmwseL rmth mad 39ymg 3911 meme Unmnca smdlerexe en dnd e a are advancesbmh painters xemzmhenlmm dsetdllelemzms m mqu eachwhlz dpparsmdya e The derrere ecupleswl mca ectmnwhzmns bath eaueemre Fma ythzxe 5 3911 s nse esl Lvrddre 3911 mhzx39s ths aperdmr dnesnm Chapter 9 Searchmg and Ordered Caueemrs 5 produce a new set but instead returns false if there are any values in the first collection that are not found in the second But this is the same as returning false if the element from the left set is ever the smallest value indicating it is not found in the other set Question The parallel walk halts when one or the other array reaches the end In the merge algorithm there was an additional loop after the parallel walk needed to copy the remaining values from the remaining array This additional step is necessary in some but not all of the set operations Can you determine which operations need this step In worksheet 27 you will complete the implementation of the sorted array set based on these ideas In Chapter 8 you developed set algorithms that made no assumptions concerning the ordering of elements Those algorithms each have Onz behavior where n represents the number of elements in the resulting array What will be the algorithmic execution times for the new algorithms subset Set operations Using Ordered Linked Lists We haven t seen ordered linked lists yet for the simple reason that there usually isn t much reason to maintain linked lists in order Searching a linked list even an ordered one is still a sequential operation and is therefore On Adding a new element to such a list still requires a search to find the appropriate location and there therefore also On And removing an element involves finding it first and is also On Since none of these are any better than an ordinary unordered linked list why bother One reason is the same as the motivation for maintaining a dynamic array in sorted order We can quickly merge two ordered linked lists to produce a new list that is also sorted And as we discovered in the last worksheet the set operations of intersection union difference and subset can all be thought of as simple variations on the idea of a merge Thus we can quickly make fast implementations of all these operations as well The motivation for keeping a list sorted is not the same as it was for keeping a vector sorted With a vector one could use binary search quickly find whether a collection contained a specific value The sequential nature of a linked list prevents the use of the binary search algorithm but not entirely as we will see in a later chapter Self Study Questions Chapter 9 Searching and Ordered Collections 6 1 What two reasons are identi ed in this chapter for keeping the elements of a collection in sorted order 2 What is the algorithmic execution time for a binary search What is the time for a linear search 3 If an array contains n values what is the range of results that the binary search algorithm might return 4 The function dyArrayGet produced an assertion error if the index value was larger than or equal to the array size The function dyArrayAddAt on the other hand allows the index value to be equal to the size Explain why Hint How many locations might a new value be inserted into an array 5 Explain why the binary search algorithm speeds the test operation but not additions and removals 6 Compare the algorithm execution times of an ordered array to an unordered array What bag operations are faster in the ordered array What operations are slower 7 Explain why merging two ordered arrays can be performed very quickly 8 Explain how the set operations of union and instersection can be viewed as variations on the idea of merging two sets Short Exercises 1 Show the sequence of index values examined when a binary search is performed on the following array seeking the value 5 Do the same for the values 14 41 70 and 73 5 7 I8 12 24 37 40 41 42 50 I68 I69 72 Analysis Exercises 1 The binary search algorithm as presented here continues to search until the range of possible insertion points is reduced to one If you are searching for a specific value however you might be lucky and discover it very quickly before the values low and high meet Rewrite the binary search algorithm so that it halts if the element examined at position mid is equal to the value being searched for What is the algorithmic complexity of your new algorithm Perform an experiment where you search for random values in a given range Is the new algorithm faster or slower than the original Chapter 9 Searching and Ordered Collections 7 N E 4 V39 Provide invariants that could be used to produce a proof of correctness for the binary search algorithm Then provide the arguments used to join the invariants into a proof Provide invariants that could be used to produce a proof of correctness for the set intersection algorithm Then provide the arguments used to join the invariants into a proof Do the same for the intersection algorithm Two sets are equal if they have exactly the same elements Show how to test equality in On steps if the values are stored in a sorted array A set is considered a subset of another set if all values from the first are found in the second Show how to test the subset condition in On steps if the values are stored in a sorted array The binary search algorithm presented here finds the midpoint using the formula IOW high 2 Recently Google reported finding an error that was traced to this formula but occurred only when numbers were close to the maximum integer size Explain what error can occur in this situation This problem is easily fixed by using the alternative formula IOW high IOW 2 Verify that the values that cause problems with the first formula now work with the second Programming Projects N E Rewrite the binary search algorithm so that it halts if it finds an element that is equal to the test value Create a test harness to test your new algorithm and experimentally compare the execution time to the original algorithm Write the function to determine if two sets are equal as described in an analysis exercise above Write the similar function to determine if one set is a subset of the second Create a test harness for the sorted dynamic array bag data structure Then create a set of test cases to exercise boundary conditions What are some good test cases for this data structure On the Web Wikipedia contains a good explanation of binary search as well as several variations on binary search Binary search is also explained in the Dictionary of Algorithms and Data Structures Chapter 9 Searching and Ordered Collections 8 ME 430 Equation Sheet First Order systems USEfUI Numbers 5 overshoot leads to C 2 07 T5 7a 16 overshoot leads to C 2 05 l l s a Rise Time T B C07leadstoa45 T a C 05 leads to 04 2 30 Settling Time 46 T9 7 1 Root Locus Re nement 4 T9 a 2 o Breakaway and break in points For C gig nd 8 such that N GDG 7 D GNG 0 second order SyStem51 o jw crossing Form Routh Table and nd LUZ gain for obtaining a row of zeros Form aux Ts m equation using that gain and solve for s settling Time 0 Arrival and Departure Angles T 1 Eemoriems lt2k1gt180 s s 2 Steady State Error Cw 7 5 For closed loop transfer function Ts s 7 ltan Es X9 7 13 Percent Overshoot X511 T5l OS 100 e WW 1 42 7 ilnOS100 T 71392 zn2OS100 Rise Time 164 T 7 5 M c gt 186 T 7 6 M c gt 213 T 7 7 M c gt Peak Time Tp 7r wnx17C2


Buy Material

Are you sure you want to buy this material for

25 Karma

Buy Material

BOOM! Enjoy Your Free Notes!

We've added these Notes to your profile, click here to view them now.


You're already Subscribed!

Looks like you've already subscribed to StudySoup, you won't need to purchase another subscription to get this material. To access this material simply click 'View Full Document'

Why people love StudySoup

Bentley McCaw University of Florida

"I was shooting for a perfect 4.0 GPA this semester. Having StudySoup as a study aid was critical to helping me achieve my goal...and I nailed it!"

Jennifer McGill UCSF Med School

"Selling my MCAT study guides and notes has been a great source of side revenue while I'm in school. Some months I'm making over $500! Plus, it makes me happy knowing that I'm helping future med students with their MCAT."

Jim McGreen Ohio University

"Knowing I can count on the Elite Notetaker in my class allows me to focus on what the professor is saying instead of just scribbling notes the whole time and falling behind."

Parker Thompson 500 Startups

"It's a great way for students to improve their educational experience and it seemed like a product that everybody wants, so all the people participating are winning."

Become an Elite Notetaker and start selling your notes online!

Refund Policy


All subscriptions to StudySoup are paid in full at the time of subscribing. To change your credit card information or to cancel your subscription, go to "Edit Settings". All credit card information will be available there. If you should decide to cancel your subscription, it will continue to be valid until the next payment period, as all payments for the current period were made in advance. For special circumstances, please email


StudySoup has more than 1 million course-specific study resources to help students study smarter. If you’re having trouble finding what you’re looking for, our customer support team can help you find what you need! Feel free to contact them here:

Recurring Subscriptions: If you have canceled your recurring subscription on the day of renewal and have not downloaded any documents, you may request a refund by submitting an email to

Satisfaction Guarantee: If you’re not satisfied with your subscription, you can contact us for further help. Contact must be made within 3 business days of your subscription purchase and your refund request will be subject for review.

Please Note: Refunds can never be provided more than 30 days after the initial purchase date regardless of your activity on the site.