Optimized Disjoint Set Operations & Algorithm Design Review

cse 373 data structures and algorithms n.w
1 / 18
Embed
Share

Explore the optimization techniques for disjoint set operations and dive into algorithm design concepts through a walkthrough of Kruskal's algorithm. Understand the importance of union-by-rank and path compression in improving the efficiency of disjoint set data structures. Join the autumn 2018 session of CSE 373 with Shrirang (Shri) Mare to enhance your understanding of data structures and algorithms.

  • Disjoint Set
  • Algorithm Design
  • Optimization
  • Data Structures
  • Kruskals Algorithm
rayaanacharya
jake_3 Follow

Uploaded on | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

Download Presentation

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

E N D

Presentation Transcript

  1. CSE 373: Data Structures and Algorithms More on disjoint sets Autumn 2018 Shrirang (Shri) Mare shri@cs.washington.edu Thanks to Kasey Champion, Ben Jones, Adam Blank, Michael Lee, Evan McCarty, Robbie Weber, Whitaker Brand, Zora Fung, Stuart Reges, Justin Hsia, Ruth Anderson, and many others for sample slides and materials ... 1

  2. Today Revisiting Kruskal s algorithm (with union/find operations) Array representation of a disjoint set Review: Answering algorithm design questions CSE 373 AU 18 2

  3. Review Set and union Set: -Collection of elements. -We want to identify all elements in a set with one value, so that findSet(x) == findSet(y) if x and y in one set. -In tree structure, every node has one root. -So use a tree structure for our set, and identified the set as the root element 2 3 1 5 4 5 Union of two elements is union of sets of those elements: -Combine the two trees CSE 373 AU 18 3

  4. Review Improving union Problem: Trees can be unbalanced Solution: Union-by-rank! - let rank(x) be a number representing the upper bound of the height of x so rank(x) height(x) - Keep track of rank of all trees - When unioning make the tree with larger rank the root - If it s a tie, pick one randomly and increase rank by one rank = 0 rank = 0 rank = 0 rank = 2 rank = 1 2 0 4 4 5 3 1 5 CSE 373 AU 18 4

  5. Review Improving findSet() Problem: Every time we call findSet() you must traverse all the levels of the tree to find representative Solution: Path Compression - Collapse tree into fewer levels by updating parent pointer of each node you visit - Whenever you call findSet() update each node you touch to point directly to overallRoot rank = 3 rank = 3 findSet(5) 8 8 11 7 10 9 6 5 4 6 9 10 11 7 12 13 2 4 3 3 12 13 2 5 CSE 373 AU 18 5

  6. Optimized disjoint set runtime makeSet makeSet(x) Without Optimizations With Optimizations findSet findSet(x) (x) Without Optimizations With Optimizations union(x, y) union(x, y) Without Optimizations With Optimizations (x) O(1) O(1) O(1) O(1) O(n) O(n) Worst case: O( Worst case: O(logn logn) ) O(n) O(n) Worst case: O( Worst case: O(logn logn) ) CSE 373 AU 18 6

  7. Worksheet question 1 CSE 373 AU 18 7

  8. Worksheet question 1 CSE 373 AU 18 8

  9. Implementation Use Nodes? In modern Java (assuming 64-bit JDK) each object takes about 32 bytes - int field takes 4 bytes - Pointer takes 8 bytes - Overhead ~ 16 bytes - Adds up to 28, but we must partition in multiples of 8 => 32 bytes Use arrays instead! - Make index of the array be the vertex number - Either directly to store ints or representationally - We implement makeSet(x) so that we - Make element in the array the index of the parent we choose the representative CSE 373 AU 18 9

  10. Array implementation rank = 3 rank = 0 rank = 3 11 1 0 1 5 1 2 6 2 13 14 16 17 3 4 5 7 10 18 8 9 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 CSE 373 AU 18 10

  11. Array implementation rank = 3 rank = 0 rank = 3 11 1 0 1 5 1 2 6 2 13 14 16 17 3 4 5 7 10 18 8 9 0 0 0 1 1 1 2 2 2 3 3 3 4 4 4 5 5 5 6 6 6 7 7 7 8 8 8 9 9 9 10 10 10 11 11 11 12 12 12 13 13 13 14 14 14 15 15 15 16 16 16 17 17 17 18 18 18 -1 -1 -1 -4 1 1 2 2 2 2 2 2 1 1 6 6 7 7 7 7 7 6 -1 -4 11 11 12 12 12 12 11 11 15 15 15 15 17 17 Store (rank * -1) - 1 CSE 373 AU 18 11

  12. Worksheet question 2 CSE 373 AU 18 12

  13. Array method implementation makeSet makeSet(x) add new value to array with a rank of -1 findSet findSet(x) (x) Jump into array at index/value you re looking for, jump to parent based on element at that index, continue until you hit negative number union(x, y) union(x, y) findSet(x) and findSet(y) to decide who has larger rank, update element to represent new parent as appropriate (x) CSE 373 AU 18 13

  14. Graph Review Graph Definitions/Vocabulary - Vertices, Edges - Directed/undirected - Weighted - Etc Graph Traversals - Breadth First Search - Depth First Search Finding Shortest Path - Dijkstra s Topological Sort, Strongly connected components Minimum Spanning Trees - Primm s - Kruskal s Disjoint Sets - Implementing Kruskal s CSE 373 AU 18 14

  15. Next week Monday: Guest lecture on Technical Interviews Wednesday: P vs. NP Thursday (Section): Final review session Friday: Final review session Sunday (tentative): TA lead extra review session CSE 373 AU 18 15

  16. Topics covered in final - Everything we learned in the class - Final is cumulative with more focus on topics we covered after midterm. - So there will be questions on the topics we covered before midterm as well. - Topics not covered in final - B-Trees - Java generics and Java interfaces - Java Syntax Advice: - Make use of exams from previous terms. A practice exam will be posted on Monday. - Review section handouts for how to write good answers (particularly algorithm design questions) - Finish HW7 early so you can focus on Final. CSE 373 AU 18 16

  17. Worksheet question 3 Suppose you are given a connected graph G. Describe how you would figure out if the graph has a cycle. (Answer in at most 3-4 sentences.) CSE 373 AU 18 17

  18. Worksheet question 3 Suppose you are given a connected graph G. Describe how you would figure out if the graph has a cycle. (Answer in at most 3-4 sentences.) Run DFS but keep track of vertices in the stack. If we hit a vertex that is already in the stack, then there is a cycle in the graph. (Another solution is using topological sort, which is a similar idea, but it works only for directed graphs.) CSE 373 AU 18 18

Related


No related presentations.

More Related Content