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.

Week 9 and 10

In these two weeks, we begun analysing worst, best and average cases of a program. In week 9, we were introduced to big oh notation, and counting the number of steps in a program, which we later defined as the running time. We typically compared the running time of different sorting algorithms. In tutorial of the same week, we discussed how to find the total running time of programs and discovered that the total worst case running time of a program can be formulated by sigma notation. We also discovered that running time depends on the the length of the list of which we want to sort.

This allowed us to transition into our main topic for the week, which is Big oh proofs. We spoke about this briefly during earlier weeks of this course but it was more formally introduced this week. In our Tutorial exercise, we were given problems to work on which involved proving that a function is inside big oh provided that it satisfies the given definition.

In addition to big oh, we were also introduced to big omega proofs which computes the worst case of an algorithm. Both have similar definitions but with slight variations in inequality signs.

Overall, this week has been fairly challenging, however, I have been able to understand the basic structure of the proof and how it can be applied in different ways to various applications. I have a somewhat understanding of the theory behind proving big oh but I hope to further improve my understanding of big oh notation prior to the final exam.

Week 8

This week by far was the most demanding week as we transitioned from proofs into Big Oh analysis. I found it hard to cope up but managed to consolidate lecture notes and office hours to clear up my understanding. We learnt about the formal definition of big-Oh analysis. We learnt that through big-Oh we will be able to count the number of steps in a program execution. We also learnt about the idea of a worst case in a program, which is a case in which a program takes the most amount of steps in execution. The number of steps in a worst case can be calculated if the program takes the most amount of steps.

In tutorial, I finally cleared my understanding of proofs as our tutorial exercise included proofs.  This week overall was enjoyable and did not seem very tedious, as I managed to understand the concepts completely.

Week 7

This week, we were introduced to proof by cases. This includes breaking the argument into different cases and proving true for each case. We see this a lot in conjunction or disjunction statements. It is also used in proving absolute values of statements. This is because, the proof of an absolute value inequality can be simplified to -b < x - a < b where the original statement is | x - a | < b. This proof method seemed less complex than previous proofs because I fully understood the Professor's explanations and examples.

In this week, we were also introduced to counting steps in an algorithm, which exposed me to the concept of Big Ohs. We learnt about the efficiency of algorithms and how the number of steps which is measured as "running time" can be formulated into expressions. This lecture was straight forward as counting the number of executions in a program did not seem very demanding for me. This was one of the most enjoyable lectures for me since I have always wanted to learn about efficiency in programs.

Week 6

In this week, we were introduced to proving something false and negations of statements. This week really allowed me to increase my understanding of proving complex statements. It gave me the understanding of going from the antecedent to the consequent of the proof by assuming the antecedent and proving the consequent. We were also introduced to proving floor functions by using their definition. This week was another hectic week for me as the concepts at first seemed extremely difficult to comprehend.

One extremely difficult concept, I found was proving the limit of a statement. I was not able to find the proof of limits but I hope to clear my understanding soon.

However, during tutorial, my confusion from last week cleared up as our TA went through many examples of proofs and explained each step carefully. We were also introduced to proof by negation. This allowed me to take the negation of a statement and proving the negation. Upon successful disproval, we have successfully disproven a statement.

Week 5

This week was extremely busy for me as exam preparations were already following the assignment were underway. The exam overall did not seem hard as the questions were similar to the practice paper Professor Heap linked us. I have also practiced with various practice papers from previous course offerings, therefore I was prepared for the exam. In addition, in order to facilitate my learning, I had also read  through the book "How to prove it" from the recommendation from Professor Heap.

During Tutorials, we were also introduced to proofs and proving algorithms. We also went through the basic syntax of proofs including comments and indentation. Much of the material covered also linked to my other CS class, CSC148 since the syntax was very similar to Python. It allowed me to connect both subjects and I was ultimately able to find that writing python programs were very similar to writing structured proofs in mathematics. It provided me a lead in to the world of proofs and created a foundation of my understanding of proofs.

Week 4

During the fourth week of the course, I have continued working on my assignment and clarified my concerns with Professor Heap. This week has been a great learning experience for me because I am finally starting to understand my errors in the assignment. Towards the end of the week, I have fixed these errors and provided appropriate explanation. In the end, I have managed to finish the assignment with my group partner and submitted it on time.

During this week, we also learnt about proofs and how they can be proved. We went over the step by step procedure on how to appropriately structure the proof with explanations. We also learnt how different laws can be used to prove a statement and provide explanations. In addition to this, we have learnt about Implications and how a statement can be represented with mixed quantifiers. Hence, by the end of this week, I am now able to differentiate between statements that use the existential quantifiers and statements that use the mixed quantifiers. One aspect of the course content however, that was difficult to understand was limits. Although Professor Heap was able to explain it thoroughly, the notation that he used was confusing. I hope to fix my understanding this weekend in order to prepare me for next week's mid-term exam.