nir shahar
  • Member for 1 year, 8 months
  • Last seen this week
All possible sum of each array combination
4 votes

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 ...

View answer
Searching for sorting algorithm taking into account all possible solution of similar numbers
1 votes

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 ...

View answer
Proving correctness of Polynomial reduction
0 votes

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 ...

View answer
Confusion about whats being processed in a quantum computer
Accepted answer
1 votes

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 &...

View answer
Let Σ = {a} be a one-element alphabet and L ⊆ Σ^* be an arbitrary language over Σ = {a}. Show that L^* is regular
0 votes

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?

View answer
What is the contradiction of statement "if $n^2$ is odd then n is odd"
Accepted answer
1 votes

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$ ...

View answer
Proof that the complement of a finite language is always an infinite language
2 votes

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
Proof that the complement of a finite language is always an infinite language
-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| = |\...

View answer
Find k closest numbers to the median
1 votes

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
How are vertex capacities defined in a flow network?
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{ ...

View answer
Python: Assigning values to 2D-array elements
0 votes

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 ...

View answer
If $\Sigma_i^P = \Sigma_{i+1}^P$ then for all $k \ge i$ holds $\Sigma_k^P = \Sigma_{k+1}^P$
Accepted answer
1 votes

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 ...

View answer
Product of polynomial with negligible function is negligible
Accepted answer
0 votes

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,...

View answer
Why can't I use a polynomial-time reduction for proving P-completeness?
Accepted answer
5 votes

$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. ...

View answer
Find nodes at k distance from given source node in an undirected cyclic graph if k<=1e9
0 votes

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 ...

View answer
If two languages are polytime reducable, does that imply they are also turing reducable
0 votes

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

View answer
Memory-efficient list of N unique integers from 0..N-1 with fast lookup
1 votes

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 ...

View answer
Can a non-recognisable language have a recognisable subset?
2 votes

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$.

View answer
no-input Turing Machine which accepts in k or fewer steps
0 votes

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 ...

View answer
Convert float array to lower or higher integer, find sum(integers) == round(sum(floats)), reducible to subset sum?
0 votes

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 ...

View answer
Deploying circles on 2D space to cover most of points
1 votes

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$ ...

View answer
Arguing that the inverse of Ackermann function is upper bounded by a logarithmic function (i.e. $\alpha(n) = O(\lg n)$)
1 votes

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 ...

View answer
PDA with multiple element access - $i$ - access PDA
Accepted answer
3 votes

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$ ...

View answer
Disambiguating Big-O and Theta for Expressing Time Complexity
1 votes

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 ...

View answer
Can there be a computer without software (only hardware)?
Accepted answer
4 votes

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...

View answer
Why don't we recognize Python as a compiler-based language?
Accepted answer
1 votes

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 ...

View answer
Is it true that $P = coNP$?
Accepted answer
3 votes

$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 \...

View answer
Considerations for space complexity analysis
0 votes

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 - ...

View answer
CVAL is in P (technical detail)
Accepted answer
2 votes

Yes, you are correct. Essentially, since you are dealing with a circuit, the graph representing it is a DAG (directed acyclic graph). Hence, your implementation will indeed compute the value of each ...

View answer
The preliminary of the Bandit Gradient Algorithm
Accepted answer
0 votes

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, ...

View answer
1
2
3 4 5
16