SLOG 11 December 2nd 2014

During the last CSC165 class, I worked on a problem called diagonal with a friend of mine.  The problem involves rectangles that are made of squares with 1 unit area.  The problem is that if a diagonal line cuts a rectangle from corner to corner, how many unit squares within this rectangle will remain intact and how many will be cut?

The first step was to understand all the known and unknown of this problem.  Because the rectangle is made of squares of unit length 1, that means if we know the length and width of the rectangle, we are able to calculate how many squares are in this rectangle.  The problem involves finding two numbers; the number of squares in the rectangle that isn't cut, and the number of squares in the rectangle that is cut.

The second step was to devise a plan.  Initially, the handout had a picture of a 4 by 6 rectangle, and i realized that the line intersects the mid point of the rectangle.  What this helped me realize was that the rectangle can be split into two identical 4 by 3 rectangles, which means if we can find out how many squares are cut in this rectangle, i can just double that number to find the number of squares cut in the 4 by 6 rectangle.  However, after thinking about this plan, i realized that if the rectangle had odd side lengths, then the rectangle cannot be cut into more rectangles evenly.  After this stumbling block, i got stuck on the problem for quite some time, thinking about the possible ways of splitting each rectangle into smaller components.  Then, i suddenly realized that the diagonal line itself splits the rectangle into two identical triangles!  My plan was then focused on trying to use what i know about the triangles to calculate how many uncut squares exist inside.

With the triangle, i know that i can calculate its area, but that wont help me very much because the area represents the entire surface of the triangle, not the area of each square plus the left overs.  After much brainstorming, my friend and i realized that the triangle reminded us a lot about integration.  We drew many triangles of varying base and heights, and then divided the triangle into unit squares to see which squares are cut and which are not.  For example, imagine a triangle of base 4 and height 2.

This triangle can be viewed as 4 columns with a slanted top.  If we can find the height of the shortest side of each column, then we can find out how many uncut squares are in that column.  Then, we just need to add up all of the uncut squares of each column to find the total number of uncut squares in this triangle, and multiplying that number by 2 will give me the number of uncut triangles in a rectangle with width and length equal to the base and height of the triangle.

How can we find the height of each column?  Well since we can calculate the slope of the triangle by (height/base), we can use the slope to find the height!  Referring back to the 4 by 2 triangle, the slope will be 2/4, which is equal to 1/2.  So starting from the right most column of the triangle, this column is actually a triangle itself.  That means its height on the right is (0 X 1/2) = 0, and its height on the left is (1 x 1/2) = 1/2.  So we know the height of the two sides of this column, but neither of them are above one, so we can conclude that there are no squares in this column.  Now lets move onto the second column from the right.  The short side of its height is (1 x 1/2) = 1/2, and the long side of its height is (2 x 1/2) = 1.  We know that one of its side is 1, but the other side is less than 1, so its impossible for a square to be in this column either.  On the third column, the two heights are 1 and 3/2.  Now, both sides have a height greater than 1, so that means there is a square in this column!  On the last column, the two heights are 3/2 and 2, and since the shorter side is greater than 1, that means there exists another square in this column.  That means the 4 by 2 triangle has 2 uncut squares, which means a 4 by 2 rectangle will have 4 uncut squares, and that (8-4) = 4 squares are cut by the diagonal line.

To summarize this solution, we have come up with a formula that has been tested with numerous triangles and have worked in all cases tested so far.

What we discovered was that if knowing the longer height of a column will give us the number of squares in the next column, because in the next column, this height will be the shorter of its two heights, and if this height can be rounded down to a whole number, then that number represents the number of squares in the next column.  In the formula above, l represents the length of a rectangle, which is the same as the base of the triangle cut from this rectangle.  W represents the width of the rectangle, which is also the height of the triangle.  (w/l) is the slope of this triangle, and i represents the the distance from the tip of the triangle to the next column height.  The floor rounds the height down to a whole number, and the summation adds up all of the number of squares.  The reason why i only goes up to the second last column height is because we only need the previous height to know the number of squares in the next column.

