Ch. 2 and Ch. 4 Section 5
2 Getting Started
2.1 Insertion Sort
The sorting problem
My summary: Insert an object x into a stack such that the order of the stack is specific (e.g. increasing), so that in the end, the stack is sorted
Insertion sort - sorting a small number of elements (e.g. sorting a hand of cards)
- Parameter: an Array of sequence n that needs to be sorted, size A.length
INSERTION-SORT(A)
1 for j = 2 to A.length
2 key = A[j]
3 # Insert A[j] into the sorted sequence A[1 .. j - 1]
4 i = j - 1
5 while i > 0 and A[i] > key
6 A[i + 1] = A[i]
7 i = i - 1 # decrement i until condition is not met
8 A[i + 1] = key
- the for loop loops through the 2nd card to the end
- the while loop checks each card before the index in the for loop for until it reaches a smaller number, and is inserted to the right of it, or until it reaches the very (left) end and gets inserted there as the current smallest number
- 'A' is the (to be) sorted hand
Loop Invariants and the correctness of insertion sort
Loop invariant (sometimes?) conditions:
2.2 Analyzing Algorithms
"Cost" of each statement during run-time
Cost may depend on the input size, and which input of that size (best-case, worst-case, etc.)
Cost on this pseudocode (different than the class C++ examples)
Usually, we focus on the worst-case running time, so we have a guarantee on how long the algorithm will run, and since it occurs fairly often
We care most about the order of growth of the running time
2.3 Designing Algorithms
Insertion-sort is incremental
2.3.1 Divide and Conquer (maybe later on 2/16/17?)
4 Divide and Conquer
4.3 Substitution Method for Solving Recurrences
4.4 Recursion-tree method for Solving Recurrences
4.5 Master Method for Solving Recurrences
Problem size: n
#of Subproblems: a
Each subproblem size: n/b
n/b is either the floor or the ceiling, will not affect the asymptotic behavior of the recurrence
Between the n^{log_{b}^{a}} and f(n), the larger of the 2 functions determines the solution to the recurrence, since it will do all of the "work"