Algorithms & Probability

An engaging illustration of algorithms and probability concepts, featuring graphs, random variables, and mathematical symbols in a vibrant, educational style.

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

14 Questions4 MinutesCreated by AnalyzingTree9

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)

Algorithms & Probability

Algorithms & Probability Quiz

More Quizzes