Week 7: More proofs, algorithms.

    To start off, we learned about some more proof strategies. In particular, we learned how to proove by looking at different cases that a proof could present to see whether all cases work, if the proof is supposed to be universal, or none or only some work. Conceptually this was fairly straight forward, but it is something that will need more practice because sometimes the cases that need to be looked at aren't too obvious (or there are just too many cases, but we probably wont be dealing with problems too big).

   Proof patterns were another thing we went over. Again, this was mostly straight forward, but it's definitely something important to go over and write down to keep it in mind when looking at how to go through a proof because they can save a lot of struggle. In lecture I was actually confused by it at first, though I'm not sure if it just didn't get to me conceptually or the format of how it was presented was confusing, but when we got to elimination examples it made more sense. I'm still going over the introduction examples to understand them better.

   The final part was about algorithms, or more precisely, algorithms in relation to how they grow over time. Some of the concepts that were explained here were things I've been taught about in different classes, but in different contexts from programming algorithms (for example, population growth). From our understanding, algorithms are designed to deal with growth and large inputs, and we generally should care about how they work and grow when given large inputs. Hence, while with very small inputs, a constant could be very important, in a growing algorithm constants become practically negligible. Also, they become increasingly negligible as an input grows and the algorithm consists of a fairly high order term. That is, with something like 1209x^2, as x grows, 1209 becomes less and less important, so we don't compare two algorithms in terms of their constants. So 5x^2 has the same order as 12091x^2 as it grows. We also looked at the linear search program in python and how input influences running time. Iterating through a list grows in linear time if you're searching from the first index at 0 and moving to the next item to search each time. Based on how you build the algorithm, different inputs could be the best or worst cases. This connected a lot to some of the things we learned about in CSC148 in terms of lists and other data structures and efficiency of traversing them, and how implementation can greatly change efficiency. 

Week 6: Proof Structures and actual Proofs

   The previous week we learned about structuring proofs, and this week we learned strategies to doing actual proofs. Proof structures aren't too complicated to learn, but it was good practice to do several of them because it was very easy for me at first to just skip some necessary steps in writing a proper proof. We also learned that you can use the contrapositive to prove the statement itself, which seems like a good strategy in situations where the statement feels more ambiguous or difficult to prove. That is, if the statement is P -> Q, then the contrapositive is not(Q) -> not(P).

If you have a universal statement such as the one used in class:
"There are 5 boxes that have a total of 51 balls. Prove that there is a box with at least 11 balls in it"
So the contrapositive to this would be something like :
"There does not exist a box with at least 11 balls, therefore the 5 boxes do not have a total of 51 balls."
or in other words:
"For 5 boxes, if all boxes have less than 11 balls, the sum of all balls cannot be 51."

From my understanding, the reason for proving the contrapositive would be that to prove the statement you would actually have to directly show that a box has at least 11 balls in it, so you would need to know the set of all balls in each box (I think?).
So, given not(Q), or that each box can have at most 10 balls, that means the highest possible sum for 5 boxes with at most 10 balls each is 50. Therefore, in order to have 51 balls, one box has to have at least 11 balls in it.


    Now, moving on to actual proofs, some of this was simple and some a lot more tricky. The concept of proving a statement using the definition function made a lot of sense. It seems like if a statement is being made using a single function, knowing the definition of the function alone can be all you need to prove or disprove that statement (as I said, if the statement is just about that single function, but I wont believe this for certain until I know it to be true for sure). At least, when a function definition is all you have, the strategy of manipulating that function into different forms is the best way to prove/disprove.
    Disproving was also somewhat straightforward conceptually. You're simply proving the negation. I think doing so is much easier when disproving a universal statement, because it's much simpler to say that something exists than that everything exists. That being said, I think the above strategy of proving the contrapositive when faced with a difficult statement to prove can also be used when proving a negation. That is, to prove the contrapositive of a negation.

So, lets say my statement is:
There exists a penguin that is a mammal.             P -> Q      

the negation of this would be :                         P -> not(Q)
All penguins are not mammals.


the contrapositive of the negation would be :  Q -> not(P)
If it is a mammal, then it isn't a penguin.


Probably not the best example, but I think the concept of using the contrapositive still applies.