The blog of the student i worked with can be found here:
http://kenguoslog165.blogspot.ca/

His latest blog should be an account of how we solved this problem in his point of view.  Its worth checking out, as thought we arrived at the same conclusion, we had different approaches and methods that helped us get there.

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.

SLOG 3 October 4th 2014

In this week of CSC165, I learned about transitivity, the importance of the order of quantifiers in a statement, and the guideline to proofs.  However, the majority of the focus during this week of CSC165 was on the assignment that was due at the end of the week.  For this assignment, I worked with 2 other students in a group of three to produce the best answers that we could come up with.  Our method of ensuring that we all share the work load equally was by completing the assignment individually, and then comparing and merging our ideas and answers to produce a final version.  I felt that of the 5 questions in the assignment, the difficulty level of the questions increased from question one to questions five.  The first question was fairly basic translation of sentences to its symbolic form, and then negating the symbolic statements.  This section was mostly applying the correct negation methods and understanding the sentences properly, which did not cause me a lot of trouble. 

For question 2, I realised that I could substitute some of the predicates such as honor and persistent into one, which simplifies the statement and made comparing it to the original much easier.  It was the method we agreed to use to explain whether the statement is the converse, contrapositive, or the negation. 

The third question became a bit trickier, as it involved creating sentences myself to match the description of the questions.  My plan was to simply translate the sentences to its symbolic counter parts and vice versa, but soon I encountered statements that required complicated construction of quantifiers, predicates, and relationships.  The most difficult question in part 3 was to express that Zorn was enrolled in all courses but Zukes.  I spent a lot of time thinking about how to create the expression ‘there exists only one’ symbolically, and my initial answer was to say that for all x of classes that Zorn is enrolled in, there exists a set y of class that Zorn is not enrolled in, if x is in the set of classes that Zorn is enrolled in, then x does not equal y, and y is equal to Zukes.  At first I thought this answer was sufficient, however later I discovered that I merely said that Zorn in not enrolled in Zukes, meaning I had failed to express that Zorn is enrolled in all other classes.  After discussing with my partners, they showed me that if I said for all x, if x is a class and x is not equal to Zukes, then Zorn is enrolled in x.  This statement expressed that Zorn is enrolled in all x that is not the course Zukes. 

Question 4 was short, but although I knew that there are differences between conjunctions and implications, I had difficulty coming up with exact examples to prove one wrong and the other right.  However after thinking back to the rules about proving and falsifying universal and existential quantifiers, I remembered that to prove a universal wrong, all I needed was to show a counterexample, and to prove an existential wrong, I needed to show that there are no examples.  The final answers and the explanations are too long for me to put into this blog, but the main idea is that for implications to be wrong, P must be true and Q must be false.  However for conjunctions to be wrong, either one being false will do the trick. 

For question 5, my way of finding which implies which was to create truth tables.  I viewed each statement as a predicate, and then created a truth table to see if the second statement is true or not depending on the antecedent statement.  This question took me the longest to solve however because I did not know exactly how I should be finding out which statement implies which.

All in all, I know that I have answered the questions and shared my reasoning with my partners as best as I can, and I am confident with the results of this assignment.  

SLOG 2 September 27th 2014

               In this week of CSC165, I learned about conjunction, disjunction and negation.  The conjunction and disjunction were very similar to the ‘and (n)’ and ‘or (u)’ used in sets and Venn diagrams, and so it was fairly easy for me to understand what they mean.  Disjunction and conjunction are also identical to the “and” and “or” commands in Python, which I had learned in CSC108 already, so I was able to understand how they are used to evaluate statements and implications.  Basically, conjunction is used when the conditions on either side of the sign must all be true in order for the statement to be true.  For disjunction, only one of the condition being true will satisfy the requirement for the statement as a whole to be true.  However, the use of brackets can modify which requirement comes first, whether conjunction and disjunction, and during the tutorial this week I went over some example statements that gave me a better grasp of how conjunction and disjunction is used.  To not be confused by the order of the requirements, I like to underline parts of statements that need to be considered first.  For example, if the statement was (P n Q) u R, I would draw a line under (P n Q), and another under R, so I know which two objects I’m looking at and whether disjunction or conjunction is the main requirement of the statement. 

