Final Post

Okay, so I may have lied when I said the last post would be my last.  I realize that I actually have said nothing about what we did the last week or so of class, which had to do with the halting problem.  I found it slightly confusing and difficult to wrap my head around, and I kind of put it off until I had more time to deal with it.

Saying that, another slogger in this course found a video that describes this problem, and I found it pretty helpful:
halting problem visualized

Now I'm actually going to give you a send-off, as I am in the midst of tweaking my assignment three with only 3 hours to go.

Adieu, and goodnight.

Problem: diagonals

Last post for this semester, I've finally gotten to the point where I write up my problem.  I have decided to tackle the diagonals problem given in class, where you are given a rectangle broken into n squares by m squares.  If you were to draw a diagonal line from one corner of the rectangle to the opposite corner, can you predict how many squares the line passes through.

To begin with, we understand that our inputs are n and m, two positive integers.  Our output should also be a positive integer s, the number of squares.  Knowing this, my plan was to search for patterns in the output using simple inputs.

As discussed in class, n = m + 1 is a good starting place, so

| rectangle dimensions | number of squares |
----------------------------------------------------
|             1 x 2               |             2                |
|             2 x 3               |             4                |
|             3 x 4               |             6                |
|             4 x 5               |             8                |

This is enough data to conclude that if the input is of the form n = m + 1, the output is s = n + m - 1

Another set of interesting data is when n and m are both even

| rectangle dimensions | number of squares |
----------------------------------------------------
|             2 x 2               |             2                |
|             2 x 4               |             4                |
|             2 x 6               |             6                |
|             4 x 4               |             4                |
|             4 x 6               |             8                |

Using this data, it seems slightly scattered.  However, after some further consideration, another pattern emerges.  If you divide both n and m by two until one or both are an odd number, the output of the smaller inputs can be multiplied by 2 to the exponent of the number of times the original inputs were halved:

| rectangle dimensions | number of squares |
----------------------------------------------------
|             4 x 4               |             4                |
|             2 x 2               |             2                |   <-- 2 * 2 ^ 1 = 4
|             1 x 1               |             1                |   <-- 2 * 2 ^ 2 = 4

This is unfortunately as far as my solution has gotten so far, but after my exams are over I will spend more time working on the derivation of a formula from this information.

Since this is my last post, good luck to everyone writing finals, and I hope you enjoyed this course, I found it quite interesting myself.

Noncomputable Functions

This week, we focused mainly on noncomputable functions and the fact that problems exist for which you cannot write an algorithm to solve.  For instance, you can't check whether a given function will be caught in an infinite loop with a specific input using another function - how would it tell the difference between infinite and really really long?  There would have to be some kind of time constraint on the checking function, and so it wouldn't return the correct answer all of the time.

Noncomputable functions are functions for which we can say what f(x) is for every x, but we can't explain how to compute that.  They are impossible to code, and we can't extend other functions to cover them.  However, if we know that a function is noncomputable we can use it to prove that another function is as well - if we could theoretically extend another function to build the original, the other function is also unwriteable:

g computable -> f computable through extension

gives as a contrapositive

f non-computable -> g non-computable

which is a contradiction, so must be false

Function Proofs

This week we spent on proving that a function was in big O of something; it's output is always less than or equal to something.  I actually find it quite interesting, and the idea of being able to grossly exaggerate the numbers is very intriguing.

Term test two happened this week, I feel it went fairly well.  Proof structure is something I feel I have down pat, so I'm not too worried about that.  There are only a few more weeks until the end of the semester; hopefully I am able to make the most of them with this class.  So far it's been one of the easiest on my schedule, so I hope that doesn't suddenly change.

Good luck to everyone else for the rest of the semester (I feel like I write that every week), and I hope the midterm didn't stress you all out too much.

Even more proofs, and Term Test Two

Sorry about taking so long to post this (last) week's post, everything got a little busy and I may have gotten a little lazy.

Last week, we continued working with proofs, moving on to big Oh and big omega.  Big Oh is the upper bound; the worst case is better than big Oh, while big omega is the lower bound, the worst case is at least as bad as big omega.  We're continuing in on that this week.  I haven't really found much else new lately, just a lot of proof structure that I feel I've got down, and examples of proofs.

