Hottest Questions This Week

2

votes

3

answers

528

views

Are there problems in NP that do not reduce in polynomial time to any problem in NP?

np polynomial-time

modified yesterday ShAr 122

2

votes

1

answer

170

views

Topological sort with minimum maximal distance in array

modified 2 days ago Peter Mortensen 158

4

votes

1

answer

99

views

Is Desmos Turing-Complete?

turing-completeness

modified yesterday Bubbler 236

2

votes

3

answers

96

views

Algorithms question: Largest contiguous subset selection

algorithms divide-and-conquer

modified 23 hours ago don't talk just code 121

2

votes

2

answers

58

views

Asymptotics of $(6^n-1000)/(2^n+1)$

asymptotics

modified Sep 10 at 22:20 Jut 1

1

vote

1

answer

84

views

In search of finding an idea that work in $o(n^3)$

algorithms

modified Sep 11 at 22:01 Steven 18.6k

3

votes

1

answer

56

views

Can you diagonalize a language out of CSL?

formal-languages computability context-sensitive diagonalization

modified Sep 10 at 16:22 Yuval Filmus 257k

1

vote

2

answers

52

views

What is the entropy of an unordered list?

sets information-theory data-compression entropy

answered Sep 11 at 3:09 benrg 1,094

1

vote

1

answer

79

views

What is the meaning of the pipe symbol here?

algorithms automata discrete-mathematics distributed-systems

modified yesterday nir shahar 8,733

2

votes

1

answer

74

views

What is the regular expression for the language, {w | w does not contain the substring 11}

complexity-theory computability finite-automata regular-expressions

modified Sep 12 at 18:27 nir shahar 8,733

2

votes

1

answer

66

views

If P!=NP, does there exist infinite hierarchy of languages between P & NP?

complexity-theory

answered yesterday Emil Jeřábek 785

2

votes

1

answer

48

views

Turing machines which halt after updating a cell for the second or third time

turing-machines computability

modified Sep 11 at 9:55 Yuval Filmus 257k

0

votes

2

answers

38

views

inversions in array

algorithms algorithm-analysis

answered yesterday zkutch 2,121

1

vote

1

answer

38

views

How can an instruction be fetched every cycle?

cpu cpu-cache cpu-pipelines instruction-set

answered yesterday harold 1,698

1

vote

1

answer

37

views

What is the intuition behind working of hamming codes

hamming-code hamming-distance

modified Sep 12 at 7:11 Yuval Filmus 257k

1

vote

0

answers

60

views

Hardness result for online matching

randomness matching bipartite-matching online-algorithms adversary

modified Sep 13 at 15:23 Yuval Filmus 257k

0

votes

1

answer

43

views

I made bubble_sort() function following the algorithm. But it is not working. where is my error?

sorting python

answered yesterday san 11

1

vote

1

answer

40

views

VCdim of concentric circles

machine-learning vc-dimension

answered Sep 11 at 9:07 Yuval Filmus 257k

2

votes

1

answer

28

views

Quadratic probing variant scheme

algorithms hash

modified Sep 10 at 17:59 Yuval Filmus 257k

1

vote

1

answer

34

views

How to count occurences in a Skiplist

algorithms data-structures

answered Sep 13 at 11:31 Inuyasha Yagami 2,408

0

votes

1

answer

43

views

What is the sequence that is computed by a Turing machine?

turing-machines computability

answered 2 days ago André Souza Lemos 3,238

0

votes

1

answer

43

views

Does there exist a language O such that $NL^O= Dtime(n^{logn})^O$? How to proceed with the proof in either case?

complexity-theory

answered 2 days ago Ariel 13k

1

vote

2

answers

41

views

Example of attribute grammar that is NOT l-ORD but non-circular

attribute-grammars

answered yesterday Algoman 146

1

vote

1

answer

40

views

Solving recurrence relation with square root by reduction

recurrence-relation

answered Sep 13 at 10:04 Yuval Filmus 257k

0

votes

1

answer

24

views

Array Doubling Size Strategies

time-complexity runtime-analysis arrays stacks

answered 11 hours ago vonbrand 13.3k

1

