FS24

Task 1: Theory

Asymptotic

for a.4.) forgot to plug in the $\frac{\sqrt{(}n)}{2}$ into the $\sqrt{i}$ term.

Graph Quiz

b) If an edge is not a cut edge in a connected graph it’s part of a cycle.

e) Number of spanning trees for a graph with $n$ vertices is $n^{n-2}$ according to Cayley’s Formula.

BFS/DFS

Don’t connect a vertex twice in a BFS tree, just don’t. Don’t take shortcuts, just do it precisely.

Task 2: Theory

a)

2.) Counting Iterations ii) notice the bounds, from $i$ to $2i$ is $i+1$ iterations, not $i$. Check for $i=2$ for example: $2,3,4$ is 3 not 2. This is like from $0$ to $i$ vs. $1$ to $i$.

Code Expert

Graphs

For Bellman-Ford make sure to test for infinite distance before updating, as negative weight edges can bring Infinity - 5 < Infinity in Java.

DP

DP is hard. Make sure to work out a recursion that actually makes sense in your head. Here, instead of thinking about specific positions and partitions and start-end indices, think more general.

The correct definition of table entries here was: D[i][j] = maximum number of matching indices if [A[0], ..., A[i]] is mapped to [B[0], ..., B[j]] The recursion then gives you: D[i][j] = max_{k <= i} D[k - 1][j - 1] + 1 if {A[k] + ... + A[i] == B[j]}

To remove one of the for-loops, you can use prefix sums to calculate the sum A[i..j] = prefix[j] - prefix[i].