Studying how many steps a program takes to run, which we've been exploring using sorting algorithms, is really helpful when writing your own code.  You want to take as few steps as possible so you don't slow down your program, but it still has to do everything you want.  Nested while statements really pile on the steps, changing running times from linear (n) to exponential (n^2) or even quadratic (n^3).  I remember working on this in CSC108 last year, and we mentioned it a couple times in 148.  Figuring out how to calculate how many steps are being taken, with the right constants, may take me a bit longer than I've spent on it so far, but I'm pretty confident I can figure it out.

Hope everyone did well on the second midterm!

And More Proofs

This week assignment 2 was posted, so I have started (and almost finished it) with my partner.  This is the first time in the two years of University I've been through that I'm working with someone else on a project, and it seems to be going very well.  There is a small part of one proof we are stuck on, so hopefully a bit of sleeping on it and staring at the paper will get us over it (or convince us it just doesn't matter).  I guess we'll see how it goes.

We're putting our proof structure into practice now, which is somewhat more difficult than writing general proofs.  On the bright side, this week's material is sort of blurring into last week's for me, so there's not a whole ton of new stuff to study while I'm focusing on my other classes, which tend to take a bit more time to deal with.  I have found that a lot of the conversations I have now end up with me going 'hey! That's what we're doing in 165' which is cool, I suppose.  I have started to feel a bit like this is just being put out into space randomly? Hopefully I'm posting what I'm supposed to, and I guess I'll work on the question we're supposed to solve at some point soon.

Anyway, hope everyone else's blogs are going okay, have a good week and good luck with assignment 2.

Proving and Disproving Statements

Week 6, so we're halfway through the semester, yay!  This week was about proofs, which may or may not suck, we'll just have to wait and see.  The structure seems fairly straightforward, assume and conclude and assume and conclude, that part's actually fun.  The thinking part, however, may prove to be a little challenging.

Starting off with a straightforward proof. you pretty much set up your domains (assume \forall variables and find an example \exists variable) and then do all of your proving-stuff until you can claim that the rest of the statement is true.  Then you have to go back and close all of your assumptions with conclusions, which in class Danny did at the same time as he made the assumption.  Said like this, it sounds super easy but I know i'm going to find it crazy hard to muddle through all of the proving stuff.

To disprove a statement, you just prove the negation of it, since the negation is only true when the statement is false.  Once you have the negation, you just go through all of the same steps.  It is also possible to go through the proof and disprove it by finding a contradiction, but that seems much more difficult, so I'll stick with proving the negation for as long as I possibly can.

The tests came back this week, and for the most part mine went over fairly well, so hopefully the rest of the class keeps on like that.  I hope everyone else is happy with their results, good luck with the rest of the term!

Introductions and Proofs

Just as a little pre-amble, sorry about the changes in notation, I keep trying to find a way to insert the actual symbols but I have yet to figure it out.  I'll try to stick to just the backslashes from now on.

This week was the week of the first midterm.  I actually had a big midterm in biochemistry the day before this one, so my studying may have slipped off the top-priority spot.  Ignoring that fact, I feel like it went really well, I was well prepared despite my lack of thorough preparation, if that makes any sense.  In any case, we continued with proof structure this week, which I find really fun, but I like things that have easy-to-follow steps and procedures.

The biggest thing so far this week has definitely come from tutorial (yet again), notation in proofs and symbol introduction:

Creating a general proof without actually proving anything is an integral part of solving a proof; it helps you to organize your thoughts and find out what you actually have to prove.  Here's an example:

to prove : \forall x \in D, \exists y \in D', P(x, y)

assume x in D     #domain assumption

    find y'

        [proof of y' \in D']

        then y' \in D'

        [proof of P(x, y')]

        then P(x, y')

    then \exists y \in D', P(x, y)    # \exists -intro.

then \forall x \in D, \exists y \in D', P(x, y)     # \forall -intro.

Now this only uses the quantifier introductions; there are also \and -intros, \or -intros, and =>-intros.  They can be used under specific conditions:

\and - intro:

    If you are proving P(x) \and Q(x), ignoring the quantifier, you can introduce an \and symbol if you prove P(x) and Q(x) separately.

\or - intro:

    If you are proving P(x) \or Q(x), again ignoring the quantifier, if you assume P(x) and then prove Q(x), you can introduce the \or symbol, because it is inclusive - of Q(x) is true it doesn't matter if P(x) is or not.

=> -intro:

    If you are proving P(x) => Q(x), ditto with the quantifier, this proof actually follows the same formula as for an \or -intro.  The only way for an implication to be false is for the antecedent to be true and the consequent to be false, so we assume P(x) and prove Q(x), and we can then introduce the => symbol.

Proofs

This week, I received a rough introduction to generating proofs of logic statements.  The most important part of this, at least to me, was in reasoning my steps, and which actual steps to take.  The most important equivalences are:

implication

x => y  =  \not x \or y

distributive property

x \and (y \or z)  =  (x \and y) \or (x \and z)

deMorgan's law

\not(x \and y)  =  \not x \or \not y

When writing proofs it is important to explain the reasoning behind your steps, so that your audience can easily read through your work and understand the thought process behind it.

Negation

Week three came with another new set of information: negation.  Using the &not symbol, we can negate a statement, making the negation which is true when the statement is false.  To begin a negation, we start at the beginning of a statement, as is intuitive.  A statement beginning &notall x in X becomes &exist x in X, and vice versa.

The trickier part of negation comes after: the not symbol moves through the statement to the claims made about the variables initialized but the first part of the statement.  Negating a claim is different depending on what the claim is.  If it is an implication, the negation of that would be antecedent and not consequent. This makes sense if you think about what makes an implication false: the antecedent being true and the consequent being false.  Taking this:

P(x) => Q(x)

when negated becomes

P(x) &and &not Q(x)

When dealing with a conjunction (an and claim); the negation becomes an implication with a false consequent:

P(x) &and Q(x)

becomes

P(x) => &not Q(x)

Seeing this, it almost becomes that implication and conjunction are opposites, so long as you remember which elements must be false.  The final case would then be negating a disjunction (an or statement).  For this case, the disjunction becomes a conjunction between two false elements:

P(x) &or Q(x)

becomes

&not P(x) &and &not Q(x)

This gets more complicated when you get to implications with multiple variable interactions on either side.  I was not completely clear on how to deal with this until Week 4's Monday class, but I feel like I have a firm grasp on how to deal with these negations now.  When moving a negation through a convoluted statement, you have to move from the bigger claims down to the smaller ones the large ones are made up of.  For instance:

(P(x) &and Q(x)) => (R(x) &and S(x))

The first thing to negate is the central implication.  Doing this, we take the antecedent as true and negate the consequent:

(P(x) &and Q(x)) &and &not(R(x) &and S(x))

and then follow the negation through the consequent:

P(x) &and Q(x) &and (R(x) => &not S(x))

and voila! A negated statement with multiple claims.

Quantifiers and Implications

One of the most important things I learned this week was about the differences between universal quantifiers and existential quantifiers.  If a statement has a universal quantifier (all), in order for it to be true it must have no falsifying example; there must be no instance where the statement is false.  Therefore, to prove the statement false, you need only one example where it is not true.  If instead you have a statement with an existential quantifier (some), to prove the statement True there must be one example where the statement holds.  To prove this statement False, there must be no instance where it is True.  When dealing with an empty string, it will prove a statement with a universal quantifier True, and one with an existential quantifier False.

Implications are interesting, and sometimes confusing to construct from English sentences.  An implication is made up of an antecedent and a consequent, in the direction of:

if antecedent then consequent

      In English, however, it is sometimes said: 

 consequent if antecedent 

     or it has confusing modifying words stuck in, such as unless, which is handled as an if not statement.  I personally find this a bit confusing as you add other modifiers, and so there may be a bit of extra practice done on this subject.

Personally, I am a little excited about this new outlook on implications; I can see future arguments with my siblings becoming more interesting when I can say that their point doesn't falsify mine, when in that context it probably should.  

Empty Sets and Misunderstandings

The first week of class culminated in working on the exercises for the first tutorial. I found the instructions fairly straight-forward, but I imagine I would have had a bit of difficulty if not for the lecture material. For example, I received a bit of clarity about the behaviour of empty sets; the value of a function returning whether all values in an empty set are in another non-empty set will not be false. Similarly, a function returning whether no values of the empty set are in the non-empty set will also not be false.

Something that I was slightly confused about through the week was what the syntax of the set-building functions meant for how the function worked. Using an example function from class:

def q0(S1, S2): ''' (set, set) -> bool Return whether ... ''' return not all({x in S2 for x in S1})

I was misreading the actual code; thinking that the x value was first referring to the values in S2 and then comparing them to the values in S1. My mistake was pointed out over piazza, and I realized that it is actually the other way round. It was a small misunderstanding, but the realization is infinitely helpful in figuring out what the function actually does.