User Raphael

197 votes

3 answers

27k views

Is there a system behind the magic of algorithm analysis?

asked Apr 9, 2014 at 12:59

147 votes

4 answers

20k views

How can it be decidable whether $\pi$ has some sequence of digits?

asked Mar 14, 2012 at 13:19

145 votes

5 answers

208k views

How to convert finite automata to regular expressions?

asked May 23, 2012 at 8:19

106 votes

5 answers

18k views

How not to solve P=NP?

asked May 17, 2012 at 1:24

100 votes

5 answers

109k views

How to prove that a language is not context-free?

asked Mar 12, 2012 at 23:57

98 votes

10 answers

184k views

How to prove that a language is not regular?

asked Apr 4, 2012 at 10:30

98 votes

11 answers

30k views

Solving or approximating recurrence relations for sequences of numbers

asked Jul 17, 2012 at 18:31

76 votes

1 answer

17k views

Language theoretic comparison of LL and LR grammars

asked Mar 7, 2012 at 0:32

72 votes

4 answers

17k views

What is the novelty in MapReduce?

asked Aug 3, 2012 at 14:04

58 votes

11 answers

35k views

Why would anyone want CISC?

asked Mar 13, 2012 at 0:18

47 votes

4 answers

20k views

What are common techniques for reducing problems to each other?

asked Apr 10, 2013 at 21:31

31 votes

1 answer

10k views

Which combinations of pre-, post- and in-order sequentialisation are unique?

asked Mar 16, 2012 at 21:11

30 votes

2 answers

6k views

Why are the total functions not enumerable?

asked Mar 13, 2012 at 0:02

29 votes

4 answers

2k views

How to find a superstar in linear time?

asked Mar 15, 2012 at 7:55

29 votes

3 answers

5k views

What are staged functions (conceptually)?

asked Jul 23, 2012 at 9:04

27 votes

1 answer

9k views

How to show that L = L(G)?

asked Apr 14, 2013 at 19:02

25 votes

4 answers

3k views

How to fool the plot inspection heuristic?

asked Mar 29, 2012 at 7:09

21 votes

1 answer

1k views

Generating inputs for random-testing graph algorithms?

asked Jul 30, 2012 at 21:36

20 votes

1 answer

1k views

Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem

asked Feb 7, 2013 at 7:35

20 votes

2 answers

578 views

How to scale down parallel complexity results to constantly many cores?

asked May 3, 2012 at 8:08

20 votes

5 answers

643 views

Efficient compression of unlabeled trees

asked Mar 9, 2012 at 17:54

20 votes

5 answers

2k views

A Case Distinction on Dynamic Programming: Example Needed!

asked Mar 10, 2012 at 13:26

20 votes

2 answers

2k views

Compute a max-flow from a min-cut

asked Dec 3, 2014 at 17:19

19 votes

3 answers

453 views

How many cookies in the cookie box? -- Tiling stars

asked Dec 12, 2014 at 19:51

19 votes

3 answers

1k views

Problems Implementing Closures in Non-functional Settings

asked Mar 12, 2012 at 7:52

19 votes

1 answer

280 views

Natural occurrences of monads that make use of the category-theoretical framework

asked Mar 8, 2012 at 20:45

19 votes

1 answer

258 views

Decision problem such that any algorithm admits an exponentially faster algorithm

asked Mar 13, 2012 at 13:38

15 votes

4 answers

1k views

Is every linear-time algorithm a streaming algorithm?

asked Aug 16, 2012 at 8:26

15 votes

2 answers

1k views

Are there established complexity classes with real numbers?

asked Sep 1, 2014 at 11:13

14 votes

3 answers

1k views

What goes wrong with sums of Landau terms?

asked Mar 14, 2012 at 13:12

Stack Exchange Network

51 Questions

Is there a system behind the magic of algorithm analysis?

How can it be decidable whether $\pi$ has some sequence of digits?

How to convert finite automata to regular expressions?

How not to solve P=NP?

How to prove that a language is not context-free?

How to prove that a language is not regular?

Solving or approximating recurrence relations for sequences of numbers

Language theoretic comparison of LL and LR grammars

What is the novelty in MapReduce?

Why would anyone want CISC?

What are common techniques for reducing problems to each other?

Which combinations of pre-, post- and in-order sequentialisation are unique?

Why are the total functions not enumerable?

How to find a superstar in linear time?

What are staged functions (conceptually)?

How to show that L = L(G)?

How to fool the plot inspection heuristic?

Generating inputs for random-testing graph algorithms?

Rigorous proof for validity of assumption $n=b^k$ when using the Master theorem

How to scale down parallel complexity results to constantly many cores?

Efficient compression of unlabeled trees

A Case Distinction on Dynamic Programming: Example Needed!

Compute a max-flow from a min-cut

How many cookies in the cookie box? -- Tiling stars

Problems Implementing Closures in Non-functional Settings

Natural occurrences of monads that make use of the category-theoretical framework

Decision problem such that any algorithm admits an exponentially faster algorithm

Is every linear-time algorithm a streaming algorithm?

Are there established complexity classes with real numbers?

What goes wrong with sums of Landau terms?