Steven
  • Member for 8 years, 11 months
  • Last seen this week
Data structure for fast insertion and fast random element removal
Accepted answer
28 votes

You can achieve constant amortized time per operation by keeping a dynamically-sized array $A$ (using the doubling/halving technique). To insert an element append it at the end. To implement ...

View answer
Are all Integer Linear Programming problems NP-Hard?
Accepted answer
22 votes

If a problem is NP-Hard it means that there exists a class of instances of that problem whose are NP-Hard. It is perfectly possible for other specific classes of instances to be solvable in polynomial ...

View answer
Is $\{w_1xw_2\mid w_1,w_2\in \{a,b\}^* \text{ and } x \in \{a,b\}\}$ regular or not?
17 votes

The language is regular and a possible regular expression for $L$ is $(a\mid b)^* (a \mid b) (a \mid b)^* = (a \mid b)^+$.

View answer
How is the problem, {⟨G⟩|G has no triangle} in Logspace?
Accepted answer
17 votes

You don't need to first write all 3-tuples and then check, for each of them, whether it induces a triangle. You can just enumerate the 3-tuples one at a time and reject as soon as you find one that ...

View answer
Can any problem in P be converted to any other problem in P in polynomial time?
Accepted answer
14 votes

If by convert you mean reduce (through a Karp-reduction), then it is possible to reduce any problem $A$ in $P$ to any non-trivial problem $B$ in $P$. Here "non trivial" means that $B$ has at least ...

View answer
Proof that for 2n nodes of +1 and -1 position doesn't count
12 votes

You can prove the claim by induction on $n$. If $n=1$ the claim is clearly true since it suffices to start from the unique "+1" node. When $n > 1$, let $u$ and $v$ be two consecutive ...

View answer
I have found an example where regular expression is not closed under concatenation. Where am I wrong?
Accepted answer
12 votes

If $n$ is fixed then $a^n$ is just a single word and so is $a^nb^n$. If by $a^n$ you mean the language $\{a^n \mid n \ge 0\}$ (whose corresponding regular expression is $a^*$) then the problem is that ...

View answer
Are there problems in NP that do not reduce in polynomial time to any problem in NP?
Accepted answer
11 votes

I understand the question as asking for the truth value of the proposition $\exists A \in \mathsf{NP}, \forall B \in \mathsf{NP}, A \not\le_p B$, where $\le_p$ denotes Karp reducibility. Then the ...

View answer
Find the number using binary search against one possible lie
9 votes

A generalization of this class of problems is widely studied. See, e.g., this paper for a survey. In your particular case, the problem can be easily solved without any asymptotic change in the ...

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

In order for $f(O(n)) \in O(f(n))$ to hold you essentially want $f$ to satisfy $f(cn) \le df(n)$ where $n$ is sufficiently large. Here the inequality must hold for all sufficiently large constants $c$,...

View answer
Faster algorithm for a specific inversion
Accepted answer
8 votes

