20240116 ******************************************************* Enums ++++++++++++++++++++++++++++++++++++++++++++ What is an enum? A special data type that has one of a set of values Syntax for an enum: ----------- public enum EnumName{ ENUM_VALUE1, ENUM_VALUE2, ENUM_VALUE3, ... } Examples of enum ================================= public enum DayOfWeek{ SUNDAY, MONDAY, TUESDAY, WEDNESDAY, THURSDAY, FRIDAY, SATURDAY } public enum Planets{ MERCURY, VENUS, ... } public enum Months{ JANUARY, FEBRUARY, MARCH } public enum Directions{ UP, LEFT, DOWN, RIGHT } public enum BloodLevel{ ACCEPTABLE, MEDIUM, HIGH } public enum Size{ SMALL, MEDIUM, LARGE } Rewrite the following code to be more elegant (using an enum): int received = 0; int processing = 1; int shipped = 2; int returned = 3; int status = received; ... status = processing; public enum Tracking{ RECEIVED, PROCESSING, SHIPPED, RETURNED } FAN_WORKING=1, ALTERNATOR_WORKING=2, BELTS_WORKING=4, ...=8 Generics Exercises ++++++++++++++++++++++++++++++++++++++++++++ Generics Motivation ================================= I. Why would a developer want to use generics? Code use: Write 1 method (algorithm) that can use multiple data types Code use: Write 1 class that can handle/store multiple data types Type safety: Compilation errors instead of runtime error (earlier is better with errors) If using Object references instead, it requires type casting every time to go back to the original data type II. Give 3 examples of when a developer should employ generics General purpose data structure + Classes like ArrayList (can store any object; the algorithms are independent of the type of object being stored) Algorithms for calculating a max, etc. Writing multiple methods/classes with the only difference is the type III. What's the difference between: Pair.java PairOfObjects.java Generics Basics ================================= I. Name a restriction when using a generic entity (and a work around) Can not use a primitive data type, but we can use Primitive Wrapper class 3. Comparable vs Comparator ================================= Talk with the other members of your table about what is the main difference between using the Comparable interface and the Comparator interface Expand the Vehicle class to allow objects of that type to be sorted by the call: Collections.sort( cars ); in VehicleSorter class. Write the VehiclePriceComparator and VehicleYearPerPriceComparator classes so that the VehicleSorter class compiles and sorts as directed in the output statements. 20240118 ******************************************************* 3. Comparable vs Comparator ================================= Talk with the other members of your table about what is the main difference between using the Comparable interface and the Comparator interface Expand the Vehicle class to allow objects of that type to be sorted by the call: Collections.sort( cars ); in VehicleSorter class. Write the VehiclePriceComparator and VehicleYearPerPriceComparator classes so that the VehicleSorter class compiles and sorts as directed in the output statements. Algorithm Analysis Exercises ++++++++++++++++++++++++++++++++++++++++++++ 1. Searching Algorithms 1. Describe the algorithm for linear/sequential search to your neighbor 2. Describe the algorithm for binary search to your neighbor 3. Outline the code for linear/sequential search and binary search Linear Search: int linSearch( T search){ for( i = 0; i < array.length; ++i){ if( array[i].equals( search ) ){ return i; } } return -1; Binary Search 4. Write the code for sequential search and binary search 20240123 ******************************************************* 2. Algorithm Analysis 1. A federal institution is considering contracting you to extend your lab project into a commercial grade program. One question they have is how much is the program going to cost? They're requesting a list of categorized costs for the program. What costs are there in developing such a program? 2. Give examples of what is meant by n inputs for a given problem Number of items to sort Number of social media network connections Number of days Number of stores to determine the optimal route to visit them all 3. What's the difference between: * Best case * Average case * Worst case Applications: Finding an item in sequential search (varies based on where the item is (if it all) in the list) + Best case: First item + Average case: In the n/2th index + Worst case: It's not in the list What is the default for algorithm analysis if one is not specified? Worst case 4. List eight common growth functions and rank them in ascending order based on their Big-Oh O( 1 ) - constant O( log n ) - logarithmic O( n ) - linear O( n log n ) - linear logarithmic O( n^2 ) - quadratic O( n^3 ) - cubic O( 2^n ) - exponential O( n! ) - factorial Number of operations when n = 1,000,000: O( 1 ): 1 O( log n ): 6 O( n ): 1,000,000 O( n log n ): 6,000,000 O( n^2 ): 10,000,000,000 O( n^3 ): 10,000,000,000,000,000 O( 2^n ): 301,030 digits long! O( n! ): 5,565,709 digits long! 5. Demo: Shuffling Example $ java ShufflingExample Enter the maximum value of N: 36000000 Shuffle1 Shuffle2 n (ms) (ms) 10 0 0 100 1 1 1000 16 0 10000 252 3 100000 18911 12 1000000 (From a previous run) $ java ShufflingExample Enter the maximum value of N: 100000000 Shuffle1 Shuffle2 n (ms) (ms) 10 0 0 100 1 0 1000 9 0 10000 156 3 100000 13399 8 1000000 1206433 122 Measuring the Efficiency of Algorithms ================================= Focused on algorithms not programs Program execution times are susceptible to hardware, tricks, data, etc. Examples: ~~~~~~~~~~~~~~~~~~~~~~ void printAll(){ System.out.println( "Printing all items:\n"; if( isEmpty() ){ System.err.println( "ALERT: No items to print!\n" ); return; } Node curr = head; while( curr != null ){ System.out.println( curr.item() ); curr = curr.next(); } } // How many steps does this take to execute if there's n items in the list? System.out.println( "Printing all items:\n"; // constant number of steps (it's independent of the input size) if( isEmpty() ){ // constant System.err.println( "ALERT: No items to print!\n" ); // constant return; // constant } Node curr = head; // constant while( curr != null ){ // n iterations System.out.println( curr.item() );// constant, for each of the n iterations curr = curr.next(); // constant, for each of the n iterations } //Total: c_1 + c_2 + c_3 + c_4 + n * (c_5 + c_6) = c_7 + n * c_8 /* Another Example: ~~~~~~~~~~~~~~~~~~~~~~ How many times is the println method called in the for loop? */ int counter = 0; // c_10 for( int k = 0; k < 5; k++){ // 5 times System.out.println( "counter: " + counter++ ); // constant, for each of the 5 iterations } // Total: c_10 + 5 * c_9 = c_11 int counter = 0; // c_10 for( int k = 0; k < numberInputs; k++){ // numberInputs, n System.out.println( "counter: " + counter++ ); // constant, for each of the n iterations } // Total: c_10 + n * c_9 //What about a nested for loop? int counter = 0; // c_10 for( int j = 0; j < numberInputs; j++){ // n for( int k = 0; k < 5; k++){ // 5 times for each of the j-loop iterations System.out.println( "counter: " + counter++ ); // constant (c_9), for each of iteration (5*n iterations) } } // Total: c_10 + 5n * c_9 = c_10 + n * c_12 // What about a triply-nested for loop? int counter = 0; // c_10 for( int i = 0; i < numberInputs; i++){ // n for( int j = 0; j < numberInputs; j++){ // n times (for each iteration of the i-loop) for( int k = 0; k < 5; k++){ // 5 times for each of the j-loop (which will be n^2) System.out.println( "counter: " + counter++ ); // constant (c_9), for each of iteration (5*n*n iterations) } } } // Total: c_10 + n * n * 5 * c_9 = c_10 + n^2 * c_12 6. What are the 4 properties of growth-rate functions: 1. Ignore lower order terms (for example, O(7 * n^2 + 99 * n) = O( 7 * n^2) 2. Ignore coefficients (multiplicative constants) (for example, O(7*n^2) = O(n^2)) 3. O( f(n) ) + O( g(n) ) = O( f(n) + g(n) ) 4. O( f(n) ) * O( g(n) ) = O( f(n) * g(n) ) Simplifying the totals above: ----------- Total: c_7 + n * c_8 Becomes: O(c_7) + O(n) * O(c_8) = O( c_7 + n * c_8 ) = O( n * c_8 ) = O( n ) Total: c_11 Becomes: O( c_11 ) = O( 1 ) Total: n * c_12 Becomes: O( n * c_12 ) = O( n ) Total: c_10 + n * c_11 Becomes: O(c_10 + n * c_11) = O( n ) Total: c_10 + n^2 * c_12 Becomes: O( c_10 + n^2 * c_12 ) = O( n^2 * c_12 ) = O( n^2 ) 7. Determine the Big-Oh of the growth functions below: 5N + 4 -> O( N ) 9N^2+ 8N - 7 -> O( N^2 ) 2 log N -> O( log N ) 3N log 4N -> O( N log N ) 6*2^(7N) -> O( 2^N ) 3N! + 1/2*N^3 -> O( N! + N^3 ) -> O( N! ) 42 -> O( 1 ) 2*N^3 + 999 * N^2 + 123,456,789*N -> O( N^3 ) Stuck? Plug in some numbers to get a better idea. 8. What is the Big-Oh of linear search? O( N ) 9. What is the Big-Oh of binary search? n | # iterations ===+============= 1 | 1 2 | 2 4 | 3 8 | 4 16 | 5 32 | 6 64 | 7 exp(log n) = exp(5) n = 10^5 (log_2 n) - 1 = # of iterations O( # of iterations) = O( (log_2 n) - 1 ) = O( log n ) 10. Discuss with your neighbor(s) how understanding algorithm analysis will help you at your future job 11. What is the worst case order for the following scenarios: Given an array and an index, displaying the element at the specified index in the array: O( 1 ) Given an array of Fibonacci numbers, adding together the first n values: O( n ) Finding an item in a sorted array of integers: O( log n ) [binary search] Finding an item in an array of integers: O( n ) [linear search] Summing all elements in an ArrayList of Integers: O( ) Summing the length of all strings in a two-dimensional array (n by m elements): O( ) 20240130 ******************************************************* 11. What is the worst case order for the following scenarios: Given an array and an index, displaying the element at the specified index in the array: O( 1 ) Given an array of Fibonacci numbers, adding together the first n values: O( n ) Finding an item in a sorted array of integers: O( log n ) [binary search] Finding an item in an array of integers: O( n ) [linear search] total = 0; // O( 1 ) for( i = 0; until the end of the array; i++){ // O(1) + O( n + 1 ) + O( n ) = O( n ) total = total + array.get(i); // O( 1 ) for each iteration } Summing all elements in an ArrayList of Integers: O( n ) totalChars = 0; for( int row = 0; row < n ){ // O(n) for( int col = 0; col < m ){ // O(m) for each iteration of outer for-loop totalChars += array[row][col].length() } } Summing the length of all strings in a two-dimensional array (n by m elements): O( n * m ) Lists Exercises ++++++++++++++++++++++++++++++++++++++++++++ 1. Terminology A. With all of the members of your table, define the following terms (as they relate to lists): I. ADT (Abstract Data Type) - Interface; Theoretical data structure with allowable actions specified II. head - pointer/reference to the first link III. tail - pointer/reference to the last link IV. length - number of links V. ordered - every element has a position, in increasing sequential order 2.Linked Lists Basics 1. Draw a single link of a linked list (according to the version from the textbook) +-------------+ | element | | next | +-------------+ Link 2. Draw an empty linked list (with a header and trailer (i.e., the version from the textbook)) listSize: 0 head tail curr | | | v v v +---------------+ +---------------+ | element: null | | element: null | | next: --------+-->| next: null | +---------------+ +---------------+ Link Link 3. Draw a linked list (with a header and trailer) with a single link with "C" in it listSize: 1 head curr tail | | | v v v +---------------+ +---------------+ +---------------+ | element: null | | element: "C" | | element: null | | next: --------+-->| next: --------+-->| next: null | +---------------+ +---------------+ +---------------+ Link Link Link 3. Linked list demo: Stores the year that Columbus State University was founded (Columbus College at the time) (with adapted code from the textbook). 20240201 ******************************************************* 3. Linked list demo: Stores the year that Columbus State University was founded (Columbus College at the time) (with adapted code from the textbook). Link linkAfterCurr = curr.next(); Link secondLinkAfterCurr = linkAfterCurr.next(); curr.setNext( secondLinkAfterCurr ); LinkedLists ================================= Attributes (instance variables) ~~~~~~~~~~~~~~~~~~~~~~ listSize head tail curr Actions (methods) ~~~~~~~~~~~~~~~~~~~~~~ remove insert append size / length next clear ... 3. ADT Lists Background: Sequences of elements a_0 through a_n−1 can be represented by: ⟨ a_0, a_1, ..., a_n−1 ⟩ Additionally, for lists, use | to indicate the current position of the list. Individually complete the following, then turn to a neighbor to confirm your answers. Write down each call to the List interface necessary to complete the following operations. Draw the list representation after each operation. A. Insert every character of your first name into a basic list and write down a representation of the list using sequence notation. For example: New list: ⟨ | ⟩ l.insert( H ): ⟨ | H ⟩ l.append( y ): ⟨ | H, y ⟩ l.append( r ): ⟨ | H, y, r ⟩ l.append( u ): ⟨ | H, y, r, u ⟩ l.append( m ): ⟨ | H, y, r, u, m ⟩ B. Insert a space and then every character of your last name into the existing list and write down a representation of the list using sequence notation. l.append( " " ): ⟨ | H, y, r, u, m, " " ⟩ l.append( C ): ⟨ | H, y, r, u, m, " ", C ⟩ ... l.append( l ): ⟨ | H, y, r, u, m, " ", C, a, r, r, o, l ⟩ l.append( l ): ⟨ | H, y, r, u, m, " ", C, a, r, r, o, l, l ⟩ Final state: ⟨ | H, y, r, u, m, , C, a, r, r, o, l, l ⟩ C. Insert a space, your middle initial, and a "." in between your first and last names in the existing list and write down a representation of the list using sequence notation. l.next(): ⟨ H | y, r, u, m, , C, a, r, r, o, l, l ⟩ l.next() l.next() l.next(): ⟨ H, y, r, u | m, " ", C, a, r, r, o, l, l ⟩ l.next(): ⟨ H, y, r, u, m | " ", C, a, r, r, o, l, l ⟩ l.insert(" "): ⟨ H, y, r, u, m | " ", " ", C, a, r, r, o, l, l ⟩ l.next(): ⟨ H, y, r, u , m , " " | " ", C, a, r, r, o, l, l ⟩ l.insert( D ): ⟨ H, y, r, u , m , " " | D, " ", C, a, r, r, o, l, l ⟩ l.next(): ⟨ H, y, r, u , m , " ", D | " ", C, a, r, r, o, l, l ⟩ l.insert( . ): ⟨ H, y, r, u , m , " ", D | ., " ", C, a, r, r, o, l, l ⟩ l.next(): Final state: ⟨ H, y, r, u, m, , D, . | , C, a, r, r, o, l, l ⟩ D. Remove all but the first letter of your first name, middle name and last name and write down a representation of the list using sequence notation. l.moveToStart() while( l.isAtEnd() == false ){ char ch = l.getValue(); if( ! Character.isUpperCase( ch ) ){ l.remove(); }else{ l.next(); } } Final state: ⟨ H, D, C | ⟩ Doubly-Linked List Exercises ++++++++++++++++++++++++++++++++++++++++++++ 1. What does a link in an doubly-linked list look like? +-------------+ | element | | prev | | next | +-------------+ 2. What does an empty doubly-linked list (with a header and trailer (i.e., the version from the textbook)) look like? listSize: 0 head tail curr | | | v v v +---------------+ +---------------+ | element: null | | element: null | | prev: null |<--+-prev: | | next: --------+-->| next: null | +---------------+ +---------------+ Link Link 3. What does an empty basic doubly-linked list (no header nor trailer) look like? listSize: 0 head tail curr | | | v v v null null null This what the instance variables would look like at the end of the constructor and at the end of a call to clear. 4. What does a doubly-linked list (with a header and trailer) with a single link with "C" in it look like? listSize: 1 head curr tail | | | v v v +---------------+ +---------------+ +---------------+ | element: null | | element: "C" | | element: null | | prev: null |<--+-prev: |<--+-prev: | | next: --------+-->| next: --------+-->| next: null | +---------------+ +---------------+ +---------------+ Link Link Link or head tail curr | | | v v v +---------------+ +---------------+ +---------------+ | element: null | | element: "C" | | element: null | | prev: null |<--+-prev: |<--+-prev: | | next: --------+-->| next: --------+-->| next: null | +---------------+ +---------------+ +---------------+ Link Link Link We can get to the later state either by l.append("C") or l.insert("C"); l.next(); Note: curr can never reference the same node as head (in this implementation) 5. What does a doubly-linked list (no header nor trailer) with a single link with "C" in it look like? listSize: 1 head tail curr | | | v v v +---------------+ | element: "C" | | prev: null | | next: null | +---------------+ The above representation is the state after a call to insert("C"). currPos() would return 0 or head tail curr | | | v v v +---------------+ null | element: "C" | | prev: null | | next: null | +---------------+ We can get to the later state either by l.append("C") or l.insert("C"); l.next(); currPos() would return 1 listSize: 2 head curr tail | | | v v v +---------------+ +---------------+ | element: "C" | | element: "F" | | prev: null |<-+-prev: | | next: --------+->| next: null | +---------------+ +---------------+ The above representation is the state after the following calls: l.insert("C") l.append("F"). 20240206 ******************************************************* 6. What are the scenarios for inserting into a doubly-linked list (with a header and trailer)? 1) Appending to the end (really for the append method) 2) Inserting into the middle Update prev and next Update the node that tail is reference (if applicable) 7. What are the scenarios for inserting into a doubly-linked list (no header nor trailer)? 1) Inserting into an empty list 2) Inserting at the end of the list 3) Inserting at the beginning of the list 4) Inserting into the middle 1) Inserting into an empty list Before: ----------- listSize: 0 head tail curr | | | v v v null null null After: ----------- listSize: 1 head tail curr | | | v v v +---------------+ | element: it | | prev: null | | next: null | +---------------+ if( listSize == 0 ) //or if( head == null ) //or if( tail == null ) // create a new node Link newNode = new Link(it, null); head = newNode; tail = newNode; curr = newNode; listSize++; 2) Inserting at the end of the list Before: ----------- listSize: >= 1 tail curr | | v v +---------------+ null | element: e1 | | prev: ? | | next: null | +---------------+ After: ----------- listSize: >= 2 tail curr | | v V +---------------+ +---------------+ | element: e1 | | element: it | | prev: ? |<---+-prev: | | next: --------+--->| next: null | +---------------+ +---------------+ 3) Inserting at the beginning of the list Before: ----------- listSize: >= 1 if( head == curr ) // assuming that the code has already tested for an empty list // or if( curr.prev() == null ) // assuming that the code has already tested for an empty list and inserting into the end of list head curr | | v v +---------------+ | element: e2 | | prev: null | | next: ? | +---------------+ After: ----------- head curr | | v v +---------------+ +---------------+ | element: it | | element: e2 | | prev: null |<---+-prev: | | next: --------+--->| next: ? | +---------------+ +---------------+ 4) Inserting into the middle Before: ----------- listSize: >= 2 curr | v +---------------+ +---------------+ | element: e3 | | element: e4 | | prev: ? |<------------------------+-prev: | | next: --------+------------------------>| next: ? | +---------------+ +---------------+ After: ----------- listSize: >= 3 curr | v +---------------+ +---------------+ +---------------+ | element: e3 | | element: it | | element: e4 | | prev: ? |<--+-prev: |<---+-prev: | | next: --------+-->| next: --------+--->| next: ? | +---------------+ +---------------+ +---------------+ Other Types of Linked Lists: ================================= Circular linked lists ~~~~~~~~~~~~~~~~~~~~~~ Sorted Linked List ~~~~~~~~~~~~~~~~~~~~~~ Stacks Exercises ++++++++++++++++++++++++++++++++++++++++++++ 1. List the basic operations of a stack (and explain each one to the members at your table) push pop peek / top / topValue length isEmpty 2. Identify the Big-O for each of the basic operations Array Linked ----- ----- push O( 1 ) O( 1 ) pop O( 1 ) O( 1 ) peek / top / topValue O( 1 ) O( 1 ) length O( 1 ) O( 1 ) isEmpty O( 1 ) O( 1 ) 3. Identify multiple examples of stacks in everyday life stack of plates at a buffer Pringles Pez deck of cards driveway with cars parked Adding a floor to a new building quora.com: undo operations in a text editor 4. Compare and contrast lists and stacks (for example, which methods need to be changed?) 5. Write the contents of an array stack after each of the following operations (be sure to clearly indicate the top element in the stack): Repeat with a linked stack. Array Stack Linked Stack ----------- ------------ 0 1 Index push( A ) A (top = 1) top -> A push( B ) A B (top = 2) top -> B -> A # insert at the beginning of the stack pop( ) A (top = 1) top -> A push( C ) A C (top = 2) top -> C -> A pop( ) A (top = 1) top -> A pop( ) (top = 0) top -> null push(B) insert( Link it ){ /* before ----------- top | v +---------------+ | element: e1 | | next: ? | +---------------+ after ----------- top | v +---------------+ +---------------+ | element: it | | element: e1 | | next: --------+--->| next: ? | +---------------+ +---------------+ */ top = new Link( it, top ); length++; } 6. Write the contents of an array stack after each of the following operations (be sure to clearly indicate the top element in the stack): Repeat with a linked stack. Array Stack | Linked Stack ----------- | ------------ 0 1 2 3 4 5 6 7 Index | push( 's' ) s (top = 1) | top -> s push( 't' ) s t (top = 2) | top -> t -> s push( 'r' ) s t r (top = 3) | top -> r -> t -> s push( 'e' ) s t r e (top = 4) | top -> e -> r -> t -> s push( 's' ) s t r e s (top = 5) | top -> s -> e -> r -> t -> s push( 's' ) s t r e s s (top = 6) | top -> s -> s -> e -> r -> t -> s push( 'e' ) s t r e s s e (top = 7) | top -> e -> s -> s -> e -> r -> t -> s push( 'd' ) s t r e s s e d (top = 8) | top -> d -> e -> s -> s -> e -> r -> t -> s pop( ) s t r e s s e (top = 7) | top -> e -> s -> s -> e -> r -> t -> s pop( ) s t r e s s (top = 6) | top -> s -> s -> e -> r -> t -> s pop( ) s t r e s (top = 5) | top -> s -> e -> r -> t -> s pop( ) s t r e (top = 4) | top -> e -> r -> t -> s pop( ) s t r (top = 3) | top -> r -> t -> s pop( ) s t (top = 2) | top -> t -> s pop( ) s (top = 1) | top -> s pop( ) (top = 0) | top -> null What word is formed from the collective calls to pop? 7. Linked stack demo (URL): Pushes p, o, o, and l onto a stack and then pops each one of them off (with adapted code from the textbook). Queues Exercises ++++++++++++++++++++++++++++++++++++++++++++ 1. List the basic operations of a queue (and explain each one to the members at your table) // Source: OpenDSA Data Structures and Algorithms Modules Collection, CHAPTER 9 LINEAR STRUCTURES: https://opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/Queue.html public interface Queue { // Queue class ADT // Reinitialize queue public void clear(); // Put element on rear public boolean enqueue(E it); // Remove and return element from front public E dequeue(); // Return front element public E frontValue(); // Return queue size public int length(); //Tell if the queue is empty or not public boolean isEmpty(); } 2. Identify the Big-O for each of the basic operations O( 1 ) for all of the operations for both array-based queues and linked-queues 3. Identify multiple examples of queues in everyday life any fair line music queue digestive system An escalator A car wash 4. Compare and contrast lists and queues (for example, which methods need to be changed?) 5. Compare and contrast stacks and queues (for example, which methods need to be changed?) 6. Talk with the members of your table and determine in the textbook's AQueue class, which end do we remove values from? front 7. Talk with the members of your table and determine in the textbook's AQueue class, does the instance variable front indicate: A. where the front item is located B. where the front item will be located C. where the front item was located A. where the front item is located What does rear indicate? The index of the last item (if there is one) Specifically, given the following contents of a queue, what will be the the values of front and rear: Index 0 1 2 3 4 5 6 7 8 9 10 Y Z D E F G H I X front: 4 rear: 1 frontValue() returns: D Formatted as required by the practice assignments: AQueue (9 elements): Index 4 5 6 7 8 9 10 0 1 Front D E F G H I X Y Z Rear front: 4 rear: 1 8. Write the contents of an array queue after each of the following operations (be sure to clearly indicate the front and rear elements in the queue): Repeat with a linked queue. Array Queue Linked Queue ---------------- ------------ Index 0 1 2 3 (front=1, rear=0) enqueue( A ) A (front=1, rear=1) enqueue( B ) A B (front=1, rear=2) dequeue( ) B (front=2, rear=2) enqueue( C ) B C (front=2, rear=3) enqueue( D ) D B C (front=2, rear=0) dequeue( ) D C (front=3, rear=0) dequeue( ) D (front=0, rear=0) dequeue( ) (front=1, rear=0) 9. Write the contents of an array queue after each of the following operations (be sure to clearly indicate the front and rear elements in the queue): Repeat with a linked queue. Array Queue Linked Queue ---------------- ------------ Index Front 0 1 2 3 4 5 6 7 8 9 10 Rear enqueue( 's' ) enqueue( 't' ) enqueue( 'r' ) enqueue( 'e' ) enqueue( 's' ) enqueue( 's' ) enqueue( 'e' ) enqueue( 'd' ) dequeue( ) dequeue( ) dequeue( ) dequeue( ) dequeue( ) dequeue( ) dequeue( ) dequeue( ) Write the representation of the array-based queue (assuming it has a requested size of 10) and the above operations are performed and then the following operations are performed: Array Queue Linked Queue ---------------- ------------ Index Front 0 1 2 3 4 5 6 7 8 9 10 Rear enqueue( '!' ) enqueue( '?' ) enqueue( '@' ) dequeue( ) dequeue( ) dequeue( ) 10. Linked queue demo (with adapted code from the textbook). https://pythontutor.com/render.html#code=public%20class%20QueueDemo%7B%0A%20%20%20%20public%20static%20void%20main%28%20String%5B%5D%20args%20%29%7B%0A%20%20%20%20%20%20%20%20AQueue%3CCharacter%3E%20queue%20%3D%20new%20AQueue%3CCharacter%3E%28%2010%20%29%3B%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20queue.enqueue%28%20'A'%20%29%3B%0A%20%20%20%20%20%20%20%20queue.enqueue%28%20'B'%20%29%3B%0A%20%20%20%20%20%20%20%20queue.enqueue%28%20'C'%20%29%3B%0A%20%20%20%20%20%20%20%20queue.enqueue%28%20'D'%20%29%3B%0A%20%20%20%20%20%20%20%20queue.enqueue%28%20'E'%20%29%3B%0A%20%20%20%20%20%20%20%20queue.enqueue%28%20'F'%20%29%3B%0A%20%20%20%20%20%20%20%20queue.enqueue%28%20'G'%20%29%3B%0A%20%20%20%20%20%20%20%20queue.enqueue%28%20'H'%20%29%3B%0A%20%20%20%20%20%20%20%20queue.enqueue%28%20'I'%20%29%3B%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20queue.dequeue%28%29%3B%0A%20%20%20%20%20%20%20%20queue.dequeue%28%29%3B%0A%20%20%20%20%20%20%20%20queue.dequeue%28%29%3B%0A%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20queue.enqueue%28%20'X'%20%29%3B%0A%20%20%20%20%20%20%20%20queue.enqueue%28%20'Y'%20%29%3B%0A%20%20%20%20%20%20%20%20queue.enqueue%28%20'Z'%20%29%3B%0A%20%20%20%20%7D%0A%7D%0A%0A//%20Source%3A%20OpenDSA%20Data%20Structures%20and%20Algorithms%20Modules%20Collection,%20CHAPTER%209%20LINEAR%20STRUCTURES%3A%20https%3A//opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/Queue.html%0A%0Aclass%20AQueue%3CE%3E%7B%0A%20%20%20%20private%20E%20queueArray%5B%5D%3B%20%20%20%20%20%20//%20Array%20holding%20queue%20elements%0A%20%20%20%20private%20static%20final%20int%20DEFAULT_SIZE%20%3D%2010%3B%0A%20%20%20%20private%20int%20maxSize%3B%20%20%20%20%20%20%20%20%20//%20Maximum%20size%20of%20queue%0A%20%20%20%20private%20int%20front%3B%20%20%20%20%20%20%20%20%20%20%20//%20Index%20of%20front%20element%0A%20%20%20%20private%20int%20rear%3B%20%20%20%20%20%20%20%20%20%20%20%20//%20Index%20of%20rear%20element%0A%0A%20%20%20%20//%20Constructors%0A%20%20%20%20%40SuppressWarnings%28%22unchecked%22%29%20//%20Generic%20array%20allocation%0A%20%20%20%20AQueue%28int%20size%29%20%7B%0A%20%20%20%20%20%20%20%20maxSize%20%3D%20size%2B1%3B%20%20%20%20%20%20%20%20%20%20//%20One%20extra%20space%20is%20allocated%0A%20%20%20%20%20%20%20%20rear%20%3D%200%3B%20front%20%3D%201%3B%0A%20%20%20%20%20%20%20%20queueArray%20%3D%20%28E%5B%5D%29new%20Object%5BmaxSize%5D%3B%20%20//%20Create%20queueArray%0A%20%20%20%20%7D%0A%20%20%20%20AQueue%28%29%20%7B%20%0A%20%20%20%20%20%20%20%20this%28DEFAULT_SIZE%29%3B%20%0A%20%20%20%20%7D%0A%0A%20%20%20%20//%20Reinitialize%0A%20%20%20%20public%20void%20clear%28%29%20%7B%0A%20%20%20%20%20%20%20%20rear%20%3D%200%3B%20front%20%3D%201%3B%20%0A%20%20%20%20%7D%0A%0A%20%20%20%20//%20Put%20%22it%22%20in%20queue%0A%20%20%20%20public%20boolean%20enqueue%28E%20it%29%20%7B%0A%20%20%20%20%20%20%20%20if%20%28%28%28rear%2B2%29%20%25%20maxSize%29%20%3D%3D%20front%29%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20false%3B%20%20//%20Full%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20rear%20%3D%20%28rear%2B1%29%20%25%20maxSize%3B%20//%20Circular%20increment%0A%20%20%20%20%20%20%20%20queueArray%5Brear%5D%20%3D%20it%3B%0A%20%20%20%20%20%20%20%20return%20true%3B%0A%20%20%20%20%7D%0A%0A%20%20%20%20//%20Remove%20and%20return%20front%20value%0A%20%20%20%20public%20E%20dequeue%28%29%20%7B%0A%20%20%20%20%20%20%20%20if%28length%28%29%20%3D%3D%200%29%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20null%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20E%20it%20%3D%20queueArray%5Bfront%5D%3B%0A%20%20%20%20%20%20%20%20front%20%3D%20%28front%2B1%29%20%25%20maxSize%3B%20//%20Circular%20increment%0A%20%20%20%20%20%20%20%20return%20it%3B%0A%20%20%20%20%7D%0A%0A%20%20%20%20//%20Return%20front%20value%0A%20%20%20%20public%20E%20frontValue%28%29%20%7B%0A%20%20%20%20%20%20%20%20if%20%28length%28%29%20%3D%3D%200%29%20%7B%0A%20%20%20%20%20%20%20%20%20%20%20%20return%20null%3B%0A%20%20%20%20%20%20%20%20%7D%0A%20%20%20%20%20%20%20%20return%20queueArray%5Bfront%5D%3B%0A%20%20%20%20%7D%0A%0A%20%20%20%20//%20Return%20queue%20size%0A%20%20%20%20public%20int%20length%28%29%20%7B%0A%20%20%20%20%20%20%20%20return%20%28%28rear%2BmaxSize%29%20-%20front%20%2B%201%29%20%25%20maxSize%3B%20%0A%20%20%20%20%7D%0A%20%20%0A%20%20%20%20//Tell%20if%20the%20queue%20is%20empty%20or%20not%0A%20%20%20%20public%20boolean%20isEmpty%28%29%20%7B%20%0A%20%20%20%20%20%20%20%20return%20front%20-%20rear%20%3D%3D%201%3B%20%0A%20%20%20%20%7D%0A%7D&cumulative=false&curInstr=143&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=java&rawInputLstJSON=%5B%5D&textReferences=false 20240220 ******************************************************* Recursion Exercises ++++++++++++++++++++++++++++++++++++++++++++ 1. What are the two questions for constructing recursive solutions? I. What is the base case? (Base case: Simplest solution to the problem. When we stop the recursion. II. How do we make the original problem easier (smaller) for the next call. How can we repeatedly get CLOSER to the solution? 2. Binary Search is a classical optimal search algorithm: Look at the middle element of a sorted array. If the number you're searching is larger than the middle element, search the upper half. If the number you're searching is smaller than the middle element, search the lower half. Otherwise, the number is found. A. Apply the two questions for constructing a recursive solution to Binary Search: I. We found the key that we're looking for OR the search space is empty II. Divide the search space in half (based on the algorithm above) B. Outline the an algorithm for a recursive Sequential Search and a recursive Binary Search Sequential / linear search: Iterative check each element to see if its the item we're looking for. Stop when we find the element or we've exhausted all elements. Binary Search (return the item): Calculate the middle index (of the remaining search space), (low + high)/2 if the element at the middle index matches the key, then return the item (base case) if the key is larger than the element at the middle index, move the lower bound of the search space to be middle index + 1, and then recursively solve the smaller problem otherwise (the key is smaller than the element at the middle index), move the upper bound of the search space to be middle index - 1, and then recursively solve the smaller problem C. Write the code for recursive Sequential Search and recursive Binary Search public class Searches{ // Sequential / linear search: public static String sequentialSearchIterative( String[] arr, String key ){ // Iteratively check each element to see if its the item we're looking for. Stop when we find the element or we've exhausted all elements. for( int i = 0; i < arr.length; ++i ){ if( arr[i].equals(key) ){ // found the item return arr[i]; } } return ""; } public static String sequentialSearch( String[] arr, String key ){ // Iteratively check each element to see if its the item we're looking for. Stop when we find the element or we've exhausted all elements. return sequentialSearchRecursive( arr, key, 0); } private static String sequentialSearchRecursive( String[] arr, String key, int index ){ if( index >= arr.length ){ // not found return null; }else if( arr[index].equals(key) ){ // found the item return arr[index]; }else{ return sequentialSearchRecursive( arr, key, index + 1 ); } } public static String sequentialSearch2( String[] arr, String key ){ return binarySearchRec( arr, key, 0, arr.length - 1); } /** * @param arr Values to search in * @param low The index in arr of the lowest possible value still in the search space * @param high The index in arr of the largest possible value still in the search space */ private static String binarySearchRec( String[] arr, String key, int low, int high){ if( high < low ){ // empty search space return null; } // Look at the middle element of a sorted array. int mid = (high + low) / 2; if( arr[mid].equals(key) ){ // found the item return arr[mid]; }else if( key.compareTo( arr[mid] ) > 0 ){ // The number we're searching for is larger than the middle element, search the upper half. return binarySearchRec( arr, key, mid + 1, high); }else{ // if( key.compareTo( arr[mid] ) < 0 ){ // The number we're searching for is smaller than the middle element, search the lower half. return binarySearchRec( arr, key, low, mid - 1); } public static void main( String[] args){ String[] a = new String[5]; int index = 0; a[index++] = "apple"; a[index++] = "pear"; a[index++] = "banana"; a[index++] = "strawberry"; a[index++] = "blueberry"; System.err.println( sequentialSearch( a, "banana")); System.err.println( sequentialSearch( a, "Spondias Mombin")); } } D. Discuss with your neighbor(s) the Big-Ohs of Sequential Search and Binary Search: To calculate the worst-case Big-Oh for Binary Search for an array of size n consider the following: After 1 iteration, there are n/2 elements left to search. After 2 iterations, there are n/2/2 (or n/2^2) elements left to search. After 3 iterations, there are n/2/2/2 (or n/2^3) elements left to search. After 4 iterations, there are n/2/2/2/2 (or n/2^4) elements left to search. After k iterations, there are n/2^k elements left to search. In the worst case, searching stops when there is 1 element left to search, so n/2^k = 1 Rearranging the equation: 2^k = n Taking the log of both sides: log_2 2^k = log_2 n Simplifying: k log_2 2 = log_2 n Simplifying: k = log_2 n Requires log_2 n steps/iterations, therefore the O( log_2 n ) = O( log n ) 3. Identify answers for the two questions for constructing a recursive solution, write an outline and then a recursive solution to calculate a Fibonacci number: F_1 = 1 F_2 = 1 F_n = F_n - 1 + F_n - 2 I. II. Outline Solution 4. Identify answers for the two questions for constructing a recursive solution for the Tower of Hanoi problem. (Assume that you can make calls like moveDisc( tower1, tower2 ) to move a disc from a specified tower to another specified tower.) Also, write an outline and a recursive solution. I. There's only 1 disk (so move it) II. 1) Move n-1 discs to a spare tower 2) Move a single disc to the final tower 3) Move n-1 discs to the final tower Outline Solution private void move(String startingTower, String finalTower){ System.out.println("Move 1 disc from " + startingTower + " to " + finalTower); } public void solver(int numDiscs){ solverRec(numDiscs); } public void solverRec(int numDiscs, String startingTower, String spareTower, String finalTower){ // There's only 1 disk (so move it) if( numDiscs == 1 ){ move( startingTower, finalTower); return; } // 1) Move n-1 discs to a spare tower solverRec( numDiscs - 1, startingTower, finalTower, spareTower); // 2) Move a single disc to the final tower move( startingTower, finalTower); // 3) Move n-1 discs to the final tower (from the spare tower) solverRec( numDiscs - 1, spareTower, startingTower, finalTower); } 5. Working together with those at your table, apply the two questions for constructing a recursive solution for making change for a given amount of money. Let's assume that we are only dealing with standard US coins (with values 1, 5, 10, 25). For example, there are 242 different ways to combine pennies, nickels, dimes and quarters to make $1.00. There are 6 ways to combines those coins to make $0.15 and 4 ways for $0.10. Make sure that you can solve simple problems (like $0.05, $0.06, $0.10 and $0.15) by hand before thinking about your recursive solution. 20240227 ############################################################################# Binary Tree Traversals Exercises ++++++++++++++++++++++++++++++++++++++++++++ 1. Given the following tree, write the values of the nodes in the order that they are traversed. B / \ i r / \ / n a y Preorder Traversal Algorithm (for each subtree): visit traverse the left subtree traverse the right subtree Traversal: Binary Inorder Traversal Algorithm (for each subtree): traverse the left subtree visit traverse the right subtree Traversal: n i a B y r Postorder Traversal Algorithm (for each subtree): traverse the left subtree traverse the right subtree visit Traversal: n a i y r B 2. Given the following*: BinNode interface (http://csc.columbusstate.edu/carroll/2108/trees/binaryTrees/BinNode.java.html) BTNode class (http://csc.columbusstate.edu/carroll/2108/trees/binaryTrees/BTNode.java.html) BT class (http://csc.columbusstate.edu/carroll/2108/trees/binaryTrees/BT.java.html) write driver code to create a BT object that stores the following binary tree: B / \ i r / \ / n a y public static void main( String[] args ){ BTNode grandLefty = new BTNode( 'n' ); BTNode grandRighty = new BTNode( 'a' ); BTNode lefty = new BTNode( 'i', grandLefty, grandRighty); BTNode node = new BTNode( 'B', lefty, new BTNode( 'r', new BTNode( 'y' ), null)); BT tree = new BT( node ); } * Or use this code in pythontutor.com: https://pythontutor.com/render.html#code=public%20class%20BinaryTreeTraversalsExercises%7B%0A%0A%0A%20%20%20%20public%20static%20void%20main%28%20String%5B%5D%20args%20%29%7B%0A%20%20%20%20%20%20%20%20/*%20Create%20the%20following%20binary%20tree%3A%0A%20%20%20%20%20%20%20%20%20%20%20%0A%20%20%20%20%20%20%20%20B%0A%20%20%20%20%20%20/%20%20%20%5C%0A%20%20%20%20%20i%20%20%20%20%20r%0A%20%20%20%20/%20%5C%20%20%20%20/%20%20%20%0A%20%20%20n%20%20%20a%20%20y%0A%20%20%20%0A%20%20%20%20%20%20%20%20*/%0A%20%20%20%0A%0A%20%20%20%20%7D%0A%7D%0A%0A//%20Binary%20Tree%20implementation%0A//%20Based%20somewhat%20off%20of%20https%3A//opendsa-server.cs.vt.edu/ODSA/Books/Everything/html/BST.html%0Aclass%20BT%3CE%3E%20%7B%0A%20%20%20%20private%20BinNode%3CE%3E%20root%3B%20//%20Root%20of%20the%20BT%0A%0A%20%20%20%20//%20constructor%0A%20%20%20%20public%20BT%28%29%7B%0A%20%20%20%20%20%20%20%20root%20%3D%20null%3B%0A%20%20%20%20%7D%0A%0A%20%20%20%20public%20BT%28%20BinNode%3CE%3E%20root%29%7B%0A%20%20%20%20%20%20%20%20this.root%20%3D%20root%3B%0A%20%20%20%20%7D%0A%0A%20%20%20%20//%20Reinitialize%20tree%0A%20%20%20%20public%20void%20clear%28%29%7B%0A%20%20%20%20%20%20%20%20root%20%3D%20null%3B%0A%20%20%20%20%7D%0A%0A%20%20%20%20public%20void%20setRoot%28%20BinNode%3CE%3E%20root%29%7B%0A%20%20%20%20%20%20%20%20this.root%20%3D%20root%3B%0A%20%20%20%20%7D%0A%0A%20%20%20%20//%20%22visit%22%20a%20node%20by%20displaying%20it%20value%0A%20%20%20%20private%20void%20visit%28%20BinNode%3CE%3E%20root%20%29%7B%0A%20%20%20%20%20%20%20%20System.out.println%28%20root.value%28%29%20%29%3B%0A%20%20%20%20%7D%0A%0A%20%20%20%20public%20void%20preOrderTraverse%28%20%29%7B%0A%20%20%20%20%20%20%20%20System.out.println%28%22Pre-order%20Traversal%3A%22%29%3B%0A%0A%20%20%20%20%7D%0A%0A%20%20%20%20public%20void%20inOrderTraverse%28%20%29%7B%0A%20%20%20%20%20%20%20%20System.out.println%28%22In-order%20Traversal%3A%22%29%3B%0A%0A%20%20%20%20%7D%0A%0A%20%20%20%20public%20void%20postOrderTraverse%28%20%29%7B%0A%20%20%20%20%20%20%20%20System.out.println%28%22Post-order%20Traversal%3A%22%29%3B%0A%0A%20%20%20%20%7D%0A%7D%0A%0A%0Aclass%20BTNode%3CE%3E%20implements%20BinNode%3CE%3E%20%7B%0A%20%20private%20E%20element%3B%20%20%20%20%20%20%20%20%20%20//%20Element%20for%20this%20node%0A%20%20private%20BTNode%3CE%3E%20left%3B%20%20%20%20%20//%20Pointer%20to%20left%20child%0A%20%20private%20BTNode%3CE%3E%20right%3B%20%20%20%20//%20Pointer%20to%20right%20child%0A%0A%20%20//%20Constructors%0A%20%20public%20BTNode%28%29%7B%0A%20%20%20%20%20%20left%20%3D%20right%20%3D%20null%3B%0A%20%20%7D%0A%20%20public%20BTNode%28E%20val%29%7B%0A%20%20%20%20%20%20left%20%3D%20right%20%3D%20null%3B%0A%20%20%20%20%20%20element%20%3D%20val%3B%0A%20%20%7D%0A%20%20public%20BTNode%28E%20val,%20BTNode%3CE%3E%20l,%20BTNode%3CE%3E%20r%29%7B%0A%20%20%20%20%20%20left%20%3D%20l%3B%0A%20%20%20%20%20%20right%20%3D%20r%3B%0A%20%20%20%20%20%20element%20%3D%20val%3B%0A%20%20%7D%0A%0A%20%20//%20Get%20and%20set%20the%20element%20value%0A%20%20public%20E%20value%28%29%7B%0A%20%20%20%20%20%20return%20element%3B%0A%20%20%7D%0A%20%20public%20void%20setValue%28E%20v%29%7B%0A%20%20%20%20%20%20element%20%3D%20v%3B%0A%20%20%7D%0A%0A%20%20//%20Get%20and%20set%20the%20left%20child%0A%20%20public%20BTNode%3CE%3E%20left%28%29%7B%0A%20%20%20%20%20%20return%20left%3B%0A%20%20%7D%0A%20%20public%20void%20setLeft%28BTNode%3CE%3E%20p%29%7B%0A%20%20%20%20%20%20left%20%3D%20p%3B%0A%20%20%7D%0A%0A%20%20//%20Get%20and%20set%20the%20right%20child%0A%20%20public%20BTNode%3CE%3E%20right%28%29%7B%0A%20%20%20%20%20%20return%20right%3B%0A%20%20%7D%0A%20%20public%20void%20setRight%28BTNode%3CE%3E%20p%29%7B%0A%20%20%20%20%20%20right%20%3D%20p%3B%0A%20%20%7D%0A%0A%20%20//%20return%20TRUE%20if%20a%20leaf%20node,%20FALSE%20otherwise%0A%20%20public%20boolean%20isLeaf%28%29%20%7B%0A%20%20%20%20%20%20return%20%28left%20%3D%3D%20null%29%20%26%26%20%28right%20%3D%3D%20null%29%3B%0A%20%20%7D%0A%0A%7D%0A%0Ainterface%20BinNode%3CE%3E%20%7B%20//%20Binary%20tree%20node%20ADT%0A%20%20%20%20//%20Get%20and%20set%20the%20element%20value%0A%20%20%20%20public%20E%20value%28%29%3B%0A%20%20%20%20public%20void%20setValue%28E%20v%29%3B%0A%0A%20%20%20%20//%20return%20the%20children%0A%20%20%20%20public%20BinNode%3CE%3E%20left%28%29%3B%0A%20%20%20%20public%20BinNode%3CE%3E%20right%28%29%3B%0A%0A%20%20%20%20//%20return%20TRUE%20if%20a%20leaf%20node,%20FALSE%20otherwise%0A%20%20%20%20public%20boolean%20isLeaf%28%29%3B%0A%7D&cumulative=false&curInstr=0&heapPrimitives=nevernest&mode=display&origin=opt-frontend.js&py=java&rawInputLstJSON=%5B%5D&textReferences=false 3. Complete the {pre,in,post}OrderTraverse methods in the BT class by adding recursive methods. Each of these recursive methods should be based off of the traverse method by adding the call "visit( root );" (and changing the name of the recursive method calls): public void traverse( BinNode root ){ if( root == null ){ return; } traverse( root.left() ); traverse( root.right() ); } Code inserted into BT class: public void preOrderTraverse( ){ System.out.println("Pre-order Traversal:"); po( root ); } private void po( BinNode r ){ if(r == null){ return; } visit( r ); po( r.left() ); po( r.right() ); } Add calls to the {pre,in,post}OrderTraverse methods in your driver code and make sure that it matches what you came up with in the first part. public static void main( String[] args ){ // ... (as above) tree.preOrderTraverse(); } 20240305 ******************************************************* Binary Search Trees (BST) Exercises ++++++++++++++++++++++++++++++++++++++++++++ ADT Binary Search Trees (BST) ================================= Each node of a BST has the following 3 properties: 1) The value (or key) of the node is greater than or equal to all of the values (keys) in it's left subtree 2) The value (or key) of the node is less than all of the values (keys) in it's right subtree 3) The left and right subtrees are BSTs Searching for a key in a BST ================================= boolean searchBST( Node root, Key item ){ if( root == null ){ // item is not found in this subtree return false }else if( item < root.value() ){ return searchBST( root.left(), item ) }else if( item > root.value() ){ return searchBST( root.right(), item ) }else{ // found the item! return true } } Retrieval ================================= Just change returns from the above E findBST( Node root, Key item ){ if( root == null ){ // item is not found in this subtree return null; }else if( item < root.value() ){ return searchBST( root.left(), item ) }else if( item > root.value() ){ return searchBST( root.right(), item ) }else{ // found the item! return root.value() } } Inserting ================================= Always add as a leaf void insertBST( Node root, E item ){ if( root.isLeaf() ){ // insert as a child of the leaf if( item < root.value() ){ root.setLeft( item ) }else{ root.setRight( item ) } }else if( item < root.value() ){ insertBST( root.left(), item ) }else{ insertBST( root.right(), item ) } } Deletion ================================= Before we delete it, we need to find it boolean deleteBST( Node root, Key item ){ Node n = findBST( root, item ); if( n == null ){ // item is not in the tree return false; }else{ return deleteNode( n ); } } 3 scenarios for n: 1) n is a leaf (so no children): Set it's parent's pointer to null 2) n has 1 child: Replace n with its child 3) n has 2 children: Let's find a node that easier to delete. Not just any node (it still needs to be a BST when we're done). Pick the node with the key just BEFORE (inorder predecessor) n's value and replace n with that node. Then, delete n. 1. Draw the resulting BST after inserting the following strings (in the order provided) into an empty BST: BS, AVL, TT, TTF, RB, Splay root | v null Insert BS root | v BS Insert AVL root | v BS / AVL Insert TT root | v BS / \ AVL TT Insert TTF root | v BS / \ AVL TT \ TTF Insert RB root | v BS / \ AVL TT / \ RB TTF Insert Splay root | v BS / \ AVL TT / \ RB TTF \ Splay BS + Left AVL + Right TT + Left RB | + Left (empty) | + Right Splay + Right TTF 2. Draw the resulting BST after inserting the following strings (in the order provided) into an empty BST: Splay, BS, RB, AVL, TT, TTF Insert Splay Splay Insert BS Splay / BS Insert RB Splay / BS \ RB Insert AVL Splay / BS / \ AVL RB Insert TT Splay / \ BS TT / \ AVL RB Insert TTF Splay / \ BS TT / \ \ AVL RB TTF Now insert TT into the existing BST. What considerations are there? Insert TT Splay / \ BS TT / \ / \ AVL RB TT TTF 3. Draw the resulting BST after inserting the following strings (in the order provided) into an empty BST: AVL, BS, RB, Splay, TT, TTF Insert AVL AVL Insert BS AVL \ BS Insert RB AVL \ BS \ RB Insert Splay AVL \ BS \ RB \ Splay Insert TT AVL \ BS \ RB \ Splay \ TT Insert TTF AVL \ BS \ RB \ Splay \ TT \ TTF 4. Given the following BST, draw the resulting tree after removing A. B / \ A E / \ C F \ D Scenarios for removal: 1) 2) 3) B \ E / \ C F \ D Then, draw the tree after removing C. B \ E / \ D F 5. Given the following BST, draw the resulting tree after removing B. B / \ A E / \ C F \ D A \ E / \ C F \ D Then, draw the tree after removing E. A \ D / \ C F Remove D A \ C \ F 5. Write in the Big-Oh for the following operations on a BST. Average-case Worst-case Retrieval* O( log n ) O( n ) Insertion* O( log n ) O( n ) Deletion O( log n ) O( n ) Traversal O( n ) O( n ) We have to visit every node * the height of the tree AVL Trees Exercises ++++++++++++++++++++++++++++++++++++++++++++ 1. Discuss with your neighbor: A. What an AVL tree is (and is not): Self-balancing (it is always balanced after completing its operation) binary search tree B. The main advantage(s) of using an AVL tree Self-balancing -> Better worst-case Big-Ohs C. The Big-Ohs for AVL tree operations: Average-case Worst-case Retrieval O( log n ) O( log n ) Insertion O( log n ) O( log n ) Deletion O( log n ) O( log n ) Traversal O( n ) O( n ) 2. Review the AVL rotations handout (http://csc.columbusstate.edu/carroll/2108/trees/balancedTrees/avlRotations.pdf) 3. Insert the numbers 1, 2, ... 10 into an empty AVL tree. Draw the tree after each insertion. If appropriate, identify: A. the imbalanced node B. what type of rotation is needed Double check that: A. after each rotation that it's a BST B. after each insertion that it's an AVL tree Insert 1 1 Insert 2 1 \ 2 Insert 3 1 \ 2 \ 3 Imbalanced at 1 Right (case 4) rotation need 1 (k_1) \ 2 (k_2) \ 3 (Z) 2 (k_2) / \ 1 (k_1) 3 (Z) Insert 4 2 (left subtree height: 1, right subtree height: 2) / \ 1 3 \ 4 Insert 5 2 / \ 1 3 \ 4 \ 5 Imbalanced at 3 Right (case 4) rotation need 2 / \ 1 3 (k_1) \ 4 (k_2) \ 5 (Z) 2 / \ 1 4 (k_2) / \ 3 (k_1) 5 (Z) Insert 6 2 (k_1) / \ 1 4 / \ 3 5 \ 6 Imbalanced at 2 Right (case 4) rotation need 4 / \ 2 5 / \ \ 1 3 6 Insert 7 4 / \ 2 5 (k_1) / \ \ 1 3 6 \ 7 Imbalanced at 5 Right (case 4) rotation 4 / \ 2 6 / \ / \ 1 3 5 7 Insert 8 4 / \ 2 6 / \ / \ 1 3 5 7 \ 8 Insert 9 4 / \ 2 6 / \ / \ 1 3 5 7 \ 8 \ 9 4 / \ 2 6 / \ / \ 1 3 5 8 / \ 7 9 Insert 10 4 / \ 2 6 (k_1) / \ / \ 1 3 5 8 / \ 7 9 \ 10 4 / \ 2 8 / \ / \ 1 3 6 9 / \ \ 5 7 10 4. Insert the numbers 10, 9, ... 5 into an AVL tree. Draw the tree after each insertion. If appropriate, identify: A. the imbalanced node B. what type of rotation is needed Double check that: A. after each rotation that it's a BST B. after each insertion that it's an AVL tree Insert 10 Insert 9 Insert 8 Insert 7 Insert 6 Insert 5 5. Insert the numbers 1, 11, 2, 10, 3, 9, 4, 8, 5, 7, 6 into an AVL tree. Draw the tree after each insertion. If appropriate, identify: A. the imbalanced node B. what type of rotation is needed Double check that: A. after each rotation that it's a BST B. after each insertion that it's an AVL tree Insert 1 1 Insert 11 1 \ 11 Insert 2 1 k_1 (Right Left (Case 3)) \ 11 k_3 / 2 k_2 1 k_1 \ 2 k_2 \ 11 k_3 2 k_2 / \ 1 k_1 11 k_3 Insert 10 2 / \ 1 11 / 10 Insert 3 2 / \ 1 11 k_2 (Left (Case 1)) / 10 / 3 2 / \ 1 10 / \ 3 11 Insert 9 2 k_1 (Right Left (Case 3)) / \ 1 10 / \ 3 11 \ 9 2 (k_1) / \ 1 3 \ 10 / \ 9 11 3 / \ 2 10 / / \ 1 9 11 Insert 4 Insert 8 Insert 5 Insert 7 Insert 6 Splay Trees Exercises ++++++++++++++++++++++++++++++++++++++++++++ 1. Discuss with your neighbor: A. What a Splay tree is (and is not) Self-adjusting binary search tree (and not a self-balancing BST) B. The main advantage(s) of using a Splay tree? Recently accessed elements are at or near the root (caching effect) Good average-case and worst case Big-Ohs C. The Big-Ohs for Splay trees operations: Average-case Worst-case Retrieval O( log n ) amortized O( log n ) Insertion O( log n ) amortized O( log n ) Deletion O( log n ) amortized O( log n ) Traversal O( n ) O( n ) What does amortized mean? on average over multiple operations 2. Review the splaying handout (http://csc.columbusstate.edu/carroll/2108/trees/balancedTrees/splayingHandout.pdf) 3. Insert the numbers 1, 2, ... 5 into a Splay tree. Draw the tree after each insertion. Draw the tree after each Zig, Zig-zag and Zig-zig rotation. (Note: If it's helpful, identify which node is k1, k2, ...) (Note: Double check that after each rotation that it's still a BST.) Insert 1 ----------- Insert 2 ----------- Insert 3 ----------- Insert 4 ----------- Insert 5 ----------- 4. Insert the numbers 1, 5, 2, 6, 3, 7, 4, 8 into a Splay tree. Draw the tree after each insertion. Draw the tree after each Zig, Zig-zag and Zig-zig rotation. Insert 1 ----------- 1 Insert 5 ----------- 1 \ 5 Zig rotation 5 / 1 Insert 2 ----------- 5 / 1 \ 2 (k_2) Zig-zag rotation 5 / 2 (k_2) / 1 2 (k_2) / \ 1 5 Insert 6 ----------- 2 (k_1) / \ 1 5 (k_2) \ 6 (k_3) Zig-zig rotation 6 (k_3) / 5 (k_2) / 2 (k_1) / 1 Insert 3 ----------- 6 / 5 / 2 / \ 1 3 6 (k_3) / 5 (k_2) / 3 (k_1) / 2 / 1 Zig-zig 3 (k_1) / \ 2 5 (k_2) / \ 1 6 (k_3) Insert 7 ----------- Insert 4 ----------- Insert 8 ----------- Heaps Exercises ++++++++++++++++++++++++++++++++++++++++++++ Priority Queues ================================= 1. Write down the results of the following priority queue operations and then compare with your neighbor(s): Insert 42 Priority Queue: 42 (top) Insert 3 Priority Queue: 42 (top), 3 Insert 7 Priority Queue: 42 (top), 3, 7 or 42 (top), 7, 3 Top Priority Queue: 42 (top), 3, 7 or 42 (top), 7, 3 (retrieve 42) Pop Priority Queue: 7 (top), 3 Top Priority Queue: 7 (top), 3 (retrieve 7) Pop Priority Queue: 3 (top) Insert 99 Priority Queue: 99 (top), 3 Top Priority Queue: 99 (top), 3 (retrieve 99) Pop Priority Queue: 3 (top) What's left in the priority queue (if anything)? 3 Heaps ================================= 1. Discuss the following in a group of 3-5 people. Be prepared to share your group's conclusions. A. What are the advantages of using a heap data structure? Fast retrieval of the highest priority item B. Name several scenarios where a heap is advantageous. Hospital: Triage 911 call center Needs based scholarship OS process scheduling to-do list selector C. Name some scenarios where a heap is not advantageous. Restaurants Anything with a range operation (including sorting) or a particular element 2. Are the following heaps valid? If not, do they violate the structure and/or heap-order property? Heap structure property: Complete binary tree (not a BST) Heap order property: The value of each node is greater than its children's values A. Nodes with the following edges (6 is at the top): 6-5, 6-4, 5-3, 5-2, 4-1 Heap structure property: Yes Heap order property: Yes Heap: Yes B. Nodes with the following edges (1 is at the top): 1-2, 1-3, 2-4, 2-5, 3-6 Heap structure property: Yes Heap order property: No (unless it's a min-heap) Heap: No (unless it's a min-heap) C. Nodes with the following edges (5 is at the top): 1-4, 2-3, 2-5, 4-5 Heap structure property: No Heap order property: No Heap: No D. Nodes with the following edges (15 is at the top): 1-5, 2-5, 3-6, 4-6, 5-7, 6-7, 7-15, 8-12, 9-12, 10-13, 11-13, 12-14, 13-14, 14-15 Heap structure property: Yes Heap order property: Yes Heap: Yes E. Nodes with the following edges (8 is at the top): 1-2, 2-3, 2-4, 4-6, 4-8, 5-6, 6-7, 8-12, 9-10, 10-11, 10-12, 12-14, 13-14, 14-15 Heap structure property: Yes Heap order property: No (but it is a BST) Heap: No 3. Insertions and Deletions A. Draw the resulting heap after inserting 10, 12, 1, 14, 6, 5, 8, 15, 3, 9, 7, 4, 11, 13 and 2 into an initially empty binary heap and show its array representation. Complete binary tree -> an array Step 1: Insert the new item at the end of the array Step 2: bubbleUp Inserting 10 10 10 Inserting 12 10 / 12 12 / 10 0 1 0 1 -- -- -- -- 10 12 -> 12 10 Inserting 1 12 / \ 10 1 0 1 2 -- -- -- 12 10 1 Inserting 14 14 / \ 12 1 / 10 0 1 2 3 -- -- -- -- 14 12 1 10 Inserting 6 14 / \ 12 1 / \ 10 6 0 1 2 3 4 -- -- -- -- -- 14 12 1 10 6 Inserting 5 14 / \ 12 1 / \ / 10 6 5 0 1 2 3 4 5 -- -- -- -- -- -- 14 12 1 10 6 5 14 / \ 12 5 / \ / 10 6 1 0 1 2 3 4 5 -- -- -- -- -- -- 14 12 5 10 6 1 Inserting 8 14 / \ 12 5 / \ / \ 10 6 1 8 0 1 2 3 4 5 6 -- -- -- -- -- -- -- 14 12 5 10 6 1 8 14 / \ 12 8 / \ / \ 10 6 1 5 0 1 2 3 4 5 6 -- -- -- -- -- -- -- 14 12 8 10 6 1 5 Inserting 15 14 / \ 12 8 / \ / \ 10 6 1 5 / 15 0 1 2 3 4 5 6 7 -- -- -- -- -- -- -- -- 14 12 8 10 6 1 5 15 ... 15 / \ 14 8 / \ / \ 12 6 1 5 / 10 0 1 2 3 4 5 6 7 -- -- -- -- -- -- -- -- 15 14 8 12 6 1 5 10 Inserting 3 15 / \ 14 8 / \ / \ 12 6 1 5 / \ 10 3 0 1 2 3 4 5 6 7 8 -- -- -- -- -- -- -- -- -- 15 14 8 12 6 1 5 10 3 Inserting 9 15 / \ 14 8 / \ / \ 12 6 1 5 / \ / 10 3 9 0 1 2 3 4 5 6 7 8 9 -- -- -- -- -- -- -- -- -- -- 15 14 8 12 9 1 5 10 3 6 15 / \ 14 8 / \ / \ 12 9 1 5 / \ / 10 3 6 Inserting 7 0 1 2 3 4 5 6 7 8 9 10 -- -- -- -- -- -- -- -- -- -- -- 15 14 8 12 9 1 5 10 3 6 7 15 / \ 14 8 / \ / \ 12 9 1 5 / \ /\ 10 3 6 7 Inserting 4 0 1 2 3 4 5 6 7 8 9 10 11 -- -- -- -- -- -- -- -- -- -- -- -- 15 14 8 12 9 1 5 10 3 6 7 4 15 / \ 14 8 / \ / \ 12 9 1 5 / \ /\ / 10 3 6 7 4 0 1 2 3 4 5 6 7 8 9 10 11 -- -- -- -- -- -- -- -- -- -- -- -- 15 14 8 12 9 4 5 10 3 6 7 1 15 / \ 14 8 / \ / \ 12 9 4 5 / \ /\ / 10 3 6 7 1 Inserting 11 0 1 2 3 4 5 6 7 8 9 10 11 12 -- -- -- -- -- -- -- -- -- -- -- -- -- 15 14 8 12 9 4 5 10 3 6 7 1 11 15 / \ 14 8 / \ / \ 12 9 4 5 / \ /\ / \ 10 3 6 7 1 11 0 1 2 3 4 5 6 7 8 9 10 11 12 -- -- -- -- -- -- -- -- -- -- -- -- -- 15 14 11 12 9 8 5 10 3 6 7 1 4 15 / \ 14 11 / \ / \ 12 9 8 5 / \ /\ / \ 10 3 6 7 1 4 Inserting 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 -- -- -- -- -- -- -- -- -- -- -- -- -- -- 15 14 11 12 9 8 5 10 3 6 7 1 4 13 15 / \ 14 11 / \ / \ 12 9 8 5 / \ /\ / \ / 10 3 6 7 1 4 13 0 1 2 3 4 5 6 7 8 9 10 11 12 13 -- -- -- -- -- -- -- -- -- -- -- -- -- -- 15 14 13 12 9 8 11 10 3 6 7 1 4 5 15 / \ 14 13 / \ / \ 12 9 8 11 / \ /\ / \ / 10 3 6 7 1 4 5 Inserting 2 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 -- -- -- -- -- -- -- -- -- -- -- -- -- -- -- 15 14 13 12 9 8 11 10 3 6 7 1 4 5 2 15 / \ / \ / \ 14 13 / \ / \ 12 9 8 11 / \ /\ / \ / \ 10 3 6 7 1 4 5 2 B. Using the heap from the previous question, what does top() return? 15 C. Using the heap from the previous question, draw the heap and its array after a call to pop(). Pop steps: 1) Take the value from the highest index and put it in index 0 (and reduce the size of the heap) 2) bubbleDown( 0 ) 0 1 2 3 4 5 6 7 8 9 10 11 12 13 -- -- -- -- -- -- -- -- -- -- -- -- -- -- 2 14 13 12 9 8 11 10 3 6 7 1 4 5 2 / \ / \ / \ 14 13 / \ / \ 12 9 8 11 / \ /\ / \ / 10 3 6 7 1 4 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 -- -- -- -- -- -- -- -- -- -- -- -- -- -- 14 12 13 2 9 8 11 10 3 6 7 1 4 5 14 / \ / \ / \ 12 13 / \ / \ 2 9 8 11 / \ /\ / \ / 10 3 6 7 1 4 5 0 1 2 3 4 5 6 7 8 9 10 11 12 13 -- -- -- -- -- -- -- -- -- -- -- -- -- -- 14 12 13 10 9 8 11 2 3 6 7 1 4 5 14 / \ / \ / \ 12 13 / \ / \ 10 9 8 11 / \ /\ / \ / 2 3 6 7 1 4 5 D. Using the heap from the previous question, what does top() return? 14 E. Using the heap from the previous question, draw the heap and its array after a call to pop(). 0 1 2 3 4 5 6 7 8 9 10 11 12 -- -- -- -- -- -- -- -- -- -- -- -- -- 13 12 11 10 9 8 5 2 3 6 7 1 4 13 / \ / \ / \ 12 11 / \ / \ 10 9 8 5 / \ /\ / \ 2 3 6 7 1 4 F. Using the heap from the previous question, what does top() return? 13 G. Using the heap from the previous question, draw the heap and its array after a call to pop(). 0 1 2 3 4 5 6 7 8 9 10 11 -- -- -- -- -- -- -- -- -- -- -- -- 12 10 11 4 9 8 5 2 3 6 7 1 12 / \ / \ / \ 10 11 / \ / \ 4 9 8 5 / \ /\ / 2 3 6 7 1 4. What are the following Big-Ohs for Heaps? Operation Average-case Worst-case insert O( 1 )* O( height of the heap ) = O( log N ) top O( 1 ) O( 1 ) pop O( log N )** O( height of the heap ) = O( log N ) * On average, 2.607 comparisons (which means 1.607 swaps) ** bubbleDown( 0 ) usually goes pretty deep into the heap BuildHeap ================================= Do the following steps individually, then confer with your neighbor(s): 1. Write down the code for buildHeap() (feel free to use bubbleDown() (or siftDown())). /** * Rearrange the values provided to be a (max) heap * @param values Original value */ public Heap( E[] values ){ heap = new E[ values.length ]; System.arraycopy( values, 0, heap, 0, values.length ); buildHeap(); } /** * Arrange values into a (max) heap */ public void buildHeap( ){ // starting from the last non-leaf node (to the top node), ensure that that subheap is a heap for( int i = (heap.length - 1)/2; i >= 0; --i){ bubbleDown( i ); } } public void bubbleDown( int index ){ // calculate the indices the children int leftChildIndex = (index * 2) + 1; // or (index << 1) + 1 int rightChildIndex = leftChildIndex + 1; // While there is a child and the value at index is out of (heap) order) while ... } 2. Show the resulting heap and its corresponding array after each iteration of buildHeap() given the following initial array: 1 2 3 4 5 6 7 8 Initial: After bubbleDown(3): After bubbleDown(2): After bubbleDown(1): After bubbleDown(0): 0 1 2 3 4 5 6 7 (index) --------------------------------- 1 2 3 4 5 6 7 8 (initial) After bubbleDown(3) After bubbleDown(2) After bubbleDown(1) After bubbleDown(0) 3. What is the Big-Oh for buildHeap()? Naive / simple analysis: O( bubbleDown ) = O( log N ) O( buildHeap ) = O( N / 2 ) * O( bubbleDown ) = O( N / 2 ) * O( log N ) = O( N log N ) Worst-case number of comparison is the sum of the heights of all of the nodes in the heap: O( N ) 20240328 ******************************************************* 2. 2. Trace the following algorithms sorting the following array: 6 4 10 2 8 0 Write the contents of the array according to each specified criterion. For swaps, put a star above the number(s) that are swapped. A. Insertion sort (at the end of each iteration of the outer loop) Start at the front, working your way to the end; insert the first value from the unsorted portion, into the sorted portion by sifting up the values until they are less than the new value. 6 4 10 2 8 0 (original) 4 6|10 2 8 0 4 6 10| 2 8 0 2 4 6 10| 8 0 0 2 4 6 8 10| B. Bubble sort (after each swap) 6 4 10 2 8 0 (original) 4 6 10 2 8 0 4 6 2 10 8 0 4 6 2 8 10 0 4 6 2 8 0|10 4 2 6 8 0|10 4 2 6 0 8|10 2 4 6 0| 8 10 2 4 0 6| 8 10 2 0 4| 6 8 10 0 2| 4 6 8 10 0| 2 4 6 8 10 C. Selection sort (after each swap) Find the largest value (in the unsorted portion) and swap it into it's sorted position 6 4 10 2 8 0 (original) 6 4 0 2 8|10 6 4 0 2| 8 10 (swap 8 with itself to get it into the correct position) 2 4 0| 6 8 10 2 0| 4 6 8 10 0| 2 4 6 8 10 3. Write down the major steps for the following sorting algorithms: A. Insertion sort 1. Start with the first index as being sorted. 2. Insert the first value from the unsorted portion into the sorted portion (into it's sorted position). 3. Repeat step 2, n - 1 times B. Bubble sort 0. For j = 0 ... n - 2 1. Starting at the first index k = 0, swap values at indices k and k + 1 if they are out of order. 2. Repeat, incrementing k up to and including n - j - 2. (This guarantees that the largest value (from the unsorted portion) is now in it's sorted position.) C. Selection sort 0. For j = 0 ... n - 2 1. Select the largest value (in the unsorted portion, 0..n-1-j) 2. Swap it with the value at n - 1 - j (which is its sorted position) 4. Write down the following properties for the stated sorting algorithms: Best Average Worst-case Extra Distinguishing Big-Oh Big-Oh Big-Oh Stable? Space Features ----------------------------------------------------------- Insertion Sort O(n) O(n^2) O(n^2) Yes O(1) Simple, good for small arrays & nearly sorted sorted* Bubble Sort O(n^2)$ O(n^2) O(n^2) Yes O(1) Simple, slow Selection Sort O(n^2) O(n^2) O(n^2) Yes O(1) Simple, O(n) swaps *adaptive (means it runs faster under certain circumstances, like nearly sorted) $Could be O(n) with a simple addition of a boolean value and check Stable ----------- [ key_1, Jym_0, key_3, Jym_1, key_4, ...] -> Jim_0 will appear at a lower index then Jim_1 3. Discuss with your neighbor(s) how the following sorting algorithms work: A. Mergesort Recursively, split the array in half Merge the two halves B. Quicksort Choose a pivot (median of 3 [first, middle and last index]) Get all of the values less than the pivot on the left and the values greater than the pivot on the right Get the pivot in between the two groups (which is in its final sorted position) Recursively sort the left partition Recursively sort the right partition C. Heapsort 5. Trace the following algorithms sorting the following array: 6 4 10 2 8 0 Write the contents of the array according to each specified criterion. For swaps, put a star above the number(s) that are swapped. A. Mergesort (at the end of each merge) 6 4 10 2 8 0 (original) 6 4 10 . . . [not part of the required trace] 6 . . . . . [part of the required trace] . 4 10 . . . . 4 . . . . . . 10 . . . . 4 10 . . . [part of the required trace] 4 6 10 . . . [part of the required trace] . . . 2 8 0 . . . 2 . . [part of the required trace] . . . . 8 0 . . . . 8 . . . . . . 0 . . . . 0 8 [part of the required trace] . . . 0 2 8 [part of the required trace] 0 2 4 6 8 10 [part of the required trace] B. Quicksort (after each swap, including swapping the same element in the same place and the swap for the pivot) (choose the pivot as described in the video) 6 4 10 2 8 0 (original) Pick the pivot from 6 (index 0), 10 (middle index) and 0 (largest index) 6 :|4 10 2 8 0 Swap the pivot out of the way place (the same place as where it was) [part of the required trace] 6 4:|10 2 8 0 6 4: 10 | 2 8 0 6 4 2: 10 | 8 0 [part of the required trace] 6 4 2: 10 8 | 0 6 4 2 0 : 8 10|[part of the required trace] 0 4 2 6 8 10 [part of the required trace] 0 4 2 . . . 2:| 4 0 . . . Swap the pivot out of the way place (the same place as where it was) [part of the required trace] 2: 4 | 0 . . . 2 0 : 4 | . . . 0 2 4 . . . [part of the required trace] 0 . . . . . . . 4 . . . . . . . 8 10 Legend : the boundary between the less than the pivot and greater than the pivot | the right most value that is partitioned C. Heapsort (at the end of each iteration of each loop) Make a heap from an array of unknown values + Heapify: Start halfway through the array (working towards index 0) and bubble down Take the largest value from off of the top and swap it with the last value, then bubble down from the root Repeat the last step for all values 6 4 10 2 8 0 (original) 6 / \ 4 10 / \ / 2 8 0 bubbleDown(index: 2) 6 / \ 4 10 / \ / 2 8 0 6 4 10 2 8 0 bubbleDown(index: 1) 6 / \ 8 10 / \ / 2 4 0 6 8 10 2 4 0 bubbleDown(index: 0) 10 / \ 8 6 / \ / 2 4 0 10 8 6 2 4 0 8 / \ 4 6 / \ 2 0 8 4 6 2 0 | 10 6 / \ 4 0 / 2 6 4 0 2 | 8 10 4 / \ 2 0 4 2 0 | 6 8 10 2 / 0 2 0 | 4 6 8 10 0 0 | 2 4 6 8 10 Big-Oh: Heapify: O( N ) N bubbleDowns: O(N * log N) O(N) + O(N log N) = O(N log N) Best Average Worst-case Extra Distinguishing Big-Oh Big-Oh Big-Oh Stable? Space Features ----------------------------------------------------------- Mergesort n log n n log n n log n Yes O(n) Quicksort n log n n log n n^2 No O(1)** Heapsort n log n n log n n log n No O(1) **Recursive calls require stack space: worst-case: O(n) 8. Discuss with your neighbor(s) how the following sorting algorithms work: Bucket sort Allocate a whole bunch of buckets Put each item (based on its key) in it's correct bucket Go through the buckets in order and pull the items out Radix sort Starting with the least significant digit, bin the keys by that digit Collect the values from the bins Repeat step 1 for each digit, in ascending order of digits 9. Trace the following algorithms sorting the following array: 2152 3180 725 1781 1248 4590 2990 633 Write the contents of the array according to each specified criterion. Bucket sort (show the buckets) Radix sort (at the end of each iteration) Bucket sort 2152 3180 725 1781 1248 4590 2990 633 (original) [0] ... 2152 ... [9999] [0] ... 2152 ... 3180 ... [9999] [0] ... 725 ... 2152 ... 3180 ... [9999] [0] ... 725 ... 1781 ... 2152 ... 3180 ... [9999] ... 633 ... 725 ... 1248 ... 1781 ... 2152 ... 2990 ... 3180 ... 4590 ... 633 725 1248 1781 2152 2990 3180 4590 Radix sort | | | | original v v v v 2152 3180 0725 2152 0633 3180 4590 0633 3180 0725 0725 2990 1248 1248 1248 1781 1781 2152 4590 1781 1248 2152 3180 0633 2152 4590 0633 1781 0725 2990 2990 0725 4590 1781 3180 0633 1248 2990 2990 4590 Best Average Worst-case Extra Distinguishing Big-Oh Big-Oh Big-Oh Stable? Space Features ----------------------------------------------------------- Bucket sort O(N) O(M) O(M) Yes O(M) Radix sort O(N*l) O(N*l) O(N*l) Yes O(k + N) M is the range of values (M >= N) l is the length of the longest input k is the alphabet size 20240409 ******************************************************* What is the difference between a hash and a map? Hashing Exercises ++++++++++++++++++++++++++++++++++++++++++++ Complete the following individually, then turn to a neighbor to confirm your answers. 1. Hash Table Basics 1. What is the underlying data structure for a hash table? An array (the table part) 1) of linked lists 2) (just an array) 2. A _________ determines the location to start to look in a hash table for a key. hash function Default implementation: abs(int(key)) % tableSize Input: Key Output: An index into the array (the hash table) 3. What would the hash function look like if a string is used as the key? First, convert the string to a number 4. Explain the pattern displayed when adding in each character using string folding: StringFoldingDemo.java ASCII values get shifted over, then added into a number (an accumulator) so that several letters are stored in one number until every part of the int is used. 5. What are the requirements for a good hash function? 1. Fast (& easy) to compute O(1) 2. Distribute items evenly throughout the table 3. Involve the entire search key 4. Uses a prime base (if it uses modulo arithmetic) 6. A hash function should be careful not to just use the high- or low-order bits of the key value. What are the high-order and low-order bits? High order bits: The largest values Low order bits: The smallest values 7. Insert the following numbers into a hash table of size 7 and draw the resulting hash table: 0 1 4 9 16 Hash table: 0: 1: 2: 3: 4: 5: 6: Inserting 0 key % tableSize Hash table: 0: 0 1: 2: 3: 4: 5: 6: Inserting 1 Hash table: 0: 0 1: 1 2: 3: 4: 5: 6: Inserting 4 Hash table: 0: 0 1: 1 2: 3: 4: 4 5: 6: Inserting 9 9 % 7 = 2 Hash table: 0: 0 1: 1 2: 9 3: 4: 4 5: 6: Inserting 16 16 % 7 = 2 Collision resolution scheme 1: Hash table: 0: 0 1: 1 2: 16 -> 9 3: 4: 4 5: 6: or Collision resolution scheme 2: Hash table: 0: 0 1: 1 2: 9 3: 16 4: 4 5: 6: 8. Calculate the load factor α for the previous example. load factor α = # of items / hash table size = 5 / 7 2. Hashing: Handling Collisions 1. For each of the following strategies: A. Separate chaining 1. Given a hash table with 7 entries, draw the hash table and its contents after inserting the following numbers: 7, 11, 71, 42, 13, 49 0: -> 49 -> 42 -> 7 1: -> 71 2: 3: 4: -> 11 5: 6: -> 13 2. Describe the major steps for: 1. Inserting an item Hash (using the hash function) to find the "home" slot. Insert the new item at the beginning of the list. 2. Retrieving an item Hash (using the hash function) to find the "home" slot. Look through each key at the index (until it is found or the end of the list is reached). 3. Deleting an item Hash (using the hash function) to find the "home" slot. Look through each key at the index (until it is found [and then remove it from the list] or the end of the list is reached). 4. Displaying all items in the hash table For each slot in the hash table, display all items in the list for that slot 3. Calculate the load factor α load factor α = 6 / 7 B. Linear probing (f(i) = i, or p(K,i) = i) Instead of having an array of linked lists, we just have an array. 1. Given a hash table with 7 entries, draw the hash table and its contents after inserting the following numbers: 7, 11, 71, 42, 13, 49 0: 7 1: 71 2: 42 3: 49 4: 11 5: 6: 13 2. Describe the major steps for: 1. Inserting an item Hash (using the hash function) to find the "home" slot. While the slot is filled, go to the next slot. Then, insert the new item at the empty slot. 2. Retrieving an item Hash (using the hash function) to find the "home" slot. Apply the same probing sequence as for insertion, except that we will stop if the key is found (or a tombstone is found). 3. Deleting an item Hash (using the hash function) to find the "home" slot. While the slot does not have the item we're looking for, and the slot is not empty, go to the next slot. If the item was found, place a tombstone at that slot. 0: 7 1: 71 2: Tombstone 3: 49 4: 11 5: 6: 13 4. Displaying all items in the hash table For each slot in the hash table, display the item (if the slot is not empty). 3. Calculate the load factor α load factor α = 6/7 20240411 ******************************************************* What is the space requirements for a hash table/ An array (the table part) -> O(M) where M is the size of the hash table 1) of linked lists -> O(M + N) 2) (just an array) -> O(M) Hash function in Java: Math.abs(key.hashCode()) % tableSize C. Quadratic probing (f(i) = i^2, or p(K,i) = i^2) 1. Given a hash table with 7 entries, draw the hash table and its contents after inserting the following numbers: 7, 11, 71, 42, 13, 49 0: 7 1: 71 2: 42 3: 4: 11 5: 6: 13 f(i) = i^2 h(42) = (h(x) + f(i)) % 7 = (0 + 0) % 7 = 0 (for i = 0, look in index 0) = (0 + 1^2) % 7 = 1 (for i = 1, look in index 1) = (0 + 2^2) % 7 = 4 (for i = 2, look in index 4) = (0 + 3^2) % 7 = 2 (for i = 3, look in index 2) h(49) = (h(x) + f(i)) % 7 = (0 + 0) % 7 = 0 (for i = 0, look in index 0) = (0 + 1^2) % 7 = 1 (for i = 1, look in index 1) = (0 + 2^2) % 7 = 4 (for i = 2, look in index 4) = (0 + 3^2) % 7 = 2 (for i = 3, look in index 2) = (0 + 4^2) % 7 = 2 (for i = 4, look in index 2) = (0 + 5^2) % 7 = 4 (for i = 5, look in index 4) = (0 + 6^2) % 7 = 1 (for i = 6, look in index 1) = (0 + 7^2) % 7 = 0 (for i = 7, look in index 0) ... = (0 + 500^2) % 7 = ? (for i = 500, look in index ) 2. Describe the major steps for: 1. Inserting an item Hash (using the hash function) to find the "home" slot. While the slot is filled, use the probing function, which checks for indices that are the square of the iteration counter. Then, insert the new item at the empty slot. 2. Retrieving an item Hash (using the hash function) to find the "home" slot. Apply the same probing sequence as for insertion, except that we will stop if the key is found (or a tombstone is found). 3. Deleting an item Hash (using the hash function) to find the "home" slot. Apply the same probing sequence as for insertion, except that we will stop if the key is found. If it's found, replace it with a tombstone. If an empty slot or a tombstone is found, the key is not in the hash table. 4. Displaying all items in the hash table For each slot in the hash table, display the item (if the slot is not empty (nor has a tombstone)). 3. Calculate the load factor α load factor α = 6/7 D. Double hashing (f(i) = i * h_2(x), or p(K,i) = i * h_2(K)) and h_2(x) = R - (x % R) (where R is the prime number just smaller than tableSize M) 1. Given a hash table with 7 entries, draw the hash table and its contents after inserting the following numbers: 7, 11, 71, 42, 13, 49 0: 7 1: 71 2: 49 3: 42 4: 11 5: 6: 13 f(i) = i * h_2(x) and h_2(x) = R - (x % R) (where R is the prime number just smaller than tableSize M) h(42) = (h(42) + i * h_2(42)) % 7 = (0 + 1 * (R - (42 % R))) % 7 = (0 + 1 * (5 - (42 % 5))) % 7 = (0 + 1 * (5 - 2)) % 7 = (0 + 1 * 3) % 7 = (0 + 3) % 7 = 3 (look in index 3) h(49) = (h(49) + i * h_2(49)) % 7 = (0 + 1 * (R - (49 % R))) % 7 = (0 + 1 * (5 - (49 % 5))) % 7 = (0 + 1 * 1) % 7 = (0 + 1) % 7 = 1 (for i = 1) = (0 + 2 * 1) % 7 = 2 (for i = 2) 2. Describe the major steps for: 1. Inserting an item Hash (using the hash function) to find the "home" slot. While the slot is filled, use the probing function, which checks for indices that the iteration counter times a second hash function. Then, insert the new item at the empty slot. 2. Retrieving an item Hash (using the hash function) to find the "home" slot. Apply the same probing sequence as for insertion, except that we will stop if the key is found (or a tombstone is found). 3. Deleting an item Hash (using the hash function) to find the "home" slot. Apply the same probing sequence as for insertion, except that we will stop if the key is found. If it's found, replace it with a tombstone. If an empty slot or a tombstone is found, the key is not in the hash table. 4. Displaying all items in the hash table For each slot in the hash table, display the item (if the slot is not empty (nor has a tombstone)). 3. Calculate the load factor α load factor α = 6/7 Rehashing 1. What is rehashing? Increasing the size of the hash table 2. What are the major steps of rehashing? 1. Calculate a new table size (prime number larger than twice the size) 2. Allocate a memory for a larger hash table (array) 3. For each key in the old hash table, add it to the new hash table (using the new hash function) 3. Why do we rehash? To reduce collisions (so that insertion, retrieval and deletion are still O(1)) 4. When do we rehash? "Re-hash as little as possible" because it's O(M+N) or O(M) The load factor alpha become too high For separate chaining, when the load factor alpha gets above 75% public insertion(){ ... if( loadFactorAlpha() > 0.75 ){ rehash(); } } 20240416 ******************************************************* Graphs Exercises ++++++++++++++++++++++++++++++++++++++++++++ Graph Basics ================================= 1. Identify as many of the graph terms as you can that apply to the following graph: Undergraduate Prerequisites graph graph - a graph G is a collection of two sets: V, a set of vertices and E, a set of edges that connect the vertices directed graph or digraph - {v_1, v_2} - graph in which each edge is associated with an ordered pair of vertices undirected graph or graph - graph in which each edge is associated with an unordered pair of vertices adjacent - a vertex v_1 in a graph G is adjacent to v_2 if there is an edge between v_1 to v_2 adjacent - a vertex v_1 in a digraph G is adjacent to v_2 if there is a directed edge from vertex v_1 to vertex v_2 path - sequence of vertices v_1, v_2, v_3,...v_n where there is an edge from v_i to v_i+1 directed path - sequence of directed edges between two vertices simple path - path in which all vertices are distinct cycle - a path in which first and last vertices are the same simple cycle - a cycle that begins and ends at the same vertex and does not pass through other vertices more than once acyclic graph - graph with no cycles tree - connected, acyclic graph with a specially designated vertex called the root connected graph - there is a path between any two vertices (undirected) strongly connected - there is a path between any two vertices (digraph) weakly connected - there is a path from vertex I to vertex J or from vertex J to vertex I outdegree of a vertex - number of edges extending from the vertex (digraph) indegree of a vertex - number of edges entering a vertex (digraph) degree of a vertex - number of edges adjacent to a vertex complete graph - a graph with each pair of distinct vertices having an edge between them (graph with n vertices and exactly n(n-1)/2 edges) complete directed graph - a directed graph with exactly n(n-1) edges weighted graph - graph in which the edges represent numeric values multigraph - figure which has multiple occurrences of the same edge (two or more edges between two vertices) network - graph in which each edge has an associated positive numerical weight 2. Discuss with your neighbors the advantages and disadvantages of storing the above graph with each of the following: Adjacency list ================================= Advantages: Simple Disadvantages: Overhead for the linked list Adjacency matrix ================================= Advantages: Less memory than adjacency lists (depending on the ratio of edges to vertices; if it's a dense graph) Disadvantages: More memory than adjacency lists (depending on the ratio of edges to vertices; if it's a sparse graph) For each implementation, how could you store the vertex labels? Adjacency list ================================= 1D Array Adjacency matrix ================================= 1D Array How could you store weights? Adjacency list ================================= Change the links to from: 1) Vertex 2) Next to: 1) Vertex 2) Next 3) Weight Adjacency matrix ================================= Just put the weight in the 2D array 3. Given the following graph, BIOL_2010 / \ v v BIOL_2020 EXSC_3830 / | \ v v v EXSC_4000 EXSC_4230 EXSC_4240 | | v v EXSC_4010 EXSC_4260 draw the resulting: 1D array for vertex labels 0: BIOL_2010 1: BIOL_2020 2: EXSC_3830 3: EXSC_4000 4: EXSC_4010 5: EXSC_4230 6: EXSC_4240 7: EXSC_4260 Adjacency list ================================= 1D array of linked lists 0: -> 1 -> 2 1: 2: -> 3 -> 5 -> 6 3: -> 4 4: 5: 6: -> 7 7: Adjacency matrix ================================= 2D array To 0 1 2 3 4 5 6 7 From 0 1 1 1 2 1 1 1 3 1 4 5 6 1 7 4. Discuss with your neighbors the advantages and disadvantages of performing the following common operations on graphs for each implementation: 1. Determine whether there is an edge from vertex i to vertex j Adjacency List: Go to index i in the array, then walk down the list looking for j. O( min(|V|,|E|) ) -> O( |E| ) (where |E| <= |V|) Adjacency Matrix: adjMatrix[i][j] != EMPTY O(1) 2. Find all vertices adjacent TO a given vertex i (for example, if i is EXSC_3830, then EXSC_4000, 4230 and 4240 are adjacent to EXSC_3830) Adjacency List: For vertex i, its every vertex in its linked list: O( min(|V|,|E|) ) -> O( |E| ) (where |E| <= |V|) Adjacency Matrix: for( int j = 0; j < labels.length; ++j){ if( adjMatrix[i][j] != EMPTY ){ // vertex i is adjacent to vertex j } } O( |V| ) 3. Find all vertices adjacent FROM a given vertex j (for example, if j is EXSC_3830, then BIOL_2010 is the only vertex adjacent from EXSC_3830) Adjacency List: For each vertex i, look for vertex j in i's linked list O( |V| + |E| ) Adjacency Matrix: for( int i = 0; i < labels.length; ++i){ if( adjMatrix[i][j] != EMPTY ){ // vertex i is adjacent to vertex j } } O( |V| ) Graph Traversals ================================= 1. List the vertices in the order that the respective search will visit them (starting with vertex A): Depth-first search ================================= A B D E F C G H public void dFS( Vertex v ){ // in a graph class for( each vertex j adjacent to v ){ if( j has not been visited ){ mark j as visited System.out.println( j ); dFS( j ); } } } Breadth-first search ================================= A B C F D G E H bFS( Vertex v ){ Queue q mark v as visited enqueue v onto q while( ! q.isEmpty() ){ i = q.pop() System.out.println( i ); for( each vertex j adjacent to i ){ if( j has not been visited ){ mark j as visited enqueued j onto q } } } } q (top of the front of the queue): Visited: A B C F D G E H Traversal: A B C F D G E H 20240423 ******************************************************* Topological Sorting ================================= 1. Given the list of directed edges below, draw the directed graph: CPSC 1301K -> CPSC 1302K CPSC 1301K -> CPSC 2105 CPSC 1301K -> CYBR 2159 CPSC 1302K -> CPSC 2108 CYBR 2159 -> CYBR 2160 MATH 1113 -> CPSC 1302K MATH 1113 -> MATH 2125 MATH 2125 -> CPSC 2105 MATH 2125 -> CPSC 2108 MATH 2125 -> MATH 5125 MATH 5125 -> CPSC 2108 2. For this graph, determine the topological order. The two main algorithms to do this are: 1. Iteratively look for a vertex that has an outdegree of 0 (it has no successor) and add it to the front of a list 2. Iteratively look for a vertex that has an indegree of 0 (it has no predecessor) and add it to the end of a list After producing the topological order with one of the above algorithms, then repeat the exercise using the other algorithm. No Successor: MATH 1113, MATH 2125, CPSC 1301K, CYBR 2159, MATH 5125, CPSC 1302K, CPSC 2108, CPSC 2105, CYBR 2160 No Predecessor: MATH 1113, CPSC 1301K, CPSC 1302K, MATH 2125, CPSC 2105, CYBR 2159, MATH 5125, CPSC 2108, CYBR 2160 Shortest Paths ================================= Interpret the vertices below as cities and the edges as the cost to lay down fiber optic cable. Calculate the cost from A to each city for the following graphs: Graph 1: A -9- B A -8- F A -5- G B -2- C B -3- G C -7- D C -4- G D -2- E D -1- G E -5- F E -6- G F -7- G vertexSet: Vertices with the lowest path cost from the starting vertex weights: shortest (cheapest, fastest) path from the starting vertex to v that passes through vertices in vertexSet (initialized to ∞) vertexSet: A weights: A B C D E F G 0 9 ∞ ∞ ∞ 8 5 vertexSet: A G weights: A B C D E F G 0 8 9 6 11 8 5 vertexSet: A G D weights: A B C D E F G 0 8 9 6 8 8 5 vertexSet: A G D B weights: A B C D E F G 0 8 9 6 8 8 5 vertexSet: A G D B E weights: A B C D E F G 0 8 9 6 8 8 5 vertexSet: A G D B E F weights: A B C D E F G 0 8 9 6 8 8 5 vertexSet: A G D B E F C weights: A B C D E F G 0 8 9 6 8 8 5 Graph 2: A -2- B A -2- F A -5- C B -3- G B -4- H C -6- E D -8- E D -6- F D -1- G E -5- F G -2 -H vertexSet: A weights: A B C D E F G H 0 2 5 ∞ ∞ 2 ∞ ∞ vertexSet: A B weights: A B C D E F G H 0 2 5 ∞ ∞ 2 5 6 vertexSet: A B F weights: A B C D E F G H 0 2 5 8 7 2 5 6 vertexSet: A B F C weights: A B C D E F G H 0 2 5 8 7 2 5 6 vertexSet: A B F C G weights: A B C D E F G H 0 2 5 6 7 2 5 6 vertexSet: A B F C G D weights: A B C D E F G H 0 2 5 6 7 2 5 6 vertexSet: A B F C G D H weights: A B C D E F G H 0 2 5 6 7 2 5 6 vertexSet: A B F C G D H E weights: A B C D E F G H 0 2 5 6 7 2 5 6 Spanning Trees ================================= Spanning Trees: Connected, undirected graph without cycles The spanning tree of a connected undirected graph G is a subgraph with all of the vertices and "enough" edges to form a tree. (by removing edges) How do we know if a graph has cycles? A connected undirected graph with n vertices must have at least n - 1 edges. If it has n or more edges, then it has a cycle. A---B | | C Vertex Edges ------ ----- 1 0 2 1 3 2 DFS Spanning Tree ~~~~~~~~~~~~~~~~~~~~~~ Run DFS and we'll get a spanning tree public void dFS( Vertex v ){ // in a graph class for( each vertex j adjacent to v ){ if( (v,j) has not been visited ){ mark the edge from v to j as visited // instead of the vertex dFS( j ); } } } 1. For each of the following trees, calculate a DFS spanning tree and a BFS spanning tree (starting at A): Graph 1: (A, B) (A, F) (A, G) (B, C) (B, G) (C, D) (C, G) (D, E) (D, G) (E, F) (E, G) (F, G) DFS Answer: A-B-C-D-E-F-G BFS Answer: A-B A-F A-G B-C F-E G-D Graph 2: (A, B) (A, D) (A, F) (B, C) (B, G) (C, D) (D, E) (E, F) (F, G) DFS Answer: (A, B) (B, C) (C, D) (D, E) (E, F) (F, G) BFS Answer: (A, B) (A, D) (A, F) (B, C) (B, G) (D, E) Minimum Spanning Trees ~~~~~~~~~~~~~~~~~~~~~~ 2. Interpret the vertices below as cities and the edges as the cost to lay down fiber optic cable. What is the least cost to connect every city (starting with city A) for each graph? Draw all of the edges that are part of the solution. Prim's Algorithm ----------- Start at any vertex and add the lowest weighted edge that adds a new vertex. Graph 1: A -9- B A -8- F A -5- G B -2- C B -3- G C -7- D C -4- G D -2- E D -1- G E -5- F E -6- G F -7- G Minimum spanning tree D -1- G D -2- E B -3- G B -2- C A -5- G E -5- F The total weight is : 1 + 2+ 3 +2+ 5+ 5 = 18 20240425 ******************************************************* Graph 2: A -2- B A -2- F A -5- C B -3- G B -4- H C -6- E D -8- E D -6- F D -1- G G -2- H Euler Circuits Exercises ================================= Do the graphs below have Euler circuits (each starting at vertex A)? If so, list the vertices in the order visited. Graph 1 Graph 2 Graph 3