Week 12: Remarks

I want to thank Professor Heap for lecturing this course. Personally, this course gave me some challenges and it pushed me to my limits. The course content was challenging, but not too difficult to the point where it is undoable. Out of the five courses I took this semester, I think this is the most interesting one because I had no previous knowledge of proofs. On the other hand, my other four courses had content related to courses in high school. Overall, the course was fun and interesting and I hope to learn more proofs as well as their applications in the near future.

Week 11: Final Week & Problem-Solving Question

It's hard to believe my first exam is scheduled on December 8, which gives me roughly two weeks to prepare. This post wraps up the last full week of lectures and tutorials. Next week is strictly a Q & A session, but I'll still attend those class regardless because I need some clarification regarding some minor topics. As for this final week of new material, Professor Heap discussed the behaviour of python functions and briefly introduced simple induction. It was fairly easy to comprehend; a python function can only be created if the following two criteria are followed:
1. The behaviour of the function for every input
2. Write a procedure that computes the behaviour of the function
I've used this procedure constantly in CSC108. One of the assignments in that course asked to create a set of "test cases", which are used to test the "robustness" of a python function. This essentially follows both criteria at once because the actual test cases represent the input, while the code used to produce the correct result of each input is the writing procedure of that specific test case. Overall, the lecture was easy to digest.

To conclude my blogging of this course, here is the procedure I used to solve a complicated math-based problem. The structure of my solution is based off Polya. To begin here is the actual problem itself:

You have a rectangular grid made up of m rows and n columns (the symbols n and m represent positive whole numbers). Draw a line from the upper left to the lower right corner (the diagonal). How many of the grid squares will the line pass through the interior of? If you are told m and n, can you calculate how many squares the diagonal will meet the interior of? Can you derive a formula?

Here's what happens for 4 rows and 6 columns:

So, according to this example, the diagonal line passed through 8 squares.

Understanding the Problem

-This problem involves a group of squares organized into a rectangle

-The line begins at the top-left corner of the rectangle and ends at the bottom-right corner of the rectangle

-What's Given: The number of rows (represented by "m") and columns (represented by "n")

-What's unknown: The number of squares in contact with the diagonal line

-Condition: The line must be in contact with the interior of the squares

-The condition is clear; it displays a clear distinction between a square that is in contact with the line and a square that is not in contact with the line
-Rotating the rectangle 90 degrees in either direction will produce the same combination, but the number of rows will be the number of columns and vice-versa

Devising a Plan

-Try out "perfect rectangles", where the number of rows is equal to the number of columns (m = n)
-Observe the difference between m and n
-Check out odd and even differences 
-In addition to the difference between m and n, calculate the difference between that and the number of squares in contact with the line

Carrying Out the Plan

-I conducted 10 different tests, producing the following results:
> m = n = 2 produces 2 squares
> m = n = 3 produces 3 squares
> m = n = 4 produces 4 squares
> m = 1, n = 2 produces 2 squares
> m = 1, n = 3 produces 3 squares
> m = 1, n = 4 produces 4 squares
> m = 2, n = 3 produces 4 squares
> m = 2, n = 4 produces 4 squares
> m = 3, n = 5 produces 7 squares
> m = 12, n = 20 produces 28 squares
-I noticed that if the absolute difference between m and n is even, it produces one of these results:
>If m and n are even or m and n are odd, the number of squares = n + abs(m-n)
>If n is even, the number of squares = n
-If the absolute difference between m and n is odd, it produces one of these results:
>If n is odd, the number of squares = n
>If n and m are odd, the number of squares = n + abs(m-n)
>If n is odd, the number of squares = n + abs(m-n)
-If the difference between m and n is zero, the number of squares is equal to m or n
-As a result, I produced a python function that produces one of the above results:

Looking Back

-I may have missed some exceptions, especially the ones where m = 1. In that case, the results varied greatly. 
-I can see this solution apply to problems that involve different shapes such as rectangles

Week 10: Short Week & Assignment 3

The two day break was very relaxing; it gave me enough time to briefly review each of my courses, especially this course. Since there were only lectures on Wednesday and Friday, Professor Heap quickly skimmed through the slides and because of that, I decided to solely listen to what he was saying (rather than listening 70% of the time and writing 30% of the time). 