I also studied negation during in this week, and over negation wasn’t a difficult concept to grasp.  It is basically the opposite of what is being said.  That means if a statement is true, then its negation is false.  However, one problem I tend to have when dealing with negation is that I often confuse them with contrapositives.  What I mean by this is that when I try to find the negation of a statement, I end up finding the contrapositive instead.  To prevent this problem from reoccurring repeatedly in the future, I realised that the negation is the opposite of the statement, so if I put another negation sign in front of the negated statement, then I would get the contrapositive. 

Lastly, during the class on Friday I had the opportunity to work with my friend on a problem which involves finding and expressing the patterns of up and down creases of a paper strip folded n number of times.  I devised a plan to first observe the first 4 folds and discover the basic relationships between the number of folds n, the number of layers after being folded n times, and the number of creases c.  We found that the number of creases can be calculated using the formula 2^n – 1, which helps us understand how many creases there are.  However the problem of how the pattern of ups and downs go still remain unsolved.  We drew a diagram depicting the ups with arrows pointing up, and downs with arrow pointing down, and discovered that there exists a central crease which remains the same at all time.  Every time the paper is folded, new creases are generated on either side of existing creases, and the new creases have an alternating orientation of ups and downs.  The biggest issue we encountered was to express this pattern mathematically.  This was the most frustrating because although we know the pattern, we could not express it in a way that the pattern of creases for any number of folds can be calculated.  After doing some research about the problem at home, I learned that a type of function called recursive function can be used to predict the pattern.  This is because recursive functions are basically looping functions that uses the output as the input, thus if we can enter the basic pattern of how the creases are added, then the final crease pattern can be predicted with the function.  

SLOG1 September 17th 2014

In this week of class, I learned how to understand ideas that are expressed in various mathematical and linguistic forms.  During the first week of class, I was introduced to the basic if and then expressed as events P(x) and Q(x).  It was easy to memorize all 4 different combinations of truths and false of P and Q, but I had a hard time understanding why the if and then statements are true even when P is false.  Besides the if and then statements, I also had a difficult time visualising the all and any statements, and I had a lot of trouble when I had to work on some problems in class.  In the following classes during the first week, I was taught about the universal and existential quantifiers.  Unlike the if and then statements, I have never seen the two types of quantifiers before, and so I didn’t really understand what was going on in class, especially when the professor gave examples of statements that are expressed with the quantifiers, and what they meant in each scenarios.  All I could do during lectures was memorize and copy down as much material as possible, and try to think about them after class.  However, during my MAT137 class, I was taught about universal and existential quantifiers with much more detail, and I realised that the quantifiers are essentially just another way of expressing if and then statements without using P(x) and Q(x).  I also learned about vacuous truths in math, which helped me understand why if and then statements are true even if P is false. 

One of the most important thing I learned in class which really helped me understand the different ways of expressing implications was the rules to verifying and falsifying universal and existential claims.  I learned that:

-        To verify a universal claim, show that there are no counterexamples

-        To falsify a universal claim, show at least one counterexample

-        To verify an existential claim, show at least one example

-        To falsify an existential claim, show that there are no counterexamples

With these rules in mind, I began to translate if and then statements into their universal and existential forms, and by using the rules, I was able to figure out what needs to be true and what needs to be false in order for the statement to be true or false.  The tutorial exercise which involved expressing if and then statements with venn diagrams gave me a stronger visualisation of what is being described by if and then statements, and which areas must be empty and which areas must be occupied for various statements to be true.  I also found out after examining the 4 rules above that verifying a universal claim is the same as falsifying an existential claim, and falsifying a universal claim is the same as verifying an existential claim.  It is then that I saw the connection between universal and existential claims.  By the end of this week, I believe I have a good understanding of what has been covered in lectures and tutorials, and I am confident that my level of understanding increase as the weeks pass.