Cheatsheet for CPSC221 midterm (UBC 2016)
|
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]
|
|
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]
|
|
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
|
|
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)
|
|
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))
|
|
Queue property
FIFO: First In First Out
|
|
Core operations
- enqueue – dequeue – is_empty
|
|
Queue property
Lower Priority Value Out First
|
|
Core operations
- insert –deleteMin –isEmpty
|
|
Stack property
LIFO: Last In First Out
|
|
Core operations
– push – pop – top – is_empty
|
|
child
|
(i-1)*d+2 ~ i*d+1
|
|
parent
|
⌊(i-2)/d⌋+1
|
|
root
|
1
|
|
next free
|
size+1
|
|
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.
|
//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);
//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;
}|
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 inequality(equality).
|
|
5) Substitute back to T(n).
|
No comments yet.
Cheatography n. The art of mapping complex subjects into clear, instantly navigable reference guides.