CS61B Discussion 6 Disjoint Sets and Asymptotics Administrivia Fill out the weekly surveys! ○ Pacing points and feedback you have for us :); check Piazza! Midterm 1 solutions and grades are out! CSM sections are available, http://scheduler.csmentors.org/! Post-midterm advising appointments ○ Sign-up on Piazza or let me know if you want to talk in the discussion survey today. Optional online textbook! ○ You can find readings that correspond to the lecture videos under the ‘Readings’ column of the website Discussion survey (please fill this out!): tinyurl.com/cz-disc6-sp19 Disjoint Sets Also sometimes called “Union Find” keeps track of whether or not elements are connected ○ empires that are constantly conquering one another ○ each empire is identified by a ruling element. Three basic functions: Also sometimes called union(a, b) ○ connect(a, b) ■ brings b into a’s empire (a conquers b) ○ isConnected(a, b) ■ returns whether or not a and b are in the same empire. ○ find(a) ■ Returns the “ruler” of empire a. Implementations of Disjoint Sets Disjoint sets can be implemented in multiple ways, each with its own benefits and drawbacks. ○ Quick Find → quick to find if two are connected ○ Quick Union → quick to connect ○ Weighted Quick Union → quick union, but with some optimization Quick Find Use an array to store which set each element is in. Called quick find because it is very fast to find if two elements are in the same set (isConnected(a,b)), since you just need to check if id[a] = id[b]. 0 4 1 2 3 5 6 { 0, 1, 2, 4 }, {3, 5}, {6} 0 int[] id 0 1 2 3 4 5 6 0 0 3 0 3 6 Analogy: Each set is an “empire” and is identified by its ruler. 0, 3, 6 are the individual rulers and all the other elements belong to their empires. Quick Union Use an array to store the parent of each node -1 indicates that an item is a root. int[] parent 1 0 0 1 1 2 1 0 3 3 4 5 1 6 0 3 1 4 2 6 5 Weighted Quick Union Quick Union,

Lire le document entier