Hottest Questions This Month

39

votes

2

answers

7k

views

How does Tarjan's pseudocode work (explained to someone familiar with C or Java)?

programming-languages

modified Feb 6 at 14:14 Polygnome 103

5

votes

4

answers

2k

views

Is the infinite language unrecognizable in a Turing machine?

modified Feb 15 at 10:42 Christoph Burschka 121

5

votes

1

answer

2k

views

If graph isomorphism is in P, is then P = NP?

complexity-theory np-complete p-vs-np graph-isomorphism

modified Jan 31 at 8:14 dkaeae 1,768

7

votes

2

answers

2k

views

Does a code with length 6, size 32 and distance 2 exist?

information-theory coding-theory encoding-scheme

modified Feb 20 at 14:05 Apass.Jack 11.5k

6

votes

3

answers

478

views

Can you prevent a man in the middle from reading the message?

security

answered 6 hours ago Vilx- 121

5

votes

2

answers

470

views

Logic behind O(n) solution for 'Maximum length sub-array having given sum'

algorithms time-complexity space-complexity

modified Feb 14 at 13:50 Evil 7,783

5

votes

1

answer

557

views

Where are C++ templates inside of the lambda cube?

programming-languages type-theory dependent-types c++ calculus-of-constructions

modified Jan 26 at 14:30 Raphael♦ 57.7k

2

votes

3

answers

385

views

Given a sorted array with n elements and element x that is inside the array at position k, find k in O(min(logk, log(n-k)))

algorithms time-complexity binary-search

modified Feb 13 at 13:50 Apass.Jack 11.5k

1

vote

1

answer

361

views

Is a particular string regular (e.g is '010') regular?

formal-languages regular-languages finite-automata

modified Feb 20 at 3:52 xskxzr 3,575

7

votes

4

answers

110

views

What is the depth of recursion if we split an array into $\log_2(n)$ with each recursive call?

complexity-theory time-complexity asymptotics recursion mathematical-analysis

modified Jan 29 at 15:41 Apass.Jack 11.5k

4

votes

5

answers

232

views

Unbiased random number generator

random-number-generator

answered Feb 2 at 15:22 gnasher729 10.9k

3

votes

2

answers

227

views

The idea behind the state of Imperative languages

programming-languages programming-paradigms imperative-programming

modified 2 days ago Andrej Bauer 20.2k

3

votes

2

answers

302

views

Is there a name for this priority queue data structure?

data-structures terminology heaps priority-queues

modified Jan 27 at 17:26 Curtis F 439

2

votes

2

answers

480

views

Easy instances of the coloring problem on graphs with degree at most 4

complexity-theory graphs colorings

modified Feb 18 at 13:17 Christoph Burschka 121

3

votes

2

answers

113

views

Why is every finite language A ⊆ Σ* regular

regular-languages finite-automata

modified Feb 15 at 15:10 Draconis 4,543

3

votes

2

answers

149

views

Number of computations for multiplication

complexity-theory multiplication

answered Feb 19 at 13:41 Daniel McLaury 519

4

votes

2

answers

67

views

Sorting “almost sorted” array in $O(n\log\log n)$

sorting

answered Feb 20 at 16:42 Apass.Jack 11.5k

7

votes

2

answers

52

views

The recursion $T(n) = T(n/2)+T(n/3)+n$

asymptotics recurrence-relation

modified yesterday Raphael♦ 57.7k

3

votes

1

answer

244

views

What is an example of a weakly universal hash function that is not pairwise independent?

hash hash-tables probabilistic-algorithms

modified Feb 14 at 17:19 Yuval Filmus 193k

2

votes

0

answers

626

views

Turing machine VS Push Down Automaton in CFL

turing-machines context-free pushdown-automata

modified Feb 6 at 8:54 user100074 1

5

votes

2

answers

84

views

Must the champion of an entire tournament beat the champion of a possible tournament among other players?

correctness-proof game-theory

modified Feb 12 at 19:17 Apass.Jack 11.5k

3

votes

1

answer

267

views

Difference between sequential and parallel divide and conquer

algorithms parallel-computing divide-and-conquer

modified Feb 11 at 9:11 Discrete lizard♦ 4,214

4

votes

2

answers

75

views

Add lines to star with fixed coordinates maximizing smallest angle

algorithms graphs graph-theory computational-geometry

answered Feb 6 at 22:14 Apass.Jack 11.5k

3

votes

2

answers

89

views

How to prove the equivalence of two CFG for balanced parentheses?

