Course week 10

Self-study

The topics for this week are the following: (i) Graphs (ii) Breadth first search, (iii) Depth first search, (iv) Implementing a graph in C++

The following links will take you to the video-lectures and the accompanying slides:

Graphs and Trees

This is the same lecture as in week 7. It is included here since there are questions about graphs.

Implementing graphs in C++

Which of the following statements are true? (More than 1 statement may be true.)
Which of the following statements are true regarding connected graphs? (More than 1 statement may be true.)
Given a directed graph, in which of the following situations would a breadth first search (BFS) be useful?
Suppose a directed graph has 4 nodes \(s\), \(a\), \(b\) and \(c\). Suppose in addition the graph has all possible edges except 2: the edge from \(s\) to \(a\) and the edge from \(a\) to \(b\). What are the distances from \(s\) to each of the other nodes?
Suppose a BFS algorithm starts from node \(s\). Suppose \(x\) is some other node and a path from \(s\) to \(x\) exists. Why does the BFS algorithm assign different colors to \(x\)?
Suppose a directed graph is input to a BFS algorithm. In addition suppose that BFS starts from node \(s\) and that a path from \(s\) to each other node exists. When BFS has finished executing, which of the following are true? (Note: more than one statement might be true.)
Given a directed graph, in which of the following situations would a depth first search (DFS) be useful?
In the DFS algorithm a stack is used. Suppose \(x\) and \(y\) are two different nodes in a directed graph. According to what rule does the DFS stack operate?
Suppose we are storing a graph in C++ and we have a node struct, in which we store all the adjacent nodes in either a vector container or an unordered_set container. In what situtation would it make sense to prefer an unordered_set over a vector?
When implementing a graph in C++, which of the following is true?
What is a central question, related to this course, whose answer can be found in this week’s videos?
Of the following topics, which do you think deserves further discussion/explanation during the weekly consultation session?
Were there any parts of the video lectures that were particularly difficult? Particularly interesting? Something about which you wish to learn more?

Extra links on the topic:

Week10 - Glossary

Submit weekly exercises

Questions to be submitted this week