Week 11 - Problem Solving Exercise and Halting programs

Week 11

During the first two lessons, we worked on solving halting problems in programs. This chapter allowed me to understand the basics of computability theory, something that I will learn in great depth during CSC236. I was also given an insight on proof by induction although we did not go through the proof in great detail. A program halts if it does not get stuck in an infinite loop and returns some value, whereas a program that does get stuck in an infinite loop does not halt. This part of the course particularly interested me since my tutorial TA mentioned that determining whether a program halts can be used to create a program that can be used to debug another program which can speed up the process of coding. 

On Friday, we focused on working on a problem solving exercise, which involved finding the number of squares a diagonal passes through provided the dimensions m and n.

Before tackling this problem, I broke the problem into smaller instances. For Example, in the example above, I decreased the problem size from m = 6 to m = 4 to m = 4 to n = 2.

Following this, I concluded that m and n are related in a way such that m + n - 2. Thinking, I was done with my proof, I did not check the case where m and n are not multiples of 2 although I did know that it is in the form of n + m - k, where k is some constant. After consultation with my other group members and I discovered a pattern that k is always the greatest common denominator of m and n. I finally concluded that number of squares = m + n - gcd(m, n). This conjecture is valid as it works for every possible combination of m and n provided that m and n must obviously be natural numbers.