Show Menu
Cheatography
  1. Home >
  2. Programming >

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*log­2(n/n0)

Summation Fomulas
 

Metadata

  • Languages:
  • Published: 23rd February, 2016
  • Last Updated: 12th May, 2016
  • Rated: 5 out of 5 stars based on 1 ratings

Favourited By

albinotonnina AHA username_undefined Nazime cddc

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
          OCaml Cheat Sheet