Algorithmic Combinatorics

Winter 2018-19

FU Berlin, Mathematics and Informatics


Week 2 Quiz

Use this quiz to test your knowledge and understanding of this week's lectures.

Question 1

Consider a graph \(G\) on vertex set \( [5] \), where the weight \( w_{i,j} \) on the edge from \( i \) to \(j \), if present, is given in the matrix below. How many edges are on the lightest path from vertex \(2 \) to vertex \(5 \)?

\( W = ( w_{i,j} )_{i,j} = \begin{pmatrix} - & 5 & 2 & - & 6 \\ 5 & - & 4 & 2 & - \\ 2 & 4 & - & 1 & 7 \\ - & 2 & 1 & - & 9 \\ 6 & - & 7 & 9 & - \end{pmatrix} \).

Question 2

If we modify Dijkstra's algorithm to keep track of all lightest paths, then, compared to recording a single lightest path, we need

Question 3

A decision problem in \( NP \) might not have a polynomial-time algorithm because

Question 4

In order to show that a decision problem \( Q \) is \(NP\)-hard, it suffices to

Question 5

Suppose we use an \(\alpha\)-approximation algorithm to solve a minimisation problem, and get some result \(R\). What is the narrowest interval in which we can deduce the true minimum \(MIN\) lies?




Submit Reset

 

 

Return to top