编程辅导 COMP251: Disjoint Sets [PowerPoint slides]. https://www.cs.mcgill.ca/~jerom

CSUS REVIEW SESSION
CSUS REVIEW SESSION
BY NESHMA & FIRZANA
– Slides by Firzana and Neshma

Data Structures
• DisjointSets
• Heaps and Heapsort • RedBlackTrees
• BSTandAVLTrees
Design and Analysis
• Algorithms and Paradigm • DivideandConquer
• Dynamic Programming
• GreedyAlgorithm
• AmortizedAnalysis
• KAHOOT • Q&A
Slides by Firzana and Neshma Slides by Firzana and Neshma

Slides by Firzana and Neshma

Hash table
• What:Alist-baseddatastructurethatusesahashingfunctiontostorekeyvaluepairs
• Why: Used to reduce storage space to O(n) for n keys :unlike direct address table (that
can have a lot of wasted space compared to the number of keys saved in it)and search time to O(1) Hash function h used below h: U à{0,1,…m-1} for table of length m and uses chaining
U Universe of Keys
K Actual keys K1
T Hash Table
h(K1) h(K2)
Slides by Firzana and Neshma

Hash function
• Properties:
• Uniform distribution of keys in the table
• Regularityinkeydistributionshouldnotaffecttheaboveproperty • Examples:
• Division method
• Multiplication method
• Open addressing
Slides by Firzana and Neshma

