Hottest Questions This Month

31

votes

5

answers

5k

views

Do theorems provers demonstrate their own correctness?

modified 4 hours ago Andrej Bauer 23.4k

5

votes

2

answers

1k

views

What do the ∀ and ∃ symbols mean in the Axiom of Choice?

type-theory

modified Jan 11 at 22:23 amalloy 105

11

votes

2

answers

2k

views

Can a DFA have an unreachable state?

regular-languages finite-automata

answered Jan 16 at 19:00 vonbrand 9,428

8

votes

2

answers

382

views

Minimum number of swaps in sorting sequence

algorithms graphs sorting

answered Jan 7 at 23:03 einpoklum 614

1

vote

1

answer

2k

views

A problem in NP but not NP-complete?

np-complete np-hard np p-vs-np

modified Jan 5 at 21:31 Rational Rose 37

8

votes

3

answers

192

views

Are assembly languages untyped?

type-checking assembly

modified Jan 1 at 16:21 Ta Thanh Dinh 151

2

votes

3

answers

375

views

Show that UPrime = {1^n : n ∈ N is prime} is in P

algorithms complexity-theory

answered 8 hours ago Sepehr omidvar 1

7

votes

3

answers

125

views

Find vertices of a convex polytope, defined by intersecting half-spaces

algorithms computational-geometry

modified Jan 20 at 17:29 D.W.♦ 114k

3

votes

1

answer

408

views

Expected length of a random walk on a line

algorithms probability-theory randomized-algorithms 2-sat random-walks

modified Jan 8 at 10:01 Yuval Filmus 215k

2

votes

1

answer

274

views

O(V+E) algorithm for computing chromatic number X(g) of a graph instead of brute-force?

algorithms complexity-theory graphs np graph-traversal

answered Dec 26 '19 at 12:39 Yuval Filmus 215k

1

vote

2

answers

734

views

min vertex cover to access k edges in a tree

algorithms graphs dynamic-programming vertex-cover

answered Jan 8 at 15:39 Antti Röyskö 531

4

votes

1

answer

451

views

How does a TLB lookup compare all keys simultaneously?

memory-access paging cache

answered Jan 20 at 8:03 andy_fingerhut 198

4

votes

1

answer

242

views

Find if there is matrix that satisfying the following conditions

algorithms dynamic-programming matrices

answered Jan 10 at 8:22 D.W.♦ 114k

7

votes

1

answer

227

views

How hard is finding the shortest path in a graph matching a given regular language?

graphs regular-languages regular-expressions shortest-path

modified Jan 19 at 19:35 D.W.♦ 114k

1

vote

1

answer

536

views

Derandomization of vertex cover algorithm

algorithms graphs approximation probabilistic-algorithms vertex-cover

modified Jan 4 at 12:12 Yuval Filmus 215k

3

votes

1

answer

248

views

Find expectation with Chernoff bound

algorithms probabilistic-algorithms chernoff-bounds

modified Jan 3 at 9:45 Juho 18.4k

1

vote

1

answer

144

views

Choose the kth choice of choosing n things out of m

combinatorics

answered Jan 4 at 22:35 D.W.♦ 114k

0

votes

2

answers

129

views

What is wrong with the following $P$ problem?

np-complete np-hard np

modified Jan 9 at 17:03 greybeard 574

1

vote

4

answers

121

views

Does infinite length strings lead to uncountable languages?

formal-languages turing-machines automata uncountability

modified Jan 14 at 22:30 gnasher729 16.5k

2

votes

2

answers

190

views

Why is n log n dominated by n log^2 n?

big-o-notation

modified Jan 14 at 12:19 Pooya 35

4

votes

1

answer

309

views

Prove that the class of CFG languages that are closed under reversal is undecidable

formal-languages automata context-free undecidability

modified Dec 26 '19 at 18:36 narek Bojikian 3,154

1

vote

2

answers

111

views

Streaming digit-to-digit conversion from decimal to hexadecimal

substrings string-matching base-conversion numeral-representations

modified Jan 19 at 3:53 Louis-Jacob Lebel 38

9

votes

1

answer

215

views

Subset sum problem for permutations

algorithms complexity-theory permutations subset-sum group-theory

modified Jan 2 at 13:36 Nastya Koroleva 91

3

votes

1

answer

125

views

maximum coverage version of dominating set

graphs np-complete terminology np-hard set-cover

