What youve been waiting for...

My mathematical proof! No really, thats what im going to give you. Right now. Heres the question!


Drum roll please.....


Suppose you have a grid made up of uniformly-spaced horizontal and vertical lines. On the grid you draw a square with corners that lie on some of your grid crossings: it may be a 1x1 square, a 2x2 square, or some other size. How many line (of various sizes) segments from the grid that begin and end on grid crossings are contained in the perimeter and interior your square? What is the answer, in general, for an mxm square?

Lets assume we have an actual grid that exists, say, a 6x6 grid. All squares are even. Now, we'll start by counting the number of segments for a 1x1 square on the given grid, because we're going to use that as our base case in our proof (we'll assume that n \in \doubleN, such that n > 0). In this square, we have 4 segments. In a 2x2 square, we have 18 segments. This is counted by counting every possible concatenated line combination. For a 3x3 square, you'll find 48, for 4x4, 100, and so on. When placed in a table, the pattern is not found, but is found while counting. The number of segments in a given line of length n segments is equivalent to the triangular number, (n(n+1) / 2). We know that there are (n+1) rows in a line of size n. Because its a square, we understand that this value must be multiplied by 2. So, our formula to deduce the number of segments on a grid of size n*n is equal to 

=  (n(n + 1) / 2)(n+1)(2)

=  n(n + 1)^2

Now to prove it...

Let n be an integer, such that n is greater than 0  #an arbitrary number

Assume P(n) is the following predicate: 

    P(n) = any square with dimensions n*n has n(n + 1)^2

    Basis: P(1)

        A square with dimensions 1x1 has 4 segments. According to the predicate, the number of segments                   

         = 1(1 + 1)^2 = 4, so P(0) holds.

    Induction P(i) --> P(i + 1)

        Let i be a natural number

            Assume P(i) is true

                Then any square with dimensions i*i has i(i + 1)^2 possible segments.
                Consider a square of size (i + 1). Its number of possible line combinations of varying lengths is
                equivalent to its triangular number. We can prove this by proving the triangular number itself.
                its overall number of possible segments can be calculated by multiplying the value by its given
                number of rows, i.e. 2(i + 1 + 1). Thus, the number of segments is
                = 2(i + 1 + 1) * (i + 1)(i + 1 + 1)/2
                = (i + 1)((i + 1) + 1)^2
                So if P(i), P(i + 1) holds as well //

So long, farewell...

To all my readers here, I apologize.

I am in fact, the worst when It comes to updating slog's. But, that's another story for another day. The course finally ended Thursday, but I've spent so much time studying that I forgot to keep up. I really enjoyed the course content, and felt as though what I was learning had some application to my future career, whatever my choice may be. The tutorials were alright, although the only problem I had was that the quizzes were at the end of the tutorial, as opposed to the beginning. Other than that, everything was just fine and dandy.

Hopefully, in the case that I have to create another Slog, I will do better to keep track of my updates.

Term Test 2 and Partial Correctness!!!

Oh, how I dreaded this thing. The countless past midterms that I wrote had me a little unsure of my capabilities, but it felt as though it wasn't so bad, at least, not as bad a I had expected. Preparing for tests like these are the worst, because it isnt as if there's a set of terms you solely have to memorize for recall, but its a matter of reconstruction, in such a short period of time. Studying for tests like these, and even the final, will most likely require intense amounts of practice, to the point that understanding the requirements of a given task will seem almost effortless. But those are my two cents concerning the test.

During the lecture, we covered partial correctness, which states that if an answer is returned, it will be correct. This does not infer that a loop will terminate, however. The main problem I feel as though I will encounter while writing proofs is that I will attempt to prove partial correctness as opposed to termination. Partial correctness only proves a value given termination, as opposed to satisfying the loop invariant itself. We'll see how that goes though. 

Well, almost forgot this existed

Hopefully this will merit my lack of posting.

Today, the Master theorem and its utilization in covering run-time complexity were covered. Its conditions and utilizations in divide-and-conquer recursive algorithms were covered. It helped me in my understanding of time complexity, which was not as strong as I thought it was when I had taken CSC 165.

When looking at the tutorial problems, I kept being unable to prove that the recurrence, T in question 1 was non decreasing with the same parameters as my TA. This was because of a few computational errors, which I fexed immediately.

I'm currently gaining a greater understanding of the course, relative to my understanding at the beginning of the course. I am beginning to apply what I am learning to real world situations, which should be expected (right??)

The Term Test

Today (or yesterday evening), the term test was written. I had no idea how much i had to study, but I did know that I needed to study in order to do well (that's expected, right?). It was surprisingly a lot simppler than I thought it would have been. If my preparation for this term test is any indication of how the rest of the term is going to be, I have a lot of preparing to do in order to remain at the top of my game.

I hate introductions

So I guess I'm a little late to this Slog party for CSC 236, but with good reason. Well, not really.

I like proofs. I really do. If only I could do them well. But I guess that's the point of this course.

I'll try to post weekly, but we'll see how that goes. Until then, happy proving! Or studying for whatever.