CSUS REVIEW SESSION
CSUS REVIEW SESSION
BY NESHMA & FIRZANA
– Slides by Firzana and Neshma
Copyright By PowCoder代写 加微信 powcoder
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 à{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 FWirazladnisapü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 FWirazladnisapü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
Waldispü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
Waldispü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
Waldispü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
Waldispühl.J. (2020). COMP251: Binary se Slides by Firzana and Neshma
Example 2: insert (50) success
Waldispü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
Waldispü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
Waldispühl.J. (2020). COMP251: Divide-and-Conquer (1) [PowerPoint slides]. https://www.cs.mcgill.ca/~jeromew/teaching/251/F2020/COMP251_Lecture21_F2020.pdf
Waldispü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