Nathaniel's user avatar
Nathaniel's user avatar
Nathaniel's user avatar
Nathaniel
  • Member for 4 years, 11 months
  • Last seen this week
  • Paris, France
27 votes
Accepted

Is there an algorithm whose time complexity is between polynomial time and exponential time?

26 votes
Accepted

"partial sorting" algorithms (aka "partitioning")

16 votes

Can anyone give me an instance of 3SAT with exactly one solution?

15 votes
Accepted

What are you allowed to move into the big O notation for it to be still correct?

12 votes

How to find the largest power of two divisor of a given integer?

10 votes

Algorithm to get any spanning tree not necessarily a minimum spanning tree

9 votes

Prove that every substring closed language L ⊆ {0, 1}* is regular

8 votes
Accepted

What is a witness string? I unable to understand the concept

8 votes

Arrow notation?

7 votes

Set theory pertaining to category theory and functional programming

7 votes
Accepted

Generating Isomorphic Graphs

7 votes

Length of a regular expression

6 votes
Accepted

Are reversed reverse preorder traversals equivalent to a postorder traversal?

6 votes
Accepted

If $A ⊆ B ⊆ C$ and $A$, $C$ are decidable, then $B$ is decidable

6 votes
Accepted

Using pre-,post-, and in-order indexes to find information about a Binary Search Tree

5 votes
Accepted

Doubt about computing running time / time complexity of a function in Python

5 votes
Accepted

$\log_{2}{(\frac{1}{2}n)} + \log_{2}{(\frac{1}{4}n}) + \log_{2}{(\frac{1}{8}n)} + \ldots + \log_{2}{(\frac{1}{2^{log_{2}(n)}}n)} = O(\log_{2}(n))$?

5 votes
Accepted

n! and 2^(n^2); which one grows faster

5 votes

Equivalence relation between two CFG's

5 votes
Accepted

Asymptotic Analysis of T(n) = 2T(n/8) + 2T(n/4) + n

5 votes

An α-good tree with n nodes has height O(log n)

5 votes

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

5 votes
Accepted

Randomly selecting element from data structure, probability based on weight

5 votes
Accepted

Why {${xww|x,w∈(a+b)^*}$} is regular but {${ww|w∈(a+b)^*}$} is not $? $

4 votes
Accepted

Size of minimal DFA

4 votes

Expected running time of an algorithm

4 votes
Accepted

DFA for the language of non-empty words that are no longer than $2^6$

4 votes
Accepted

Complexity of DFS : O(m)

4 votes
Accepted

is it possible to compress a sequence of progressive unique numbers dramatically?

4 votes
Accepted

Is this language $X = \{x:xxx\in L\}$ regular?

1
2 3 4 5
9