Tag Info

3

Let's say we want to find primes by certain algorithms (called primality tests) A sound primality test will never say that a number is prime when it is composite (but it may fail to detect some primes as such; it may also sometimes fail to HALT) A complete primality test will never say that a number is composite when it is prime (but it may fail to detect ...

1

Either the car is aware of its initial position (in which case, the problem is easy) or else upon reaching an edge a car with visibility 1 is unable to correctly determine which way to turn. Thus I believe the answer to your question is no.

1

Here is an outline. Consider $k$ copies of the vertices. Call then $V_1, \cdots, V_k$. If $(u,v)$ is an edge, connect $(u_i, v_{i+1})$ for all $i$. Run BF on $s \in V_1$ and $t \in V_k$.

1

We can solve this in expected $O(n/p^2)$ time with a randomized algorithm. Pick two distinct points at random, and see if the line through them passes through at least $p$ fraction of the points. If not, repeat. The check takes $O(n)$ time to visit all the points, and the probability that both of the chosen points are on the line is $p^2$, so we will iterate ...

Only top voted, non community-wiki answers of a minimum length are eligible