CPSC221MT Cheat Sheet by cddc
Cheatsheet for CPSC221 midterm (UBC 2016)
programming computer algorithm
Logarithm Rules and PropertiesInsertion 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 subarray 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 subarray 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 NotationsBigO T(n) ∈ O(f(n)) if there are constants c > 0 and n0such that T(n) ≤c f(n) for all n ≥n0  BigOmega T(n) ∈ Ω(f(n)) if f(n) ∈O(T(n))  BigTheta 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 
dHeap ADTchild  (i1)*d+2 ~ i*d+1  parent  ⌊(i2)/d⌋+1  root  1  next free  size+1 
(Min) Heap Tree  ADTHeaporder 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) 
Download the CPSC221MT Cheat Sheet
2 Pages
http://www.cheatography.com/cddc/cheatsheets/cpsc221mt/
//media.cheatography.com/storage/thumb/cddc_cpsc221mt.750.jpg
PDF (recommended)
Alternative Downloads
Your Download Will Begin Automatically in 5 Seconds.
Close
Cheatographer
codenut.weebly.com
Metadata
Favourited By
Comments
No comments yet. Add yours below!
Add a Comment
Related Cheat Sheets