HS22

Task 1

Graph Quiz

c) For $|V|=|E|>0$ there is always a simple cycle. Because $|E|=|V|$ there cannot be a tree as $|E|>|V|-1$.

DFS

I am stupid, once again fucked up a simple DFS because I can’t read.

Task 2

d)

DFS pseudo-code error: Make sure to have the DFS start from every still unmarked vertex:

DFS(g):
	all vertices unmarked:
	for u unmarked:
		visit(u)
		
visit(u):
	mark u
	for v adjacent to u:
		....

Task 3 (DP)

Don’t fuck up the extraction. If we do $\forall i\in \{2,\dots ,n\}DP[i-1][a_i]$ is true for all, we need to make sure to put $a_i$ not $s$ like me.

Task 4

a)

DFS runtime is $O(n+m)$ in general. If we know the graph is connected, we can say that the runtime is $O(m)$ as we know $m\ge n-1$ and thus we can simplify out the $n$.