### Create a StudySoup account

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

Already have a StudySoup account? Login here

# DESIGN AND ANALYSIS OF ALGORITHMS COMP 482

Rice University

GPA 3.72

### View Full Document

## 40

## 0

## Popular in Course

## Popular in ComputerScienence

This 57 page Class Notes was uploaded by Cleora Stiedemann on Monday October 19, 2015. The Class Notes belongs to COMP 482 at Rice University taught by Staff in Fall. Since its upload, it has received 40 views. For similar materials see /class/224965/comp-482-rice-university in ComputerScienence at Rice University.

## Popular in ComputerScienence

## Reviews for DESIGN AND ANALYSIS OF ALGORITHMS

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

CMP 482 l ELEC 420 Heaps Skim CLRS 6 Review binary heaps Read CLRS 1920 Summary of Results Binary heaps Binomial Fibonnacci worst case H93 PS H93 P5quot worst case amortized Insert log n log n 1 Wmum 1 log n 1 eteMiry log n log n log n Union n log n 1 Delete log n log n log n D e c re a s39i log n log n 1 Key Alternatively Maximum Binary Heap Review Almost complete binary tree All levels filled except last where filled left to right Minheap ordered Children greaterthan or equal to parents Root min elt gt gt Height Llog2 nJ Binary Heaps Implementation Use array no need for explicit pointers Parenti Li2J Lefti 2i Righti 2i 1 Irrelevant for current discussion concentrate on tree structure Binomial Heaps Overview A list of binomial trees Each has some of the data Each has the heap property Binomial Tree Binomial Tree Properties 1 Binomial tree Bk nodes 2k Height k Degree of root k Deleting root yields binomial trees Bk1 BO Can prove by induction on k 397 affix Bo Binomial Tree Properties 2 k Bk has nodes at depth i depth 0 depth 1 depth 2 depth 3 depth 4 B4 Binomial Heap Sequence of binomial trees satisfying binomial heap property Each tree is minheap ordered O or 1 binomial tree of order k Vuillemin 1978 10 Binomial Heap Properties Binomial heap of n nodes Min key root of BO B1 or Bk Contains binomial tree Bi iff bi 1 Where bnb2b1b0 is binary representation of n trees S Llog2 nJ 1 Height 3 Llog2 nJ Binomial Heap Implementation Each node has 3 pointers parent 1St child next sibling Roots in singlylinked list from smallest tree to largest heap Binomial Heap Implementation Leftist Powerof2 Heap Binomial Heap Union Special Case Easy if each are order k binomial trees Choose smaller key as new root Connect roots Binomial Heap Union General Case Analogy 19 7 26 Binomial Heap Union Example I I I 15 Z Z 19 Running time oc trees Oog n 20 Binomial Heap Delete Min 1 Find root min key of H and delete 2 H39 9 Children of deleted key 3 H e UnionH39 H Each step OIog n 21 Binomial Heap Decrease Key Assume given pointer to node don t have to find it 1 Change key 2 While x lt parent swap bubbles node up OIog N 0c depth of node x s Llog2 nJ Binomial Heap Delete 1 Decrease key of x to cgtltgt 2 Delete min Each step OIog N 23 Binomial Heap Insert 1 He MakeHeapx 2 H e UnionH39 H OIog N Binomial Heap Sequence of Inserts Inserting 1 item can take QIog n time n Oa1step 0 n 0125teps I n 0113steps n 01114steps n 11 111 a log2 n steps Inserting sequence of n items takes On time n21 n42 n83 szn 25 Summary of Results Again Binary heaps Binomial Fibonnacci worst case H93 PS H93 P5quot worst case amortized Insert log n log n 1 Minimum 1 log n 1 DeleteMin log n log n log n Union n log n 1 Delete log n log n log n Decrease log n log n 1 Key Fibonacci Heaps Intuition Similar to binomial heaps but less structured Lazy unions Original motivation Om n log n shortest path algorithm Also led to faster algorithms for MST weighted bipartite matching Fredman amp Tarjan 1986 27 Fibonacci Heaps Structure Set of minheap ordered trees min O 0 Some nodes marked 28 Fibonacci Heaps Implementation Each node has 4 pointers parent 1st child next amp previous siblings Sibling pointers form circular doublylinked list Can quickly splice off subtrees Roots in circular doublylinked list Fastunion Have pointer to min element a root Fast findmin I 0 min 29 Fibonacci Heaps Potential Function Key quantities degreex degree of node x markx is node x marked tH trees tH 5 mH marked nodes mm 3 CDH tH 2mH CIH 11 min W39 30 Fibonacci Heaps Insert 1 Create a new singleton tree 2 Add to left of min pointer 3 Update min pointer Actual cost 01 Change in potential 1 CIgtH W 2mH Amortized cost O11 01 min I O 31 Fibonacci Heaps Union 1 Concatenate heaps 2 Keep pointer to the minimum of the two minimums min Fibonacci Heaps Union 1 Concatenate heaps 2 Keep pointer to the minimum of the two minimums Actual cost 01 Change in potential O ltIgtH tH 2mH Amortized cost 01 Fibonacci Heaps DeleteMin 1 Delete min concatenate its children into root list 2 Consolidate trees so that no two roots have same degree and finding new min min 34 Fibonacci Heaps DeleteMin 1 Delete min concatenate its children into root list 2 Consolidate trees so that no two roots have same degree and finding new min 44M current min 35 Fibonacci Heaps DeleteMin 1 Delete min concatenate its children into root list 2 Consolidate trees so that no two roots have same degree and finding new min current min 36 Fibonacci Heaps DeleteMin 1 Delete min concatenate its children into root list 2 Consolidate trees so that no two roots have same degree and finding new min ELd gw 7 min current 37 Fibonacci Heaps DeleteMin 1 Delete min concatenate its children into root list 2 Consolidate trees so that no two roots have same degree and finding new min ELd gw 7 min current Merge 17 amp 23 trees 38 Fibonacci Heaps DeleteMin 1 Delete min concatenate its children into root list 2 Consolidate trees so that no two roots have same degree and finding new min min Merge 17 amp 7 trees 39 Fibonacci Heaps DeleteMin 1 Delete min concatenate its children into root list 2 Consolidate trees so that no two roots have same degree and finding new min i g4 l CM current Merge 7 amp 24 trees 40 Fibonacci Heaps DeleteMin 1 Delete min concatenate its children into root list 2 Consolidate trees so that no two roots have same degree and finding new min 41 Fibonacci Heaps DeleteMin 1 Delete min concatenate its children into root list 2 Consolidate trees so that no two roots have same degree and finding new min 42 Fibonacci Heaps DeleteMin 1 Delete min concatenate its children into root list 2 Consolidate trees so that no two roots have same degree and finding new min current 43 Fibonacci Heaps DeleteMin 1 Delete min concatenate its children into root list 2 Consolidate trees so that no two roots have same degree and finding new min current Merge 41 amp 18 trees 44 Fibonacci Heaps DeleteMin 1 Delete min concatenate its children into root list 2 Consolidate trees so that no two roots have same degree and finding new min current 45 Fibonacci Heaps DeleteMin Analysis DH Dn tH 2mH max degree of any node in Fibonacci heap with n nodes Actual cost ODn tH 01 work adding min s children into root list amp updating min ODn tH work consolidating trees At most Dn children of min node s Dn tH 1 trees at beginning of consolidation trees decreases by one after each merging Amortized cost ODn tH ACIH ODn tH39 s Dn 1 since no two trees have same degree mH39 s mH ACIgtH s Dn 1 tH 46 Fibonacci Heaps DeleteMin Analysis ls amortized cost of ODn good Yes if only Insert Union amp Deletemin supported In this case Fibonacci heap contains only binomial trees since we only merge trees of equal root degree Dn s Llog2 NJ Yes if we support Decreasekey cleverly Dn s Llogq NJ where q is golden ratio 1618 47 Fibonacci Heaps DecreaseKey Case 0 minheap property not violated 1 Decrease key 2 Change min pointer if necessary Decrease 46 to 45 48 Fibonacci Heaps DecreaseKey Case 1 parent of x is unmarked 1 Decrease key 2 Remove link to parent 3 Mark parent 4 Add X s tree to root list updating heap min pointer Decrease 45 to 15 49 Fibonacci Heaps DecreaseKey Case 1 parent ofx is unmarked 1 Decrease key 2 Remove link to parent 3 Mark parent 4 Add X s tree to root list updating heap min pointer Decrease 45 to 15 50 Fibonacci Heaps DecreaseKey Case 2 parent of x is marked 1 Decrease key 2 Move node to root list updating heap min pointer 3 Move chain of marked ancestors to root list unmarking 4 Mark first unmarked nonroot ancestor Decrease 35 to 5 51 Fibonacci Heaps DecreaseKey Case 2 parent of x is marked 1 Decrease key 2 Move node to root list updating heap min pointer 3 Move chain of marked ancestors to root list unmarking 4 Mark first unmarked nonroot ancestor min Decrease 35 to 5 52 Fibonacci Heaps DecreaseKey Case 2 parent of x is marked 1 Decrease key 2 Move node to root list updating heap min pointer 3 Move chain of marked ancestors to root list unmarking 4 Mark first unmarked nonroot ancestor I a Decrease 35 to 5 53 Fibonacci Heaps DecreaseKey Case 2 parent of x is marked 1 Decrease key 2 Move node to root list updating heap min pointer 3 Move chain of marked ancestors to root list unmarking 4 Mark first unmarked nonroot ancestor I 0 o E e marked node has had 1 child moved to root list Once we move a 2ncl child of node we also move the node Decrease 35 to 5 54 Fibonacci Heaps DecreaseKey Analysis Notation tH trees in heap H mH marked nodes in heap H IH tH 2mH Actual cost Oc where c of nodes cut 01 time for decrease key 01 time for each cut Amortized cost Oc ACIH 01 tH39 tH C mH39 s mH c 2 Each cut unmarks a node Last cut could potentially mark a node ACIgtH s c2c2 4c 55 Fibonacci Heaps Delete 1 Decrease key of x to cgtltgt 2 Delete min element in heap Amortized cost ODn 01 for decrease key ODn for delete min Dn max degree of any node in Fibonacci heap 56 Fibonacci Heaps Bounding Dn Dn max degree in Fibonacci heap with n nodes Can show Dn s Iogq n where I 1 5 2 Thus Delete amp Delete min take Oog n amortized time Proof is somewhat tedious amp explained well in CLRS Key Lemma Let sizex nodes in subtree rooted at x Then odegreeoo s sizex 57

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

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

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

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

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

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