Hottest Questions This Month

43

votes

9

answers

7k

views

Is UTF-8 the final character encoding for all future time?

encoding-scheme

modified Jun 19 at 22:08 Robbie Goodwin 101

16

votes

5

answers

7k

views

Why do more powerful programming languages tend to have slower implementations?

programming-languages

answered Jun 25 at 18:45 Quantum Mechanic 101

18

votes

8

answers

4k

views

Is Group Theory useful in Computer Science in areas other than cryptography?

modified Jul 7 at 12:21 Schism 103

9

votes

7

answers

4k

views

Checking equality of integers: O(1) in C but O(log n) in Python 3?

complexity-theory time-complexity runtime-analysis python c

modified Jul 6 at 9:10 Tom van der Zanden 11.7k

2

votes

3

answers

1k

views

Prove or Disprove: an infinite intersection of regular languages is a context-free language

regular-languages context-free

modified Jun 26 at 13:07 6005 2,954

7

votes

3

answers

894

views

Computation Complexity books for a mathematician

complexity-theory books

modified Jun 20 at 8:22 Bean Guy 73

11

votes

3

answers

2k

views

Are there competitions for integer programming?

satisfiability integer-programming sat-solvers mips programming-contest

modified Jul 7 at 22:15 John L. 23.2k

1

vote

1

answer

664

views

Is it true that if L* is recursive, L is also recursive?

formal-languages computability kleene-star

modified yesterday John L. 23.2k

5

votes

2

answers

215

views

Graph coloring variation

graphs np-complete terminology colorings

modified yesterday John L. 23.2k

4

votes

2

answers

194

views

Difficulty in understanding the proof of the lemma : “Matroids exhibit the optimal-substructure property”

algorithms proof-techniques greedy-algorithms matroids

modified Jul 7 at 14:50 John L. 23.2k

8

votes

2

answers

126

views

Is the leapfrog automata problem in P?

complexity-theory turing-machines

answered yesterday user326210 388

4

votes

1

answer

223

views

What is the computational complexity of “real-life” regular expressions?

formal-languages regular-expressions chomsky-hierarchy

modified Jun 23 at 15:07 lemontree 419

1

vote

1

answer

358

views

What are the modern alternatives to Backus–Naur form and what are their advantages?

formal-languages context-free formal-grammars syntax syntax-trees

modified Jun 22 at 2:33 Aaron Rotenberg 2,899

14

votes

1

answer

428

views

Is the language of words that are unbalanced in the first half context-free?

formal-languages context-free formal-grammars

modified Jun 28 at 12:18 Vor 11.7k

4

votes

1

answer

193

views

What is the goal of studying all those NP-complete problems?

complexity-theory graphs np-complete

answered Jun 24 at 12:44 Pål GD 8,446

2

votes

1

answer

105

views

What does the notation $ [ i \neq k ] $ mean?

notation

modified Jul 2 at 22:14 Gerardo Zinno 167

2

votes

1

answer

121

views

Average number of exchanges during first partition stage in Quicksort

algorithm-analysis asymptotics quicksort

modified Jun 30 at 21:16 John L. 23.2k

6

votes

1

answer

104

views

Binary-ish search through partially ordered set

search-algorithms binary-search

modified 10 hours ago John L. 23.2k

2

votes

1

answer

170

views

Proof for NP-hardness of simultaneous minimization and maximization of a weighted subset

np-complete np-hard np satisfiability 3-sat

modified Jun 29 at 12:46 Pål GD 8,446

2

votes

1

answer

76

views

Confusion in Turings proof of the undecidability of the Entscheidungsproblem

turing-machines turing-completeness

modified Jun 22 at 20:56 Wololo 123

1

vote

1

answer

192

views

What are the known ambiguities in C language grammar?

context-free formal-grammars c syntax syntax-trees

modified Jun 21 at 0:51 BearAqua 463

0

votes

3

answers

102

views

Can a 600 MB text file with digits of the square root of 2 be compressed to 600 KB?

data-compression python

modified Jun 25 at 7:47 Jakube 1,241

0

votes

2

answers

69

views

What subfields in computer sciences may one study without learning Object Oriented Programming?

cpu simulation object-oriented

answered Jul 1 at 22:17 gnasher729 19.1k

3

votes

1

answer

227

views

A variation of the halting problem

turing-machines undecidability decision-problem

modified Jun 28 at 6:44 prime_hit 858

2

votes

1

answer

64

views

Complexity of Integer Factorization

complexity-theory turing-machines time-complexity decision-problem

answered Jun 18 at 19:25 Ariel 11.5k

1

vote

1

answer

171

