Cheatography
https://cheatography.com
Cheatsheet for CPSC221 midterm (UBC 2016)
Logarithm Rules and Properties
Insertion Sort - Algorithm1 3 7 2 0 | [1 3 7]2 0 | [1]3 7 2 0 | [1 2 3 7] 0 | [1 3]7 2 0 | [0 1 2 3 7] |
Starting from one end, ensure the sub-array sorted in each pivot
Selection sort - Algorithm1 3 7 2 0 | [0 1 2]3 7 | [0]1 3 7 2 | [0 1 2 3]7 | [0 1]3 7 2 | [0 1 2 3 7] |
Starting from one end, ensure the sub-array sorted in each pivot
Bubble sort - Algorithm1 3 7 2 0 | 1 2(0 3)7 | 1 3(2 7)0 | 1(0 2)3 7 | 1 3 2(0 7) | (0 1)2 3 7 | 1(2 3)0 7 | 0 1 2 3 7 |
Binary comparison and swap, shift each pivot by at most 1 position in an iteration
| | Sorting ComplexitiesAlgorithm | Time | | Space | | Best | Worst | Worst | Bubble Sort | O(n) | O(n^2) | O(1) | Insertion Sort | O(n) | O(n^2) | O(1) | Selection Sort | O(n^2) | O(n^2) | O(1) | Quicksort | O(n log(n)) | O(n^2) | O(log(n)) | Heapsort | O(n log(n)) | O(n log(n)) | O(1) | Mergesort | O(n log(n)) | O(n log(n)) | O(n) |
Asymptotic NotationsBig-O T(n) ∈ O(f(n)) if there are constants c > 0 and n0such that T(n) ≤c f(n) for all n ≥n0 | Big-Omega T(n) ∈ Ω(f(n)) if f(n) ∈O(T(n)) | Big-Theta T(n) ∈ Θ(f(n)) if T(n) ∈O(f(n)) and T(n) ∈ Ω(f(n)) |
Queue ADTQueue property FIFO: First In First Out | Core operations - enqueue – dequeue – is_empty |
Priority Queue ADTQueue property Lower Priority Value Out First | Core operations - insert –deleteMin –isEmpty |
Stack ADTStack property LIFO: Last In First Out | Core operations – push – pop – top – is_empty |
d-Heap ADTchild | (i-1)*d+2 ~ i*d+1 | parent | ⌊(i-2)/d⌋+1 | root | 1 | next free | size+1 |
(Min) Heap Tree - ADTHeap-order property parent’s key <= children’s keys | Structure property nearly complete tree | Heapify algorithm Heapify the tree from bottom up, percolate DOWN a node as deep as needed for each node. |
Binary Heap Operations Complexity:
Heapify - O(n)
Find Min - O(1)
Insert - O(log(n))
Delete - O(log(n))
| | Loop -> (Tail) Recursion//Loop
int i = 0;
while (i < n)
doFoo(i);
i++;
//Recursion
void recDoFoo(int i, int n){
if (i < n) {
doFoo(i);
recDoFoo(i + 1, n);}
}
recDoFoo(0, n);
|
Equivalent for loop:
for (int i=0; i<n; i++) doFoo(i);
Tail Recursion -> Iteration//Tail Recursion
int fact_acc (int n, int acc) {
if (n)
return fact_acc(n –1, acc * n);
return acc;
}
//Iteration
int fact_acc (int n, int acc) {
for(;n;n--)
acc = acc * n;
return acc;
}
|
Recurrence Simplification Strategy1) Find T(n) for the base cases. | 2) Expand T(n) for the general patterns. | 3) Drive the recursive term to the base case. | 4) Solve and represent k with n by inequality(equality). | 5) Substitute back to T(n). |
e.g.
T[n <= n0] = C1
T[n]= T[n/2]+C2
-> T[n] = T[n*(1/2)]+C2
-> T[n] = T[n*(1/2)^k] + k*C2
Let n*(1/2)^k <= n0 -> T(n*(1/2)^k) = C1
-> n*(1/2)^k * (2)^k <= n0* (2)^k
-> n/n0 <= (2)^k
-> log2(n/n0) <= log2((2)^k)
-> log2(n/n0) <= k
-> T[n] = C1+k*C2 = C1 + C2*log2(n/n0)
|
Help Us Go Positive!
We offset our carbon usage with Ecologi. Click the link below to help us!
Created By
codenut.weebly.com
Metadata
Favourited By
Comments
No comments yet. Add yours below!
Add a Comment
Related Cheat Sheets