Hottest Questions This Week

3

votes

2

answers

289

views

Should the certificate for NPSPACE be polynomial in size?

modified 2 days ago D.W.♦ 132k

3

votes

2

answers

377

views

If regex describes FSAs, what string formats describe Turing machines?

modified 2 days ago Pseudonym 15.3k

9

votes

1

answer

268

views

What is the closure of context-free languages under finite intersections?

complexity-theory formal-languages context-free formal-grammars context-sensitive

modified yesterday Hendrik Jan 25.6k

2

votes

2

answers

166

views

What would be the big O notation for a function that attempts to find pairs of users that participate in different discussions?

algorithms big-o-notation

answered Jun 16 at 20:37 Joseph Kaptur 1

1

vote

1

answer

109

views

Hilbert's Hotel for guests with infinite string name

uncountability diagonalization

modified yesterday Ran G. 19.7k

1

vote

3

answers

84

views

Time Complexity of Logarithmic For loop

complexity-theory time-complexity

answered Jun 14 at 17:50 Léon 31

0

votes

1

answer

39

views

Reason that integers are used for priorities instead of float

process-scheduling multi-tasking

answered 2 days ago Pseudonym 15.3k

0

votes

1

answer

46

views

Cache coherence is worthless and does nothing?

computer-architecture concurrency

answered Jun 15 at 0:12 Pseudonym 15.3k

2

votes

1

answer

35

views

Difference between convex hull algorithms

computational-geometry convex-hull

answered 23 hours ago Vincenzo 2,825

1

vote

1

answer

72

views

What's the difference between a protocol and a distributed algorithm?

algorithms distributed-systems protocols

modified Jun 15 at 5:23 Brian Tompsett - 汤莱恩 1,656

2

votes

1

answer

52

views

How to prove the same states are repeating in Synchronizable DFA?

automata finite-automata

modified 2 days ago ladypary 23

4

votes

2

answers

30

views

How do you express a floor / ceiling in the approximation factor of an approximation algorithm?

complexity-theory computability approximation

answered Jun 17 at 11:20 gnasher729 22.7k

3

votes

1

answer

49

views

Minimum number of groups such that every element in graph is included?

graphs group-theory subgraphs

modified Jun 17 at 5:23 Juho 21.2k

-3

votes

1

answer

56

views

How to design fast/efficient algorithms?

algorithms efficiency

modified Jun 17 at 15:56 vonbrand 13.1k

2

votes

1

answer

42

views

Is ANN a data structure or an algorithm?

neural-networks

answered Jun 16 at 18:07 nir shahar 5,804

2

votes

1

answer

25

views

How does software prefetching work with in order processors?

computer-architecture compilers cpu-cache memory-hardware cache

answered 2 days ago Wandering Logic 16.8k

2

votes

1

answer

29

views

Effectively decidable vs. noneffectively (or ineffectively) decidable

terminology decidability

modified 19 hours ago GeekestGeek 131

1

vote

1

answer

34

views

Is it true that PRIMES are in SPARSE?

complexity-theory formal-languages primes

answered Jun 17 at 12:46 nir shahar 5,804

1

vote

2

answers

43

views

Prove that { $\langle M \rangle$ : $M$ is a TM and $L(M)$ is decidable} is undecidable

complexity-theory turing-machines decidability

answered Jun 14 at 16:59 Léon 31

3

votes

2

answers

43

views

Is it possible to reverse engineer cellular automata?

cellular-automata

answered 5 hours ago Ilmari Karonen 1,728

3

votes

0

answers

70

views

+50

From coin flips to algebraic functions via pushdown automata

pushdown-automata probabilistic-algorithms simulation

modified 6 hours ago Peter O. 111

2

votes

1

answer

33

views

Generalization of Cellular Automata

reference-request cellular-automata

answered Jun 17 at 10:38 Ilkka Törmä 196

0

votes

1

answer

52

views

Ray tracing tree

computer-graphics

modified Jun 16 at 13:46 Maria Zak 19

0

votes

1

answer

31

views

Is whole OS copied to ram when running?

operating-systems

answered Jun 15 at 18:01 Gilles 'SO- stop being evil' 40.6k

-1

votes

1

answer

51

views

Does ⌊1/𝑛⌋∈Θ(1/𝑛) or to Ω(log𝑛)

algorithms complexity-theory time-complexity asymptotics big-o-notation

