Hottest Questions This Month

18

votes

4

answers

5k

views

Time complexity of an algorithm: Is it important to state the base of the logarithm?

algorithms time-complexity

answered May 22 at 17:37 templatetypedef 5,739

29

votes

6

answers

6k

views

Why are ambiguous grammars bad?

compilers ambiguity

modified yesterday ComFreek 251

28

votes

2

answers

4k

views

Is Lambda Calculus purely syntactic?

lambda-calculus functional-programming

modified Jun 10 at 6:27 Camion 101

12

votes

5

answers

1k

views

Is there any use case for the bottom type as a function parameter type?

type-theory type-checking

answered May 27 at 16:28 J_mie6 210

9

votes

3

answers

1k

views

Intuition behind eigenvalues of an adjacency matrix

graph-theory adjacency-matrix

modified May 30 at 3:55 Sasho Nikolov 2,317

4

votes

2

answers

669

views

How to find sum of maximum K elements in range in array

data-structures search-trees

modified May 20 at 10:57 Yuval Filmus 202k

3

votes

3

answers

96

views

Does $L_1L_2 = L_2L_1$ imply $L_1 = L_2$?

formal-languages regular-languages

modified May 23 at 19:48 Hendrik Jan 21.7k

4

votes

2

answers

393

views

NL - iterating all edges of a graph in log space

complexity-theory graph-theory

modified May 27 at 21:11 Yuval Filmus 202k

5

votes

1

answer

233

views

How to prove the emptiness of intersection of two context free languages is undecidable?

formal-languages context-free reference-request undecidability

modified May 18 at 18:13 Apass.Jack 17k

5

votes

2

answers

131

views

List of major Open Problems in Computational Complexity and their Likelihood?

complexity-theory reference-request

answered Jun 3 at 19:43 Markus 46

5

votes

2

answers

131

views

Finding row wise sum of transpose of hv-convex binary matrix

graph-theory combinatorics

modified Jun 9 at 2:06 MegaTom 131

2

votes

3

answers

354

views

Do height-balanced binary trees have logarithmic depth?

data-structures binary-trees

modified Jun 4 at 21:48 Yuval Filmus 202k

3

votes

5

answers

110

views

Given a set of numbers, get the maximum 10 number average below a certain threshold

algorithms time-complexity

modified Jun 6 at 19:42 gnasher729 13.4k

1

vote

3

answers

78

views

in function declarations, what advantages are there to having the type of the parameter specified after the parameter name?

programming-languages

answered May 28 at 22:03 Gilles♦ 34k

1

vote

2

answers

99

views

Can the pre-order traversal of two different trees be the same even though they are different?

trees binary-trees graph-traversal search-trees

modified 2 hours ago lox 1,007

2

votes

3

answers

118

views

concatenation of context sensitive and context-free is context sensitive or not?

formal-languages context-free context-sensitive

modified Jun 6 at 14:47 xskxzr 4,460

2

votes

3

answers

190

views

Is time complexity more important than space complexity?

algorithms time-complexity cryptography

modified Jun 12 at 4:02 Apass.Jack 17k

2

votes

1

answer

296

views

+150

Solving recurrence relation with minimum and factorial

recurrence-relation factorial

modified 13 hours ago Evil 8,487

4

votes

3

answers

97

views

Is it a tautology or not? According to my truth table its not

propositional-logic

modified May 27 at 14:50 Yuval Filmus 202k

2

votes

4

answers

145

views

Algorithm for fewest moves in 1's, 10's, 100's, etc

algorithms

modified May 29 at 21:42 Toothpick Anemone 188

2

votes

1

answer

222

views

Efficient Algorithms for Destroyed Document Reconstruction

image-processing

answered May 19 at 23:32 Evil 8,487

6

votes

1

answer

81

views

Can all regular tree types be expressed as $\mu$ types?

programming-languages lambda-calculus type-theory tree-automata

modified May 23 at 12:55 Andrej Bauer 21k

6

votes

2

answers

58

views

Sequence to explore the complexity of the NP problem

soft-question

modified May 27 at 13:03 dkaeae 3,318

3

votes

2

answers

93

views

Bubble Sort with “while” loop - why is average case n^2?

algorithms algorithm-analysis time-complexity asymptotics

