User D.W. - Computer Science Stack Exchange

129 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

81 votes

3 answers

55k views

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

asked May 18, 2013 at 6:56

50 votes

6 answers

59k views

How to prove greedy algorithm is correct

asked Jun 24, 2016 at 5:22

35 votes

5 answers

9k views

Enumerate all non-isomorphic graphs of a certain size

asked Aug 31, 2014 at 21:16

33 votes

3 answers

7k views

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

asked Jul 9, 2013 at 20:56

31 votes

3 answers

10k views

Teaching NP-completeness - Turing reductions vs Karp reductions

asked Oct 23, 2013 at 23:45

28 votes

2 answers

48k 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

4 answers

571 views

Complexity classes where $C^C = C$

asked Aug 22, 2013 at 20:52

22 votes

3 answers

2k views

Algorithm to minimize surface area, given volume

asked Sep 28, 2015 at 5:18

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

2 answers

2k views

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

asked Nov 4, 2013 at 3:28

15 votes

0 answers

721 views

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

asked Nov 16, 2013 at 3:08

15 votes

3 answers

3k views

Cast to boolean, for integer linear programming

asked Dec 22, 2015 at 4:03

13 votes

3 answers

6k views

Closest pair of points between two sets, in 2D

asked Nov 5, 2016 at 3:02

12 votes

1 answer

2k views

Algorithm to test whether a language is regular

asked Nov 14, 2013 at 7:13

12 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

675 views

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

asked Jun 14, 2014 at 3:00

11 votes

1 answer

2k views

Data structure for map on intervals

asked Dec 2, 2013 at 18:19

10 votes

1 answer

202 views

Mathematical optimization on a noisy function

asked Feb 18, 2015 at 19:38

9 votes

3 answers

4k views

Kernelization trick, for neural networks

asked Oct 19, 2013 at 7:01

9 votes

0 answers

179 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

1 answer

239 views

Verify correctness of quantifier elimination, using SAT

asked Oct 4, 2013 at 20:40

7 votes

2 answers

333 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

145 views

Subsequence of one string but not of others

asked Aug 31, 2017 at 17:20

7 votes

2 answers

419 views

Integral solutions to circulation problem

asked Oct 25, 2020 at 17:57

6 votes

1 answer

68 views

Small world theorem for set constraints

asked Jul 11, 2017 at 7:02

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

Complexity classes where $C^C = C$

Algorithm to minimize surface area, given volume

Could min cut be easier than network flow?

When to use SAT vs Constraint Satisfaction?

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

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

Cast to boolean, for integer linear programming

Closest pair of points between two sets, in 2D

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?

Data structure for map on intervals

Mathematical optimization on a noisy function

Kernelization trick, for neural networks

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?

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

Integral solutions to circulation problem

Small world theorem for set constraints