User D.W.

128 votes

15 answers

16k views

How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

asked Aug 28, 2014 at 20:51

80 votes

3 answers

53k views

Express boolean logic operations in zero-one integer linear programming (ILP)

asked May 18, 2013 at 6:56

48 votes

6 answers

54k views

How to prove greedy algorithm is correct

asked Jun 24, 2016 at 5:22

35 votes

5 answers

8k views

Enumerate all non-isomorphic graphs of a certain size

asked Aug 31, 2014 at 21:16

32 votes

3 answers

7k views

Encoding 1-out-of-n constraint for SAT solvers

asked Jul 9, 2013 at 20:56

29 votes

3 answers

9k views

Teaching NP-completeness - Turing reductions vs Karp reductions

asked Oct 23, 2013 at 23:45

28 votes

2 answers

46k views

How to prove that a language is context-free?

asked Dec 2, 2013 at 4:18

22 votes

6 answers

2k views

Algorithm to test whether a language specified in algebraic form is context-free

asked Nov 11, 2013 at 19:42

22 votes

3 answers

2k views

Algorithm to minimize surface area, given volume

asked Sep 28, 2015 at 5:18

21 votes

4 answers

543 views

Complexity classes where $C^C = C$

asked Aug 22, 2013 at 20:52

20 votes

1 answer

2k views

Could min cut be easier than network flow?

asked Jun 9, 2015 at 19:50

19 votes

1 answer

3k views

When to use SAT vs Constraint Satisfaction?

asked May 28, 2013 at 4:15

15 votes

3 answers

3k views

Cast to boolean, for integer linear programming

asked Dec 22, 2015 at 4:03

14 votes

2 answers

2k views

MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?

asked Nov 4, 2013 at 3:28

14 votes

0 answers

695 views

Test whether two languages are equal, when give in algebraic form

asked Nov 16, 2013 at 3:08

13 votes

3 answers

5k views

Closest pair of points between two sets, in 2D

asked Nov 5, 2016 at 3:02

11 votes

1 answer

2k views

Data structure for map on intervals

asked Dec 2, 2013 at 18:19

11 votes

1 answer

2k views

Algorithm to test whether a language is regular

asked Nov 14, 2013 at 7:13

11 votes

2 answers

2k views

Smallest DFA that accepts given strings and rejects other given strings

asked Jan 13, 2014 at 9:37

11 votes

1 answer

651 views

What do complexity classes look like, if we use Turing reductions?

asked Jun 14, 2014 at 3:00

10 votes

1 answer

194 views

Mathematical optimization on a noisy function

asked Feb 18, 2015 at 19:38

9 votes

0 answers

175 views

Boolean formula that agrees with most truth assignments

asked Feb 28, 2014 at 3:52

9 votes

1 answer

1k views

Given n strings, is one of them a substring of another?

asked Nov 3, 2014 at 1:58

9 votes

4 answers

3k views

Can element uniqueness be solved in deterministic linear time?

asked Feb 4, 2015 at 22:45

9 votes

3 answers

4k views

Kernelization trick, for neural networks

asked Oct 19, 2013 at 7:01

9 votes

1 answer

231 views

Verify correctness of quantifier elimination, using SAT

asked Oct 4, 2013 at 20:40

7 votes

2 answers

328 views

Automated lip-reading: inferring what someone is saying, based upon video of them speaking

asked Sep 2, 2013 at 5:05

7 votes

1 answer

144 views

Subsequence of one string but not of others

asked Aug 31, 2017 at 17:20

6 votes

1 answer

67 views

Small world theorem for set constraints

asked Jul 11, 2017 at 7:02

6 votes

1 answer

3k views

Find all cycles through a given vertex

asked Jul 7, 2016 at 9:41

Stack Exchange Network

88 Questions

How to fool the "try some test cases" heuristic: Algorithms that appear correct, but are actually incorrect

Express boolean logic operations in zero-one integer linear programming (ILP)

How to prove greedy algorithm is correct

Enumerate all non-isomorphic graphs of a certain size

Encoding 1-out-of-n constraint for SAT solvers

Teaching NP-completeness - Turing reductions vs Karp reductions

How to prove that a language is context-free?

Algorithm to test whether a language specified in algebraic form is context-free

Algorithm to minimize surface area, given volume

Complexity classes where $C^C = C$

Could min cut be easier than network flow?

When to use SAT vs Constraint Satisfaction?

Cast to boolean, for integer linear programming

MIN-2-XOR-SAT and MAX-2-XOR-SAT: are they NP-hard?

Test whether two languages are equal, when give in algebraic form

Closest pair of points between two sets, in 2D

Data structure for map on intervals

Algorithm to test whether a language is regular

Smallest DFA that accepts given strings and rejects other given strings

What do complexity classes look like, if we use Turing reductions?

Mathematical optimization on a noisy function

Boolean formula that agrees with most truth assignments

Given n strings, is one of them a substring of another?

Can element uniqueness be solved in deterministic linear time?

Kernelization trick, for neural networks

Verify correctness of quantifier elimination, using SAT

Automated lip-reading: inferring what someone is saying, based upon video of them speaking

Subsequence of one string but not of others

Small world theorem for set constraints

Find all cycles through a given vertex