vote

1

answer

38

views

Oldest publication of the lower bound on comparison sort

history

modified yesterday Inuyasha Yagami 2,408

0

votes

1

answer

29

views

Algorithm to find approximate position of element from a noisy sorted list

algorithms binary-search searching

modified 2 days ago Inuyasha Yagami 2,408

0

votes

1

answer

22

views

Minimum spanning tree where weights of edges are intersecting sets

optimization sets weighted-graphs minimum-spanning-tree

modified Sep 11 at 15:01 Steven 18.6k

0

votes

1

answer

28

views

Efficient random sampling from large discrete distribution

time-complexity statistics sampling

answered Sep 11 at 17:41 Steven 18.6k

0

votes

1

answer

28

views

Inversions of Insertion Sort and Bubble Sort

algorithms algorithm-analysis

modified yesterday Steven 18.6k

1

vote

0

answers

35

views

Square of a directed graph $G=\left< V, E\right>$

complexity-theory graphs graph-traversal

modified 2 days ago Avra 235

0

votes

1

answer

27

views

Using FFT as a black box to solve subset sum. How is this done? Given a set of numbers, S, and a target value T

algorithms divide-and-conquer subset-sum polynomial-time-reductions fast-fourier-transform

answered Sep 14 at 2:09 Inuyasha Yagami 2,408

0

votes

1

answer

34

views

Formal proof of existence of equivalent parse tree for each derivation

context-free formal-grammars

modified Sep 13 at 0:26 Node.JS 131

1

vote

1

answer

16

views

Consequences of a polytime algorithm for a decision problem reducible to 3SAT

np-complete np complexity-classes

answered Sep 11 at 9:58 Yuval Filmus 257k

0

votes

1

answer

26

views

Greedy approach behind SPOJ Aggressive Cows problem

greedy-algorithms binary-search

answered yesterday Inuyasha Yagami 2,408

1

vote

0

answers

33

views

Is quantum computing a serious usable instrument for the IT industry?

probability-theory quantum-computing

modified Sep 13 at 11:08 Yuval Filmus 257k

0

votes

0

answers

30

views

Is the length of the longest balanced parentheses in )()(())()()))())))( 10 and not 12?

algorithms

modified Sep 12 at 5:36 greybeard 881

0

votes

1

answer

30

views

How is a histogram implemented as a data structure?

data-structures

answered Sep 14 at 3:22 D.W.♦ 134k

2

votes

0

answers

29

views

Simple efficient algorithm for dynamically maintaining max of special linear functions

algorithms data-structures optimization online-algorithms

asked Sep 11 at 1:55 Chengyuan Ma 21

1

vote

1

answer

22

views

Finding maximum clique given, for each edge, union of all cliques containing it

complexity-theory graphs clique

modified Sep 11 at 13:17 Yuval Filmus 257k

1

vote

1

answer

22

views

How can you apply dynamic connectivity problem to digital photos?

algorithms digital-image-processing

answered Sep 10 at 22:19 Kyle Jones 7,570

0

votes

0

answers

28

views

Natural Join in relational algebra

databases relational-algebra

modified 3 hours ago Encipher 139

-2

votes

0

answers

27

views

Can i recover data if i completely wiped the disk? Please help! [closed]

partitions

asked Sep 13 at 16:51 Thunderstorm 1

1

vote

0

answers

27

views

Describing the matrix product $BB^T$ of the incidence matrix of a directed graph $G=\left< V,E \right>$

graphs

modified 2 days ago Yuval Filmus 257k

0

votes

0

answers

27

views

Regular expression for all words over $\Sigma$ in which at least one symbol is missing

regular-expressions

modified yesterday Yuval Filmus 257k

-2

votes

0

answers

27

views

javascript coding error [closed]

programming-languages coding-theory

modified yesterday S Aditya 1

0

votes

1

answer

27

views

Compress set of mostly known bitstrings

data-compression

answered 3 hours ago Pseudonym 16.1k

0

votes

1

answer

20

views

K-Path-Problem is in $P$ or $NPC$

graphs np-complete np

answered 2 days ago Nathaniel 3,628

Top Questions

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