Week 8- Formal definition of big-Oh and its proof structure

        In this week's class, I was taught the formal definition of O(f(n)), which is referred to as the asymptotic upper-bound:

By categorizing a function as O(f(n)) means that the function grows no faster f(n). And this definition simply means beyond breakpoint B, the function g is upper-bounded by f(n).

        An example is to prove that the function f(n)=2n^2 + 1 is upper-bounded by n^2:

The detailed proof structure for this is:

Because the definition for upper-bound begins with there exists, my first line for the proof begins with choosing a c' and a B'. However since I do not know how the proof will turn out, I left the values for c' and B' blank for now. I then proceed to the next line by stating that the values I chose for c' and B' matches their given domain. I then assume a generic natural number n because of its universal quantifier. On the same line, I also assumed the antecedent to be true. Then I squared the antecedent. Since I want to arrive at the equation that 2n^2 + 1 is less than or equal to cn^2, I made B' equal to 1 for simplicity. Hence n^2 is greater than or equal to 1. Because I chose a value for B', I go back and fill in the first line with B' = 1. And since 1 is a natural number, my choice is applicable.  Then, I added 2n^2 to both sides of the inequality, and simplified it to 2n^2 + 1 is less than or equal to 3n^2. Now, it is obvious that in order to prove  2n^2 + 1 is less than or equal to cn^2, all I need is to make c' equal to 3.

        In conclusion, during tests, it is much easier to figure out a value for B' and c' on a piece of scrap paper before writing the formal proof. This is because with more complicated examples, I might have to constantly change my approach.

Week 7- Algorithm’s time complexity

        In week 7, I was introduced to a brand new concept of sorting algorithms and their complexities. Statements, such as “the worst-case runtime of bubble sort is in O(n^2),” that used to make no sense, now made perfect sense to me. However, I have to admit that calculating the worst running time is the hardest part in this course so far.

        To begin, “running time” in computer science does not mean the length of time in which an algorithm is run, rather, it means the number of steps that the algorithm takes to run. And sometimes, the number of steps an algorithm takes to run depends on the size of the input (which is often referred to as n). For instance, a program may take a running time of 2n steps, and another program can take nlogn times to run. However, the number of steps is not important since we only care about the change in running time as input size varies. Hence, constant factors of running times do not matter, only the highest-order term matters, which means 2n^2 is no different than 301n^2 since they are both in the category of n^2  running time.

    The hardest part of this week is to compute the running time for the worst case. By definition, the worst case time complexity of P with input X (in the set of I) of size n is:

And when counting the steps, it is much simpler to break the program into separate parts and then evaluate the number of steps required for each. In general, a return statement requires one step; an if-statement requires at least two steps, where one has to be the evaluation of the condition of the if-statement, and the other steps are the lines to be executed if the condition of the if-statement is satisfied; an assignment statement requires one step; a variable or constant evaluation also requires one step; and arithmetic, comparison or boolean operators also each require one step. Lastly, break the program into simpler parts by letting while loops be a separate entity. After the separations are done, add up the number of steps for each part under the worst-case possible. One thing to keep in mind is to figure out the number of times the while loop iterates as the input size varies. 

An example of linear search:

Line 1 is an assignment statement, so it is evaluated into 1 step. line 6 is a return statement, so it is also evaluated to be 1 step. In the worst case possible, given that len(A) == n, the while loop is iterated exactly 3n times plus one extra step in which the while loop condition is evaluated to be false. To be more specific, with an input size of length n, i is incremented from 0 to (n-1) (since if i = n, the while loop condition would return false), which means the loop is iterated n time. And within the while loop, there are 3 lines. However, in the worst case,  the x that the program is looking for will not be in list A, thus, line 4 will never be executed. This means with each iteration of the while loop, line 2, line 3 and line 5 are evaluated each time. Line 2 is always evaluated because its the while loop condition. Line 3 is always evaluated because it is the if-statement condition, and it will always evaluate to false. Line 5 is evaluated each time because it is an arithmetic operation. This means that in total, with an input size of length n, the while loop contributes 3n steps. However, one cannot forget one last step in which the while loop condition is tested and is evaluated to be false (where i = n), which in turn leads to the return statement in line 6. Thus, in conclusion, the worst case occurs when x is not in list A at all and  WLS(n) = 3n + 3.