Each element $j$ contributes $1$ to the cardinality of all sets $\{j > i \mid \sigma_j > i\}$ for which $i < \min\{\sigma_j, j\}$, and $0$ to the other sets. You can compute all $n$ values $K(...

View answer
Two regular languages over the same alphabet, regular or not regular?
8 votes

I see several problems. In your first part you say that, given a regular language $L$, $\overline{L}$ is regular since $\Sigma^*- L$ is also regular. This is true, but it is implicitly using the ...

View answer
Why does the Huffman coding algorithm produce a valid tree?
Accepted answer
7 votes

Let $v$ be a vertex of the tree. If $\pi_v$ is the path from the root of the tree to $v$, then the string $s(v)$ constructed from the labels of $\pi_v$ is unique (if you really want, you can prove ...

View answer
Irregularity of $\{ w_1 aa w_2 \mid |w_1| \neq |w_2| \}$
Accepted answer
7 votes

For $i \ge 0$ define $w_i = b^i aa$. For any $i,j \ge 0$ with $i \neq j$ you have that $b^i$ is a distinguishing extension for $w_i$ and $w_j$. Indeed, $w_i b^i \not\in L_2$ but $w_jb^i \in L_2$. Then ...

View answer
Proof that $P\subseteq NP$ without nondeterministic TM
Accepted answer
7 votes

The first definition you are referring to is probably the one that defines $\mathsf{NP}$ as the set of problems $\Pi$ for which there exist a non-deterministic poly-time Turing machine that decides $\...

View answer
Why is $\log n+\log \frac{n}{2}+\log \frac{n}{4}+\log \frac{n}{8}+\cdots+\log \frac{n}{n}=\Theta (\log^2 n)$?
Accepted answer
7 votes

Assuming $n$ is a power of $2$, you have: $$ \sum_{i=0}^{\log n} \log \frac{n}{2^i} = \sum_{i=0}^{\log n} \left( \log n - i \right) = \sum_{i=0}^{\log n} i = \frac{(\log n)(\log n+1)}{2} = \Theta(\log^...

View answer
Topological sort with minimum maximal distance in array
6 votes

The measure you are trying to minimize is called (directed) bandwidth. Finding a minimum directed bandwidth ordering is NP-hard.

View answer
how can turing machines be universal models of computation if they can't perform binary search?
Accepted answer
6 votes

Turing Machines can simulate binary search, in the sense that they can compute whatever you can compute using binary search. You seem to be confusing computability and complexity, which are two ...

View answer
Test if $ \sum_{n=0}^\infty \frac{n^2}{2^n} $ = O(1)
6 votes

It is false that $$ \sum_{n=0}^\infty \frac{n^2}{2^n} \ge \left( \sum_{n=0}^\infty n^2 \right) \cdot \left( \sum_{n=0}^\infty \frac{1}{2^n} \right), $$ assuming that's what you meant. You can see ...

View answer
Is this clique algorithm in polynomial time correct or might it have another time complexity?
Accepted answer
6 votes

Your analysis of the time complexity is wrong. Specifically this statement: In every loop we have less n s-clique where every s-clique might have maximum s(n−1) adjacent nodes to look at. In fact ...

View answer
Find the power of 2
Accepted answer
6 votes

Assuming arithmetic operations take constant time, you can compute it in $O(\log \log n)$ time. Start with $n_0=2$ and iteratively compute $n_i = n_{i-1} \cdot n_{i-1} = 2^{2^i}$ until $n_{i} > n$...

View answer
Minimize edges of a directed unweighted graph
6 votes

There is no polynomial-time algorithm for your problem, unless $\mathsf{P}=\mathsf{NP}$. Let $H$ be a connected undirected graph with at least $2$ vertices and consider the directed graph $G$ ...

View answer
Could anyone prove why O(n^(log n)) < O((log n)^n)?
Accepted answer
6 votes

Using $ < $ with the big-oh notation is a bit of abuse of notation. Formally, I take your statement to mean $\forall f(n) \in O(n^{\log n}), \; f(n) \in O((\log n)^n)$. Let $f(n) \in O(n^{\log n})...

View answer
Can Turing Machines solve non-decision problems?
6 votes

You can define two kinds of Turing Machines, transducers and acceptors. Acceptors have two final states (accept and reject) while transducers have only one final state and are used to calculate ...

View answer
Two definitions of Safe Edge
5 votes

They are two different definitions. The interview definition calls a safe edge one that is not part of any cycle and therefore cannot be removed from $G$ without disconnecting it, thus changing the ...

View answer
Upper bounds for a binomial coefficient
Accepted answer
5 votes

The argument looks correct. Also notice that you can get a better (but still loose) upper bound as follows: $$ \binom{k}{p-1} \le \sum_{i=0}^{k} \binom{k}{i} = 2^k $$ Where the equality $\sum_{i=0}^{k}...

View answer
Is the fastest solution for one NP-Complete problem the fastest solution for all NP-complete problems?
5 votes

A polynomial-time reduction only needs to preserve the size of the problem up to a polynomial upper bound (which is implied by the time constraint). As an example, suppose you have two NP-complete ...

View answer
Choose $n$ out of $2n-1$ boxes containing at least half of all white balls and half of all black balls
Accepted answer
5 votes

Let $B^*, B_1, B_2, \dots, B_{2n-2}$ be the the bins sorted by the number of white balls, in non-increasing order (break ties arbitrarily). Notice that the first bin is called $B^*$. Consider the two ...

View answer
Prove finding k disjoint paths from n given paths in a directed graph is NP-complete
Accepted answer
5 votes

Membership of your problem in $\mathsf{NP}$ is trivial. To prove that it is also $\mathsf{NP}$-hard consider an instance of (the decision version of) independent set consisting of a graph $G=(V, E)$ ...

View answer
ip/tcp packet decoding without wireshark
Accepted answer
5 votes

My guess is that what you are seeing is a Level 2 Ethernet frame and therefore the preamble is missing. Also the Ethernet checksum seems to be missing. In this case everything seems to line up (the ...

View answer
1
2 3 4 5
26