Show Menu
Cheatography

CPSC221MT Cheat Sheet by

Cheatsheet for CPSC221 midterm (UBC 2016)

Logarithm Rules and Properties

Summations for Printing

Summation Rules

Don`t panic

Insertion Sort - Algorithm

1 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 - Algorithm

1 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 - Algorithm

1 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 Comple­xities

Algorithm
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 Notations

Big-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))

Big-O Complexity Chart

Queue ADT

Queue property
FIFO: First In First Out
Core operations
- enqueue – dequeue – is_empty

Priority Queue ADT

Queue property
Lower Priority Value Out First
Core operations
- insert –deleteMin –isEmpty

Stack ADT

Stack property
LIFO: Last In First Out
Core operations
– push – pop – top – is_empty

d-Heap ADT

child
(i-1)*d+2 ~ i*d+1
parent
⌊(i-2)­/d⌋+1
root
1
next free
size+1

(Min) Heap Tree - ADT

Heap-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 Comple­xity:
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 Simpli­fic­ation Strategy

1) 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 inequa­lit­y(e­qua­lity).
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*lo­g2(­n/n0)

Summation Fomulas

Help Us Go Positive!

We offset our carbon usage with Ecologi. Click the link below to help us!

We offset our carbon footprint via Ecologi
 

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          Related Cheat Sheets

          Visual Studio 2013 Community Cheat Sheet