How to modify Bellman-Ford algorithm for this specific Minimum Cost Flow problem? I'm trying to design an algorithm for the following optimization problem. Suppose that $G=(V, E)$ is a digraph where $V$ and $E$ are sets of vertices and edges of $G$, respectively. $|V| = n$ and $|E| = m$. $c$ is the cost vector; $c_{ij}$ is the cost of edge $(i,j)$. Costs can be negative and $G$ may have cycles (negative or positive). The target is a minimum cost flow from source vertex $1$ to sink vertex $n$ which must satisfy some constraints. So let $x$ be the solution vector; if $x_{ij}=1$ then the edge $(i,j)$ is a part of minimum cost flow. Here is my optimization problem:

$$min \sum_{(i,j)\in E}c_{ij}x_{ij}$$

Subject to these constraints:

$$\begin{array}{ll}
\sum_{i\in V}x_{ij}&=&\sum_{i\in V}x_{ji}~~~~~~\forall j\in V (j\neq1,n)\\
\sum_{j\in V}x_{1j}&=&1\\
\sum_{i\in V}x_{in}&=&1\\
x_{ij}&\in&\{0,1\}~~~~~~\forall i,j\in V\end{array}$$

First constraint makes us sure that in the final solution vector, total number of edges outgoing from vertex $i$ and total number of edges incoming to that vertex are equal.

Only one edge can go out from vertex $1$, based on second constraint and only one edge can come to vertex $n$, based on third constraint.

Finally, last constraint tells us that the maximum flow allowed for each edge is $1$.

This is the problem of sending a flow of value one from vertex $1$ to vertex $n$  subject to the constraints with a capacity limit of $1$ on each edge and the vector $b$ set to $0$.

I asked this question because I think a flow in this case can be viewed as a path, in which we can goes around it's cycles (if any cycle exists on the path) only once and it can't meet vertices $1$ and $n$ more than once. So, can we solve this problem using a modified version of Bellman-Ford or any other dynamic programming algorithm? Time order isn't the matter to me. I just don't want to use algorithms designed for the general form of minimum cost flow problem.

Minimum cost path

If you're looking for a minimum cost path, you can find that directly with Bellman-Ford.  Just let the weight on each edge $(i,j)$ be the cost $c_{ij}$, and ask Bellman-Ford to find for you the shortest path from the source to the sink; this will be exactly the minimum cost path (assuming there are no negative cycles in the graph).

Minimum cost flow

If you're looking for a minimum cost flow, one natural approach is to try using the Ford-Fulkerson method.  In each iteration of Ford-Fulkerson, you must find an augmenting path in the residual network.  In your particular case, you might try computing a minimum-cost augmenting path from the source to the sink.  Now what algorithm do you know that can compute a minimum-cost augmenting path in a digraph (potentially with cycles and potentially with negative-weight edges)?  That should be enough of a hint to give you something you can try.  Since it's your exercise problem, I'll let you work out the details and see if you can prove whether it works or not.

