WEEK 9

The Term Test 2

I think this time I did a better job than the term test 1. I paid more attention to proper time distribution, and finished all the problems on time. However, I was not sure about the second question’s answer, and I will look at that part more later on. I hope I can get a good mark.

What I Learnt

This week we did more exercise on big-Oh proofs.

When the proof came, all we needed is picking appropriate c and B.

* I got two tips, which were very useful to find c and B:

1)   c should larger than the constant factor of the highest-order term

2)   see what happens when n= 1

Then we could find appropriate c and B.

* When there is more complicated polynomial function in big-Oh, we need appropriate c and B to connect them together, for example:

The Challenging Part

For non-polynomials, we used limit at infinity and L’hopital Law, which were important parts in MAT137. For instance:

Learning this type of proof helped me laid a solid foundation of that part in MAT137, I really appreciate it.

An Interesting Finding

When I read other classmates’ slogs, Albert Xie’s slogs drew me attention, because he added a number of funny pictures and videos into his slogs, which makes the articles more readable and enjoyable. I can improve my slog from learning his. (http://99bugsbutaglitchaintone.blogspot.ca)

WEEK 8

What I Learnt and Difficulties

This week’s material covered the formal definition of O and Ω, and worst-cases analyses of two algorithms.

The formal definition of O and Ω

At the beginning of the lecture, Larry used a vivid example (chicken and turkey) to show us the definition, which successfully drew my attention and helped me understand them in a short time.

Although I had no problem on understanding the formal definition of O and Ω, I could not recite them correctly and always mixed them up, because they were almost the most complicated definitions I have seen.

In order to avoid mixing them up, I decided to only remember the formal definition of O, and the Ω just had the reverse symbol at the last part. I copied the definition on the paper lots of times and read it out loudly, and finally recited it!

Worst-cases analyses of two algorithms

I was really not good at understanding the worst-cases analyses at first, and had no idea about what sigma meant.

But when I typed all the code into Python, and put the code into visualizer to see how it functioned, it made more sense to me. The analysis in Ana’s slog also helped me a lot (http://anadamnjanovic.blogspot.ca/2014/11/week-8.html). I knew we calculated each loop’s running time, and add them together (inner loop first, then the outside loop). And do not forget to add the step “line 1” and “loop guard” in the end.