nir shahar
  • Member for 1 year, 7 months
  • Last seen this week
Prove or disprove: $L^n=M^n\nRightarrow L=M$ where $L$ and $M$ are languages
Accepted answer
2 votes

What about $\Sigma^*$ and $\Sigma^*\setminus\{11\}$?

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

$0^*$ will generate any number of repetitions of $0$, and will also generate the empty string $\epsilon$. So, the problem with your expression is that $11$ is also accepted, since we can write it as $$...

View answer
Algorithm to get maximum value of tuples from two sets
2 votes

Lets define the following bipartite graph: The nodes in the first group, will be the elements from $A$, and the nodes in the second group will be the elements from $B$. Add an edge between every ...

View answer
How to prove time complexity for this algo?
2 votes

Your intuition is a great starting point. To formalize this, consider denoting by $F(n)$ the number of times the col-- happens, or equivalently, the total time you waste in the while loops. Notice, ...

View answer
Disprove sorting in O(log(n))
Accepted answer
2 votes

The first argument does help with a rigorous refutation for the statement. If you want to really be formal, here is how you should approach it (its not a formal proof, but more of a sketch for how you ...

View answer
Implement a dictionary by using direct addressing on a huge array
2 votes

Here is another hint: how would you find whether an element is valid in $O(1)$ in this auxiliary stack? Try to somehow "connect" the index at the original huge array, to the place in the ...

View answer
Simplest transformation from XOR to CNF SAT
Accepted answer
2 votes

Lets start with transforming $a\oplus b = True$. This is simple enough, since it happens if and only if either one of $a$ or $b$ is $True$ and the other is $False$. We can easily encode it as follows: ...

View answer
Is ${\Sigma_2^\textsf{P}}^\textsf{coNP}\subseteq\textsf{PH}$?
Accepted answer
2 votes

For any language $L$, and for any oracle $O$, we have that $L^O=L^\overline{O}$. Substitute $NP$ instead of $O$, and $\Sigma^P_2$ instead of $L$ and you get that ${\Sigma^P_2}^{coNP}={\Sigma^P_2}^{NP}$...

View answer
Given two languages $A,B \subseteq \Sigma^*$, prove that $A/B$ is semi-decidable if both the languages are semi-decidable
Accepted answer
2 votes

Let us keep this in mind: $w\in A/B \iff \exists z\in B: wz\in A$ Since we are working with semi-decidable machines, then we have no problem iterating over all $z$'s until we find a good one! ...

View answer
Longest path between two nodes of a graph
Accepted answer
2 votes

Yes (assuming you meant that we can choose $e$ freely. If it isn't the case, the answer is "no"). Let $P_1:=a\rightarrow v_1\rightarrow v_2\rightarrow \dots \rightarrow b$ be the shortest ...

View answer
Importance of study of mathematics in algorithm design and other computer science fields
Accepted answer
2 votes

Take a look at my answer here. Basically, the different areas of math are used in different areas of computer science as well. Specifically for algorithms, for example, knowing probability theory can ...

View answer
Algorithm that will find the minimum number of steps to get from state $j$ to state $i$
Accepted answer
2 votes

This is indeed a correct approach. It can be improved further by using binary search on $k$, but you have to be careful with it since you want to multiply a small number of matrices (and computing $A^...

View answer
Find if two elements in an array sum up to a given number
Accepted answer
2 votes

There is an $O(n)$ solution, using a nice trick: Keep track of the different values you have already seen in an auxiliary hashmap, called $seen$. Now, loop over the elemnts of the array (the original ...

View answer
Tic-Tac-Toe in PSPACE
2 votes

An $n\times n$ grid takes $n^2$ memory cells. You don't need to remember the "history" of the game, as it is irrelevant.

View answer
Help Understanding the Halting Problem
2 votes

It seems you are struggling to understand the definition of the halting problem. So I will try my best to define it so you can understand easily. Our task, is to create some algorithm, which we will ...

View answer
Given a finite alphabet, how to generate all possible strings while excluding those that don't feature an element at least once?
Accepted answer
2 votes

For every position $0\le i\le 1000$, enumerate over all strings that have $e$ at their $i$'th spot. This can be easily done as you need to enumerate on strings with length $i-1$ and strings with ...

View answer
An "easy" graph problem I can't solve
2 votes

For every edge $(u,v)$ with weight $2$, create a new node $w_{u,v}$. Discard the edge $(u,v)$, and instead of it add two edges $(u,w_{u,v})$ and $(w_{u,v},v)$ with weight $1$. Now you can use a ...

View answer
There exists some number $x$ so in any run of BFS from vertex $w$, so the distance from $u$ to $v$ in BFS tree is always $x$
Accepted answer
2 votes

The statement is false. Take a look at the following graph: In one BFS run, you will get the following tree: That has a distance of $1$ between $u$ and $v$, while in a different run, you could get ...

View answer
Language in NPC and CoNP
Accepted answer
2 votes

Let $L\in NP$. Thus, $L\le_p A$. Since $A\in coNP$, then $L\in coNP$. Hence, $NP\subseteq coNP$. Now, let $L\in coNP$. Thus, $\overline{L} \in NP$ and therefore $\overline{L}\le_p A$. From reduction ...

View answer
Reduction with NPH
Accepted answer
2 votes

if a problem is in $NPH$ then it is also in $NPC$ This statement is incorrect. A language is in $NPC$ if it is in $NPH$ and it is in $NP$. Answer 4 is incorrect as well since that would imply that ...

View answer
P = NP ==> there exists no OWF: proof using NTM and binary tree
Accepted answer
2 votes

The core idea is good. You might want to elaborate more on how this process is done in detail: Let us keep in mind that an OWF is a function $F$ that can be computed in $poly(n)$ time but $F^{-1}$ ...

View answer
Does this Qualify as Sub-Exponential?
Accepted answer
2 votes

Lets say there are $N(n)$ partitions. Then, for each partition you do $O(n^c)$ work (important note: make sure for all partitions this is the same $O(n^c)$. That is, for this particular $c$, for all ...

View answer
disadvantages of a long time quantum in scheduling
2 votes

Try to think in practical terms what would actually happen if your computer used a big quantum: Lets say our quantum is 1 second. Now, say you browse in a browser (for example, CS stack exchange), and ...

View answer
Understanding contradiction in proof of Algorithm for Testing of Clustering of points in metric space in sub-linear time
Accepted answer
2 votes

From what I understand, the problem the paper is trying to solve is a gap problem of deciding whether $X$ is $(k,b)$-clusterable, or at least $\epsilon$-far from being $(k,2b)$-clusterable. Since they ...

View answer
Is Programming Witchcraft or Actual Magic?
2 votes

In my opinion, programming is magic: you get into a small dark room and smash keyboards and poof you got infinite money. Just kidding! programming isn't magic at all, nor witchcraft. If you will learn ...

View answer
NP problem: certificate concept clarification
2 votes

The second approach is technically the correct interperation. When we say "a verifier gets a certificate $c$ that looks like [...] and computes something", then we actually mean that this ...

View answer
Why 2^(2n+2) not equal to θ(2^2n)?
2 votes

It is theta of $2^{2n}$: $$2^{2n+2}=4\cdot 2^{2n}=\Theta(2^{2n})$$

View answer
What is the sense of distance in the definition of SSSP Problem?
Accepted answer
2 votes

It is defined by the function $d_s(x)=distance(s,x)$. Basically, its just the distance function where we fix the source node to be $s$.

View answer
Hilbert's Hotel for guests with infinite string name
Accepted answer
2 votes

An (infinite) string is uniquely identified by a function $s:\mathbb{N}\rightarrow \{A,B\}$, such that $s(n)$ is the $n$'th character in the string. The number of such functions is known to be: $|\{A,...

View answer
non-existence of sentence that captured specific property
Accepted answer
2 votes

You are right that $N$ is used in this way. If you want a proof without $N$, you will have to prove in some other way (for example, by sentence induction) that $M'\models\psi$. I understand you that ...

View answer
1 2
3
4 5
16