SLOG 10 November 23rd 2014

During this two lecture week, I learned about the existence of problems that cannot be solved through algorithms.  During the first lecture, the professor introduced the problem about finding out whether or not a program will halt, or stop, either because it has completed its task, or due to some error.  We can't simply run the code and determine whether or not it will halt, because we cannot determine whether the program is taking a long time or if it is stuck in an infinite loop that will never end.  However, there is a function called halt which is able to return a boolean representing whether or not the function being tested will halt.  One of the problems that the professor introduced to us is about the function naval gaze.  What naval gaze does is that it calls halt upon halt, and the conclusion is that the results are always contradicting what the function is supposed to do.  I did not understand exactly how this concept worked, and i was planning on studying the notes this weekend, however the course website is not yet functioning, and all of the links of the cache didn't work, so I'm planning on going to the professor's office hours next week in order to get a better idea of why some probems can't be solved through computations.

SLOG 9 November 17th 2014

During last week's CSC165, I learned about what big O and big Omega meant, and how the functions look like graphically, as well as how to prove that some functions are of big O or big Omega of others.  I learned that a big O function of a function f is a function that always produces a y value greater than f(x) when x is greater than a certain value.  This value is denoted as B, the break point.  The value c in the definition of a big O function is essentially the multiplier that makes the big O function greater than f.  Big Omega is basically the same as big O, except big Omega is a function that is always below function f after the break point.  What below means is that every y value that big Omega returns is less than f(x).  Then, knowing the full definition of big O and big Omega, the professor showed us a number of new relationships that about big O and big Omega.  I learned that when attempting to prove these relationship, it is much easier to first picture the relationship in my head.  For example, if the statement is something such as ' if f is O(g) and g is O(h), then f is O(h)'.  Thinking about this scenario graphically, i realise that f is bounded above by g, which is bounded above by h, so f is also bounded above by h.  I think that the difficult part of these proofs is not finding the c value, but locating the correct B, because the value c's relationship to the functions is directly shown through the definitions of big O and big Omega, but B is only found when we start creating boundaries of n through our manipulations.  Therefor, it is sometimes hard for me to keep track of all of the boundaries that i have set for n through my proof.

SLOG 8 November 9th 2014

During this week's CSC165, i was primarily focused on studying for the second term test on proofs.  Prior to the test, i had just finished assignment 2, and felt pretty confident about proving universal and existential claims, as well as how to write the format of proofs in general.  I studied last year's test, and found it to be very easy, especially since there were only 3 questions.  After writing the test, i found question 1 and 3 to be very standard, however question 2 was not as easy.  For question two, i was asked to disprove a statement, so i took its negation and began attempting to prove it.  However, due to my being conditioned to relate variables e and d to limits, it took me a long time to understand the actual statement and its negation, and even then i made the mistake of defining one of my variables d as e times 2 instead of e plus 1.  This lead to many problems as i continued my proof, and only did i realize my error when time was up.  Alas, i had written the proof structure so hopefully i wont lose too many marks on that question.  Before this week, i was also quite confused about the 'steps' and big O notation that we had been covering in class, but after the tutorial exercise that focused on counting the steps of an algorithm, and finding its worst case scenario (which is when every loop is evaluated for the maximum number of times).  On Friday, the professor showed some more proofs of how some functions are of big O notation, and from these proofs, i learned that there is much more freedom in manipulating variables and inqualities when proving big O.  For example, when showing that 3n^2 + n is of On^2, the professor showed that we can simply turn n into 2n^2, because 2n^2 is always bigger than n, and then express 3n^2 + n with an less than inequality as 5n^2.

SLOG 7 November 4th 2014

The focus of this week's CSC165 was on assignment 2.  There were a total of 6 statements that were in assignment 2, which needed to be proved or disproved.  The first question involved using the floor, which was something that had been covered in class previously.  However, upon starting question one, i realized that the statements were actually quite difficult to prove fully.  For the first statement, i attempted to use part of the definition of the floor of x, which was that if a natural number z is less than or equal to x, then z is less than or equal to the floor of x.  I wanted to split the antecedent,  which was: if z ≤ x, into a disjunction of z less than x or z equal to x, and then use one part of the disjunction to prove the statement. However, my partner said that I can't just split the less than or equal to sign into a disjunction, so we ended up spending a lot of time thinking up an alternative solution. In the end, we came up with a solution which involved introducing new variables into the proof after talking to Professor Heap to make sure we can do it. The second and third statements were the most difficult of this assignment. The hardest part was to first figure out whether or not these statements are true. From calculus, i recognized 1.2 and 1.3 as definitions of limits, and so i wrote the statement in its limit format, which was: the limit as x approaches w of floor of x is equal to the floor of w. After figuring out the meaning of the statement, i drew the graph of the floor of x, and quickly realized that the statement was false. The disprove of this function involved finding the negation of the statement, which had 3 existential quantifiers. At first i wanted to pick a value for each of the existential quantifiers, but then i realized because there is also a universal quantifier before the last existential, i can only write the last existential(which is w) in terms of the universal (which was d).

The biggest lesson i learned from doing assignment 2 is that before i attempt to jump into the proof, i should first make sure i understand exactly what it is saying, and try to visualize the relationship. I realized as i were doing assignment 2 that often times i get stuck because i dont see the relationship between the numbers and variables, however after i visualize the statement graphically, i can figure out whether the statement is true of false much quicker