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) |
Created By
codenut.weebly.com
Metadata
Favourited By
Comments
No comments yet. Add yours below!
Add a Comment
Related Cheat Sheets