### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Discrete and Foundational Mathematics I MATH 187

BSU

GPA 3.72

### View Full Document

## 18

## 0

## Popular in Course

## Popular in Mathematics (M)

This 11 page Class Notes was uploaded by Breanne Schaden PhD on Saturday October 3, 2015. The Class Notes belongs to MATH 187 at Boise State University taught by Staff in Fall. Since its upload, it has received 18 views. For similar materials see /class/218009/math-187-boise-state-university in Mathematics (M) at Boise State University.

## Popular in Mathematics (M)

## Reviews for Discrete and Foundational Mathematics I

### 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/03/15

There is one exercise in this document at the end the rest is an explana tion of bubble sort and heap sort Via a moderately large example Bubble sort The idea is to take a list of numbers and go through it item by item7 at each step comparing the current item with the next item and swapping them if necessary to bring them into the right order An example follows 7 9 3 8 4 1 2 5 6 7 and 9 in right order position 1 so no change 7 9 3 8 4 1 2 5 6 9 and 3 in wrong order position 2 7 3 9 8 4 1 2 5 6 9 and 8 in wrong order position 3 7 3 8 9 4 1 2 5 6 9 and 4 in wrong order position 4 7 3 8 4 9 1 2 5 6 9 and 1 in wrong order position 5 7 3 8 4 1 9 2 5 6 9 and 2 in wrong order position 6 7 3 8 4 1 2 9 5 6 9 and 5 in wrong order position 7 7 3 8 4 1 2 5 9 6 9 and 6 in wrong order position 8 738412569 At this point we go back to position 1 and start over Notice that because the maximum element will always be moved to the top7 we only have to go 1 up to position 7 in the next cycle7 then position 67 and so on There are at most two operations to perform at each step a comparison and possible swap so the maximum number of operations in this example is 287321 lngeneral12n72n71 7 so the maximum number of operations in bubble sorting a list with n elements is 2 7 n2 7 n S 722 this is a 00 cost quadratic Quadratic algorithms are much better than exponential algorithms but still not ideal As it turns out7 the list sorting problem is solvable using 0n log2n operations7 which is much faster for large problems We describe a particular algorithm called heap sort77 which displays an interesting combination of concepts from number theory and graph theory in an applied context We use the same list as our working example 793841256 But we organize it completely di erently we use a trick of interpreting a list as a tree The idea is that position 72 in the list is viewed as being connected to positions 272 and 272 1 below and to position above This 2 turns the numbers into a binary tree I don7t know a way to draw lines in to make the tree structure clear7 but you can each number is linked to the numbers on the level below it just to the left and right of it A tree structure of this kind is called an upside down heap just in case the number in each position on the tree is greater than or equal to the two numbers in the positions just below it Notice that the height of the tree made by the numbers from 1 to n is at most log2n 1 the tree for n 2 is the rst with 2 levels7 for n 4 is the rst with 3 levels7 for n 8 is the rst with 4 levels7 for n 16 is the rst with 5 levels7 and so forth We use an algorithm rather like bubble sort to turn any tree into a heap work backward through the list looking at the bottom of the tree rst and working up and if the number at position 72 is greater than the number at position exchange them In terms of the tree7 work from the bottom up if the number in any position is less than the number in the positionjust above it in the tree7 exchange them There are 272 possible operations in one pass of this bubbling operation it will need to be carried out no more than log2n times in case the smallest number in the tree started out at the top level7 for example Once the tree has been turned into a heap7 we observe that the largest number on the list is now at the top of the heap We swap it with the number in the last position the place where we want it to be in the nal sorted list7 then take that position out of our heap since the number is in the right place7 we ignore it from here on The resulting tree might not be a heap7 but it will take few steps to x it If the number swapped into the top position is smaller than one of the two numbers below it7 swap it with the larger of the two Then do the same thing in its new position and keep doing this until you reach the bottom of the tree or everything settles down This will take no more than 2log2 steps because you don7t need to x the entire tree7 just one vertical path through it Then this new heap will have its largest element on top swap this to its correct position in the sorted list position 72 7 1 and remove position 72 7 1 from the heap Keep repeating until the whole list is sorted The whole process will take no more than 472 log2 72 steps 2n log2 steps to make the tree into a heap the rst time7 then 1 step of moving an item to its correct position in the list followed by no more than 2log2n corrections to the heap7 these last two things repeated 72 times We carry out the entire algorithm for the example above At each step we show the tree format we occasionally show the list format too First we have to turn this tree into a heap We go through the list backward through lower levels of the tree back ward then through higher levels in this tree we don7t make any change until we get to the 9 at the second level which is less than the 7 above it so we swap and we nd no more inversions during the rst pass of the algorithm for making the tree a heap During the second pass we notice that the 8 on the third level is less than the 7 on the second level so we swap them The tree is now a heap which happened remarkably quickly because this example was accidentally almost a heap anyway but any tree of numbers of this same size would become a heap after no more than three passes enough swaps to move a small number at the top all the way to the bottom The list is now of the shape 9 8 3 7 4 1 2 5 6 We know that 9 is the largest number in the list so we swap it to the end where it belongs 683741259 and exclude the last position from our tree which now looks like this 5 Now we x it to a heap again exchange the possibly bad 6 with the largest number below it 8 5 5 and we have a heap again the 6 is greater than the 5 below it Now the list has the shape 873641259 and we know that 8 is the largest number in the tree7 so we swap it with the 5 in the second to last position7 so that our list now looks like this 573641289 and our tree now looks like this notice that we now exclude the 8 just as we excluded the 9 6 4 1 2 The new entry 5 at the top is bad7 so we exchange it with the largest entry below the 7 6 4 1 2 6 Now we have a heap again7 so we know the 7 is biggest and we swap it to its correct position 763541289 becomes 263541789 and our tree becomes ignoring the 7 now as we ignored the 8 and 9 earlier 5 4 1 This is bad of course swap 2 at the top with 6 below it and then with 5 below it 2 4 1 and we have a heap again Now we have a heap again7 so we know the 6 is biggest and we swap it to its correct position 653241789 becornes 153246789 and our tree becornes ignoring the 6 now as we ignored the 778 and 9 earlier The 1 is bad and swaps with the 5 2 4 and then with the 4 notice it went in the other direction this time 5 2 1 17m not going to show the lists this time I peel o the 5 from the top adding it to the sorted list 5767 77879 and replace it with the 1 at the end of the heap 1 4 3 2 then bubble the 1 down 4 1 3 2 and again 4 2 3 1 Then peel the 4 o onto the sorted list 47576777879 and replace it with the 1 again 1 2 3 bubble the 1 down it swaps with the larger 3 rather than the 2 3 This is a heap so it peels the 3 o replacing it with again the 1 our sorted list is now 3747 5767 77879 one last swap 1 peel the 2 OE and add it to the list and there is nothing more to be done we now have the sorted list 12734756777879 Exercise Your exercise is not nearly as large as the one above Show all steps in sorting the 117 97 237 77 147 3 using bubble sort7 then show all steps in sorting the same list using heap sort I haven7t worked the exarnple7 and it is small enough that bubble sort rnight accidentally do better7 but I expect that heap sort will win Solutions to the exercise will be posted by Friday afternoon Sorry l7rn posting this late Tuesday morning Here are the steps in bubble sort I only showed the steps where something was actually done numbers were swapped 119237143 911237143 11723143 11714233 911714323 beginning of second pass 971114323 71131423 beginning of third pass 791131423 793111423 fourth pass 7 3 9 11 14 23 fth pass 379111423 In the heap sort section I show the part which is a heap or is being made a heap as a tree and the sorted part as a list once it shows up Here7s heap sort Make the tree a heap I only show the stages where swaps actually hap pen Remember that we work backward through the list from the bottom of the tree 23 11 7 9 rst pass complete only one swap needed in second pass It is a heap now 14 11 7 Take 23 o top 14 11 7 sorted 23 3 11 7 sorted 23 11 3 7 sorted 23 Its a heap again take 14 o top sorted 14 23 sorted 14 23 Its a heap again take 11 o top sorted 11 14 23 23 sorted 11 14 23 Its a heap again take 9 o top sorted 9 11 14 23 sorted 9 11 14 23 Take 7 o top then 3 o top 37111423 There are actually more steps in the heapsort algorithm in this small example at least there are more actual swaps This isn7t surprising because it has more overhead It is worth noting that the sorting question on your nal is avoidable it is a part in a two part question Where you can choose one or the other But I persist in thinking that students in the past have had fairly good success With this kind of question

### 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

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "I used the money I made selling my notes & study guides to pay for spring break in Olympia, Washington...which was Sweet!"

#### "There's no way I would have passed my Organic Chemistry class this semester without the notes and study guides I got from StudySoup."

#### "Their 'Elite Notetakers' are making over $1,200/month in sales by creating high quality content that helps their classmates in a time of need."

### Refund Policy

#### STUDYSOUP CANCELLATION 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 support@studysoup.com

#### STUDYSOUP REFUND POLICY

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: support@studysoup.com

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 support@studysoup.com

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.