In terms of content, this week was whether a function would halt or continue executing in a particular situation. I know that if a program halts, it would not display a result in the python shell, which means it is in an infinite loop, but I am unclear regarding the structure of a halt function. Hopefully, the annotations can provide some clarity. This idea of halt was discussed throughout the rest of the lecture. In python and any other programming language, there are functions that are "computable" and there are functions that are "non-computable". A non-computable function is a function that is well defined, but does not tell how to compute it. An example of a non-computable function is the halt function that was mentioned a few sentences ago. In other words, the halt function cannot be easily identified as a computable function because it could display a result in the python shell after a certain number of minutes. A typical function such as "str.isdigit()" displays its result instantaneously; with the halt function however, it may not display its result instantly; it may in fact not display anything at all, which indicates it's non-computability. I did encounter this problem while working on an program for CSC108H1. The task of the program was to display the author of a text file based on a set of characteristics; one of them was called "average sentence length". Once the program reads a file, it will display the name of the author in the shell. In some cases, the author name was displayed instantly. In other cases, it took several minutes for the result to display. That is an example of a "non-computable" function. If I was impatient, I could have stopped the execution of the program if it failed to display a result within a span of a few seconds. I may have assumed that one of the functions in the program was executing an infinite loop.

To conclude this week's blog, next week is the last week of the course! I am very excited while at the same time feel a little overwhelmed. My first exam is to be held on December 8, while the exam for this course is to be held on December 10, which gives me approximately 2 and a half weeks to prepare. I am certain that I will focus heavily on this course and use all my resources to thoroughly prepare for this exam.

Week 9: Test 2 Results & Big Omega

     I was very disappointed when I discovered my mediocre result on the CDF website. My initial reaction was frustration and anger. Upon that, I knew I had to change the way I study the material. I have noticed that I mainly memorize the processes with solving the problems. Now I know that I need to actually practice completing problems such as the ones from the course site. Hopefully, more practice translates to a higher mark on the examination.
     In regards to this week's course content, I learned the process of proving Big Oh and Big Omega. Professor Heap mentioned Calculus a few times and he suggests using it for solving these proofs. All the calculus-based techniques are already familiar, so, I should have no problem with understanding the processes. The 
statement associated with Big Omega is very similar; in fact, it is nearly identical to the Big Oh statement, but the only difference is instead of f(n) being less than or equal to "c times g(n)", f(n) is greater than or equal to "c times g(n)". So, I became a little more confident since the process of proving Big Omega is similar to Big Oh. 

     I think the result from Test 2 threw my focus off course because it was much worse than what I anticipate. Like I said, it is time to increase study time by solving practice problems from the course site. 

Week 8: Maximum Slice & Proving O(n^2)

This week, I learned the essentials of proving O(n^2). To me, it feels very similar to the proofs discussed last week. So, it was fairly easy to understand and I'm assuming Professor Heap will continue on last weeks slides because there were three slides left to discuss. I hope he begins class on time because it usually begins speaking at roughly 15 minutes past the hour, which leaves him only 45 minutes to cover the slides. He would have completed last week's slides if he began speaking at exactly 11:10, but I guess he doesn't want anyone to be late. 

Ever since I wrote the first term test for this course, the content was fairly easy to digest. It could be that I wasn't studying hard enough during the beginning of the semester, and the result of the first test sure woke me up. Hopefully the results from the second test (which will be released next Wednesday) are a sign of improvement.

Week 7: More of Last Week & Finishing up Assignment 2

This week was a little rough, in terms of understanding the content. It was mainly focused on the efficiency of insertion sort and calculating the worst case scenario of inputting a value for an insertion sort. This sort is constructed with a set of "while" loops. At that point, I was not clear with the upper and lower bound of a worst case scenario. Hopefully, the course notes will provide an explanation regarding this part of the lecture. As for the rest of the content, it was easy to understand. The O(n^2) is simply a set of functions that returns positive real numbers by inputting natural numbers. This is necessary to determine the worst case scenario of insertion sort. 

In other news, Assignment 2 for this course is nearly complete. It was a little difficult, but it was convenient because it provided preparation for the second term test. Hopefully, results are improved compared to the first assignment, but I think a little more practice wouldn't hurt. 

Week 6: Inference Rules & Sorting Strategies

This week, I learned the rules of introducing logical structures; they were fairly understandable because I already knew how to structure a proof based on the structure of the claim. If it is a implication, assume the antecedent and prove the consequent. I had no problems understanding these rules. For the rest of the lecture, Professor Heap introduced sorting strategies and it began with two common algorithms: Insertion sort and selection sort, one of which is very familiar because I use it for several card games. I may need to review the worst case for a program because I am unclear as to how the worst case scenario is generated for an insertion sort. Overall, the lecture was fun and refreshing.