formal-languages context-free formal-grammars

modified Feb 8 at 8:43 dkaeae 1,768

1

vote

1

answer

83

views

Is this partitioning problem NP-complete?

algorithms np-complete reductions np approximation

modified Feb 6 at 14:38 orlp 5,855

3

votes

2

answers

105

views

Finding the maximum of a bitonic sequence

algorithms arrays discrete-mathematics

answered Feb 7 at 7:25 aaag 1,205

3

votes

2

answers

121

views

$f(n) = o(n^c) \rightarrow \exists \epsilon > 0 \ s.t. f(n) = O(n^{c-\epsilon})$

asymptotics master-theorem

answered Jan 28 at 14:51 Apass.Jack 11.5k

3

votes

1

answer

57

views

Why more and more languages do not have link stage when compiling?

compilers

answered 2 days ago Derek Elkins 9,223

5

votes

1

answer

119

views

How does treewidth behave under graph minor operations?

graph-theory discrete-mathematics graph-minors treewidth

modified Feb 17 at 20:51 D.W.♦ 99.4k

3

votes

2

answers

42

views

Is there a systematic way to know when to alpha-transform free variables?

lambda-calculus variable-binding church-numerals

modified Jan 28 at 16:04 Draconis 4,543

2

votes

3

answers

84

views

How does a computer “wait” time?

computer-architecture programming-languages

modified Feb 10 at 18:03 D.W.♦ 99.4k

5

votes

2

answers

50

views

Topology vs sigma-algebra's as a framework for approximate information?

logic topology

modified Feb 13 at 19:39 Andrej Bauer 20.2k

3

votes

2

answers

63

views

Interesting logic problems

logic decision-problem search-problem

modified 9 hours ago KVN 177

3

votes

2

answers

126

views

Efficient data structure handling insert(number) and find(sum) returning pair a,b such that a + b = sum

algorithms data-structures efficiency

answered Feb 4 at 18:22 Ajay Deshmukh 1

3

votes

1

answer

125

views

Mathematical Problem Solving

algorithms computability

answered Jan 27 at 17:24 KVN 177

5

votes

2

answers

57

views

Identity types and universes

type-theory dependent-types homotopy-type-theory

answered Feb 10 at 22:01 Andrej Bauer 20.2k

2

votes

2

answers

33

views

Union of a regular and a non-regular language

formal-languages regular-languages

answered yesterday Peter Taylor 1,186

2

votes

1

answer

114

views

Dependent type system with different computation model

reference-request type-theory dependent-types

answered Feb 4 at 20:39 Andrej Bauer 20.2k

1

vote

1

answer

82

views

What does all uppercase letters mean?

lambda-calculus

modified Feb 11 at 0:05 D.W.♦ 99.4k

2

votes

2

answers

135

views

Minimizing the maximum Manhattan distance

computational-geometry

modified Feb 15 at 12:53 David Eisenstat 859

2

votes

2

answers

105

views

Iterative Fibonacci algorithm correctness proof, finding loop invariants

algorithms correctness-proof induction loop-invariants

modified Jan 28 at 11:59 KVN 177

2

votes

2

answers

132

views

Decidability of equivalence to existential formulas

formal-languages time-complexity logic first-order-logic

modified Feb 18 at 8:00 F.D.C. 13

3

votes

2

answers

45

views

Regular expression for binary words with 1 in the middle

automata finite-automata regular-expressions

modified Feb 12 at 16:37 Apass.Jack 11.5k

3

votes

3

answers

95

views

Complexity of forming a min heap out of a given array with k inversions

time-complexity heaps

modified Feb 20 at 9:43 Amir H 81

1

vote

1

answer

113

views

Sorting lower bounds for almost sorted array

data-structures time-complexity sorting comparison

modified Feb 10 at 4:14 Yuval Filmus 193k

4

votes

2

answers

51

views

Does there exist a context-free language $L$ such that $L\cap L^2$ is not context-free?

regular-languages context-free regular-expressions

answered Feb 14 at 0:21 Hendrik Jan 21.2k

8

votes

1

answer

64

views

Given a constant k, find the biggest possible rooted tree, if for every path from root to leaf, the sum of the arity of its nodes equals k?

trees combinatorics

modified Jan 29 at 11:06 Hendrik Jan 21.2k

3

votes

2

answers

79

views

Merging balls interview problem

algorithms dynamic-programming greedy-algorithms stacks

answered Feb 17 at 0:35 gnasher729 10.9k

Top Questions

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