Hash function
• Division method •h𝑘 = 𝑘𝑚𝑜𝑑𝑑
– d must be chosen carefully
– Tip: choose prime d not too close to a power of 2
REMINDER: BIT SHIFT:
101101 >> 1 = 10110 (right shift)
Division by 𝟐𝒌
• Multiplication method
•h𝑘 = 𝐴.𝑘𝑚𝑜𝑑2! ≫(𝑤−𝑟)
-𝐴, 𝑘 are both 𝑤 bit numbers
– (2!”# < 𝐴 < 2!) - Slower to compute but effective Slides by Firzana and Neshma Open addressing • No chaining 1. Probe the table 2. Insert if slot empty else calculate another hash function • More slots than keys • Deletion is difficult and deleted cell must be marked deleted not NIL Possible hash functions REMINDER! Search must use the same probe sequence Linear probing h𝑘,𝑖 = h$% +𝑖modm Tendency to clustering Quadratic probing h𝑘,𝑖 = h$% +𝑖.𝑐"+𝑖#.𝑐# modm - Must guarantee full permutation - Secondary clustering Double hashing h𝑘,𝑖 = h" 𝑘 +𝑖.h# 𝑘 moem - Second hash function must be relatively prime to guarantee full permutation Slides by Firzana and Neshma Analysis: Hashing with chaining, open addressing NOTE: Average case analysis rather than worst case Hashing with chaining • Note:Assuminguniformhashing • Insertion:𝑶(𝟏) • Deletion: 𝑶 𝟏 + 𝒔𝒆𝒂𝒓𝒄𝒉 𝒕𝒊𝒎𝒆 • Worst case: : 𝑶(𝒏) • Average case: 𝚯(𝟏 + 𝜶) Hashing with open addressing • Note:Assuminguniformhashing • Expectednumberofprobein 1. Unsuccessful search: 𝟏 (𝟏# 𝜶) Note: Expected number of probes to insert is at most the same as above 2. Successful search: 𝟏 . 𝒍𝒐𝒈 𝟏 REMINDER! Load factor : 𝜶 = n keys and m slots Slides by Firzana and Neshma Disjoint Sets Slides by FWirazladnisapüahnld.J.N(2e0s2h0m). aCOMP251: Disjoint Sets [PowerPoint slides]. https://www.cs.mcgill.ca/~jeromew/teaching/251/F2020/COMP251_Lecture9_F2020.pdf Some definitions • Connected components: set of nodes connected by a path (or a single node by itself) • Partition:For𝐵#∪𝐵$∪𝐵%...∪𝐵&=𝐒,for𝐒beingthesamplespaceand𝐵'∩ 𝐵( =∅𝑖𝑓𝑓𝑖 ≠𝑗 andnoneofthesubsetsareempty Slides by Firzana and Neshma Disjoint sets • What:Atreeorlist-basedabstractdatastructure • How: Each node in the partition of nodes has a representative node • Has operations: 1. Find(i):returnstherepresentativeofthesubset(orpartition)thatcontainsi 2. Union(i,j):mergessetcontainingiandj,thechoiceofrepresentativeisdecidedby implementation Set representation Tree representation Slides by Firzana and Neshma • Worstcase a Find(x) is O(n) Union by size Afterunion: • The depth of any node after union isatmost𝒍𝒐𝒈𝒏for𝒏 nodes in the set Union by height After union: • The height of tree is at most log n for n nodes in the set • The tree of height 𝒉 has at least 𝒏𝒉 ≥ 𝟐𝒉 nodes Union (c,z) Slides by Firzana and Neshma Path compression Example: find(m) a If parent[i] == i { return i; }e l s e { parent[i] = find(parent[i]); return parent[i] } Slides by Firzana and Neshma Running time Union(i,j) Quick find Union by size/ height • Unionbysizewithpathcompression:𝑶(𝒍𝒐𝒈𝒏)showntotake𝑶(𝒎𝜶(𝒏)) • Note:𝜶(𝒏))forn 𝟐𝟎𝟒𝟖 −𝑨𝟒(𝟏) ; 𝜶(𝒏)is4 Slides by Firzana and Neshma More resources for disjoint sets • Goodresource:http://www.cim.mcgill.ca/~langer/251/5-disjointsets.pdf Slides by Firzana and Neshma Heaps and Heapsort Slides by Firzana and Neshma • What:Atree-baseddatastructure(completebinarytree) • How: We fill the tree from top to bottom, left to right. Represent using arrays REMINDER! Does not follow BST properties • TwoTypes: • Root: Node with minimum value • Property: Every node is smaller than their children • Root: Node with maximum value • Property: Every node is greater than their children Slides by Firzana and Neshma Heaps: Height and Arrays 1 Root at element 1 NOT 0 Height Properties: • Number of edges in the longest path from that node to a leaf • Heap height = root height: Θ (log n) • Basic operations: Θ (log n) time • Type: Minimum Heap 8 • Height = 3 • Array of length 12: Array Properties: • (int[] A, Index i) • Root: A[1] • Parent[i]: A[Floor(i/2)] • LeftChild[i]: A[2i] • RightChild[i]: A[2i+1] Slides by Firzana and Neshma Heaps: Build Heap Provided an array, build MaxHeap: MaxHeapify(Array A, index i): Visit element at current index (starting: length[A]/2) Check if heap property is met: i. If satisfied: continue to 3 ii. If not satisfied: Heapify and go to 2 Stop if index = 0, if not, go to next element, i-1, (repeat) If the element at index i does not satisfy heap property • LeftChild[i] or RightChild[i] > current
Let the index k, be the (left or right) child whose value is greatest
Change the value of the element at index i with the value of element at index k
Provided a node, build MinHeap:
• Example: MinHeapify:
Add it to the most left spot that is available.
Check if heap property is met
i. If satisfied: continue
ii. If not satisfied: Heapify
Stop if no more nodes to add or (repeat)
If the value of node does not satisfy heap property • CurrentNode < parentNode Check if current node is root • If not: Switch node with parent node and now currentNode = ParentNode (repeat) • If yes: Stop Slides by Firzana and Neshma Heaps: Example Max-Heap (provided Array) START 12345678 12345678 12345678 12345678 12345678 MaxHeapify(4), swap(4,8), heap satisfied at index 8 MaxHeapify(3), swap(3,6), heap satisfied at index 6 MaxHeapify(2), swap(2,5), heap satisfied at index 5 MaxHeapify(1), swap(1,3), heap not satisfied at index 3 MaxHeapify(3), swap(3,6), heap satisfied at index 6 Slides by Firzana and (Ascending) • Steps:GivenanarrayAsizen 1. Build a Max-Heap 2. Start with k = n-1 3. Swap the element at index 1 with element k of array A Descending order: Build Min-Heap i. ii. iii. iv. v. Elements from index n-k up to n is sorted Remaining elements from 1 up to n-k do not satisfy heap property MaxHeapify(1); the root. Repeat step 3 Else: Stop Slides by Firzana and Neshma Example Heapsort (provided Max-Heap) START 12345 12345 swap(1,5), then MaxHeapify(1) K=5 MaxHeapify(2) swap(1,4) then MaxHeapify(1): Property Met K=4 swap(1,3) then MaxHeapify(1): Property Met swap(1,2) then MaxHeapify(1): Property Met Slides by Firzana and Neshma Analysis: Max-Heapify # of nodes at height h in binary 𝑛 = 2!"# − 1 Max-Heapify(Array A, size n) • WorstCase: • Size of largest subtree ≤ &' (Last row of tree is half full) • 𝑻 𝒏 ≤ 𝑻 𝟐𝒏 + Θ(1) 𝟑 • 𝑻𝒏 =𝑶(𝒍𝒐𝒈𝒏) • Or equivalently, • h: the height of the node of MaxHeapify = # nodes in left subtree* + # nodes in right subtree +1 = (2&'# − 1) + (2&'"−1) + 1 =3∗2&'" −1 Rearrange: 𝑻𝒐𝒕𝒂𝒍 𝒏 𝒊𝒏 𝒉𝒆𝒂𝒑 Substitute into * (2&'#−1)= (2∗('"−1) #(*" 𝟐𝒏 ) Slides by Firzana and Neshma Analysis: Build Heap, HeapSort Build Maxheap Loose Upper Bound: • Cost of Maxheap: 𝑶(𝒍𝒐𝒈𝒏) • # of Calls: 𝑶(𝒏) • =𝑶𝒍𝒐𝒈𝒏∗𝑶𝒏 • = 𝑶(𝒏𝒍𝒐𝒈𝒏) Tight Upper bound: • Cost of Maxheap: 𝑶(𝒉) • # of Calls: • # nodes at height h ≤ Ceiling( 𝑪𝒐𝒔𝒕 𝒐𝒇 𝒂 𝑴𝒂𝒙𝒉𝒆𝒂𝒑𝒊𝒇𝒚 ∗ # 𝑴𝒂𝒙𝑯𝒆𝒂𝒑𝒊𝒇𝒚 𝒄𝒂𝒍𝒍𝒔 𝑩𝒖𝒊𝒍𝒅 𝑴𝒂𝒙𝑯𝒆𝒂𝒑 + (𝑬𝒙𝒄𝒉𝒂𝒏𝒈𝒆 𝒆𝒍𝒆𝒎𝒆𝒏𝒕 ∗ 𝒏) + (𝑴𝒂𝒙𝑯𝒆𝒂𝒑𝒊𝒇𝒚 ∗ 𝒏) • (For loop n-1 times) • ∑!"# (!"# ∗𝑂(h) • 𝑂 (' ∑𝒉"𝒍𝒐𝒈𝒏 𝒉 ) //series ( 𝒉"𝟎 𝟐𝒉 • 𝑂(𝑛=𝑶(𝒏) • = ∑𝒉$𝒍𝒐𝒈𝒏 𝒉$𝟎 • Build MaxHeap: 𝑶(𝒏) • Exchange element: 𝑶(𝟏) • Max-Heapify: 𝑶(𝒍𝒐𝒈𝒏) • 𝒏+𝒏+𝒏𝒍𝒐𝒈𝒏 • = 𝑶(𝒏𝒍𝒐𝒈𝒏) Slides by Firzana and Neshma Slides by Firzana and Neshma • What: A variation of a binary search tree (BST) that is self-balancing • BST attributes + 1 bit (represents the color: black/red) • All leaves / empty trees: color black (represent using Nil, color[Nil] = black) • Operations: 𝑂(𝑙𝑜𝑔𝑛) • Height: 𝑂(𝑙𝑜𝑔𝑛) // n number of nodes Don’t usually show sentinels Nil Nil Nil Nil Nil Nil Nil Slides by Firzana and Neshma Red : Properties & Height Properties 1. A node is either Red or Black 2. The Root is Black 3. All leaves (nil) are • Heightofnode:h(x) • # edges in the longest path to a leaf • Blackheightofnode:bh(x) • # of black nodes on the path from node to leaf • Not including x 4. A Red node has children nodes colored black / No consecutive red nodes 5. Each node: Every path to a leaf has same # of black nodes / same bh • Blackheightoftree=bh(root) • Lemma1: Node with h(x), 𝒃𝒉 𝒙 ≥ 𝒉 𝒙 • Lemma2: Rooted at node x, subtree has ≥ 𝟐𝒃𝒉 𝒙 • Lemma3: T with n internal nodes: height h ≤ 𝟐 ∗ 𝒍𝒐𝒈(𝒏 + 𝟏) internal nodes Slides by Firzana and Neshma Red : Insert Node Insert node like you would with BST: Compare with root all the way to the bottom II. Inserted to a leaf node Color node to be red RB-Fixup: Check Red Properties by: // While the parent[x] is Red Re-Coloring Nodes II. Rotation Slides by Firzana and Neshma GrandParent[x] Let x be the inserted node Red Example Slides by Firzana and Neshma Property 4 violated • TheUncleisRed • TheGrandParent[x]is : 1. ChangeParent[x]andUncle[x]to Black 1. Property 5 violated! 2. ChangeGrandParent[x]toRed 1. Property 5 restored 3. xpointermoves2levelup 1. x = GrandParent[x] GrandParent[x] Parent[x] 6 Applies to right child GrandParent[x] Slides by Firzana and Neshma 6 8 Nil Nil Slides by Firzana and Neshma Property 5 is violated! • TheUncle[x]isblack • xisrightchild Grandarent[x] x remains the same level Left Rotate at Parent[x] Parent and x switch Parent[x] = x, x = Parent[x] Grandarent[x] Slides by Firzana and Neshma Slides by Firzana and Neshma Property 5 is violated! • TheUncle[x]isblack • xisaleftchild Color Parent[x] Black, GrandParent[x] Red Property 4 violated! Rotate Right on GrandParent[x] Property 4 is met. Parent[x] is black so stop GrandParent[x] GrandParent[x] Slides by Firzana and Neshma Parent[x] 7 Nil Nil 4 Nil Nil Nil Nil 12 Nil Nil Nil Nil Slides by Firzana and Neshma Red : Insert Analysis • To insert (before fix-up) / Insert in BST / height of RB Tree: 𝑂(𝑙𝑜𝑔𝑛) • Change colour to Red: 𝑂(1) • RB-Fixup: • While loop if Case 1 • Recoloring: 𝑂 1 • Case 1: x moves 2 levels up • At most 2 rotations: Case 2 and Case 3 • At most loops: 𝑂(𝑙𝑜𝑔𝑛) • 𝑶(𝒍𝒐𝒈 𝒏) 𝒕𝒊𝒎𝒆 Slides by Firzana and Neshma BST & AVL Trees Slides by FWirazladnisapüahnld.J.N(2e0s2h0m). aCOMP251: Binary search trees, AVL trees & AVL sort [PowerPoint slides]. https://www.cs.mcgill.ca/~jeromew/teaching/251/F2020/COMP251_Lecture6_F2020.pdf Binary Search Tree(BST) • Properties: Nodes smaller than the parent are in left subtree Nodes bigger than the parent are in right subtree • Operations: Best case: Balanced tree h = 𝜣(𝒍𝒐𝒈 𝒏) Operations Time taken for tree with height h Search (Tree, Key) 𝜣(𝒉) Insert (Tree, Key) 𝜣(𝒉) Delete (Tree, Key) 𝜣(𝒉) Note: h = 1 + max (height(left child) , height(right child)) arch trees, AVL trees & AVL sort [PowerPoint slides]. https://www.cs.mcgill.ca/~jeromew/teaching/251/F2020/COMP251_Lecture6_F2020.pdf Worst case: Unbalanced tree Slides by Firzana and ̈hl.J. (2020). COMP251: Binary se Height of AVL tree is always O(log n) BST SUCH THAT HEIGHT OF ANY TWO CHILD SUBTREES DIFFERS BY AT MOST ONE Slides by Firzana and ̈hl.J. (2020). COMP251: Binary search trees, AVL trees & AVL sort [PowerPoint slides]. https://www.cs.mcgill.ca/~jeromew/teaching/251/F2020/COMP251_Lecture6_F2020.pdf Violates AVL property! Balance factor Waldispühl.J. (2020). COMP251: Binary search trees, AVL trees & AVL sort [PowerPoint slides]. https://www.cs.mcgill.ca/~jeromew/teaching/251/F2020/COMP251_Lecture6_F2020.pdf Slides by Firzana and Neshma arch trees, AVL trees & AVL sort [PowerPoint slides]. https://www.cs.mcgill.ca/~jeromew/teaching/251/F2020/COMP251_Lecture6_F2020.pdf Waldispühl.J. (2020). COMP251: Binary se Slides by Firzana and Neshma Example 1: insert (15) arch trees, AVL trees & AVL sort [PowerPoint slides]. https://www.cs.mcgill.ca/~jeromew/teaching/251/F2020/COMP251_Lecture6_F2020.pdf Waldispühl.J. (2020). COMP251: Binary se Slides by Firzana and Neshma Example 2: insert (50) fail arch trees, AVL trees & AVL sort [PowerPoint slides]. https://www.cs.mcgill.ca/~jeromew/teaching/251/F2020/COMP251_Lecture6_F2020.pdf Waldispühl.J. (2020). COMP251: Binary se Slides by Firzana and Neshma Example 2: insert (50) success Waldispühl.J. (2020). COMP251: Binary search trees, AVL trees & AVL sort [PowerPoint slides]. https://www.cs.mcgill.ca/~jeromew/teaching/251/F2020/COMP251_Lecture6_F2020.pdf Slides by Firzana and Neshma Algorithm : AVL insert Suppose x is lowest node violating AVL • Ifxisright-heavy: If x’s right child is right-heavy or balanced: Left rotation Else: Right followed by left rotation • Ifxisleft-heavy: If x’s left child is left-heavy or balanced: Right rotation Else: Left followed by right rotation 4. Then continue up to x’s ancestors. arch trees, AVL trees & AVL sort [PowerPoint slides]. https://www.cs.mcgill.ca/~jeromew/teaching/251/F2020/COMP251_Lecture6_F2020.pdf Waldispühl.J. (2020). COMP251: Binary se Slides by Firzana and Neshma Run time BST/AVL sort • BSTsort: 1. Build a BST out of the given keys (unsorted) 2. Run an in-order traversal to print the keys in sorted order (run time 𝜣(𝒏)) 3. Best case: 𝛀(𝒏 𝒍𝒐𝒈 𝒏) for insertion 𝜣(𝒍𝒐𝒈 𝒏) 1. Worst case: 𝜣(𝒏𝟐) for insertion 𝜣(𝒏) • AVLsort: 1. Same as BST sort but with AVL tree 2. Best/worst case: 𝐎(𝒏 𝒍𝒐𝒈 𝒏) for insertion 𝜣(𝒍𝒐𝒈 𝒏) Slides by Firzana and Neshma KAHOOT ! Data Structures Site: kahoot.it PIN: Slides by Firzana and Neshma Quick Break Slides by Firzana and Neshma Algorithms Paradigm Slides by Firzana and Neshma Recursive backtracking example • Anautobiographicalnumberisanumbersuchthatthefirstdigitisthenumber of zeros in the number, the second digit is the number of ones in the number, ..., and the tenth digit is the number of 9 in the number. The first digit must be non-zero. • For example: 1210. • Question: find a 5-digit autobiographical number Slides by Firzana and Neshma Question: find a 5-digit autobiographical number What do we know? 1. Each digit has 5 options [0,1,2....4] Please note that in the recording I said it has 10 options and that is incorrect!! 2. First digit needs to be non-zero 3. Value of each digit depends on all other digits for example if the first digits is 8 then there has to be 8 zeroes in the number. 4. All the digits must add to 5 Slides by Firzana and Neshma Question: find a 5-digit autobiographical number Slides by Firzana and Neshma Slides by Firzana and Neshma Divide and Conquer Waldispühl.J. (2020). COMP251: Divide-and-Conquer (1) [PowerPoint slides]. https://www.cs.mcgill.ca/~jeromew/teaching/251/F2020/COMP251_Lecture21_F2020.pdf Waldispühl.J. (2020). COMP251: Divide-and-Conquer (2) [PowerPoint slides]. https://www.cs.mcgill.ca/~jeromew/teaching/251/F2020/COMP251_Lecture22_F2020.pdf Slides by Firzana and Neshma Divide and Conquer • Divide the problem into sub-problems that are like the original problem but smaller in size • Conquerthesub-problemsbysolvingthemrecursively.Iftheyaresmall enough, just solve them in a straightforward manner. • Combinethesolutionstocreateasolutiontotheoriginalproblem Slides by Firzana and Neshma Sorting application Obvious applications Some problems become easier once elements are sorted Non-obvious applications. Organize an MP3 library. Identify statistical outliers. Convex hull. Display Google PageRank results. Binary search in a database. Closest pair of points List RSS news items in reverse chronological order Remove duplicates in a mailing list. Minimum spanning trees (Kruskal's algorithm). Slides by Firzana and Neshma Merge sort thenq= 𝒑-𝒓 𝟐 MergeSort (Array, p , r) { if (p < r) Do practice Loop invariant property for Merge or merge-sort MergeSort( A, p , q) MergeSort(A, q+1, r) Merge (A,p ,q, r) Initial call: MergerSort (A, 1, n) Slides by Firzana and Neshma Analysis of Merge sort • Divide: computing middle take 𝜣(𝟏) • Conquer: solving two sub problems takes 2 T(𝒏/𝟐) • Combine : merging n elements takes 𝜣 𝒏 • Runningtime: 𝑻 𝒏 =𝜣(𝟏)forn=1 𝑻𝒏 =2T 𝒏𝟐 +𝜣(𝒏)forn>1 Thus,𝑻 𝒏 =𝜣(𝒏𝒍𝒐𝒈𝒏)
Slides by Firzana and Neshma

Divide and conquer Master theorem
Slides by Firzana and Neshma

Master method
Goal. Recipe for solving common divide-and-conquer recurrences: T ( n ) = a T nb + f ( n )
・a ≥ 1 is the number of subproblems.
・b > 0 is the factor by which the subproblem size decreases.
・f (n) = work to divide/merge subproblems.

程序代写 CS代考加微信: powcoder QQ: 1823890830 Email: powcoder@163.com

Related Posts