Diagonals (Problem solving)

1. Understanding the Problem
In this particular problem, we are presented with a grid of m rows and n columns with a line drawn diagonally through it. We want to know how many grids will have the line pass through it. We want to come up with some formula that we can use to determine the number of squares that the line will pass through given a specific m and n.
The unknowns here are the m and n, so our formula will need to include these as variables.
We are given an example figure of m=4 and n=6. Below, is a recreation of the figure, along with a simpler version of m=2 and n=3.

2. Devising a Plan
First, we should notice that this pattern seems to continue. To be sure, we created an extended version as seen below.

Therefore, we should take into mind this repeating pattern when coming up with a formula. From our simpler figure above, we see that there are 4 squares covered by the line for every 2 rows and 3 columns. This can be extended to say that there are 4 squares for every 2m rows and 3n columns.

3. Carrying out the Plan

A few other things we should consider are:

• There is 1 of 1 square crossed by the line when m=1 and n=1.
• There is 2 of 2 squares when m=1 and n=2.
• There is 3 of 4 squares when m=2 and n=2.
• There is 4 of 6 squares when m=2 and n=3.
• There is 4 of 9 squares when m=3 and n=3.
• There is 5 of 12 squares when m=3 and n=4.
• There is 5 of 16 squares when m=4 and n=4.
• There is 7 of 20 squares when m=4 and n=5
• There is 7 of 25 squares when m=5 and n=5.
• There is 8 of 30 squares when m=5 and n=6.

From this, we can draw the conclusion that it is possible to have the same number of squares crossed by the diagonally line given different m and n. This proves a bit troublesome. A piece-wise function or a formula that relies on cases will be required. So I'll stop here.


4. Looking back

The Last (Week 12)

As the final week (almost) of this course, I decided to talk about my general reception of this course instead (since I didn't bother trying to pretend I know what diagonalization is).

I entered this course with mostly a negative attitude as people who have taken it before told me it was exclusively math, and actually consisted of no programming at all. On the first day when the professor talked about ambiguous claims, I found it somewhat interesting. As the semester progressed, the topics alternated between more interesting things such as claims using words to more dull things such as proving delta-epsilon claims. Halfway through the term, I found this course to be more straightforward than I had initially thought, especially when compared to a certain math course which shall not be named.

Despite a complete lack of programming, I found this course useful as it helped me in several other course. The most helpful thing I learned during this course was the ability to generate the body of proofs. This was especially useful for a certain math course. As I became better at linking a few things together in order to solve the "thinking" portion of proofs, I became able to see mathematical proofs in a new light. I used to believe that the body of proofs were simply ass-pulls with little to no reasoning behind it, and impossible for someone who had not memorized every formula and theorem in existence. I still think that for my math course, but this course was a bit different. It was much easier to fulfill the thinking aspect and implement the body of the proofs.

I found the logical arithmetic to be useful for writing clearer programs in my other computer science course. I found myself constantly applying or undoing DeMorgan's law for my logical operations of if structures. This post gives a few more points that I left out about this course in general that I agree on.

One thing that I disliked was that when introducing new topics, the Professor seems to assume too much prior knowledge on various aspects of it from the students. While there are many students who seems to be able to follow regardless, others cannot. I do not believe that the students who cannot follow the Professor's introduction are marginally less intelligent but rather had less to no exposure on the assumed knowledge. In my case, it usually takes until the following tutorial for me to understand what was going on. Perhaps it is just that I don't tend to pay attention well to things I don't understand.

On a parting note, I think that the tests in this course are kind of nice.

終わり

Halting the Slogs (Week 11)

It's great that there was a shorter week during this week. However, I didn't actually do anything productive over that extended break. I guess relaxing can count as something, after all it's good to alleviate stress once in a while.
During this week, we touched onto the last topic in this course that was noted in Chapter 5 of the course notes. Just like starting any new topics, I immediately get lost and stop paying attention for a short while until I can actually grasp the ideas being discussed. However, with a certain test for a certain course coming up, I found myself neglecting this week's notes completely.
I kind of thought that all things in the universe could be computed given enough knowledge of it and time to implement the algorithm. This week brought to light that there exists things in which no one could ever implement an algorithm for, no matter how knowledgeable they are on the required task and no matter how much time is given. This struck me as rather strange. It is certainly true that you cannot implement everything using Python or perhaps any other programming language, but I wonder if the same can be said about implementing an algorithm by words. If it can be implemented using words, then certainly, one day, it should be possible to implement current day impossible algorithms.
One example given in class on an uncomputable algorithm, is the function halt. This student provides a proof for it. This function takes in a function and some other argument then calls the function on said argument. It will return True if that call halts and it will return False should it not halt. This problem is very apparent since if the call of the function does not halt, meaning never returning control back to the user, we will never get an answer. The fact that the function does not halt means we will never move on to the next line to return False, thus the function cannot be implemented. It may work well for function calls that halts, but it cannot determine when the calls do not halt. As said in class, it is impossible to tell if a bunch of code is taking a really long time to execute or it is caught up in some infinite loop.