Sayonara Minasan

Officially, CSC165 ended just last night, but I forgot to make my final post so I am doing it now.

Assignment #3 was pretty much like assignment #2, where you had to prove or disprove several mathematical statements. Compared to #2, #3 was actually even a bit easier, because there were less questions in #3 and also because the structure of the proof was essentially the same as the ones we mastered in the previous unit, except it was applied to different types of problems. The last question was the only part that was troublesome to figure out, but it turned out that the correct way to do the problem was just to literally follow the proof structure shown in the course note. BUT MAN WAS THE COURSE NOTE CONFUSING! I had to go to a help session and a tutorial to clear up the problem, but even then I was still confused whether the solution for the last question was really correct. Well since I already submitted the assignment, it is too late to contemplate it now.

Several people gave me comments about this course before I signed up for it. They warned me that this course is a "homework hell", that "professor don't teach the course well", or that "only smart people can do well". Oh how wrong I was. It turned out that the professor was nice, assignments were straightforward, tests were easy, and the whole course is kind of relaxing. And this blog. This is definitely the most unorthodox academic evaluation I have ever had, but whoever came up with this idea needs to be praised, because having a chance to look at other people's blogs and replying immediately back to the comments of my own blog were definitely something that I enjoyed doing. Overall, I am 100% glad that I took this course at this time of the year. I was lucky enough to meet a professor who can make the students enjoy the course while successfully teach the students computer theory.

Lastly, thanks to all of you who were reading my blog since January. Perhaps in the future (maybe in the second year computer theory course), we might meet face to face. My actual name is not Suzushiro in case you don't know. But if you ever see an Asian guy who is a fourth year life science taking computer science course starting September of 2013, then that would be me, and feel free to say hi to me when you see me.

Well, that ends my last post in CSC165. Take care and goodbye to y'all.

Who wouldn't want free lunch?

As part of the course requirement, I need to write about an episode where I solve a math problem and show the steps I took to solve it on this blog. The one I chose is this one here:

http://www.cdf.toronto.edu/~heap/165/W13/ProblemSolving/freeLunch.pdf

I chose this particular problem because it was really easy to understand and because I got hooked by its title. I mean, who wouldn't want free lunch?

