Week 11: Final Week & Problem-Solving Question

It's hard to believe my first exam is scheduled on December 8, which gives me roughly two weeks to prepare. This post wraps up the last full week of lectures and tutorials. Next week is strictly a Q & A session, but I'll still attend those class regardless because I need some clarification regarding some minor topics. As for this final week of new material, Professor Heap discussed the behaviour of python functions and briefly introduced simple induction. It was fairly easy to comprehend; a python function can only be created if the following two criteria are followed:
1. The behaviour of the function for every input
2. Write a procedure that computes the behaviour of the function
I've used this procedure constantly in CSC108. One of the assignments in that course asked to create a set of "test cases", which are used to test the "robustness" of a python function. This essentially follows both criteria at once because the actual test cases represent the input, while the code used to produce the correct result of each input is the writing procedure of that specific test case. Overall, the lecture was easy to digest.

To conclude my blogging of this course, here is the procedure I used to solve a complicated math-based problem. The structure of my solution is based off Polya. To begin here is the actual problem itself:

You have a rectangular grid made up of m rows and n columns (the symbols n and m represent positive whole numbers). Draw a line from the upper left to the lower right corner (the diagonal). How many of the grid squares will the line pass through the interior of? If you are told m and n, can you calculate how many squares the diagonal will meet the interior of? Can you derive a formula?

Here's what happens for 4 rows and 6 columns:

So, according to this example, the diagonal line passed through 8 squares.

Understanding the Problem

-This problem involves a group of squares organized into a rectangle

-The line begins at the top-left corner of the rectangle and ends at the bottom-right corner of the rectangle

-What's Given: The number of rows (represented by "m") and columns (represented by "n")

-What's unknown: The number of squares in contact with the diagonal line

-Condition: The line must be in contact with the interior of the squares

-The condition is clear; it displays a clear distinction between a square that is in contact with the line and a square that is not in contact with the line
-Rotating the rectangle 90 degrees in either direction will produce the same combination, but the number of rows will be the number of columns and vice-versa

Devising a Plan

-Try out "perfect rectangles", where the number of rows is equal to the number of columns (m = n)
-Observe the difference between m and n
-Check out odd and even differences 
-In addition to the difference between m and n, calculate the difference between that and the number of squares in contact with the line

Carrying Out the Plan

-I conducted 10 different tests, producing the following results:
> m = n = 2 produces 2 squares
> m = n = 3 produces 3 squares
> m = n = 4 produces 4 squares
> m = 1, n = 2 produces 2 squares
> m = 1, n = 3 produces 3 squares
> m = 1, n = 4 produces 4 squares
> m = 2, n = 3 produces 4 squares
> m = 2, n = 4 produces 4 squares
> m = 3, n = 5 produces 7 squares
> m = 12, n = 20 produces 28 squares
-I noticed that if the absolute difference between m and n is even, it produces one of these results:
>If m and n are even or m and n are odd, the number of squares = n + abs(m-n)
>If n is even, the number of squares = n
-If the absolute difference between m and n is odd, it produces one of these results:
>If n is odd, the number of squares = n
>If n and m are odd, the number of squares = n + abs(m-n)
>If n is odd, the number of squares = n + abs(m-n)
-If the difference between m and n is zero, the number of squares is equal to m or n
-As a result, I produced a python function that produces one of the above results:

Looking Back

-I may have missed some exceptions, especially the ones where m = 1. In that case, the results varied greatly. 
-I can see this solution apply to problems that involve different shapes such as rectangles