Week 6 - Proof by cases

        In this week, I learned about proof by cases, proofs with multiple quantifiers, and proofs involving definitions such as limits and floor. To begin, proofs with multiple quantifiers are no different than having only one quantifier, since the proof statement for “for all” will always begin with “assume…” following an indentation for the second line, while the proof statement for  “there exist” will begin with “pick x= …” with no indentation in the following line. Moreover, proofs involving manipulation of the definition of limits are also very straightforward, since the definition of limits and its epsilon-delta proof are already taught in MAT137. As for the definition of floor, ample examples and solutions are being supplied by the professor. Hence, the only difficulty I encountered in this week is only the topic of proof by cases.

        The reason for my lack of confidence in proof by cases is that the number and type of cases vary depending on the statement itself. No matter how many examples I am taught, the type of cases I encountered are all different. Hence, I was afraid that I might miss a case and forget to consider it during a test. Due to this doubt, I have gathered some tips concerning proof by cases.

        In general, when proving a formula using proof by cases, I have to first split my arguments into different cases while covering all possibilities, then prove the conclusion for each case. For example, when proving x^2 + x is even for all integers x, I have to prove for 2 cases, where one is x is even and the other case is x is odd (since x^2 + x is factored into x(x + 1) which means one of the factor has to be even while the other is odd). Another example where proof by cases is used is when proving “something equals to another thing”. In this situation, I have to prove two cases, where the first case is “something >= the other thing”, and the second case is “something <= the other thing”. By proving both cases are true, I can conclude that the conjunction of the two cases yield equality (=). Furthermore, some tips for generating cases is to break up the domain D into D1 U D2 U D3 U….U Dn, in which the number of cases is n. Lastly, the “Law of the excluded middle”, which states that a formula can only be true or false and nothing in between, can be introduced in my proof so that I can split P into two cases depending on whether it evaluates to true or false (P V not P).

        

Week 5- Prove Using Contradiction

        This week, I was taught different types of proofs such as proof using contrapositive, proof using contradiction, proof for existence and proof about sequences. Among them, the hardest to grasp and understand is proof by contradiction. At first, I don’t know how to establish a contradiction and when should I apply it in proofs. However, as more examples are being shown in class, I realized that there is no such thing as the perfect timing to use proof by contradiction, because it can be used whenever. 

        Generally, proof by contradiction is used when I want to prove the conclusion without establishing or knowing anything about the antecedent. To be more specific, to arrive at a possible contradiction, I first have to identify the statements that I already know is true. Then I prove “P implies Q” by transforming the implication to its contrapositive, which is “not Q implies not P” and assume the conclusion (Q) to be false. I then write down some steps that leads to “not P”, which thus proves that a contradiction exists since P is previously established to be true.

        A quick example to demonstrate proof by contradiction is to prove the statement “there are infinitely many natural numbers.”. First, to derive a contradiction, assume that there is a finite number of natural numbers (which is not Q). If this supposition is true, then there must exist a largest natural number x such that no other natural numbers are greater than it. However, a contradiction is generated since if I double x, I get another natural number y = 2x (y is a natural number because natural numbers are closed under multiplication) that is greater than x (since 2 > 1). Hence, there does not exist a largest natural number x, and I arrived at a contradiction by assuming not Q. As a result, the statement “there are infinitely many natural numbers” is true.

        In conclusion, proof by contradiction is a great technique to use when one is not sure what the antecedent is in the statement. 

Week 4's Transitivity

          In class, we were introduced to the topic of transitivity. This idea simply means that if a ⇒ b, and  b ⇒ c, then a ⇒ c. As simple as this idea may sound, the professor asked the class to negate the statement:    

and simplify it by transforming all implications into disjunctions as a way of proving the entire original implication to be true. Personally, this is the hardest part of Week 4’s lessons since it involves  De Morgan’s Law and many other laws we learned in the previous week, such as the distributive laws:

The other difficulty in simplifying the negation is that the notations become really messy as the implication gradually breaks down into disjunctions. Hence, it was very hard to not make a mistake. In my picture example, I negated the implication by changing the P --> Q to P or not Q following De Morgan’s Law. On the third line, I changed P ---> Q into its equivalent statement not P or Q. I also simplified the negation of the last bracket by employing De Morgan's Law. On the fifth line, I expanded the equation using a similar approach to FOIL in math class. Since all statements are conjoined by or's, Q or not Q is omitted from the equation since it is false. (recap: false or true yields true, however false and true yields false.) On the last line, since all three statements are false, the negation of the original statement is true. Hence, the original implication is true.

        To sum up, the most challenging part about this week's class is to simplify or change the original statement using De Morgans law, distributive law and etc. One mistake during computing could lead to a completely different conclusion. This reminds me that I have to be more careful during future tests.