[From here, I am going to assume you read the problem and know what I will talk about. It shouldn't take you more than a minute to understand what the problem is about]

Looking for a pattern for who wins was the first thing I did, because it is the easiest and fastest way to come up with a solution. So I set up three groups of friends with sizes of eight, nine, and ten. I found that f1, f3, and f5 got free lunch when their group sizes were eight, nine, and ten respectively. Subsequently, I found that when the group size is eleven, f7 won. So clearly, there is a pattern where f(y = 2(x-7.5)) is going to get a free lunch if the group size is eight or above. But I wondered, who is going to win if the group size is less than eight, could it be f(-1)? To see who wins when the group size is less than eight, I first looked for who wins when the group size is seven, six, and five, and I found that f7, f5, and f3 won respectively. So without investigating the result of who will win when the group sizes are one, two, three, and four, from the pattern above, I know that f1, f1, f3, and f1 are going to win respectively.

From the analysis above, I figured out the fundamental behavior of who the winner is going to be. Basically, the winner ID is going to increase by two from one until the winner ID is equal to the group size. After that point, the winner ID is going to start from one again, until it once again reaches the group size by increasing the winner ID by two every time the group size increase by one. The problem now is, whether I can find a function that can accurately portray this scenario. 

In a sense, this problem is a 3-dimensional problem, because the end result (the free-lunch winner ID) is dependent on two factors, one being the group size, and the other being the number of times the winner ID had to refresh itself to f1. Therefore, if there is an equation that can determine who will get free lunch, it will look something like:

winner ID = 2n + (something affected by refresh#)           where n = group size

The 2n comes from the fact that winner ID increases by two for every increase in group size if the winner ID is not refreshing. To look for how refresh# affects the stuff inside the bracket, I once again looked for a pattern in the refreshing behavior of winner ID. What I noticed was that the group sizes at which the winner ID gets refreshed at were 1, 2, 4, 8, 16, 32.........For most people, this should already ring a bell that this is a base 2 exponential function. I also noticed, that before winner ID is refreshed, the stuffs inside the bracket is a constant. In fact, I determined previously that the constant inside the bracket take a list of values -1, -3, -7, -15........ which value to take on depends on how many times the winner ID was refreshed. So now, what I am interested in finding is a function whose output is only dependent on which integer power of 2 the input is. The only one I can think of is the ceil(base_2_log(n)). With this function, I can create another function that will give me an output that corresponds to the values in the list [-1, -3, -7, -15........] based on the group size. The function that I came up with is:

1-2^ceil((base_2_log n+1))                          where n = group size

Now, let's confirm whether this function can give me those values in the list. If the group size is 1, then this function will give you -1. If the group size is 2, this function will give you -3. If the group size is 3, this function will STILL give you -3. If the group size is 23 or 29, the function will give you -31. Now we have confirmed that this is the function we want to put inside that bracket to solve for winner ID. The final function that will yield the winner ID is:

                    winner ID = 2n + 1 - 2^ceil((base_2_log n+1))           where n = group size

or to make it sound simpler:

                   number of people in between you and starting person counting counter clockwise

                   = 2n - 1 - 2^ceil((base_2_log n+1))           where n = group size

Thus this concludes my attempt to find a way to get free lunch for whoever lucky enough to have a group of friends who are peculiar as the friends mentioned in the problem. Just make sure you know how many people are in your group, then you can plug that number into this formula, and it will tell you how many people should be in between you and the starting person.

If your friends choose who gets free lunch by counting 3 rather than counting odd, then I can only guess that the final formula look something like:

                    winner ID = 3n + 1 - 3^ceil((base_3_log n+1))           where n = group size

Just to make sure I was right, I plugged in n = 9 into this equation, and I got 1 as the winner ID. Then I simulated the physical scenario on paper for group size 9, and that also showed that f1 will win.

How to be successful in CSC165

If you have being keeping up with all the previous posts that I have made, then you might have started to notice that my posts are getting more and more mundane each passing week. Its not that I am not looking forward to anything amazing, but its that the initial flame I had for CSC165 died down and nothing has fueled that flame. Don't get me wrong, the course is still great, but I just lose interest in things in general after I spend a long time doing it, and CSC165 is no exception.

Since I really got nothing important to talk about, I will just discuss why I think I am successful in this course so far. My current projection is I will get A+ in this course, and my friends and my ability to study "correctly" were the most important factors contributing to this. If you want to do well in the assignments, friend is a MUST HAVE. Not only in this course, but also in other courses, my butt was saved more times than I could count by having friends who I could compare my answer to and discuss methods to solve problems with. 

It is sort of ironic in that I didn't plan to make any friends in this course at the start because I thought I could handle everything the professor threw at me. Before the first assignment was due, I had the opportunity to be acquainted with a fellow student in the course. Initially, we got to know each other through discussing a problem the professor urged the students to try in class (the magic of CSC165 by Prof. Heap). By some weird miracle that seemed like fate, we met again in the tutorial session in the following day, so we hit it off nicely despite it being the first tutorial. Soon afterwards, I got to know several other people in the tutorial, and ever since then we would always compare and discuss the assignments. Without them, my marks in the assignments easily could have being 20% lower than what I had gotten.

I guess the other factor, the ability to study efficiently, is not something everybody has immediate access to. Since I am a 3rd year student, I learned in the first two years what I have to do to survive in University, especially in a brutal University like U of T, where you are competing with over thousands of other brilliant minds. I think a lot of the students in computer science courses make the mistake of thinking that they can understand everything the professor teaches just by attending the lectures. This is actually a really easy mistake to make, because everything in computer science at the beginning is so straight forward, that students forget that there are thousands of different ways that you can twist those fundamental mechanics into something deep and unfamiliar. They don't realize that having an understanding in uncharted territory is just as important as understanding the basics.

I don't have a complicated studying habit for this course. If you have read my previous posts, then you would know that the only thing I do is understanding exactly what the professor was trying to teach in all of his slides, understand the purpose of each slide, and understand how I can use what I learned in those slides to apply to new problems. If you are lucky, then those slides might even contain things that are "deep and unfamiliar" might appear on the exam, and you are the dumbest person in the world if you don't recognize it and prepare for it immediately. You might be wondering, what happens if you encounter the "deep and unfamiliar" on the exam? Well, that is what your thinking brain and mad skill is for.

I guess the last important factor that I forgot to mention that is important for my success is how hard you work. The two factors I mentioned previously is something that you obtain. Once you obtain them, there is not much more you can do to those factors that will further lead you to success. But you can always work harder than how much you work now. Let's say if you spend ten hours doing an assignment, but another you from another dimension spends fifteen hours doing the same assignment, the you from the other dimension will beat you. In that sense, how much work you put on something is unlimited, and if you are willing to put in more work than your competitors, then you will naturally come out to be at the top.

Proof Unit Result

In case you are not a student of U of T taking CSC165, I will say here that the class average for both the proof test and the assignment were REALLY HIGH. The test's average came out to be roughly 80%, which was one of the highest I have seen, and one that I definitely didn't think I would see in a course that is not about life science (because, you know, all the Asian kids go to Life Science). Furthermore, one person whom I talked to about the result of the test got 100%, so maybe the rest of my friends in CSC165 also got 100%? Likely. The average on the assignment, which was roughly 72%, was more reasonable than the test average, but it was still fairly high in my opinion because the more normal average is around the average of the first assignment, which was roughly 65%. What did I get in the end? Well, if I mention it here then I will probably make myself sound like a total arrogant jerk (like I don't sound like one already), so I will refrain from mentioning it here.

For the past week, I was reading the lecture notes so to not fall too far behind from not understanding  what was going on in the actual lectures. This method works for me, because I can understand most, if not everything, just from reading the annotated notes. Occasionally I might have a question or two, but I can always ask the professor or the TAs about them during the tutorial or the help session.

Nothing more significant happened recently.

Latest Test Impression

Well, that last test was so much easier than I had expected! There were no tricks involved in the questions, since they were either previously shown in lectures or we had the chance to do them in the assignment. The one thing that I am glad that DID not come up on the test was the proof of the limit that was done in class, because the logic involved in some of the steps was not apparent. Before the test, I was asking around people outside the test room whether they were also confused, and many of them were. Since there was no limit proofs on the latest test, I believe that it will definitely come up on the final exam, and I caution everybody who is reading this post to actually analyze that proof if you do not already understand it.

Now that is out of the way, I can finally catch up on the lectures on Algorithm Analysis. One thing that I learned from studying for the 2nd midterm was that studying the lectures in CSC165 is not time consuming like other courses. For example, I only spent around 5 hours studying for the 2nd midterm. I think Algorithm Analysis will only be slightly longer to study for because there are more lectures involved, but otherwise the same approach I used to study for the 2nd midterm should also apply here.

From what I have seen in the lectures, Algorithm Analysis is nothing more than calculating the speed of algorithms. All you are doing is counting how many lines of codes a program has to go through based on the size of a list. I will probably spend three hours sometimes this week to catch up on all the lectures that I didn't bother to review.

Upcoming test impression

The second midterm of the course will be next week Friday. Although I didn't pay too much attention in class for the past few weeks, I don't think I am in such a terrible position as to not do well on the test. You see, the professor posts up the annotated version of the lecture notes, and also the course provides the students with a "course note" so students can study off of them and do well on the test without even attending the lectures, theoretically. Of course it helps if you attend the lectures and pay strong attention to the contents of the lectures, but for someone like me who processes information slowly, it is better to digest the information by reading the notes slowly after class.

Even though I haven't started studying for the test, I am already confident about it, because the proof assignment did a great job familiarizing me with proof structures and proof logic. There were six proofs that I had to do and they required me to use a wide variety of proof methods. For example, I had to know how to do direct proof of universally-quantifi ed implication, indirect proof of universally-quantifi ed implication, direct proof of universally-quantifi ed predicate, proof by contradiction, and direct proof structure of the existential (this is actually five of the six methods listed in the course note). So whatever questions the professor throws at me on the test, it is highly likely that each of them will require me to use one of the methods that I am familiar with. The other great thing about the assignment was that it encouraged me to attend the help center where I learned new things about proof writing. The TAs there were great at guiding students like me towards writing a logical proof, but they were also great at pinpointing mistakes that I made in my assignment, which gave me a chance to realize some of my previous misconceptions I had about proof writing.

Although the test is soon, I don't think I will have time to study this until maybe the upcoming Wednesday. But honestly, that is probably enough time for something that I am already confident at. I just got to read up on lecture notes, and ask the professor any questions that I may come up during the course of my reading. The final step will just be doing some proof exercises. Then I will be all set.

Proof is owning me up

I will be honest here, I had completely underestimated the difficulty of doing proofs in this course. I got less than perfect on the latest tutorial quiz that I got back. The quiz was about proof, and I still got less than perfect even though all I had to do was put down the structure of the proof without actually completing it. It was just due to a simple mistake but it was still pretty difficult to accept the reality of the situation. And on the same day, I also couldn't do the proof on another quiz. This time it wasn't the structure, but I had difficulty coming up with the logic behind the proof. Thinking back on it now, it was actually really simple, but the pressure of when I was doing the quiz in combination with my lack of proof practice stopped me from thinking flexibly.

The proof assignment that we obtained is doing relatively well compared to my quizzes. The questions on the assignment are straightforward at first, but they gradually get harder. I might not have mentioned this yet, but I did poorly on the first assignment by my standard and expectation. I am expecting this assignment to be better, however, because not only do you get less questions to do, but also because each question requires lots of effort to be put in unlike the questions from assignment 1. The more effort you put in answering a question, the more understanding you have of it, and the easier it is for you to spot any mistakes.

Right now I am stuck on trying to show that the greatest common factor of m and n, where m is bigger or equal to n, is also the greatest common factor of n and m-n. I have tried a few methods so far and none of them seems to get me what I want, or maybe simply I didn't think far enough with the methods I came up with. Regardless, thinking about the problem is challenging my mind and I enjoy doing that especially since it is a school assignment.