modified May 25 at 2:34 Apass.Jack 17k

0

votes

3

answers

71

views

Is λx. a valid Lamda Calculus abstraction?

lambda-calculus

modified Jun 2 at 9:16 user2542769 3

2

votes

1

answer

111

views

Proof that shortest path with negative cycles is NP hard

graph-theory shortest-path

answered Jun 2 at 19:08 BlueRaja - Danny Pflughoeft 885

2

votes

3

answers

52

views

How is functional property guaranteed in type theory when function type is defined?

type-theory homotopy-type-theory

modified Jun 12 at 21:03 Andrej Bauer 21k

4

votes

2

answers

62

views

sorting with noisy but persistent answers

algorithms sorting

modified Jun 6 at 9:26 Steven 423

2

votes

3

answers

60

views

proving L1* ∪ L2* ⊆ (L1∪L2)*

automata regular-languages

answered May 20 at 15:22 Konstantin Kotenko 21

5

votes

1

answer

76

views

Reduction from Exact Cover to Fixed Exact Cover

reductions np-hard

modified May 26 at 14:39 red31 132

0

votes

2

answers

67

views

What is the height of a tree with recursion formula: $T(n) = T(n - \sqrt{n})$

time-complexity trees recursion

answered Jun 12 at 14:49 Emil Jeřábek 406

3

votes

2

answers

40

views

Graphs of maximum degree three

graphs graph-theory

answered May 23 at 19:07 Juho 16.4k

3

votes

3

answers

81

views

CFG for all strings of a’s and b’s that contain a different number of a’s and b’s

automata context-free strings

answered Jun 5 at 18:09 Yuval Filmus 202k

1

vote

1

answer

132

views

how to find total paths in a graph which have only one vertex common with a given path

algorithms graphs trees

modified Jun 13 at 8:19 Vince 1,008

2

votes

1

answer

58

views

Floating point arithmetic

floating-point

modified May 28 at 7:10 Community♦ 1

4

votes

1

answer

196

views

Data structure for selection of K elements and taking sum

algorithms data-structures

modified Jun 10 at 17:41 Community♦ 1

0

votes

2

answers

86

views

Why run -time of N-Queens using backtracking algorithm fluctuates?

algorithms algorithm-analysis backtracking

modified May 24 at 6:01 Tom van der Zanden 9,264

2

votes

2

answers

109

views

Minimum number of comparisons in comparison-based sorting algorithms [closed]

sorting

modified May 26 at 18:55 Bulat 1,266

2

votes

1

answer

109

views

Showing that a language is NP Complete (advice)

complexity-theory

answered yesterday David Richerby 72.6k

4

votes

1

answer

83

views

Linked list: advantages of preventing movement of nodes and invalidating iterators on add/remove

java linked-lists c++

modified May 29 at 14:55 rcgldr 234

1

vote

3

answers

81

views

How is an Assembly Language Processed by a CPU's Circuitry?

computer-architecture assembly

answered Jun 5 at 11:55 gandalf61 176

0

votes

1

answer

61

views

Is computer science really a branch or sub-branch of physics? [on hold]

physics

modified Jun 13 at 11:29 orlp 6,610

2

votes

2

answers

73

views

How does a compiler infer a value's type?

compilers type-inference

answered May 24 at 11:57 ratchet freak 3,023

3

votes

2

answers

43

views

Give an NL-algorithm for complement of 2-SAT

complexity-theory 2-sat

answered May 27 at 15:42 Yuval Filmus 202k

4

votes

2

answers

55

views

Algorithm for factoring elements of permutation groups?

algorithms permutations group-theory

modified May 31 at 17:06 mo2019 171

1

vote

2

answers

87

views

Reduce 4-SAT to 5-SAT

time-complexity np-complete np-hard satisfiability polynomial-time

answered May 21 at 18:35 Apass.Jack 17k

5

votes

1

answer

65

views

Searching a Treasure

algorithms complexity-theory time-complexity search-algorithms

modified 2 days ago Apass.Jack 17k

3

votes

2

answers

81

views

Proving that a set of operations can't generate one integer from a given one

algorithms number-theory search-problem

modified Jun 10 at 16:56 David Richerby 72.6k

Top Questions

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