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.