Showing posts with label CLRS. Show all posts
Showing posts with label CLRS. Show all posts

Wednesday, May 16, 2012

Lectures on Algorithms

Although I'm devoted to Knuth, CLRS' Introduction to Algorithms is a good read.

Leiserson (the "L" in CLRS) has his lectures [youtube.com] free online. Caution: skip the first 16 or 17 minutes of the first lecture, it's administrative stuff.

The course website is available [mit.edu] thanks to MIT's OpenCourseWare.

The pseudocode appears a little foreign for neophytes (e.g. writing foo←bar instead of foo=bar for assignment). The assignment pseudocode operator actually remains the same across the board...at least, among theoretical computer scientists.

CLRS fixes their pseudocode conventions in their third edition, however; which was published after these lectures were Youtubed.

A personal quibble: array indices for CLRS begin at 1. This annoys me. But it is a misdemeanor, not a felony.

Also, if you are wondering about the difference between big-O notation and big-Theta notation: suppose some algorithm for a computer were Θ(n), then it is O(n). But not all O(n) algorithms are Θ(n) --- there are some rare instances when this is true.

So Θ(n) gives a more strict criteria than O(n), but in practice it's "ok" to mix up notations (since we usually examine worst-case scenarios anyways!).

Addendum: when is it not ok to make this mistake that [f(n)=Θ(g(n))]==[f(n)=O(g(n))] for some f(n), g(n)?

When f(n)<g(n).

However, if g(n)<f(n)<c*g(n) for every n and for some fixed positive integer c, then [f(n)=Θ(g(n))]==[f(n)=O(g(n))]

So if we study the worst case situations, it's okay to mix up big-O and big-Θ notation. The difference occurs when we study the best-case behaviour (which Leiserson calls "bogus"), and possibly when we study the average-case behaviour.

Punch-line: the big-Θ convention is "stronger" than (i.e., implies) the big-O notation, but big-O notation does not imply big-Θ in general.

For studying worst-case behaviour, they are equivalent.

When studying average-case behaviour, we do not know if they are equivalent (it needs to be proven for each algorithm).

When studying best-case behaviour, you are committing fraud: best-case scenarios are bogus.