20250813 ******************************************************* Hospital preferences: | 1st | 2nd | --+-----+-----+ h | | | h'| | | Student preferences: | 1st | 2nd | --+-----+-----+ s | | | s'| | | "h-s in M*" means (by hospital-optimality): Hospital preferences: | 1st | 2nd | | 1st | 2nd | --+-----+-----+ --+-----+-----+ h | s | | Atl| Bob | | h'| | | NY | | | M* (the Gale-Shapley matching) ----------- h - s Atl - Bob "but h is not the worst valid partner for s" There's a hospital (e.g., NY) that Bob likes less than Atl and NY-Bob is a valid match. Student preferences: | 1st | 2nd | --+-----+-----+ s | h | h' | s'| | | | 1st | 2nd | --+-----+-----+ Bob| Atl | NY | Ali| | | "There exists stable matching M in which s is paired with a hospital,
say h', whom s prefers less than h." There's another stable matching between Bob and NY and Bob prefers NY less than Atl. "Let s' be the partner of h in M" Ali is matched with Atl in the other stable matching M ----------- h' - s NY - Bob Hospital preferences: | 1st | 2nd | --+-----+-----+ h | s | | h'| s | | | 1st | 2nd | --+-----+-----+ Atl| Bob | | NY | Bob | | h would rather have s and s would refer have h, so it's unstable Bob would rather have Atl, and Atl would rather have Bob, so it's unstable. 20250820 ******************************************************* 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: Insert 3 Priority Queue: Insert 7 Priority Queue: Top Priority Queue: Pop Priority Queue: Top Priority Queue: Pop Priority Queue: Insert 99 Priority Queue: Top Priority Queue: Pop Priority Queue: What's left in the priority queue (if anything)? 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? B. Name several scenarios where a heap is advantageous. C. Name some scenarios where a heap is not advantageous. 2. Are the following heaps valid? If not, do they violate the structure and/or heap-order property? A. Nodes with the following edges (6 is at the top): 6-5, 6-4, 5-3, 5-2, 4-1 Heap structure property: Heap order property: Heap: B. Nodes with the following edges (1 is at the top): 1-2, 1-3, 2-4, 2-5, 3-6 Heap structure property: Heap order property: Heap: C. Nodes with the following edges (5 is at the top): 1-4, 2-3, 2-5, 4-5 Heap structure property: Heap order property: Heap: 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: Heap order property: Heap: 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: Heap order property: Heap: 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. Inserting 10 Inserting 12 Inserting 1 Inserting 14 Inserting 6 Inserting 5 Inserting 8 Inserting 15 Inserting 3 Inserting 9 Inserting 7 Inserting 4 Inserting 11 Inserting 13 Inserting 2 B. Using the heap from the previous question, what does top() return? C. Using the heap from the previous question, draw the heap and its array after a call to pop(). D. Using the heap from the previous question, what does top() return? E. Using the heap from the previous question, draw the heap and its array after a call to pop(). F. Using the heap from the previous question, what does top() return? G. Using the heap from the previous question, draw the heap and its array after a call to pop(). 4. What are the following Big-Ohs for Heaps? Operation Average-case Worst-case insert O(2.607)=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) 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 the subheap is a heap for( int i = (heap.length - 2)/2; i >= 0; --i){ bubbleDown( i ); } } 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: bubbleDown: O( log n ) buildHeap: N/2 * O( log n) = O( N log N ) Worst-case number of comparisons is the sum of the heights of all of the nodes in the heap: O(N) 20250825 ******************************************************* Graphs Exercises ++++++++++++++++++++++++++++++++++++++++++++ Graph Traversals ================================= 1. For each graph, list the vertices in the order that the respective search will visit them (starting with vertex A): * Breadth-first search * Depth-first search Graph 1 (graph A -- B; A -- C; A -- I; B -- D; D -- G; G -- H; C -- E; C -- F; H -- I; I -- J;): Breadth-first search ================================= A Depth-first search ================================= A Digraph 1 (graph A -> B; A -> C; A -> I; B -> D; D -> G; G -> H; C -> E; C -> F; H -> I; I -> J;): Breadth-first search ================================= A Depth-first search ================================= A Graph 2 (graph A -- B; A -- D; A -- E; B -- C; B -- E; B -- F; C -- F; D -- E; E -- F): Breadth-first search ================================= A Depth-first search ================================= A 2. For Graph 1 and Digraph 1 (above), list the vertices in the order that the respective search will visit them (starting with vertex C): Graph 1: Breadth-first search ================================= C Depth-first search ================================= C Digraph 1: Breadth-first search ================================= C Depth-first search ================================= C 3. Write pseudo code for each of the searches below: Breadth-first search bfs( Vertex i ){ Queue q - initialize with i mark i as visited while( q is not empty ){ v = q.dequeue() // check for unvisited locations foreach u in (neighbor of v){ if( ! u is visited ){ mark u as visited q.enqueue( u ) } } } } visit( Vertex i){ display i's name } Depth-first search dfs( Vertex i ){ Stack q - initialize with i mark i as visited while( q is not empty ){ v = q.pop() // check for unvisited locations foreach u in (neighbor of v){ if( ! u is visited ){ mark u as visited q.push( u ) } } } } 4. Algorithm Efficiency 1. What are the following Big Os? Search Adjacency List Adjacency Matrix BFS O( m + n ) O( n^2 ) DFS O( m + n ) O( n^2 ) 20250903 ******************************************************* Topological Sorting ================================= 1. Assume that you are getting ready for a date. Given the list of activities below, determine an ordering to accomplish all of the tasks: Activity Buy flowers Dinner Dress & groom Make dinner reservations Pick-up date Select activity Topological Ordering: Select activity Make dinner reservations Dress & groom Buy flowers Pick-up date Dinner Activity 2. Given the following digraph, produce a topological order: Digraph with the following edges: MATH_1113 -> MATH_2125; CPSC_1301K -> CPSC_1302K; MATH_1113 -> CPSC_1302K; CPSC_1301K -> CPSC_2105; MATH_2125 -> CPSC_2105; CPSC_1301K -> CYBR_2159; CYBR_2159 -> CYBR_2160; 3. Describe three algorithms to determine a topological order: 1. DFS, appending nodes in reverse order 2. Add nodes that have no outgoing edges, then remove them from the graph. Repeat. 3. Add nodes that have no incoming edges, then remove them from the graph. Repeat. 4. For each of the above algorithms, what is the Θ: 1. Θ(m+n) 2. Θ(m+n) 3. Θ(m+n) Review: ++++++++++++++++++++++++++++++++++++++++++++ What are the important topics of each module? Asymptotic order of growth of any of the algorithms discussed Module 1: Introduction / Gale-Shapley Algorithm ================================= Stable / unstable pairs Algorithm analysis Hospital optimality vs student optimality Module 2: Basics of Algorithm Analysis ================================= Asymptotic order of growth + Binary search + Big-O (O) + Big Omega (Ω) + Big Theta (Θ) Priority queues and heaps + Inserting * bubbleUp + Deleting * bubbleDown + buildHeap + heapify + peek + pop Module 3: Graphs ================================= Trees Cycles Traversal + BFS + DFS Bipartiteness + Testing for Bipartiteness Digraphs Connectivity + Strong components DAGs Topological orders / sorting 20250915 ******************************************************* makeSet findSet( Node u) union( Node u, Node v) Array-Based Implementation ================================= Big-O ~~~~~~~~~~~~~~~~~~~~~~ makeSet: O(1) findSet: O(N) union: O(N) Pointer-based Implementation ================================= Node with reference to object and reference to parent node Big-O ~~~~~~~~~~~~~~~~~~~~~~ makeSet: O(1) findSet: O(log N) union: O(1)