Assignment 2 – Algorithms on Directed
You task is to code a small collection of graph algorithms, based on your
directed_graph class for assignment 1 (all vertices and edges have positive
- Shortest paths.
- Strongly connected components.
- Topological sort.
Besides the above, the class should offer an operation to solve the following
- Consider each vertex as a city, vertex weight as the city’s population, and
the weight of each directed edge as the cost of delivering any amount of
goods from one city to another. Given a city that plans to deliver goods to
all other cities, can you find a way to deliver the goods to every other city
with the minimum average-delivery-cost per person? Your function should
return this minimum cost-per-person.
For example, in the above graph, A and C have the population of 800 and 400,
respectively, and it takes the cost of 900 to deliver any amount of goods from A to
C while there is no way to deliver the good directly from C to A.Suppose A -> B, A -> C, A -> C -> D, A -> B -> E are the paths you use to
deliver goods from A to other cities, your function should return ( cost(A->B) +
cost (A->C) + cost(C->D) + cost(B->E) ) / (the total population of
B,C,D,E) = (600+900+4000+3000)/(300+400+710+221) = 5. Your tasks is to
figure out the minimal return possible by determining the optimal paths for the
delivery. Note that, you can deliver any amout of goods at a fixed cost between
two adjacent cities; therefore, you only need to countcost(A-C) and cost(A->B)
once in this example.
You are provided with the following:
- directed_graph_algorithms.cpp. The four methods present in the
skeleton are the entry point for the tests. As with the first assignment, you
should be able to complete the assignment within the
directed_graph_algorithms.cpp file. You main task is to implement the
four functions, which are not part of the class.
- directed_graph.hpp. Please copy your submission for assignment 1 to
this file. The fully working implementation of a directed graph class in this
file will be reused by directed_graph_algorithms.cpp.
- main.cpp. This is where you can do any testing you like.
The “run” button will compile and execute main.cpp, the “mark” button will run
directed_graph_algorithms.cpp against the tests.
You may modify any of these files as you see fit, e.g., adding extra functions and
extra classes, as long as the tests still execute.
As with assignment 1, this assignment will be marked against three components:
functionality, design and style.
Functionality will be marked exclusively by the tests, and constitutes 17% of the
subject’s total mark.
Design will be marked by your tutor and constitutes 12% of the subject’s total
mark. It does not depend on the functionality of your code. You may be asked
questions by your tutor to help them test your understanding of your code. It will
be marked qualitatively against the following rubric:• Pass The code shows basic understanding of how to employ data
structures to achieve a goal. The design should avoid unnecessary
data structures and should make reasonable use of iteration and recursion
- Credit The design shows a solid understanding of data structures and
demonstrate effective use of control structures to achieve the
- Distinction The design shows a high degree of understanding of how to
use data structures to achieve a goal efficiently, and demonstrate some
evidence that the design does not use unnecessary resources. The design
should be clean and efficient.
- High Distinction The design demonstrates a high degree of understanding
of data structures and how to efficiently employ them to build algorithms
that not only meet technical goals, but support maintenance and future
Style will also be marked by your tutor and constitutes 6% of the subject’s total
mark. It will be marked qualitatively against the following rubric:
- Pass The code mostly uses some formatting standard and is somewhat
- Credit The code adheres well to a formatting standard and variables are
- Distinction At least as well formatted as for Credit standards, along with
sufficient inline commenting to explain the code.
- High Distinction Excellent formatting and variable naming. Excellent,
judiciously employed comments that explain the code without just
repeating the code.
Extra explanations are available at
All being well, assuming you submit before the deadline and attend your Week 12
tutorial (in the class you are actually enrolled in – exceptions will only be made for
cases where attendance at your enrolled tutorial is impossible), we aim to return
the marks for the assignment within a week of the tutorial. The “mark” button will
become available two weeks before the due date, which is Friday 29 May 2020,
to give you some peacetime to focus on your assignment.
SubmissionYou will submit your work with the “mark” button on Ed. No other submissions will
be accepted. You are welcome to develop your code elsewhere, if that suits your
workflow, but remember it must compile and run on Ed. We are using the g++
compiler set to C++17 standard for this assessment. However code that compiles
with clang++ should also work with g++ (unless you’re doing something weird – so
You may submit as many times as you like (in fact, repeated submission is an
expected part of the development process).
Due date: The code submission of this assignment is due by 23:59 pm Sunday
Due date for late submission: A penalty (10% of the assignment’s full mark,
i.e., 3.5 marks) will be applied to code submissions after the due date yet before
23:59 pm Sunday 21/06/2020.
No code submission will be accepted after the due date for late submission.
All code will be checked for student misconduct and plagiarism using specialised
code similarity detection software.