So, the rest of the class had a lot of math and stuff about limits. It has been a while since I've done calculus, but it shouldn't be too tricky to remember some things to understand this stuff better. For now though, it was a little bit daunting.

Week 5: Looking Back at the Assignment and Midterm.

   Now that some time has past since submitting the assignment, and I've reviewed the sample solutions among other things for the midterms, I can understand many of the areas I've had a lot of trouble with before. I had some difficulty understanding the concept of implications in logic, which I'm sure reflected on how I answered the fifth part of the assignment. It made sense to me when it was written with symbols in a simple form like P ==> Q, that this means that P is a subset of Q. However, when written in English or a mix of English and math, I got lost in understanding implication in a more vague English sense. Had I thought of all those questions in the assignment as "one must be a subset of the other", then I would have had a much easier time going through them. Hopefully I've learned from those mistakes and wont repeat them.

    As for the midterm, it was actually pretty good. I'm a third year student, so I'm no stranger to how a lot of term tests are here at UofT, especially for first year courses. This wasn't anything like I remembered first year course tests to be, which is perhaps just because the life science courses I was in were more interested in weeding out students, or I've just matured more since then and know how to study better. That being said, I don't think it was just easy marks, I thought it was fair and you had to actually think about the problems.
The first two sections of my test were a lot like the practice test and stuff we learned in class (the q0-q3 python functions). There were a few areas where I was actually really close to making a mistake in reading the problem (the set of P3 on my test almost got me, unless I'm wrong and it actually did). Where I know I messed up was the last question (which I do think was a lot trickier than what a lot of other test papers had for that question).

So the question was something like this:

∃d∈D| P(d) ⇔ Q(d) 
∃d∈D| P(d) ∧ Q(d)

Write sets for D,P, and Q that make one of these true and the other false.

    So, when I saw this question at first I had no idea how to do it and thought they were identical (I mean, they do intuitively seem to be identical). For whatever reason, I had forgotten how vacuous truth worked. My understanding now is that the first statement could be true and the second false by making both P and Q false (or a set that can't have anything in it). The logic behind that would be that False = False is true, but False and False is False (makes sense). 
So, I guess a set for D,P, and Q could be something like:

D  is the set of all integers
P is the set of all integers x that are greater than x + 1 
Q is the set of all integers y that are greater than y + 5 

So, you can't really put anything into P or Q, which makes the two sides false, but the bi-implication of it true. P and Q on the other-hand are just plain false. 

Week 4: The Assignment

    So now that the assignments are all over and submitted, I thought I'd dedicate this week's course logs to stuff about the assignment, to things that were challenging, confusing, or just plain easy.

To start off with question one, it didn't feel too challenging. The way I solved the problem was to first write out each of the statements with mathematical symbols, and then negate the statements. After that, I translated the negation into English. While it would have been easier to just figure out the negation in english first and then turn that into a symbolic representation, I felt that it would be good practice of using symbols to do it the other way around, and it would also help avoid misinterpreting some of the vague aspects of English.

So, for example, problem d:

There are diagonal acronyms that are bifurcated.
\thereexists a \element of A| D(a) ^ B(a)

So, to negate that, I said that
d. All diagonal acronyms are not bifurcated.
∀a\elementof A| D(a) ^ ¬B(a)

     Moving on to question 2, I'd have to say I enjoyed this part most of all, even though part d was challenging and a bit tricky. So, I had to decide whether the statements were equivalent to the converse, contrapositive, and negation. The first 3 seemed straightforward, but the last one was actually an inversion. My initial reaction was to think that the question was written incorrectly, but I realized that it asked for "equivalence", which I believe refers to the truth value in relation to the original statement. An inversion is just a converse of the contrapositive, and since the contrapositive depends on the truth value of the original statement, it's converse, should function in the same way as the converse of the original statement. So, I determined that the inverse is equivalent to the converse.

  I don't really have anything to say about question 3, and the only thing about question 4 that bugged me was drawing venn diagrams in a word/text processor. As for 5 though, this part was tricky. There's still plenty of things that I have to go over, but my general logic was that for one to imply the other, it has to be its subset, so I just went with answering it from there. The only thing I couldn't figure out at all was the final one, the empty set. I hope that this gets answered for me eventually though!