The Final Note

This course has pretty much come to an end. There is just the exam to go. Yesterday my group and I finished the last assignment (finally!). It was pretty difficult to understand at first but after reading through the course notes and the lecture slides, everything started to fall into place. I guess the hardest part was Question 6, the halting problem. Man, that took me a while to figure out. Here is a picture from Timothy Lock's SLOG (http://timothylock.me/sLOG/2014/11/30/week-11-halting/), which I also found in the course notes that really helped me understand and solve this problem.



The exam will be in a week, and I am saddened by the thought that this course is almost over. It has been a great experience and I really liked both Danny and Jason, my TA. They were awesome! Thank you guys for making this such an interesting course.

Other SLOGs

Over the period of the past few months, I have sometimes visited other SLOGs posted by my colleagues to see whether we have the same reaction to the course. In particular, I selected a few ones to follow. The first one was done by Loora Li, at http://looralicsc165slog.blogspot.ca/
I found that, like myself, she is also taking MAT137 and MAT223. In fact, sometimes she highlights the thoughts that have popped into my head during the lecture but which I decided to neglect for my blog, such as the mentioning of one-to-one and onto. It was also interesting to see that she had almost identical problems to mine (such as difficulty with Question 6 on A3, etc.)

Also, I loved the slog of my friend Vlad Chapurny, found here: http://vladcslog.blogspot.ca/
He had a humorous approach to his posts, and I liked how he shared a lot of his personal feelings. Here is, for example,  one of his closing sentences: "Now I am just sitting and biting my nails to get my results back, in hope I did well on all the work this week."

However, I was disappointed with a lot of slogs which just had one entry in them, from the very first week. It was sad to see that people just gave up on this activity,  which I find quite interesting because I don't usually blog about anything.

Another cool person who I found via the slog was Timothy Lock. His blogs had a very interesting explanation to the different problems he encountered, and his answers included diagrams and code snippets and pictures, just what I like. Also, I was impressed by the website he made, very unique and bright and colourful. Kudos to him!

Finally, one last blog I'd like to mention is Keirn's, from http://keirnslog.blogspot.ca/
Keirn had quite lengthy discussions about almost everything in this course, and he also included diagrams and code and logical solutions. Moreover, he even included a song in the blog, which was a first, even though I looked through many other different slogs. Overall, I think he had a pretty interesting way of presenting his ideas, and some of them helped me understand the material better.

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!

Eleventh Week: The Short Week

This week was really short, with just two lectures held. The reason for this, as I think I have already mentioned in the previous posts, is the Reading Week. Not that I did that much reading over those two days, but it was a really welcome short break. Now with just one week to go, I am feeling a lot fresher and readier for the soon upcoming exam.

Meanwhile, this week Danny has been going over the halting problem, proved by the famous Alan Turing way back in 1936. It was quite easy to understand because it was easy for me to follow the steps of the proof by contradiction we derived in class. I will probably need a little more hands-on practice before I feel totally comfortable with this concept.

As well, the third assignment has been posted, and I believe it is a nice preview of what is going to be on the final exam. Finally, the CDF website is still down, so there is no way for me to figure out what my marks for my test 2 and assignment 2 are, which worries me a little.

Tenth Week: Results

Well, we got our test 2 back, and I wasn't that satisfied with my mark. Turns out I did screw up some things that I should have been more careful about. However, on the bright side, I started to really get the Big-Oh and Big-Omega principles, since they are very similar to the proofs we have been doing for the past month, with just maybe a little more thinking involved.

As well, there is no tutorial this week, nor is there a lecture on Monday, due to the Reading Week, thanks to the gracious University of Toronto. But Danny and Larry made sure that we don't just waste our time by telling us that they'll post the third assignment over the weekends. I guess that this is a good thing because it will give me more free time to spend thinking over the problems stress-free, which is exactly how I prefer to complete my tasks.

Ninth Week: The Second Test

This week went by pretty quickly, probably because I only had this course twice. On Wednesday, I had my second test for CSC165, and it was actually quite easy - just three proofs. Since we were told whether to prove or disprove each statement, I automatically wrote out the structures for each proof and then completed the in-between logic without much problems. Two of the questions were very similar to the ones we had to do for Assignment 2, which was due on Monday. As well, one of the proofs we did earlier in the course came in as a quite useful property, which was great because I put it down on my cheat sheet.

During the lectures, we have continued analyzing equations using Big-Oh and Big-Omega functions. They are becoming easier and easier to understand. I guess that practice does make perfect. Overall, I am really happy about the way the course goes.

Eighth Week: Scary Proofs for Halloween

This week was a little more difficult than the others. Even though we have been doing proofs for quite some time now, and the proof structure was pretty easy to remember, the two proofs that we completed this week were much harder. They were Big-O and Omega proofs, which are basically upper and lower bounds for worst-case scenarios of linear search programs. What was hard about these proofs was the counting of lines that the program will run through in the worst case. In particular, it was a little hard to understand why, for the Omega proof, we had to count only the lines of the innermost loop. Thankfully, these won't be on the test next week.

Speaking of the upcoming test, I'm not sure at all what this test will be on. Just proofs? Hopefully, because that seems pretty easy. It is pretty much all that we have been doing the past few weeks, and the assignment as well. Even though I am working in the group, I have managed to prove (or disprove) almost all the questions by myself, so I consider myself ready for whatever is coming up on the test. Hopefully. :)