Exam 1 Deck Flashcards
Fibonachi Time Complexity T(n)
If n<= 2 T(n) = 1 ELSE T(n)=2^n+1 - 1
Fibonachi Recursive Relation
T(n)= T(n-1) + T(n-2)
T(n)? Big-0?
for(int i = 0; i < n; i++){
for(int j = i+1; j< n; j++){
Simple Statement
}
}T(n) = n(n-1)/2 => T(n) = 0.5n^2 - 0.5n
Big 0 => n^2
T(n)? Big-0?
for(int i=0; i<=n; i++){
for(int j=1; j<=n; j++) {
for(int k=n; k>=1; k--) {
sum = i+j+k;
cout<< sum << endl;
}
}
}T(n) = 2 x n x n x (n+1) => 2n^3 + 2n^2
Big 0 => n^3
Master Theorem Case 1:
T(n)=
IF
If ( d > log[b] a )
T(n) = c * n^d
Master Theorem Case 2:
T(n)=
IF
If ( d = log[b] a )
T(n) = n^d * (log n)
Master Theorem Case 3:
T(n)=
IF
If ( d < log[b] a )
T(n) = n^(log[b] a)
Using Master Method:
T(n) = 9T(n/3) + n
What are a, b, c, d?
What is Big-O?
a = 9 b = 3 c = 1 d = 1 Because d = 1 and log<3> 9 = 2 d < log<b> a T(n) = n^(log<b> a) => n^(log<3> 9) T(n) = n^2</b></b>
Using Master Method:
T(n) = T(2n/3) + 1
What are a, b, c, d?
What is Big-O?
a = 1 b=3/2 c= 1 d = 0
log<3/2> 1 = 0 and d = 0
d = log<b> a</b>
T(n) = n^0 * log n => 1 * log n T(n) = log n</b>
Using Master Method:
T(n) = 3T(n/4) + n*log n
What are a, b, c, d?
What is Big-O?
a = 3 b = 4 c= log n d = 1 log<b> a = log<4> 3 = x and 0 < x < 1 d > log<b> a 1 > x T(n) = c * n^d T(n) = n*log n</b></b>
Using Master Method:
T(n) = 2T(n/2) + n
What are a, b, c, d?
What is Big-O?
a = 2 b =2 c = 1 d = 1 log<2> 2 = 1 d= 1 log<b> a = d so T(n) = (n^1) log n T(n) = n log n</b>
Using Master Method:
T(n) = 8T(n/2) + n^2
What are a, b, c, d?
What is Big-O?
a = 8 b = 2 c = 1 d = 2 log<2> 8 = 3 d < log<b> a => 2 < 3 so T(n) = n^(log<b> a) T(n) = n^3</b></b>
List comparison sort algorithms:
Insertion Sort:
Merge Sort: A[n], B[m], C[n+m)
Heaps
Quick Sort
Which can have duplicate values? Heaps or Binary Search Trees?
Heaps
Last Child in a Heap is?
The LOWEST right child
Insertion Sort T(n) Best/Worst?
Best = T(n) = n -1
Worst: T(n) = n^2
Merge Sort T(n) Worst? Which variable are passed in?
Worst: W(n,m) = n+m-1 COMPARISONS
T(n) = nlog n - (n-1)
O(n) = nlog n
A[n], B[m], C[n+m)
Heaps Sort T(n) Worst? Build? Shrinking Cost? Insert/Increase Key? Return Max?
Worst Building Cost = O(n) Shrinking Cost = O(n log n) Worst = O(n log n) Priority Queue (Heap) functions Increase Key (or insert) O(n) = log n Return Max = O(n) = 1
Which comparison sorts are Worst O(n) = n log n?
Heaps and Merge Sort (and on average not worst case Quick Sort)
Which comparison sorts are Worst O(n) = n^2
Insertion Sort and Quick Sort
Quick sort is only n^2 if the list is sorting such that A[n] < A[n+1]
Mostly Quick sort is n log n
BST n = max number of nodes in a tree of given height h. What is the function for n? What is the function for h? What is the worst time complexity?
n = 2^h - 1 h = log (n+1) O(n) = log n
What is the O(n) for BST search?
O(n) = n
In general the O(n) = h
How do you traverse a BST to create a vector?
start at furthest left child
local left-> parent -> local right -> parents parent -> parents right sibling ext
left -> parent -> right recursively basically
How do you delete an item from a BST?
If the item is not present? Nothing
If the item is present in a leaf with no children then delete the leaf
If the item is in a node with 1 child then replace the child with the parent and delete the parent-now-child
if the item is in a node with 2 children: Find the largest item in the LEFT sub tree. Recursively remove it. Use it as parent of the two sub trees
Calculate the BST cost?
Root of tree Cost = 0 + 1
Child cost = depth * probability of node
Tree cost = root + all children costs
In a Huffman tree, the most frequent values used are closer to the _______ of the tree. Thus having a _____ amount of bits.
Top
Smaller/Lower
In a Huffman tree, the least frequent values are stored closer to the ________ of the tree. Thus having a _____ amount of bits.
Bottom
Larger/Higher
Huffman trees can be used to…
Used to represent what?
encode messages. used to represent characters
ASCII has a _______ amout of bits for each character. Huffman has a _______ amount of bits for each character
fixed
dynamic
Left edge has value of _ in a Huffman tree. Right edge has value of _ in a Huffman tree. Characters are stored in ______ nodes.
0
1
leaf
How do we append Huffman characters bits?
Root->Leaf
Count Sorting must be sorting ______ variable type. N input numbers are in a ________ _________.
Integers
Limited Range
Counting Sort has 4 loops put them in order
//fill helper array with 0s for i = 0 to k do C[i] = 0
//count the numbers that equal i for i = 1 to n do C[A[i]] = C[A[i]] + 1
//add them up so we can count their spots later for i = 1 to k do C[i] = C[i] + C[i-1]
//put the items in array B with C[i] and A[j]
for j = n downto 1
do{
i = A[j]
B[C[i]] = A[j]
C[i] = C[i] -1
} END
What is the time complexity of the counting sort?
O(n) = n+k or just O(n) = n
How to make counting algorithm work with negative numbers?
As long a they are negative integers its easy. Add the minimum number to all numbers, sort then subtract the minimum number out again.
How do you do a radix sort?
Radix-Sort (A, d) // d = num of digits in largest number
for i = 1 to d
—–do Counting Sort on A on the ith digit
End
What is the time complexity on Radix sort?
O(n) = d(n+k)
or
O(n) = n
Bucket Sort Worst T(n)? Average case?
O(n) = n^2 Average T(n) = n
When should we use Counting Sort? When should we use Radix Sort? When should we use bucket sort?
Counting sort is good if the number range is not too big.
Radix is good if there are a low number of digits
Bucket sort is good for linked lists, and is dependent on your hasting function.
What are the non-comparison sorting algorithms?
Counting, Radix, and Bucket
On average what is the O(n) of non-comparison sorts? Counting O(n) ? Radix O(n) ? Bucket O(n) ?
Mostly O(n) = n Counting = O(n) = n+k Radix = O(n) = d(n+k) Bucket = O(n) = n^2 but on average = n
How do we construct a Hoffman Tree?
Sort the array of characters by frequency
take the two lowest frequency items (A[1] and A[2]) add them together. That sum is compared to all the other values. Grab the two lowest and join them. When joining the smaller value goes on the left, larger on the right. Continue till tree is completed. Always join the two lowest frequencies.
Modify fibo to allow for dynamic programming int fibo (int n) if n <= 2 return 1 else return fibo (n-1) + fibo (n-2)
int fibo_init ( int n ) {
create array f[n]; //fill initial array with -1
for int i = 0; i < n; i++
f[i] = -1;
return fibo(n); // call the recursion function fibo
}
int fibo (int n)
if n<=2 // check if easy fibo
return 1;
else if f[n] != -1 { //have we solved already?
return f[n];
}
else {
int answer = fibo(n-1) + fibo(n-2)
f[n] = answer; //save the answer for future use
return answer;
}
Matrix
A
r[1,1] r[1,2] r[1,3]
x
r[2,1] r[2,2] r[2,3]
x B t[1,1] t[2,1] t[3,1]]
AB?
this is a 2x3 and a 3x1 = 2x1
so
M[1,1] = r11 x t11 + r12 x t21 + r13 x t31
M[2,1] = r21 x t11 + r22 x t21 + r23 x t31
A : a x b
B : b x c
AB = ?
axc
Multiply A 4 8 0 2 1 6
B
5 2
9 4
AB?
Can we? 3x2 x 2x2 = 3x2 yes
1 2=c 3x2= r x c
4x5 + 8x9 4x2 + 8x4 1
0x5 + 2x9 0x2 + 2x4 2
1x5 + 6x9 1x2 + 6x4 3=r
What is the number of multiplications between AB if A = 12x2 and B = 2x2
AB number of multiplications would be 12 x 2 x 2= 48
Number of ways we can multiply n matrix?
C(n-1) = C(2n-2, n-1) /n Cn = (2n)!/(n+1)!n!
How many ways can you multiply 4 matrix?
C3 = 4 matrix multiply
6!/4! * 3!
6x5
——– = 5
3x2x1
For for a set of functions that we are trying to find the longest set of compatible activities what is: Si Fi Li Pi
Si = start time of activity Fi = finish time of activity Li = longest set of compatible activities (number of|) Pi = which activity is compatible with current activity i
Where is an new item inserted into a heap? How do we restore heap-ness?
New items are inserted at the lowest and most left position. To restore heap-ness we look at the parent and swap if inserted value is larger. continue until not true.
Where is an item removed from in a heap?
Always the top
In a heap the item that is removed leaves a hole, what leaf/child moves to that hole? What do you do to restore heapness?
Lower right child. To restore heap-ness swap with child that is larger. Repeat until not true
