The readings for Monday, November 14 are:

1. Data Structures and Other Objects Using C++:

• 15.4
2. Data Structures & Algorithm Analysis

• 11.4 - 11.5
3. Algorithms

#### TL;DR

The focus of the reading is graph algorithms, specifically Kahn's Algorithm for topological sorting, Dijkstra's Algorithm for single-source shortest path and Prim's Algorithm for computing a minimum spanning tree.

## Questions

Once you have completed the readings, answer the following questions in the `reading10/README.md` file in your assignments repository:

1. What exactly is:

A. A Topological Sorting? What is a real world application of this?

B. A Single-Source Shortest Path? What is a real world application of this?

C. A Minimum Spanning Tree? What is a real world application of this?

2. Given a graph, is it possible to have more than one:

Briefly explain why or why not.

3. For each of the following graphs:

A. Use Kahn's Algorithm to compute a topological sort of the nodes.

For instance, `Graph 0` could have the following topological sorting:

```A, C, B, E, D, F
```

B. Use Dijkstra's Algorithm to compute the shortest path from `A` to every other node.

For instance, `Graph 0` could have the following spanning tree:

```(A, C)
(C, B)
(C, E)
(D, F)
(E, D)
```

C. Use Prim's Algorithm to compute the minimum spanning tree (assume the edges are undirected).

For instance, `Graph 0` could have the following minimum spanning tree:

```(A, C)
(B, C)
(C, E)
(D, E)
(D, F)
```

## Submission

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 10 - TA assignment list.

#### Development Branch

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