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. 

Week 5: Proving False Statements and Limits

This week, I learned the process of proving false statements and wrote my first term test. Beginning with proving false statements, it is equivalent to disproving a statement. In other words, proving that something is false is simply proving its negation. Once I found out that disproving a statement is the same as proving its negation, it became very easy to understand. The rest of the lecture was mainly on proving a statement with cases. I somewhat understand the process of proving with cases, but I need to refer to the course notes to fully understand the process. 

As with the term test, I have mixed feelings because there were a few questions that were a little hard to comprehend. The first part of the test was what I expected, but it became more difficult as I progressed through each question. Overall, I should have done better if I spent more time on the course notes rather than the lecture slides. Hopefully, this is a signal for me to spend more time on the course notes for the next term test.

Week 4: Contradictions & First Term Test

This week, I learned how to prove an existential claim as well as a sequence. Proving an existential claim very similar to proving a universal statement, except there are a few changes to the wording. As for a sequence, it is nearly identical to the proof of an existential claim. As a result, I was able to understand it quickly with no hesitation. The last part of the lecture was about the use of contradiction; it was sort of confusing at first, but once I read the notes over and over, it became clearer. Proving the contradiction of a claim shows that the contradiction is false, thus, making the original statement true. 

On the other hand, I wrote my first term test of the year! It was a little jarring at first, but I was able to complete all the questions within the 50 minute period. However, I realized that the test was very similar to the test test that was posted a few days ago. I felt very upset because I did not spend enough time with the sample test; I simply skimmed through the paper; I focused most of my studying on the course notes. Hopefully, the mark I receive on this test is somewhere in the 60-80% range. 

Week 3: Mixed Quantifiers & Intro to Proofs

There are a few things I found interesting on this week's course material. Transitivity is simply a relation between multiple cases. For instance, if driving a sports car implies driving fast and driving above the speed limit implies aggressive driving behavior, then driving a sports car implies driving aggressively. Multiple implications lead to a single conclusion, such as the example mentioned here. A few slides down, there were a few statements that were interpreted with a graph, but it did not seem clear in my eyes. I know Professor Heap said something like "if the enemy goes first, then it is possible", but I need to re-read the lecture slides as well as the course notes to improve my understanding of this concept.  

Throughout the rest of Friday's lecture, Professor Heap introduced proofs. I am not entirely excited about this because I sometimes struggle with proofs, which seem frustrating and a waste of time. Nonetheless, proofs is something I must master because it is a vital component in computer science. This introduction mainly focuses on the outline of a proof, which to me is fairly understandable. 

The first test of this course is to be held on Wednesday, October 4 and it will cover chapters 1 & 2. I plan to spend at least one day solely on preparing for it because it is worth a large portion of the course. Hopefully, doing well on this test sets the stage for doing well on my other courses.   

Week 2: Back on Track

This week, I learned a few important topics, all which are applicable to Assignment 1, which I have not completed yet. Negation is the easiest to digest because it simply translates a statement so that it is the opposite of its original. I have used negation many times during my experience with programming Java. In that case, the "not" keyword is used as negation (same goes for a few other programming languages).  Scope was also discussed in class and it is also used in programming; it is simply determining the order in which a group of statements are evaluated. I immediately understood this concept because I had a similar experience with Java programming. 

In regards to this week's tutorial, it was completely different from week one; despite the fact that I arrived 17 minutes late, I had no shred of doubt regarding the content. As soon as I saw the writing on the blackboard, I felt relieved because the solutions that were posted on the board were identical to the ones I wrote the night before. During the quiz, I was one of the last to complete it because I prefer to use every single minute, even if I had complete trust to solution I wrote on the paper. I already mentioned the fact that I did not complete Assignment 1 yet, but I plan to spend at least one full day on it, with no study time from any of my other courses. 

The commutative, associative and distributive properties were also familiar because I learned these properties back in the "early days" of mathematics.  

Overall, this week is more enjoyable compared to last week, but in all fairness, Week 1 could have been similar to this week because I chose not to take the course seriously and it resulted in many consequences including stress and frustration. Hopefully, Week 3 continues this trend which is to relax and enjoy the ride.

Week 1: Rough, but Manageable

     During the first several days of classes, I focused mainly on travelling to them rather than the content itself, and CSC165 is no exception. In fact, this is the only class where I feel lost in the echo. The content from week 1 appeared to be simple and concise, but I realized that this course requires maximum precision. As with any course, one must review and study the content on a daily basis. I have been too focused on my other courses, particularly SOC101 and ENV100. Despite my lack of prioritization for this course, there were a few things I found interesting to me. The course began with questions that ask whether CSC165 is the right course; one of them was "Do you memorize math?" I immediately knew that CSC165 perfectly matched my needs because I have a strong background in mathematics and this is mainly due to my reliable memory. However, my memory is far from perfect and I am no math wizard.
     Overall, this first week was hectic and it felt stressful. Now that I established my routine for the semester, I can now focus strictly on my studying time. There is one thing that may interfere with my studying is laziness. We all had some moment where we "chose" to be lazy and that is totally fine, but once it controls your life, it becomes a never-ending cycle. Hopefully, I start out fresh next week with a desire to learn.