Hottest Questions This Week

3 votes

2 answers

1k views

Length of a regular expression

regular-expressions

Nathaniel

7,127

answered May 17 at 18:59

2 votes

1 answer

514 views

Is there an algorithm that in some cases is an improvement of BFS in the same way A* is an improvement of Dijkstra?

Nathaniel

7,127

modified May 17 at 23:03

2 votes

3 answers

107 views

Find the smallest difference between two numbers in a DS in O(1) time

time-complexity data-structures runtime-analysis binary-trees heaps

Subhankar Ghosal

170

answered May 18 at 18:25

4 votes

1 answer

145 views

Is the set of languages satisfying the pumping lemma closed under concatenation?

regular-languages pumping-lemma closure-properties

Yuval Filmus

269k

answered yesterday

2 votes

2 answers

78 views

Are reversed reverse preorder traversals equivalent to a postorder traversal?

binary-trees graph-traversal

Hendrik Jan

27.2k

answered yesterday

0 votes

3 answers

72 views

How is pipelining possible?

cpu

gnasher729

24.9k

answered May 18 at 11:14

2 votes

1 answer

114 views

Disprove: if L is decidable then Prefix(L) is decidable

turing-machines undecidability halting-problem check-my-answer

John L.

33k

modified May 16 at 21:01

1 vote

1 answer

79 views

How to find parameter sets for a big-O expression to be fixed-parameter tractable?

complexity-theory runtime-analysis big-o-notation parameterized-complexity

John L.

33k

modified May 17 at 21:31

3 votes

1 answer

65 views

Allocating m rooms of varying capacity to n booking requests of varying sizes

optimization dynamic-programming optimal-strategy

D.W.♦

140k

modified 2 days ago

1 vote

1 answer

59 views

How to convert AFA to ε-NFA / NFA / DFA?

regular-languages automata finite-automata

Hendrik Jan

27.2k

modified May 17 at 20:59

1 vote

2 answers

45 views

Why is $A_{TM}$ not mapping reducible to $E_{TM}$?

turing-machines reductions undecidability

user2277550

255

modified yesterday

0 votes

1 answer

74 views

I think I have discovered a new sorting algorithm using binary search tree [closed]

sorting trees binary-search-trees

Yves Daoust

3,318

answered May 17 at 10:44

0 votes

1 answer

73 views

Finding a Hamiltonian Cycle in a directed graph - graph problem

algorithms graphs python hamiltonian-path hamiltonian-circuit

PK96

29

modified May 18 at 18:03

0 votes

1 answer

72 views

Is there a hash-map implementation optimized to favor key lookups based on frequency (if key is referenced the most then it is searched first)?

algorithms search-algorithms search-trees hash-tables

gnasher729

24.9k

answered yesterday

0 votes

1 answer

56 views

Why is there a 'true' statement as precondition in the following loop invariant

loop-invariants

Yves Daoust

3,318

modified 2 days ago

0 votes

1 answer

56 views

Does a constant time compression algorithm proves that P=NP?

complexity-theory time-complexity np-complete polynomial-time data-compression

Steven

22.7k

modified yesterday

0 votes

1 answer

64 views

Dynamic routing algorithm

computer-networks weighted-graphs dynamic-graphs

user19121278

31

modified May 18 at 9:02

1 vote

2 answers

49 views

Pushdown automaton that accepts $a^{2k} b^{3k}$, without multiple pop

pushdown-automata

user19121278

31

modified May 15 at 19:08

2 votes

1 answer

62 views

prove that if L is context-free then L' = {w2#w1 | w1#w2∈L} is context-free

regular-languages context-free computation-models

Hendrik Jan

27.2k

modified May 15 at 22:41

0 votes

2 answers

47 views

A little confusion with Big Theta time complexity

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

Björn Lindqvist

957

modified 2 days ago

1 vote

1 answer

41 views

Algorithm to calculate lower incomplete gamma function

numerical-algorithms numerical-analysis

Denis

131

modified May 16 at 6:01

0 votes

1 answer

39 views

Walk from vertex u to vertex v on complete graph, formula for number of walks of length k

graphs discrete-mathematics graph-traversal

Nathaniel

7,127

modified May 15 at 20:11

1 vote

1 answer

38 views

How many different boolean functions exist up to permutation of its $n$ variables

boolean-algebra permutations boolean-complexity

Yuval Filmus

269k

answered 2 days ago

1 vote

2 answers

48 views

