Week 12-Proof by Induction

        This week, I was taught proof by induction. This topic is not unfamiliar to me since I already learn it from MAT137. However, by re-learning it in CSC165, my understanding was solidified.  I think the hard part about proof by induction is the idea that by assuming a term works and later proving that the next term works, I am able to demonstrate that all term works. After being taught again in CSC165, I was convinced by the prof that proof by induction does work.
         Proof by induction is a proof technique used to establish a given statement for all natural numbers. It is similar to the idea of dominoes, in which by knowing that domino0(d0) works, I know that d1 works, then d2, then d3 and so on until all dominoes (all natural numbers) have been enumerated. The general structure for proof by induction goes like this:
 1. Assume d0 does fall
 2. Base case: d0 falls # by assumption
 3. Induction step: - assume n a generic natural number, and that dn falls
                              - then dn+1 falls # dn will hit dn+1
                              - then for all n, dn falls implies dn+1 falls
                              - then for all n, dn falls
                              - then d0 falls implies for all n, dn falls
Basically, the central idea is that after proving that the base case works, assume the assumption works for dn, and try to arrive at a conclusion that dn+1 also works.
        Here is an example of proof by induction, (without the quantifiers and bookends):
 claim:

proof:

Lastly, proof by induction is a topic that comes easy to me since I already learned it before. However, the problem about diagonals presented in class troubles me. I was unable to figure out a clear pattern to the boxes since there are too many different combinations of dimensions for the box. Thanks to Loora's blog, I was able to gain some insight.

http://looralicsc165slog.blogspot.ca/2014/11/last-problem-solving.html?showComment=1417589892018#c163994337424380139

Week 11- Halt, computability and many other confusions

        This week, I was introduced to the most confusing concept ever----that nobody can write a halt(f,n) that works for all programs. In order to recount my troubles, I have to first explain what is halt. Basically, halt is a Python function with two arguments. The first argument takes any other function f, and this function f has to take a single input n. The second argument is any input n that can go into the function f. What halt does is that it examines the code in f, and all the data in n, then return the boolean value True if f(n) halts at a certain value of n. If f(n) does not halt at any value of n, then halt(f,n) returns the value False. For some programs, it is possible to write a halt function that tests if the function halts.
        For instance, a halt function can be written to test if function may_halt halts at a specific s.

All I need to do is to check the length of string s. If length of s is not even, which means it's odd, then the program may_halt halts by printing the string s and the string " has odd length", while halt(may_halt, s) returns the value True. Similarly, if the length of s is even, then may_halt(s) iterates forever nonstop and halt(may_halt, s returns False. However, I cannot write a halt for function collatz(n). Maybe in the near future, someone may come up with a code for halt that tests if collatz halts or not, but as for now, no one has any idea how. All we know is that collatz halts for every single n up to more than 2^58, but we don't know if it halts for all n in the set of natural numbers.

Hence, although it is possible to write a halt for may_halt, it is impossible to write a halt(f,n) that works for all programs. The impossibility to write a universal halt confuses me and I could not comprehend why is this concept true. I understand that for functions like collatz, I might not be able to write a halt function. But what makes computer scientists so certain that it is impossible to write a halt that works for all programs? For instance, the fact that we don't know if alien exists does not necessarily mean that they don't exist. It could be that aliens do exist but we just haven't encounter one yet. My confusion is cleared after I was shown its proof.

        The proof for the claim that nobody can write halt(f,n) uses proof by contradiction. Now, consider the function sushi in two cases:

For the first case, assume sushi(sushi) halts, then halt(sushi, sushi) is True and the while loop iterates forever (an infinite loop), which means that sushi(sushi) does not halt (I arrived at a contradiction). For the second case, assume sushi(sushi) does not halt, then halt(sushi, sushi) is False and 2 is returned. This also poses a contradiction since it would mean that sushi(sushi) does halt. Thus, because contradiction occurred in both cases, we cannot write halt(f,n). 

Week 10-Proving General Statements

        From this week and from last week, I learned proofs that involve the definition of lower_bound, upper_bound and limits. Such proofs are very specific about the functions involved in the definitions, and  a function has to be given in order for the proof to work. However, this week, I learned how to prove general statements that does not involve a specific function. In other words, I need to proof certain claims for a general function f and g. What makes this week's material easy is that all these proofs involve similar concepts and formats. The only important thing to keep in mind is to memorize the definition of upper-bound, lower-bound, limits and their corresponding negations. Here is an example of a proof for a general statement:

To begin the proof, I first assume that f, and g both belong to the set of function F. This is because the proof asks me to prove the general statement for all f and g in F. Then I proceed by assuming the antecedent as usual. And from the antecedent, I know that f is lower-bounded by g, hence I can state its definition in the next line. Because I have to assume the antecedent and arrive at the consequent, I have to arrive at the definition that f^2 is lower-bounded by g^2. Hence I have to prove that

is true (where f(n) is f^2 and g(n) represents g^2). From this understanding, I have to pick values for both c and B. Since I don't really know how the proof will turn out, I left the pick c and pick B line empty for now and start by assuming the domain and the antecedent in the following line. Next, I squared f. Since from the antecedent, I know that f is greater than or equal to c'g, I also know that its square is greater than or equal to the square of c'g. In order to use the definition of f lower-bounded by g, n has to be greater than B', hence B can equal to B'. Now that I know what to pick for B, I can go back and write pick B= B'. And because B' is a natural number, B is also a natural number. Then I proceed with my previous calculation and got to that f^2 is greater or equal to c'^2 times g^2. In order to arrive at the consequent that f^2 is greater than or equal to cg^2, all I have to do is make c = c'^2. Hence I know what values to pick for c. And because c' is a positive real number, and real numbers are closed under multiplication, I can state that c is also a positive real number. Now that the proof is finished, all i have to do is to state the bookends and conclude the original claim.

        In conclusion, it is much faster to figure out the values for c and B before tackling the problem. To be able to do this, quickly formulate the proof on a piece of scrap paper. Hence, by figuring out what I have to do in order to arrive at the consequent, I can write up the proof much faster than having to change my c and B values constantly.

Week 9-Prove big-Oh of non-polynomials using limits

        In this week's class, I was taught how to prove that a non-polynomial function(such as an exponential function) grows faster than a polynomial function. To devise such a proof, I need to first learn the the definition of limits and the L'Hopital Rule. A good thing about this lesson is that I was recently taught the application of the L'Hopital Rule, however, the definition of limit used in CSC165 differs from the one I learned in MAT137. To begin, L'Hopital Rule is used to compute the derivative (or the limit) of a function in the form of f/g, where f and g are functions with g not equal to 0. An example is:

where I applied the L'Hopital Rule twice to obtain a denominator that is not equal to 0.

The value I received is positive infinity, meaning that as n approaches positive infinity 3^n/3n^2 also becomes increasingly large (also positive infinity). In other words, as n increases, 3^n becomes much more larger than 3n^2. This understanding is used to prove that 3^n grows at least as fast as 3n^2.

Now here is a complete example for proof using definition of limits:

        In conclusion, to prove that an exponential function is lower-bounded by a polynomial function, first assume c and B. Then prove that the limit of the exponential function divide by the polynomial function approaches infinity when n also approaches infinity. Later, state the formal definition of the limit and pick n in terms of n' and B. Then, just use the definition of limit to prove the consequent of the definition of lower_bound. To sum up, this type of proof is no different than the materials covered last week (such as the proof for lower- and upper-bound). The only difference is that the definition of limits is applied. Hence, I found this week's class to be very easy to understand.

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.