Alternatively, if conceptual simplicity is the goal, linear programming (LP) is one approach that is conceptually very simple and might apply to your porblem, and it has a polynomial running time.  LP immediately gives a solution to your problem (though possibly not with integer $x_{ij}$'s), and it's a well-known theorem that you can solve LP in polynomial time.  Of course, LP might be a "bigger hammer" than you want to throw at this.  Also, I don't know if LP will give you an integral flow, which you seem to want.  There's a standard theorem that says that, for the linear program associated with a maximum flow problem, there is always an integral solution to the LP that is optimal (you can't do better with non-integral flows).  I don't know if that carries over to the minimum-cost flow setting as well.


Conflict Driven Clause Learning combined with brute force I am learning about the Conflict Driven Clause Learning method to solve SAT problems. In this method it is possible to learn clauses and add these in the set of the initial clauses. I understand a learned clause as the negation of a conjunction of clauses such that these make a formula false (conflict).

I have thinking in another way to add learned clauses, in parallel way, to the set of learned clauses. That is, select a random set of assignments for the all variables of a formula $\phi$. If these assignments make the formula false then add this to the set of learned clauses, using negation operator. Sorry by my ignorance but, Do you know if is it reasoning valid?

For example in the next formula in Dimacs format

1 4 0
1 -3 -8 0
1 8 12 0
2 11 0
-7 -3 9 0
-7 8 -9 0
7 8 -10 0
7 10 -12 0

If 1=0 and 2=1 and 3=1 and 4=0 and 5=0 and 6=0 and 7=0 and 8=0 and 9=0 and 10=0 and 11=0 and 12=1 then $\phi$ is false. Then, the new set of formulas is

1 4 0
1 -3 -8 0
1 8 12 0
2 11 0
-7 -3 9 0
-7 8 -9 0
7 8 -10 0
7 10 -12 0
1 -2 -3 4 5 6 7 8 9 10 11 -12

Your reasoning is valid, but it won't help a SAT solver go much faster.  Your method produces long clauses that only forbid a single assignment.  What you want to speed up a recursively searching SAT solver is to learn short clauses that forbid many assignments.  That requires a more sophisticated learning strategy than adding a simple disjunction of the negation of the current variable assignment.


Are there programs that can 'translate' source code between any two languages? Are there programs that can 'translate' source code between any two languages (assuming the translator has access to the requisite libraries)?

If there are, how do they work (techniques used, knowledge required, etc)? How would they feasibly be constructed?

If they aren't, what are the restrictions preventing their development? Is this an A.I complete problem (natural language translation is listed as one)?

EDIT
Conversion is only expected, when the language has the same expression power, can solve the same kind of problems and the code to be converted can be expressed in the destination language. (E.g conversion from a shell script to MATLAB isn't expected).

TLDR; this is possible but not practical.

  (assuming the translator has access to the requisite libraries)?

This ends up being the tricky bit, and is part of why things like this don't end up being used in practice.

All compilers are translators. Translating from one language to another is definitely possible, and this is literally all a compiler is doing. The language that a compiler spits out as output is generally machine code or assembly, but this is just another language, and there are compilers (sometimes called transpilers or transcompilers) which translate between two languages. For example, there's a gamut of compile-to-Javascript languages like PureScript, Elm, ClojureScript, etc.
Translating between any two Turing Complete languages is always possible. Ignoring things like library calls and FFI and other nasty practical bits that get in the way, that is. If a language is Turing Complete, then you have:

A translation that converts a Turing Machine to code in this language
A translation from this language into a Turing Machine

So to translate from language A to language B, you convert the A code into a Turing Machine, then convert that machine into B code.

Of course, in practice, the practical bits get in the way, and this also requires you having the translations accessible to you. They exist for basically every language, but that doesn't mean someone has taken the time to write them out.
Doing this translation efficiently is hard. Different language prioritize different things. For example, if you translate from C to Python, you're probably going to have to end up simulating C's memory as a Python dictionary, so that you can do pointer arithmetic. There will be overhead associated with this, because you're now not accessing the bare metal memory instructions.

Different languages have difference performance priorities, so something that one language optimizes (or rather, an implementation of one language optimizes) might be impossible to do quickly in another language. Translating a functional language with proper tail calls will have slowdown if you translate it into a language without proper tail calls.
Doing this translation doesn't make the code readable. It's easy to get a piece of code in language B that behaves the same as the code from language A. It's hard to make it look like code a human would have written in B, for a number of reasons. A and B might have different abstraction tools, and the computer has no idea what makes code readable. This will be particularly true if you end up using the Turing Machine translation I described earlier.

This raises the question: what's the point of such a translation? If all you get at the end us a block of slow, unreadable code, why not just compile it to machine code and use some kind of FFI or inter-process communication to link the pieces together?

There are some exceptions to this. Sometimes you need things in a certain language (like JavaScript). Sometimes language are similar, and a sensible translation is easy. Sometimes a language is not meant to be run, but to have its code extracted into another language (such as Coq).

But in general, it's not a very practical thing.


Is it possible to convert LBA into DFA? Today I learned about an abstract class of machines called linear bounded automata.

It is intended to model real-world computers that have a limited amount of memory. I have always thought that real computers are DFAs due to the finite memory (but the DFA is a terribly poor abstraction).

Is it possible to convert LBA into an equivalent DFA by making every possible tape configuration into a state of the DFA?

No, you can't do this. A single LBA can process inputs of any possible finite length. For any individual input, there are only finitely many possible tape configurations but, over all possible inputs or all possible lengths, there are there are infinitely many possible tape configurations. A finite automaton can't have one state for each of these configurations.

In particular, LBAs can accept non-regular languages, such as $\{a^nb^n\mid n\geq 0\}$ so there are LBAs that can't be converted to a single DFA.

What you could do is produce an infinite family of DFAs, one for each possible input length. Each of these would have a finite number of states. However, such an infinite family could recognize any language – even undecidable ones! – because every language contains only finitely many strings of each length and every finite language is regular.


Analyze time series data to get min max over past period of time The algorithm should analyze measured time series data in realtime and should check if all values of the specified last period lay inside a specified range. The range is calculated with max-min over the specified time period.

Input data

t        | 10:00 | 10:01 | 10:02 | 10:03 | ... | 19:00 |
Temp [°C]| 40    | 41.3  | 39    | 43    |     | 45    |

Algorithm parameters

Duration D: Past time to check for min/max
Max range R: (max-min) < R

e.g: Check if the temperature was steady within 2 °C for the last hour. D=1hour, R=2°C

The algorithm should check periodically during data acquisition if the condition (all values of the last hour have been inside a range of 2°C) is true.

Other requirements

The sampling time can be from 10Hz to 50kHz.
The time will always be increasing.
Since this algorithm should run in an realtime environment there should be no memory allocations during run time

Possible solutions

At the moment I have two possible solutions but do not like both of them:

Store all values within the duration in a bounded fifo-buffer and perform a min/max check from start to end periodically. I expect this to be the worst solution
Store the tuples in two B-Trees:

There are two indexes

TimeIndex t->(t,v): Index from time to tuple,
ValueIndex v->list(t,v): Index from the value to a list of tuples with this value.

The algorithm will first get all tuples that are outside the time range and remove them in the value index.

Then the value index is updated with the newly measured tuples.

The range can then be determined by looking up the minimum and maximum key in the value index.

I think the second approach is faster but will allocate memory during runtime. Since it should run in a realtime environment I like to avoid allocations.

Is there another possibility with O(log n) and no allocations?

The following paper provides a O(1) algorithm:

D. Lemire, Streaming Maximum-Minimum Filter Using No More than Three Comparisons per Element, Nordic Journal of Computing, 13 (4), 2006 (https://arxiv.org/abs/cs/0610046).

An implementation of this algorithm is provided in the GNU Scientific Library (see https://www.gnu.org/software/gsl/doc/html/movstat.html).


How to produce all the numbers in a range [0,1,...,n] for which if 0<=k<=n, then for a positive integer x, the expression: k & x = k? I am trying to figure out an efficient way to produce all the numbers in a given range for which, their bitwise AND with a positive integer (say x) gives the same number; that means k & x = k.

Is there a better way to do it so that I do not need to go through all the numbers from 0 to n and check for it?

This answer shows how to find all values of $x$ satisfying the equation for fixed $k$. The OP asked for all values of $k$ satisfying the equation for fixed $x$, but the same methods work for both problems.

First of all, we have $k \& x = k$ if $x_i = 1$ whenever $k_i = 1$. If we think of $k,x$ as sets whose elements are the 1 bits, then the equation becomes $k \cap x = k$, which is equivalent to $k \subseteq x$, and so if $i \in k$ (i.e., $k_i=1$) then $i \in x$ (i.e., $x_i=1$).

In order to generate all solutions $x$ in the range $0,\ldots,n$, it suffices to generate all solutions in increasing order; we can stop once reaching a solution which is larger than $n$.
How do all solutions look like? Let the 0 bits of $k$ be $i_0 < i_1 < \cdots < i_\ell$. Then the solutions are
$$ k + \sum_{j=0}^\ell b_j 2^{i_j}, $$
where $b_j \in \{0,1\}$; we can replace addition equivalently with bitwise OR. Moreover, if we think of $b_\ell\ldots b_0$ as a binary number, then the mapping from $b_\ell \ldots b_0$ to $k + \sum_j b_j 2^{i_j}$ is monotone: as we go over all values of $b_\ell \ldots b_0$ in increasing order, the values of $k + \sum_j b_j 2^{i_j}$ appear in increasing order. This leads to the following algorithm:

Let $b \gets 0$.
Compute $x = k + \sum_j b_j 2^{i_j}$, where $b_j$ is the $j$th bit of $b$.
If $x \leq n$, output $x$, increase $b$ by 1, and go back to 2. Otherwise, halt.


Question about the Simon's algorithm This comes from trying to understand the "Simon's algorithm".

So we have a set of $2^n$ kets $|x_i \rangle$ one each for $i \in \{0,1\}^n$. Each $x_j \in \{0,1\}^n$. And we have the further constraint that $x_i = x_j$ iff $i = j + s \pmod{2} = j \oplus s$ (bitwise addition modulo $2$) for a certain $s \in \{0,1\}^n$. (so every $|x_k\rangle$ is guaranteed to have a second copy)

Now one has this state given as $\psi_a = \frac{1}{\sqrt{2^n}}\sum_{i \in \{0,1\}^n} |i\rangle|x_i\rangle $ So this is a state of some 2 qubit system.

Given this I want to understand why a measurement on the second qubit would necessarily collapse this to the state, $\psi_b = \frac{1}{\sqrt{2}} ( |j\rangle + |j \oplus s\rangle)|x_j\rangle$ for some $j \in \{0,1\}^n$?

Is this measurement of the second qubit state trying to measure some observable/Hermitian operator whose eigenstates are precisely these $\psi_b$s? Then it would make some sense that the only things one sees are these $\psi_b$ states.

But this would still not clarify the weird probability addition that is happening here as shown below.

One notes that the state $\psi_b$ will be obtained with a probability of $(\bar{\psi_b} \psi_a)^2 = (\frac{ 2}{ \sqrt{2^{n+1} }})^2 = 1/2^{n-1}$. These $\psi_b$s obviously do not span the entire $2^{2n}$ dimensional Hilbert space available to these two qubits. They are not a basis.

But the probabilities don't add up rightly either $\sum_b ( \bar{\psi_b} \psi_a )^2 = 2$. Wonder is the interpretation of the fact that the probabilites over all these possibilities seem to add up to $2$!
Some explanations I found say that these states $\psi_b$ being the only possibilities is forced because of the fact that the second qubit is being measured in the "computational basis". This argument is not clear to me.

I'm not sure I get all your questions. I'll try to answer according to my interpretation of what you are asking, and you can clarify if I got you wrong.

  Given this I want to understand why a measurement on the second qubit would necessarily collapse this to the state, $\psi_b = \frac{1}{\sqrt{2}} ( |j\rangle + |j \oplus s\rangle)|x_j\rangle$ for some $j \in \{0,1\}^n$?

First, there is no second qubit, but a second system (of $n$ qubits). Next, consider $\psi_a$, and recall that for any $f(x_j)$ there are only two preimages $j$ and $j\oplus s$, then if you measure $f(x_j)$ at the second system, the first system must either be $j$ or $j\oplus s$.

  Is this measurement of the second qubit state trying to measure some observable/Hermitian operator whose eigenstates are precisely these $\psi_b$s? Then it would make some sense that the only things one sees are these $\psi_b$ states.

Kind of. However, you don't measure $\vert\psi_a\rangle$ directly. There is another hadamard gate which is missing there. I.e., you measure
$$(H\otimes I) \left\vert\psi_a\right\rangle = \frac1{2^n}\sum_x\sum_i (-1)^{i\cdot x}\left\vert i\right\rangle\left\vert f(x)\right\rangle$$

Now if you re-arrange it properly, it should give
\begin{align*}
\frac1{2^n}\sum_{x\in\{0,1\}^n}\sum_i (-1)^{i\cdot x}\left\vert i\right\rangle\left\vert f(x)\right\rangle &=
\frac1{2^n}\sum_{j\in XS}\sum_i (-1)^{i\cdot j}\left\vert i\right\rangle\left\vert f(j)\right\rangle + (-1)^{i\cdot (j\oplus s)}\left\vert f(j\oplus s)\right\rangle \\
&=
 \frac1{2^n}\sum_{j\in XS}\sum_i \left ((-1)^{i\cdot j}+(-1)^{i\cdot j}(-1)^{i\cdot s}\right)\left\vert i\right\rangle\left\vert f(j)\right\rangle \\
&=
 \frac1{2^n}\sum_{j\in XS}\sum_i (-1)^{i\cdot j}\left(1+(-1)^{i\cdot s}\right)\left\vert i\right\rangle\left\vert f(j)\right\rangle
\end{align*}
Where $XS\subseteq \{0,1\}^n$ is the largest subset such that if $j\in XS$ then $\forall j'\in XS, f(j)\ne f(j')$; so that the sum over $j$ is only over half the space and  we don't count twice $x=j$ and $x=j\oplus s$. But note that $f(j)=f(j\oplus s)$ which we use in the second transition.

The above shows that for any $i$ for which $s\cdot i=1 \mod 2$ there is a destructive interference that cancels these terms, and you are left with only $i$'s for which $s\cdot i=0 \mod 2$. Thus, any $i$ you will measure (at the first system) must satisfy $s\cdot i=0 \mod 2$.


SLR parse table and unambiguity If it is possible to construct an SLR parse table with no conflicts for a particular grammar does that mean that the grammar is unambiguous?

I think that since we have constructed the parse table which means for every sentence we would be able to decide whether the string will be accepted or not. But I am a little bit confused on whether it is really true or not. Actually, I am trying to prove that a grammar is unambiguous and I constructed parse table with no conflicts.

As said in the comment by Yuval, an SLR parse table with no conflicts (or parsing deterministic finite automaton) for a particular grammar implies that the grammar is unambiguous.

In fact, that is true for most if not all popular parsing methods.

LL(k)
LR(k)
SLR(k)
LALR(k)

Here is the sketch of a proof for all parsing methods. A parse table or a parsing finite automaton specifies an algorithm to produce all leftmost derivations (or rightmost derivations) of the input sentence. If there is no conflict in the parse table or the finite automaton is deterministic, only one derivation can be generated. That means the grammar is unambiguous.

Note for a given sentence, there is only one leftmost derivation is equivalent to there is only one rightmost derivation.


How can I apply Rice's theorem? I am learning for my computability and complexity exam in which there is always an exercise to decide whether some problem is decidable or not.

In one of the past exams, there was the following problem:

Given Turing Machine M, decide whether there exists a prime number on which M halts.

I am supposed to decide whether the problem is decidable or not.

I guess I can rewrite the problem into the language $L = \{ \langle M \rangle | \exists p \in \mathbb{P} : M(p) \downarrow  \}$. I have been given a hint that I can use Rice's theorem to prove the language is undecidable. I am actually struggeling, since I have no idea how should I apply Rice's theorem to (generaly any) problem.

I am interested in these questions:

How can I find out whether Rice's theorem is applicable or not?
If I find it out, how to apply it? (In this excercise in particular)

Any help appreciated.

Here's another, elementary proof technique that does not use Rice's theorem which is way overkill for this simple problem.

We have Turing machine family $F(A)$ that goes into an infinite loop for any input except 2, in which case it will run program $A$, which can be arbitrary.

Now if we could decide your original problem we could decide for arbitrary inputless Turing machines whether they halt using $F$. But this is obviously undecidable and therefore your original problem is as well.


Does there exist an undecidable problem such that the answer is YES for exactly one input to a UTM, and NO for all others? Suppose I have a universal Turing Machine (UTM) which accepts some input in binary. Is there a computational problem such that the answer to the problem is YES (accepting) for exactly one input (and hence NO for all others), but determining which input is the accepting one is undecidable?
Or is there a fundamental reason this cannot happen? Or is determining if this  problem exists undecidable?

I assume this is equivalent to asking: is there a property of TMs such that this property is true for exactly one TM and not true for all others such that determining which TM this is true for is undecidable?

For every Turing machine over some language L, there is a set of words that it will halt and accept on and a set of words it will halt and reject on, if it does halt.

If $|L| = 1 $ then the Turing machine will accept on exactly one input.

Given an arbitrary M and some input, we cannot decide whether the program will halt; halting problem. However, since M is not arbitrary, it’s fixed,this is not the Halting problem. I believe an algorithm would only need to check if the input is equal to the first element in L.


Can there be a strict transaction that is not 2Phase? I am confused about the definition of a strict transaction. What is the difference between a transaction that is strict and a transaction that is both strict and 2 phase?

Strictness Strictness ($\textsf{ST}$) is related to recoverability. Serializability ($\textsf{SR}$) is one of many consistency conditions of transactions, which is somewhat orthogonal to recoverability. 2PL is a protocol usually used to ensure serializability.

First, I don't think the term "strict transaction" is proper. Strictness, just like serializability, is defined over executions (also called histories or schedules) of transactions.

Secondly, strictness is incomparable to serializability (there are various versions of serializability. I suppose you are referring to CSR --- conflict serializability).

Finally, your question "Can there be a strict transaction that is not 2Phase?" should be

  "Is there any execution which is strict but not serializable?"

The answer is "Yes". For example, $e = r_1(x) \; w_2(x) \; w_2(y) \; c_2 \; r_1(y) \; c_1$. You can check that $e \in \textsf{ST} \land e \notin \textsf{SR}$.


Finding the bandwidth of a band matrix I am designing an algorithm that solves a linear system using the QR factorization, and the matrices I am dealing with are sparse and very large ($6000 \times 6000$). In order to improve the efficiency of the algorithm, I am trying to exploit the sparsity of the matrix by finding its bandwidth, but I have to run through the matrix a lot of times to find it, and it is taking too long.

The main idea I am using to find the bandwidth is:

for each row, find the start(row) and end(row): these are the intervals in which the elements are different of $0$;
to find start(row): iterate from the beginning of the row until the element is not $0$;
to find end(row): iterate from the end of the row until the element is not $0$;

The problem is that I am running through many unnecessary $0$'s, but I can not figure out how to avoid this and guarantee a solid result. Thanks.

As a sparse matrix is mostly made of zeros.
Using a 2-dimensional array for all elements will be an inefficient way to represent such data as more than half of the array will be zeroes which is the reason for the increased time cost for finding bandwidth in your case.

In your case if you have a matrix $M$ of size $n * m$ then you'll be using a 2 dimensional array of size $n*m$. However it is not necessary to do so

A more efficient way will be to represent only the non zero elements using a 2 dimensional array with only three columns.e.g.

------------------------
 R    |   C    | V
------------------------
 0    |  0     |  1
------------------------
 0    |  3     |  4
------------------------
 1    |  5     |  11
------------------------
 .    |  .     |  .
------------------------
 .    |  .     |  .
------------------------
 .    |  .     |  .

Where R is the row of the nonzero element,C is its column and V is its value in a given matrix.

In this way if you have $t$ nonzero elements in the Matrix then you need to access only $3*t$ elements in the above 2-dimensional array.

Now you can find the maximum and minimum values of C for any row R and can calculate their difference.

The largest difference you'll come across will be the bandwidth.I hope it makes sense.


Prove (p → ¬q) is equivalent to ¬(p ∧ q) I need to prove the above sequent using natural deduction. I did the first half already i.e. I proved $(p\rightarrow\neg q)\rightarrow \neg (p \wedge q)$, but I'm stuck on where to start for the reverse i.e. proving $\neg (p \wedge q) \rightarrow (p\rightarrow\neg q)$. I figured I would start by assuming $\neg (p \rightarrow \neg q)$ and then working towards a contradiction, but I'm still at a dead end. Can someone point me in the right direction? Thanks.

Can we use that $a \to b$ is same as $\neg a \lor b$? If yes then:
$$\neg (p \wedge q) \rightarrow (p\rightarrow\neg q) $$
is same as
$$(\neg p \lor \neg p) \rightarrow (\neg p \lor \neg q)
$$


What properties does a co-RP problem need to be in P? Given an arbitrary language $L$ with an algorithm $A$ that places $L$ in $co-RP$ what other properties does the Algorithm $A$ need to have to so that $L$ is in $P$?

For example:

Considering $L$ is in $co-RP$ we have a guarantee that:

if $x \in L$ then $A$ accepts $x$ guaranteed $(P(A(x)=1) = 1)$

if $x \not\in L$ then $A$ accepts $x$ with a propability $f(n)$ $(P(A(x)=1) = f(n))$ with $n = |x|$ and $f(n) \geq 0$

What property does $f$ need to have so that $L$ is in $P$?

As $P \subseteq ZPP$ and $ZPP = RP \cap co-RP$ there needs to be a property to $f$ that places $L$ also in $RP$. As such there needs to be a way to construct an algorithm $B$ for $L$ that discards $x \not\in L$ guaranteed in polynomial time. Under what conditions for $A$ is this possible? For what $f$ is this the case? Is there any other property $A$ needs to have so that $L$ is in $P$?

Considering from my comment that there exists an upper bound to the runtime of $A$: $p(n)$ then there are only $2^{p(n)}$ possible ways a coin-flip of a randomized algorithm can manipulate the outcome of the result.

If the error propability of $A$ I described as $f$ is a fraction with part $\frac{g(n)}{2^{p(n)}}$ then creating a deterministic program that runs $g(n)$ many times plus one different paths of a possible computation of $A$ it is guaranteed that at least one of these paths would have identified the false positive as false.

Therefore we can skip the journey through $RP$ into $ZPP$ and can argue that if $g$ is a polynomial function we need to run $g(n) + 1$ times the polynomial Algorithm $A$ resulting in a polynomial runtime of $(g(n)+1) \cdot p(n)$ that deterministically solves $x\in L$ or $x \not\in L$ with an error propability of $0$, therefore placing $L$ in $P$.

This is but one case where, given a randomized algorithm that places a language $L$ clearly in $co-RP$ places $L$ also in $P$.


NP-completeness of graph isomorphism through edge contractions with an edge validity condition Given Graphs $G=(V_1,E_1)$ and $H=(V_2,E_2)$. Can a graph isomorphic to $H$ be obtained from $G$ by a sequence of edge contractions ? We know this problem is NP-complete. What about if only a subset of edges are valid for contraction at each step of the sequence. For example when deciding the first edge for contraction, there are only a subset $E'\subset E_1$ of edges eligible for contraction. If you pick $e\in E'$ for contraction and get an intermediate graph then when deciding the second edge for contraction in this intermediate graph there are a subset $E''$ of edges eligible for contraction and so on.

Does this problem stay NP-complete ?

The answer is yes.  Suppose that you had a polynomial-time algorithm to solve your revised problem.  Apply that algorithm to the special case where the subset of edges available at each step is the whole set.  We'd then have a polynomial time algorithm for the original, known NP-complete, problem.

To have any hope of dreaming up a non-NP-complete version, you'd need to put a restriction on the subsets that were eligible that would prevent an immediate reduction to the original problem.  At that point you'd have a new problem which you cannot easily show is NP-complete.  However it is in the nature of NP-complete problems that, if your restriction avoids 2+ choices at each step, it very likely to be NP-complete.

(Note, it is currently unknown whether the simpler problem of identifying whether two graphs are isomorphic is NP-complete.)


Does the concept of subtype require dynamic method binding? https://en.wikipedia.org/wiki/Subtyping says

  In programming language theory, subtyping (also subtype polymorphism or inclusion polymorphism) is a form of type polymorphism in which a subtype is a datatype that is related to another datatype (the supertype) by some notion of substitutability, meaning that program elements, typically subroutines or functions, written to operate on elements of the supertype can also operate on elements of the subtype.

In the concept of "subtype", when explaining "substitutability" as "program elements, typically subroutines or functions, written to operate on elements of the supertype can also operate on elements of the subtype", does it assume/require dynamic method binding (e.g. the one specified as virtual functions in C++)?

Specifically, given a type B with a method m(), a function

void f(B b){
    b.m();
}

and a subtype S of B which redefines m() method,  which does S being a subtype of B according to the meaning of "substitutability" in the wikipedia article mean:

either if calling f() with an instance s of S, then b.m() in f() will invoke S.m() instead of invoking B.m(), (this case   requires dynamic method binding.)
or if replace B with S in the definition of f(),

void f(S s){
    S.m();
}

still work, i.e. f() can operate with both B and S, i.e. "subtype" only requires  thatS also has a method m() with the same signature as B.m()? (This case doesn't require dynamic method binding.)

Thanks.

No. It doesn't even require a notion of "method" at all. Even if you have objects and methods, it doesn't necessarily require a notion of dynamic dispatch. Indeed, dynamic dispatch is only relevant if you can "override" methods (where, here, I'm [atypically] including implementing an interface as "overriding" [abstract] methods).

All subtyping states is if $t$ is a term of type $S$ then $t$ is also a term of type $T$ if $S\operatorname{\mathtt{<:}}T$. There are a variety of ways to implement this. For structural subtyping, usually the idea is that the sub-type is representationally compatible with the super-type so that their common interface literally refers to the same code. For example, if the 3-tuple $(A,B,C)$ is represented by contiguously storing a representation of $A$, $B$, and $C$, and similarly for a 2-tuple, then a 3-tuple literally is a 2-tuple that just happens to have a representation of $C$ following it. This is represented by $(A,B,C)\operatorname{\mathtt{<:}}(A,B)$. As another example, a sum/variant type $A+B+C$ could be represented as a tag indicating the variant and a representation of $A$, $B$, or $C$ as appropriate. If the tags are compatible, then a value of type $A+B$ literally is a value of $A+B+C$ leading to $A+B\operatorname{\mathtt{<:}}A+B+C$. Something like dynamic dispatch could be used internally to avoid relying on representational compatibility if desired by the language implementer.

Another approach would be to have subtyping imply the implicit insertion of coercions from sub-types to super-types. Dynamic dispatch is just completely irrelevant to subtyping in this context.

Common object oriented languages tend to conflate subtyping and subclassing, but they are fairly different concepts. Many (most?) programming languages that have some degree of "subtyping" fail to satisfy various notions of "substitutability", so the baseline is usually just that using a sub-type as a super-type typechecks and (usually) doesn't crash. (Even that low bar fails to be met by e.g. Java and C# and certainly C++.)

You could have a language that supports dynamic dispatch which doesn't have a notion of subtyping. For example, conversions to "super-types" could be explicit.


Proving a set is semi-decidable Let $S = \{ ⟨M,q⟩ | (\exists x) M $ reaches state $q$ when running $M$ on $x$$\}$, where ⟨M,q⟩ is coded TM M and state q.

To prove that $S$ is semi-decidable, I've tried to use the equivalence:

Language $L$ over alphabet $\Sigma $ is semi-decidable $ \iff $ There exists a semi-decidable language $M$, such that $L = \{x \in \Sigma ^ \ast| \exists y \in \Sigma ^ \ast ⟨x,y⟩ \in M\} $.

Let $L_H = \{ ⟨M, q, x⟩ ∣ M$ runs on $x$ $\& $ $M$ reaches state $q \}$ and let $H(⟨M, q, x⟩)$ be a TM which decides $L_H$. If we simulate $M$ and $M$ runs on $x$ and reaches state $q$, then H accepts and $⟨M, q, x⟩ \in L_H$, therefore all words in $L_H$ are accepted by $H$ and $L_H$ is semi-decidable. Is it enough to show that $S$ is also semi-decidable? What are other common ways to prove a language is semi-decidable?

You are missing a proof that $L_H$ is semi-decidable.

Here are two ways to prove that $S$ is semi-decidable.

First method. The following predicate is decidable: "$M$ reaches state $q$ after running on $x$ for $t$ steps". Hence the following is semi-decidable: "there exist $x,t$ such that $M$ reaches state $q$ after running on $x$ for $t$ steps".

Second method. On input $M$ and $q$, simulate $M$ on all possible inputs (by dovetailing); output $\langle M,q \rangle$ for each state $q$ reached by each of these simulations.


How do I compute the power consumption of a DRAM refresh? Given a DRAM-based memory system with a total capacity of $x$ bytes, $y$ DRAM rows and a refresh time of $t$ milliseconds, how do I compute the power consumption for one DRAM refresh? I couldn't find something concerning this question so far.

$P = I \cdot \Delta V$, meaning one has to find the current consumption $I$ and the difference in voltage $\Delta V$, often denoted by $V_{dd}$ of the respective DRAM, in this case one can choose an arbitrary DRAM since nothing is specified.


Getting the idea behind pumping length correct I am unsure whether I got the notion behind the pumping length correctly. I know its definition, and just want to make sure that I understood everything correctly.

Suppose we have an automata that accepts $0^{*}1^{*}$. The longest word accepted is $01$ without an iteration, whose length is $2$. So $n=2$, am I correct?

In case of $0......01^{*}$ where there are $n$ zeroes, the constant would be simply equal to $n+1$.

Is my thinking correct?

One thing that's worth pointing out is that there can be many lengths that satisfy the pumping lemma. In your example, setting the pumping length to 2 does satisfy the pumping lemma. And so does length 3, 4, 5, etc. I think what you're asking about is the minimum pumping length. The pumping lemma is generally used to show proof that a language is not regular, in which case it doesn't really matter what the minimum pumping length actually is, just that there is some finite pumping length.

Anyway, I believe that the minimal pumping length for 0*1* is actually one, not two. It's true that the 01 is the the longest word accepted without an iteration, but that's not precisely the definition of the pumping length. There are two possible words of length one:  0 and 1. Both of these words can be pumped, and as you've shown, any words of length two or more can be pumped. Therefore, any word of length one or more can be pumped, so the minimal pumping length is one.

For your second example, I assume you mean the language L = {0n 1* | n is a specified constant}. In that case I believe you're right that the minimum pumping length is n + 1. We can pump 0n1, but we can't pump 0n.


unambiguous grammar that produce equal number of a and b is there any unambiguous grammar on alphabet={a,b} that can produce strings which have equal number of a and b (e.g. "aabb" , "baba" , "abba") ?

The problem with $S\to aSbS\mid bSaS\mid \varepsilon$ is that you're just making sure you match each $a$ with a $b$ (where we consider an $a$ and a $b$ to be matched iff they appeared during the same derivation step).

To ensure non-ambiguity, you must add a constraint on the matching to ensure that it is unique (while maintaining its existence). One way to do that is to make sure you match the first $a$ (resp. $b$) after your $b$ (resp. $a$) that hasn't been matched yet.

So you'd get something like $$
S\to aB S\mid bA S \mid \varepsilon\\
A \to a \mid b \square\\
B\to b \mid a\square$$

The idea is the following:

You want $S$ to generate words with as many $a$ as $b$s. At any points you can stop with the $S\to \varepsilon$. If you do add an $a$ with $S\to aBS$, then you need to add a $b$ later, and you put a $B$ to remind you of that, and then you continue with another $S$. The same things applies for $S\to bAS$.
If you have an $A$, it means that you are one $a$ short. If you read an $a$, everything is fine and you've got nothing else to do. But if you read a $b$, you are now two $a$s short. I left a $\square$ for you to fill to encode that.
$B$ works like $A$.

Solution :

   You are two $a$s short so you are twice one $a$ short: $A \to a \mid b AA$. Similarly $B\to b\mid aBB$

For the proof, see this where $a,b,A,B$ are replaced with $0,1,O,I$ and your language is generated by $E$.


Data normalization when control has multiple values in CS/CE (This question was originally posted at https://academia.stackexchange.com/questions/68675 but was considered too specific for Academia.)

In computer science/engineering research papers relating to performance improvement wherein execution time is normalized to control benchmarks (i.e. speedup plots), how is that normalization generally implemented when the control(s) is/are executed multiple times in order to avoid the possibility of other processes/interrupts/etc. taking processor time and skewing the results? My first thought would be to just use the minimum time achieved for each benchmark, but as that would probably not be the minimum possible execution time in most cases and, depending on the situation, overall execution time rather than best-case execution time may be more important, is it better to just accept the skewing and go off the means? Or is it better to use the median for each set of results?

One simple approach is to use the median.  It is less sensitive to outliers than the mean, but still serves as a good summary of typical running time.  Alternatively, you could use the mean but in that case you should inspect all the results yourself to check for the possibility of outliers.  I personally would recommend the median.

Papers often show confidence intervals as well, so that you can assess the effect of statistical noise.

Normally, benchmarks are run on an isolated system to minimize interference from other tasks.

Note that there are many challenges with benchmarking.  Even simple irrelevant changes can cause significant changes to performance, e.g., because they happened to change cache alignment to something that is randomly better or worse.  Therefore, it can be difficult to separate out whether your optimization led to a 3% performance improvement because your optimization is an improvement, or if that's just randomness (e.g., just recompiling with slightly different settings can change the running time by +/- 3%, and you happened to get unlucky once and lucky the other time).


Calculating Tag Bits in a Direct-Mapped Cache The following comes from Patterson & Hennessy Computer Org. and Design (5th ed., p. 390):

  How many total bits are required for a direct-mapped cache with 16 KiB
  of data and 4-word blocks, assuming a 32-bit address?

My question is, how can we determine the tag bits based on the book's answer?

The answer shows the following:

  We know that 16 KiB is 4096 (212) words. With a block size
  of 4 words (22), there are 1024 (210) blocks.
  Each block has 4 $\times$ 32 or 128 bits of data plus a tag, which
  is 32 $ - $ 10 $ - $ 2 $ - $ 2 bits  [emphasis added].

I see that 32 is the assumed address size (in bits); 10 is the index (log2 of 1024); and 2 bits are the offset; however, what are the other 2 bits subtracted from 32?

Since Hennessy & Patterson uses MIPS architecture as the basis for all its examples, we can assume that this example is no exception. MIPS is byte addressable. Hence a byte offset of 2 bits (to address the four bytes in the 32-bit word size) need to be included in the 32 bit address.

These 2 bits occupy the least significant two bits of the 32 bit address's binary representation. Hope that helps!


extend ECMAScript by adding new keywords and syntax I would like to extend ECMAScript by adding new keywords and syntax to it, for example:

|variableName| stipulates a special kind of variable which I would like to be able to include in a normal ECMAScript line of code, for example:

|variable1| = 1 + 1
|variable1| = |variable2|.length - 3

a more complex one would be:

@SpecialObject[propertName:propertyValue,..., propertyNameN:propertyValueN] {
    {|variable1| == true} => {
        console.log("condition 1 applies")
        |variable1| = false
    }
    .
    .
    .
    {|variable2|.length !== 0} => {
        console.log("variable 2 contains elements")
        |variable2| = Date.now()
    }
}

I have built an initial prototype by impementing my own lexer and parser (using Chevrotain), but it is quite limited as it only supports those specific constructs of my new syntax, what I would like to do is to make it more powerful by being able to include ECMAScript code in my syntax, how could it be done?

I know of two plausible approaches:

One approach is to start with a lexer and parser for ECMAScript and modify them.

Another approach is to build your own preprocessor that takes as input a program with your syntax, and transforms it to EMCAScript which can be accepted by an existing interpreter (by replacing instances of |variable| with something that does fall within the normal ECMAScript syntax).  Since you haven't told us anything about the semantics of the |variable| syntax, I can't make any suggestions for a specific transformation to apply, but you might be able to work one out.


Weakly NP-complete problems and strongly NP-complete problems I'm still confused with the terms Weakly NP-complete and strongly NP-complete.
Many people states that weakly NP-complete problems are the problems with time complexity growing as a polynomial in the magnitude of the input, while strongly NP-complete problems are the problems with time complexity growing as a polynomial in the size of the input.
Does this make checking whether a number is prime or not (which is always considered as polynomial-time problem) a weakly NP-complete problem since its time complexity is growing as a polynomial in the magnitude of the input but as an exponential in the size of the input?

Many problems involve integers, for example in the form of integer weights. There are two common ways to encode integers:

Binary encoding, or more generally base B encoding for some constant B.
Unary encoding, in which (ignoring signs) $n \geq 0$ is encoded as $0^n1$.

A problem is weakly NP-complete if it is NP-complete when weights are encoded in binary. It is strongly NP-complete if it is NP-complete when weights are encoded in unary. For example, SUBSET SUM is weakly NP-complete but not strongly NP-complete, whereas BIN PACKING is strongly NP-complete.

Every strongly NP-complete problem is also weakly NP-complete since the reduction which changes the encoding of integers from unary to binary runs in polynomial time. The reduction in the other direction, in contrast, could run in exponential time.

Primality testing can be done in polynomial time in both unary and binary encodings, though in the latter case it's a highly non-trivial result known as the AKS primality test.


When can a deterministic finite-state-automaton (DFSA) along with its input sequence be said to be a part of another DFSA? For a Finite State Automaton / Finite State Machine (FSM) $F$, that has an input alphabet, a set of possible states, an initial state, a set of possible final states and a state transition function, let a finite input sequence $S$ is given, such that at the end of this sequence the FSM enters a final state and stays in that state.
Can this FSM $F$ along with the input sequence $S$ be considered a separate FSM $F'$?
Analogous to this, can a Turing machine $T$ along with a finite tape $P$ be considered a separate Turing  machine $T'$?
What are the conditions, if any, for this to be true assuming it is true?
Note: I expect a formal proof, or a reference/outline to a formal proof that proves that either of this can or cannot be done. Some theory related to this is also welcome.
My research:
Closely related topic:
R. T. G. TAN (1979) Hardware and software equivalence, International Journal of Electronics, 47:6, 621-622, DOI: 10.1080/00207217908938690

I am aware of the principle of hardware and software equivalence, which states that a given task can be performed using hardware or software, i.e. digital hardware and software are equivalent models of computation. But I think my question is different from this one.
Motivation:

From this question (
Is there code below microcode? ) I think we can consider an FSM with its input sequence (microcode) to be a part of another FSM (the digital computer), but of course much more circuitry like Arithmetic and Logical Unit (ALU) and datapath is needed to make a computer. Microcode is used only for the control circuit.

This answer claims the data in the RAM of a computer along with the CPU can be considered to be a part of a bigger circuit.

To quote:

The circuit is fixed (it is the gates in the processor) and part of its input is data that depends upon the program you are executing (which is stored in the RAM of the computer). However, you could consider this a larger circuit where part of it is hardcoded (i.e., the program part of the input is hardcoded); then you can view a computer running a program as a big circuit with part that is universal and identical for all programs (the gates of the processor) and part that depends on the program (the hardcoded input), and this immediately gives a mapping from programs to circuits. The mapping is implemented by a compiler.

It's not clear to me how to interpret "can be considered", so I'm going to identify one technical question that can be answered.
Given a FSM $F$ and an input sequence $S$, it is possible to build another FSM $F'$ so that the execution of $F'$ on the empty input is in one-to-one correspondence with the execution of $F$ on $S$ (and in particular, both end at the same end state(s); e.g., either $F$ accepts on $S$ and $F'$ accepts on the empty input; or $F$ rejects on $S$ and $F'$ rejects on the empty input).
The proof is a straightforward application of the product construction: we construct one FSM $F_0$ that outputs the fixed sequence $S$, and then compute the parallel composition of $F_0$ with $F$.
The following is also true: given a Turing machine $T$ and a fixed input $P$ (i.e., initial state of the tape $P$), then it is possible to construct another Turing machine $T'$ such that execution of $T$ on input $P$ has the same result as execution of $T'$ on any input.
Formal proofs with Turing machines are often tedious and uninformative, so it's easier to see how this is true by considering a real-world program.  For instance, suppose we have Python code that defines some function t():
def t(x):
    ...

and we have some fixed string p.  Consider the following Python function t':
def t(x):
    ...
def t'(x):
    return t(p)

Then it is easy to see that the behavior of t' on any input is equivalent to the behavior of t on input p.  (Here we have hard-coded a lexical constant string in the place indicated with p above.)  You can do the same thing with Turing machines, where the machine first writes $P$ on the tape, and then starts executing $T$, to define a Turing machine $T'$ that proves the claim above.


Proving that the language of satifiable CNF formulae with primes is NP-complete Given the following language:

  $$L=\left\{\langle\phi, n\rangle \ \middle|\  \begin{array}{l}\phi\text{ is a satisfiable Boolean formula}\\ \text{written as POS (in CNF form)}\\ \text{and $n$ is a prime number}\end{array}\right\},$$

  Prove that L is an NPC language.

This is the first time I'm trying to solve this kind of questions, and I am stuck.

This is what I have so far:

To prove that a language is NPC, I need to prove two things:

1) $L \in \mathrm{NP}$

2) For any $L'\in \mathrm{NP}$, there exists a poly-time reduction from $L'$ to $L$.

To prove (1), can I say that $\phi$ is NP (because we know that SAT is NP), and that $n$ is P (because Prime is P)?

If so, I think that I need to say that $\mathrm{P} \subseteq \mathrm{NP}$ to complete the proof of (1).

What's next?

For 1): You have to prove that the language is solvable by a nondeterministic TM in polynomial time. The easiest way is indeed to use previously defined TMs, e.g. the TM to solve SAT. So your approach is correct.

For 2): You don't have to prove it for every $L'$ $\in$ $NP$ explicitly, it suffices to give a reduction from a language that is NP-complete. The idea is that you reduce every word $w' \in L'$ to a word $w \in L$, so if you find an efficient way to solve $L$, you also have an efficient way to solve $L'$. So you can choose any NP-complete language that should provide a simple reduction to $L$.

The next step therefore would be to choose such NP-complete language $L'$.

Next you have to find a reduction $f$ to reduce your previously chosen language $L'$ to your language $L$. Depending on your choice of $L'$, this can be a very simple process in your case. Note that $\{$ $f(w') \mid w' \in L \} \subseteq L$, not $\{$ $f(w') \mid w' \in L \} = L$


Need help understanding this optimization problem on graphs Has anyone seen this problem before? It's suppose to be NP-complete.

  We are given vertices $V_1,\dots ,V_n$ and possible parent sets for each vertex. Each parent set has an associated cost. Let $O$ be an ordering (a permutation) of the vertices. We say that a parent set of a vertex $V_i$ is consistent with an ordering $O$ if all of the parents come before the vertex in the ordering. Let $mcc(V_i, O)$ be the minimum cost of the parent sets of vertex $V_i$ that are consistent with ordering $O$. I need to find an ordering $O$ that minimizes the total cost: $mcc(V_1, O), \dots ,mcc(V_n, O)$.

I don't quite understand the part "...if all of the parents come before the vertex in the ordering." What does it mean?

You can think of the parent sets as incident nodes; that is if $V_i$ is in the parent set of $V_j$, there is a (directed) edge from $V_i$ to $V_j$.

An ordering "consistent" with this graph in the sense of the exercise is a topological sorting, that is a topological ordering $V_{\pi(1)}, \dots, V_{\pi(n)}$ has no pair $(i,j)$ with $i<j$ so that there is an edge from $V_{\pi(j)}$ to $V_{\pi(i)}$.

The problem is then to find an ordering as consistent with the graph as possible.


Doubts about infinite language decided by a turing machine Assume you have an infinite language $L$ over alphabet $\Sigma=\{a,b\}$
For example, $L=\{ax \mid x \in \Sigma^*\}$

Can a Turing Machine, $M$ decide this language?

(Generalizing, are all the recursive languages finite?)

In my opinion, it can, since I can enumerate all the strings and say if they are in the language or not. However, enumerating all the strings will take infinite amount of time, so I will never end up enumerating them.

Can someone clarify this doubt?

Some infinite languages are decidable, some are not. The algorithm that you give, however, doesn't work, for two reasons:

When the input is not in a language, you never find out.
It is not always possible to enumerate all the words in $L$. A language $L$ for which this is possible is known as recursively enumerable (r.e.), and by many other terms. An example of a language which is not r.e. is the language of encodings of Turing machines which don't halt on the empty input. That is, $\langle M \rangle$ is in the language if $M$ never halts when running on the empty input.

In your specific example, there is a very simple Turing machine accepting $L$. The Turing machine examines the first symbol, accepts if it is $a$, and rejects otherwise.


Prove the recursive enumerability of the class of NP-hard context-free languages I was asked to prove that the next language is recursive enumerable :

$$L= \{ \langle G \rangle \mid SAT<L(G) \} $$

where $G$ is a context free grammar and there is a polynomial reduction from the SAT problem to the language that's accepted by $G$.

I can't seem to understand why this problem is in RE. Isn't determining whether a word is accepted by a certain CFG done in a polynomial time? What am I missing here?

You should distinguish between two cases. If $\mathsf{P} \neq \mathsf{NP}$ then $L(G)$ cannot be $\mathsf{NP}$-hard since $L(G) \in \mathsf{P}$. In this case, $L = \emptyset$.

Conversely, if $\mathsf{P} = \mathsf{NP}$, then all non-trivial languages in $\mathsf{P}$ are $\mathsf{NP}$-hard. In this case, $L = \{ \langle G \rangle : L(G) \neq \emptyset, \Sigma^* \}$. It is possible to decide whether $L(G) \neq \emptyset$, and the problem of determining whether $L(G) \neq \Sigma^*$ is clearly r.e. (in fact, it is $\Sigma_1$-complete), and so $L$ is r.e. (in fact, $\Sigma_1$-complete).


Can element uniqueness be solved in deterministic linear time? Consider the following problem:

Input: lists $X,Y$ of integers

Goal: determine whether there exists an integer $x$ that is in both lists.

Suppose both lists $X,Y$ are of size $n$.  Is there a deterministic, linear-time algorithm for this problem?  In other words, can you solve this problem in $O(n)$ time deterministically, without using randomness?

Unfortunately, you cannot assume that the list elements are all small.

I can see how to solve it in $O(n)$ expected time using a randomized algorithm: randomly choose a 2-universal hash function $h$, store the elements of $X$ into a hashtable (using $h$ as the hash function), and then look up each element of $Y$ to see if it is in the hashtable.  The expected running time will be $O(n)$.  However, I can't see how to find a deterministic algorithm with $O(n)$ running time.  If you try to derandomize this and fix a single specific hash function, there will exist a worst-case input that causes this procedure to run in $\Theta(n^2)$ time.  The best deterministic algorithm I can find involves sorting the values, but that won't be linear-time.  Can we achieve linear running time?

Also, I can see how to solve it in linear time if you assume that all of the list elements are integers in the range $[1,n]$ (basically, do counting sort) -- but I am interested in what happens in the general case when we cannot assume that.

If the answer depends on the model of computation, the RAM model jumps to mind, but I'd be interested in results for any reasonable model of computation.  I'm aware of $\Omega(n \log n)$ lower bounds for decision tree algorithms for element uniqueness, but this isn't definitive, as sometimes we can find linear-time algorithms even when there is a $\Omega(n \log n)$ bound in the decision-tree model.

You can solve the problem in linear time if you have enough memory to have a bit for each possible value in X and Y.  This does not impose any restrictions of the ordering of X and Y.

Initially all bits are unset.
Iterate over X setting the corresponding bit.
Iterate over Y checking if the corresponding bit was set above.


Are files download times actually unknowable due to the halting problem? When downloading a file from the internet to our computer we are usually prompted with an estimate of how long it will take for the file to be downloaded.
From the Halting Problem, we know that $\mathrm{HALT}_{\mathrm{TM}}$ is undecidable, where:
$\mathrm{HALT}_{\mathrm{TM}} =\{⟨M,w⟩\mid M \text{ is a TM and }M\text{ halts on input }w \} $
Assuming that we can neglect the lack of infinite memory, we can model our computer writing on the disk as a Turing Machine $M$ and take the string encoding of the downloaded file as the input $w$. (More precisely, $w$ should be the string obtained composing the packets sent by the network)
From the Halting Problem it follows that it's not only impossible to know when the download will end, it's even impossible to know whether the download will ever end.
So, are files download times actually unknowable due to the halting problem? If not, where the above reasoning fails?

Not at all.
The halting problem says it is impossible to decide whether an arbitrary turing machine with arbitrary input will halt. But there are many, many specific turing machines where we can prove that they halt for every input, or where we can look at the input and decide if the turing machine will halt or not.
And since the people writing the download code surely wrote it in such a way that it is guaranteed to finish for every import, there will be a proof that it is guaranteed to finish.


Linear Bound Automaton Power Please tell me is their deterministic linear bound automaton same power as non-deterministic linear bound automaton to recognize any language?

Your question is equivalent to asking whether or not $DSPACE(O(n)) = NSPACE(O(n))$, which is an open problem, known as the first LBA problem.


Shortest path with nodes containing collectibles of negative cost Suppose you have a graph with weighted edges and nodes. Edges always have non-negative costs (representing e.g. fuel costs), and nodes always have non-negative benefits (representing e.g. collectible fuel tanks). A path from A to B is a series of contiguous edges starting at A and finishing at B. The net cost of a path is the sum of the weights of edges (including multiplicity) on the path minus the sum of the benefits of the distinct nodes (ignoring multiplicity) on the path.

In principle paths are permitted to visit a node more than once, but the node's benefit is only ever collected once (i.e. you can't pick up the same fuel can twice).

Is there an efficient algorithm to find a minimum cost path from A to B in this situation? What if you're promised that the input contains no paths from A to B with net negative cost? What if you're happy with heuristics that perform well when nodes containing 'fuel' are scarce?

This is NP-Complete, by reduction from Traveling Salesman Problem (TSP).

Take any TSP.  Give every city an extremely large "negative-benefit," and set the origin city as both the start and finish.  Now running a solver for your problem will give the solution to the TSP.

I'm not sure of any "efficient heuristics", but if you remove the condition that nodes are allowed to be visited twice, the problem becomes much easier.  If you subtract every nodes' "negative benefit" from all its incoming edges, it becomes a normal shortest path problem.


Build a tree for $(-\infty,+\infty)$ similar to dyadic interval trees for $\left[0,+\infty\right)$ Using dyadic intervals, I can build a binary tree for $\left[0,+\infty\right)$ by having a node the $i$-th at level $l$ representing the range
$\left[i\cdot2^l,(i+1)\cdot2^l\right)$ and has the $(i)$- and $(i+1)$ at level $l-1$ as children.

I would like to build a similar tree for $(-\infty,+\infty)$, but it is not clear to me how this can be done using a single tree. One solution would be to use two binary trees as described above, one for positive and one for negative numbers. Is there a solution that uses a single tree? The tree does not have to be binary, but it would be good if there is a bound on the branching factor.

The intended use of this is to maintain information about floating point values. That is, $l$ can also be negative. It can be used, for example, to do approximate percentile queries. See for example: https://github.com/twitter/algebird/blob/develop/docs/src/main/tut/datatypes/approx/q_tree.md and https://github.com/twitter/algebird/blob/develop/algebird-core/src/main/scala/com/twitter/algebird/QTree.scala.

Maybe the surreal numbers will work as dyadic intervals.
Surreal numbers have a reduced form containing a left and right surreal which is like a range.
I think these ranges match the description of "dyadic intervals" in the link you provided.
Nan (the empty set) is considered to be positive or negative infinity depending on whether it is on the left or right side of the reduce surreal form.
The bit form of these dyadic intervals will be the right/left path down the surreal tree diagram (https://en.wikipedia.org/wiki/Surreal_number)
They start like this:
Surreal No.  Tree path  Binary Form   Reduced Form    Interval
   0            nan
   1            ""            1           {0|0}      {-inf,+inf}
   2           "L"           10           {0|1}      {-inf,0}
   3           "R"           11           {1|0}      {0,+inf}
   4           "LL"         100           {0|2}      {-inf,-1}
   5           "LR"         101           {2|1}      {-1,0}
   6           "RL"         110           {1|3}      {0,1}
   7           "RR"         111           {3|0}      {1,+inf}

You would also have to imagine that half way between + and - infinity is zero. Then half way between zero and +inf is 1. Then half way between 1 and +inf is 2. etc for all integers. Maybe that makes it unsuitable.
I am unsure whether surreal numbers are related to your question. I had already noticed that the surreal numbers have a quality of half ranges when I read your post.
Edit:

a "1" bit is prefixed to the L/R path of the given surreal. Where L=0 and R=1. Ex:-1/2 is LR on the surreal tree diagram. LR converts to 01 and then we prefix a "1" to get "101". 101 is the binary form of the LR path.
Surreal numbers are listed as their birth number. Not their value number. Their values of their left/right reduced sides are used to determine the ranges they represent.
I can provide python code which produces these list if you want to see how these numbers and ranges are created.
the example provided above was made by hand and certainly contains mistakes.


amortized analysis of max heap Q) Consider an ordinary binary max-heap data structure with n elements that supports insert and extract-max in $O(log(n))$ worst-case time. Give a potential function $\Phi$ such that the amortized cost of insert is $O(log(n))$ and the amortized cost of extract-max is $O(log(n))$, and show that it works.

solution

The formula of amortized cost is

$a_n = c_n + \Phi(D_n)  - \Phi(D_{n-1})$

Where the potential function: $\Phi (D_n) = n log(n)$.

for insert:

$= c_n + \Phi(D_n) - \Phi(D_{n-1}) \leq log(n) + n log(n) - (n-1)log(n-1) \leq 3 log(n+1) = O(log(n))$

So, the amortized cost of insert is $O(log(n))$

extract max:

$a_n = c_n + \Phi(D_n) - \Phi(D_{n-1}) \leq log(n) + n log(n) - (n+1)log(n+1) = log(n) + n(log(n)) - n log(n+1) - log(n+1) < 0$

So, the amortized cost of extract-max is $O(1)$

Assuming this is correct. Could someone explain how they got the potential function?

When doing amortized analysis with a potential function, the potential function appears out of nowhere.  One way to come up with a potential function is to try picking some function, and then see if the calculation goes through.  If that doesn't work, one can try adjusting the potential function to make the calculation go through.  Sometimes we might let $\Phi(\cdot)$ be a placeholder, see what properties it needs to have to make the proof go through, and then try to come up with a function that has those properties.

In other words -- there is not necessarily any systematic way to find a potential function that works.  You might need to use trial-and-error, or a lucky guess, or other methods.


IEEE754 representation in hexadecimal? In class, I've heard hexadecimal representation for IEEE754 mentioned and described in 32bit length as a format that consists of one bit for sign, normalized 6-digit fraction (with an implied leading zero) and biased (+64) 7bit exponent, leading me to believe it's not just a made up spec.

However, googling the actual IEEE754-2008 standard, I've found only 5 basic formats for base 2 and base 10 in it (binary32, binary64, binary128, decimal64, decimal128) and some more interchange formats for these two bases, but no mention of representation in base 16. Could that specification be some rejected proposal which is difficult to find now or am I missing something here?

Hexadecimal notation is just a shortcut writing one hexadecimal digit instead of four bits. For example 1A is exactly the same as 00011010. So eight hexadecimal digits give you the same as the binary32 format.

What you describe may be that someone takes one sign bit, 2 hex digits for the 8 bit exponenent, and 6 hex digits for the 23 bit mantissa. That would be possible but a bit misleading.


decidability about intersection of regular language and context free language Is "Given a CFL L and a regular language R, is intersection of L and R an empty set?" decidable? What if we replace L with the complement of L? One of them is decidable and the other is not. For the one that is decidable, give an algorithm. For the other, give an undecidability proof.

For the first part "Given a CFL L and a regular language R, is intersection of L and R an empty set?", I have the following idea. I think it is decidable because an intersection of context-free language and regular language is context-free, and then we can build context-free grammar G from the langauge. For a given CFG G, checking whether the language(G) is empty or not is decidable.

But I have one thing that I'm not sure of. For given context-free language, how can a Turing machine build context-free grammar? As far as I know, there is no known procedure for doing this. If there is no general procedure for building context-free grammar, I think the above proof is invalid.

But I read a proof of theorem "Every context-free language is decidable" from Sipser textbook, and the proof says that for any arbitrary CFL A, we build a grammar G that recognizes A, and we have to include this description of G into our machine. I guess this could work because CFL is fixed, but the above machine needs to take any arbitrary CFL L and regular language R.

It is known that the intersection of a regular language and a context free one is context free. Besides, you can always take your regular language to be $\Sigma^*$, so any context free language can be the result.
Then the question is if a given context free language is empty, which is easy to answer.
To ask if the complement of a context free language is empty is to ask if it is $\Sigma^*$, which is undecidable.


Must you work with all qubits in a circuit when applying a gate? When looking at this question:
How to apply a 1-qubit gate to a single qubit from an entangled pair?

And other questions, it makes it seem like when you have a quantum circuit involving $N$ qubits, that when you want to peform a gate operation on a subset of the qubits, that you must still make a matrix that applies to all qubits.

Is this always true, or is it only true in the case where qubits are entangled?

In other words... is it only entangled qubits that we have to process together, or must all qubits in a circuit be processed together?

You can apply a quantum gate on any subset of the qubits, not affecting the rest.

This can be formalized as evolving certain qubits via $U$ while the other qubits evolve via $I$, thus the joint unitary is $U \otimes I$.


Can I write a regular expression or regular grammar for this language? Let's say I have a formal language,

  a^n b^n which mean ab,aabb,aaabbb

Can I write any regular expression or grammar to create a language like this? I am positive not entirely sure that there is not regex possible, however have no idea about the grammar part?

This language is context-free but not regular. It is isomorphic to the problem of matching open and closed parentheses: (n)n which is a well-known non-regular language. To prove this yourself, you would use the pumping lemma for regular languages.

Every regular grammar describes a regular language.
This language is not regular.
Therefore, there cannot be a regular grammar that describes it.


Can a non-RE language be reduced to an RE language? Let $L$ be recursively enumerable and $U$ be non-recursively-enumerable. Is it possible to reduce $U$ to $L$ recursively, $U\leq_R L$? Personally, I do not think this is possible. If we can reduce $U$ to $L$ by a Turing machine that always halt and we also have an Turing machine that compute $L$ (may not halt), then we connect these two parts, we will have a Turing machine to compute $U$. Then $U$ is also recursively enumerable.

I was asked to show some language $L$ is recursively enumerable first, which was OK. But afterwards, I was asked to show some language which is known not recursively-enumerable, $L_{diag}=\{w_i|M_i\text{ does not accept } w_i\}$ can be reduced to it. I.e. $L_{diag}\leq_R L$ which does not make sense to me.

As you say, no non-RE language $U$ can be reduced to any RE language $L$, because, then, we could recognize $U$ using the reduction and the recognition algorithm for $L$.

The language $L_{diag}$ that you mention is indeed non-RE: it's the complement of an RE set that isn't recursive.  There is no recursive reduction from $L_{diag}$ to $L$.


Creating a temp array vs passing one in Mergesort In my CS class, we've discussed two ways of dealing with the temporary array required for the merging phase of mergesort. One of them is to pass a full-size temporary array as a parameter, e.g. merge(array, tempArray, first, last), and another is to create a temporary array of appropriate size (or two half-sized arrays) in the function call, e.g.

merge(array, first, last):

...
leftArray = items from first to middle
rightArray = items from middle+1 to last
...

My CS professor is of the opinion that the first option will somehow have a performance (speed/memory) improvement over the second, but I don't understand why. Merging the arrays is a "tail" operation in mergesort, and so the second option doesn't seem like it will actually require more memory overall. Is the only reason why because memory allocation takes time?

Thanks!

Memory management would be the only reason. In the second approach, you need to create $2n$ arrays total size of about $2n\log{n}$. If it is happening with a large $n$ or very small computing unit, you will face serious performance issues.
Finally, you have to be careful with memory when you work with recursive functions. It easily cause memory overflow.


Is $BQP$ in $P^{NP}$? I read in the introduction of this paper

http://www.scottaaronson.com/papers/uncompute.pdf

that there is a problem $B$ such that $BQP^B \not\subset P^{NP^B}$, and that $B$ is in $BPP$. But, using the fact that $BPP$ is in $BQP$ and that $BQP$ is low for itself (i.e. $BQP^{BQP}=BQP$), as proved in

http://arxiv.org/pdf/quant-ph/9701001v1.pdf

can we state that $BQP^B \subseteq BQP^{BPP} \subseteq BQP^{BQP} = BQP$ and thus $BQP \not\subset P^{NP^B}$ and finally $BQP \not\subset P^{NP}$?

I think your logic is valid, but not sound.
The problem is that the oracle $B$ is not what's in $BPP$. The question being asked about $B$ is what's in $BPP$.
When Scott Aaronson's paper "Quantum Lower Bound for Recursive Fourier Sampling" says

Green and Pruim [10] gave an oracle B for which $BQP \not\subset P^{NP}$. [...] while Green and Pruim’s problem is in BPP

the noun phrase "Green and Pruim’s problem" is not refering to $B$.
The Problem
The referenced paper "Relativized Separation of EQP from $P^{NP}$" defines a problem $L$.
The input to $L$ is a predicate $B$ and a range parameter $n$. The predicate $B$ accepts natural numbers between $2^n$ and  $2^{n+1}$, and returns either true or false for each. It is promised that $B$ will return true for either exactly $\frac{1}{4} 2^n$ of the allowed inputs, or else for exactly $\frac{3}{4} 2^n$ of them.
The output $L(B, n)$ is the classification of the relevant range of $B$ into the promised quarter-true or quarter-false categories.
The Separation
A $P^{NP}$ machine can't compute $L$ because $B$ has too many inputs to check. There's exponentially many spots to check (w.r.t. $n$), so eventually any accepting path must be leaving a huge proportion unchecked. An adversary can start with some arbitrary accepting input, simulate the proposed $P^{NP}$ machine to find out which inputs the machine checks on one path that accepts that input, then toggle inputs that that particular path didn't check to create a should-be-non-accepting input that fools the machine into accepting.
(Note: I implicitly assumed that $B$ could be inspected only by querying it. This fails e.g. if $B$ is provided as a circuit diagram. That's why $B$ will end up being our oracle.)
A $BPP$ machine can compute $L$ easily: just sample $B(x)$ at a random allowed $x$ and return that. The odds of getting it wrong are $\frac{1}{4}$, which is less than the typical-but-arbitrarily allowed $\frac{1}{3}$. You can sample more to make it more reliable.
A $BQP$ machine can also compute $L$, with the $BPP$ strategy.
An $EQP$ machine can use Grover's algorithm to solve $L$ with certainty. (Also works for BQP, but overkill.)
The Oracle
So we have a decision problem $L(B, n)$ that separates $P^{NP}$ and $BQP$, but relying crucially on the assumption that the machine is limited to querying $B$. Furthermore, we don't have enough input space to specify all of $B$'s outputs, and we can't use a compact representation like a program or circuit because that violates the only-querying-allowed assumption. Thus we're forced to cheat and give $B$ to the machine as an oracle.
This raises the issue of how to pick $B$. What if we picked a weak $B$, such as one where $L(B, n)$ is always $0$? Something that a $P^{NP}$ machine could be hardcoded into defeating? Fortunately we can get around that by choosing $B$ with diagonalization: iterate all $P^{NP}$ machines and use the $2^i$ to $2^{i+1}$ range of $B$ to defeat the $i$'th machine by the adversarial method I explained earlier.
Thus $B$ is an oracle that tells you something about how $P^{NP}$ machines try to query predicates, not an oracle about solving some problem in $BPP$. So it is not necessarily the case that $B \subset BPP$. It's probably not the case, actually, since computing a bounded version of $B$ involves simulating exponentially many $P^{NP}$ machines.


Question on word probability for hierarchical softmax used in natural language processing I am reading the following paper: https://papers.nips.cc/paper/5021-distributed-representations-of-words-and-phrases-and-their-compositionality.pdf

On page 4 of the paper they describe the hierarchical softmax which is intended to reduce the computational complexity (I believe only during training time) of training a neural network to learn word vectors. The hierarchical softmax output layer is a balanced binary tree.

Here is the description given in the paper for computing $p(w\vert w_I)$ (where $w_I$ is the input word or set of words, and $w$ is the missing word we are trying to predict):

More precisely, each word $w$ can be reached by an appropriate path from the root of the tree. Let $n(w,j)$ be the $j$-th node on the path from the root to $w$, and let $L(w)$ be the length of this path, so $n(w,1)=root$ and $n(w,L(w))=w$. In addition, for any inner node $n$, let $ch(n)$ be an arbitrary fixed child of $n$ and let $\lbrack x \rbrack$ (can't figure out how to generate brackets used in paper) be $1$ if $x$ is true and $-1$ otherwise. Then the hierarchical softmax defines $p(w_O \vert w_I)$ as follows:

$$p(w\vert w_I) =\prod_{j=1}^{L(w)-1}\sigma(\lbrack n(w,j+1)=ch(n(w,j))\rbrack \cdot v_{n(w,j)}'^T v_{w_I})$$

where $\sigma(x) = 1/(1+\exp(-x))$.

Now, I understand that we are using the sigmoid function to essentially "squish" the dot products of our two vector arguments in values between $0$ and $1$ (i.e. probabilities). But, I don't understand the user of the indicator function in this equation. Going down the tree I feel like we should be multiplying probabilities at each branch, and somehow I know the indicator function must be "steering" us down the tree, but I cannot tell how. Intuitively, I feel like it would be more appropriate to have an indicator function that outputted $\sigma(x)$ or $(1-\sigma(x))$ based on left or right turns.

I have figured out my confusion.

The indicator function is $\lbrack x \rbrack$ is set to output a $-1$ or a $1$ based on the argument being false or true, respectively.

When the authors say "let $ch(n)$ be an arbitrary fixed child of node $n$", they mean arbitrary in the sense of left child or right child. But in order for our function to work, we must decide on this arbitrary decision. So, let us assume $ch(n)$ ouputs the left child of unit $n$.

Then as we go down our tree, if $\lbrack n(w,j+1) = ch(n(w,j))\rbrack = 1 $ it means the next node on our path is to the left of the parent node $n(w,j)$ and if $\lbrack n(w,j+1) = ch(n(w,j))\rbrack = -1$ it means that the next node is to the right of $n(w,j)$.

As a result, since we defined $ch(n)$ to indicate the left child, all left probabilities are calculated as $\sigma(v_{n(w,j)}'^T\cdot v_{w_I})$ since $\lbrack n(w,j+1) = ch(n(w,j))\rbrack = 1 $. Now we know that the probability on the right must then be   $1 -\sigma(v_{n(w,j)}'^T\cdot v_{w_I})$. This is where I was confused since the function outputs $\sigma(-v_{n(w,j)}'^T\cdot v_{w_I})$. But let $a=v_{n(w,j)}'^T\cdot v_{w_I}$ and we can verify that $\sigma(-a)=1-\sigma(a)$.

We have $\sigma(a) = \frac{1}{1+e^{-a}}$, now observe that

$\begin{align*}
1 - \sigma(a) &= \frac{1+e^{-a}}{1+e^{-a}}-\frac{1}{1+e^{-a}}\\
&=\frac{e^{-a}}{1+e^{-a}}\\
&=\frac{1}{e^a}\times \frac{1}{1+e^{-a}}\\
&=\frac{1}{1+e^a}\\
&=\frac{1}{1+e^{-(-a)}}\\
&=\sigma(-a).
\end{align*}$

Hence the function $$p(w\vert w_I) =\prod_{j=1}^{L(w)-1}\sigma(\lbrack n(w,j+1)=ch(n(w,j))\rbrack \cdot v_{n(w,j)}'^T v_{w_I})$$

simply multiplies probabilities along the branches corresponding to the path from the root node to the proper leaf node $w$.


Given a DCEL, how do you identify the unbounded face I have constructed a DCEL using the procedure described in How do I construct a doubly connected edge list given a set of line segments?.

This correctly identifies all faces, however I'm struggling to come up with a way to identify the unbounded face surrounding my graph.

So far my only idea is that by building a polygonal representation of every face, I  could find the face polygon which 'contains' all the others, but this seems kind of messy.

Take any extreme vertex (say among the vertices having the minimum x-coordinate, the one that minimizes y). This vertex is  incident to two edges touching the outer face. Namely the first and the last half-edges leaving this vertex. The first one has the outer face on its right and the last one on its left.


What is the regular expression to the given language? I can't really find out, how can the following given Language be written down with regular expressions

$
L = \{ a^{3k-1} b^n a^{2t} \mid n > 0; k, t\ge1 \}
$

I had some guesses, but I don't know how to express the part $a^{3k-1}$ of the Language.
Probably it should look something like this:

$(aaa)^+$ [something] $b^*(aa^+)$

Look at the three parts of your language:

For the $a^{3k-1}$ part, we have possibilities $a^2, a^5, a^8, \dots$. For this part we'll have any 2 $a$s plus a multiple of 3 $a$s. That's expressible as $aa(aaa)^*$.
The $b^n$ part is easy, it's just $b^+$, since you need $n>0$.
The $a^{2t}$ part is likewise easy. Since $t\ge 1$ we can express this as $(aa)^+$.

Now concatenate these three regular expressions.


Binary representation of 129 when using 8bits for two's complement? I have this confusion regarding binary representation of decimal value 129 (or even 128). If 8 bits are used to represent numbers when doing the two's complement, then we know that '00000000' to '01111111' are used for 0 to 127 and leading 1 is used for negative numbers i.e. 1xxxxxxx where x is any combination of 0's and 1's to represent the value of that negative number.
But then how is 128 represented in 8 bits because the first bit is reserved for telling the number is negative (basically a signed number)?

The range of integers representable in 8 bits using two's complement is –128 to +127.

If instead the numbers are unsigned, then the range becomes 0 to 255.


Regular Expression for even-odd language of string I am new to Automata theory and would to make a regular expression for "even-odd" strings, defined over $\Sigma = \{a,b\}$, which is the set of strings with even numbers of $b$'s and odd number of $a$'s. I am also interested in constructing a DFA and NFA for the language.

I tried

  Even number of $b$'s = $(a^{\ast}ba^{\ast}ba^{\ast})^{\ast}$

Edit: I got  DFA and NFA for odd number of $a$'s and even numbers of $b$'s and still unable to make regular expression which will allow only even number of $b$'s and odd nubmer of  $a$'s .
I also tried this Regular Expression

  $(a(bb)^{\ast}(aa)^{\ast})^{\ast} $

Note: From above RE only  those strings are generated which start from a but i want that RE which generate string of even number of $b$'s and odd number of $a$'s regardles of starting from a or b

Constructing a DFA (and thus an NFA), is quite trivial, so let's focus on the regular expression. (well, you can always convert a DFA into a regular expression, but this will not be very insightful, is it?)

Let's start simple. How do we construct an expression that describes only even length strings (over $\{a,b\}$)? Or even more simple, how to construct an expression for a language of only even length strings over $\{a\}$?

If there's only $\{a\}$ in the alphabet, we either have none, or they come in groups of two, so a possible answer is $(aa)^*$.
When we have both $a$ and $b$, things become a bit more difficult. For instance, $(ab)^*$ is incorrect, since it doesn't allow $aa$. On the other hand, any expression of the form $(a^*b^*)^*$ not going to work, since we can't control the number of each letter. However, as before, we know that the letters must come in groups of 2, thus we should expect the form to be something like $(xy)^*$ with $x,y$ describing only even length strings, but what should $x,y$ be in this case? Well, we can just write all possible options, getting:

$$ ( aa+ ab+ ba+ bb)^*$$
(can you make it shorter?)

Now let's ask how do we get odd-length strings. Again, if the alphabet has only $a$, this would be quite easy - we can construct an even string, and add another $a$, getting:
$$ (aa)^*a$$

A similar approach works for the case where the alphabet is of size two:
$$ ( aa+ ab+ ba+ bb)^*(a+b)$$

Now a sanity check: we add the "a" or "b" only at the end. Maybe it comes in the middle, and not in the end?! Convince yourself that adding at the end is equivalent, and gives the right answer.

Finally, try to use the above ideas to solve your question. There is still some leap left, so don't give up too fast. Some hints:

    Hint1: the length of the final string must be odd (if it contains both letters)

.

    Hint2: get rid of one letter, so the length is even, and furthermore, both letters appear an even number of times!

.

    Hint3: don't forget to put back the one letter you got rid of. Convince yourself you placed it in the correct place...


Solve the following recurrence-relations: $T(n)=5T(n/3)+T(2n/3)+1,T(n)=2T(\sqrt{n})+\log_2(n)$ Solve the following recurrence-relations:
my attempet for the first one was doing upper bound and lower bound by changing for lower $6T(n/3)+1$ and for upper $6T(2n/3)+1$  but i didn't get the same order for $\Theta$
$T(n)=5T(n/3)+T(2n/3)+1,T(1)=c$
$T(n)=2T(\sqrt{n})+\log_2(n),T(4)=2$
I'm not sure if I solved this right but:
setting $y(n)=T(2^n)$ we get
$y(n)=2T(\sqrt{2^n})+\log_2(2^n)=2y(n/2)+n$ using the master's theorem we get that $y(n)=\Theta(nlogn)$ and therefore $T(n)=\Theta(log(n)loglog(n))$
And for the first recurrence i still don't know

Now that we know the answer, we could simplify the proof.
Let's prove that $$T(n)\in\Theta\left(n^2\right)$$
Define $k=k_n$, index of $n$ in base $3/2$, to be the smallest $k$ such that $n/(3/2)^k<1$.

Upper bound:
Assume that $C$ is very large such that $T(1)\leq C=C\cdot1^2$, $1-3C<-C/2$, and that for all $k<K$ and all $m$ with index $k$ we have $$T(m)\leq C(m^2-1/2)$$
Note: We are going to use the $-1/2$ to carry out the induction as it was done in the other answer.
Let $n$ be of index $K$. Then $n/3$ and $2n/3$ are of index smaller than $K$. It follows that
$$\begin{align}T(n)&=5T(n/3)+T(2n/3)+1\\
&\leq 5C(n/3)^2-5C/2+C(2n/3)^2-C/2+1\\
&=Cn^2\left(5/3^2+(2/3)^2\right)+1-3C\\
&=Cn^2+1-3C\\
&\leq Cn^2-C/2\\
&=C(n^2-1/2)\end{align}$$

Lower bound:
Assume that $D$ is such that $D>0$, $T(1)\geq D\cdot 1^2=D$, $1-3D\geq -D/2$, and that for every $k<K$ and $m$ of index $k$ we have $$D(m^2-1/2)\leq T(m)$$
Let $n$ be of index $K$. Then $n/3$ and $2n/3$ are of index smaller than $K$. Therefore,
$$\begin{align}
T(n)&=5T(n/3)+T(2n/3)+1\\
&\geq 5D((n/2)^2-1/2)+D((2n/3)^2-1/2)+1\\
&=Dn^2\left(5/3^2+1/(3/2)^2\right)-5D/2-D/2+1\\
&=Dn^2+1-3D\\
&\geq D\left(n^2-1/2\right)
\end{align}$$

By induction we have proven that for all $n$ we have $$D(n^2-1/2)\leq T(n)\leq C(n^2-1/2)$$
Therefore, $$T\in \Theta(n^2-1/2)=\Theta(n^2)$$


Sudoku Puzzles in O log n time although inefficient Suppose, I got a hypothetical fixed list of all possible general Sudoku puzzles.  I then create the pseudo-code to demonstrate the algorithm.

The algorithm does a search to compare the indexes of elements
in the puzzle that are not listed as zero.
In other words, all the possible listed Sudoku
grids are compared until a solution is found matching solution sharing the elements with the
same index.

--

tuple=[.......]

tuple=[.......]

all possible Sudoku grids.

Here's our solver.

solver = input('enter the puzzle like this 10000030004000...)

if Element with Same Index solver == tuple1, tuple2,...

print (solution containing exact elements that share the indexes in
       both the solution and puzzle)

Will this algorithm solve all Sudoku Puzzles in O log n time?

Such an algorithm can solve Sudoku, but it will be very slow in practice.

By definition, Sudoku is on a 9x9 grid, so there are only a fixed (finite) number of possible puzzles.  Your algorithm encodes all of them.  Therefore, your algorithm takes constant time, i.e., $O(1)$ time.

What this is telling you is that asymptotic analysis is not a useful tool for analyzing the running time of a Sudoku solver, as asymptotic running time focuses on how the running time grows as you increase the size of the input.  With Sudoku, you can't increase the size of the input; the size of the input is fixed.  Thus it doesn't even make sense to talk about asymptotic running time for solving Sudoku puzzles.

Some people do analyze a generalization of Sudoku, where instead of a 9x9 grid, we have a $k^2 \times k^2$ grid, where $k$ can be any integer.  Then one can consider asymptotic running time.  However, your algorithm can't be applied to this generalization of Sudoku, as there are infinitely many puzzles for this generalization, so you can't hardcode them all in the code of your algorithm -- every algorithm must be of finite length.  Thus, in that setting, while asymptotic analysis does apply, your algorithmic approach no longer works.


Number of nodes in Van-Emde-Boas tree of universe size u? The universe size $u$ in vEB trees is square rooted at each level until $u = 2$. So, unlike search trees, the branching factor is different at each level.

The height of the tree is $h = \lg \lg(u)$ and $u$ is an even power of 2, $u = 2^{2^k}$. I tried to calculate the count using the sum:
$$\sum_{i=1}^{h-1} 2^i\,2^{i + 1}$$
But it doesn't work. Any idea on how to do the math?

Edit:
Sorry for the confusion that might be caused by the illustration. The illustration is based on the CLRS book's implementation of VEB trees, but the summary nodes are not shown.
Thinking again about it now, I would like to know the count of all the nodes including the summary nodes and their tree nodes, as well as, the count of just the nodes without the summary.

The nice picture in the question does not include the summary nodes nor the min and max fields, both of which are indispensable components of a van Emde Boas tree (vEB tree). A better illustration might be the following picture taken from how to read off the set represented by a van-Emde-Boas tree, which was drawn by Raphael based on a figure in CLRS, where a number in orange is drawn at a min field that marks its presence in the set of integers being represented.

How many nodes are there in the vEB tree implemented like the illustration above?

There are $1 + 5 + 5 \times 3 = 21$ nodes in the illustration above.

For the sake of simplicity, let $w=2^h$ and $u=2^w=2^{2^h}$. A vEB tree over the universe $\{0,1,\cdots, u-1\}$ is of depth $h=\log\log u$.

There is one node of depth 0, which is the root node.
There are $2^{2^{h-1}} + 1$ nodes of depth 1.
Each node of depth 1 has $2^{2^{h-2}} + 1$ child nodes of depth 2.
...
Each node of depth i has $2^{2^{h-i-1}} + 1$ child nodes of depth $i+1$.
...
Each node of depth $h-1$ has $2^{2^{h-h}}+1=3$ child nodes of depth $h$.

In total, the number of all nodes is
$$1 + \sum_{i=1}^{h}\prod_{k=1}^i(2^{2^{h-k}} + 1)=(2^{2^h} - 1)\sum_{i=0}^{h}\frac1{2^{2^i} - 1}\tag{1}$$
which is 1, 4, 21, 358, 92007, 6029862760, 25898063359598159721, $\cdots$ for $h=0,1,2,3,4,5,6,\cdots$ respectively. When $h\ge4$, the number of nodes is about $1.404u$.

Similarly, the number of all summary nodes is, for $h\ge1$,
$$1 + \sum_{i=2}^{h}\prod_{k=1}^{i-1}(2^{2^{h-k}} + 1)=(2^{2^{h}} - 1)\sum_{i=1}^{h}\frac1{2^{2^i} - 1},\tag{2}$$
which is 0, 1, 4, 21, 358, 92007, 6029862760, $\cdots$ for $h = 0,$$1, 2,3,4,5,$$6,\cdots$ respectively.

What is the number of all non-summary nodes? Subtracting (2) from (1), we obtain

$$(2^{2^{h}} - 1)\left.\frac1{2^{2^i} - 1}\right|_{i=0}=2^{2^h}-1=u-1.$$

The formula also hold for $h=0$. So we have obtained the following surprising formula.
$$\text{the number of non-summary nodes in a vEB tree of universe size } u=2^{2^h}\text{ is }u-1.$$

Every node at the same depth use the same amount of space. Nodes at a smaller depth may use much more space than those at a larger depth. For example, for $h=5$, the root node contains a bit-array of size 65536 but a leaf node just contains several words. Since the number of nodes that use bigger space decreases very quickly as their depth becomes smaller, the total space used is $O(u)$.

Exercise. The number of all leaf nodes, which are vEB trees of universe size 2 in a vEB tree of universe size $u=2^{2^h}$ is $u-1$.


Automatic Downcasting by Inferring the Type In java, you must explicitly cast in order to downcast a variable

public class Fruit{}  // parent class
public class Apple extends Fruit{}  // child class

public static void main(String args[]) {
    // An implicit upcast
    Fruit parent = new Apple();
    // An explicit downcast to Apple
    Apple child = (Apple)parent;
}

Is there any reason for this requirement, aside from the fact that java doesn't do any type inference?

Are there any "gotchas" with implementing automatic downcasting in a new language?

For instance:

Apple child = parent; // no cast required

Upcasts always succeed.

Downcasts can result in a runtime error, when the object runtime type is not a subtype of the type used in the cast.

Since the second is a dangerous operation, most typed programming languages require the programmer to explicitly ask for it. Essentially, the programmer is telling the compiler "trust me, I know better -- this will be OK at runtime".

When type systems are concerned, upcasts put the burden of the proof on the compiler (which has to check it statically), downcasts put the burden of the proof on the programmer (which has to think hard about it).

One could argue that a properly designed programming language would forbid downcasts completely, or provide safe casts alternatives, e.g. returning an optional type Option<T>. Many widespread languages, though, chose the simpler and more pragmatic approach of simply returning T and raising an error otherwise.

In your specific example, the compiler could have been designed to deduce that parent is actually an Apple through a simple static analysis, and allow the implicit cast. However, in general the problem is undecidable, so we can't expect the compiler to perform too much magic.


Determining the particular number in $O(n)$ time and space (worst case) $\newcommand\ldotd{\mathinner{..}}$Given that $A[1\ldotd n]$ are integers such that $0\le A[k]\le m$ for all $1\le k\le n$, and the occurrence of each number except a particular number in $A[1\ldotd n]$ is an odd number. Try to find the number whose occurrence is an even number.

There is an $\Theta(n\log n)$ algorithm: we sort $A[1\ldotd n]$ into $B[1\ldotd n]$, and break $B[1\ldotd n]$ into many pieces, whose elements' value are the same, therefore we can count the occurrence of each element.

I want to find a worst-case-$O(n)$-time-and-$O(n)$-space algorithm.

Supposing that $m=\Omega(n^{1+\epsilon})$ and $\epsilon>0$, therefore radix sort is not acceptable.
$\DeclareMathOperator{\xor}{xor}$
Binary bitwise operations are acceptable, for example, $A[1]\xor A[2]$.

Here is an idea for a simple algorithm; just count all occurrences!

Find $m = \max A$. -- time $\Theta(n)$
"Allocate" array $C[0..m]$. -- time $O(1)$¹
Iterate over $A$ and increase $C[x]$ by one whenever you find $A[\_]=x$. If $C[x]$ was $0$, add $x$ to a linear list $L$. -- time $\Theta(n)$
Iterate over $L$ and find the element $x_e$ with $C[x_e]$ even. -- time $O(n)$.
Return $x_e$.

All in all, this gives you a linear-time algorithm which may use (in the sense of allocating) lots of memory. Note that being able to random-access $C$ in constant time independently of $m$ is crucial here.

An additional $O(n)$ bound on space is more difficult with this approach; I don't know of any dictionary data-structure that offers $O(1)$ time lookup. You can use hash-tables for which here are implementations with $O(1 + k/n)$ expected lookup time ($n$ the table's size, $k$ the number of stored elements) so you can get arbitrarily good with linear space -- in expectation. If all values in $A$ map to the same hash value, you are screwed.

On a RAM, this is implicitly done; all we need is the start position and maybe the end position.


Python: Clustering based on pairwise distance matrix I have a matrix which represents the distances between every two relevant items. For example, M[i][j] holds the distance between items i and j. My next aim is to cluster items by these distances.
I can provide some parameters: maximal number of clusters, maximal distance between two items in a cluster and minimal number of items in a cluster.
I cannot, however, provide the "central items" which the algorithm should start with.
I went through some of python's clustering packages, like scikit-learn, but did not find anything that matches.

Any ideas?

Thank you :)

The constraints you have are not very clear (why should you start with "central items" ?). You should maybe try to come up with a well defined problem by precisely defining the clustering(s) you are looking for.

For example, if the clustering you want is such that the maximum number of clusters is $k_{max}$ and the maximum distance between two elements in a cluster is $d_{max}$, one possible approach is to perform a Complete-linkage Hierarchical clustering of your items. Possible clusterings then correspond to cuts in the resulting dendogram. Most library include the possibility of finding a cut that correspond to $k$ clusters or at a "height" $d$. A cut at height $d_{max}$ corresponds to the smallest clustering that respect the distance constraint. If the latter is not possible with the library you are using, you can explore every cut from size $1$ to size $k_{max}$ and select one that respects the distance constraint (Note it may not always be possible to found one e.g. with  $d_{max}$ close to $0$ and $k_{max}$ close to $1$.)