Since there is no such thing as infinite memory, can we say that all pushdown automata and Turing machines are actually very big DFA?

complexity-theory turing-machines finite-automata pushdown-automata

Hendrik Jan

27.2k

answered May 15 at 19:37

2 votes

1 answer

37 views

Find a context-free grammar for uc^nd^nv where the number of a's and b's in uv are equal

formal-languages context-free

Hendrik Jan

27.2k

answered May 15 at 14:01

0 votes

1 answer

46 views

Cosine distance in a space, and cheating?

machine-learning euclidean-distance

Yves Daoust

3,318

modified yesterday

1 vote

1 answer

25 views

Can Boolean circuits of polylog depth represent all Boolean functions?

circuits boolean-complexity

Emil Jeřábek

935

answered May 17 at 13:32

0 votes

0 answers

50 views

Binary compression algorithm with decompress by index

algorithms complexity-theory data-structures information-theory data-compression

Yuval Filmus

269k

modified 5 hours ago

1 vote

1 answer

38 views

Is finding the union of all minimum hitting sets NP-hard?

np-hard check-my-answer

orlp

12.3k

modified May 16 at 16:11

1 vote

2 answers

38 views

Formal mathematical resolution for Recurrence Relations

recurrence-relation

Yves Daoust

3,318

answered 12 hours ago

0 votes

1 answer

48 views

Find $k$ shortest paths in linear time

algorithms

D.W.♦

140k

answered 20 hours ago

1 vote

1 answer

27 views

Find the largest subset of unpaired elements [duplicate]

algorithms optimization np-complete sets

Ashwin Ganesan

1,005

answered May 15 at 13:37

1 vote

0 answers

43 views

$\epsilon$-Testing the property of subsequence non-existence

algorithms randomized-algorithms substrings

Theorem

141

modified 10 hours ago

1 vote

1 answer

33 views

Time Complexity of ${n \choose k}$

time-complexity

D.W.♦

140k

answered 21 hours ago

1 vote

1 answer

25 views

If predicate P is partially-decidable, is ¬P decidable, partially decidable or undecidable?

undecidability semi-decidability decidability

Yuval Filmus

269k

modified May 15 at 18:14

0 votes

0 answers

40 views

What can be the topic of my assignment for presentation about overall computing performance?

computer-architecture cpu performance high-performance-computing

AHF

187

modified 4 hours ago

-3 votes

0 answers

33 views

The Language of All Palindromes - Is it CFL?

formal-languages regular-languages automata context-free formal-grammars

AutoMata

1

asked yesterday

0 votes

0 answers

31 views

Undirected unweighted sub-graph enumeration with threshold on node value

algorithms graphs data-structures

Tom Finet

236

modified 2 days ago

1 vote

0 answers

30 views

Split Bipartite Graph

graphs partitions bipartite-graph

Jon Nir

143

modified May 17 at 21:20

-1 votes

0 answers

30 views

Flow in Ford-Fulkerson algorithm

computer-networks routing dynamic-graphs

Jun Seo-He

99

asked May 15 at 20:03

0 votes

0 answers

29 views

Find a set K of k vertices in a graph such that the distance between any vertex to the closest vertex in K is minimized

algorithms time-complexity

Throckmorton

967

modified May 18 at 2:48

-3 votes

0 answers

29 views

Fixed parameter tractability Big O

complexity-theory

Sarah

1

asked 2 days ago

1 vote

1 answer

22 views

Why do we use {+1, -1} in place of {0, 1} for the Fourier analysis of boolean functions?

boolean-algebra

Yuval Filmus

269k

answered May 16 at 10:40

1 vote

1 answer

17 views

Efficient search of a large set of documents to find documents that only contain a particular set of words

dynamic-programming search-algorithms natural-language-processing search-problem information-retrieval

D.W.♦

140k

modified May 18 at 4:11

0 votes

1 answer

28 views

The average time complexity of linear search with weighted probability

algorithms

jhjhb

1

modified 9 hours ago

-3 votes

0 answers

27 views

Its about automata [closed]

automata finite-automata context-free

Abdelrahman Ahmed

1

asked 2 days ago

2 votes

0 answers

27 views

Universal register machine that recognizes the image of a partial function

computability computation-models

Jr.

21

modified May 16 at 6:34

2 votes

0 answers

27 views

$y$-Fast Tries: Why not partition into groups of $\Theta(\log^2 M)$ elements?

data-structures integers succinct-data-structures

templatetypedef

8,807

modified 9 hours ago

Top Questions

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