CS101 Flashcards
define log,N
k in the expression 2^k = N
ex
2^4 = 16 -> log_2_,16 = 4
log_2_N = k -> 2^k = N
Big O - O(logN)
+ a problem where the number of elements gets halved each time
+ like binary search
define declarative programming
declarative programming is a programming paradigm—a style of building the structure and elements of computer programs—that expresses the logic of a computation without describing its control flow.
Big 0 of recursive function with multiple recursive calls
int f ( int n ){
if ( n<= 1 ) { return 1; }
return f(n-1) + f(n-1);
}
O(2^n)
Permutations cardinality
factorial
ex: “abcd” permutations have cardinality of 4! = 432*1
ex: Different ways we can give olympic medals to 8 athletes?
+ 8 different athletes can get gold, then 7 remaining can get silver, then 6 remaining can get bronze
+ 876 = 336
Print permutations recursively with backtracking
public void testPerms() {
String s = “abc”;
permute(s.toCharArray(), 0, s.length() - 1);
}
private void permute(char[] arr, int left, int right) {
if (left == right) {
System.out.println(String.valueOf(arr));
} else {
for (int i = left; i <= right; i++) {
swap(arr, left, i);
permute(arr, left + 1, right);
swap(arr, left, i);
}
}
}
private void swap(char[] arr, int left, int right) {
char temp = arr[left];
arr[left] = arr[right];
arr[right] = temp;
}
+ O(nn!) runtime
+ we call permute n times in the first call, then n-1 times in the first level of recursion, then n-2 … so nn-1*n-2..1 which is n!
+ then the printing of the string happens once for each permutation so n * n!. ??? I don’t believe!!!
Formula for calculating big-0 runtime of functions with recursive calls
O(branches^n)
ex: fibonacci -> 1,1,2,3,5,8… has 2 branches per level so O(2^n)
int fib(n){
assert n >= 0;
if( n < 2 ) return 1;
return fib(n-2) + fib(n-1);
}
java shift operator
int twoToTheZero = 1;
int twoToTheThird = twoToTheZero «_space;3;
-2^-3
-2^-3
= 1/-2 * 1/-2 * 1/-2
= -1/8
O(sqrt(n)) vs O(log,n)
for large n, O(sqrt(n)) is much larger than O(log,n)
O(sqrt(n)) example algorithm
func(a){
for( int i = 0; i * i < a ; i ++ ){
print("im i^2 " + i*i)
}
}2^7
128
2^8
256
2^10
1024 Bytes = 1KB
2^16
65,536 Bytes = 64KB
2^20
1,048,576 Bytes = 1MB
approx 1 million
2^30
1,073,741,824 Bytes = 1GB
approx 1 billion
2^32
4,294,967,296 Bytes = 4GB
approx 4 billion
2^40
1,099,511,627,776 Bytes = 1TB
approx 1 trillion
java signed int max and min
max
+ (2^31)-1
+ 2,147,483,647
+ approx 2 billion
min
+ -(2^31)
+ -2,147,483,648
+ approx negative 2 billion
6 optimize and solve techniques
1) remove duplicate work
2) DIY - try to solve an example and see how you naturally did it
3) simplify and generalize
4) base case and build
5) data structure brainstorm
6) work towards the best conceivable runtime
algorithm for printing the matching elements in two arrays
go through first array and place each element into a hashtable
go through second array and lookup each element
O(N+M)
if they’re the same size O(2N) aka O(N)
int stringToInt(String str, int base)
ex:
stringToInt(“11”,2) returns 3
private static int stringToInt(String str, int base) {
//TODO check nulls empties base is 2 to 16
int ret = 0;
int exp = 0;
for (int i = str.length() - 1; i >= 0; i--) {
int digit = charToVal(str.charAt(i));
//TODO check digit range
ret += digit * Math.pow(base, exp++);
}
return ret;
}
mergesort implementation
private void mergeSort(int[] list) {
//TODO error check input
if (list.length <= 1) {
return;
}
int[] left = new int[list.length / 2];
int[] right = new int[list.length - left.length];
System.arraycopy(list, 0, left, 0, left.length);
System.arraycopy(list, left.length, right, 0, right.length);
mergeSort(left);
mergeSort(right);
merge(list, left, right);
}
private void merge(int[] list, int [] left, int [] right){
int iLeft = 0, iRight = 0, iTarget = 0;
while (iLeft < left.length && iRight < right.length) {
if (left[iLeft] < right[iRight]) {
list[iTarget++] = left[iLeft++];
} else {
list[iTarget++] = right[iRight++];
}
}
System.arraycopy(left, iLeft, list, iTarget, (left.length - iLeft));
System.arraycopy(right, iRight, list, iTarget, (right.length - iRight));
}
Heap stored as an array
define methods to determine index of relative nodes
root(), parent(i), left(i), right(i)
root() { return 0; }
parent(i) { return (int) Math.floor(((double)i - 1) / 2); }
left(i) { return ( i * 2 ) + 1; }
right(i) { return ( i * 2 ) + 2; }
Min Heap usage
only used to keep track of a min
note: datastructures that need to keep track of midpoints or medians can maintain an min and max heap
Min Heap sort add
place new number in bottom right of tree and switch with parent as long as parent is less than new node
Min Heap sort remove
+ pop off root
+ place last node at root
+ swap with the lower value child if either child is less than last node
HashTable worst case and common case lookup
worst case O(N)
+ worst case it turns into an unsorted list
common case O(1)
+ compute hash code, index = hash % bucketcount , search for actual item in the bucket
