### Create a StudySoup account

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

Already have a StudySoup account? Login here

# LAB Data Structures CS 230

GPA 3.89

### View Full Document

## 16

## 0

## Popular in Course

## Popular in ComputerScienence

This 132 page Class Notes was uploaded by Jordon Hermiston on Thursday October 29, 2015. The Class Notes belongs to CS 230 at Wellesley College taught by Staff in Fall. Since its upload, it has received 16 views. For similar materials see /class/230947/cs-230-wellesley-college in ComputerScienence at Wellesley College.

## Reviews for LAB 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: 10/29/15

CS23O Data Structures Handout 27 Prof Lyn Turbak December 6 2004 Wellesley College Heaps The Many Meanings of Heap The word heap has several different common meanings in computer science 1 It is used as a synonym for an abstract priority queue 2 It is used to refer to a particular class of concrete implementations for a priority queue In this interpretation some priority queues are heaps and some are not which is at odds with meaning 1 9quot In a very different interpretation heap is commonly used to refer to the region of memory used for storing entities whose lifetime exceeds that of the execution frame in which they were created aka heap Object Land This is in contrast to the stack which is the region of memory used for storing entities whose lifetime is less than or equal to that of the execution frame in which they were created aka stack Execution Land Here we shall focus on interpretation 2 though 1 shall be implied in the term heapsort Heapsort Heapsort is a sorting algorithm based on priority queues Here is a generic form based on a max priority queue Modify vector to contain sorted elements from low to hi public static void heapSortMax Vector v Create a max pq MaxPQ pq new MaxPQZZZO Any MaxPQ implementation will do Insert all elements from vector into max pq for int i 0 i lt vsize i pqenqvgeti Store all elements in sorted order from max pq into vector for int i vsize 1 i gt 0 i Must go from highest index down vseti pqdeq Notes 0 This is easy to adapt to min priority queues How 0 In the above method the vector is assumed to contain Comparable elements However it can be easily adapted to take an explicit Comparator as an argument How 0 Later we shall see that a particular implementation of heapsort with max priority queues is particularly e icient Some people reserve the term heapsort for this particularly e icient version E iciency of Max PQ Operations What is the worstcase asymptotic running times of the following max pq operations for the speci ed implementations Assume ean der and first are invoked on an n element heap and heapSortO is invoked on an n element vector The Heap Condition For meaning 2 of heap a binary tree is a max heap if it satis es the following condition at every node in the tree Max Heap Condition The value of a node is 2 the values of all values in both subtrees Similarly a min heap satis es at every node a min heap condition in which the node value is S the values of all values in both subtrees Max Heap Example Consider the following integer tree T Running Times of Heap Operations What is the worst case time of first on a heap It turns out that we can make the worstcase time for ean and der proportional to the height of a heap What is the worstcase height of a heap with n nodes We would like to guarantee the worstcase height of an n node heap is logn In this lecture7 we study a restricted form of heap satisfying this condition the complete heap Binary Addresses We want to de ne a notion of completeness for a binary tree To do this7 it is rst helpful to de ne the binary address of a node in a binary tree 0 The address of the root of the tree is 1 o The root of the left subtree of node with address a has address 2 e a o The root of the right subtree of node with address a has address 2 e a 1 Here are the nodes of T annotated with binary addresses Binary addresses are relative to the chosen root Here are the nodes of the two subtrees of T annotated with binary addresses Complete Trees An n element binary tree is complete if the set of binary addresses of its nodes is the n element set 1 n Example Reconsider the tree T Note An n element binary tree is full if it is a complete tree of height h with 2h 7 1 nodes Which subtrees of T are full What s So Great About Complete Trees Complete trees have two important features 1 The height of an n node complete tree is logn in the worst case 2 Because the binary addresses cover the range 1 to 71 complete trees are easily represented as arraysvectors Eg7 in languages with 1 based array indexing Note In languages with O based array indexing the index is one less than the binary address Address Arithmetic For Complete Trees Complete Heaps A complete max heap is a binary tree that is both complete and a max heap Example Below are some sample complete max heaps containing the letters A L G D R I T H M S A letter later in the alphabet is considered greater than a letter earlier in the alphabet These are just some of the many possible complete heaps possible with this set of elements Complete Heap Enqueuing We can enqueue an element x onto a complete heap in time proportional to its height by 1 inserting x in the next free complete tree slot This maintains completeness of the tree but can Violate the heap condition 2 bubbling x up77 towards the root until the heap condition is restored The result is a complete heap with one more element Step 1 takes constant time and step 2 takes worstcase time proportional to the height of the tree7 which is logn Complete Heap Enqueuing Example Enqueue the letters A L G D R I T H M S into an initially empty complete max heap insert insert H H A L bubbl eUp H insert H insert H Complete Heap Enqueuing Code Here is Java code for enqueuing onto a complete heap represented as a vector instance variable elts and comparator comp public void enq Object x eltsaddx Add x at next binary address bubbleUpeltssize 1 Bubble up from last binary address public void bubbleUp int addr while addr gt 0 ampamp greaterThanaddr paddraddr swapaddr paddraddr addr paddraddr public boolean greaterThan int addr1 int addr2 return compcompareeltsgetaddr1 eltsgetaddr2 gt 0 public void swap int addr1 int addr2 Dbject temp eltsgetaddr1 eltssetaddr1 eltsgetaddr2 eltssetaddr2 temp Complete Heap Dequeuing We can dequeue the next element from a complete heap in time proportional to its height by 1 remembering the top node value first which will be returned later 2 moving the value lst from the last complete tree slot into the top node This maintains completeness of the tree but can violate the heap condition 03 bubbling last down77 by swapping it with the larger of its two children if one is greater than last until the heap condition is restored The result is a complete heap with one less element q returning the remembered value first Steps 17 27 4 take constant time and step 3 takes worst case time proportional to the height of the tree7 which is logn Complete Heap Dequeuing Example We will use the dequeuing algorithm speci ed above to dequeue all the elements from the complete heap that resulted from the enqueuing process bubbleD own bubbleD own A H H I delete E E A delete H delete delete H H G A 39 Complete Heap Dequeuing Code Here is Java code for dequeuing from a complete heap represented as a vector instance variable elts and comparator comp public Object deq if eltssize 0 throw new CollectionExceptionquotAttempt to deq empty queue quot else Dbject first eltsget0 Remember top value in heap Dbject last eltsremoveeltssize 1 Name last value in heap if eltssize gt 0 eltsset0 last Move last value to top of heap bubbleDown0 Bubble down from top of heap return first public void bubbleDown int addr int largest aderfLargestladdraddr aderfLargestraddraddr addr if largest addr swapaddr largest bubbleDownlargest Given a known valid complete heap index addr2 and a possibly invalid index addrl returns the index associated with the largest value if addr1 is valid or addr2 if addr1 is invalid public int aderfLargestltint addrl int addr2 if addrl lt eltssize ampamp greaterThanaddr1 addr2 return addrl else return addr2 Building a Complete Heap From a Vector It is often necessary to build a complete heap from a given collection of objects such as a vector array list etc For concreteness we will focus on building a complete heap from a vector What s an e icient way to do this A n logn approach An obvious approach is to simply enqueue all the elements from the vector oneby one into an initially empty complete heap Here s the code for such an approach public static MaxPQ fromVector Vector v MaxPQ pq new MaxPQCompleteHeapO Enumeration xs velements while xs hasMoreElementsO pq enqxs nextElementO return pq You should convince yourself that this takes time n logn for an n element vector A n approach An alternative approach is to use a copy of the given vector as the vector representing the complete heap and to bubble down77 elements starting at the next to last row of the heap and working up to the top row of the heap This ordering guarantees that by the time the bubbling down process is invoked at a node both subtrees are already guaranteed to be heaps So after the nal bubble down77 is performed at the root of the tree the tree is guaranteed to be a heap Here is the code for this approach public static MaxPQ fromVector Vector v MaxPQCompleteHeap pq new MaxPQCompleteHeap pqelts Vector vclone Note vsize 2 is the largest index of an element in the next to last level of the tree for int i vsize 2 2 i gt 0 i pqbubbleDowni return pq It turns out that the running time of this algorithm is n which is asymptotically faster than the obvious algorithm explored above Heapsort Revisited When using heapSort to sort a vector v it is possible to use v itself for the elements of the compelete heap rather than using a copy of v This leads to a version of heapSort that is mplace which means it uses only constant extra storage space in addition to the vector being sorted This idea will only work with max complete heaps Why won t it work for min complete heaps CS23O Data Structures Handout 24 Prof Lyn Turbak Monday December 9 2002 Wellesley College Heaps This is a revised version of the preliminary handout distributed on Tue Dec 3 The Many Meanings of Heap The word heap has several different common meanings in computer science 1 It is used as a synonym for an abstract priority queue 2 It is used to refer to a particular class of concrete implementations for a priority queue In this interpretation some priority queues are heaps and some are not which is at odds with meaning 1 9quot In a very different interpretation heap is commonly used to refer to the region of memory used for storing entities whose lifetime exceeds that of the execution frame in which they were created aka heap Object Land This is in contrast to the stack which is the region of memory used for storing entities whose lifetime is less than or equal to that of the execution frame in which they were created aka stack Execution Land Here we shall focus on interpretation 2 though 1 shall be implied in the term heapsort Heapsort Heapsort is a sorting algorithm based on priority queues Here is a generic form based on a max priority queue Modify vector to contain sorted elements from low to hi public static void heapSortMax Vector v Create a max pq MaxPQ pq new MaxPQZZZO Any MaxPQ implementation will do Insert all elements from vector into max pq for int i 0 i lt vsize i pqenqvgeti Store all elements in sorted order from max pq into vector for int i vsize 1 i gt 0 i Must go from highest index down vseti pqdeq Notes 0 This is easy to adapt to min priority queues How 0 In the above method the vector is assumed to contain Comparable elements However it can be easily adapted to take an explicit Comparator as an argument How 0 Later we shall see that a particular implementation of heapsort with max priority queues is particularly e icient Some people reserve the term heapsort for this particularly e icient version E iciency of Max PQ Operations What is the worstcase asymptotic running times of the following max pq operations for the speci ed implementations Assume ean der and first are invoked on an n element heap and heapSortO is invoked on an n element vector The Heap Condition For meaning 2 of heap a binary tree is a max heap if it satis es the following condition at every node in the tree Max Heap Condition The value of a node is 2 the values of all values in both subtrees Similarly a min heap satis es at every node a min heap condition in which the node value is S the values of all values in both subtrees Max Heap Example Consider the following integer tree T Running Times of Heap Operations What is the worst case time of first on a heap It turns out that we can make the worstcase time for ean and der proportional to the height of a heap What is the worstcase height of a heap with n nodes We would like to guarantee the worst case height of an n node heap is logn We shall study two restricted forms of heaps that satisfy this condition 1 complete heaps this lecture 2 leftist heaps next handout Binary Addresses We want to de ne a notion of completeness for a binary tree To do this7 it is rst helpful to de ne the binary address of a node in a binary tree 0 The address of the root of the tree is 1 o The root of the left subtree of node with address a has address 2 e a o The root of the right subtree of node with address a has address 2 e a 1 Here are the nodes of T annotated with binary addresses Binary addresses are relative to the chosen root Here are the nodes of the two subtrees of T annotated with binary addresses Complete Trees An n element binary tree is complete if the set of binary addresses of its nodes is the n element set 1 n Example Reconsider the tree T Note An n element binary tree is full if it is a complete tree of height h with 2h 7 1 nodes Which subtrees of T are full What s So Great About Complete Trees Complete trees have two important features 1 The height of an n node complete tree is logn in the worst case 2 Because the binary addresses cover the range 1 to 71 complete trees are easily represented as arraysvectors Eg7 in languages with 1 based array indexing 4 23 56 E Note In languages with O based array indexing the index is one less than the binary address Address Arithmetic For Complete Trees Complete Heaps A complete max heap is a binary tree that is both complete and a max heap Example Below are some sample complete max heaps containing the letters A L G D R I T H M S A letter later in the alphabet is considered greater than a letter earlier in the alphabet These are just some of the many possible complete heaps possible with this set of elements Complete Heap Enqueuing We can enqueue an element x onto a complete heap in time proportional to its height by inserting x in the next free complete tree slot This maintains completeness of the tree but can Violate the heap condition H I bubbling x up77 towards the root until the heap condition is restored The result is a complete heap with one more element Step 1 takes constant time and step 2 takes worstcase time proportional to the height of the tree7 which is logn Complete Heap Enqueuing Example Enqueue the letters A L G D R I T H M S into an initially empty complete max heap insert H Complete Heap Enqueuing Code Here is Java code for enqueuing onto a complete heap represented as a vector instance variable elts and comparator comp public void enq Object x eltsaddx Add x at next binary address bubbleUpeltssize 1 Bubble up from last binary address public void bubbleUp int addr while addr gt 0 ampamp greaterThanaddr paddraddr swapaddr paddraddr addr paddraddr public boolean greaterThan int addr1 int addr2 return compcompareeltsgetaddr1 eltsgetaddr2 gt 0 public void swap int addr1 int addr2 Dbject temp eltsgetaddr1 eltssetaddr1 eltsgetaddr2 eltssetaddr2 temp Complete Heap Dequeuing We can dequeue the next element from a complete heap in time proportional to its height by 1 remembering the top node value first which will be returned later 2 moving the value lst from the last complete tree slot into the top node This maintains completeness of the tree but can violate the heap condition 03 bubbling last down77 by swapping it with the larger of its two children if one is greater than last until the heap condition is restored The result is a complete heap with one less element q returning the remembered value first Steps 17 27 4 take constant time and step 3 takes worst case time proportional to the height of the tree7 which is logn Complete Heap Dequeuing Example We will use the dequeuing algorithm speci ed above to dequeue all the elements from the complete heap that resulted from the enqueuing process bubbl eD own bubbleD own A H bubbleD own A delete delete H H G A Complete Heap Dequeuing Code Here is Java code for dequeuing from a complete heap represented as a vector instance variable elts and comparator comp public Object deq if eltssize 0 throw new CollectionExceptionquotAttempt to deq empty queue quot else Dbject first eltsget0 Remember top value in heap Dbject last eltsremoveeltssize 1 Name last value in heap if eltssize gt O eltsset0 last Move last value to top of heap bubbleDown0 Bubble down from top of heap return first public void bubbleDown int addr int largest aderfLargestladdraddr aderfLargestraddraddr addr if largest addr swapaddr largest bubbleDownlargest Given a known valid complete heap index addr2 and a possibly invalid index addrl returns the index associated with the largest value if addr1 is valid or addr2 if addr1 is invalid public int aderfLargestltint addrl int addr2 if addrl lt eltssize ampamp greaterThanaddr1 addr2 return addrl else return addr2 Building a Complete Heap From a Vector It is often necessary to build a complete heap from a given collection of objects such as a vector array list etc For concreteness we will focus on building a complete heap from a vector What s an e icient way to do this A n logn approach An obvious approach is to simply enqueue all the elements from the vector oneby one into an initially empty complete heap Here s the code for such an approach public static MaxPQ fromVector Vector v MaxPQ pq new MaxPQCompleteHeapO Enumeration xs velements while xs hasMoreElementsO pq enqxs nextElementO return pq You should convince yourself that this takes time n logn for an n element vector A n approach An alternative approach is to use a copy of the given vector as the vector representing the complete heap and to bubble down77 elements starting at the next to last row of the heap and working up to the top row of the heap This ordering guarantees that by the time the bubbling down process is invoked at a node both subtrees are already guaranteed to be heaps So after the nal bubble down77 is performed at the root of the tree the tree is guaranteed to be a heap Here is the code for this approach public static MaxPQ fromVector Vector v MaxPQCompleteHeap pq new MaxPQCompleteHeap pqelts Vector vclone Note vsize 2 is the largest index of an element in the next to last level of the tree for int i vsize 2 2 i gt 0 i pqbubbleDowni return pq It turns out that the running time of this algorithm is n which is asymptotically faster than the obvious algorithm explored above Heapsort Revisited When using heapSort to sort a vector v it is possible to use v itself for the elements of the compelete heap rather than using a copy of v This leads to a version of heapSort that is mplace which means it uses only constant extra storage space in addition to the vector being sorted This idea will only work with max complete heaps Why won t it work for min complete heaps Leftist Trees Let the rank1 of a binary tree be the length of its right spine 7 ie the length of the rightmost path from the root to a leaf Example Nodes in the following tree are annotated with their ranks Call a binary tree leftist iff it satis es the following leftist condition for every subtree t of the tree rankleftt 2 rankrightt In the above example the subtrees rooted at T and S and necessarily all of their subtrees are leftist but the subtree rooted at M is not le st It is not di cult to show the following fact Let n be the number of nodes in a leftist tree and r be its rank Then T S lgn 1 It turns out that the time taken to enqueue an element onto dequeue and element from and merge a leftist tree with a leftist tree depend on the length of its right spine and so are proportional to its rank r By the above fact these operations on leftist trees are guaranteed to take only logarithmic time in the worst case Leftist Heaps A leftist max heap is simply a binary tree that is both leftist and a max heap Leftist min heaps are de ned similarly Example The following is one of the many leftist max heaps for the letters in the word ALGORITHMS To save on space explicit leaves have been omitted 1The term rank 7 is often used as a name for some relevant property of a data structure Ebractly which property it refers to depends on the particular data structure and what is trying to be proven 11 Combining Leftist Heaps Suppose that t1 with rank In and t2 with rank k2 are two leftist heaps and that 1 is a value that is 2 every value in t1 and t2 Then it is possible to glue t1 and t2 together with 1 to form a new leftist heap by choosing for 11 s left subtree the tree with the larger rank This process is shown diagrammatically below via rules for a question mark operator 7 that chooses the larger ranked tree for the left subtree o k1gtk2 k21 0 k1ltk2 k11 k1 k2 j k1 k2 k1 k2 gt k2 k1 Merging Leftist Heaps The core of most leftist heap operations is a merge function that merges two heaps along their right spines It is similar to the merge function used to merge sorted lists in mergesort Below are the rules for merging two leftist max heaps ZgtA A A A Given leftist heaps of size m and n the worstcase running time is the rightspine lengthm right spine lengthn logm logn Merging Example Below we show the merging of two leftist heaps one that contains the letters A L G D R and one that contains the letters I T H M S 2 1 11 2 1 11 Note how the leftist condition guarantees that the trees are skewed toward the left which means that the right spine tends to be short In the above example the result of merging two trees with a right spine length of 2 yields another tree with a right spine length of 21 Interestingly leftist trees are particularly ef cient when they are isomorphic to lists along the left spine and are least ef cient when they are balanced Dequeuing From a Leftist Heap Other priority queue operations are easy to implement with leftist heaps often in terms of merge For example To dequeue an element from a leftist heap remember the root value to return later and merge the two subtrees of the root node Example Dequeuing an element from the result of the merge on the previous page returns T and yields the following leftist heap2 Enqueuing Onto a Leftist Heap To enqueue an element x onto a leftist heap t merge a single tree containing x with t Example Enqueuing Q onto the result of the previous dequeue step yields the following leftist heap 2The notation gt indicates the application of potentially several rewrite steps whose intermediate results are not shown Building a Leftist Heap To build a leftist heap from a collection vectorarraylistetc of n elements they can be enqueued oneby one onto an initially empty leftist heap This takes time n logn in the worst case But a bottom up technique similar to that used in the e icient version of fromVector for complete heaps can be used to build a leftist heap in n time Here we illustrate the technique with the letters C D M P U T E R CS23O Data Structures Handout 37 Prof Lyn Turbak Thursday April 26 2007 Wellesley College Heaps The Many Meanings of Heap The word heap has several different common meanings in computer science 1 It is used as a synonym for an abstract priority queue 2 It is used to refer to a particular class of concrete implementations for a priority queue In this interpretation some priority queues are heaps and some are not which is at odds with meaning 1 9quot In a very different interpretation heap is commonly used to refer to the region of memory used for storing entities whose lifetime exceeds that of the execution frame in which they were created aka heap Object Land This is in contrast to the stack which is the region of memory used for storing entities whose lifetime is less than or equal to that of the execution frame in which they were created aka stack Execution Land Here we shall focus on interpretation 2 though 1 shall be implied in the term heapsort Heapsort Heapsort is a sorting algorithm based on priority queues Here is a generic implementation Modify vector to contain elements sorted from low to high public static ltTgt void heapSort VectorltTgt v ComparableltTgt comp 1 Create an empty priority queue any implementation will do PQueue pq new PQueueZZZltcomp 2 Insert all elements from vector into priority queue for int i 0 i lt vsize i pqenqvgeti Store all elements in sorted order from priority queue into vector for int i vsize1 i gt 0 i must go from highest index down vseti pqdeq Notes 0 We can supply any ComparatorltTgt to compare elements of type T By the PQueue contract supplying null for the comparator will use the ComparableltTgt compareToO method for comparisons if type T has one 0 Later we shall see that heapsort is particularly e icient if a certain implementation of priority queues is used Some people reserve the term heapsort for this particularly e icient version E iciency of Max PQ Operations What is the worstcase asymptotic running times of the following priority queue operations for the speci ed implementations Assume ean der and first are invoked on an n element heap7 and heapSortO is invoked on an n element vector The Heap Condition For meaning 2 of heap7 a binary tree is a max heap if it satis es the following condition at every node in the tree Max Heap Condition The value of a node is 2 the values of all nodes in both subtrees Similarly a min heap satis es at every node a min heap condition in which the node value is S the values of all values in both subtrees Max Heap Example Consider the following string tree T Running Times of Heap Operations What is the worst case running time of front on a heap with n nodes It turns out that we can make the worstcase time for ean and der proportional to the height of a heap What is the worstcase height of a heap with n nodes We would like to guarantee the worstcase height of an n node heap is logn In this lecture7 we study a restricted form of heap satisfying this condition the complete heap Binary Addresses We want to de ne a notion of completeness for a binary tree To do this7 it is rst helpful to de ne the binary address of a node in a binary tree 0 The address of the root of the tree is 1 o The root of the left subtree of node with address a has address 2 e a o The root of the right subtree of node with address a has address 2 e a 1 Here are the nodes of T annotated with binary addresses 7 Binary addresses are relative to the chosen root Here are the nodes of the two subtrees of T annotated with binary addresses Complete Trees An n element binary tree is complete if the set of binary addresses of its nodes is the n element set 1 n Example Reconsider the tree T Note An n element binary tree is full if it is a complete tree of height h with 2h 7 1 nodes Which subtrees of T are full What s So Great About Complete Trees Complete trees have two important features 1 The height of an n node complete tree is logn in the worst case 2 Because the binary addresses cover the range 1 to 71 complete trees are easily represented as arraysvectors Eg7 in languages with 1 based array indexing E 1 6 3 can be represented as the array 4 5 l3 6 Note In languages with O based array indexing eg7 Java and C7 the index is one less than the binary address 2 3 4 5 01 El Address Arithmetic For Complete Trees 2index Complete Heaps A complete max heap is a binary tree that is both complete and a max heap Example Below are some sample complete max heaps containing the letters A L G D R I T H M S These are just some of the many possible complete heaps possible with this set of elements Complete Heap Enqueuing We can enqueue an element x into a complete heap in time proportional to its height by H inserting x in the next free complete tree slot This maintains completeness of the tree but can Violate the heap condition I trickling x up77 towards the root until the heap condition is restored The result is a complete heap with one more element Step 1 takes constant time and step 2 takes worstcase time proportional to the height of the tree7 which is logn Complete Heap Enqueuing Example Enqueue the letters A L G D R I T H M S into an initially empty complete max heap insert insert H H A L trickleUp H insert H insert H Java Code for Complete Heap Enqueuing Here is Java code for enqueuing into a complete heap represented as a vector instance variable elts and comparator comp public void enq T x eltsaddx Add x at next binary address trickleUpeltssize 1 Trickle up from last binary address private void trickleUp int addr while addr gt 0 ampamp greaterThanaddr paddraddr swapaddr paddraddr addr paddraddr private boolean greaterThan int addr1 int addr2 return compareeltsgetaddr1 eltsgetaddr2 gt 0 private void swap int addr1 int addr2 T temp eltsgetaddr1 eltssetaddr1 eltsgetaddr2 eltssetaddr2 temp Complete Heap Dequeuing We can dequeue the next element from a complete heap in time proportional to its height by 1 remembering the top node value first which will be returned later 2 moving the value last from the last complete tree slot into the top node This maintains completeness of the tree but can violate the heap condition 9quot trickling last down77 by swapping it with the larger of its two children if one is greater than last until the heap condition is restored The result is a complete heap with one less element q returning the remembered value first Steps 17 27 4 take constant time and step 3 takes worst case time proportional to the height of the tree7 which is logn Complete Heap Dequeuing Example We will use the dequeuing algorithm speci ed above to dequeue all the elements from the complete heap that resulted from the enqueuing process trickleDoWn trickleDoWn H H delete H delete delete H H G A Java Code for Complete Heap Dequeuing Here is Java code for dequeuing from a complete heap represented as a vector instance variable elts and comparator comp public T deq if eltssize 0 throw new RuntimeExceptionquotAttempt to deq empty queue quot else T first eltsget0 Remember top value in hea T last eltsremoveeltssize 1 Name last value in heap if eltssize gt 0 eltsset0 last Move last value to top of heap trickleDown0 Trickle down from top of heap return first private void trickleDown int addr int largest aderfLargestladdraddr aderfLargestraddraddr addr if largest addr swapaddr largest trickleDownlargest Given a known valid complete heap index addr2 and a possibly invalid index addrl returns the index associated with the largest value if addr1 is valid or addr2 if addr1 is invalid private int aderfLargestltint addrl int addr2 if addrl lt eltssize ampamp greaterThanaddr1 addr2 return addrl else return addr2 Building a Complete Heap From a Vector It is often necessary to build a complete heap from a given collection of objects such as a vector array list etc For concreteness we will focus on building a complete heap from a vector What s an e icient way to do this A n logn approach An obvious approach is to simply enqueue all the elements from the vector oneby one into an initially empty complete heap Here s the code for such an approach public static ltTgt PQueueCompleteHeap ltTgt fromVectorInefficient VectorltTgt v PQueueCompleteHeapltTgt pq new PQueueCompleteHeapltTgt for int i 0 i lt vsize i pqenqvgeti return pq You should convince yourself that this takes time n logn for an n element vector A n approach An alternative approach is to use a copy of the given vector as the vector representing the complete heap and to trickle down77 elements starting at the next to last row of the heap and working up to the top row of the heap This ordering guarantees that by the time the trickling down process is invoked at a node both subtrees are already guaranteed to be heaps So after the nal trickle down77 is performed at the root of the tree the tree is guaranteed to be a heap Here is the code for this approach public static ltTgt PQueueCompleteHeapltTgt fromVector VectorltTgt v ComparatorltTgt comp PQueueCompleteHeapltTgt pq new PQueueCompleteHeapltTgtcomp pqelts VectorltTgt vclone pqbuildHeap return pq private void buildHeap Note vsize 2 is the largest index of an element in the next to last level of the tree for int i eltssize 2 2 i gt 0 i trickleDowni It turns out that the running time of this algorithm is n which is asymptotically faster than the obvious algorithm explored above See C8231 for the details Sometimes we want to re use the supplied vector for holding the elements of the priority queue public static ltTgt PQueueCompleteHeapltTgt fromVectorShared VectorltTgt v ComparatorltTgt comp PQueueCompleteHeapltTgt pq new PQueueCompleteHeapltTgtcomp pqelts v pqbuildHeap return pq Heapsort Revisited When using heapSort to sort a vector v7 it is possible to use v itself for the elements of the compelete heap rather than using a copy of v This leads to a version of heapSort that is mplace which means it uses only constant extra storage space in addition to the vector being sorted public static ltTgt void heapSortEfficient VectorltTgt v ComparatorltTgt comp PQueueCompleteHeapltTgt pq fromVectorSharedv comp for int i vsize1 1 gt 0 i vseti pq deq This idea will only work with max complete heaps Why won t it work for min complete heaps LessKnown Java Control Statements Q The Conditional operator O The SWITCH statement Q The DO loop 0 The infinite loop r The iterated FOR loop 42 Java s Conditional Operator Systemoutpr1ntln quotYour change 15 count count quotDimequot quotDimesquot e lts syntaxis condition expressionl expressionz lfthe condition is true expressionl is evaluated if it is false expressionz is evaluated 0 The value ofthe entire conditional operator is the value ofthe selected expression 43 Comparing Data When comparing data using boolean expressions it39s important to understand the nuances of certain data types Q Comparing integers is straight forward but how about comparing oating point values for equality comparing characters comparing strings alphabetical order comparing object vs comparing object references 43 Comparing Floats and Doubles kiwi 0 You should never use the equality operator when comparing two floating point values float or double 0 Two oating point values are equal only if their underlying binary representations match exactly 0 To determine the equality of two oats you may want to use the following technique if Mathabs 1 2 lt TOLERANCE s stemoutpint1n quotEssentially equalquot lfthe difference between the two oating point values is less than the TOLERANCE they are considered to be equal TOLERANCE could be set to an appropriate level ie 0000001 43 Comparing chars J 9 Java characters are based on the Unicode character set 0 Unicode establishes a aiticular numeric value for each character an therefore an ordering e For example the character 3939 is less than 39J39 because it comes before it in the Unicode character set In Unicode the digit characters 09 are contiguous and in order Likewise the uppercase letters A Z and lowercase letters az Climates Unicode Values are contiguous and In order 48 throug1157 A7 Z 651hmugh90 gvtmougmz 43 Comparing strings 39 gt Remember that in Java a character string is an object Q The equals method can be called with strings to determine if two strings contain exactly the same characters in the same order lt9 The equals method returns a Boolean result if namelequals name2 Systemoutprint1n quotSame namequot 43 Lexicographic Order if namelcompae39l oname2 lt 0 Systemoutpint1n namel quotcomes firstquot else if namelcompae39l oname2 0 Systemoutpint1n quotSame namequot else Systemoutpint1n name2 quotcomes firstquot x Lexicographic ordering is not strictly alphabetical w rcase and lowercase characters are mixed 9 For example quotGreatquot comes before the string quotfantastlcquot 0 Also short strings come before longer strings with the same prefix Therefore quotbookquot comes before quotbookcasequot 43 Comparing Objects e operator can be applied to objects it returns true if the two references are aliases ofeach other iii The equals method is de ned for all objects but unless we rede ne it when we write a class it has the same semantics as the operator has been rede ned in the Strlng class to compare the characters in the two strings When you write a class you should rede ne the equals method to return true underwhatever conditions are appropriate 44 The switch Statement switch Option 0 The expression of a switch statement MUST result in an Gas VA 39 integr type aCount break meamng an luteger case 39339 byteshort1nt long bCount or a char reek dafaulh 0 It CANNOT be a boolean untquot or a oating point Value 39 float or double 44 GradeReportjava Systelnoutprint quotEnter a numeric grade 0 to 100 v grade scannext1nt category 913 e o Systelnoltprint quotThat grade is v switch category case 10 Systemoutprintn A Excellent v break case 9 Systemoutpriutn a Very c0001quot break as a System out printh NC Good v ak Systemoutprintn quot1 Needs workquot re default Systemoutprintln F Not a passing gradequot 47 Comparing while and do IheJthilerLoop The do Loop int count 0 do t process count whilecount lt 5 45 Infinite Loops are An example of an in nite loop int count 1 while count lt 25 Systemoutprint1n count u 1 co nt count This loop will continue executing until interrupted ControlC or until an underflow error occurs But why would you ever use an infinite loop Another Infinite Loop 39 F 2Kfr by 31 Amend mm iar mm Mt mm W rr gt 521 Zquot Mr A G a quoteffnuannz 533 gtquot l 3 M MW my 9 W J 3mm 5 46 Iterators 0 An iteratoris an object that allows you to process a collection of items one at a time 0 An iterator object has a hasNext ethod that returns true if there is at least one more item to process 0 The next method returns the next item 0 The Scanner class is an iterator the hasNext method returns true ifthere is more data to be scanned the next method returns the next scanned token as a string e Scanner class also has variations on the hasNext method for speci c data types such as hasNextInt 46 URLDissectorjava fileScan new Scanner new Filequotwebsitesjnpquot Read and process each line of the file while fileScanhasnext url fileScan nextLineo Systemoutprintln 39WJRL w e url urlscan new Scanner url urLScan useDelimiter Vquot Print each art of the url whue urlScanhasNext Systemoutprintln v v e urlScannext Systemout printlno 48 Iterators and for Loops 7 A variant ofthe for loop simpli es the repetitive processing the items For example if BookList is an iteratorthat manages Book objects the following loop will print each boo for Book In Book BookL st Systemoutprint1n myBook 6 This style of for loop can be read quotfor each Book in BockList 0 Therefore the iteratorversion of the for 00 39 sometimes referred to as the foreach loop 0 It eliminates the need to call the hasNext and next methods explicitl 171 Binary Search Trees BSTs A Search tree is a tree Whose elements are organized to racililaie finding a paniculai elemen e A binary search tree is a binary tree llial roi eacli node n suurree or n oiilains Elements less man we element stared lrl n me iiglil suolree or ncoiilaiiis elements greatertnan ur equal nine element stared rl n 439 HOW do you Search for an elemem Binaiy Search trees can hold any type oi Comparable data 171 Adding an Element to a BST ext to add The shape of a binary Search tree depends on what 171 Degenerate Tree A grossly unbalanced tree with some long paths 0 When does it occur Why is it undesirable s 171 Removing an Element from a BST 4 Removing alargel iii a BST is iiol as simple as that for linear data Structures ller removing the elenieni the resulting ree rnlJSl Still be valid 4 What iryou remove 887 5m 607 3 gt simulom 41409 171 After the Root Node is Removed ltgt Draw Tree 2 valid con gurations 172 BST Implementation 4 2 The Elnarysearchl ree interface class adds support for add remove 51nd fmdmn and fmdmax 172 javafoundationsBinarySearohTree Hinaxyseazch39l xeejava Java medalinns mm m intexface u a hinaxy seaxch uquot package javafnundatinns puhlic inlexface BinnysenctheeltT extends Cmnpaxahleltrgtgt extends HinaxyTxeeltTgt mu m syecifiad element to m uquot public Wm add u dummy Find and xeunns m element in m u matching m specified lnqel nvexxides a find method of Hinazy39lxee public 139 find 1 may nun m minimum value in m hinaxy sench u public 139 findninn nun m maximum value in m hinaxy sench u public 139 nduaxu Remnves and leunns m sIecified element lam m L122 public 139 mm m anetb 172 javafoundationsBSTNode HS39Hlndejava Java Enundalinns Repxesenls a nude in a hinaxy seaxch an slnxinq Cnmyazahle ll elemms package j avafnllndalinns puhlic class nsmndeltw extends CnmyaxahlgltTgtgt extends Hmndeltwgt Cleales a new mg nude with m specified data pnhlic Bs39nrnde 11 12quotan I gummy max 41409 172 javafoundationsBSTNode Add a new nude containing the sneeifieu element at the apyxnyxiale place in this lxee mlAlia void add 11 item if litemcnmpaxe39l n1elemenl lt n if 1left mil U left new Hs39nlnde itemH lse HHS39nlndeuer add 1iteut else if light lull U light new Hs39nlnule 1itesnt EST ndeTliqhtbadd item max 172 javafoundationsBSTNode ll Retuxns the nude in this subtle whnse element matches the 5p cified lnxqel Reluxns null if the laxqel is nut In u H nvenides t e f nd methnd f B39 lnde t 31 n the hi y h haxaclexisl nuhlie Hsnlndeltwgt find 11 tngetp Hsnlndeltwgt xesull null if 1tuiet euuuuiewuelementp m iesult this els if llaxqelcmnpaxel n1elemznlb lt n if 1le t nullp xesult e HBSTIIndeDlerfind Hagen else if light mil ID xesllll Ulis lndeniqhthind unnetp 1 xetuin xesult max 172 javafoundationsBSTNode ll Remnves ee netuxns a the specified Laxqet fxnm this suhtx 39 12 The txee will he unchanged if H xefexence tn the xevised t the laxqel is nut fumed public nswhuueltwgt ienmveu LaxJen HSTllndeltTgt xesult this if Inqelcnmyatel39nlelemenl if 1le t xesull null 5 else if 1len e nuLl ampamp light e zesult Es39nlndebleflr II 5 else if 1len es nul in light I malt WW xesull msmuaepiiuht Situatinn 2 else ll Situatinn 3 esult yelSuccessan xesu1t12ft left i t light e light max 172 javafoundationsBSTNode else if 1tusuetemnnuiewu1elenentp lt m if 1le t nullp left 1BS39Hlndeblerxemnv tnqetb el t if light ig ndeyxiqhntemnv laxqelb null i ht 7 was xeunn xesult ll Find and xetuxns the nude II this nude and the cantain s the s H lunatinn in the t inq the innxdex successnl of n xemnve uccessnx lm its nxiqin pluteated HSTllndeltTgt yelSuccessan BST ndeltTgt succesqu e 1B5T nd9xiqht while lsuccessnxqeueft1 I successnx Es39 lndED s e null uccessnx Eethem p HHS39nlndehiqhtb xemnve 1s ccessnx getElemznt u p xeunn sueeessux 41409 172 javafoundationsLinkedBinarySearchTree Linkiniaaysaacmajava Java Foundations main m hinaxy Lxee using a linked xepxesenlalinn package j avafmlndalinns impuxt javafnundalinns impuxt javafnundalinnsexceylinns mlAlia class Linked inaxyseaxctheeltT xuna CmnpaxahleltTgtgt xuna Linked inatyTxeeltTgt implements HinnyseaxctheeltTgt cuau an Quirky hinaxy sench u public Linked inazySaxctheeH will max 172 javafoundationsLinkedBinarySearchTree cuau a hinaxy seaxch 19 with m specified element at its ll Knot puhlic Linked innysenxchl xee u elemenll xnnl new nsmndeltwgtlelemznln mid m specified element to this hinaxy sench u pnhlic void an 11 item i if lam mm in w BSTIlndeltTgtlitemH 1quot HHSTIlndelxwntladdlitemli max 172 javafoundationsLinkedBinarySearchTree Remnves and mu m element matching m specified anel fxmn mi hinaxy seaxch u Thxnws an Elemenulnli nundllxceplinn if m anel i not found public 139 mm m Inge HSTllndeltTgt node am if um I n and HS39HlndeyxnnLl findtaxqetl if 1mm null 0on new Elemenulnli nundllxceglinn imam upexatinn failed i We such 1 tans xnnl iinswuaaeiaamumaveuaiam xeunn nude qelElemenl i public 139 ndninll i public 139 findnaxll i i 173 Balanced Binary Search Trees j Q The flnd and add operations ofa balanced tree of n nodes have an ef ciency of Ologzn length of the longest path ltgt The more degenerate a tree becomes the 51nd and add operations approach On ltgt Our BST implementation does not guarantee a balanced tree The shape ofa BST is determined by the order which elements are added to the tree ltgt Othertypes of trees exist to ensure that they stay balanced ltgt They include AVL trees and redblack trees See animations at 41409 41409 173 Right Rotation zig 173 Left Rotation zag 13 5 7 15 3 10 7 13 5 10 3 15 173 zigzag Rotation 173 zagzig Rotation If the imbalance is Q If the imbalance is caused by a long path caused by a long path in the left subtree of in the right subtree of the right child of the s i the left child of the u 3 root we can address it u a root we can address it I a u by by performing a right 391 E perfon39ning a le El In El liq rotation around the El rotation around the ml m offen ing 5 tree Aluminium mmmm offs ing subtree mmmm mmmw and then performing a and then performing a lelt rotation around the right rotation around root Binary Trees Wellesley College C8230 Lecture 17 Thursday April 5 Handout 28 PS4 due 130pm Tuesday April 10 a um DATA Moflvaflon IneffICIency of Linear Sfr39ucfur39es TRU Up fo fhis poinf our focus has been linear sfrucfures arrays vecfors linked lisfs Some operafions on linear sfrucfures are cheap Consfanf fime Gefsef elf af a given index in arrayvecfor Add elf fo fhe end of a vecfor Add elf fo fhe fronf of a immufable lisf Add elf fo fhe back of a mufable lisf if have poinfer fo lasf node Logarifhmic fime Binary search on sorfed arrayvecfor ther operafions are expensive linear in size Inserfingdelefing elf af arbifr39ary posifion in an arrayvecforlisf Finding an elemenf in a lisf even a sorfed one There is no linear sfrucfure for which inserfion delefion and membership operafions eg in priorify queues sefs bags and fables are all cheaper fhan linear 172 Idea Branching of Binary Search I Ru Linking of Linked LisTs gt Binary Trees A binary Tree is ei rher a leaf 0 a node WM 1 a left sub rree 2 a value and 3 a right sub rree binary rree node lef r sub rree value righ r sub rree 99m A Sample Binary Tree Values are of ren shown in The nodes Offen The leaves are no r shown buf fhey re sfil fhere T T I ree ermmo ogy Nodes A and C are The children of node F F is The parenT of A and C A and C are siblings Grandparents grandchildren eTc defined similarly A node wiThouT a parenT is a rooT Eg node F is The rooT of The Tree and node A is The rooT of F39s lefT subTree considered separaTely from The whole Tree A descendanT of a node n is a node on The paTh from H To a leaf Eg nodes D B and E are The descendanTs of A An ancesTor of a node n is a node on The paTh from H To The rooT Eg Nodes B A and F are The ancesTors of E a um M T T I 5 ore ree ermmo ogy The heighT of a node n is lengTh of The longesT paTh from H To a leaf below iT Eg node 6 has heighT 1 node C has heighT 2 and node F has heighT 4 The depTh of a node n is The lengTh of The paTh from H To The rooT Eg node F has depTh 0 node C has depTh 1 and node 6 has depTh 2 A binary Tree is heighTbalanced iff aT every node n The heighTs of n s lefT and righT subTrees differ by no more Than 1 The example Tree is heighTbalanced buT would noT be if 6 were removed There are oTher noTions of Tree balance in C5231 SET Binary Search Trees V Ru To geT full advanTage of binary Trees for daTa sTrucTures need The values To be ordered A binary search Tree BST is a binary Tree in which The following properTies hold aT every node 1 All elemenTs in The lefT subTree are 3 The value 2 All elemenTs in The righT subTree are 2 The value Here is a sample BST gt BSTs will be very imporTanT in The nexT lecTure when we use binary Trees To implemenT daTa sTrucTures like seTs bags and Tables For now we39ll sTick wiTh generic binary Trees General Trees In general Trees can have any number of nodes Trees are used for many purposes Family Trees SporT TournamenTs Animal kingdom OrganizaTional charT A graph wiThouT cycles A home39s plumbing and elecTrical sysTems File sysTems DocumenT sTrucTure eg HTML Java class hierarchy RepresenTing an expressionprogram 99D D TA 1 Ari rhme ric Expressions as Tr39ees TRU a b a bc a b c A Ar39i rhme ric expressions are offen r39epr39esen red as binary Tr39ees Infernal nodes are operations Leaves are numbersvariables Oper39cn or precedence is enforced by The Tree shape MBi nTr39ee Contract 392 public s ra ric ltTgt MBinTreeltTgt leaf public sTa ric ltTgt boolean isLeafMBinTr39eeltTgt Tr public s ra ric ltTgt MBinTreeltTgt nodeMBinTr39eeltTgt If T val MBinTreeltTgt r r public sTa ric ltTgt T value MBinTr39eeltTgt 139r39 public s ra ric ltTgt MBinTreeltTgt lef r MBinTr39eeltTgt rr39 public s ra ric ltTgt MBinTreeltTgt righ r MBinTr39eeltTgt rr39 public sfa39ric ltTgt void se rValue MBinTr39eeltTgt rr39 T newValue public sTa ric ltTgt void se lLef r MBinTreeltTgt rr39 MBinTreeltTgt newLef r public sTa ric ltTgt void se rRigh r MBinTreeltTgt rr39 MBinTreeltTgt newRigh r 17710 5709 9K1 9amp1 lm Hashing lgSAM Pros and Cons TRU TRU To search for an enTry in The Table Pros compuTe The hash function on The enTry39s key Searching 0 InserTing O Use The value of The hash funcTion as DeleTing O an index inTo The Table Cons 39 Two or more keys may hash To The same index CannoT keep adding new elemenTs Then employ some meThod of collision resolurion Tabe size is fixed like an array Needs expansion capabiliTies cosle Would be nice To have a perfecT hashing funcTion buT many iTems may end up on same locaTion Colisions needs resoluTion policy WhaT properTies would we like in our hash funcTion If you do noT know N O b posiTive inTegers provide for dynamic resizing gillAg LOGCl FGCTOV gillAg WhaT Is a good Hash FuncTIon TRLJ 1quot Good NM load factor of a hashTable Brian hhOShC de hashCOde mad M number of enTries N in Table Mi prime divided by The Table capacity M 2 NoTe mod in Java noT The same as 7 3 4 Ellen BeTTer 39Heuris cs hh hC d h hC d b d d M o 5 Stella as o e a as o e mo p mo If you know N make M 15 N 6 Tabs p prime N 7 8 9 Cr39eaTe larger Hash Table InserT old elemenTs inTo new l l O H H c a Mark N 77 878 5709 W H sh 1 0 Add 5539 WTquot H 5h 2 L39 P b39 1 In on arra 3 en re In 1 In on arra I Inear ro In my 9 y P 9 my 9 y 9 39 When The index hashed To is occupied by a sTranger Open address39ng M gtgt N probe The nexT posiTion If ThaT posiTion is empTy we inserT The enTry oTherwise we probe The nexT posiTion and repeaT aa ab 22 l Lj l O 1 2 3 4 673 674 675 How are collisions are resolved wiTh This Technique H A s H I N G I s F U N 8 1 19 8 9 14 7 9 19 6 21 14 O 1 2 3 4 5 6 7 8 9 39IO AH 7 9b gkhh T here is a problem Though ClusTering SeparaTe Chaining As The Table begins To fill up quotBrianquot more and more enTries musT be examined before The desired enTry is found S reaquot quotEllenquot InserTIon of one enTry may greale increase The search Time for oThers quotLynquot For example consider H S H I quotMarkquot 0 1 quotquotTakisquot H A S H I N G I S F U N 2 8 1 l9 8 9 l4 7 9 l9 6 21 14 3 o 1 2 3 4 5 6 7 8 9 10 4 5 4509 6quot A STack as an AbsTr39acT DaTa Type f m 15 1 St k TRU Ruj ac 5 A sTack Addi ngan Removing LasTin fir39sTouT LIFO pr39oper39Ty Element anrelement The lasT iTem placed on The sTack will be The fir39sT iTem removed Analogy A sTack of dishes in a cafeTer39ia vs A queue Fir39sT in fir39sT ouT FIFO pr39oper39Ty The fir39sT iTem added is The fir39sT iTem To be removed Top Of stack Stack of cafeteria dishes vertical slice view H 1 1 2 H 2 lmAl Developing The STack ADT ATA public interface StackInterfaceltEgt TRU TRU Determines whether stack is empty ADT sTack oper aTions CreaTe an empTy sTack public boolean isEmpty Adds an item to the top of a stack DeTermine wheTher a sTack is empTy Add a new iTem To The sTack Public V id P ShE Hemmer Remove from The sTack The iTem ThaT was Removes the top of a stack added mos39 recenHy Exception Throws StackException if the stack is empty public E pop throws StackException ReTr39Ieve buT noT remove from The sTack The iTem ThaT was added mosT r ecenle Retrieves the t P f e Steek Exception Throws StackException if the stack is empty public E peek throws StackException 4509 99 o I Slmple Example Pr39ln l lng a S rack wu l houf deS l r39oylng l lquot returns a String representation of the contents of a Stack import java util For Java s Stack class from top to bottom assuming that the E on the Stack have the toString method public class Stack39I39est public String toString StackltEgt stk public Static veid main Create a temporary stack to hold contents of stk StackltStringgt stk new Stackltstringgt StackltEgt tempstack new StackltEgt stk push quotonequot String S quot Stkpushquot twoquot While stkempty E element stkpop Stk39p p S S elementtoString quot Stk puSh quot three quot tempStack push element System out println quot Contents of Stack using z quot S S II I restore contents of stk While tempStack empty stk push tempStack pop Wha l39 does sfk con l39ain return S How would we define toString H5 H6 ATA amp Advanced Example Checklhg for Balanced Braces g TA d Checking Balanced Braces Helper39 Me l hods T RLJ Tel J An example of balanced br39aces returns true if c is an open bracket Inputstrmg Stackasalgorithmexecutes public static boolean open bracket char c 1 2 3 4 return lt3 3939 II c 3939 II c 3939 II c 39lt39 abc 1pushquotquot Examples of unbalanced br39aces 2 push quotquot Too many braces returns true if c is a close bracket cde Too few closing braces Siackemptybalanced public static boolean close bracket char c fgh Misma39l39ching br39aces return lt2 39gt 39 II c 3939 II c 39139 II c 39gt39 b a C 1push quot 2 push quot apop returns the cloSing bracket matching the input open bracket Stacknotemptynotbalanced public static char matching bracket char c if c 39 39 return 39 39 abc else if c 39 39 return 39 39 139pUShI else if c 39 39 return 39 39 2p0p else return 39gt39 Stack emptywhen last quotquot encountered mot balanced H 7 H 8 99M DATA J Checking Balanced Br39aces Pseudocode TRLJ while still more chars to read get next char in the string if it is openbracket then push it on top of the stack if it is a closebracket pop char off stack check to see if it matches bracket What can go wrong H 99KB DATA J Checking Balanced Br39aces Pseudocode TRU Start by declaring string balanced so far while still more chars to read ampamp string balanced so far get next char in the string if it is openbracket then push it on top of the stack if it is a closebracket if stack empty gt not balanced pop char off stack check to see if it matches bracket if not matched gt not balanced Checking Balanced Br39aces T RLJ returns true if the string S has balanced open and closed brackets public static boolean isBalanced String S Stack ltCharactergt stk new Stack ltCharactergt int i 0 boolean balanced true char nextC top while balanced ampamp i lt Slength nextC ScharAti get the next character in the string if openbracketnextC push open brackets onto the stack stkpushnew CharacternextC else if closebracketnextC check whether the matching open bracket is on top of stack if stkempty balanced false else top stkpopcharValue if nextC matchingbrackettop balanced false abcdefg1jklmnopqr true i rue ltgt false return balanced ampamp stkempty lalsc H11 if stack not empty gt not balanced H 10 99KB DATA Implementations of the ADT Stack TRU The ADT stack can be a b c Implemented usung 30 30 30 An array Op Op Op A referencebased list 20 20 The ADT LinkedList W V 10 The ADT Vector39 Array 20 ADT StackInter39face quot Provides a common specification for39 quot the three implementations 10 StackException Used by StackInter39face Linked Extends java Iang RuntimeException H 12 4509 lt 9m 3AM public interface StackInterfaceltEgt TRU Determines whether stack is empty Precondition None Postcondition Returns true if the stack is empty otherwise returns false public boolean isEmpty Adds an item to the top of a stack Precondition newItem is the item to be added Postcondition If insertion is successful newItem is on top of the stack public void pushE newItem Removes the top of a stack Precondition None Postcondition If the stack is not empty the item that was added most recently is removed from the stack and returned Exception Throws StackException if the stack is empty public E pop throws StackException Retrieves the top of a stack Precondition None Postcondition If the stack is not empty the item that was added most recently is returned The stack is unchanged Exception Throws StackException if the stack is empty public E peek throws StackException S rackExcep rion TRL S rackExcep ri on Any Java me rhod Tha r implemen rs a s rackusing algori rhm should do one of The following Take precauTions To avoid an excep rion Provide Try and ca rch blocks To handle a possible excep rion file StackExceptionjava public class StackException extends javalangRuntimeException public StackExceptionString s supers just let my parent handle it end constructor end StackException SJJh ATA j An Army Based Implemen ra rlon S rackAr39rayBased class Implemen rs S rackIn rer39face Ins rances S racks Pr39iva re da ra fields An array of Objects called i rems The index Top top items K 5 13 7 I I I I 10 I I I I O 1 2 k MAXSTACK 1 4 Array indexes 9 public class StackArrayBasedltEgt implements StackInterfaceltEgt private ltEgt items Assumes top of stack is at itemsO public StackArrayBased public boolean isEmpty public void pushE newItem public E pop throws StackException public E peek throws StackException 4509 4509 An Implementation That Uses public class StackLinkedListBasedltEgt I RU The ADT LinkedLis r rRu implements StackInterfaceltEgt private LinkedListltEgt items Assumes top of stack is at position 0 ubl39 St kL nk dL39 tB d The ADT LinkedLIsT can be used To p items 2 LinkZLiEgt0 r epr esen r The items in a stack List position public boolean isEmpty How do we implement The stack ADT 1 10 T0 of stack return itemsisErcptyo eg push pop peek etc If The p elements of The stack are stored in a whim v ld puShE neWItem LinkedLisT 2 80 itemsadd0 newItem 3 60 public E pop throws StackException o if isEmpty return itemsremove0 else throw new StackExceptionquotStack Exception on pop stack emptyquot listsize 5 public E peek throws StackException if lisErrptyO return itemsget0 else throw new StackExceptionquotStack Exception on peek stack emptyquot H 17 H 18 A Client Pr39ogr39am Catching an Exception I RLJ W Ru public class StackTest public class StackTest public static void mainString args public static void mainString args StackLinkedListBasedltIntegergt stack StackLinkedListBasedltIntegergt stack new StackLinkedListBasedltIntegergt new StackLinkedListBasedltIntegergt for int i0 ilt10 i for int i0 ilt10 i stackpushi stackpushi end for end for for int j0 jlt15 j for int j0 jlt15 j try Systemoutprint1nstackpop Systemoutprintlnstackpop end for catch StackException ex Systemoutprint1nquotEmpty stacklquot end main break end for end main What s the problem What changes are needed 1f we do not want to use a LlnkedLlst 1mp1ementat135 1 10 gum ATA A ReferenceBased ImplemenTaTion TRU STackReferenceBased ImplemenTs STackInTerface Top is a reference To The head of a linked lisT of iTems 4 4 4 4 991 ATA 155 The JavauTIlSTack Class While iT conTains operaTions similar To a classic sTack iT conTains oTher differences Java uTil STack provides a search operaTion ThaT aTTemst To locaTe a TargeT elemenT reTurns iTs disTance from The Top of The sTack Java uTil STack is based upon The VecTor class which supporTs direcT access To elemenTs aT specific indices m The javauTilSTack Class The ova uTil STack class was deve oped mainly as a convenience javaJanngject A Much of The added funcTionaliTy comes Through inheriTance and inTerface implemenTaTion javaulilAbstrauCollenion A javautilAbstraclUst A javamtiereclor A A sTack is noT everyThing a VecTor is so iT is noT a proper isa relaTionship javauti5tnck IT also violaTes The premise of a welldeSIgned collecTIon class spush tem D E ltltinterfamgtgt EEEE39 39EE quot quot L I Lui empwoibomt n 1 searchIo Object int 9amp1 lm ImporTanT ApplicaTion ExecuTion STack TRU public int firstint a int b int c third n a sesame m rd public int secondint f second f g int 9 rd 9 thirdfrg rst a b C I rd public int thirdint m int n maln 1 1 return n public static void mainString args int i j Remember factorlal What happens Nhen you can fact5000007 Systemoutprintln firstij 4509 More Binary Trees Wellesley College C8230 Lecture 18 Monday Apn39l 9 Handout 29 PS4 due 130pm Tuesday April 10 iii Overview of Today s Lec rure TRU More pracTice wriTing binary Tree meThods Discussion of binary Tree Traversal MBi nTree Contract 392 Class me rhods public s ra ric ltTgt MBinTreeltTgt leaf public sfa ric ltTgt boolean isLeafMBinTreeltTgt Tr public s ra ric ltTgt MBinTreeltTgt nodeMBinTreeltTgt If T val MBinTreeltTgt r r public sfa ric ltTgt T value MBinTreeltTgt Tr public s ra ric ltTgt MBinTreeltTgt lef r MBinTreeltTgt rr public s ra ric ltTgt MBinTreeltTgt righ r MBinTreeltTgt rr public sfa ric ltTgt void se rValue MBinTreeltTgt rr T newValue public sfa ric ltTgt void se lLef r MBinTreeltTgt rr MBinTreeltTgt newLef r public sfa ric ltTgt void se rRigh r MBinTreeltTgt rr MBinTreeltTgt newRigh r There are o rher class me rhods like size copy fromS rringO and Traversal me lhods Ins rance me rhods public String l39oSl39ring 0 public boolean equals Objec r x public s ra ric ltTgt S rring ToS rring MBinTreeltTgt Tr roS rringF rre quot D A E B F C 5 quot Notes 1 The ToS rringO insfance me rhod is similar 2 There is an quotinversequot me rhod public sfa ric MBinTreeltSTringgt fromS lringS rring s 187 99D DATA Making a Shallow Copy of a Tree V Ru copyF rr39ee public s ra ric ltTgt MBinTreeltTgt copy MBinTr eeltTgt rr39 agbm 5 NonDestructive Mapping Example mapLower CaseNDF rr ee public sTa ric MBinTreeltSTringgt mapLower39CaseND MBinTr eeltS rr inggt Tr 9K1 Des rr39uc rive Mapping Example S ra re of F rr ee offer mapLower CaseDF rr ee F rr ee l3 gt public sTa ric void mapLower39CaseD MBinTr eeltS rr inggt Tr lt33quot TRU Tr ee Cr ea rion heigh rTr39eeO heigh rTr ee3 a Wi rh sharing can use fewer nodes heigh rTr ee3 g public sTa ric MBinTreeltInfegergt heigh rTr39ee in r h r Tree Creation TRU dep rhTree dep rhTree3 gt i Wi rh sharing can use fewer nodes dep rhTree3 gt public s ra ric MBinTreeltInTegergt dep rhTree in r h r re rurn dep rhTreeDep rh0h r Helper me rhod wi rh ex rra argumen r public s ra ric MBinTreeltInTegergt dep rhTreeDep rh in r dep rh in r h r bread rhTreeO The Tree values in bread rhTreeO are The binary addresses of The nodes public s ra ric MBinTreeltInTegergt bread rhTree in r n re rurn bread rhTreeAux1n Helper me rhod public s ra ric MBinTreeltInTegergt bread rhTreeAux in r roo r in r n 1R7 Q gD ATKZQ Binary Tree Traversal V Ru preOrderPrin rFree inOrderPrinTF rree posTOrderPrinTFree breadThOrderPrinTFTree 18711 C8230 Jeopardy Fall 2002 Gameboard Asymptotics Rilg Gotchas Lists Trees Potpourri 1 1 1 1 1 1 2 2 2 2 2 2 3 3 3 3 3 3 4 4 4 4 4 4 5 5 5 5 5 5 08230 Jeopardy Fall 02 p233 Asymptotics 1 Consider the function fn 3n 7 List all of the following sets that do not contain f Back 08230 Jeopardy Fall 02 p333 Asymptotics 2 List the following eight asymptotic complexity Classes in order from smallest to largest 90 91 3 n 10gn 910gn 9012 9013 92 Back 08230 Jeopardy Fall 02 p433 Asymptotics 3 Give the asymptotic complexity class ie 9 notation for the best algorithm we have studied for each of the following problems a Inserting n elements one at a time into a sorted array b Popping the top element off of a stack of n elements c Searching for an element in a balanced binary tree c Sorting a list ofn elements e Deleting an element from a balanced binary search tree Back 08230 Jeopardy Fall 02 p533 Asymptotics 4 Match up each of the following algorithms with the recurrence equation that best characterizes it Back binary search linear search merge sort selection sort towers of Hanoi T1n1T1n 1 T2n12 gtiltT2n 1 T3n nT3n 1 T401 1T4n2 T5n n2gtiltT5n2 08230 Jeopardy Fall 02 p633 Asymptotics 5 List all of the following recurrence equations whose solution is n 08230 Jeopardy Fall 02 p733 RunningTimes 1 Which of the following sorting algorithms have n logn running times in the worst case a selection sort b merge sort c quick sort d insertion sort e heap sort using a complete heap f tree sort ie build a BST and list elements in inorder Back 08230 Jeopardy Fall 02 p833 RunningTimes 2 List all of the following that can be done in lineartime in the worst case a Determining ifx is in a lengthn list b Sorting a list ofn elements c Building a BST from a list ofn elements d Listing in sorted order all elements of an nelement BST e Building a complete heap from a vector ofn elements f Listing in sorted order all elements of an nelement complete heap Back 08230 Jeopardy Fall 02 p933 RunningTimes 3 List all of the following that can be done in logarithmic time in the worst case a Determining if 90 is in an array b Determining if 90 is in a sorted vector c Determining if 90 is in a balanced binary tree d Determining if 90 is in a balanced binary search tree e Inserting 90 into a complete heap f Deleting 90 from a leftist heap g Merging two complete heaps h Merging two leftist heaps Back 08230 Jeopardy Fall 02 p1033 RunningTimes 4 Consider the following method public static IntList inOrderList IntTree t if ITisLeaf return ILempty else return ILappendinOrderListITleft ILprependITvalue inOrderListITrightt t t For each of the following assumptions write a recurrence equation describes the worst running time of the method and give the asymptotic solution of the equation 1 t is a balanced tree 2 t is an arbitrary tree Back 08230 Jeopardy Fall 02 p1133 RunningTimes 5 1 Write a recurrence equation for the worst case running time of the following method 2 give the asympotic solution of the equation and 3 describe a simple modification to the method that dramatically improves its asymptotic runmngtkne public static int f ObjectList L if ILisEmpty return 0 else return ILlengthLILlengthL fILtailL Back 08230 Jeopardy Fall 02 p1233 Gotchas 1 What is the bug in the following Java method public int sum Vector v intsO for int i O i lt Vsize i s s vgeti return 5 Back 08230 Jeopardy Fall 02 p1333 Gotchas 2 What is the bug in the following Java Class public class Location private Point where public Location Point where w public int X return wherex Point w I Back 08230 Jeopardy Fall 02 p1433 Gotchas 3 What is the bug in the following Java method public static int toInt Object X if X instanceof Integer return XintValue else return 0 Back 08230 Jeopardy Fall 02 p1533 Gotchas 4 Draw a binary tree that is not a binary search tree but for which the following buggy isBST method returns true INCORRECT version of isBST public static boolean isBST IntTree t return ITisLeaft ITisLeafITleftt ITValuet gt ITValueITleftt ampamp isBSTITleftt ampamp ITisLeafITrightt ITValuet lt ITValueITrightt ampamp isBSTITrightt Back 08230 Jeopardy Fall 02 p1633 Gotchas 5 What output is displayed by the following Java method when invoked on the following vector of strings a b C d e public static void removeAndDisplay Vector v for int i O i lt vsize i Systemoutprintlnvremovei Back 08230 Jeopardy Fall 02 p1733 Lists 1 Several data structure implementations we have studied have instance variables that are mutable lists with dummy header nodes What is the purpose of the dummy header node Back 08230 Jeopardy Fall 02 p1833 Lists 2 What is wrong with the following method for testing if an integer list is sorted public static boolean isSorted IntList L return ILisEmptyL ILheadL lt ILheadILtailL ampamp isSortedILtailL Back 08230 Jeopardy Fall 02 31933 Lists 3 Describe 1 one advantage of a mutable list over an immutable list and 2 one advantage of an immutable list overanu amelbt Back 08230 Jeopardy Fall 02 p2033 Lists 3 Describe 1 one advantage of a mutable list over an immutable list and 2 one advantage of an immutable list overanu amelbt Back 08230 Jeopardy Fall 02 p2133 Lists 4 Flesh out the body of the following method for turning a nonempty noncyclic mutabe list into a cyclic list ie a list whose last node s tail points to its first node public static void cylcify ObjectMList L flesh this out Back 08230 Jeopardy Fall 02 p2233 Lists 5 Answer both of the following 1 what is the running time of the following method on a list of length n 2 rewrite the body of the method so that it has the same behavior but has an asymptotically better running time public static IntList revDouble IntList L if ILisEmptyL return L else ILpostpendrevDoubleILtai1L 2ILheadL Back 08230 Jeopardy Fall 02 p2333 Trees 1 List the values of all nodes in the following tree at which the heap condition is not satisfied x J 8 Back 08230 Jeopardy Fall 02 p2433 Trees 2 List the values of all nodes in the following tree at which the binary search tree condition is not satisfied A Back 08230 Jeopardy Fall 02 p2533 Trees 3 List the values of all nodes in the following tree at which the leftist condition is not satisfied A Back 08230 Jeopardy Fall 02 p2633 Trees 4 Draw the tree that results from dequeuing an element from the following complete heap a Will Back 08230 Jeopardy Fall 02 p2733 Trees 5 For every n is it possible that all the distinct integers in Ln can be arranged into a single binary tree that is both a BST and a leftist heap Assume that larger numbers have higher priority Back 08230 Jeopardy Fall 02 p2833 Potpourri 1 List all of the following collections for which a balanced binary search tree is an efficient representation bag priority queue queue set stack taMe bbbbbb Back 08230 Jeopardy Fall 02 p2933 Potpourri 2 For each of the following reallife collections give the data structure that would most appropriately model the situation cities visited during a trip bag dictionary entries priority queue emergency room waiting area queue pile of papers set shopping cart of grocery items stack supermarket checkout ine table Back 08230 Jeopardy Fall 02 p3033 Potpourri 3 Match up each of the following collections with the data structure that is most appropriate for representing it Back priority queue queue sequence set stack 23 tree cyclic linked list leftist heap noncyclic linked list vector 08230 Jeopardy Fall 02 p3133 Potpourri 4 Answer both of the following 1 Is every complete heap a leftist heap 2 Is every leftist heap a complete heap Back 08230 Jeopardy Fall 02 p3233 Potpourri 5 What is the largest n such that all the distinct integers in Ln can be arranged into a single binary tree that is both a BST and max complete heap Back 08230 Jeopardy Fall 02 p3333 61 GUI Elements Commandline applications interact with the user through simple prompts and feedback but they lack the rich user experience With GUI the user is not limited to responding to prompts in a particular order and receiving feedback in one place Three kinds of objects are needed to create a GUI in Java componen events listeners 61 Components Events Listeners ltgt Component de nes a screen element used to display information or allow the userto interact with the program A containeris a special type of component that is used to hold and organize other components Event an object that represents some occurrence in which we may be interested Often correspond to user ac ions mouse button press key press Most GUI components generate events to indicate a user action related to that componen Program that is oriented around GUI responding to user events is called 9V9 Ne Listener an object that waits for an event to occur and respon s in way when it does In designing a GUIbased program we need to establish the relationships between the listener the event it listens for and e component hat generates the event 61 GUI Elements ltgt To create a Java program that uses a GUI we must instantiate and set up the necessary components implement listener classes that de ne what happens when particular events occur and establish the relationship between the listeners and the components that generate the events of interest Java components and other GUIrelated classes are defined primarily in two packages javaawt javaxswing 7 A variety of interactive components r e 62 Components Buttons 7 nfcnu s text elds elnout from lltevooalo check Was 7 a button tnat can be toggled on or on uslng tne rnouse llnolcates a boolearl value ls set or set raurn outtnns eto orovloe a set of rnutuallv excluslve ootlons lruers e speclrv a nurnenc valtle Within a bounded range es 7 select one of several ootlons from a drop down rnenu 3209 63 Layout Managers Q Every container is managed by a layout managerobject that determines how the components in the container are arranged visu all Every container has a default layout manager but we can replace it if desired Q The layout manager is consulted when needed such as when the container is resized or when a component is added Q A layout manager determines the size and position of each component Every layout manager has its own rules and properties governing the layout ofthe components it contains For some layout managers the order in which you add the components affects their positioning Q Q 63 Predefined Layout Managers mlm M7 7 Border Layout Organlzes components into ve areas North South East West and Center Box Layout Organizes components into a single row ot co1umn Tabbed Layout Organizes components into one area such that only one area is visible at a time Flow Layout Organizes components from left to right starting new rows as necess Gnu Layout Organizes components into a grid of rows and co umns Layout Manag Demo Flow Holder 1 oni 63 Flow Layout Q The easiest layout managers to use Q The JPanel class uses ow layout by default Q Puts as many components as possible on a row at their preferred size Q When a component can not t on a row it is put on the next row 63 Border Layout Q A borderlayout has ve hymn wanauu um wan t tn mn39mN 7 l IUWON 1 nurrou 4 component they contain If no components are added to a region the region takes up no room in the ovelall layout Q Q The Center area expands to ll any available space 3209 63 Grid Layout A v ummmqwm components in a rectangular grid of rows and co umns One component in each cell all cells are the same size The umb f columns in a grid layout is established by using parameters to he constructor when he layout manager is created nents are added to the grid layout hey ll the grid from left to right top to bottom No way to explicitly assign a a a n hthManaar nn n n a mquot rm m w amquot am Bax mm H mm c lt9gt r r Iuca iun other han the order in which they I are added to the container I H mm i 63 Box Layout A box layout organizes components eithervertically or horizontally i one row or one column It is easy to use and when combined with other layout managers can produce complex GUI designs Components are organized y in the order in which the are a e tot e container There are no gaps between the components in a box layout Q r mrrmua 63 Containment Hierarchies Q The way components are grouped into containers and the way those containers are nested within each other establishes the containment hierarchy for a GUI For any Java GUI program there is generally one primary toplevel container such as a frame or pplet Q The toplevel container often contains one or more containers such as panels These panels may contain other panels to organize the other components as desired 67 GUI Design Keep in mind our goal is to solve a problem Q Fundamental ideas of good GUI design include knowing the user preventing user errors optimizing user abilities being consistent We should design interfaces so that the user can make as few mistakes as possible 3209 C5230 Data Structures Handout 33 Prof Lyn Turbak Thursday April 19 2007 Wellesley College RECURRENCES Overview of Today s Lecture Recurrence equations a tool for analyzing algorithms Applications of recurrence equations TwoStep Strategy for Analyzing Algorithms 1 Characterize runningitime space etc of algorithm by a recurrence equation 2 Solve the recurrence equation expressing answer in asymptotic notation Recurrence Equations A recurrence equation is just a recursive function definition It defines a function at one input in terms of its value on smaller inputs We use recurrence equations to characterize the running time of algorithms Tn typically stands for the runningitime of a given algorithm on an input of size n for a particular case worsticase by default but could be averageicase or best case Recurrence equations for divideiandiconquer algorithms typically have the form General Case n 2 I Tn afsubprablems T 3126 afeach subprablemh cast afdivideampglue Base Case n lt I Tn 0 Because the base case is always the same it is usually omitted When defining Tn Deriving Recurrence Equations Examples 1 InseIt an element into a sorted list of a tree not a BST with n numen39c n a n that the BST remains balanced a element x multiply each node n on the to x by the sum of the elements in the Solving Recurrence Equations The RecursionTree Method We will use the recursiontree method for solving recurrence equations C8231 covers other approaches 1 Construct a recursion tree by unwinding the recurrence equation 2 Determine the cost of the entire tree by summing the costs of the nodes Recurrence 1 Tn Tn 1 1 Also derivable Tn 7 1 Tn 7 2 1 Tn72Tn73 1 cost of nodes number of nodes n Recurrence 2 Tn Tn 1 n Also derivable Tn7 1 Tn7 2 n 7 1 Tn72Tn73 n72 n 1eve1s II Total cost of nodes 1 2 3 n 7 2 n 7 1 n E k Arithmetic series see below k1 3 Arithmetic Series A series is arithmetic if ak c a0 Trick Sum corresponding pairs of numbers Examples N o 123n I 0 Sum offirstn elements of series7 10 13 16 Analyu39ng Insertion Sort N O R T Idea On the ith step of the algorithm insert A i into the sorted segment A 1 1 1 0 Invariant After the ith step of the algorithm A 1 i is sorted Matching Theoretical Results with Performance Numbers for Insertion Sort Timings for insertion sort on Java vectors in milliseconds ll Analyu39ng Selection Sort Idea On the ith step of the algorithm store into A i the smallest element of A i n Invariant After step i the elements A 1 i are in their final sorted Dositions Performance Numbers for Selection Sort Timings for selection sort on Java vectors in milliseconds ll Recurrence 3 Tn Tn2 1 Also de vable TnZ Tn4 l Tn 4 Toys 1 etc E w a lgn 1 levels 6 Total cost of nodes number of nodes lgn 1 lggnl 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 7 Information Servises Com In em We start with one Tn node and In this handout we use lgn to stand for log2n number of times n can besuocessively divided by 2 The later quantity is lgn including the Recurrence 4 Tn Inn2 n generaed by the original Tn node gives lgn 1 nodes Also de vable TnZ 2Tn4 112 Tm4 2Tn8 m4 level 1 Total cost nnumber of levels nlgn l n lgn Recurrence 5 Tn 2Tn2 1 Also de vable TnZ 2Tn4 l Tm4 2Tn8 1 level lgn l Total cost number of nodes sum of nodes at each level l 2 4 8 21 quot Geometric sen39es See below 1gn 2k k0 Geometric Series A series is geometric if ak c ak1 LetSnstandforaocka0 aoca002a06 aocquot k Nate carefully Sn has n1 terms not H terms Notice the following 0811 aoca002a0c5aocquota0 CW1 78na0 aocaocza0 aocquot c 71Sna0 CW1 iao a0cquot171 If 0 lt c lt 1 and n 600 the above formula can be rewritten as Examples 12482quot 124821gltngt 12 14 18 13 19 127 Paper tearing example Analyu39ng Merge Sort U I N S I O R I T E I D Idea Recursively sort subarrays and then merge a El them into a single sorted array Performance Numbers for Merge Sort Timings for merge sort on Java vectors in milliseconds ll Analyu39ng Quick Sort 1 CKSRT Idea a Choose AO as the pivot a Step 1 Partition A into two subarrays by moving elements in A a 52 1 65565 all elements lt pivot 7 E R S The lesses subarray should occupy the left portion of A M and greaters should occupy the right portion of A 71 2 greaters all elements gt pivot One way to partition is to use two fingers moving inward starting at opposite ends of arrays and swapping when left element is gt pivot and right element is lt pivot Performance Numbers for Quick Sort Tirnings for quick sort on Java vectors in milliseconds ll Recurrence 6 Tn Tn 1 lgn Also de vable Tnil Tn72 1gn71 Tn72 Tn73 1gn72 Picture goes here Tn 1gn 1gn71 1gn72 1g2 1g1 1gn n71 n72 3 2 1 Because lgm lgb loga b 1gn 1gn z n1gn by Stirling s approximation Analyu39ng Tree Sort Picture goes here Idea Insert A s elements oneibyione into a binary search tree When done read elements back into A via an in order traversal Performance Numbers for Tree Sort Timings for tree sort on Java vectors in milliseconds ll Recurrence 7 Tn Tn2 11 Also de vable TnZ Tn4 112 Tm4 Tms m4 lgn m Total costnn2n4n21 quot lt 22 k0 Recurrence 8 Tn 2Tn 1 1 Also de vable Tnil 2T1172 1 T1172 2T1173 1 w I gr 39139 mgr LquotT 11L 39K 1 ft f fa ia TI39FT Total cost 1 2 4 2 Summary The following table summarizes and generalizes the above examples Equivalence classes of functions are arranged in the table from quotbiggestquot to quotsmallestquot That is if function f appears above function g in the table then g is Of but f is not Og or equivalently f is Qg but g is not Qf It is worth noting that there are many more equivalence classes than are listed in the table but the ones in the table are the ones most commonly encountered in this comse r Tn Tnia logn a gt 1 7 11gt agt gt or Tn kTn7ak b k gt 1 a gt O b gt O or base of log is Se rs Bags and Tables Wellesley College C8230 Lecture 13 Thursday March 15 Handout 23 Exam 1 due Friday March 16 39 g TA j Overview of Today s Lec rure 1 SeTs concepTually unordered collecTions of elemenTs wiThouT duplicaTes buT may need order on elemenTs To implemenT efficienle 2 Bags concepTually unordered collecTions of elemenTs wiTh duplicaTes 3 Tables associaTions of keys and values ask RARAM MaThemaTical SeTs R In maThemaTics a seT is an unordered collecTion of elemenTs wo duplicaTes A seT is wriTTen by enumeraTing iTs elemenTs beTween braces Eg The empTy seT wiTh no elemenTs is wriTTen InserTion inserTs an elemenT inTo a seT if iT39s noT already There inserT aquot D quotaquot inserT bquot quotaquot quotaquot bquot quotbquot aquot order is irrelevanT inSerI139llalll Haul Ilbll Haul Ilbll Hle Hall inSerI139llclll Ialllllb Haul b IICH Halli CHI Ilbll Hle Hall IICH Hle C Hall IICHI all Ilbll IICHI b Hall DeleTion removes an elemenT if iT39s in The seT deleTe aquot U deeella l Haul llbll II bu deeellb l Halli llbll Hall deeellc l Halli Ilbll Haul Ilbll Size CardinaliTy ISI is The number of elemenTs in S ICIGH uaul ubu uaul llblll llcll 1373 9 EAl3 More SeTs i2 Membership x E S is True if x is in The seT S and false oTherwise quotaquot E false quotaquot E quotaquot bquot True quotcquot E quotaquot bquot false SubseT 51 Q 52 is True if all elemenTs in 51 are also in 2 Q quotaquot bquot is True quotaquot Q quotaquot bquot is True quotbquot Q aquot bquot is True quotaquot bquot Q quotaquot bquot is True quotaquot bquot Q quotaquot is false quotaquot Q is false Union 51 U 52 all elemenTs in aT leasT one of 1 and 52 quotaquot equot U quotbquot fquot quotaquot quotequot fquot InTersecTion39 1 052 all elemenTs in aT boTh 51 and 52 quotaquot equot O quotbquot fquot quotbquot dquot Difference 51 52 or 5152 all elemenTs in 51 ThaT are noT in 52 quotaquot equot quotbquot fquot quotaquot equot 99D DATA A SeT InTerface in Java ParT 1 TRU InTerface To muTable seTs of elemenTs of Type T A seT is an unordered collecTion ThaT does noT conTain duplicaTe elemenTs WARNING This is differenT Than The sTandard JavauTilSeT inTerface imporT JavauTil imporT ITeraTor ITerable public inTerface SeTltTgt exTends ITerableltTgt public boolean inserT T x InserTs x inTo This seT reTurns True if new member public boolean deleTe T x DeleTes x from This seT reTurns True if successful public boolean isMemberT x ReTurns True if x is a member of This seT else false public T choose ReTurns an arbiTrary elT from This collecTion Throws RunTimeExcepTion if empTy public T deleTeOne DeleTes and reTurns an arbiTrary elT from This collecTion Throws RunTimeExcepTion if empTy public void union SeTltTgt s Modify This seT To conTain The union of iTs elemenTs wiTh Those of s public void inTersecTion SeTltTgt s Modify This seT To conTain The inTersecTion of iTs elemenTs wiTh Those of s public void difference SeTltTgt s Modify This seT To conTain The difference of iTs elemenTs wiTh Those of s more meThods on nexT page 99K DATAh A SeT InTerface in Java ParT 2 TRU The remaining SeT meThods are similar To STack Queue PQueue meThods public inT size ReTurns The number of elemenTs in This seT public boolean isEmpTy ReTurns True if This seT empTy false oTherwise public void clear Removes all elemeTs from This seT public SeTltTgt copy ReTurns a quotshallowquot copy of This seT public ITeraTorltTgt iTeraTor ReTurns an iTeraTor yielding The elemenTs of This seT public STring ToSTring ReTurns a sTring indicaTing Type and conTenTs of This seT The elemenTs may be lisTed in any order J 9539 h g DATA How to Implement A Set TRU As a sorted vector How long does isMemberO take insert As a sorted list How long does isMember take insert 9U llM Mathematical Bags MultiSets I Rd In mathematics a bag multiset is an unordered collection of elements with duplicates A bag is written by enumerating its elements with duplicates between braces Eg the empty bag with no elements is written 0 The bag with one quotaquot is written quotaquot quotaquot The bag with two quotaquots is written quotaquot quotaquot Most set notions insertion deletion membership subset union intersection difference cardinality generalize to bags as long as duplicates are accounted for Eg39 insertquotaquot quotaquot bquot quotaquot bquot quotaquot quotaquot bquot quotaquot deletequotaquot quotGquot quotGquot quotGquot quotbquot quotCquot quotCHD quot0quot quotGquot quotbquot quotCquot quotCquot quotaquot bquot g quotaquot bquot true quotaquot bquot g quotaquot bquot false quotaquot dquot u quotaquot quotdquot quotequot quotaquot d d quotequot quotaquot quotcquot m quotaquot bquot quotaquot bquot quotaquot quotcquot quotaquot bquot quotaquot quotcquot uaul an an bu cu llcll 6 138 99D QATA New Bag OperaTions l2 MulTipliciTy39 we shall wriTe xB my nonsTandard noTaTion for The number of occurrences of elemenT x in bag B aka The mulTipliciTy of x in B Ilallllla l Ilaquot b C IICH aquot BI 3 bquot BI 1 cquot Bl 2 dquot BI O DeleTeAll deleTexB deleTes one occurrence of x from B SomeTimes we wanT To deleTe all occurrences of x from B For This we use deleTeAllxB deeella l Haul all all b C IICH Hall Illaquot b C IICH deleTeAlla l Haul all all b C IICH Ibquot CHI IICH deleTeAlld l Haul all all b C IICH Haul all all b C IICH CounTDisTincT39 IBI counTs all elemenT occurrences in B including duplicaTes SomeTimes we wanT jusT The number of disTincT elemenTs For This we use counTDisTincTB uaul an an llblll cu llcll 6 counfbisfincfuaul an an llblll cu llcll 3 1379 9U gillA A Bag InTer39face in Java I pth InTerface To muTable bags of elemenTs of Type T A bag is an unordered collecTion ThaT does noT conTain duplicaTe elemenTs imporT javauTil imporT ITeraTor ITerable public inTerface BagltTgt exTends ITerableltTgt MeThods ThaT are new To bags public inT mulTipliciTy T x ReTurn The mulTipliciTy of x in This bag public void deleTeAll T x DeleTe all occurrences of x in This bag public inT counTDisTincT O ReTurn The number of disTincT elemenTs in This bag public ITeraTorltTgt disTincTElemenTs O ReTurn an iTeraTor yielding The disTincT elemenTs of This bag All The remaining meThods of BagltTgt are Those of SeTltTgt oTher meThods go here 13710 99D QATAy Bags are noT SeTs R Why noT use inheriTance To relaTe BagltTgt and SeTltTgt public inTerface BagltTgt exTends SeTltTgt public inT mulTipliciTy T x ReTurn The mulTipliciTy of x in This bag oTher bagspecific meThods Because bags generally don39T behave like seTs A bag insTance cannoT always be used where a seT is expecTed For example public sTaTic boolean isITASeT SeTltSTringgt s sdeeTe fooquot reTurn sisMember fooquot isITASeTO should reTurn True for every seT BuT iT will reTurn false for a bag ThaT conTains more Than one occurrence of quotfooquot A bag impemenfafion mighT inheriT meThods from a seT impemenfafion BuT The Type of a bag is differenT Than The Type of a seT 13711 subh llM j Bag Example Word Frequencies TRU PrinT The frequencies of words in The give file in alphabeTical order public sTaTic void frequencies STring filename 13712 99D QM5 Digression Ordered SeTs and Bags R SeTs and bags are unordered collecTions of elemenTs However we can also have ordered noTions of seTs and bags in which The order of elemenTs maTTers The order mighT be specified by a ComparaTor or The Comparable compareTo meThod in which case elemenTs would have a welldefined index For insTance in The ordered bag Haul all all b C IICH aquots are aT indices 0 1 2 quotbquot is aT index 3 and cquots are aT indices 4 amp 5 Since elemenTs have a welldefined index we could requesT The elemenT aT a given index or deleTe The elemenT aT an index from an ordered seTbag InserTing elemenTs inTo or deleTing elemenTs from an ordered seTbag can shifT The indices of oTher elemenTs similar To whaT happens in a vecTor We will noT consider implemenTaTions of ordered seTs or bags This semesTer 13713 if u TAh Tables AssociaTe Keys wiTh Values TRU Example a phone direcTory name Ann Bob Carol Call each row a Table enTry There is aT mosT one enTry in a Table wiTh a given key ConcepTually enTries are noT ordered by key buT They may be ordered in implemenTaTion for efficiency Core Table operaTions GeT a value from The Table for a given key PuT a value inTo The Table for a given key overwriTing any exisTing enTry wiTh ThaT key 1314 99D QATAJ A Table InTer face in Java R InTer face To muTable Tables ThaT map keys of Type T To values of Type V This is somewhaT similar To The sTandar39d JavauTilMapltKVgt inTer face in Java Unlike Maps Tables do noT allow null values To be associaTed wiTh a key public inTerface TableltKVgt public void puTK key V value Modifies Table To associaTe key wiTh nonnull value If an enTr y wiTh key alr eady exisTs H is over wr iTTen If value is null a RunTimeExcepTion is Thr own public V geTK key ReTur n The value associaTed key in This Table else null public boolean r39emove K key Remove The enTr39y wiTh The given key from This Table The Table is unchanged if There is no such key ReTur ns True if There was an enTr y else false public ITer aTor ltKgt keys ReTur ns an iTer aTor of all keys in The Table public inT size ReTur ns The number of enTr ies in This Table public boolean isEmpTy ReTur ns True if This Table has no enTr ies else false public void clear Removes all enTr ies from This Table public TableltKVgt copy ReTur ns a quotshallowquot copy of This Table public STr ing ToSTr ingO ReTur ns a sTr ing r epr esenTaTion of This Table 1315 99KB RAl5 Our39 Phone Dir39ecTor39y in Java 12 Value 3924 8763 5816 TableltSTr39ingInTeger39gt dir39ecTor39y new TableVecTor39Sor39TedltSTr39ingInTeger39gt dir39ecTor39ypuT Bobquot new InTeger 8763 dir39ecTor39ypuT Car39olquot new InTeger392673 Carol39s old exTension dir39ecTor39ypuT Annquot new InTeger393924 dir39ecTor39ypuT Car39olquot new InTeger395816 Carol39s new exTension dir39ecTor39ygeT Bobquot gt 8763 An InTeger39 noT an inT dir39ecTor39ygeT Car39olquot gt 5816 MosT r39ecenT exTension dir39ecTor39ygeT Dianaquot gt null No exTension in Table 1316 Key buggle Value favori re color TableltBuggleColorgt favori res new TableVecTorSorTedltBuggleColorgt Buggle bl new Buggle Buggle b2 new BuggleO favori respu rb1Colorred favori respu rb2 Colorblue 13717 ggkhh QM14M Wha r are Tables Good For R Adding vir rual insfance variables To objects eg person39s favori re ice cream flavor All sorts of directories phone direc rories Linux file direc rories Da39rabases provide sophisfica39red Table managemen39r Indexing files and web pages Program analysis and execu rion symbol Tables environmen rs Implemen ring bags 13718 lmnux 161 Trees 6 Atree is a nonlinear hierarchical structure v Tree is comprised ofa set of nodes in which elements are stored and edges connect one node to another 6 A node can have only one parent but may have mul iple children Nodes hat have the same parent are siblin s g There is only one root node in the tree The root is he only node which has no parent 161 Tree Terminology A node that has no children is a leaf node lt9 A note hat is not the root and 2 has at least one child is an D E internal node A subtree is a tree structure that makes up part of another tree F G 3 We can follow a path hrough a star ing lt0 a tree from parent to child at e roo lt9 A node is an ancestor of ano her node if it is above it on the path from ot t can be reached by following a path from a particular node are the descendants of that node The level of a node is the length of Q t l m ath length is determined by counting the number of edges that must be followed to get from the root to the node The height or depth of a tree is the length of he longest path from the root to a leaf 161 Tree Classifications Trees can be classi ed in many ways One important criterion is the maximum number of children any node in the tree may have This is sometimes referred to as the orderofthe r e General trees have no limit to the number of children a node may have A tree that limits each node to no more than n children is referred to as an nary tree Trees in which nodes may have at most two children are called binary trees A tree is considered to be balanced ifall of the leaves ofthe tree are on the same level or at least within one level of eac other D Balanced umnnm 161 Balanced Complete and Full ltgt A balanced nary tree with m elements will have a height oflognm Q A balanced binary tree with n nodes has a height oflogzn ltgt An nary tree is full ifall leaves ofthe tree are at the same height and every nonleafnode has exactly n children Q A tree is complete if it is JII or mil to the nexttolast level with all leaves at the bottom level on the lelt side of the tree 41309 162 Tree Traversals ltgt Because of the nonlinear nature of a tree traversing a tree is generally more interesting than traversing a linear structure A particular type oftraversal simply dictates the order in which the elements ofa collection are assesse Tramads FIGURch ABDHIEJMNCFGKL mumsquot HDiIBEMJNAFCKGL Postwar HIDMNJ EBFKLGCA Lavalorder ABCDEFGHIJKLM N 162 Pseudocode of PrelnPost Traversals 1 Nodes are visited before or Visit the root in between a Visit the root node after any subtrees are visited the traversals ofthe left the traversals of he left and right subtrees and right subtr es visit nag Txavexse 12m Txavexse 119m Txavexse 11 n visit nude 1 v 11 my an my Txavexse mam m n Travm39sals Freeman Indium Posmrum mumomen 162 LevelOrder Traversal Visit the nodes on each level lett to right top to bottom starting at the root Enquelle m no node of m m ml the queue u not empty DegIlene nude more Prenatal 163 Strategies for Implementing Trees Arraybased implementations are the less obvious choice but sometimes usefu Computed Links in an Array A 3901234567 ABCDE F B C wastedspace D E F G 41309 163 Computed Links in an Array For full or complete binary trees we can use an array to represent a tree For any element stored in position n the elements left child is stored in position 2n1 the elements right child is stored in position 2n1 Ifthe represented tree is not complete or relatively complete this approach can waste large amounts of array space 163 Stored Links in an Array rltgt Array positions are allocated on a rstcome rstserved basis ltgt Each element of the array is an ob39ec that stor J t es a reference to the tree element and the array index ofeach child 163 Linked Nodes H Each tree node can be de ned using a separate class similar to Ll nearNode or linked lists Nodes contain a reference to the data stored in the node and references for each ofthe possible children ofthe node Binarytree 2references required left and right children narytree n references required one for each possible child ltgt Trees organized this way lend themselves to recursive processing for many operations 164 javafoundationsBinaryTree nihixyueejiui Java Fo mdalinns Defines the inlexface to i kin11y lxee cullectiuh package javafomdalinns impuxt j avalllil1lexalnx public ihtexiacc BinnyTxeeltTgt extends 1tenbleltwgt t H netuzns the element stnxed in the mat nf the txee public 139 qelknnlElemnll ll netuzns the left subtxee of the mat public HinaxyTxeeltTgt yetLeftH Reluzns the light suhlxee of the nut public HinaxyTxeeltTgt qeuliqhul Relmns lxlle if the hinny lxee contains an element that matches the specified element and false otherwise public hnnlean contains 11 tnqetl 164 javafoundationsBinaryTree netmhs a xefexence tn the element in the mee matching is tax et public 139 find is lnqell netmhs mn if the hinny mee cchtaihs ha elements and II false nthexwise public hnnlean ismplyll39 ntmhs the numhex of elements in this hinazy mee public int sizell netmhs the smiha xepxesenlalinn of the hinazy mee public Slxinq tcsmihcll ntmhs a plenxdex manual ah the hinaxy mee puhljn lteaatcaltwgt pxznxdextl netmhs ah innxdex manual ah the hinaxy mee public lteaatcaltwgt ihmaexll netmhs a pnstnxdex manual ah the hinazy mee cuhlic lteaatcaltwgt pnslnxtlextl Pexfnms a levelrnxdex manual ah the hinaxy mee public lteaatmltwgt levelnxdEXH 164 A Binary Tree Implementation 7 ltgt A possible set of operations for a 39n the binary tree is shown I ElnaryTree interface Unmamr m ltgt ElnaryTree has no methods to add a particular element or to remove a particular element from the tree B39l39Nnde Re ned versions of binary tree such as binary search trees will R R de ne those methods based on speci c characteristics U a ElnaryTree is still useful in certain D situations 164 javafoundationsBTNode 164 javafoundationsBTNode BT ndejava Java rcmaatichs Repxesenls a min in x Thexefnxe this class alsa xeplesenls the ant f package javafcuhaatichs allelic class H39nlndelt3939gt r pxnlecled 139 element pxnlecled BTIlndeltTgt left light a hina y mee with a left and light child 0 a suhmee means a new mee min with the sncifiea aata hnlic hmcae u elemehtl r this elenht element left sight mu ll netuzns the element stated in this nude public 139 qeLElemznlU utuxh elemsht ll sets the element stnxed in this nude public void setalesnht u elcmehtl this elenht element ll netuzns the left suhtxee of this nude public HTllndeltTgt ntheftu utuxh left mu 41309 164 javafoundationsBTNode 164 javafoundationsBTNode ll sets the left child of this node mllit void setheft 1HTIInIeltTgt leflb this1eft left Relmns the light suhtxee of this node mlIlia H Hlndelt39l gt getnightn xeulxn light sets the light child of this node public void setRiqht umIodelt1gt xightp thisxioht light moxe II II Relmns the element in this suhtxee that matches the specified taxqel netoxhs no if the laxqet is hot fnund public BTllndeltTgt find It taxqet HTllndeltTgt leslllt hon if telmentequm1taxqetn xesult this e1se if ueft I how xesult 1etfihd1toxoetp hon u light hon xiqhtfind1taxqetb xetoxh xesull moxe 164 javafoundationsBTNode 1 64 javafoundationsBTNode ll netuzns the numhex of nodes in this suhtxee mlIlia iht cooth int leslllt e if Iieft I hunt xesult K leflcnunlU if light I holly xesull xiqhtmuunl xetoih xesoit moxe II II Pexfnms oh innxdex txovexsoi on this sohtxee updating the specified itexatnx public void innxdel mxayltexatnzltl39gt itexb if Iieft I mil ID leftinnxdel itelH itex add 1e1esoehtp if light hunt xiqhtdnnxdel Htelb II The following methods ole left is panxalllninq pxnjecls II II pllhlic void peoxdex mxayltexatnxltl39gt itezp mlIlia void pnstnxdex 1mxay1texatnxltTgt itexp 41309 164 javafoundations Linked BinaryTree Linked inaxy39l39xeejava Java rnnniitinne ll Implement a hinazy tiee using a linked xepxesentalinn package javafnundatinns LInqudBllmr ree impull j in til Itexitn unpalt j avnfnnniitinne n impul39 j avafnllndalinns zxceplinns n an nae mlAlia class Linked inaryTxeeltTgt implements HinazyTxeeltTgt pxnlecled EnlndeltTgt mt Cleales in empty hinaxy txee D R gulllit Linkeininiiyueeu E b mt null noxe 164 javafoundations Linked BinaryTree Cleales a hinazy tiee with the specified element is it xnnl Public Linkeininiiynee u elemenlb mt e new nunieltwgt1e1enenci cieitee i hinazy tiee with the Lwn specified subtlees public Linked inaxy39l xee u element Linked innyTzeeltTgt left Linked inaxyTxeeltTgt xithb xnnl new HTllndeltTgt1elemean xnnl eetLeft lefonnfH mateetnigntiiigntinnty ll netuzns the element stated in th e xnnl of the Lxee Thxnws in anntycnueetinnaxeentinn if the ll Empty public 139 qelknnlElemnli 1 if mint null than new Emylycnlleclinnlxceplinn Gel mt npetalinn 1 failed The txee is empty i xeultn mt getmenenti p noxe 164 javafoundations Linked BinaryTree ll netuzns the left suhuee nf the mat nf this txee Yullljc Linked inaxyszeltTgt netLeft n if mint nnui than new a t cnueetinnzxee tinn Gel left n elation faile39gl xw39ne txee is en ym P Linked inaxyTxeeltTgt xesult new Linked inaxyTxeeltTgt1H lest1mg e lunlqelLefLD ietun xeenlt Relmns tne elenent in this hinaxy lxee that matches the syecif ed lazqel Thxnws i Elemenulnli mmdilxceplinn if the telnet i nut mind public 139 find 11 tilgeti BTllndeltTgt nude e m if mint nnui nnie xnntfind1tnqeu if innie e up than new Elemenulnli nundllxcer uni LinnUE ind upexalinn failed such element in txee w xeulxn adhqelElemznlU noxe 164 javafoundations Linked BinaryTree Relmns the number at e1enente in this hinazy lxee public int size n K int xeenn n if mt I nnui xesult e xnnlmnunli xeulxn lest1t Pnpulales and lelulns in ilexalnx containing the element in tnie hinaxy lxee using in innxdex tuneuii public IlexalnxltTgt innxdEIH mtayllelalnlltTgt itei new mxaylletalnxltTgt1H if mint I run LU untinnxiex 1itexi xetnxn itex 41309 164 javafoundations Linked BinaryTree Populate and In an ilexalnx containing the elements in um hinaxy lxee using a levelnxdex uanual gulllic IlexalnxltTgt levelnxLIEIH LinkedvueueltHTllndeltTgtgt quell new LinkedvueueltHTllndeltTgtgtH7 mzayllexalnxltTgt ital new mxayllexalnxltTgt1H 1 mm I mm queue enqueue Imam while llqueuerEmyuU l mmbe cuaum queuedequeuell auaaaa louxxenlqel lmenl1ll if cuxxenlqelLele I Iqu quellenqlleu21cuxxenlqlLefl1H if cuttenlqelkiqht1l I may quellenqllellelcmxentqetkith1ll xeulxn nu max 164 javafoundations Linked BinaryTree satisfies the Ilexahle anuafan using an innxdex txavexsal public IlexalnxltTgt itexalnlll xeulxn annan ll The following methods axe left as pxngxanlninq pxnjects public Linked inazyTxeeltTgt amuamn I I in hnnlean camaans u lnxqell I I public hnnlean man I I public Slxinq rustling I I public IlexalnxltTgt plenxdexll I I public IlexalnxltTgt pnstnxdzxtl I I 165 Decision Trees H A decision tree is a tree whose nodes represent decision points and whose children represent the options availa The leaves ofa decision tree represent the possible conclusions that might be dravm based on the answers Decision trees are sometimes used in expertsystems software that attempts to represent the knowledge of an expert in a particular eld 5 Q A simple decision tree with yesno questions can be modeled by a binary tree lt9gt Expertise examples adoctor a car mechanic accountant PC help desk 165 A Decision Tree for Diagnosing Back Pain V N N v mam Guyanan 30mm mamm mm m m a m mm mm magaan w may am am me am m N v N7 Y N7 iv I I 3mm Vuumllnavn smnnm39m You39navmm mum Vnunayaave ll m In Immaan names a vase my mum a mm N mm m M Wm W W 41309 165 BackPainAnalyzerjava 165 BackPainExpertjava HackPainnnalyzexjava Java andalinns Demnnslxales the nsc nf a hinaxy L122 mlAlia class aacuainnnalyzcx Ask questions of m nsca tn diagncsc a ncdical pxnhlem public static vnid nain maincl alqu HackPainExpexl exyexl nsw BackPainExpele expextdiaqnnsel BackPainExpexljava Java Foundations Replesenls a simple expexl system in hack pain diagncsis impull javazcnndacicnsn puhlic class HackPainExpexl pxivale Linkcdninaaynccltsuinggt Lxee Sets up the diagnosis questinn Lxee public HackPainExpexLH 1 String cl Did u pain nccuz aflex a 1an nx jnlu 39 Du an have a cuclw Du 11 cc pexsislenl c ness new keduinaxyheeltstxinggte7 kedainaxyneeltstxinggt92 n4 n5 n3 nan Lmked inaxyneeltstxinggte 16 a7 tree 11quot Linked inaxyneeltstxinggtel n2 n3 Lin Lin Du anl have difficulty cnnlxnllinq your ams u lcgsw ha mnxninq s i 165 BackPainExpertjava Fullnws an diagncsis lxee hased on nsca xespnnses public void diagncsc1 y cannex scan s new Samuel syslemdnh Linked inaxyTxeeltStxinqgt cnncn s Lxee Syslnnnulpxinln usc you xe having hack pain b while cuxenlJiZEH gt 1 Systemnulpxlnlln 1c gcmccmlcnsncm if scanJueleine1Leljualslqnnxecaset WI H mnenl s cnncn man mum cuxxenlqellith1b System nut ptinlh Gallant gcmccmlcncnu n 41309

### 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 bought an awesome study guide, which helped me get an A in my Math 34B class this quarter!"

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

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