user avatar
user avatar
user avatar
Louis
  • Member for 10 years, 4 months
  • Last seen more than a month ago
17 votes

How can we assume that basic operations on numbers take constant time?

14 votes

How to prove that a language is not regular?

12 votes
Accepted

Randomized Selection

8 votes
Accepted

Quicksort vs. insertion sort on linked list: performance

8 votes

HALF CLIQUE - NP Complete Problem

8 votes

Complexity of an optimisation problem in 3D

7 votes

P-Completeness and Parallel Computation

7 votes
Accepted

Chernoff bounds and Monte Carlo algorithms

7 votes

Can PRNGs be used to magically compress stuff?

6 votes

How do O and Ω relate to worst and best case?

6 votes

Convex Hull algorithm - why it can't be computed using only comparisons

6 votes
Accepted

Turing-unrecognizable language - what TM does?

6 votes
Accepted

Rectangle Coverage by Sweep Line

5 votes

Proving a specific language is regular

5 votes

Complexity of finding the largest $m$ numbers in an array of size $n$

5 votes

Loop invariant for an algorithm

5 votes

For what kind of data are hash table operations O(1)?

5 votes

Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?

5 votes
Accepted

Amplifying the correctness of $\mathsf{RP}$ algorithms using expander graphs

5 votes
Accepted

Why is the set of NFA that accept all words in co-NPSPACE?

5 votes
Accepted

Can't understand why the DP Subset Sum algorithm is not polynomial

5 votes
Accepted

Edges in and out of cycles and their relation to connectivity of the graph

5 votes

Chernoff bound when we only have upper bound of expectation

4 votes
Accepted

Randomized Meldable Heap - Expected Height

4 votes

C++ Strings vs. Character Arrays

3 votes

Proof that the existence of a Hamilton Path in a bipartite graph is NP-complete

3 votes

Short and slick proof of the strong duality theorem for linear programming

3 votes

Using Pumping Lemma to prove language $L = \{(01)^m 2^m \mid m \ge0\}$ is not regular

3 votes

MST with half the edges the maximum weight

3 votes

What is the point of (Compactness theorem in the) Overspill principle?