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. :)

Seventh Week: Proofs and Penny Piles Solution

This week we continued to learn about different types of proofs, such as direct (implication - assume A, conclude B), indirect (contrapositive - assume not B, conclude not A), existential (providing an example, universal (proving true for all elements), and falsity (proving the negation). While the format of the proof was quite easy to get, sometimes the tricky part is to come up with the in-between steps. However, we did lots of examples, and I am starting to get the hang of it, and I have more practicing to do since the second assignment is all about the proofs mentioned above.

As well, this week we had another fun activity where we had to come up with all the possibilities of the number of coins that we can rearrange from left to right drawer by exchanging half the coins between them. The result is actually quite surprising, because we can get all arrangements, as shown in the tree below. Note that all the values can be exchanged (for example 3 | 61 means that we can get 61 | 3 as well), simply because my third step was operation r, and not l, which resulted in 48 | 16 instead of 16 | 48.

Sixth Week: Grades, Proofs

This week has been one the best weeks yet, and a big part of this cheerfulness is the fact that I got my results back for my exam and my assignment. Getting perfect on the midterm is always a great boost to your self-confidence and enthusiasm, while on the assignment I got a very nice grade as well. As for the lessons, this week we started learning the format of different types of proofs (existential and universal), which is pretty easy to get as it is very repetitive. However, sometimes the logic in between the steps can get tricky, so I have to pay a lot of attention to small details. Also, I find it quite tedious to write all the concluding sentences (such as all the variables, the antecedent and consequent), but I understand that this will be crucial if we have much bigger proofs that can take several pages. Therefore, I practice a lot of different problems in order to get the format of the proofs down to automatic.

Fifth Week: The Test

This week was my first test in university, so obviously I was pretty stressed out. Even though I spent a lot of time going over the material and applying my knowledge on the practice tests, I was still afraid that there will be some trick questions on the test that I wouldn't know how to do. Turns out I didn't have a lot to worry about because the test was a LOT like the practice test that was handed out. And for one of the questions, I just had to apply the same logic that I was using for my first assignment. However, I found the preparation for the test still essential for my - hopefully - success. I managed to refresh all the concepts and ideas taught in this course so far. As well, I created a very detailed aid sheet that I didn't actually use during the test since I understood all the concepts clearly. All in all, I am very happy about the way the test went and now I am looking forward to the day off we get for Thanksgiving! ;)

Fourth Week: First Assignment and Test

This last week was a little more stressful than the previous three because of the Assignment 1 that was due on Friday. Man, was it tricky and nerve-wrecking, always having to double-check your work and second-guess your answers. Not to mention that I also have to study for the test that's coming up in less than a week!

The lessons themselves were pretty easy for me to understand, since we started the topics of proofs, inequalities and limits, mathematical subjects with which I am very familiar. I also liked this week's tutorial and having to use different laws to prove implications. The 4 laws that we learned about are the commutative, associative, distributive, and De Morgan's laws. Finally, another cool idea called transitivity was introduced in this course - it is the chain of results that proves P => Q by finding in-between implications.

Third Week: More on the Folding Problem (Coding)

So, now that we know the pattern, we can use recursion in Python to get the results. Below is the code that can be used to generate that pattern, given the number of folds:

And here is the result of running the code in the Python Shell:

Third Week: Answers to the Exciting Folding Problem

This class has probably been my most favorite class of all, probably because I am such a big fan of logic problems. And although the folding problem seemed pretty challenging at first, after giving it a little thought and using observation, I was able to find the pattern very quickly, before the hints were given. So below are the answers to this problem explained thoroughly, I hope.

Obviously the first step was to test the first few cases, for which I got the following results ('D' is down crest, 'U' is the up crest):

Fold #1  =            D
Fold #2  =         U D D
Fold #3  =  U U D D U D D

The first major observation that helped me crack the problem was to notice that the middle element is always 'D'. Then, it was just a matter of identifying what comes after that 'D' and before that middle 'D'. To get the answer, we have to realign the answers to the right, with the middle D underlined:

Fold #1  =                                             D
Fold #2  =                                       U D D
Fold #3  =                           U U D D U D D
Fold #4  =  U U D U U D D D U U D D U D D

Do you see it now? The pattern on the right of the middle 'D' is the pattern of the previous fold. Now, it's just the matter of identifying what is the pattern on the left of the middle 'D'. But if you look at the first patterns (aligned center), and compare the results, you'll see that they are symmetrical in a way. If you switch every 'U' for 'D', and 'D' for 'U' on the left side, you'll see the symmetry:

Fold #2  =         U D D                               =               D D D
Fold #3  =   U U D D U D D                         =         D D U D U D D

Therefore, the left pattern is the reverse of the opposite values of  the right pattern. Mathematically, I guess you can represent the answer the following way:

New-Pattern  =   reverse (not Old-Pattern) + 'D' + Old-Pattern


Geometrically, we can also see a pattern, as shown below: in the red we see the previous pattern repeated, and in the dashed green we see the old pattern again, only rotated by 90 degrees.

First and Second Week (September 8 - 19)

These weeks were my first two weeks of CSC165H1, or of any course, for that matter. And while I was a little stressed out about lectures, especially given the fact that I missed a couple of lectures as I was wait-listed on ROSI, I found it very easy and stress-free to adapt. I guess I have to give a lot of credit to my instructor, Danny Heap, for making the lectures so exciting. He is always upbeat and makes the class very enjoyable. What I also like about his method of teaching is that he always explains every topic very thoroughly and provides a lot of examples to help understand and remember that topic. As well, every question that I - or any of my fellow classmates - have are immediately taken up and answered with absolute clarity.

So far, I am extremely satisfied with the course. It covers material similar to some other courses I am also taking (MAT137Y1), but it provides more in-depth definitions and relates it to computer programming. As well, this course is also acting as a refresher of Python syntax, which I haven't used for some time.

The one problem that I really enjoyed solving this week was figuring out the ages of the 3 kids given the facts that the ages multiply to give 36, their sum is not unique, and that the eldest person plays piano. It didn't take me long to figure out the two possibilities (9, 2, 2 or 6, 6, 1) that might meet the first two conditions, so the answer - 9, 2, 2 - was pretty obvious. I liked this example because it involved logical thinking to get to the answer. Besides, it was also cool to use the new notation to outline the problem first, making sure to indicate all the given and required variables, and then coming up with multiple methods to find the solution.

As well, a lot of attention was paid to quantifiers, implications, converse, and negation throughout the lectures. And while for some people it may be easier to use mental Venn diagrams, I also found it more helpful to reword the question first, and then see how to prove it wrong (when using negation). For example, take question 1 d) from tutorial exercise #1, "some of the three python programs don't pass all three test suites." To negate this sentence, I first change it to "not all programs pass all three test suites", and then just get rid of the "not", thus getting the following negating sentence - "all programs pass all three tests." EDIT: As I learned today, this technique is actually called 'contrapositive,' and not 'negation,' but the idea is the same - it toggles the truth value of the statement.

Overall, I am very happy with my experience with CSC165H1 so far, and I am looking forward to my future lectures!