nir shahar
• Member for 1 year, 8 months
• Last seen this week

Sadly, the worst case scenario is exponential in time, no matter what algorithm you use. To see why, consider the following set of numbers: $A:=\{2^k \mid 0 \le k\le n\}$. There are $n$ numbers in ...

Just ise any regular sorting algorithm. All other permutations are guaranteed to be formed by taking all inner permutations of elements with the same value (e.g, if there are 3 elements with the same ...

The definition of NP-Hard states: "A problem $L$ is NP-Hard, if for every problem $L'\in NP$, there exists a polynomial reduction from $L'$ to $L$, namely - $L'\le_p L$". Now, since $A$ is ...

You are not far off the mark - quantum computations are all about probabilities. You may say that a quantum program (i.e, a series of quantum gates) computes $n+m$ (when $n,m$ are inputs), if with &...

Hint: Let $w\in L$ be the smallest non-empty word. What can you say about the relation between $L^*$ and $w$? How can you construct one from another?

The textbook shows an example of using a proof technique called "proof by contradiction". Basically, if you want to prove $A\rightarrow B$, then this technique says: "assume that $B$ ...

Here is a formal proof for the statement (warning, this really is a formal proof, and hence is not very intuitive): Let $\Sigma$ be a non-empty alphabet (either finite or infinite), and let $L\subset \... View answer -1 votes Lets denote$n:=|L|\in \mathbb{N}$. For any nonempty$\Sigma$, it is clear that$\Sigma^*$is infinite. By definition,$\bar L = \Sigma^*\setminus L$. Therefore,$|\bar L| = |\Sigma^*\setminus L| = |\...

Hint 1: try to transform the $n$ elements in such a way that the $k$ closest to the median will be the smallest $k$ elements after the transformation. Hint 2: now use a standard algorithm to find the $... View answer Accepted answer 0 votes Just like edges have capacities on them (i.e, how much flow is allowed to go through them), they have added capacities for nodes. If a node$v$has capacity$C_v$, then any flow with$\sum_{e \text{ ...

This happens because of how you created the array. I won't get into too much detail, but if you are familiar with the concept of "pointers", then an array is just a pointer - copying it will ...

Hint 1: Substitute directly into the definition of the hierarchy with oracles. Use induction in the proof. Hint 2: It is well known that $\Sigma_kSAT=\Sigma_k^P$. Try to use this in your proof (make ...

You are allowed, but you have to make sure to keep it formal. The property of $negl$ guarantees you that $\exists n_0 : \forall n>n_0: negl(n)<\frac{1}{p(n)k(n)}$ for some polynomial $k(n)$. Now,...

$P$-completeness is defined in terms of reductions stronger than polynomial reductions. For example, the notion of log-space reductions is such a "stronger" (more restrictive) reduction. ...

Do a regular BFS (for at most $k$ iterations, if you want to optimize it), and then loop through the vertices and take all of those that have $k$ distance. This approach works in $O(|V|+|E_k|)$ where ...

Hint: take $A=\emptyset$ and some $B\in R\setminus P$ where $R$ is the set of all recursive languages.

This is equivalent to storing a permutation of $n$ items in memory. There are in general, $n!$ ($n$ factorial) such permutations, and it is well known that $\log(n!)=\Theta(n\log(n))$. Hence, you will ...

Take any language $L\notin RE$. Now, $\emptyset \subseteq L$, and clearly $\emptyset\in RE$. FYI, the converse is also not necessarily true: $L\subseteq \Sigma^*$, and $\Sigma^*\in RE$.

Well, just simulate $M$ for $k$ steps and see if it accepts or not Or, if you want to prove by induction for some reason (there shouldn't be any reason to do this), then just run the machine for one ...

Here is how I would solve this: Denote $A$ as the array, which has $n$ values $A_1,\dots,A_n$. Without loss of generality, I will assume that there is no integer in $A$ (think of how to deal with the ...

Here is a start (for the case where you allow overlap): For every point $v$, start by drawing a circle with radius $r$ such that $v$ is at its center. Now, observe the following nice property: Let $d$ ...

Yes, it is an abuse of big-O notation. Hint: To actually prove the theorem for all $n$ (not only those within practical limits), try to show instead that the ackerman function is $\Omega(2^n)$. This ...

Hint: replace every $d$-depth transition with a set of states and transitions that will read out $d-1$ elements, then read the last element and do the transition, and afterwards return the last $d-1$ ...

Lets start by explaining the difference between big-O and $\Theta$. Basically, if we think of big-O as "bounding from above", we can think of $\Theta$ as "bounding both from below and ...

Thats called a logic circuit. It computes stuff. No software here, only physical logic gates involved. Even though technically a computer is a logic circuit...

The compilation process is a process of taking code from language "A" and translating it to code from language "B". Lets start by saying that python doesn't compile at all - it ...

$P=coNP$ is an open question, equivalent to the famous: "is $P=NP$ true?" question. The definition of $coNP$ you have is incorrect. The correct definition is the following: coNP:=\{L\mid \...

Usually, when talking about Turing Machines - the space complexity refers to the furthest position the TM's head will reach in its entire execution for the given input. For every step further - ...

This follows almost immediately from the definition of expectation, when we sample the actions with the distribution that $\pi_t$ (the bandit) defines, and the inherent randomness of the model. First, ...