Nitemice

Because I’ve been spending all my time studying lately, the only thing I’ve had time to write is study notes. So I thought that I’d make the most of them, share a bit of my new knowledge with you, and give you a quick crammer’s guide to some of the topics from each of my subjects this semester. The information probably won’t mean a whole lot to you if you’ve never learnt anything about the topic before, but if you have, hopefully, this’ll clear up a few things for you.

This one’s about Maths for Computing. This subjects covers sets & number sets, functions & relations, matrices, special functions, logic, proofing methods, algorithms, counting methods and probability.

Pigeonhole Principle

Put simply: If (n+1) or more pigeons are put in n pigeon-holes, there must be at least 1 pigeon-hole with 2+ pigeons in it.

Euclidean algorithm

This complicated monster is quite straight forward once you understand it. Basically, the Euclidian Algorithm involves repeatedly dividing whatever you divided the last number by, by the remainder of the last division. You repeatedly do this until there’s no remainder, and whatever you divided by last (which was the remainder before the 0) is the greatest common divisor of the two numbers from which you started. The GCD just means that this is the largest number that can divide both the starting numbers to give a whole number answer.

That actually sounds pretty complicated still, so let me break it down for you. So you take the two numbers you want to find the GCD of and divide the larger one by the smaller one. What this actually involves is working out what the closest multiple of the second number is to the first number, and how many are left over. Then you divide the second number by this left-over number, so that you get a new left-over number. Then you use the new left-over number to divide the old left-over number, and on and on it goes until you get 0 as your leftover, at which point, the number you were dividing by is your GCD.

Hey, if you don’t like my explanation, have a look at this: http://youtu.be/AJn843kplDw

Proofs

So, we learnt about four proving methods, for showing that a statement or predicate is true. Each is done differently, and works best in a different situation.

Direct Proof – Used when what you’re proving is simple/straightforward, it simply involves assuming the hypothesis is true, and using this to prove the conclusion.

Contrapositive Proof – Is also a fairly straightforward proof, with a bit more interest & flair, it involves assuming the conclusion is false, and using this to prove the hypothesis false. That is, when the conclusion is false, the hypothesis will also be false.

Proof by Contradiction – A more tricky type of proof, involving assuming both the hypothesis is true AND the conclusion is false, and using this to find an impossible fact (a contradiction), which proves it wrong. E.g. you may find that 0=1, or that 1 is an even number, which are not true, thus proving the situation impossible.

Proof by Induction – The most complex and time-consuming type of proof, which is specifically reserved for proving mathematical facts across a set of integers. i.e. showing that [n/n = 1] is true for all positive integers. There are three parts to this proving method: Base step, Inductive step (with inductive hypothesis), and Conclusion.

Base step: This is where you prove that the rule holds at all, by doing a LHS vs. RHS, subbing in the borderline value i.e. the lowest value that is implied in the range given. In the example above, this value would be 1.

Inductive step: where all the work happens. Start off by rewriting out the formula you’re proving, subbing in k for n. This is called the inductive hypothesis, and we assume this is true, thanks to the base step. We then write it out again, subbing in k+1 for n this time. It should look nearly exactly like this:

Assume P(k): equation with k in it

To Prove P(k+1): equation with k+1 in it

Then choose a side of the second equation (with k+1 in it), and *mathematically* mess around with it until you can make it look like one of the sides of the first equation (the one with just k in it) so you can sub in the other side of it. Then, it’s a time for a bit more *mathematical* messing around to make the new equation look like the other side of the second equation.

Conclusion: This is where you just say in real words what you’ve proven. You’re basically writing the original question out again, saying that it’s true.

Here’s a super quick, simple example:

 n/1 = n, for all positive integers (and everything else, but that’s not important here)

Base Step:

  n=1

  LHS = 1/1 = 1  RHS = 1 = LHS

Inductive step:

  Assume P(k): k/1 = k –(Inductive Hypothesis)

  To Prove P(k+1): k+1/1 = k+1

 LHS =

 k+1/1 =

 k/1 + 1/1 =

 k/1 + 1 =

 (k) + 1 =

 RHS

Conclusion:

  n/1 = n is true for all positive integers.

Boolean Matrix tricks

Boolean matrix multiplication can be done really easily already, but with the knowledge of a few tricks, it’s almost instantaneous! So, as you should already know, you multiply matrices by  taking the row of the first matrix and lining it up along the column of the second, multiplying the corresponding numbers and adding the results together, then moving on to the next column. When you’re out of columns, you go to the next row and do it all again for a new row in the resulting matrix. For a better description of matrix multiplication, look here: http://www.mathwarehouse.com/algebra/matrix/multiply-matrix.php

Now, when you’ve only got 1s and 0s, that’s pretty easy, but you hardly even need to do that much. You just need to spot the patterns. Anywhere a 1 appears, the row it lines up with will be replicated. Anywhere a 0 appears, the row it lines up with will be lost. Here’s an example: say the first row of our first matrix is [100]. This means that the row in the result matrix will be an exact copy of the first row of the second matrix.  Have a look below.

The same thing will happen no matter the placement of the 1.

The only other situation not covered by this is, what happens if there’s more than one 1. Well, that’s pretty simple too! All you do is combine the rows with which the ones line up. So if your first matrix was [110], you would just combine the first and second rows to get your result row. And don’t forget, this is Boolean so 1 + 1 = 1, not 2!! See it in full below.

Until Next Time,

Nitemice

Related articles

• Greatest Common Divisor (algorithmcatalog.wordpress.com)
• 6 Math Problems That You Can Solve To Earn Thousands Of Dollars In Prize Money (businessinsider.com)