Halting!

Upper and lower bound proofs are very similar. On the consequent part of the proof, the upper bound states f(n)≤cn² while the lower bound states f(n)≥cn². The less than or equal sign changes to a greater than or equal to sign. To prove big-O, you have to over-estimate the function that is in big-O and under-estimate the function that is big-O. When done over and under estimating, a c must be picked to make the right side of the inequality an upper bound. To prove big-Omega it is the other way around. You have to under-estimate the function that is in big-O and over-estimate the function that is big-Omega.

To under-estimate, you would remove a positive term or multiply a negative term. To over-estimate, you would remove and negative term or multiply a positive term.

This week I learned how to prove statement such as ∀f,g,h∈F,(f∈O(g) and g∈O(h))⇒f∈O(h). Intuitively, this statement is true because f grows no faster than g and g grows no faster than h, then f must grow no faster than h.

Since f∈O(g) and g∈O(h), then f(n)≤cg(n) and g(n)≤c'h(n). Then f(n)≤cg(n)≤cc'h(n), which proves f∈O(h).

I was also introduced to the halting problem this week. At first I was confused, Timothy also stated that he was confused in his slog too. After reading the notes on my own, I understood it a lot more and it became clear! Reduction also posed the same issue, but after reading the PDF slides again, I understood it.

I learned that if function f(n) can be implemented by extending to another function such as g(n), then f(n) reduces to g(n). Also, to prove that a function is computable, you have to show that the function reduces to another function that is computable. Lastly, to prove that a function is non-computable, you have to show that the function reduces to another function that is non-computable

Proofs have returned!

Prof. Heap introduced a notation that represent functions that take in a natural number and return a non-negative real number. The notation is ƒ: ℕ →ℝ ^≥0. In the lecture this week I learned how to prove 3n²+2n∈O(n²). ∃c∈ℝ+, ∃B∈ℕ, ∀n∈ℕ, n≥B ⇒ f(n)≤cn². To prove that statement we would have to find equations larger than 3n²+2n which is f(n) and equations less than or equal to cn². Then the equations would have to be linked proving 3n²+2n≤cn².

I also learned how to prove n³∉ O(3n²). First the standard thing to do is to negate the statement and then prove the negation. We want to make n³>c3n². This occurs when n>c3=3c. So we have to make n>3c and n≥B. So the statement in the proof would be, pick n>max(3c, B). Additionally a larger c or B doesn’t hurt, since it still proves n³∉ O(3n²) and it is only an approximation.

How to figure out what is big-Oh of who turned out to be pretty simple between polynomials. You only have to look at the highest degree term. The function with the larger or same degree is the big-Oh. In other words f(n) is in O(g(n)) exactly when the highest-degree term of f(n) is no larger than the highest-degree term of g(n).

Sorting!

 This week I learned the formal definition of O(n²). The formal definition is when n is beyond breakpoint B, f(n) is upper-bounded by cn², where c is come chosen constant multiplier. Ω(n²) is the set of functions that grow no slower than n². Ɵ(n²) is the set of functions that are both O(n²) and Ω(n²).

A fairly intuitive thing that I learned in the lectures this week was that functions similar to nⁿ grow fast and functions similar to log (n) grow slowly.

The sorting algorithm introduced this week was fairly simple, since it was review. I learned a variety of sorting algorithms in high school, such as merge sort, quick sort, insertion sort, etc. I the lecture Prof. Heap went over insertion sort. Insertion sort grows a sorted list within an unsorted list. In each insertion an element is removed from the unsorted portion of the list and inserted within the sorted portion.

One thing I found really surprising was that the loop guard adds one step each time a while loop stops iterating. In addition, lines outside the loops add one step and are constant. Another thing that surprised me was that summation is used to create a formula for worst case running time.

I also learned what a maximum splice function does this week. Maximum splice enumerates all possible slices of a list and calculates the sum of each slice, returning the max. Also, when finding the upper-bound it is okay to overestimate the number of steps and when finding the lower-bound it is okay to underestimate the number of steps.

This week I did the folding problem solving problem. First, I read over the problem and made sure I understood it. The problem asks if I can arrange pennies from two drawers, so that one of them have 48 pennies, using two operations, 1 and r. Secondly, I came up with a plan. My plan was to make a tree of what arrangements I could come up with. Then I would work backwards from 48 and try to get to one of the arrangements that have been confirmed.