Posted by: atri | October 11, 2010

Lect 18: Analyzing BFS

In today’s lecture, we implemented BFS and showed that it run in time O(m+n). The slides have been uploaded.

The rest of Section 3.3 and Sections 3.4 and 3.5 are reading assignments. Next lecture, we will wrap up our discussion on the BFS implementation and start talking about topological sorting of directed graphs. The latter is from Section 3.6 in the book.

I think I went faster than usual today and it seemed to work OK. If you feel like it, you can give your feedback via the poll below:

I am also mulling over “hosting” the student blog posts on a separate blog. If I decide to do so, I will put links to the posts from my posts on each lecture. If you feel like it, you can give you feedback via the poll below:

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: