Algorithms & Probability

Computing the shortest path between any two nodes in a graph, in the general case, is known to be NP-complete.
True
False
If S:={X_1, ..., X_n} are independent random variables, then any non-empty subset of S contains independent random variables.
True
False
In class you have discussed Cristofides' Algorithm. The algorithm gives a 1.5 approximation for the Traveling Salesman Problem.
True
False
There exist not only Monte Carlo and Las Vegas algorithms, but also a class called Atlantic City Algorithms. Which of the following can be considered an Atlantic City Algorithm?
Running a parallelized version of target shooting on a cluster for more than a day.
Returning a random answer.
Running a Las Vegas algorithm for 0.1 seconds and then checking the answer (if available) with a polynomial time Monte Carlo checker.
A randomized algorithm where a human checks the answer by hand.
Randomized QuickSort is a...
Monte Carlo Algorithm
Las Vegas Algorithm
Atlantic City Algorithm
All of them
Increasing the number of samples in Target-Shooting helps in...
Reducing the bias
Reducing the variance
Reducing the noise
When you can NOT use the linearity of the expectation for the random variables X_1, ..., X_n?
You can always use the linearity of expectation.
If the random variables are not independent.
If the expectation of at least one of the random variables X_1, ..., X_n is not defined.
Which of the following holds?
Any maximum (inklusionsmaximual) matching is also maximal (kardinalitätsmaximal).
Any maximal (kardinalitätsmaximal) matching is also a maximum (inklusionsmaximual) matching.
Both
What was the relationship between the mathematicians Chebyshev and Markov, the proposers of the respective inequality?
Twins
Teacher-Student
Lovers
They didn't know each other
We say that a graph G is planar if...
Its vertex set V can be partitioned into two disjoint sets V_1 and V_2 such that every edge in the graph connects a vertex in V_1 and a vertex in V_2.
It contains a subset of vertices with at least n/2 elements such that every two distinct vertices in are adjacent.
There exist a path that visits each node exactly once.
It can be drawn on the plane in such a way that its edges intersect only at their endpoints.
In the exercise class, we have discussed bootstrapping for the Min-Cut problem. This gives a limit algorithm that computer the correct answer with arbitrarily large constant probability in time...
O(n^3)
O(n^2log n)
O(n^2)
Which of the following was mentioned in class to be an NP-complete class of problems?
Classic Nintendo Games
The Cemetery Map of Indiana Jones and the Kingdom of the Crystal Skull.
Determining the optimal chess move in the general case.
Determining whether the sorting hat of Harry Potter has done the correct choice.
How many rounds do we need to wait, in expectation, to complete a collection of $n$ elements if the process satisfies the assumption of the Coupon collector problem?
O(nlogn)
O(n)
O(H_n)
The algorithm by Mucha and Sankowski for matrix multiplication of $n\times n$ matrices has runtime...
O(n^3)
O(n^(2.8074))
O(n^(2.373))
O(n^2)
0
{"name":"Algorithms & Probability", "url":"https://www.quiz-maker.com/QW1VYXRCK","txt":"Computing the shortest path between any two nodes in a graph, in the general case, is known to be NP-complete., If S:={X_1, ..., X_n} are independent random variables, then any non-empty subset of S contains independent random variables., In class you have discussed Cristofides' Algorithm. The algorithm gives a 1.5 approximation for the Traveling Salesman Problem.","img":"https://www.quiz-maker.com/3012/images/ogquiz.png"}