Print Out First Section
Asymptotics
- O(1) -> O(log N) -> O(N) -> O(N log N) -> O(N^2) -> O(2^N) -> O(3^N) -> O(N^N)
- all logarithmic are θ(log n) by change of base rule (differ by only a constant)
- Asymptotic notation only cares about “highest-growing” terms. For example, O(n^2+n) = THeta(n^2)
- Asymptotic notation does not care about leading constants.
- Any exponential with base >1 grows faster than any polynomial
- The base of the exponential matters. For example, 3n= O(4n), but 3n != Ω(4n).
image-20200903014008287
Divide and Conquer
these problems depend on breaking up a bigger problem into smaller problems that are completely independent of each other types of divide and conquer “top down”, usually recursive example: binary search
bin_search(arr, x):
If Len(arr) == 0:
Return false
Mid <- arr[len(arr) / 2)]
If mid == x:
Return mid
Elif mid < x:
Return bin_search(arr[0:mid], x)
Else:
Return bin_search(arr[mid:len(arr)], x)
do work that influences your split break up search space (binary search) Work is done as you go down the tree
– General structure of a recursive algorithm:
∗ Split the problem up.
∗ Make a recursive calls to problems of size n/b
∗ Combine the results. (In time O(n^d) )
“bottom up” example: merge sort (iterative) need to do something with all the problems however there are much more possibilities when the problem is bigger. So, to alleviate work, break into small problems and combine the small problems in an intelligent fashion usually using some property that you have created via your work (in merge sort this invariant is the array is sorted)
in this type: work is done as you come up the tree (you merge the sorted subproblems together)
Proof techniques
- Invariants and induction are pretty similar.
Loop invariant proofs: One possible scheme: prove an invariant is true for all iterations 1 Initialization: the invariant(s) is true prior to the first iteration of the loop 2 Maintenance: if the invariant is true for iteration n, it is true for iteration n+1 3 Termination: when the loop terminates, the invariant is true on the entire input For bubblesort, the invariant is “At iteration i, the sub-array A[1..i] is sorted and any element in A[i+1..A.size] is greater or equalt to any element in A[1..i]”
uid: 202009022351 tags: #teaching