John L.
  • Member for 3 years, 6 months
  • Last seen this week
  • Canada
7 answers
91 votes
21k views
41 bookmarks
Why are some programming languages "faster" or "slower" than others?
1 answers
74 votes
13k views
44 bookmarks
Language theoretic comparison of LL and LR grammars
3 answers
71 votes
47k views
46 bookmarks
Express boolean logic operations in zero-one integer linear programming (ILP)
8 answers
51 votes
105k views
32 bookmarks
How to prove a language is regular?
6 answers
51 votes
10k views
17 bookmarks
Keeping a String Secret in (Open) Source Code
4 answers
49 votes
5k views
19 bookmarks
What is the meaning of $O(m+n)$?
1 answers
48 votes
19k views
28 bookmarks
Show that { xy ∣ |x| = |y|, x ≠ y } is context-free
10 answers
48 votes
11k views
13 bookmarks
O(·) is not a function, so how can a function be equal to it?
2 answers
44 votes
8k views
26 bookmarks
Perplexed by Rice's theorem
4 answers
43 votes
16k views
35 bookmarks
What are common techniques for reducing problems to each other?
6 answers
40 votes
6k views
34 bookmarks
How does a computer work?
6 answers
35 votes
8k views
17 bookmarks
Do lossless compression algorithms reduce entropy?
2 answers
32 votes
20k views
12 bookmarks
Show how to do FFT by hand
7 answers
32 votes
9k views
14 bookmarks
What are the simplest examples of programs that we do not know whether they terminate?
2 answers
30 votes
5k views
17 bookmarks
Is Lambda Calculus purely syntactic?
7 answers
30 votes
6k views
16 bookmarks
Are algorithms (and efficiency in general) getting less important?
2 answers
30 votes
12k views
18 bookmarks
Optimization version of decision problems
4 answers
30 votes
27k views
16 bookmarks
Is Morse Code binary, ternary or quinary?
2 answers
29 votes
2k views
15 bookmarks
Longest Repeated (Scattered) Subsequence in a String
1 answers
29 votes
1k views
10 bookmarks
Asymptotics of the number of words in a regular language of given length
2 answers
28 votes
38k views
19 bookmarks
How to prove that a language is context-free?
3 answers
27 votes
36k views
7 bookmarks
When is the minimum spanning tree for a graph not unique
3 answers
26 votes
2k views
13 bookmarks
Is the language of pairs of words of equal length whose hamming distance is 2 or greater context-free?
3 answers
23 votes
2k views
9 bookmarks
Why are NP-complete problems so different in terms of their approximation?
5 answers
23 votes
5k views
10 bookmarks
What is the formal, rigorous definition of a programming language?
2 answers
21 votes
12k views
9 bookmarks
Do the minimum spanning trees of a weighted graph have the same number of edges with a given weight?
3 answers
21 votes
6k views
1 bookmarks
Why is this code uniquely decodable?
2 answers
20 votes
45k views
13 bookmarks
Residual Graph in Maximum Flow
3 answers
17 votes
8k views
9 bookmarks
Example of a non-context free language that nonetheless CAN be pumped?
13 answers
17 votes
10k views
7 bookmarks
Why do we need full-fledged workstations running massive OSes with massive software?
1
2 3 4 5
7