## What surprised Mark Zuckerberg, at his 2005 Harvard Lecture

Back in 2005 Mark Zuckerberg took a “Computer Science” lecture at Harvard.

He started by talking about some of the strategies that Facebook used to improve its performance, one of them being caching.

After talking for a while he asked the audience for any questions. To his surprise there weren’t any technical questions as such. Well anyone will be surprised I guess. After answering a few questions he finally commented “No CS Questions”.

Watch this clip, which is quite funny !

## Traversing a Graph using Depth First Traversal

Earlier we have seen how to build a simple Graph using Adjacency List and how to traverse it using breadth first traversal. The Graph which was used is presented below.

Building on that we are going to see how to traverse that Graph using another popular approach known as “depth first traversal”, or DFT. This video acts as a supplement to this article.

At the end of this Post I have presented code written in C to show you how can DFS be implemented. After all we should be able to write the code and not just talk about the approach.

A popular application of depth first traversal is to do Topological Sorting or Ordering.

Understanding DFT

In DFT we pick a vertex to start with. In our example friendship graph we start with Ankur. We visit this and mark it as visited.

Next we explore the adjacent vertices to this vertex, like Reena. But we don’t explore the next adjacent vertex to Ankur i.e. Dikshit, instead we explore further and visit Nidhi, who is connected to Reena. So what we are doing is traversing the depths till we reach a leaf or a node that has been visited. Then we backtrack and start exploring the next adjacent node i.e. Dikshit.

Doesn’t this sound recursive? It is and as you will see our code makes use of recursion to perform DFT.