Algorithm Analysis

Note: This post covers Week 7.

Finally! Some actual more typical computer science material!

We started off the lecture by discussing proofs by cases (useful for proofs involving absolute values or different cases when a variable is odd or even) and then reviewed all the proof structures we had done so far. This was a good synopsis to copy down for the exam aid sheet, Then we moved on to "Algorithm Analysis and Asymptotic Notation."

Prof. Zhang lectured about running time, juxtaposing merge sort (which operates in n log(n) time) and bubble sort (which operates in quadratic time) as an example. Since only the asymptotic behaviour of algorithms is of interest, which is to say only their behaviour as input sizes get very large, we learned that we can place algorithms into separate classes depending on their rate of growth. Thus big-Oh notation was introduced.

Proofs, Proofs and More Proofs

Note: This entry combines both Weeks 5 & 6

Midterm week! This test was fairly easy, as a few minutes spent practicing with last years test would leave you well prepared. We also finished up assignment 1 this week. It was more challenging than any of the other course material, but quite doable in a few hours.

Prof. Zhang started off Week 5's lecture proving how "if you did bad, then it is not bad" which was an entertaining example of a direct proof. We learned several new proof techniques, such as proof by contrapositive (when P => is too hard, try not Q => not P), proof by contradiction (assume not Q and arrive at a contradiction, thereby proving the contrapositive) and how to prove sequences. This was a much more challenging class than the previous ones, and it takes a while to get used to proofs. It's confusing at first when you don't know how to start, but I guess that's just something that goes away with practice.

Week 6 was spent building on what was learned in the previous week and providing us with examples of how to prove non-boolean operators (ie: "floor"), disprove statements (prove the negation), and prove limits

Proofs using the floor function were fairly difficult to do because we had to mold the definition to suit our purposes as opposed to simply applying memorized laws. This was a major part of assignment 2 and one of the hardest parts of the course up till now. Delta epsilon limit proofs were fairly straightforward because I had already learned them in calculus, but we encountered more difficult instances on the assignment.

This was an interesting two weeks learning the basics of proofs and I'm interested to see how we'll apply these techniques to more technical computer science scenarios.

Problem Solving Exercise

I will be using Polya's method to attempt to solve the problem depicted here.

Understand the Problem

The problem at hand is to predict whether creases on a repeatedly folded paper will be hill or valleys.

Devise a Plan

I will try to fold the paper and record the pattern of hills/valleys after each successive fold, in an attempt to uncover a pattern.

Carry Out the Plan

Folds | Hills | Valleys

   1         0           1

   2         1           3

   3         3           8

   4         8          14

It seems to be the number of valleys is the same as the number of hills for the next fold. I can't figure our another pattern after that thought...

Look Back

I tried one method, perhaps I should try again because I don't see a pattern.

Acknowledge When and How You're Stuck

I don't really see a pattern so I'm quite lost...

Finishing up the "Language of Math"

Note: This post covers Week 4

We added to bi-implications and transitivity to our mathematical toolbox this week, and mixed it up with multiple quantifiers. It was a fairly easy lecture, but a good opportunity to practice using the various predicate laws we learned last week (ie: distributive, DeMorgan's).

We started proofs this week. First we were presented with an example limit proof, which was pretty straightforward because it had already been covered in MAT137 (but too déjà vu...bad memories). My friend Isobel is absolutely right here when she writes that taking 137 is very useful for this course, it made this lesson so much easier than if it were the first time I were exposed to these ideas. We were also introduced to the indented Python-like proof structure that is very different (much more organized and symbolic-heavy) from that used in calculus.