views

Minimum cost of “signal” cover in a tree with DP

dynamic-programming trees

modified Jun 19 at 11:28 Steven 9,180

2

votes

1

answer

62

views

Returning random integer from interval based on last result and a seed

arrays randomized-algorithms memory-management subsequences intervals

answered Jul 3 at 18:28 D.W.♦ 122k

5

votes

1

answer

48

views

Does big-Oh impose an ordered partition on the set of the “usual” functions?

reference-request big-o-notation

modified Jun 26 at 17:30 John L. 23.2k

3

votes

1

answer

70

views

Does $\mathcal{P}\neq\mathcal{NP}$ imply $\mathcal{NP}\neq\mathcal{NP}^{\mathcal{NP}}$?

complexity-theory

modified Jun 13 at 11:15 Pål GD 8,446

4

votes

2

answers

70

views

If I can efficiently uniformly sample both $A$ and $B\subset A$, can I efficiently uniformly sample $A-B$?

probability-theory sampling random-number-generator

answered Jul 2 at 14:36 morty 1

1

vote

1

answer

113

views

Given an array $a$, we have to find product of $a_{j}$-$a_{i}$ modulo $998244353$ over all $i$ and $j$ given $j>i$

polynomials fast-fourier-transform

modified Jul 5 at 22:08 plop 111

1

vote

3

answers

100

views

Algorithm to compute power function on interval [0, 1]

numerical-algorithms

modified Jun 30 at 6:24 njuffa 315

0

votes

3

answers

97

views

Big O vs Big $\Theta$ during coding interview

time-complexity big-o-notation ambiguity

answered Jun 18 at 14:58 Hugues 19

1

vote

1

answer

57

views

Any reason why Turing Machine would prevail on recursion theory?

turing-machines recursion

answered Jul 5 at 21:23 Bjørn Kjos-Hanssen 834

1

vote

2

answers

66

views

Finding the shortest path in a grid which has walls

algorithms graphs graph-traversal

modified Jun 12 at 18:49 Steven 9,180

2

votes

1

answer

66

views

What is the expected time complexity of checking equality of two arbitrary strings?

time-complexity runtime-analysis python string-matching

modified Jul 3 at 1:05 jtschoonhoven 237

2

votes

2

answers

51

views

Prove that every regular subset of $a^nb^n$ is finite

formal-languages regular-languages finite-automata

answered Jun 26 at 11:35 gnasher729 19.1k

0

votes

2

answers

38

views

Online shortest path in ordered DAG

graphs shortest-path online-algorithms

modified Jun 17 at 7:16 Steven 9,180

10

votes

0

answers

131

views

Is the two-color leapfrog problem in P?

complexity-theory turing-machines

modified 3 hours ago user326210 388

3

votes

2

answers

101

views

Check for common element in two arrays using FFT

algorithms discrete-mathematics fourier-transform

modified Jul 6 at 17:55 dk14 223

0

votes

1

answer

77

views

What is the VC dimension of the hypothesis class $H=\left\{f_{\theta_{1}, \theta_{2}}: R^{2} \rightarrow\{0,1\} \mid 0<\theta_{1}<\theta_{2}\right\}$?

learning-theory vc-dimension

modified Jun 20 at 23:29 hinduml 11

1

vote

2

answers

77

views

Functional Programming and Category Theory

reference-request functional-programming category-theory

modified Jun 23 at 12:01 ice1000 734

2

votes

1

answer

89

views

Find two disjoint set

algorithms sets

modified 2 days ago Aaron Rotenberg 2,899

1

vote

1

answer

42

views

What is the maximum number of indices one can create on a table with N columns?

databases permutations

modified Jun 16 at 7:40 Glorfindel 610

1

vote

1

answer

69

views

Cannot understand the relevance of $\binom{n-1}{2}$ subarrays in The Maximum Sub-array Problem

algorithms divide-and-conquer maximum-subarray

modified Jun 21 at 19:04 John L. 23.2k

3

votes

1

answer

53

views

Recurrence relation for the number of “references” to two mutually recursive function

proof-techniques recurrence-relation recursion

answered Jul 1 at 4:40 John L. 23.2k

0

votes

1

answer

68

views

“Given an algorithm, decide whether it runs in polynomial time” is this problem in NP?

complexity-theory np polynomial-time

answered Jun 22 at 4:01 D.W.♦ 122k

1

vote

2

answers

50

views

What is exactly an empty Sub-array

algorithms maximum-subarray

modified Jun 22 at 12:35 zingergi 36

Top Questions

Looking for more? Browse the complete list of questions, or popular tags. Help us answer unanswered questions.