### Create a StudySoup account

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

Already have a StudySoup account? Login here

# ALGORITHMS AND DATA STRUCTURES C S 315

UT

GPA 3.8

### View Full Document

## 15

## 0

## Popular in Course

## Popular in ComputerScienence

This 2 page Class Notes was uploaded by Ryley Lang on Sunday September 6, 2015. The Class Notes belongs to C S 315 at University of Texas at Austin taught by Staff in Fall. Since its upload, it has received 15 views. For similar materials see /class/181676/c-s-315-university-of-texas-at-austin in ComputerScienence at University of Texas at Austin.

## Similar to C S 315 at UT

## Reviews for ALGORITHMS AND DATA STRUCTURES

### 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: 09/06/15

L L I I r 00 39 Ebuildingsmallpieces e Iin Java by 39 5 never I easyintegrating hard 00 chara encapinheritance sub poly typeset of g 39 quot errorssub polymethod that expects parametertype T accepts S where S is a subtype Waterfall Model 1write specs2design code3write code4test code 5integrate code6maintain code XPpair progwrite test cases first optimize lastsimplestdesignwork on diff parts of code make frequent small releasesfacilitate changes in requirementsdecisionsCoding Cycle redwrite test casesgreenwrite codeblueclean it up typecastonly changes type temporaril typing map an expression to a type overloadingad hoc polymorphism same me d L39 quot39 g 39 39 39 39 Lquot g details1simplifies2focus on whole3deal with 39 39 39 39 quot 1 quot L 39 quot39 s 25ubtypesame method signatures define parts Ill at I oftype hierarchy Parametric Poly same quot parameter 439 uses precise in man Big Ohprovides upper bound on proofnot worst case Big 9 provides lower bound Recursion1base case 2make progress towards base case3assume recursive calls work4avoid redundant work T eoermaiiy 39 39 39 L quot 39 39 nlogn 39 39 worst case Facts aFor inputs length n assuming no duplicates there are n permutationsb For each permutation there exists exactly 1 input forwhich permutation is a correct sort consider n elements a1a2an there is one permutation that produces sorted output Initially Sn PICTURE Selectionbubble sort are On2 staticType va riablenew dynamicType quotwhat can be called quotwhich specific method will be called EXA Stable sorting algorithms maintain the relative order of records With equal keys If all keys are different then this distinction is not necessary But if there are equal keys then a sorting algorithm is stable ifWhenever there are two records let39s say R and S With the same key and R appears before S in the original list then R will always appear before S in the sorted list When equal elements are indistinguishable such as with integers or more generally any dataWhere the entire element is the key stability is not an issue 39 39 h d interpreter 39 p 39 yp i a to form reference to cia awrapperrla 39 impiememin 39 39 to inheritance W J L N we 39 39 39 39 typcroverriding the return type with a subtype derived class V V K y L imL L r V operation using an arrav binarv search tree a data structure 39 39 remn al and searching 39 Kth wallest item The cost islog averagercase for simple I u urn r v p v in one oftwo groups greater than or smaller than the p39 r p39 M and orderingl buildHeap operationprocessofreinstating heap order in a complete tree which can be done in linear 39 39 39 binarvtreetree 39 39 39 4 d I t39 fthe minimum involvesplacing the former last item in a hole that iscreated at the root The the tree an M pia u next available location and then bubbling itup until the new item can be placed in it e psort algorithm based on the idea that a priority queue can be used to sort in 0NlogN time Data begins at position 0 so children of node I are in positions 2i1 and 2i2 Heapsort is NOT stable0n log n c static void heapsort Comparable 1 a Insertion Sort for int i alength 2 i gt 0 iquot M bUllClHeap stable 0n2 om percDown a i alength f0 int 1 alength 11 gt 071 publlc statlc VDld lnsertlonisrtunt array swapReferences a 0 i M deleteMaX V in n percDown a 0 i for int i l l lt n i l int j l l int B arrayl private static int leftChlld int i while j gt 0 M ax3 71 gt B return 2 c i 1 arrayij arrayijrl 3 t lndex i the position from whlch to percolate down int n the logical size of the binary heap arraylj V private static void percoownlt Comparable l a int i int n int chlld l Comparable tmp for tmp a1 lettChildlt i lt n i child shellsort child lettChildlt i stable 0nlogzn 0n if child 1 n a 1 ampamp a child icompareTo al child 1 lto child public static void shellsortlt Comparable l a if tmpcompareTo a child 1 lt o fen int gap alength 2 ga gt o ala gapgap2lintgap22 else for int i gap i lt alength i break i Comparable tmp a i i int j i al i tmp for j gt gap ampamp tmpcompareTo a j a lndexl the lndex ot the first Object gap 1 lt Di 1 ap rill index the lridex of the second Object a aintint2 l a public static final void swapReferences Object l i object tmp a indexl 1 a lndexl al lndeXZ l a lndeXZ tmp Binary searchifthe input array has been sorted and is performed from the middle ratherthan end s logarithmic because the search range is halved in each iteration 0 Big 0hTN if OFN if there are positive constants c and N0 such that TNicFN when NzN ClogNlogZNNNlogNN2N32NN NN Big OmegaTN if OmegaFN if there are positive constants c and N0 such that TN3cFN when NzNO Big Thetathe upper bound growth rate ofT N equals lower bound lJ39ttleOh growth rate of TN is strictly less than FN is oFN iff TN is OFN and TN i not 0 FN mergesort stable Olnlognl public static void mergesortlt comparable 1 a Private static Comparable 1 tmpArray new Comparable alength 1 r i t hig mergesort a tmpArray 0 alengt e 1 f private static void mergeSOrt Comparable 1 a Comparable tmpAr else int left int right 1 if left lt ght nt cen r ft right 2 mergesort a tmpArray left center mergesort a tmpArray center 1 right merge a tmpArray lef center 1 right a a 391 array of Comparable item tmpArray an array to place the merged result leftpos the leftmost index of the subarray rlghtPos the index of the start of the second half rlghtEnd the rightmost index of the subarray private static void mergelt Comparable 1 a Comparable 1 tmpAr ray int leftPos int rlghtPos int rlghtEnd 1 int leftEnd rlghtP s e 1 int tmpPos leftPos int numElements rightEnd e leftPos l Main 1101 while leftPos lt leftEnd as rlghtPos lt rightEnd if a leftPos compareTo a rightPos lt 0 tmpArray1 tmppos 1 e a leftPos 1 else tmpArray tmpPos 1 a rightPos 1 while leftPos lt leftEnd copy rest of first half tmpArray tmpPos 1 e a leftPos 1 while rlghtPos lt rightEnd opy rest of tight l tents tmpArray1 tmppos 1 e a rightpos 1 Copy tmpArray hack for in i i lt numElements i rightEnd a rightEnd tmpArray rightEnd quickso t notstable olnlognleolnzl 39 void quicksortlt low CUTOFF gt high Comparable 1 a int low low insertionSort a high l Sort low middle high int middle low high 2 if a middle 1compareTo a low 1 lt o swapReferences low middle if a high 1compareTo a low lt 0 swapReferences a low high if a h gh 1compareTo a middle 1 lt o swapReferences a middle high Place pivot at position high e l swapReferenceS Comparable pivot a1 hi h a middle high 7 l g i 1 H Eegln partitioning int i i for l low I hlgh a 1 l while a i 1compareTo pivot lt 0 while pivotcompareTo a as 1 lt 0 if i gt 3 break swapReferenceS a i i Restore swapReferen guicksortlt a Sort small guicksortlt a pivot ces a i high e l 1 y l y elements i 1 high Sort large STABLEOn must have fixed 1 of digits starts from east significant bits public class Radlxsort public static Vold radixSOrtint arrl ifarrlength 0 return lnl np new lntarrlength Z int1 q new int10xloo1 lntiklf o fork0klt4kl forioiltnplengthel i mu 1 i1 npi 1 el fori0iltqlengthi q i1 e1 forfl0lltarrlength71 l OXFFltltkltlt3 amparrllgtgtkltlt3 1 ifq l q fr else l qlr whllenpll 1 e1 l f nPlf l npl0 arri1 npl 1 el fOrlql071lt0X10071 forlql illllnpll 1 arrj npl 0 l

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

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

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

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