The readings for Monday, November 7 are:
Data Structures and Other Objects Using C++:
If you do not have the primary textbook, you can use the following free alternative texts instead:
Data Structures & Algorithm Analysis
The focus of the reading is graphs, specifically adjacency list and adjacency matrix representation, and depth-first search and breadth-first search traversal.
Once you have completed the readings, answer the following questions in the
reading09/README.md
file in your assignments repository:
Briefly explain what it means for a graph to be:
A. Connected?
B. Acyclic?
C. Directed?
D. Simple?
E. Weighted?
Given the following graphs:
A. Provide the adjacency matrix and the adjacency list for each
graph. For instance, Graph 0
would have the following adjacency matrix
and adjacency list:
Graph 0 - Adjacency Matrix Graph 0 - Adjacency List A B C A: 0 1 1 A: B C B: 0 0 0 B: C: 0 1 0 C: B
B. What is a reason for using an adjacency matrix instead of an adjacency list to represent a graph?
C. Conversely, what is a reason for using an adjacency list instead of an adjacency matrix to represent a graph?
Given the following non-recursive implementation of depth-first search:
struct Graph { map<string, set<string>> adj; // Adjacency List/Set }; void traversal(Graph &g, const string &s) { stack<string> q; set<string> v; // TODO while (!q.empty()) { // TODO } }
A. Complete the implementation of depth-first search by filling in the
TODO
sections with the appropriate C++ code. Remember to:
Print out each node you visit.
Visit each node exactly once.
B. What is the purpose of stack<string> q
?
C. What is the purpose of set<string> v
?
D. What would we need to change in the function to perform a breadth-first search instead of depth-first search?
To submit your solution, you must initiate a Merge Request in your private assignments repository and assign it to the appropriate TA from the Reading 09 - TA assignment list.
To facility the Merge Request workflow, you must do your development in its own branch:
$ cd path/to/repo # Go to your repository $ git checkout master # Make sure we are on master branch first $ git pull # Make sure we have changes from GitLab $ git checkout -b reading09 # Create reading09 branch ... # Do your work $ git commit # Commit your work (can do this multiple times) $ git push -u origin reading09 # Push branch to GitLab