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!