Universal and Existential Quantification

    In Week 3, the class covered notes on quantifiers. Fortunately, all of the logic was already taught during the first 2 weeks of MAT137. Hence, following along with the class was easy breezy. 

    The first topic being talked about was universal quantification, represented by the symbol ∀. This ‘upside down A ‘ symbol is defined as “for all” or “for every”. When being used in a statement, ∀ can either make all of the examples in the statement true or make all of the examples false. For example, the statement “all even numbers are real numbers” can be written as ∀x∈{even numbers}, x∈R, which is true. Contrarily, the statement “every real number is even,” (∀x∈R, x∈{even numbers}) is false, since odd numbers and rational numbers also belong to the set of real numbers.

    The second topic being discussed is existential quantification, represented by the symbol ∃. This “flipped E” means “there exists” or “there is at least one.” It is used in statements where there are some examples that are true or some examples are false. For instance, the statement ‘there exists an integer that is greater than zero’ can be written as “∃x∈Z, x>0”. This statement is true because it is basically saying “there are some positive integers”, meaning that there could also be negative integers (a proof for this would be the number 3). Now, if I change the existential quantifier in this statement to the universal quantification so that “all integers are positive” , then my statement would be false since a counter-example would be that -2 is also an integer but it is smaller than 0. Differently, if I say “there is an integer between the number 1 and 2” (∃x∈Z, 1<x<2), then this statement is false since that no integers are between 1 and 2.

    Lastly, the two quantifiers can be combined into a more complex statement. For instance, “for all integers, there exists at least one other integer that is greater than the said integer” (∀x∈Z, ∃y∈Z, x<y) or in simpler words “a biggest integer does not exist”, which is true. However, if I switched the order of the statement and turn it the other way around into “∃y∈Z, ∀x∈Z, x<y”, then the statement is false, since it is basically saying that “there exists one integer that is bigger than every other integer”. In conclusion, the order in which an existential or universal quantification is used is very important, and if applied in the wrong way would make a true statement false.

My struggle on Week 1 materials

        In week 1, I was presented with a new approach to tackling complicated problems in CSC165. It followed a detailed 4 steps, which consisted of understanding the problem, formulating a plan, executing the plan, and finally, verifying the solution. I literally laughed at the steps because it seemed so simple and common sense. As effortless as it may sound, each steps actually requires students to record in a way that makes sense to the person marking the paper and to the writer him/herself. 

        When I was presented with a sample problem named “Streetcar drama,” and was asked to apply the new problem-solving mechanism, I was completely confused. First of all, the problem seemed like a normal “solve for x problem,” however information required to create a system of equations was insufficient. Second, the question was presented in a conversation style and some info seemed irrelevant. Therefore, when professor Heap asked the class to solve on their own, I sat on my chair for the entire time, struggling to jot something down. And when the class was discussing the answer to this problem, I realized that this is not high school math. Other than applying the simple skill of solving equations, CSC165 also requires students to logically deduce information based on sentences involving no numbers. Because the class only discussed the approach to the problem but not the answer, I went home and spent some time thinking about the problem. Guided by the class discussion and Polya’s approach, I first began by reading and understanding the problem:

You are on a streetcar during rush hour, and overhear the following conversation fragments between persons A and B:

A: haven’t seen you in a long time! How old are your three kids now?

B: The product of their ages is 36.

A: That doesn’t really answer my question…

B: Well, the sum of their ages (in years) is —[at this point a fire engine goes by and     obscures the rest of the answer.]

A: That still doesn’t really tell me how old they are.

B: Well, the eldest plays piano.

A: Okay, I see, so their ages are—[at this point you have to get off, and you miss the     answer]

Then, I listed the givens:

1) from the first part of the conversation, I know that B has 3 kids with ages a, b, c where abc = 36

2) since the product of the kids’ ages was 36, it is correct to assume that 1 ≤ a, b, c ≤ 36

3) from the sentence “the eldest plays piano,” I know that there is a child who is older than the other two by at least a year

      Despite the little amount of information I extracted, I followed Polya’s approach and continued on by stating the required, which was to find the ages of the three kids, represented by variables a, b, and c. My next step is to devise a plan that can find the solution. My first instinct was that this problem is similar to system of equations, where I can solve for variables when given both the product and sum of the numbers. So I carried out my plan by writing down all the possible three factors between 1 and 36 that can multiply to 36.

        After listing all the possible combinations for a, b, and c, I faced another roadblock — I don’t know the sum of the kids’ ages. With only one equation, the three variables cannot be solved. Applying Polya’s approach, I reverted back to step three and determined what info I was missing. And from there, I changed my original plan by rereading the conversation. After many tries I realized that the two younger kids are probably twins. This is because when A was given the product and the sum of the ages, and was told that the eldest plays the piano, he is able to arrive at the conclusion. The only way this could be possible is that the two younger ones are twins. Anything else becomes impossible to solve since it will involve three distinct variables and only two equations can be created. Furthermore, the sum of the ages is not unique, meaning that at least 2 combinations of ages result in the same sum. This is because even after given the sum and the product, A still couldn’t figure out the combination, since there is more than one possibility. And when given the hint that the oldest plays the piano, A can quickly eliminate one of the solution since the two younger ones have to be twins. So I began writing down the corresponding sum to each combination. It turns out that both 1, 6, 6 and 2, 2, 9 result in a sum of 13. However, 1, 6, 6 does not work because there is only one eldest child. Hence 2, 2, 9 is the only solution to the kids’ ages.

        In conclusion, although I struggled to understand Week 1’s lessons, and was frustrated with my intelligence, I was able to overcome the difficulties. Not only did I familiarized myself with the problem solving mechanism, I also gained insight into a new type of math problem that involves logic and reasoning. Even though I still don’t feel confident about the course materials, I believe through some extra help and hard work, I will gradually become accustomed to this new subject.