Week 7: Divide and Conquer & Master Theorem

Just as I guessed last week, we did go into further details of Master Theorem. But as I didn't review the lecture notes and the textbook this week, I fount it still hard for me to really understand the Master Theorem. But this time it is the TA that helped me a lot. I asked him about the master theorem after the tutorial, and he really caught my points and make me understand the master theorem in words! I was just confused about those abstract parameters for Master Theorem.

We also studied more on the divide and conquer method. At first I was confused again about the meaning of the term, thinking that it would be something new. But later I just realized that we have already used this method a lot. It just the philosophy of using method like recurrence to divide a big problem into several small problems and solve them separately then recombine the results.

By now, we have practiced a lot on time complicity, and I'm now quite familiar with the terms like upper bounds, big-oh etc,     :)

Practice makes perfect!

The lecture notes for this week is not well organized, thus I decide not to post it.

Week 6 : More Time Complexity, Unwinding and Master Theorem

We covered a lot of things in this week's lecture. But as I've made up the background knowledge that I was missing. I managed to catch up with the pace of the lecture (Again, thanks to Jason and Harry!).

First of all, we discussed more on Time Complexity on trying to calculate the upper bounds of recursive binary search. As we encountered trouble using the method we did to calculate lower bound, we applied another method, which to me is very similar to the former method, but just more tricky.

Then we learned to use Unwinding to analyze questions involving recursive definitions. Since I have done this a lot in my previous school (like analyzing Fibonacci Sequence), this is not hard to me. But I didn't quite catch up with how to prove the recurrence of binary search is non-decreasing. Then I read Lemma 3.6 in the textbook, it explains very clearly.

Later, we were introduced the Master Theorem, I found it really abstract and hard to understand. But since the professor didn't go into much detail, maybe this topic isn't that importan or we may go for the details later.

This week's lecture notes are as follows:

Week 5: Time Complexity & First Test

This week we studied Time Complexity, mainly about the method to estimate how much time a program would take to do a job. This lecture seems to be a disaster to me, because the methods involved some techniques and terms that I had never heard of while all my classmates have learned them in CSC165! I even didn't know what the terms "lower bounds", "upper bounds", "big-oh" and "big-omega" mean! I just tried my best to follow the lecture.

 I do need to thank a lot to two of my new friends Jason and Harry! Jason is my classmate in CSC236, and he taught me about the concepts of those terms after class. Harry sent me some lecture notes of CSC165, so that I can refer to when I found some background knowledge missing. Just as the old Chinese saying goes: "You have to depend on your parents when at home, and you have to depends on your friends when away from home!"

We also had out first term test this week. And it was my first term test in UofT. The difficulty of the term test is appropriate. Again, if you attend all the classed and do some exercises, this won't be a problem.:)

I didn't take much note on this week's lecture, because it was already hard for me to catch up with the pace. But I did set down the meaning of Big-Oh and Big-Omega in my note. :)

Week 4: Structural Induction & Assignment 1

I feel really guilty that I fell asleep during this week's lecture. So I learned this week's material mainly by self study, reading the annotated slides and the textbook.

Through the process of self study, I find a tip that I'd like to share with you guys: read both the annotated slides for Thursday and Friday. I found that the first part of the annotation of Thursday's slides are of higher quality than Wednesday's slides, but the second part is of lower quality than Friday's.

Also, I did talk to someone and made some friends this week -- some other guys who are also from China. I found that it does help if we discuss questions in our mother language, though I know that I need to speak English as more as I can. But this seems to be an issue that I need to balance some time.

What's more, we handed in out first assignment this week. The questions were mainly on proving statements using Simple Induction or Complete Induction, not hard. And I just realized that if I attend all the lectures and tutorials and do some exercises, then the quizzes and assignments won't be a big problem.

At this point, my fear of this course has already gone.  :)

Since I fell asleep during the lecture, I have no notes to post here. :(

Week3: Well Ordering

This week's topic was focused on well-ordering. First of all, the concept of well-ordering was introduced and proved. Then we had some examples on proving some statements using well-ordering.

The concept of well-ordering was new to me. And I was a little bit confused about the concept at the lecture. Though I can understand all the examples, It wasn't clear to me what exactly the concept of well-ordering is. Furthermore, I didn't know for which part of the examples, the principle of well-ordering was applied.

My approach to find out the answer was to read the text book and lecture notes. After doing the reading and looking back at all the examples. I just realized that all I need to remember about the principle of well-ordering is that "Every none empty subset of N has a smallest element." Just that!

Also I wanted to ask some of my classmates. But at that time, I simply didn't know and hadn't talked to anybody. So I realized that maybe the first step that I should do was try to be brave and speak out and make more friends.

This week's tutorial was focused on Complete Induction. Though the questions on the hand out were not hard. I had difficulty to finish the quiz in time, because I wanted to add some creativity and try a new method rather than the one presented by the TA. But later I regretted that I should try my creativity work after class, not during the quiz!

Quiz 1 was returned this week. Though I got full mark, I made a mistake in the predicate.
My predicate looked like this:
P(n): For all n belongs to N, blah blah....
Here I shouldn't use "for all", it made the predicate too strong.

My lecture notes are as follows:

Week2: Complete Induction

Week 2's material was mainly focused on Complete Induction (Or we can call it Structure Induction). This topic was as expected as we discussed about Simple Induction in week 1.

This week's material was also not hard, and it made me feel more confident in this course. But there're still something new and interesting to me that we leaned to apply induction to prove problems with trees. I just learned the tree data type before I came to UofT (we learned to deal with trees using Haskell) and it's fun that we can use induction to analyze trees. Furthermore I leaned a new concept "full binary tree" that every internal nodes of the binary tree has exactly 2 children. And we did an example to prove that every full binary tree, except the zero tree, has an odd number of nodes (I set down the proving process on the second page of my notes).

Also we had our first tutorial and first quiz this week. The tutorial and quiz were practices on Simple Induction. The questions were very relavent to the lecture materials and not hard.

Week1 Introdcution and Simple Induction

The first class of CSC236 was taken on the fourth day that I start to study in UofT (I'm a newly admitted transfer student). Frankly speaking, I was a bit nervous to attend the first class, afraid of missing some basic background information because I didn't take the CSC165 courses. And the course information sheet did scare me because of the marking scheme and the amount of tests and assignments. I didn't expect that the workload would be that heavy. However, fortunately, the first class came as a relief to me. The materials covered in the first class were mainly focused on Simple Induction (we mainly called it Mathematical Induction in high school), which is not hard.
The following is my lecture notes taken to prove some problems:

Sorry for the late starting of my SLOG

Hi all,

I'm really sorry for starting my SLOG this late!
I'll update my SLOG regularly from now on!

Hope to make more friends in the class.

All the best:)

Hengwei Guo (Jerry)