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!