Twelfth Week: The Last Week

This week was the last week of classes (almost, there is one more lecture next week officially), but we pretty much finished all the material that will be covered this year anyway. These past two lectures Danny introduced to us several different concepts, but first he allowed us to understand the halting problem better by using other problems and extending them to the Halt one. He also used the process called diagonalization to show how some problems can't be solved.

As well, we started to learn induction. I have already solved many problems using induction, so I have got a lot of experience, but Danny's method was different, using conditionals and statements involving logic. I have understood induction much better because of this.

Finally on Friday we had another problem to solve - Diagonals Counting. We were supposed to draw a line from the upper left to the lower right corner of a m by n rectangular grid (the diagonal). Then we were supposed to understand through how many of the grid squares the line will pass. The picture below shows a 4 by 6 grid where the diagonal passes through 8 squares.



The base cases were easy to come up with - given input D(m,n), where D outputs the number of squares that diagonal passes through, we note that D(m,n) = D(n,m). This is seen clearly if we simply rotate the paper.

Next, if m = 1, then D(m,n) = n (switch if n = 1)
Then if there is a common factor between m and n, we have to factor it out: D(m,n) = c * D(m/c, n/c) until the two values are either not co-factors or either m or n equals 1.
If there is no common factor, then D(m, n) = m + n - 1.

This was a pretty difficult but an amazing problem!