Posted by: atri | September 28, 2012

Lect 12: Trees

Today we proved that a tree with n nodes has exactly n-1 edges. We then started with designing an algorithm to decide whether two given vertices are connected or not. This material is from Section 3.1 and 3.2 in the book. Next lecture, we are going to formally state the Breath First search and prove some interesting properties about the algorithm (and its correctness).

The slides and notes for the lecture have been uploaded.

Here is the link to sign up mock interviews that Andy talked about at the beginning of the lecture.

Also I did not get around to defining (connected) component in class today. It is needed for the first question on HW 4: please go ahead and read up the definition from the book. In short here is the definition: given a graph G=(V,E), a subset S\subseteq V is called a connected component if the following are true

  1. For any two vertices u,w\in S, u and w are connected; and
  2. For any vertices u\in S and x\in V\setminus S, u and x are not connected.

In the news caster graph that we have seen in the slides, there are two connected components: one with the American newscasters and the other with the Indian newscasters.

If you have any questions, please post them on piazza.



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: