Lab 2

Due Oct 13, 2020 by 10am
Points 9
Submitting a text entry box
Available after Sep 16, 2020 at 6pm

Submit the following, as a group (it is sufficient that only one of you make the submission):

A list of which problems you have solved, with links to the corresponding Kattis submissions.
A short statement of who did what.

(Getting Accepted on Kattis is a necessary but not sufficient condition for passing a lab task. Before starting, read the General Lab Instructions for more details)

Hint: in C++ in particular but also Java it is useful to use iterators to represent vectors/sets/etc. For an example of this for the longest increasing subsequence task below, see here. An advantage of this approach is that the function does not require the input to be stored in some specific container type, you can use arrays, vector, list, or whatever other container type has the operations needed in the function.

Note that the API suggestions below are to be interpreted as pseudo code, you should translate them to your favorite language as you see fit.

Required time complexity means that your algorithm should have this time complexity. In some cases it might be possible to pass the Kattis tests with a slower algorithm, but if you do so, you might still get points deducted when presenting your labs.

Single Source Shortest Paths

Task 2.1: Non-negative weights (1p)

Implement Dijkstra's algorithm for finding the shortest path from a vertex to all other vertices of a graph with non-negative edge weights.

Kattis will only ask for the length of the shortest path, but your solution must also be able to construct paths.

API suggestion:
distance/parent[] shortest_path(graph G, node start)

Problem ID on Kattis Links to an external site.: shortestpath1 Links to an external site..

Task 2.2: Time-table search (1p)

Add support to your Dijkstra implementation to handle time table graphs, where each edge can only be used at certain specific time steps.

It is OK if you do this separately from the basic Dijkstra implementation.

Kattis will only ask for the length of the shortest path, but your solution must also be able to construct paths.

API suggestion:

distance/parent[] shortest_path(graph G, node start)

Problem ID on Kattis Links to an external site.: shortestpath2 Links to an external site..

Task 2.3: Negative Weights (1p)

Implement the Bellman-Ford algorithm for finding the shortest path from a source vertex to all vertices in a graph where edge weights are allowed to be negative.

Kattis will only ask for the length of the shortest path, but your solution must also be able to construct paths.

API Suggestion:
distance/parent[] shortest_path(graph G, node start)

Problem ID on Kattis Links to an external site.: shortestpath3 Links to an external site..

All Pairs Shortest Paths

Task 2.4 (1p)

Implement the Floyd-Warshall algorithm for finding the shortest distance between all pairs of nodes in a graph with edge weights.

API suggestion:
distance[][] shortest_path_all_pairs(graph G)

Problem ID on Kattis Links to an external site.: allpairspath Links to an external site..

Spanning Trees

Task 2.5: Minimal Spanning Tree (1p)

Implement some algorithm for finding a minimal spanning tree in a graph, provided one exists.

API suggestion:
tree mst(graph G)

Required time complexity: O( (|E|+|V|)·log(|V|) ).

Problem ID on Kattis Links to an external site.: minspantree Links to an external site..

Flows and Cuts

Task 2.6: Maximum Flow (1p)

Implement an algorithm to find a maximum s-t flow in a flow network.

API suggestion:
graph max_flow(graph G, vertex s, vertex t)

Problem ID on Kattis Links to an external site.: maxflow Links to an external site..

Note: Those of you who have taken the "ADK" course will probably be able to make use of the maxflow lab from that course -- perhaps just as an inspiration source, or perhaps as a pretty much complete solution that just needs some dusting off.

Task 2.7: Minimum Cut (1p)

You get the same input as in the max-flow problem, but need to find a subset U of the vertices V such that s belongs to U but t belongs to V\U and the sum of capacities of edges from U to V\U is minimized.

API suggestion:
vertex_set min_cut(graph G, vertex s, vertex t)

Problem ID on Kattis Links to an external site.: mincut Links to an external site..

Task 2.8: Minimum Cost Maximum Flow (1p)

The minimum cost maximum flow is a generalization of maximum flow, where the edges have costs (in addition to capacities). Like in the original problem, the goal is to find a flow of maximum size, but subject to this constraint, you also want the total cost of the flow to be minimized.

The cost of a flow through a specific edge is the amount of flow through the edge, multiplied by the cost of the edge. The cost of a flow in the graph is the sum of the costs of the flows through each edge.

Implement an algorithm to find a minimum cost maximum flow in a flow network with edge costs.

Kattis will only ask for the size of the maximum flow and the value of the minimum cost, but your solution must also solve the problem of constructing the actual flow.

API suggestion:
graph max_flow(graph G, vertex s, vertex t)

Problem ID on Kattis Links to an external site.: mincostmaxflow Links to an external site..