SLOG #9: Problem-Solving (Diagonals)

Before I begin my problem-solving episode, I would like to first mention that the problem-solving section on http://zanecsc165.blogspot.ca/ was one of the most detailed (and awesome) post I've read.
But back to my problem...

Understanding the Problem:

I have a rectangular grid made up of m rows and n columns, where m and n are whole numbers. Problem: If I draw a line from the upper left to the lower right corner, how many grid squares does the diagonal line meet?

Given information: values for m and n

Unknown: number of squares the line passes

Devising a Plan:

-          The first thing to do is to try a couple of examples. Consider the following cases:

Ø  m and n are both even

Ø  m and n are both odd

Ø  m = n

Ø  m is even and n is odd (and vice versa)

-          Take note of any patterns that seem to appear

-          Try using a hint from the back of the worksheet

→ What happens in special cases, such as n = m + 1, or when m and n are both even?

→ Are there cases when the problem scales down to some smaller rectangle?

-          From the patterns, try coming up with a universal formula that works for all cases

Carrying out the Plan:

We can see that in this special case (m = n), the number of boxes filled equal m (or n).

What about when m and n are both even?

When m and n are both even, notice that the pair (m, n) can be reduced to a multiple of some numbers. For example: (2, 4) = 2(1, 2), (2, 6) = 2(1, 3), and (8, 4) = 4(2, 1).

This means that whenever we see a pair of number that have a common factor other than 1, we can factor out a number and scale down the rectangle. 

In the case where (m, n) = (3, 9): notice that 3 can be factored out 3(1, 3). 

Now let's consider when one variable is even, and the other is odd: 

In the sets of numbers that I used, none of them could be factored. This means that when devising a formula, we have to take into account large rectangles that cannot be broken down into smaller ones.


Now that I have drawn sample rectangles, there are some prominent re-occurring patterns.
1. Large rectangles can be broken down into smaller ones if the set of numbers have a common factor that is not 1. When we factor out a some integer, let's name it variable k, we have k number of small rectangles with the dimensions (m/k, n/k). What does this mean? This means that by knowing how many grids the diagonal passes on the rectangle with dimensions (m/k, n/k), we can know how many grid boxes the line passes in the non-scaled rectangle (by multiplying the number of grids found in scaled-down rectangle by the integer k).

2. In special cases, such as n = m, we can automatically conclude that the number of grid boxes the diagonal goes through is equal to m or n. This makes sense visually as well.

3. There are rectangles where dimensions are not-so-friendly. We need a method where it would work ANY type of rectangle. Here is my method:


Assign x = n and y = m, then treat them as coordinates and plot them on a Cartesian plane. Draw a line starting from (0, 0) to (x, y). Now that we know two points, we can get the slope of the line. Put the line in y = mx + b form.

Plug in values for x = 1, x = 2, ..., x = n - 1, and get the corresponding y-values.

Now, take the ceiling of the y-value. Whatever the value the ceiling is, shade in the box to the right of the x-value (for clarification, refer to the example below). Notice that when x = 2, we shade in two boxes. This is because when x = 3, the ceiling of y increases one step to two. This means that there is one grid the diagonal is crossing in order to connect the two boxes.

We can now add up the number of boxes shaded in (and also add 1 to account for the box at (0, 0)). This gives us 6. In order to get the number of grids for the rectangle (4, 10), multiply 6 by 2 to get 12.


Looking Back: 
I know that my method is not efficient. I'm having difficulty putting this method into a nice, one-step formula. In terms of correctness... so far it has worked for all examples that I have tried (including all of the cases mentioned in the planning stage). However, since I do not have a formula to sum this up, it would be extremely tiresome to calculate something like m = 150 and n = 200. I could possibly implement a python function using this line of thinking though.

SLOG #8: Finally Understanding Big-Oh, but New Confusion with Halting

I haven't written in about two weeks so this post is going to be longer than usual.

Last Monday and Tuesday was reading break. Hooray for long weekend! I was planning to get some studying done for CSC165, but other assignments and midterms kept me busy.

Last Tutorial: 
We covered proofs with big-Oh.

Steps to proving big-Oh:

1. Write out the definition of what it means for a function to be in big-Oh. In words, the definition basically means that there is a c in the set of positive real numbers, and there is a B in the set of natural numbers, such that for all natural numbers (n), if n is greater than or equal to B, then beyond B (the break point), function f(n) is upper-bounded by c multiplied by the other function.  
2. Do some rough work to find values for c and B. Try to play with manipulating inequalities until you have the result you want. 
3. Write the proof structure, and fill in the body of the proof with the information gathered from rough work. 

Lectures and New Information

For the past week in class, we've been talking about the halting problem. I have to say this is the most confused I've been all semester. All I know is that Church and Turing first proved the halting problem. And my job is to reduce halt to a function (not even sure what that means). Literally, that's all I know about it. I did go visit the CS aid center but the TA there didn't learn about so he couldn't help much. I'm planning to read over both Danny's and Larry's class notes on it, and definitely go through the course notes. And then after that, visit office hours. I'm really worried I won't understand this in time for the assignment though. In our assignment, it's asking us to reduce halt to meaning_of_life. The only information we're given is "return True if f(I) return 42, False otherwise". I'm not quite sure what I'm supposed to do with that piece of information.

However, I'm glad to find that I'm not the only person with this confusion. http://celinasopiniononcsc165.blogspot.ca/ expressed similar confusion. She did do a blog post on a halting problem, but after reading her post, I'm still confused as ever. 

SLOG #7: Thoughts on Test 2 and New Challenges

Thoughts on Test # 2: 
I'm so glad this stressful week is finally over (assignment due on the Monday, and a term test on the Wednesday!). Generally, I thought the test was not as bad as what I was expecting. There was definitely enough time to finish. The only question I struggled with was the second one. Guess I still haven't mastered limit proofs. However, the first and last question were surprisingly similar to assignment 2.

What I'm having trouble with...
I've been having difficulty understanding lecture for the past week. I think most of the fault lies on me, as I haven't had the time or energy to look over my notes. But good news is, I finally took the time to study big Oh proofs, and counting steps over the weekend, and I think I finally understand what's going on (yay!). Once you get past all the Greek letters and variables, it's not too bad.

The trickiest part about it is picking values for c and B. The general idea to take out of doing these proofs is to leave the values for c and B blank when writing the structure. Then go on to do the proof body. Also, don't be scared to overestimate! For example: 3n² + n ≤ 3n² + n² = 4 n². You're trying to simplify the inequality so that the right side can be expressed in terms of the variable of the highest degree. After doing this, you have the value for c, and you can go back and assign a value for c.

 .