modified Jun 15 at 12:07 nir shahar 5,804

1

vote

1

answer

48

views

Is $L = \{xw^3x^{rev}\mid x, w\in\{0, 1\}^*\}$ context-free?

formal-languages context-free formal-grammars

answered 2 days ago Hendrik Jan 25.6k

1

vote

1

answer

37

views

First-order logic - Does exist a sentence that is satisfiable by all infinite models and only by them?

first-order-logic predicate-logic

modified Jun 15 at 17:31 nir shahar 5,804

0

votes

1

answer

37

views

What is the optimal solution for the following “Largest lexicographical string with <= K consecutive elements” problem? Why is my answer wrong?

sorting strings

modified 2 hours ago tribbloid 101

0

votes

1

answer

35

views

Decide if the edges of a mixed graph can be directed in order to be an Eulerian Graph

graphs network-flow eulerian-paths

modified Jun 16 at 14:24 Steven 15.5k

2

votes

1

answer

26

views

How are two registers are enough to simulate a Turing machine?

turing-machines computation-models

answered Jun 17 at 6:50 Yuval Filmus 254k

0

votes

1

answer

55

views

Prove that the Language $L=\{code(M)\;|\;L(M)\; \text{is closed under reversal}\}$ is undecideable

reductions

answered Jun 14 at 18:37 nir shahar 5,804

1

vote

0

answers

54

views

Find two paths in a Graph which are disjunct in

graphs weighted-graphs directed-graphs

modified Jun 15 at 9:09 Cyan Houdini 11

1

vote

2

answers

32

views

Loop Invariants: Can someone explain this concept?

algorithms programming-languages loops

answered Jun 16 at 19:27 nir shahar 5,804

1

vote

2

answers

30

views

More efficient algorithm for Withdraw/Deposit position in bank statement

algorithms

answered yesterday D.W.♦ 132k

0

votes

1

answer

30

views

How are extremely large integers stored and implemented in programming languages?

cryptography c++ c

answered 4 hours ago Vincenzo 2,825

1

vote

1

answer

23

views

Number of unique values in array in $\theta(n)$ average expected time

sorting randomized-algorithms hash-tables

answered Jun 15 at 18:23 nir shahar 5,804

1

vote

1

answer

27

views

How B Tree guarantees self balancing property?

b-tree

answered Jun 16 at 9:33 Matthew Towers 487

0

votes

1

answer

27

views

Understanding a summation notation. Sum(j=2 to n) j - 1

algorithm-analysis summation

answered 2 days ago Pseudonym 15.3k

2

votes

1

answer

20

views

Parts of a function used in Space Complexity

space-complexity

modified Jun 17 at 17:22 Venus 121

-1

votes

1

answer

32

views

Number of comparisons in Quicksort

quicksort

modified Jun 14 at 14:38 Brian Tompsett - 汤莱恩 1,656

0

votes

0

answers

40

views

Given $n$ sets of matrices, find $n$ matrices that have the least number of LCDs among their entries

algorithms matrices integers factoring

modified 2 days ago Davide Valdo 101

1

vote

0

answers

40

views

equivalence of validity above different alphabet

logic first-order-logic propositional-logic logical-validity

modified 2 days ago Ella 59

-2

votes

0

answers

39

views

Is the approximation of this algorithm bounded?

algorithms approximation vertex-cover

modified Jun 14 at 3:53 t24akeru 143

-1

votes

1

answer

39

views

Context-free grammar for $a^{2n} b^{2n}$

formal-languages context-free

modified Jun 17 at 15:26 John L. 26.2k

0

votes

1

answer

60

views

Counting strongly connected components in a directed graph in $NL$

complexity-theory graphs space-complexity computation-models nondeterminism

modified 2 days ago nir shahar 5,804

1

vote

0

answers

36

views

Find the median in a full min-heap with at most $\left \lfloor \frac{n}{2} \right \rfloor$ comparisons

data-structures heaps

modified Jun 16 at 10:19 oren1 143

1

vote

1

answer

27

views

Avoid Storing Keys in Key-Value Store by Replacing the Key with 128-bit Murmur3 Hash

data-structures search-algorithms hash

answered Jun 16 at 18:47 D.W.♦ 132k

0

votes

1

answer

21

views

Efficient structure for pruning on job scheduling

np-complete scheduling

answered Jun 15 at 14:53 Vincenzo 2,825

Top Questions

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