Posted by: atri | September 29, 2010

Lect 13: Graph Basics

In today’s lecture, we covered some basic graph definitions including undirected/directed graphs, paths, cycles and connectivity. The slides have been uploaded.

Next lecture, we will finish up some remaining definition and then talk about trees. Time permitting, we will start talking about algorithms for checking connectivity. The material will be from Sections 3.1 and 3.2 in the book.



  1. In the beginning of class I recall you saying something about posting a sort of walk through for finding Big Omega, but I don’t see it anywhere. Although its entirely possible that I misheard you.

    • Hi Anthony,

      I’ll be talking about the proving Omega lower bound on running time in the online office hours. So you can either join in or look through the transcript later on. The details on the online office hours are here.

Leave a Reply

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

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

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s


%d bloggers like this: