User Louis

18 votes

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

answered May 3, 2012 at 12:06

15 votes

How to prove that a language is not regular?

answered Apr 4, 2012 at 14:06

12 votes

Accepted

Randomized Selection

answered Apr 18, 2012 at 15:25

8 votes

Accepted

Quicksort vs. insertion sort on linked list: performance

answered Apr 20, 2012 at 10:43

8 votes

HALF CLIQUE - NP Complete Problem

answered Apr 9, 2012 at 21:14

8 votes

Complexity of an optimisation problem in 3D

answered Apr 20, 2012 at 11:58

7 votes

P-Completeness and Parallel Computation

answered Apr 21, 2012 at 20:48

7 votes

Accepted

Chernoff bounds and Monte Carlo algorithms

answered Nov 25, 2013 at 15:11

7 votes

Can PRNGs be used to magically compress stuff?

answered Mar 24, 2014 at 18:05

6 votes

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

answered Mar 26, 2014 at 11:36

6 votes

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

answered Apr 18, 2014 at 14:32

6 votes

Accepted

Turing-unrecognizable language - what TM does?

answered May 9, 2014 at 16:10

6 votes

Accepted

Rectangle Coverage by Sweep Line

answered Apr 20, 2012 at 18:52

6 votes

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

answered Apr 19, 2012 at 8:53

5 votes

Loop invariant for an algorithm

answered Apr 9, 2012 at 21:31

5 votes

Proving a specific language is regular

answered Apr 21, 2012 at 21:07

5 votes

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

answered Apr 24, 2012 at 18:29

5 votes

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

answered Apr 9, 2015 at 14:15

5 votes

Accepted

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

answered Apr 10, 2015 at 11:30

5 votes

Accepted

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

answered May 4, 2014 at 21:24

5 votes

Accepted

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

answered May 7, 2014 at 11:14

5 votes

Accepted

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

answered Apr 5, 2014 at 18:48

5 votes

Chernoff bound when we only have upper bound of expectation

answered Apr 29, 2015 at 21:26

4 votes

Accepted

Randomized Meldable Heap - Expected Height

answered Mar 15, 2016 at 8:26

4 votes

C++ Strings vs. Character Arrays

answered Apr 20, 2012 at 11:03

3 votes

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

answered Nov 26, 2013 at 8:56

3 votes

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

answered Nov 20, 2013 at 0:00

3 votes

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

answered Apr 4, 2012 at 13:00

3 votes

MST with half the edges the maximum weight

answered Apr 9, 2015 at 11:18

3 votes

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

answered May 11, 2014 at 17:40

Stack Exchange Network

52 Answers

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

How to prove that a language is not regular?

Randomized Selection

Quicksort vs. insertion sort on linked list: performance

HALF CLIQUE - NP Complete Problem

Complexity of an optimisation problem in 3D

P-Completeness and Parallel Computation

Chernoff bounds and Monte Carlo algorithms

Can PRNGs be used to magically compress stuff?

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

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

Turing-unrecognizable language - what TM does?

Rectangle Coverage by Sweep Line

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

Loop invariant for an algorithm

Proving a specific language is regular

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

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

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

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

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

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

Chernoff bound when we only have upper bound of expectation

Randomized Meldable Heap - Expected Height

C++ Strings vs. Character Arrays

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

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

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

MST with half the edges the maximum weight

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