Countability!

The lecture this week left me surprised. I couldn't believe that the size or natural numbers was equal to the size of even natural numbers.

I learned that when given two sets, for example X and Y, if there exists a well defined function f: X→Y that is 1-1 and onto, the the size of X is equal to the size of Y. This can be used compare the sizes of sets with infinity many elements. The only issue is finding f: X→Y.

I also learned that any set that is less than or equal to the size of natural numbers qualifies as countable. What also surprised me was that there are countable infinitely many python functions that can be written because each and every python function can be turned into a unique natural number. This also surprised Kevin, which he wrote on his blog.

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.

Running time

In this week’s lectures a lot of content was covered. A lot more than how much is usually covered. I spent more time after the lecture reviewing the material covered as a result. One of the more interesting things I learned in the lecture this week was proof by cases. To prove by cases you have to split the argument into different cases, also the conclusion for each case has to be proved. An example would be, for all real numbers n²+n is even. There would be two cases. One would be where n is even and the other would be where n is odd. A surprising thing that I learned was uniqueness: If there are two natural numbers (m, n) and one of them aren’t equal to zero, there is exactly one pair of natural numbers (q, r) where m = qn + r, n > r >= 0. Another interesting concept I learned this week was running time, which is the number of steps taken by an algorithm. Running time is also independent of the hardware itself, meaning that it only depends on the algorithm. For running time, only how the number of steps grow as the size of the input grows matter. This means that 6n² and 800n² are no different, hence constant factors don’t matter. Also, we only care about large input sizes which means that n²+2 and n²+n are no different, only the highest term matters.

I also learned O(n²), which is called the asymptotic upper-bound. Which means that the function is growing no faster than n². Ω(n²) was also covered. Ω(n²) is called the asymptotic lower-bound. Which means that the function is growing no slower than n². It is also worth noting that asymptotic notation is simplification of real running time.

One thing I found pretty intuitive was that program running time varies with input. There is also a worst case where the running time is the longest for a specific length of input. There is also a best case and average case.

Test week!

This week I had my first midterm test. I felt pretty prepared for it and I think I did fairly well. I reviewed all the PDFs from the lectures and did all the tutorial questions again. I also did a couple tests from that were from last years winter session website. After Prof. Heap posted a practice test, I did it and I did fairly well, so I felt pretty confident for the real test! In the lecture, I learned the non boolean function floor. The symbolic definition of floor is: ⌊x⌋∈∧⌊x⌋≤x∧∀z∈, z≤x⇒z≤⌊x⌋. Also, when working on a proof with a definition such as ∀x∈ℝ, x≤⌊x⌋+1, it helps to fully understand the definition. When figuring out how to prove it, manipulating expressions into forms that are close to what is in the detention also helps. When working on proofs before writing the body doing rough works is highly recommended because you would know whether or not the statement is true and it would help with the structure. Limit proofs were also introduced in the lectures this week. I find them a bit confusing, but I get them to an extent. Usually in a limit proof you would have to leave delta till you learned more about it. Additionally, to prove it you would have to used a backwards search to find delta.

More proofs!

This week’s lecture went more into depth proofs, it was pretty interesting. I found how proving a statement true using the reverse direction interesting. Instead of proving an implication straight on, you can prove the negation and in some cases it will be easier. Also, I learned what the floor of x means. It means the largest integer that is smaller or equal or x. For example, if x was 5.5 then the floor of x would be x. I was also amazed about how a statement is deemed false. To prove a statement false, you prove the negation is true. This also amazed Kevin, which he wrote on his blog. Additionally, I learned how to prove by cases. To prove that n²+n is even, you would have two cases where n is even and where n is odd. Proving an existential true was fairly intuitive. All that has to be done is to finding a single example. Another thing I found interesting was that proofs can consists of different structures, there are different ways to prove a single thing.

This week I did the folding problem solving problem. First, I read over the problem and made sure I understood it. The problem asks to find a method of predicting the number of up and down creases a paper has when folded a number of times. Secondly, I came up with a plan to solve the problem. My plan was to fold the paper one time and write down the number of up and down creases and repeating until I have an appropriate sample size. Then using the data to find two functions that finds the number of up creases and down creases. After getting a bit stuck I looked at the hints and one of them states that one pattern is somehow contained in the other. After that I was thinking about the relation and it came to me. When the paper is folded the initial folds remain in the new pattern.

First taste of proofs

This week’s lectures were fairly interesting. I learned when A bears a relation to B and B bears the same relation to C, then A bears it to C. This means that the relationship is transitive. For example, if ∀x∈X, (P(x)⇒Q(X))∧ (Q(x)⇒R(X)) is true then ∀x∈X, P(x)⇒R(X) is also true. Also, the order of quantifiers matters, ∀x∈X, ∃y∈X means that you choose a y after your enemy chooses a x; on the other hand, ∃y∈X, ∀x∈X means that you choose a y and then your enemy chooses a x. The meaning of statements entirely change when the order of the quantifiers are altered. I was also introduced to the definition of a limit during this week’s lecture. I learned how to find a range for a delta when epsilon is given. For example, when given the ∀e∈ℝ⁺, ∃d∈ℝ⁺, ∀x∈ℝ, |x-2|<d⇒|x²-4|<e and e=2 the method for calculating d would be to plug the y values into the antecedent. Which would give the values |2^0.5-2|=0.586 and|6^0.5-2|=0.449 so delta must be less than the smallest difference (d<0.449). The outline for a proof is also pretty interesting. You “assume” when the quantifier is ∀ and “let” when the quantifier is ∃. Also, when the statement consists of an implication you assume the antecedent. After the body of the proof is complete you introduce the quantifiers. What surprised me was the way to find proofs. The two ways introduced in the lecture was bubble search and tree search. In bubble search and tree search you try to find the chain of antecedents and consequents.

I learned a lot this week in CSC165. A couple symbols were introduced, which are conjunction ∧, disjunction∨ , and negation ¬. I really enjoyed learning about the concept of vacuous truth, where a “false” statement can be proven true. For example, ∀x∈R, x2-2x+2=0 ⇔ x>x+5, can technically be proven true because to disprove an equivalence you have to find a counter example. However, for the statement mentioned earlier there are no solutions to x2-2x+2=0 and x>x+5, meaning that no counter examples exist. As a result, no counter examples exist, meaning the statement can only be true. This blew my mind and also Timothy. He also wrote that it confused him in his blog. The problem-solving session on Friday was also something I enjoyed. The class learned to look at a problem like a computer science function in a way. Thinking of the problem as a set of inputs and outputs helped make the problem easier to solve.

First SLOG of the year!

The first two weeks of University was not as bad as I thought it would be. Time went by a lot faster than I thought it would. I feel like it is because I learned a lot from my courses, such as CSC165. On Monday, before heading to CSC165, I looked over the PDF slides and I wondered what the heck is an upside down "A" and a backwards "E"? After attending class, I learned that ∀ means "for all" and ∃ means "there exists." Also, I found an example of implication Mr. Heap amusing. In his PDF he wrote "if you eat your vegetables, then you can have dessert" and said that his mother said that to him. From that example I learned how an implication does not necessarily go both ways, so having dessert does not necessarily mean you ate your vegetables.

As of now, I feel fairly confident about the material I learned this week. However, earlier this week I did not feel confident. I felt very confused and was unsure about the material because I'm taking MAT135. In MAT135 the professor never went over the symbols and terminology, so I was at a disadvantage from those who took MAT137 because their professor did go over symbols and terminology. Right after the lecture I felt lost in I started reading the course notes to catch up and went ahead of the class. The lectures after that felt like a breeze and it was a good decision to read the course notes.