Tutorial 7
------------

1. Floyd Warshall based APSP -- all 8 steps, start with the definition of the recursive problem (assuming that vertices are labelled using integers {1,2,... , n}.
A(u,v,w) = length of the shortest path from u to v such that all intermediate vertices (except u,v) on the path is from the vertices {1, ... , w}.

2. DP for longest path in a DAG:
LP(u,k) = length of the longest loop-free path to u using at most k edges

3. Show how to solve a 3k-path problem by reducing it to a graph problem.
Suppose you are given a directed graph G and two vertices s and t. Design and analyse an algorithm to determine if there is a walk/path in G=(V,E) from s to t (possibly repeating vertices and/or edges) whose length (number of edges) is divisible by 3.

4. Prove that: If v has the largest post value in a graph, then v must belong to a source SCC.

5*. Show how to solve LIS by reducing it to a graph problem.
Hint: Construct a graph 1,…n where (𝑖,𝑗) is an edge if 𝑖 < 𝑗 and 𝑥𝑖 < xj.