General

Read!

Read the exercise again to make sure the instructions have been followed:

• edge cases
• proper output format

Task 1 Theory

Asymptotic growth

Common mistakes:

• $2^{(n^2)}\ne {2^n}^2=2^{2n}$ this is very wrong!
• Showing the right thing then misinterpreting: show $\frac{f(n)}{g(n)}\to \infty$ thus false, when we wanted to show $\ge \Theta (g(n))$ and thus it’s correct.

Recursion Asymptotic growth

Assume $a_1=1$ and $a_n=3a_{n-1}+1$ for $n\ge 2$. Prove $a_n\le O(4^n)$. We can use induction to prove exercises like these.

B.C.: For $n=1$, we have $a_1=1<4^1$. I.H.: We assume $a_n\le c\cdot 4^n$ for some $n\ge 1$. I.S.: $a_{n+1}=3\cdot a_n+1\le 3c\cdot 4^n+1$ Which means $a_{n+1}\le 3c\cdot 4^n+1$ which is smaller than $4c\cdot 4^n+1$ which is smaller than $c{4}^{n+1}+1$ and thus our recursion works.

Asymptotic trick

Series Trick: Given $T=7^1+7^2+\cdots +7^n$ we can do $7T-T=7^{n+1}-7^1$ then factor out for $T(7-1)=....$ and divide to get $T=\frac{7^{n+1}-7^1}{6}$.

Integral Trick: Simply integrate the sum (for example ${\sum }_{i=1}^n{i}^{3.5}$) you have to get an asymptotic bound.

While Loop to for Loop

For a while loop like this:

j = 1
while j <= n do
	j = 2j
	f()

the runtime is not ${\sum }_{j=1}^{\lfloor {\log }_{2}n\rfloor }$ but instead ${\sum }_{j=0}^{\lfloor {\log }_{2}n\rfloor }$. We go from $0$ to $\lfloor {\log }_{2}n\rfloor$ not from $1$.

Theory Runtime for Graphs

Building Graph

Building the graph takes $O(|V|+|E|)$ time. We give $|E|\le a\cdot b+b\cdot (b-1)$ in the case of an undirected graph with two vertex sets, one of size $a$ and another of size $b$: $|V|=a+b$. The set $a$ is not connected, there are only edges from all $a\to b$ ($a\cdot b$ edges) and then set $b$ is connected (fully connected at most) thus $b\to b\sim b\cdot (b-1)$ as each is linked to all others. Thus the total runtime is $O(a+b+a\cdot b+b\cdot (b-1))=O(a\cdot b+b\cdot (b-1))$ $=O(b(a+b)$.

Running the Algorithm

The algorithms we have are given in relation to $|V|$ and $|E|$ which means that Prim’s on a connected graph for example like here takes $O(|V|\log |E|)$ which in our previous case would come out to $O(b(a+b)\log (a+b))$.

Extracting Solution

Extracting the solution can be reading off a distance from an array in $O(1)$. In our case it’s $O(b(a+b))$ as we iterate over all edges to compare them and filter out edges in $a$.

Theory Pseudocode

DFS Pseudocode

Make sure to not forget to include a for loop over all vertices that are unmarked if we are not sure the graph is connected.

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

Otherwise, we aren’t checking the vertices that aren’t in the ZHK of our chosen start node.

DP Tasks

Recursion

Make sure not to forget the $+1$ or whatever is needed in the case where we successfully gain something.

Calculation Order

Give the calculation order as a for loop, like so:

for i \in {1, ..., n}:
	for j \in {i + 1, ..., n}:
		compute DP[i][j]

Runtime

Explicitly state the runtime for the calculation of an entry: “Calculating the entry takes $O(i)$ time, which we can upper bound by $O(n)$ since $i\le n$.” Then the number of entries: “We have $O(n^2)$ entries” Then the total runtime: “Thus the total runtime is $O(n^3)$.”

Code Expert

Shortest Path

The solution can sometimes be to set the distance of not only the start vertex, but “all start vertices” to 0, instead of using ASSP algorithms.

DFS vs. BFS

Use DFS when we want to find a toposort or something, BFS when we need shortest paths in an unweighted!!!

BFS Implementation

Note that for BFS we set visited to true before/after we add it to the queue, not once we pop it!!!

Queue<Integer> Q = new LinkedList<>();
Q.add(s);
 
int[] dist = new int[n];
dist[s] = 0;
boolean[] visited = new boolean[n];
visited[s] = true;
 
int reached = 0;
 
while (Q.size() > 0) {
  s = Q.remove();
  
  for (int i = 0; i < E.get(s).size(); i++) {
	int u = E.get(s).get(i);
	
	if (T[u] > dist[s] && !visited[u]) {
	  dist[u] = dist[s] + 1; // And set the distance her
	  Q.add(u);
	  visited[u] = true; // NOTE: We set visited to true here
	  reached++;
	}
  }
  
}
 
return reached + 1;