modified Jan 3 at 18:27 John L. 20.2k

2

votes

4

answers

192

views

solving a problem with induction

induction

answered Jan 14 at 3:22 Ashwin Ganesan 394

5

votes

1

answer

87

views

Primitive word and cyclic rotations

strings word-combinatorics

modified Jan 17 at 21:14 Hermann Gruber 260

-2

votes

0

answers

383

views

I cant find a solution for a question of an array about prefix sum?

arrays

modified Jan 11 at 9:07 CodeChef 1

4

votes

1

answer

175

views

Search for maximal value smaller than V in an array composed of K linear functions

algorithms data-structures search-algorithms

answered Jan 12 at 15:02 John L. 20.2k

3

votes

2

answers

106

views

Thought process to solve tree based Dynamic Programming problems

algorithms trees dynamic-programming recurrence-relation recursion

modified Jan 20 at 6:03 ARR110 38

3

votes

2

answers

153

views

Examples of Analysis of Branch and Bound Method

linear-programming branch-and-bound

modified Jan 20 at 8:56 Laakeri 695

1

vote

2

answers

68

views

Is a^mb^n where m=n^2 a CFL?

automata context-free

modified Dec 28 '19 at 2:50 xskxzr 5,796

-1

votes

1

answer

218

views

Proof for clustering in a network of friendship

algorithms graphs clustering

answered Jan 2 at 16:42 Saad Balbiyad 76

0

votes

2

answers

79

views

How is the set of functions from ${\{a,b\}}$ to $N$ countable?

discrete-mathematics sets counting uncountability

modified Jan 2 at 5:06 Mars 265

4

votes

1

answer

99

views

Improving time complexity from O(log n/loglog n) to O((log ((nloglog n)/log n))/loglog ((nloglog n)/log n))

algorithms time-complexity big-o-notation

modified Jan 16 at 13:48 John L. 20.2k

4

votes

1

answer

122

views

Go from source to destination in 2d matrix with min steps collecting all candies. How to do it?

algorithms graphs matrix

answered Jan 4 at 16:42 shgr1092 73

3

votes

1

answer

73

views

What should I read to understand semantics of programming languages?

reference-request programming-languages semantics books

modified Jan 15 at 3:06 Apoorv Ingle 504

3

votes

1

answer

92

views

Why doesn't everyone use microkernel-based operating systems?

operating-systems os-kernel

modified Jan 6 at 6:12 Daniel Moskovich 151

6

votes

1

answer

181

views

Functor laws and natural transformations in Haskell

category-theory haskell

answered yesterday Pseudonym 11.1k

3

votes

2

answers

132

views

Union of a language in P and a language in NP\P

complexity-theory np

answered Jan 16 at 1:45 PMercier 54

2

votes

1

answer

62

views

How do I simplify $O\left({n^2}/{\log{\frac{n(n+1)}{2}}}\right)$

asymptotics landau-notation big-o-notation

modified Jan 9 at 6:19 Shiv 1,634

1

vote

1

answer

163

views

Error lower-bound for an algorithm for vertex cover

algorithms graphs randomized-algorithms vertex-cover

modified Dec 30 '19 at 16:21 narek Bojikian 3,154

3

votes

1

answer

121

views

How does a GPU get data from a CPU?

computer-architecture

answered Dec 31 '19 at 19:13 D.W.♦ 114k

3

votes

1

answer

89

views

What is the LTL expression for “there is a value of y whose next value is 8”?

linear-temporal-logic

answered Dec 25 '19 at 20:37 Shaull 14.1k

3

votes

1

answer

69

views

Dynamic data structure that checks all prefix sums of a subsequence are >= 0 and sum is = 0

data-structures binary-trees avl-trees

modified Jan 4 at 18:19 D.W.♦ 114k

2

votes

1

answer

69

views

How can I improve my algorithmic ingenuity?

algorithms education

answered Jan 9 at 10:58 IS3NY 56

2

votes

2

answers

68

views

Why doesn't everyone use distributed operating systems?

operating-systems os-kernel

modified Jan 7 at 22:49 Mars 265

2

votes

1

answer

112

views

Find shortest path of R,G,B Graph

algorithms graphs

modified Dec 28 '19 at 16:49 Aaron Rotenberg 1,905

0

votes

4

answers

87

views

Why are not programs already in binary code?

programming-languages

modified Jan 2 at 15:21 Guillermo Phillips 302

Top Questions

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