Posted by: atri | September 14, 2012

Lect 8: What is an Efficient algorithm?

In today’s lecture, we finished proving the correctness of the Gale-Shapley algorithm and then we discussed what our notion of an efficient algorithm is. A lot of reading material was assigned today: Sections 1.1, 1.2, 2.1, 2.2 and 2.4 in the textbook. Since you guys have seen asymptotic notation before, I am going to do a quick review on Wednesday (remember we are off on Monday due to Rosh Hashanah) and Zihe will cover the material in more detail in her recitations next week (but remember no recitation on Monday either). So I will mostly talk about Sec 2.2 in the book and talk a bit about what it means to say that the run time of an algorithm is e.g. O(n^2) or is e.g. \Omega(n^2). In particular, I plan to go through the run time analysis of a simple algorithm.

The slides for todays’ lecture have been uploaded.

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s

Categories

%d bloggers like this: