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

SLOG 6 October 27th 2014

During last week's lectures, we finished covering methods and formats of proofs and moved onto discussing algorithms.  We reviewed some main strategies that we should employ when starting proofs.  For example, to prove universal, we show that there are no counter examples, to prove existential, we just have to find one example.  For implication, we start with the assumption and try to reach the conclusion.  For and statements, we must show that both propositions are true, and we can do this by tackling each proposition independently and then checking to see if both are true.  For or statements, we can also tackle each proposition individually, and as long as one is true, the claim will be true as well.  I learned that these links can also be used to introduce new claims or objects into the proof.  For example, if we know that an implication is true, then we can introduce the consequent when we reach the antecedent in the proof.  Then, we can use the consequent as the antecedent to introduce other implications to eventually reach what we want to show.

We started algorithms by talking about sorting algorithms, which are algorithms used to sort/organize data.  We talked about the the number of steps, or actions that each algorithm takes to complete its task.  When analyzing the speed of algorithms, I can look at their average speed, best case speed, and worst case speed.  For now, I learned that we should focus on looking at algorithms based on their worst speed, because the best speed is not 100% consistent and won't tell us much, and the average speed will take far more effort to calculate.

Lastly, on Friday I worked on a problem involving two drawers and 64 pennies.  To begin, all 64 pennies are in one drawer.  As long as the number of pennies in a drawer is even, I can take half of that number of pennies and move it to the other drawer.  The opening question is to find a way to have 48 pennies in a drawer.  I realized that because I am always splitting the number in half, then the number of pennies in each drawer will always be a combination of some exponent of 2.  For example, 64 is 2^6, which splits into 2^5 and 2^5, which can then split into 2^5+2^4 and 2^4.  2^5+2^4 is 48, so I solved the opening problem without much difficulty.  However the real question was whether or not I can get all numbers from 1 to 64.  When I started thinking about this problem, I realized that since there are two drawers, and the sum of pennies in both is always 64, then if I can get numbers 1 to 32 to show up in one of the drawer, then 32 to 63 will be in the other drawer.  My plan was to create a diagram showing all possible combinations of sums of exponents of 2, and showing that it can represent all 64 numbers, but I was very time and space consuming and I was unable to solve it yet.  I think professor Heap showed this question to us because it is similar to algorithms; though many do the same job, some do it much quicker and require much less space.

SLOG 5 October 20th

Last week I only had 2 lectures of CSC165 because of Thanksgiving, and the focus of the two lectures were on the structure of proofs.  Professor Heap repeated the the structure of proofs on a few different examples, such as proofs involving floors and limits.  I learned that the beginning of each proof always starts by defining the main variable as part of the set of real, integers, natural, and etc.  The second step is to assume the antecedent, which is pretty easy to identify when it comes to limit proofs because of the implication.  However when doing proofs about the floor of a variable, it is also crucial to put its definition in the proof.  Essentially, I learned that I should put all of the conditions that I know is true as an assumption before I begin the thinking part of the proof.  After finishing the assumptions, the next step is to somehow arrive at the consequent from the antecedent.  The difficulty of this step varies greatly.  For example, with a limit proof, it was quite easy for me to complete the thinking part as I have done limit proofs in math.  However with floor proofs, I often get stuck about how I should proceed.  However with more practice, I believe that I will be able to arrive at the fundamental insight that will allow me to complete the proof quicker in the future.  After arriving at the consequent, the last section of the proof is to finish the assertions made earlier.  The middle section of the proof will have proved that because of the assumptions made, the consequent that we arrived at is true, so the last section is basically re writing the first section.

SLOG 4 October 13th 2014

During the two lectures of this week's CSC165, I learned more about proofs, and also went through some examples of how to prove universal and existential claims.  From what I've learned during the first few weeks of class, proving a universal claim means to show that there are no counter examples, and proving an existential claim is showing one example.  Because of this, proving an existential claim seems easier because i just need to find a number or a set the matches both the antecedent and consequent of the claim.  Proving universal claim is much more difficult, as it involves defining the antecedent, and then trying to turn the antecedent into the consequent through mathematics.  Writing proofs is something that I have been learning in my MAT137 class for the past few weeks as well, and learning how to write proofs in CSC165 has actually helped me understand the proofs in MAT137 more clearly.  This is most likely because we used simpler examples, and Professor Heap went through the thought process of each step.

Although this week's class wasn't difficult, the midterm on Wednesday told me that I have much to learn in this class.  Prior to the midterm, I have felt very confident about 165, since I was able to almost all of the tutorial problems and have gotten full marks on every quiz.  I looked over some rules about symbolic expressions and studied last year's midterm as well as the assignment 1 answers.  However on the midterm, though i was able to breeze through question 1 and 2, i got stuck on question 3 for a very long time, and in the end handed in my test before i was able to come up with an answer.  When i first looked at question 3, and the complicated statement 3, i automatically assumed that i need to transform it into its contrapositive or a simplified version, and so i began doing that, thinking the answer will eventually become evident.  It did not, and only after the exam did i realise that i should have just focused on understanding the two original statements instead of trying to transform them into some other form.  This exam taught me to not assume anything about the questions on an exam, and hopefully i will be able to do better on the next one.