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.

WEEK 7

6 weeks have been past, which means we have spent half of semester already. How time flies! And we have already learned so many things; I think it is time for me to have a mid-term review!

What I Learnt

        This week we focused on more complicated proofs: proof by cases. It was not hard to me. I needed to take several situations into account. Just like cutting one problem into pieces and solving them one by one as what I did before. Thus, this was just the further application of the old knowledge, nothing new actually.

Here, I learnt these two parts together with comparison and contrast:

Part A:

To prove, we let k = 7i^2 + 2i in order to connect antecedent and consequence together.

Part B:

To disprove, we use the theorem that the quotient and remainder are unique.

Just find an n^2 equals to 7k+1, and n not equals to 7i+1

          1^2 equals to 7 * 0 +1, and 1 equals to 7 * 0 +1

          6^2 equals to 7 * 5 +1, and 6 not equals to 7i+1

Then we use n = 6

What I Need To Do

    Like what Abhinav Chawla mentioned: ” It made me realize that it's only practice that would help me out to harden my concepts of writing a thorough proof.”(http://abhinavchawlacsc165.blogspot.ca/2014/11/week-7.html) Till now, we have a number of manipulation laws and many different-typed problem needed to solve. I need more practice to familiar them and improve my speed of solving a problem.