Algorithms & Probability
Algorithms & Probability Quiz
Test your knowledge in Algorithms and Probability with our engaging quiz designed for enthusiasts and learners alike! Challenge yourself and see how well you understand fundamental concepts in computer science and mathematics.
- 15 thought-provoking questions
- Focus on algorithms, graph theory, probabilistic methods, and more
- Get instant feedback on your answers
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.
{"name":"Algorithms & Probability", "url":"https://www.quiz-maker.com/QPREVIEW","txt":"Test your knowledge in Algorithms and Probability with our engaging quiz designed for enthusiasts and learners alike! Challenge yourself and see how well you understand fundamental concepts in computer science and mathematics.15 thought-provoking questionsFocus on algorithms, graph theory, probabilistic methods, and moreGet instant feedback on your answers","img":"https:/images/course3.png"}