The readings for Monday, November 14 are:
Data Structures and Other Objects Using C++:
Data Structures & Algorithm Analysis
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.
Once you have completed the readings, answer the following questions in the
reading10/README.md
file in your assignments repository:
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?
Given a graph, is it possible to have more than one:
B. Single-Source Shortest Path?
Briefly explain why or why not.
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)
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.
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 reading10 # Create reading10 branch ... # Do your work $ git commit # Commit your work (can do this multiple times) $ git push -u origin reading10 # Push branch to GitLab