FS25

Task 1:

a)

6.) We need to use logarithms to reveal a fibonacci like growth. Note that just because a proof by induction fails to bound $a_n\le O(5^n)$, doesn’t mean that this is false. We need a concrete contradiction.

b)

2.) ${\sum }_{i=1}^n{\sum }_{j=1}^{i^2}{\sum }_{k=1}^{j^3}2={\sum }_{i=1}^n{\sum }_{j=1}^{i^2}\Theta (j^3)={\sum }_{i=1}^n\Theta (i^8)=\Theta (n^9)$Remember the technique to get from ${\sum }_{j=1}^{i^2}\Theta (j^3)$ to $\Theta (i^8)$.

c) After $k$ comparisons of SelectionSort, what is the largest guaranteed number of sorted elements.

To find the first sorted element guaranteed, we need $(n-1)\approx n$ comparisons. For the second one we need $(n-2)\approx n$ comparisons. We can therefore upper bound for the amount of comparisons $k$ needed to find $m$ sorted elements with $k\approx m\cdot n$.

If we now fix $k$, we find the number of sorted elements $m\approx \frac{k}{n}\in O(k/n)$.

Task 2

d) How many different MSTs?

We need to check how many edges of the same weight there are that are actually in any MST.

Notice that the edges with weight 9 are not actually in any MST. The only choices we have are the multiple weight 3 edges. For the lower left, we choose 1 of 2 (2 possibilities) and in the upper right 2 of 3 (3 possibilities). Therefore we have $2\cdot 3=6$ different MSTs.

Task 3

a) Dynamic Programming

ii) Recursion We don’t need to check for $s+t+a_i\le k$ in $C_3$ as this recursion is not an “optimality check” but a feasibility check (i.e. we check if $t-a_i\ge 0$ because otherwise that entry doesn’t exist).

iii) Extraction We check all possible entries that are less than $k$, not just the worst case of $M[n,k,k]=true$. In addition, we need to check that $m-s-t\le k$, for all possible $s,t$.

b) MST problem

When you see undirected and minimal cost → MSTs (not dijkstra’s, even though all edge weights are positive).

The solution here is to use extra vertices to enforce the constraints. By adding $0$ edges (guaranteed the smallest), from a start vertex $s$ to all power plants, we enforce the “no factory connected to more than one plant” condition using the no-cycle property of MSTs.

The runtime of setting up the graph is $|V|+|E|$ apparently, so take that into consideration for the runtime justification.

c) BFS layering

Make sure to add the waiting edges to the set of edges.

Make sure to give the start- and end-vertex in the new format $(v_{start},0)$ and $(v_{end},k)$. We can use $k$ as we can just wait at $k$.

Task 4

b)

Make sure to check that the counterexample actually fits the required criteria!!!! A graph with no eulerian cycle cannot disprove a statement requiring that the graph has a eulerian cycle!!!!!!!!

c)

ii) Check proof for logical holes. Arguing that there does not exist an edge $(u,v)\in E$ since $v\notin Q$ only works if $G$ is a cycle. Otherwise we could have $u\to w\to v\to u$ which forms a cycle, with no source.