Midterm 1 Cheatsheet

Polymorphism Static compile-time polymorphism: implicit casting. Dynamic runtime polymorphism: decide which implementation of a method to use (overrride).

Exceptions Check exceptions: compiler will force you to deal with it. Handle with try catch or add throws in definition. OnCheck exception: compiler does not bother (Error or RuntimeException class)

Asymptotic Growth Rate O(1), O(log n), O(n), O(nLog n), O(n^2), O(n^k), O(c^n), O(n!) Space complexity = Input Space + Auxiliary Space (non input space)

Asymptotic Analysis T (n) ≤ c ⋅ O(x) = Big O (Upper Bound) | Worst Case: T(n) is a member of O(f(n)) if there exist positive constants c and n0 s.t. T(n) <= c * f(n) for all n >= n0. Set of functions slower T(n) ≥ c ⋅ Ω(x) Big Omega (Lower Bound) | Best Case: T(n) is a member of Ω(f(n)) iff there exist positive constants c and n0 st T(n) >= c * f(n) for all n >= n0. Set of functions faster c1 ⋅f(x)≤T(n)≤c2 ⋅f(x)Big Theta (Tight Bound) | Between Upper and Lower Bound: Θ(f(n)) is the set of functions that grow no faster and no slower than f(n)

Amortized analysis is the concept of spreading work over multiple iterations. e.g. O(n) only happens every n passes so is Amortized O(1)

Quadratic Sorts Selection: 1. go through entire list to “select” the minimum element in the list that is not sorted. 2. Swap the minimum element with the one at the start. 3. Repeat Insertion

public void sort(IndexedList<T> indexedList) {
	for (int i = 0; i < indexedList.length() - 1; i++) { 
		int min = i;
		for (int j = i + 1; j < indexedList.length(); j++) {  
			if (this.less(indexedList.get(j), indexedList.get(min))) {
				min = j;
			} 
		}
		if (min != i) { 
			T t = indexedList.get(i); 
			indexedList.put(i, indexedList.get(min));
			indexedList.put(min, t); 
		}
	}
}

Insertion: 1. Assume the first index is sorted. 2. Compare next index to index before it and check if it is less. If so, insert, if not, keep it. for i gets values from 1 to length-1

j gets i  
while j > 0 and val[j] < val[j-1]
	swap val[j] and val[j-1]
	decrement j by 1 

Bubble: 1. Compare first element to next element. Swap if next element is smaller. 2. Then compare second term with next (it will = first term if it was swapped). 3. Swap n times to bubble every biggest one by one to the top

public void sort(IndexedList<T> indexedList) {
	boolean swapped;
	for (int i = indexedList.length() - 1; i > 0; i--) { 
		swapped = false;
		for (int j = 0; j < i; j++) {
			if (less(indexedList.get(j + 1), indexedList.get(j))) { 
				swap(indexedList, j, j + 1); 
				swapped = true;
			}
		}
		if (!swapped) {return; 
		}
	}
}

Stack and Amortized Analysis: LIFO: Single Linked List Stack
push - prepend, pop - head = head.next top - return head.data empty - head == null
Array Stack: push - arr[numElements++] =x : pop - numElements -= 1
Code Contracts: Preconditions: requirements prior to entering a method. Postconditions: expectations at the time the method exits. Invariants: describe the expected state for all instantiated objects of a class.

Java Generics & Test First Development:

@Test
@DisplayName("test pop throws exception if called on an empty stack") public void popThrowsExceptionOnEmptyStack() {
	try { 
		stack.pop();  
		fail("Did not throw the EmptyException");
	} catch (EmptyException ex) {
		System.out.println("pass!");
	}
}
@BeforeEach void setUp() { 
	numbers = new ArrayIndexedList<>(size, defaultValue);
}