Task 2
e) Toposort?
Give a directed cycle as a counter-argument!
Task 3
b) Graph Modelling
Be sure to fucking read the instructions you stupid idiot! If they say output “IMPOSSIBLE” if there is no suitable vertex, make sure the algorithm that extracts the solution includes this case!
d) DFS
just use the basic dfs template and then make sure to correctly use true/false values and or operators. Runtime is easily proven from memorised DFS runtime.
Task 4 Proofs
c) MST proof
We can just define an entire such that instead of swapping only a single vertex. This leads to a cleaner proof. Just assume broader things, take the easier way!