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).