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.
Interesting use of big-Oh notation to sort algorithms into classes. That could be a useful idea for future coding projects.
ReplyDelete