### Create a StudySoup account

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

Already have a StudySoup account? Login here

# Algorithms CSCD 320

Eastern Washington University

GPA 3.86

### View Full Document

## 82

## 0

## Popular in Course

## Popular in ComputerScienence

This 9 page Class Notes was uploaded by Dewitt Paucek on Sunday October 11, 2015. The Class Notes belongs to CSCD 320 at Eastern Washington University taught by Timothy Rolfe in Fall. Since its upload, it has received 82 views. For similar materials see /class/221496/cscd-320-eastern-washington-university in ComputerScienence at Eastern Washington University.

## Similar to CSCD 320 at Eastern Washington University

## Popular in ComputerScienence

## Reviews for 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/11/15

Divide and Conquer Generation of Fibonacci Numbers There is an Olog n method to generate Fibn It depends on using 2x2 matrix multiplication combined with the Olog n algorithm for performing exponentiation F F 1 1 N Theorem N N FN FM 1 o F2 F1 1 1 1 Bas1s case forN l 1 F 0 Proof by induction on N gt 1 1 1 N 1 1 N4 1 1 Recurrence 1 0 1 0 1 0 FN Fer 1 1 Substltute the 1nduct1ve hypothes1s F N71 F N72 1 0 F F F N N71 N Perform the matrix multiplication Fer FNrZ Fer F N1 F N Slmpllfy F1bonacc1 numbers FN Fer Let basis be the initial 2x2 matrix shown above For expon gt 1 left recursebasis expon2 and right for even expon has the same contents as left but for odd expon is basis left The result then is left right The matrix multiplications of course are not unit operations In fact they require four multiplications and four additions for each of the four cells of the result N Based on material in httpdspacemitedubitstreamhandlel721 l368476046JFall 200 lNIUrdonlyresElectrical Engineering andComputerScience6046JIntroductionto AlgorithmsFa11200 lA02BOC08F6F34 lODAE983F7EF50E540E01ecture03pdf Printed 2010 Jul16 at 1654 Page 1 public class Fibidiandic static int count 0 static void mult72x2long lt long rt longresult int row col k for row 0 row lt 2 row for col 0 col lt 2 col long accum O for k O k lt 2 k accum accum ltrowk rtkcol count resultrow col accum static long matrixidiand7clong x int expon long leftnull rightnull result lL 0L OL lL Identity matrix if expon result long xclone else if expon gt D left matrixidiand7cx expon2 right new long22 Systemarraycopyleft0 O rightO O 2 Systemarraycopyleftl O rightl O 2 if exponampl mult72x2left x right mult72x2left right result return result public static void mainStringl argm long basis lL 1L lL 0L L result for int k 2 k lt 256 k k count 0 result matrixidiand7cbasis kl SystemoutprintfquotFibd d in d multadd pairsnquot kl resultlO count count 0 result matrixidiand7cbasis k SystemoutprintfquotFibd d in d multadd pairsnquot k resultlO count Printed 2010 Jul16 at 1654 Page 2 DSW Tree Balancing Algorithm by Timothy Rolfe This is an algorithm to balance a binary search tree without requiring any additional space beyond the left and rightlinks that are inherent in a binary tree It was devised by Colin Day and later improved by Quentin F Stout and Bette L Warren hence the acronym DSW These notes are based on the discussion of the algorithm in Adam Drozdek s Data Structures and Algorithms in C PWS Publishing 1996 pp 173 ff Step one generate a degenerate BST with all left links NULL Drozdek refers to this as creating the Backbone and it is based on performing rightward rotations on every node with a nonnull left link Step two given n nodes in the tree make approximately log2n rightwardonly traversals of the tree performing leftward rotations This generates a complete binary tree 7 that is except possibly at the bottom level all tree levels are full and if the bottom level is not full all nodes are grouped on the left The two rotations spoken of above are as one might expect inverses of each other As such it is more useful to show the grandparent Gr whose link must be altered and then instead of parent and child leftward node Lt and rightward nodeRt For completeness the leftward child of Lt is shown even though it is not moved as well as the rightward child of Rt The child that is moved is the subtree occurring between Lt and Rt in one circumstance it is the rightward child of Lt in the other it is the leftward child of Rt Ri t rotate 91 Left ro a e t t R P P Q R In the spirit of Drozdek s Delete logic the rotation functions implementing the abovesketched algorithms have been written so that they return a reference to the modified subtree as they do their updates In the implementation of the DSW algorithm 1 have taken from Warren and Stout the technique of placing the entire BST to be balanced as the right subtree of a pseudoroot This means that none of the rotations are in fact done at the root node greatly simplifing the programming NOTE All Binary Search Tree balancing algorithms are based on rotations exactly as seen in the DSW algorithm Some perform compound rotations that is they use transformations that may be viewed as two or more rotations within a valid Binary Search Tree that still retain the BST property for the generated tree A more extensive discussion of the DSW algorithm is available at httppenguinewueduNtrolfe DSWpaper Printed on 2010707720 at 1802 Page 1 DSW Tree Balancing Algorithm Page 2 From Stout and Warren 7 translated from Pascal to C to Java by Tim Rolfe Stout and Warren explicitly encode the rightward rotations While in the implementation that follows the rotations are isolated in their own callable functions Tree to Vine algorithm a quotpseudo rootquot is passed comparable with a dummy header for a linked list void treeitoivine BSTnode root BSTnode VineTail remainder temthr VineTail root remainder VineTailRight while remainder NULL ilf no leftward subtree move rightward if remainderLeft NULL VineTail remainder remainder remainderRight else eliminate the leftward subtree by rotations else Rightward rotation temthr remainderLeft remainderLeft temthrRight temthrRight remainder remainder temthr VineTailRight temthr vineTail vineTail emainder T3 T1 rotate gt T1 T2 T2 T3 Figure 2 A TreetoVine Rotation Quentin F Stout and Bette L Warren Tree Rebalancing in Optimal Time and Space Communications ofthe ACM V01 29 N0 9 September 1986 p 904 NOTE for ACM members the full text is available online through httpwwwacmorgpubscontentsjoumalscacm Navigate to V01 29 N0 9 Printed on 20100720 at 1802 DSW Tree Balancing Algorithm Page 3 DSW Algorithm Implementation Methods public class DSW extends BST public void rebalance BSTnode pseudoiroot rotiset pseudoiroot Dim Perform a set of nim left rotations new BSTnode 1 null root Takes care of the nonifull leve vinify pseudoiroot Posticondition degenerate tree thrlne mgt l Eziancegg20tlight ggiggzogg tigg balanced tree rotiset pseudoiroot m Perform a set of m left rotations correctTree root null Update heights and parent links i l Turn an arbitrary binary search tree into a vine degenerate tree ig irlffg 3Ett settled get valid helght and Size values Note pseudoiroot guaranteed noninull 39 private VOld Vlnlfy BSTnode pseudo r00 e void correctTree BSTnode node BSTnode parent i l BSTnode Gr pseudoiroot Grandparent if inio iv l Dial3L p Grright parent While p null First correct below this node if pleft 1 null Eliminate all leftward links mde Grright rotateRightGrright 39 g 39 7 G ht NOW w can properly correct this node p 7 r39rlg ltVal nodeleft null nodeleftheight 0 else rtVal noderight 1 null noderightheight 0 7 nodeheight i Mathmax ltVal rtVa Gr iprrl ht else move rightward and do it again ltVal nodel f nul 9 no 1 Size or p 39 g 39 rtVal noderight l noderightsize 0 nodesize l ltVal rtVal l Tim Rolfe utility routine for balancepseudoiroot private void below rotisetBSTnode pseudoiroot i t n Rotation functions BSTnode BSTnode rotateLeft BSTnode lt if n 0 return Zero rotations to be done Rotate leftward iquot left node moves down right node moves up p seudoiroot Root is at pseudoirootright BSTnode rt ltright q rtleft for 39 n gt O pright nquot rotateLeftpright Note 39 after the rotate just p pright rtleft lt move one position iquot rotate ltright q itself moves the other position return rt Return the link to the new subtree root if p null ampamp n l l l Systemerrprintln quotAbout to jump through null iquot ABORTI lquot BSTnode rotateRightBSTnode r Systemexitl Rotate rightward iquot right node moves down left node moves up BSTnode lt rtleft q ltright39 l ltright rt rtleft q Eiginblge iigaiyesearCh tree Wine generate the return lt Return the link to the new subtree root e void balance BSTnode pseudoiroot BSTnode p pseudoirootright i n Number of nodes in the degenerate rightward tre end Class DSW m Nodes in the completely full part of the final tree Count the nodes in the vine or n O p l n for m null p pright 1 m lt n1 Overshoot then back off m m mZ 7 l pow20 floorlognl log2 r 1 Printed on 20100720 at 1802 TreeiBalancing Trace of the DSW Algo thln on a 177node Tree Page 4 4 Re Tlm 9 Re est even 2 ReeTlm 3 ReeTlm 7 Reesteven 8 Reesteven 39 Reesteve e LeeMark Printed on 20100720 at 1802 15 ReeTim l6 Leesteven Reesteve Two Rotations Printed on 20100720 at 1802 TreeiBalancing Trace of the DSW Algotithln on a 177node Tree Seven Rotation Three Rotations Begin Tree Balancing One Rotation Page 5 WorstCase FixHeap Total Traversals Timothy Rolfe As noted in class the worst case is going to be the situation in which the array to be heapi ed has the data stored exactly backwards from what the heap will require In this case each DownHeap operation will traverse from the root of the wheap being repaired down to the leaf level The number of edges along this path will be the difference of the leaf level from the level of the root of the subheap being repaired We use level 0 for the root rather than 1 Let k be the leaf level in a full binary tree that is full at all levels 0 through k The number of subheaps with one edge down to the leaf level will be 2m the number of subheaps with two edges down to the leaf level will be 21H eventually the root of the entire heap just one will have k edges down to the leaf level Notice that the number of edges down to the leaf level also shows up being subtracted from k in the exponent for 2 We can collect all of this information into a summation kil k 2 wherek j gives the number of edges down to the leaflevel 120 1 and 2 gives the number of nodes at that level in the tree This one summation however can be reorganized into two summations for which we have closedform solutions kil kil kil kil Z k2 Z 122 kZZJ Z 122 J390 J390 j0 j0 kil k Z 2 will simply give us k 2 k7 l as the wellknown summation ofpowers of 2 J39 0 A handout in the quot 39 of binarv trees has the proof of the summation that can easily be transformed mult1ply1ng both s1des by 2 mm 2 j 2 k l 2 2 F1 kil A simple correction for the summation indices gives 2 j 2 k 2 2k 2 39 i 0 J Combiningk2k71 7 k722k 72 k2k7k2k7k2k172 2k 717k71 Nikil Therefore even in the worst case the FixHeap algorithm is 0 N We ve already seen that the best case is 0 N 7 as N2 Thus worst case takes approximately twice as long as best case Mark Allen Weiss Algorithms Data Structures and Problem Solving with C after giving a proof for this recurrence poses nding another proof as his problem 2010 k Here is the Instructor s Guide solution to problem 2010 7 let SN k j 2 j Form 2SN SN 2 then combine Will have massive cancellations kil I ll work from k j 2 J since thejk term disappears because of kij J390 kil 2SN Z k j 2 11 Multiply both sides by 2 J390 k Zltk pl2p Letpjl pl k k Zltk p2p 2217 Rearrange p1 p1 k k Z k p2p k 2 2p 1 AddinandsubtractoffapOpartinboth p0 p0 k k l Z k p 2p k 2 l l l Solve summationofthepowers of2 70 kil k p 2p k 2k1 2 Note that kip clobbers the last sum term 70 k4 Z k 39 2 k 2k1 2 Relabel summation index fromp toj J390 kil k N l k Z k j 2 Rearrange use de nitionN2 171 J390 SN 2SN 7 SN k N l kzlk f392j 7 kggk jlzj 10 Nilik QED Same answer second proof Printed 20107Julil9 at 0521

### 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 signed up to be an Elite Notetaker with 2 of my sorority sisters this semester. We just posted our notes weekly and were each making over $600 per month. I 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."

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