REC and RE under intersection Would the intersection of a recursive language and a recursively enumarable language be recursive or recurisvely enumbarable or neither?

Assume $L_{3}$ is the intersection of some language $L_{1}$ $\epsilon$ RE and some other language $L_{2}$ $\epsilon$ REC .

Since $L_{2}$ $\epsilon$ REC, there must be a Turing-Machine $M_{2}$ that holds on every input, whethere or not the input x $\epsilon$ $L_{2}$.
If we now have a k-NTM $M_{3}$ that on one band simulates
$M_{2}$ and upon acceptance of the input switches to another band where it then simulates $M_{1}$ (for $L_{1}$).

Since $M_{1}$ is only ever simulated if $M_{2}$ accepts the input, $M_{1}$ only gets the chance to hold for every word x $\epsilon$ $L_{1}$ $\bigcap $ $L_{2}$.

That means we can already assume that we wont get stuck in a loop for words x $\notin $ $L_{2}$.

However that is not the case for words that are in the intersection or only in $L_{2}$ and not in $L_{1}$, as the simulation of $M_{1}$ wil also be recursively enumarable and may run forever, without us ever knowing whether the input is accepted or not.

If my thoughts so far were correct, that means that  $L_{3}$ $\epsilon$ RE.

What I am uncertain about is if there is any sort of algorithm or technique with which we could make the simulation of $M_{1}$ decidable, or if maybe it is possible to make an entirely new TM, independent from $M_{1}$ and $M_{2}$ and make sure it is decidable?

You have been going well. Yes, $L_3=L_1\cap L_2\in\text{ RE} $.

Could it be that $L_3$ is recursive?

The answer is not necessarily. There are several cases here.

If $L_1$ is a recursive language as well, then $L_3$ is also recursive.
If $L_1$ is not a recursive language, then $L_3$ may or may not be recursive.

For example, let $L_2$ be the languages of all words. Then $L_3=L_2$ is not recursive.
For example, let $L_2$ be the language that does not contain any word. Then $L_3$ is also the language that does not contain any word, which is recursive.

Exercise 1. Show that if both $L_1$ and $L_2$ are recursive, then $L_1\cap L_2$ is recursive.

Exercise 2. Construct two languages $L_1$ and $L_2$ that satisfy all following conditions.

$L_1$ is recursively enumerable.
$L_2$ is recursive and $L_2$ is not the language of all words.
$L_1\cap L_2\subsetneq L_1$ is recursively enumerable but not recursive.


Does the order in which qubits are measured matter in quantum computing? I’ll define my question more specifically:

Lets suppose we have an $n$ bit quantum computer, with qubits labelled $q_{1},…,q_{n}$, and let $b$ be any bit string of length $n$ (let’s assume we’ve labelled each qubits’ states $0$ and $1$ so that we obtain an $n$ bit bit string when we measure the qubits).

The question is, is the probability that we obtain $b$ when we measure each qubits’ state dependent on the order in which we measure the qubits?
I have a feeling the probability would be independent of the order the qubits are measured, but am struggling to prove this.

No, the order doesn't matter.

Proofs

Algebra. Take an input state $\sum_k c_k |k_0 k_1 k_2 ...\rangle$. Apply the definition of measurement from your textbook to it. Compute the expression for the probabilities and outputs of each case when measuring qubit 0 then qubit 1. Do the same for measuring qubit 1 then qubit 0. Notice that the two expressions are equal. Generalize.
Circuit moves. Measurement is equivalent to a CNOT gate from the target qubit onto an ancilla qubit that you simply don't use for anything else:

So if you think you can change the outcome statistics by reordering measurements, you should think you can do the same without involving measurements at all (until a simultaneous measurement of all qubits at the end of the circuit). All you should need is independent CNOTs. But clearly independent CNOTs can be re-ordered.
Play. For me, the fact that ordering doesn't matter wasn't proven so much as experienced. I dragged gates around in Quirk and noticed that measurement is easily the most boring operation. All measurement does is throw away off-diagonal density matrix elements. Even for the target qubit, measurement doesn't change the computational basis probabilities.


Example for Database architecture PHPMyadmin is stated as a 3 tier database architecture.How is  this possible,Isn't it a 2 tier architecture.What are the real world examples of 1-tier and 2-tier architecture.

"3 tier database architecture" is a bit of misnomer, as database by itself doesn't have extra tiers. So what are the 3 tiers? From outter-most to inner most, they are:

presentation,

application processing,

data management.

https://example.net is literally 1-tier since it doesn't have application processing and data management, it just presents a text permitting you to use that domain name in documentations.
FTP would be a 2-tier protocol since it doesn't have application processing.


Simulating a probability of 1 of 2^N with less than N random bits Say I need to simulate the following discrete distribution:

$$
  P(X = k) =
\begin{cases}
\frac{1}{2^N}, & \text{if $k = 1$} \\
1 - \frac{1}{2^N}, & \text{if $k = 0$}
\end{cases}
$$

The most obvious way is to draw $N$ random bits and check if all of them equals to $0$ (or $1$). However, information theory says

$$
\begin{align}
S & = - \sum_{i} P_i \log{P_i} \\
  & = - \frac{1}{2^N} \log{\frac{1}{2^N}} - \left(1 - \frac{1}{2^N}\right) \log{\left(1 - \frac{1}{2^N}\right)} \\
  & = \frac{1}{2^N} \log{2^N} + \left(1 - \frac{1}{2^N}\right) \log{\frac{2^N}{2^N - 1}} \\
  & \rightarrow 0
\end{align}
$$

So the minimum number of random bits required actually decreases as $N$ goes large. How is this possible?

Please assume that we are running on a computer where bits is your only source of randomness, so you can't just tose a biased coin.

Wow, great question!  Let me try to explain the resolution.  It'll take three distinct steps.

The first thing to note is that the entropy is focused more on the average number of bits needed per draw, not the maximum number of bits needed.

With your sampling procedure, the maximum number of random bits needed per draw is $N$ bits, but the average number of bits needed is 2 bits (the average of a geometric distribution with $p=1/2$) -- this is because there is a $1/2$ probability that you only need 1 bit (if the first bit turns out to be 1), a $1/4$ probability that you only need 2 bits (if the first two bits turn out to be 01), a $1/8$ probability that you only need 3 bits (if the first three bits turn out to be 001), and so on.

The second thing to note is that the entropy doesn't really capture the average number of bits needed for a single draw.  Instead, the entropy captures the amortized number of bits needed to sample $m$ i.i.d. draws from this distribution.  Suppose we need $f(m)$ bits to sample $m$ draws; then the entropy is the limit of $f(m)/m$ as $m \to \infty$.

The third thing to note is that, with this distribution, you can sample $m$ i.i.d. draws with fewer bits than needed to repeatedly sample one draw.  Suppose you naively decided to draw one sample (takes 2 random bits on average), then draw another sample (using 2 more random bits on average), and so on, until you've repeated this $m$ times.  That would require about $2m$ random bits on average.

But it turns out there's a way to sample from $m$ draws using fewer than $2m$ bits.  It's hard to believe, but it's true!

Let me give you the intuition.  Suppose you wrote down the result of sampling $m$ draws, where $m$ is really large. Then the result could be specified as a $m$-bit string.  This $m$-bit string will be mostly 0's, with a few 1's in it: in particular, on average it will have about $m/2^N$ 1's (could be more or less than that, but if $m$ is sufficiently large, usually the number will be close to that).  The length of the gaps between the 1's are random, but will typically be somewhere vaguely in the vicinity of $2^N$ (could easily be half that or twice that or even more, but of that order of magnitude).  Of course, instead of writing down the entire $m$-bit string, we could write it down more succinctly by writing down a list of the lengths of the gaps -- that carries all the same information, in a more compressed format.  How much more succinct?  Well, we'll usually need about $N$ bits to represent the length of each gap; and there will be about $m/2^N$ gaps; so we'll need in total about $mN/2^N$ bits (could be a bit more, could be a bit less, but if $m$ is sufficiently large, it'll usually be close to that).  That's a lot shorter than a $m$-bit string.

And if there's a way to write down the string this succinctly, perhaps it won't be too surprising if that means there's a way to generate the string with a number of random bits comparable to the length of the string.  In particular, you randomly generate the length of each gap; this is sampling from a geometric distribution with $p=1/2^N$, and that can be done with roughly $\sim N$ random bits on average (not $2^N$).  You'll need about $m/2^N$ i.i.d. draws from this geometric distribution, so you'll need in total roughly $\sim Nm/2^N$ random bits.  (It could be a small constant factor larger, but not too much larger.)  And, notice is that this is much smaller than $2m$ bits.

So, we can sample $m$ i.i.d. draws from your distribution, using just $f(m) \sim Nm/2^N$ random bits (roughly).  Recall that the entropy is $\lim_{m \to \infty} f(m)/m$.  So this means that you should expect the entropy to be (roughly) $N/2^N$.  That's off by a little bit, because the above calculation was sketchy and crude -- but hopefully it gives you some intuition for why the entropy is what it is, and why everything is consistent and reasonable.


Post-selection and complexity theory I read about post-selection and didn't understand the meaning behind this thing. I didn't understand the Wikipedia article well, so what is a simple but understandable explanation of post-selection and how to use it in complexity?

I went ahead and looked to see if there was a good resource that I could provide, but beyond some resources that Aaronson wrote, I could not find any good additional supplements. You should check out what he says and see if that helps. However, I'll do my best to provide a very quick and potentially hand wavy interpretation.

Basic Quantum Computing: (If Needed)

Consider a quantum computer with some number of quantum bits. Before we measure quantum bits, they are in a superposition of many possible output states. When measured, they collapse to a single state that is sampled from a probability distribution of states. In other words, during measurement, some state is "chosen" randomly from all possible states, with some more likely than others to be "chosen".

A quantum computation takes these unmeasured qbits and methodically applies quantum logic gates. Doing this influences that superposition (the probability distribution of final states). When we are done applying quantum gates, we perform a measurement on the entangled qbits (final quantum state). This gives us a result we can use, but all the underlying quantum information is lost, preventing us from measuring again. The quantum computation would have to be repeated from scratch in order to perform another measurement. To account for errors, quantum computations are usually performed multiple times to build up additional confidence in the final result.

Postselection in a Computation:

When computing a decision problem, let us just designate a single quantum bit, $q_1$, as our "answer" where $\lvert1\rangle$ and $\lvert0\rangle$ correspond to accept and reject.

Postselection introduces conditional probability into the mix. We say we want to postselect a quantum bit, $q_1$,for a specified outcome of a second bit, $q_2$. To simplify matters, let us assume that this is the last thing that we do before measuring. Without postselecting, our machine would accept with  $\mathbb{P}\left[q_1=\lvert1\rangle\right]$. If we use post selection as described above, we are telling $q_1$ to only be in a superposition of states that work given that $q_2=\lvert1\rangle$. The probability that the computation accepts now becomes $\mathbb{P}\left[q_1=\lvert1\rangle\mid q_2=\lvert1\rangle \right]$. This essentially filters out all possible states that $q_1$ could have been in if $q_2 = \lvert0\rangle$.

If $q_2$ happened to be defined as an indicator of a "good" computation in our experiment, then, by using postselection, we would have thrown out all the "bad" computations.

Note: $\mathbb{P}\left[q_2=\lvert1\rangle\right]$ must be $>0$ or else the conditional probability measure is not well defined.

So in short, postselection gives us the ability to force quantum bits to think that another quantum bit is in a specific state we choose. This lets us filter out a lot of results that we consider to be useless to us when we measure our quantum state. As demonstrated in Aaronson's proof of $\text{PostBQP = PP}$, the ability to postselect provides significant computational advantage over vanilla models of quantum computation.


Construct this two-taped Turing Machine {(u#,v#):u,v E {a,b}* , |u| = 2|v|} I am having troubles trying to create this two-taped Turing Machine, I understand how I would get it to accept 2 strings of equal length. But to move forwards, I dont know how I would check to see if |u| = 2|v|

One possible solution running in linear time:

1) Move head of the first tape to the right until you reach end of $u$ while copying each symbol of $u$ to the second tape. But first write a blank symbol on the second tape as the first symbol.

2) Read $v$ by two symbols and for each pair of symbol of $v$ erase one symbol of $u$ on the second tape (starting from the last symbol and moving backward).

3.1) If all symbols (of $u$) on the second tape has been erased then check if the first head has reached end of the string (of $v$). If "no" then REJECT else ACCEPT.

3.2) If the TM has reached end of the string of $v$ (on the first tape) then check if the second tape is empty. If "yes" then ACCEPT else REJECT.


Peterson's vs. Bakery Algorithm From my CS course, the Peterson's Algorithm and the Bakery Algorithm both are solutions which satisfy the 3 requirements of any solution to the critical section problem. a) What are their adv/disadv over each other , and b) if they already solve the critical section problem, why do we need semaphores?

a) what are the advantages/disadvantages over each other?

According to the lecture note: Sections 17.4.1 and 17.4.3, we can summarize as follows:

The original Peterson’s Algorithm works with only 2 processes.
The Peterson's algorithm requires multi-writer registers while the Bakery algorithm uses only single-writer registers.
Both algorithms are starvation-free. Furthermore, the Bakery algorithm offers a strong near-FIFO guarantee.
Both algorithms work with atomic registers. However, the Bakery algorithm works with even weaker registers (safe registers actually, see here).
The Bakery algorithm uses unbounded registers. Nevertheless, this problem can be fixed.

  b)  If they already solve the critical section problem, why do we need semaphores?

A Semaphore is a generalization of mutual exclusion locks. Each Semaphore has a capacity, denoted by $c$ for brevity. Instead of allowing only one thread at a time into the critical section, a Semaphore allows at most $c$
threads, where the capacity $c$ is determined when the semaphore is initialized. (See the book "The Art of Multiprocessor Programming" by Maurice Herlihy and Nir Shavit; Section 8.5).


Is my pumping lemma proof correct? Show that $L = \{a^nb^l \ | \ n \leq l \}$ is not regular

I'd like to check if my proof for this is correct.

Proof: Choose any positive integer $m$. Pick $w = a^mb^{m+1} \in L$. Note that $|w| = 2m+1 \geq m$ and $1\leq |a^m| \leq m$. Write $w=xyz$ where $x=\varepsilon$, $y=a^m$ and $z=b^{m+1}$. We have
$$xy^3z= \varepsilon(a^m)^3b^{m+1} = a^{3m}b^{m+1} \not\in L\,,$$
since $3m > m+1$ for any positive integer $m$. Thus by the contrapositive of the Pumping Lemma we can conclude that $L$ is not regular. $\square$

Although we normally close "check my work questions", this question illustrates a very common mistake with the pumping lemma, so is intended as a reference question.

No, this proof is not correct.

To prove that a language is non-regular using the pumping lemma, you need to show that:

for all $m>0$, there is a string $w\in L$ of length at least $m$ such that
for all ways of writing $w=xyz$ with $|y|\geq 1$,
there is some $i\geq 0$ such that $xy^iz\notin L$.

You have shown that some way of writing $w=xyz$ makes part 3 true, but that is not enough.

To understand why, it's helpful to consider why the pumping lemma is true. The point is that, if a language is regular, it is accepted by a DFA and that DFA has some number $n$ of states. That means that, if it reads a string $w$ of length more than $n$ then, by the pigeonhole principle, it must enter some state $q$ twice (or more).  Then we can set $w=xyz$ where

$x$ is what is read before entering $q$ for the first time ($x=\varepsilon$ if $q$ is the initial state);
$y$ is what is read after the character that causes the first entry to $q$ up to, but not including, the character that causes the second entry to $q$ (so $y$ contains at least one character, i.e., $|y|\geq 1$);
$z$ is the rest of the string.

Now the point is that the string $xy^iz$ causes the DFA to go around the loop from $q$ to $q$ $i$ times, then carry on to an accepting state by reading $z$, so every string $xy^iz$ must also be accepted. However, the specific partition of $w$ into $x$, $y$ and $z$ depends on which automaton you're considering. To show that no automaton accepts the language, you need to show that every possible automaton fails, which means you need to show that all possible partitions $w=xyz$ fail.


Why is a sequence of n Push, Pop, Multipop operations O(n²)? From "Introduction to Algorithms" by Cormen, Leiserson, Rivest, Stein, Third Edition, page 453:

  Let us analyze a sequence of $n$ Push, Pop, Multipop operations on an initially empty stack. The worst-case cost of a Multipop operation in the sequence is $O\left(n\right)$, since the stack size is at most $n$. The worst-case time of any stack operation is therefore $O\left(n\right)$, and hence a sequence of $n$ operations costs $O\left(n^2\right)$, since we may have $O\left(n\right)$ Multipop operations costing $O\left(n\right)$ each. Although this analysis is correct, the $O\left(n^2\right)$ result, which we obtained by considering the worst-case cost of each operation individually, is not tight.

Part of this seems badly written:

  [...] since we may have $O\left(n\right)$ Multipop operations costing $O\left(n\right)$ each.

Why would they count the number of some items in terms of running time, $O\left(n\right)$? The way I interpret this is that a sequence of only $n$ multipops(n) will result in $O\left(n^2\right)$, but after the first one, I imagine the stack is empty.

Someone try and explain how the worst case cost of a sequence of $n$ push, pop, multipop is $O\left(n^2\right)$. Or perhaps what may help is if you can rewrite the problem statement... maybe that's what is confusing.

Question:  Do the push, pop, and multipop cumulatively add up to $n$, or is it $n$ push, $n$ pop, and $n$ multipop operations?

First, let me comment on 2 misconceptions I see in your question:

Landau notation ('Big $O$ notation') does not exclusively refer to running times, we can use it to describe any function we wish.
The fact that the worst case running time is $O(n^2)$ doesn't mean the running time isn't also $O(n)$.

The second part comes close to the point of this part in the book. The authors first show that a (crude) analysis of executing the multi-pop operation $n$ times: worst case of a single multi-pop is $O(n)$, we pop $n$ times, so we spend at most $O(n^2)$.

However, do all of our $n$ multi-pop operations require $O(n)$ time? The authors continue to show that using the aggregate analysis that this isn't the case, by which they obtain a sharper bound of $O(n)$ for $n$ multi-pop operations.

So, in this section, the authors show the utility of aggregate analysis by the multi-pop example.

As for the part labeled as 'question': yes, the total running time of all $n$ operations is $O(n)$, as the book describes in the next section:

  We can pop each object from the stack at most once for each time we have pushed it onto the stack. Therefore, the number of times that POP can be called on a nonempty stack, including calls within MULTIPOP , is at most the number of PUSH operations, which is at most $n$


Stack memory questions Are data and return addresses both pushed on the same stack space?
If yes, couldn't this piece of code cause problems:

CALL r1 //the PC is now the contents of register 1, return address is pushed on the stack.
POP r2  //pop the top of the stack and put the data in register 2.
RET     //return from subroutine

The POP instruction would delete the return address of the subroutine so the RET instruction will return to the wrong location.

Yes, they are stored on the same stack.  Yes, that sequence of code could cause problems.  It is up to the compiler (or the assembly language programmer) not to do that.

A compiler will typically ensure that the start of the function pushes some number of words (say $n$ words), and that the end of the function pops off exactly as much as was pushed -- no more, and no less.  As long as you do that, the return address will be left undisturbed and the RET will return back to right after the CALL.  If you don't follow that kind of convention, then all sorts of strange things can happen, exactly as you say -- so make sure you follow the convention.


What are some research papers or techniques that deals with fitting clothes on a human? Given an image of a dress (from different angles), what could be ways to fit it on a human image (again multiple angles corresponding to dress)? Any link to research papers or tutorial regarding this?

I would expect most of the works use Generative Adversarial Networks (GANs) for this because they are powerful generative models capable of learning the complex underlying probability distribution.

In this amazing work the authors used a Conditional GAN, in which they can generate an image conditioned on semantic segmentation map. In your case, you might want to condition on two images, one of a dress and the other of a human. https://github.com/NVIDIA/pix2pixHD

You might also want to look at the ICCV 2019 workshop on fashion.


Show that function is not turing-computable? We have two functions:

$f_1: \mathbb{N}\rightarrow \mathbb{N} \quad $
$f_2: \mathbb{N}\rightarrow \mathbb{N}$

By definition $f_1$ is turing-computable while $f_2$ is not.

Then we define a third funtion $g(n) = f_1(n) + f_2(n)$.

I want to show that $g(n)$ is not turing-computable:

So first assume that $g(n)$ is computable.

That means I can write it like this:

$f_2(n) = g(n)-f_1(n)$

Which (is where I'm not sure) means that $f_2$ can be computed which is a contradiction to the definition, which results that $f_2$ is not turing-computable.

This proof is correct as written, well done :) Remember this pattern, because an identical proof can be used in a wide variety of similar problems such as rational/irrational numbers and polynomials/non-polynomials


How to represent a 0-valid boolean formula? I read in these two papers http://www.ccs.neu.edu/home/lieber/courses/csg260/f06/materials/papers/max-sat/p216-schaefer.pdf and http://people.csail.mit.edu/madhu/papers/noneed/fullbook.ps that if we have a boolean formula that is $0-valid$ then (of course) SAT problem is in $\mathcal{P}$ but finding a solution with maximum true literals is $\mathcal{NP}-$hard.

N.B. As defined in the previous papers, a $0-valid$ boolean formula $f$ is a boolean formula $f: \{0, 1\}^n\rightarrow\{0, 1\}$ that satisfies $f(0, \dotsc, 0)=1$.

My question is:

Can I represent a general $0-valid$ boolean formula on the variables $x=\left(x_1, \dotsc, x_n\right)$ by the following one:

$f(x)=\bigwedge\limits_{i=1}^{L}\bigvee\limits_{i\in\mathcal{S}_l}\neg\;x_i$?

Where $L$ is the number of clauses and $\mathcal{S}_l\;\forall\;l\in\{1,\dotsc, L\}$ is a subset of $\{1, \dotsc, n\}$.

The constraints of a $0$-valid formula can be more general. All we know about them is that they are satisfied if all variables are $0$. For example, a constraint could be $x = y$ (i.e. $(x \land y) \lor (\lnot x \land \lnot y)$). Your form is not general enough, since it only considers constraints of the form $\lnot x_1 \lor \dots \lor \lnot x_\ell$.

While your formulation doesn't capture the problem of determining the most positive solution for a $0$-valid CSP, it is equivalent to an even more classical problem, set cover. In particular, your problem is NP-complete.


Running time of a function $P$ calling itself via $P(P(n/2))$ int P(int n)
{
  if (n==1)
    return 1;
  else
    return P(P(n/2));
}

How will this function P(P(n/2)) be executed and what will be the recurrence relation for this code?
Original image with the code

There is an unwritten assumption that the input is always at least $1$ (otherwise your function never terminates). Under this assumption, it is easy to prove by induction that the function does terminate, and always returns $1$. Therefore in the expression $P(P(n/2))$, we are first invoking $P$ with the input $n/2$, and then with the input $1$. It follows that the running time $T(n)$ of your function satisfies the recurrence $$ T(n) = T(\lfloor n/2 \rfloor) + \Theta(1), $$ with initial condition $T(1) = \Theta(1)$. The solution is $T(n) = \Theta(\log n)$.


Draw a Turing machine that decides the language of all words over the alphabet {a, b} that have an odd number of a’s and an odd number of b’s Does the question mean draw a Turing machine that takes input with any number of a's and any number of b's (eg. aaabbb, ab, abababab, etc.). The turing machine should only then accept or reject the input and should not be stuck in loop?

Example of a drawing to answer the question:

Yes. "Words over the alphabet $\Sigma=\{a,b\}$" means that the input can be any string containing $a$s and $b$s in any order, and "decide" means that the machine must halt (accept or reject) on every input, and not get into an infinite loop.


Articulation vertex in complementary graph I need to implement an algoritm, but I can't understand the theory behind it.

How can I prove that if v is an articulation vertex in a graph G , that it will not be an articulation vertex in G' complimentary graph ?

I know that an articulation vertex , is one which when removed disconects the G . And that the complementary graph , is one with two distinct vertices adjacent if and only if they are not adjacent in G.But I can't figure out how to connect this statements with my problem.

Hint: An equivalent characteristic of "an articulation vertex $v$" is as follows:

  $v$ is an articulation vertex in $G$ $\iff$ there exists two vertices $x,y$ such that $v$ is on all the paths between $x,y$.

So it suffices to check all the pairs $x,y$ in $G'$ to see whether there exists some path between them which does not pass $v$.

More hints:

Consider two cases:

In $G$, $v$ is on all the paths of $x,y$. Then is $e = (x,y) \in G'$?
In $G$, $v$ is not on all the paths of $x,y$. Where are $x$ and $y$ if $v$ is removed in $G$? Then,

2.1 What if $(x,y) \notin G$?
2.2 What if $(x,y) \in G$? Can you find a path $x \leadsto y$ in $G'$ which does not pass $v$?


Confused by extremely high autocorrelation I have the following python code

x = [100.0 for _ in range(1000)]
for i in range(1, len(x)):
     x[i] = x[i-1] + (2*randint(0, 1)-1)*step_size
import numpy as np
print np.corrcoef(x[:-1], x[1:])

I am getting extremely high correlation values, over 99.9%, more precisely

[[ 1.          0.99785636]
 [ 0.99785636  1.        ]]

Does anyone know what's going on? How can I get such large autocorrelation? Can anybody help me get better intuition and understanding of this?

Most of the values of the random walk $x$ are large ($\omega(1)$) with high probability. Therefore the difference between $x_i$ and $x_{i+1}$, which is $\pm 1$, is small. So the random walk correlates well with itself.

You can get results even closer to $1$ if you start your random walk from some position far away from the origin. Try it out!


Does a graph diameter equal to DFS tree depth? given an unweighted graph, does the graph diameter equal to the maximum DFS tree depth?

and the same about BFS?

regarding both directed and undirected graphs.

thanks :)

Regarding DFS the answer is no. Here there is a counter example.

The red arcs represent the DFS tree starting from the topmost node. This tree depth is 5 while the diameter is 3.

On the other hand, the maximum BFS tree depth coincides with the diameter of the graph (of course, this is valid if the graph is connected). If you run BFS from a source node S, all path found from this point to any other point will be of minimal length, i.e it contains all shortest path from point S to any other point. Though the maximum BFS tree depth is the maximum among all shortest path.


Why not decide coNP language L with same NDTM used for $L^c$? In Michael Sipser's book language is defined to be in NP iff it is decided by nondeterministic polynomial time Turnig machine. Why can't we use same machine to decide if language $L^c$ is in coNP? Just run every string x on same NDTM and if it accepts x then x is not in $L^c$ and if it rejects x then it is. What am I missing here?

In this book runnin time for NDTM is defind only for deciders, NDTM which halts in all branches.

I assume that you want to "decide if $x\in L^c$ and output the complement". Tell me if I misunderstand.

$L^c$ is in NP if there's an NDTM accepts $x$ in "at least one" branch iff $x\in L^c$. So $x\in L$, i.e. $x\notin L^c$ means the NDTM rejects $x$ in "all" branches. Think more carefully about these quantifiers.

NDTM can always find the accepted branch if it exists, but this doesn't means the NDTM has checked all branches. So we can't decide if $x\in L$ with the same NDTM in the trivial way you mentioned.

Edit: If you want to prove $L\subseteq NP$, you should construct "one NDTM" such that there exists a polynomially long path to an accepting state iff $x\in L$. You might think flipping the answer is quite simple, but where's the answer? There doesn't even exist a state representing "NO". This is the problem. You can't add another Turing machine which read the output of $M$ and output its complement either since the whole structure is not a valid NDTM.


Brute force algorithm for "Binary Puzzle" Binary puzzle

Binary puzzle is an puzzle played on a $n × n$ grid; intially some of the cells contain a zero or a one (fixed cells); the aim of the game is to fill the remaining empty cells according to the following rules:

Each cell should contain a zero or a one.
No more than two similar numbers next to or below each other are allowed.
Each row and each column should contain an equal number of zeros and ones.
Each row is unique and each column is unique.

Decision problem:

  Input : A partially filled n×n grid with 0's and 1's.

  Question : Can we fill the
  empty cells with a zero or a one in a way that follow the above mention rules ?

For $n \times n $ this problem known to be NP-complete.

Brute force Algorithm :

If the given $n \times n$ is empty then it is an yes instance ( use the basis set of $ \mathcal{ R^{n\times n}}$).
Case I: If only one row is filled and it is an valid row  (follow the above mentions rules ) then it is an yes instance. Second row is going to be the complement of first row (make 0 to 1 and 1 to 0).
Case II : if $k$ rows are filled and they are valid then I can fill the table upto 2k rows by using trick of complement.

Question :  How to design a brute force algorithm for the problem stated above ?

For $k$ fixed cells, you try all $2^{n^2-k}$ possibilities of filling the remaining $n^2-k$ cells and check for each fully filled board whether it fulfills all stated constraints.


Efficient flood filling (seed filling) I am referring to the algorithm that fills a white area of arbitrary shape in a binary digital image, starting from a given white pixel, using the Moore (8 neighbors) or Neumann (4 neighbors) connexity rules.

There are well-known solutions to this problem, such as recursion on the immediate neighbors, or the scanline approach. The former takes 4/8 tests of the neighbor color per pixel, and the latter takes a little less as when a straight run of pixels is processed, one backward test is saved per pixel. I have heard of an article possibly published in 2006, which is based on outline following, but have no reference for it.

(Whether the actual implementation uses the recursion stack or an allocated array is not relevant for this question. Nor is the "fixed-memory" requirement for which solutions have been proposed.)

My intuition tells me that better could be achieved by avoiding the repetition of some neighbor tests. In an extreme case, you can fill a square starting from the middle and spiraling until you reach the boundary with just one test per pixel, as you know that all pixels inside the spiral have been filled.

So my question: do you know of any theoretical study on the required number of neighbor tests per pixel for flood filling ? (The question can be rephrased in terms of graph theory as a connected component labeling problem.)

Following comments by @EvilJS which restarted a bibliographic search, here is relevant material that improves upon the initial algorithm by Alvy Ray Smith, which I called "scanline" in the OP.

It seems that the number of pixel visits was lowered from 2 to 1.5 in the worst case. It also seems that the minimum achievable rate depends on the topology of the filled area. The '85 article by Fishkin & Barsky is the most theory-oriented resource.

Computer Graphics And Geometric Modelling : Implementation & Algorithms
Max K. Agoston , Springer (2005), ISBN 10: 1852338180 ISBN 13: 9781852338183. See 2.4 Fill Algorithms.
Smith, A. Ray, Tint Fill, Computer Graphics, Vol 13, No 2, Aug 1979, 276-283 (SIGGRAPH 79 Conference Proceedings).
Fishkin, K.P., and Barsky, B.A., “An Analysis and Algorithm for Filling Propagation,” Proc. Graphics Interface 1985, 203–212.
Fishkin, Ken, “Filling a Region in a Frame Buffer,” in [Glas90], 278–284.
Heckbert, Paul S., “A Seed Fill Algorithm,” in [Glas90], 275–277.
[Glas90] is Glassner, A.S., editor, Graphics Gems, Academic Press, 1990.


What features of a problem make it NP-complete/hard? This isn't a question about what NP-completeness or hardness is, but about what, in general and informally, make a problem NP-complete? That is to say, what features of a problem might make me suspect a problem is NP-complete/hard?

To elaborate, for instance, lets say I’m seeing the graph coloring problem for the first time, or independent set, etc. Are there intrinsic features of these kinds of problems that might make me suspect they cannot be solved efficiently?

By definition, a problem is NP-complete if it's in NP and every other problem in NP can be reduced to it. The only literal answer to the question is that one: essentially, a problem is NP-complete only if it can be proven to be NP-complete. Since proof is a creative activity, it's not possible to give a series of rules, along the lines of "If a problem looks like X, Y or Z, then it's NP-complete."

However, there are some common features. First, the problem must be in NP, which means that we must be able to efficiently check a potential solution (e.g., check a proposed colouring for a colouring problem). Of course, designing efficient algorithms is also a creative act but, usually at least, proving that a new problem is in NP is fairly straightforward.

Once I've convinced myself that a problem is in NP, the thing that usually makes me feel that it might be NP-complete are non-locality and the presence of some kind of conflicting goals. Examples:

Satisfiability problems are non-local in the sense that choices for the variables in one clause also affect many other clauses. There are competing goals in that clauses containing $X$ want us to make $X$ true, but clauses containing $\neg X$ want the opposite.
In colouring problems, we wish to use as few colours as possible but features of the graph cause us to need many colours. Choices for colours in one part of the graph may have cause problems far away (see, e.g., Erdös's famous result that, for any $k$, there are graphs of arbitrarily large girth that are not $k$-colourable despite the fact that having large girth means they look locally like trees).
In something like vertex cover, we're looking for a set that is, in a sense, "small but powerful". We can trivially find large vertex covers but the difficulty is in finding a small set that still does everything that we need.

Another feature can be that the "obvious" algorithm that you first think of seems to involve uncontrollable backtracking when you try to make it really work. For example, you might try to solve independent set greedily by starting with a single vertex and iteratively adding vertices that don't send any edges to the set you've built so far. But you soon realise that a bad choice early on can limit your options later and you start having to backtrack. Satisfiability problems tend to work like this, too.

However, be aware that adding even more restrictions to a problem can make it easier.  For example, everything I've said above might make you suspect that 2-colourability and 2-SAT are NP-complete. But it turns out that 2-colourable graphs are so special that you can easily detect them and the back-tracking in 2-SAT can be kept under control.


What is M referring to when talking about memory size( 4M x 8) In the following paragraph its talking about memory and it throws M into the L X W of memory notation and i'm confused on how 4M = 2^22. Thanks in advance

PARAGRAPH:

Memory is built from random access memory (RAM) chips. (We cover memory in detail in Chapter 6.) Memory is often referred to using the notation length   X   width (L   X   W). For example, 4M   X   8 means the memory is 4M long (it has 4M   =   2^2     X   2^20     =   2^22   items) and each item is 8 bits wide (which means that each item is a byte). To address this memory (assuming byte addressing), we need to be able to uniquely identify 2 ^ 22   different items.

M in this context is just defined to be $2^{20}$, so if you have M items (bits, bytes, whatever), you'll have $2^{20}$ of them. The letter was chosen since it's the first letter in the term mega, meaning a million. Since $2^{10}=1024$ is close to $1000$, we'll have $2^{20}=(2^{10})^2≈(1000)^2=1000000$. M is sometimes called a "binary million".


Algorithm to extract line-like contour in 3d Hello people on the internet,

I'm currently searching for some kind of fast algorithm that allows me to extract curves in three dimensional space that arise as the intersection of two level sets of smooth functions, i.e.
\begin{align*}\mathcal{C} = \{\vec{x} \in \mathbb{R}^3 | \; F(\vec{x})= l \; and \; G(\vec{x})=s \} \end{align*}

I was thinking that something similar to marching cubes might work, but not having a computer science background I'm struggling to make out if and how that would look.
Does anyone have a suggestion on what I could do?

Edit: I currently use a very inefficient solution where I compute one isosurface with a preimplemented python method on a 3d grid, then check the isosurface for wanted values of the other function (walking along curves in slices of the surface and checking for crossings of the value) and collect all such points. In the end I group them with a clustering algorithm.

Edit2: In my specific case, the functions are defined with a few random parameters for some finite natural $N$, which are $\varphi_n \in [0,2\pi), A_n \in [0,1], \vec{k}_n \in S^2$ (the unit sphere) and are restricted to a three-dimensional cube of some size $a$.
\begin{align*}F(\vec{r}) &= \frac{1}{T} \sum_{n=1}^N A_n \cos(2\pi \vec{k}_n \cdot \vec{r} + \varphi_n) \\
G(\vec{r}) &=  \frac{\partial_z F}{|| \nabla F ||}  \end{align*}
for some normalization constant $T$. I want to work with the intersection curves (that I made out to generally be several disconnected ones) for different parameters.

Here is a generic approach:

Find a point on the intersection of these two curved planes, i.e., on the intersection of $F(\vec{x})=l$ and $G(\vec{x})=s$.  Call that point $\vec{x}_0$.
Trace along the intersection curve, starting at $\vec{x}_0$, and continuing as far as you can.  Then do the same starting from $\vec{x}_0$ in the opposite direction.
Find a new point $\vec{x}_0$ on the intersection of $F(\vec{x})=l$ and $G(\vec{x})=s$ that's not part of what you've traced so far, and go back to step 2.

To instantiate this, we need to know how to implement each of these steps.

To find a point on the intersection of $F(\vec{x})=l$ and $G(\vec{x})=s$, you can use any method for solving a system of nonlinear equations.  There are many.  If you're not familiar with the subject, one simple approach is to minimize the objective function

$$\Phi(\vec{x})= \|F(\vec{x})-l\|^2 + \|G(\vec{x})-s\|^2$$

using, e.g., gradient descent.

To trace along the intersection curve, you can use the gradient to help you.  Suppose that $\vec{x}_0$ is a point on the intersection curve, and expand the Taylor series for $F$ and $G$.  We get

$$F(\vec{x}) = F(\vec{x}_0) + \nabla F(\vec{x}_0) \cdot (\vec{x}-\vec{x}_0) + \dots \approx l + \nabla F(\vec{x}_0) \cdot (\vec{x}-\vec{x}_0)$$

and similarly

$$G(\vec{x}) \approx s + \nabla G(\vec{x}_0) \cdot (\vec{x}-\vec{x}_0).$$

So, for $\vec{x}$ to be on the intersection curve, we require $ \nabla F(\vec{x}_0) \cdot (\vec{x}-\vec{x}_0) = 0$ and $\nabla G(\vec{x}_0) \cdot (\vec{x}-\vec{x}_0)=0$ (assuming $x$ is very near $x_0$).  Since $\nabla F(\vec{x}_0)$, $\nabla G(\vec{x}_0)$, and $\vec{x}_0$ are known and computable, this gives us two linear equations in three unknowns, so we can solve for $\vec{x}$ using a linear equation solver.   In particular, compute the two vectors $\nabla F(\vec{x}_0)$ and $\nabla G(\vec{x}_0)$, then find a unit vector $\vec{d}$ that is orthogonal to both of them.  Now you can trace out the intersection curve from $\vec{x}_0$ by preceding in the direction $\pm \vec{d}$; in other words, the line $\vec{x}_1=\vec{x}_0 + c \vec{d}$ is approximately on the intersection curve, when $c$ is close to 0.  (If you want, you can generate $\vec{x}_1$ in this way, then "fine-tune" it by using it as the starting point for gradient descent with objective function $\Phi$ to compute $\vec{x}_1$ more precisely and to make sure you stay on the intersection curve.)  This gives you a way to step along the intersection curve, one point at a time.

How to implement step 3?  This might depend on the specific functions $F,G$.  One approach is to modify the objective function $\Phi$ to penalize points that are near the part of the curve you've already found, e.g.,

$$\Phi(\vec{x}) = \|F(\vec{x})-l\|^2 + \|G(\vec{x})-s\|^2 + \sum_i {1 \over \|\vec{x}-\vec{x}_i\|^2},$$

where the $x_i$'s are points you've previously found (or some well-spaced-out subset of them).  Another approach might be to do step 1 (gradient descent on $\Phi$, without the penalty term) starting from many different starting points (e.g., spaced on a coarse grid).  There may be a better way in your specific situation; I don't know.

I expect this should be more efficient than enumerating all grid points and evaluating $F,G$ at every grid point, especially as the spacing of your grid points gets small.  It does require you to be able to compute the gradients of $F,G$, but in your situation that seems to be no problem.


How does the 3-opt algorithm for TSP work? I understand that the 3-Opt Heuristic for solving the Traveling Salesman problem involves removing three edges from a graph and adding three more to recomplete the tour. However, I've seen many papers that mention that when three edges are removed, there remain only 2 possible ways to recombine the tour - this doesn't make sense to me.

For example, I found a paper [1] that says:

  The 3-opt algorithm works in a similar fashion, but instead of removing two edges we remove three. This means that we have two ways of reconnecting the three paths into a valid tour1 (ﬁgure 2 and ﬁgure 3). A 3-opt move can actually be seen as two or three 2-opt moves.

However, I count 3 different ways to reconnect the tour. What am I missing here?

Also, can someone link me to an algorithm for 3-opt if possible? I'm just trying to understand it, but I haven't come across any clear algorithms yet: all resources I find simply say "remove three edges, reconnect them". That's it, which is sort of vague.

Here are the 3 tours that seem to me to be 3-opt moves after removing three edges.

Heuristics for the Traveling Salesman Problem by C. Nilsson

You missed the footnote — these ways are "not including the connections being identical to a single 2-opt move". Indeed, there are only two permutations in $S_3$ without fixed points (also known as derangements), namely $(123)$ and $(132)$. More generally, for a $k$-opt move it is enough to consider permutations without fixed points, since those with $t$ fixed points are $(k-t)$-moves.

The algorithm for $k$-opt local search is as follows. Start with some initial solution, say the one produced by Christofides's algorithm. Repeatedly try to improve it by performing a $k$-opt: choose $k$ edges and reconnect them in a different way (this time it's OK if the move is also an $\ell$-move for some $\ell < k$) that results in a shorter tour.

The way this is implemented is by going over all sets of $k$ edges and over all ways of reconnecting the edges, perhaps in some intelligent order, and computing the difference in length (there is no need to recompute the length of the entire tour, just the different of length; that takes $O(k)$ instead of $O(n)$); if an improvement is found, we make the switch and repeat from the beginning. We continue like that until we get stuck.

A different variant is to always try all possibilities, and use the one that results in the best improvement. There are also other variants which you can probably find in the literature.


Low-level shift operator implementation I want a shift operator for an architecture that implements boxing. Basically, the high-level constructs represent integers as 31 bits followed by 1 bit set to one as a tag (so to represent binary int i I use instead 2i+1). Let's denote the box representation as $[[\cdot]]$, then I was able to make the following deductions. Consider x the number to be the shifted value and y the shift value (read the following to understand the whole process):

$[[\text{shift} \, x \, y]] = 2*{\text{shift} \big[\frac{[[x]]-1}{2} \, \frac{[[y]]-1}{2}}\big] + 1 = 2*{\text{shift} \big[\frac{[[x]]-1}{2} \, \frac{[[y]]}{2}}\big] + 1 = $

$= {\big[\text{shift} \; [[x]]-1 \, \frac{[[y]]}{2}}\big] + 1$

Here we can use $\frac{[[x]]-1}{2}$ or $\frac{[[x]]}{2}$ because $[[x]]$ always ends with a one however in the last step we remove the division by two and for $[[x]]$ we have to keep $-1$ but not for $[[y]]$. Please note that this translation is meant for left shifts where the bit structure of $x$ is important, namely if we have $x_1 x_2 x_3 1$ the last bit will be actually used in contrast with the right shift case.

The following is the version for the right shift (again read what follows to understand the process):

$[[\text{shift} \, x \, y]] = 2*{\text{shift} \big[\frac{[[x-1]]}{2} \, \frac{[[y-1]]}{2}}\big] + 1 = 2*{\text{shift} \big[\frac{[[x]]}{2} \, \frac{[[y]]}{2}}\big] + 1 = $

$= {\big[\text{shift} \; [[x]] \, \frac{[[y]]}{2}}\big] + 1$

Here the point is that the last bit is no longer useful and can be ignored.

I wonder if me scheme is correct and efficient in the sense that it may exist other procedure that is more efficient than mine. I would appreaciate as well that you clarify the intuitive ideas I gave for my procedure (if it is correct) reelaborating my assertions with possibly more accurate ones. Also I would appreciate ideas that suggest how to mix this two implementations.

Yes, it is correct.  Yes, it is efficient: your implementation for left-shift requires only four basic operations (i.e., about four instructions), and your implementation for right-shift requires only three basic operations.


Constant folding vs. Constant propogation What is the difference between constant folding and constant propogation? They both seem to do the same thing, instead of saving constants into stack or evaluating a full arithmetic expression, they simply replace it with the result which can be obtained at compile time. What is the difference between two?

Based on these two websites: http://www.compileroptimizations.com/category/constant_folding.htm and
http://www.compileroptimizations.com/category/constant_propagation.htm

The difference is that constant propogation is not saving a variable to the stack, because we know its a constant (like x = 10;) and can simply plug it in everywhere (say if you had an expression y = x + x + x => y = 10 + 10 + 10) it is used in machine code. Whereas, constant folding is simply evaluating expressions that use constants and substituting the result into the machine code (like y = 10 + 10 + 10; => y = 30;)


$A^* = B^*$ with $\{0,1\}$ contained in $A$ but not in $B$ I'm trying to exhibit two formal languages $A,B ⊆ \{0,1\}^*$ such that $A^* = B^*$ and $\{0,1\}$ is contained in $A$ but not in $B$.

Finding a language for $A$ is very easy, but I get stuck on $B$, because since $A^*=B^*$, and A has $\{0,1\}$, that $B^*$ must also have $\{0,1\}$. I can't think of a language that has $\{0,1\}$ in $B^*$ but would not be in $B$. Maybe I'm missing something.

If $0 \in A$ then clearly $0 \in A^* = B^*$. Conversely, if $0 \in B^*$ then $0 \in B$: indeed, if $0 = w_1 \ldots w_n \in B$, then exactly one of the $w_i$ can be non-empty, and it must equal $0$. Therefore $\{0,1\} \subseteq A$ and $A^* = B^*$ implies $\{0,1\} \subseteq B$. In other words, there are no two languages $A,B$ satisfying your constraints.


If NP is the class of problems that cannot be solved in polynomial time, what is co-NP? In my super non-rigorous class on optimization, the prof defined NP as the class of decision problems that cannot be solved in polynomial time. By definition, P is the class of decision problems that can be solved in polynomial time.

Then what is so called co-NP? Does co-NP = P in the sense of 'complement' of a set as used in set point topology?

Is there an intuitive way of explaining the meaning of co-NP in terms of problem that can be solved in _________ time? And the intersection between NP and co-NP?

Your prof was absolutely not rigorous (i.e. completely wrong), that's why the distinction between NP and co-NP doesn't make sense with his definition. Better definition:

Def.: A decision problem (that is a problem where the result is either YES or NO and nothing else) is in NP if for every instance where the result is YES there exists a hint such that we can prove that the result is YES in polynomial time in the size of the problem by using the hint. (You will notice that there need not be a hint to prove the answer is NO, if the answer is indeed NO).

An example (not NP complete): If your decision problem is whether a number is composite (YES) or prime (NO), then for every composite number I can give you as a hint one non-trivial factor f. Then you can prove that the answer is YES by checking that the number is divisible by f.

Interestingly, when the number is prime, there isn't such a trivial hint that let's you prove the answer is NO. (There are hints, but nowhere near as simple).

And co-NP is defined almost the same, except there must be a hint if the answer is NO. For every problem X in NP, you can pose the problem Y: "Is the answer to problem X NO", and that problem Y would be in co-NP by definition.


AVL Trees Height-Balance Property An AVL tree is one that satisfies the height-balance property which states that: For every position p of T, the heights of the children of p differ by at most 1.

Below is an example AVL tree. However, I've highlighted a node whose child's height would imply that their difference is not at most 1.

Can someone explain to me what I am missing?

The nodes you are highlighting are a node and its child. The promise is that the heights of siblings don't differ by more than $1$. In other words, the promise is that for every node $p$, the heights of the children of $p$ differ by at most $1$ from each other.


Difference between dynamic loading and dynamic linking in the OS First of all, I saw many answers of this topic in Quora, Stackoverflow, and this site. But, I couldn't definitely understand the difference between dynamic loading and dynamic linking.
What I understood until now is this.

Dynamic loading : system library or other routine is loaded during run-time and it is not supported by OS.
Dynamic linking : system library or other routine is linked during run-time and it is supported by OS.

What I'm confusing is the behaviour of this two concepts. I know that loading occurs after linking like below image. (from Operating System concepts 9th edition, Chapter 8 figure 8.3)

Then, my question is that does dynamic loading is occured after dynamic linking? If I'm wrong, what is the exact difference between two concepts?

Let me explain these terms in the simplest way possible. Now since both the terms have the word dynamic in them, both occur during execution.

Dynamic Loading : Suppose our program that is to be executed consist of various modules. Of course its not wise to load all the modules into main memory together at once(in some cases it might not be even possible because of limited main memory). So basically what we do here is we load the main module first and then during execution we load some other module only when its required and the execution cannot proceed further without loading it.

Dynamic Linking : Suppose our program has some functions whose definition is present in some system library. We do know the header file only consists of declarations of functions and not definitions. So during execution when the function gets called we load that system library into main memory and link the function call inside our program with the function definition inside system library.


Modal logic axiom S4, transitive and reflexive frame, tableaux solver I have a difficult problem to solve which as mentioned in the title is related to modal logic axiom S4.
So, here is some background knowledge that can be useful:

S4 axiom is a class of transitive and reflexive frames
S4 satisfiability problem is PSpace-Complete
lastly solver for S4 does not terminate without a trick which will allow it to return a finite model.

Knowing all this, I have implemented a solver for propositional modal logic S4 and it also terminates with a finite model. In general solver uses Tableaux approach and generates graph in which the input formula is true. So, to outline what the algorithm does we have the following:

algorithm start by creating a graph with a single node with the input formula.
then we solve alpha, beta, gamma and delta formulas until each sub-formula is marked as being visited.
for termination part of the algorithm, every time a new node is about to be created (which is caused by delta formulas) we check whether the same node already exists in the graph. If yes, then we do not create a new node but we add an edge to the node that has that value.

This is enough to see what the algorithm does. What I am trying to do next is to prove that the algorithm is correct and will always work. For this purpose I will need to structure a formal proof.

So is anyone familiar enough with the topic to suggest what technique can be used to with the proof? What should be used bisimulation or filtration? Furthermore, it would be great if you could sketch out the proof if possible.

Any help would be very very appreciated.

To find a descriptive answer to this post, please see my thesis which presents background information of various modal logics including S4. It also contains detailed implementations of the algorithms used along with implementations in python.

I have also proved that NPSpace problems such as S4 or K4 are terminating in finite time without infinite looping. Here is the link to full report -> Link to the pdf file located on my website. I would recommend reading it fully and following the research papers which were used to make sure full knowledge is transferred onto you :).

Please note that this was a research project which I have now finished. Nevertheless, if anyone wants to expand on my work or would like me to get involved on similiar topic, please get in touch in any way possible.


Turing Machine Decidable: What right does the definition have to say what's not in language L? I'm having trouble understanding the definition of Turing Decidable. The definition goes something like this:

  TM M decides language L iff the strings in L put M into the Accept state
  and the strings NOT IN L put M into the Reject state

My problem is.. the strings "NOT IN L"? How can the definition be based on what's not in L? Shouldn't the definition be more like this?

  TM M decides language L iff the strings L put M into the Accept state
  or the Reject state.

Then you can divide L into two subsets - those that are accepted, and those that aren't. But they're all decided by M, no?

(I'll convert the comment into an answer)

First, definitions:

$L$ is a language, that is, a set of words where each word has a finite length. If all the words that ever exist are denoted as $\Sigma^*$ then any language is $L\subseteq \Sigma^*$. Words that are not in $L$ are in a different subset we denote $\overline L=\Sigma^*\setminus L$. Both $L$ and $\overline L$ can be infinite (i.e., have infinite many words). Still, each word in $L$ or in$\overline L$ is of finite length.

Now, assume that we have a TM that never goes into an infinite loop (such TMs are called deciders). If it never goes into a loop, it means that for any input word, it will either halt and accept or halt and reject.

If we used your second definition, then any $L$ will be $L=\Sigma^*$, since all the words are either accepted or rejected.

So the answer is that the first definition is correct. A decider $M$ (a TM that always halt!) splits the space of all the possible words $\Sigma^*$ into two disjoint subsets, the words that are accepted by $M$, denoted $L(M)$ and the ones rejected by $M$, denoted $\overline{L(M)}$. Again, $\Sigma^*=L(M) \cup \overline{L(M)}$, since every word is either accepted or rejected.


How do I prove regular/non-regular with Nerode-Theorem? How to use it? $L_{1}=\left\{w \in\{a, b\}^{*} | \#_{a}(w)=0\right\}$

$L_{2}=\left\{w \in\{0,1\}^{*} | w=u v u \text { with } u, v \in\{0,1\}^{*}\right\}$

I have problems to prove regularity with the nerode theorem

The idea behind this is that the nerode classes have to be finite for a regular language

How do I use this?

For L1 I know this

There is only $b^{n}$ due to the fact that there language does not accept any a

Let m$\neq$n than there exists $b^{n}b$ and $b^{m}b$ for all m $\in \mathbb{N}$\n an n $\in \mathbb{N}$\m and of all them are in L

For 2 I know this

Let vu be x so for all a,b $\in \{0,1\}^{\star}$ ax an bc are in L.

You'd have to prove that the equivalence relation for your language is of infinite index to show it isn't regular. If regular, the equivalence classes are exactly the states of tje minimum DFA for the language.

In this case, both are regular (if I understand the notation correctly, $L_1$ is just strings with no $a$; for $L_2$ you can take $u = \epsilon$ and $v$ the given string, so $L_2 = \{1, 2\}^*$). Nice red hering, BTW.


TM recognizing $0^n1^n$ requires Ω(log n) space I am trying to prove that any deterministic 1-tape Turing Machine which recognizes the language $L = \lbrace{0^n1^n | n \geq 0 \rbrace}$ requires
$\Omega(\text{log }n)$ space.

I believe this can be done using a crossing sequence argument.
I have been trying to imitate the $DSPACE(O(1)) = REG$ proof from wikipedia.

What I have tried is:

Suppose $L \in DSPACE(S(n))$, for some $S(n) = o(\text{log } n)$ and let $M$ be an $S(n)$ space bounded TM recognizing $L$.
Since $L$ is not regular, $L \notin DSPACE(O(1))$. Therefore, given $k \in \mathbb{N}$, let $x \in L$ be a string of minimal length that requires more than $k$ worktape cells.

Let $C$ be the set of configurations of  $M$ on $x$. That is, $C$ is the set of tuples of the form

(state, work tape head position, work tape contents).

Then $|C| \leq |Q_M| \times S(n) \times 2^{S(n)} \leq 2^{cS(n)} = o(n)$, where $c$ is some suitable constant.

The crossing sequence at $i^{\text{th}}$ cell boundary is the sequence of such configurations  occurring as the input head moves across that boundary.
Each term of a crossing sequence can be any of the $|C|$ elements from $C$.

Also, length of any crossing sequence cannot be more than $|C|$; for otherwise, some configuration will repeat and $M$ will enter into an infinte loop.

Therefore,
number of crossing sequences of $M$ on $x$ $\leq |C|^{|C|} \leq 2^{cS(n)2^{cS(n)}} $.

The problem is that this doesn't give the required bound. So, a cleverer argumet is needed.

As you correctly point out by counting configurations, it holds that $SPACE[o(\log n)]\subseteq TIME[o(n)]$.

There is a theorem stating that $TIME[o(n\log n)]=REG$. See e.g. here.

If, by contradiction, we had $\{0^n1^n: n\in \mathbb{N}\}\in SPACE[o(\log n)]$, it would then follow that $\{0^n1^n: n\in \mathbb{N}\}\in REG$, which is clearly false.

Thus, $\{0^n1^n: n\in \mathbb{N}\}$ cannot be solved in $SPACE[o(\log n)]$.


A variation of the graph coloring problem Given a set of colors $M$ and a graph $G=(V,E)$. Allocate the colors to minimize the number edges with same color on the two vertices of the edge (i.e. minimize pairs of adjoining vertices with same color.).

This problem is different from standard coloring problem. Could someone please provide some literature where this problem is studied?

If $|M| = 2$, this is the max-cut problem.


HyperLogLog leading zeros distribution I'm reading this article.

In particular I'm having some trouble trying to replicate the results of the first image in that article.

For x=9, the graph says that the probability is 0.20 aprox. But from my calculations I get something different. After some thought I think I may be misinterpreting the idea of the calculation.

First attempt: Doing the sum of a X -> Bin(1024, 1/29), calculating f(X=1)+...+f(X=1024). My calculation equals 0.86 which is not 0.20

Then I thought that maybe he was talking about just having 1 result with 9 leading zeros. This means that from the 1024 numbers, we can have only 1 success in any of the 1024 numbers. Which is 0.27... closer but far from 0.20.

What am doing wrong here?

It looks like you could be more careful. "For x=9, the graph says that the probability is 0.20 approx." In fact, the graph says that probability is slightly less than 0.12.

Here is the relevant quote from the article on hyperloglog

This is a plot of probability of having x leading zeros, with 1024 distinct items. You can see that the probability peaks at around x = 10, as expected - but the distribution is quite wide, with x = 9, 11 or 12 being at least half as likely as x = 10. (The distribution peaks 0.5 units higher than expected, so this implies that 2k will overshoot by a factor of 20.5, or about 1.4. This shows up as a correction factor later.)

The probability of having exactly $x$ most leading zeros with 1024 terms is the difference of the probability of have no more than $x$ leading zeros and the probability of have no more than $x-1$ most leading zeros.
$$ P[x] =
\left(1-\left(\frac12\right)^x\right)^{1024}
-\left(1-\left(\frac12\right)^{x-1}\right)^{1024} $$
In particular, the probability of exactly 9 most leading zeros $P[9]\approx 0.1169$.
Here is a Python program that computes the probabilities shown in the above graph.
P = [0] * 23
for x in range(1, 23):
    P[x] = (1 - 0.5 ** x) ** 1024 - (1 - 0.5 ** (x - 1)) ** 1024
for x in range(4, 23):
    print(x, round(P[x], 4))

Here is its output.
4 0.0
5 0.0
6 0.0
7 0.0003
8 0.0178
9 0.1169
10 0.2326
11 0.2388
12 0.1723
13 0.1037
14 0.0569
15 0.0298
16 0.0153
17 0.0077
18 0.0039
19 0.0019
20 0.001
21 0.0005
22 0.0002

By the way, thanks for mentioning such a nice article that explains the hyperloglog algorithm that counts approximately using only $\log\log N$ bits. $\log\log N$ is arguably underestimating, since more powerful hash functions are needed as $N$ grows, which need more space to compute. Even if we add the space used by the has function, hyperloglog algorithm is amazingly ingenious in several ways.


On what abstraction is a filesystem actually built on? Data is read in terms of a block from a storage device(magnetic, optical, flash). Size of the block depends upon the filesystem and os. The physical device may have different units of storage like sectors.

Do filesystems create the abstraction layer directly over the physical device, or do they work over something called as a block device?

If they work over the block device then does it mean that when we create a partition table(gpt, msdos, mac) then block device abstraction is created and filesystems(fat, ntfs, ext) are then created for partitions of the device over the block device layer?

You usually have several layers. You will have a physical level, where complete sectors can be read or written - except on SSD drives, you can only write into an area that is zeroed, and you can only zero sectors 32 or 64 at a time. Much more interesting than a hard drive.

On top of that you have a level that is still in the hard drive. Caches on a hard drive, highly complex controllers on an SSD drive. SSD drives especially need to be handled right to get maximum performance, and that is built into the controller instead of the operating system.

On top of that you usually have one level handling partitioning, possibly one level handle fusioning of partitions on several drives, and a level handling full disk encryption. And you'll build your file system on the highest of those levels.


Free description of the Kameda-Weiner algorithm? I found the paper "On the State Minimization of Nondeterministic Finite Automata" which, I assume, contains the Kameda-Weiner algorithm that I've been searching for. It's behind a paywall though. I'm just a hobbyist. Can someone explain it, or point me to another source?

Brzozowski's paper on arXiv might have a full account of the algorithm. He's one of the pioneers in what I've termed the "algebraic approach" for formal language and automata theory - best known for invoking the "Brzozowski derivative" (aka left-quotient) to describe the state transition of a regular language in algebraic terms. It's the same operation that we used in producing a dramatically simpler proof of Parikh's theorem in 1999. For commutative Kleene algebras, the operator actually is a derivative operator complete with its own version of Taylor's Theorem.
In the paper, https://arxiv.org/abs/1301.5585, Brzozowski brings the derivative/quotient infrastructure to bear; but from a casual reading of the paper, I can't tell if he's described the Kameda-Weiner method in full generality or not.


How do we define the term "computation" across models of computation? How do we define the term computation / computable function generically across models of computation?
Beginning with the textbook definitions of: {Linz, Sipser and Kozen} for "computable function".
A function f with domain f is said to be Turing-computable of just computable if there exists some Turing machine M = (Q, Σ, Γ, δ, q0, □, F)
such that q0w ⊢* Mqₘf(w), qₘ ∈ F, for all w ∈ D  (Linz:1990:243)
Computable Functions
A Turing machine computes a function by starting with the input to the function on the tape and halting with the output of the function on the tape. (Sipser:1997:190)
Definition 5.12
A function f: Σ* → Σ* is a computable function if some Turing machine M, on every input w, halts with just f(w) on its tape.  (Sipser:1997:190)
A partial function σ: Σ* → Σ* is said to be a computable function if σ(x) = M(x) for some Turing machine M. (Kozen:1997:347)
I need to have the term [computable function] defined generically across models of computation so that I can know whether or not a specific C function is a [computable function].
Linz, Peter 1990. An Introduction to Formal Languages and Automata. Lexington/Toronto: D. C. Heath and Company.
Sipser, Michael 1997. Introduction to the Theory of Computation. Boston: PWS Publishing Company
Kozen, Dexter 1997. Automata and Computability. New York: Springer-Verlag.

Definition 5.12 is a standard way of defining a "computable function".  I see that you wish it was defined generically, but things are not as you wish they were; computability is typically defined with respect to a single model of computation.
That said, if you have any other Turing-complete notion of computation, then it is easy to prove that you can replace "Turing machine" with "machine in that model of computation" and you'll get an equivalent notion: in other words, there will be a Turing machine that computes $f$ iff there is a machine in that model of computation that computes $f$.  So the concept is indeed quite generic, even if the definition is not articulated that way.
See also https://en.wikipedia.org/wiki/Computable_function#Definition.
The exact semantics of C are messy and hard to formalize, and there appears to be some debate about whether C is Turing-complete, so C code is typically not a good way to prove that a function is computable or to reason about whether a function is computable.


Proof of sum of powerset? Is there already a worst case time complexity proof for the sum of all elements in a power set? I would assume, naively, you have to just add everything, which would run in about 2^n, where n is the size of the set.

For example: A = {1,2,3} Powerset(A) = {{}, {1}, {2}, {1, 2}, {3}, {1, 3}, {2, 3}, {1, 2, 3} } Sum(Powerset(A)) = {{} + {1} + {2} + {1 + 2} + {3} + {1 + 3} + {2 + 3} + {1 + 2 + 3} }

I'm defining addition between sets as: A = {1}, B = {2,3}, A + B = {1} + {2 + 3} = 6

Hint: If I understand you correctly, you are after
$$ \sum_{B \subseteq A} \sum_{x \in B} x. $$
Try reversing the order of summation:
$$ \sum_{B \subseteq A} \sum_{x \in B} x = \sum_{x \in A} \sum_? x, $$
where $?$ is some condition that you will have to come up with. See if that helps you to find a closed formula for the original double sum.


How to simulate backreferences, lookaheads, and lookbehinds in finite state automata? I created a simple regular expression lexer and parser to take a regular expression and generate its parse tree. Creating a non-deterministic finite state automaton from this parse tree is relatively simple for basic regular expressions. However I can't seem to wrap my head around how to simulate backreferences, lookaheads, and lookbehinds.

From what I read in the purple dragon book I understood that to simulate a lookahead $r/s$ where the regular expression $r$ is matched if and only if the match is followed by a match of the regular expression $s$, you create a non-deterministic finite state automaton in which $/$ is replaced by $\varepsilon$. Is it possible to create a deterministic finite state automaton that does the same?

What about simulating negative lookaheads and lookbehinds? I would really appreciate it if you would link me to a resource which describes how to do this in detail.

First of all, backreferences can not be simulated by finite automata as they allow you to describe non-regular languages. For example, ([ab]^*)\1 matches $\{ww \mid w \in \{a,b\}^*\}$, which is not even context-free.

Look-ahead and look-behind are nothing special in the world of finite automata as we only match whole inputs here. Therefore, the special semantic of "just check but don't consume" is meaningless; you just concatenate and/or intersect checking and consuming expressions and use the resulting automata. The idea is to check the look-ahead or look-behind expressions while you "consume" the input and store the result in a state.

When implementing regexps, you want to run the input through an automaton and get back start and end indices of matches. That is a very different task, so there is not really a construction for finite automata. You build your automaton as if the look-ahead or look-behind expression were consuming, and change your index storing resp. reporting accordingly.

Take, for instance, look-behinds. We can mimic the regexp semantics by executing the checking regexp concurrently to the implicitly consuming "match-all" regexp. only from states where the look-behind expression's automaton is in a final state can the automaton of the guarded expression be entered. For example, the regexp /(?=c)[ab]+/ (assuming $\{a,b,c\}$ is the full alphabet) -- note that it translates to the regular expression $\{a,b,c\}^*c\{a,b\}^+\{a,b,c\}^*$ -- could be matched by

[source]

and you would have to

store the current index as $i$ whenever you enter $q_2$ (initially or from $q_2$) and
report a (maximum) match from $i$ to the current index ($-1$) whenever you hit (leave) $q_2$.

Note how the left part of the automaton is the parallel automaton of the canonical automata for [abc]* and c (iterated), respectively.

Look-aheads can be dealt with similarly; you have to remember the index $i$ when you enter the "main" automaton, the index $j$ when you leave the main automaton and enter the look-ahead automaton and report a match from $i$ to $j$ only when you hit the look-ahead automaton's final state.

Note that non-determinism is inherent to this: main and look-ahead/-behind automaton might overlap, so you have to store all transitions between them in order to report the matching ones later, or backtrack.


Show that the regular languages are closed against taking "the second half" Given $L$ is regular, the proof that $\mathrm{HALF}(L)$ is regular is pretty straightforward to me (e.g., #11 in this link): simply making a NFA and meeting in the middle with 2 original DFAs, the creation of such NFA proving it is regular.

However, what if you wanted to prove the 2nd half string is regular, not the 1st half of a string.  That is,

$$\mathrm{2HALF}(L) = \{ x\mid yx\in L \text{ for some }y\text{ with } |y|=|x|\}\,.$$

Compare this to the standard

$$\mathrm{HALF}(L) = \{ x\mid xy\in L \text{ for some }y\text{ with } |y|=|x|\}\,.$$

I struggled on a solution, trying to use the same method as used on $\mathrm{HALF}(L)$ but can't seem to wrap my head around it.

Hint: if $L$ is regular, the reversal $L^R$ of the language $L$ is regular; see How to show that a "reversed" regular language is regular.  You should be able to use this fact.

Alternative hint: guess the middle point (non-deterministically), then...

Since this is an exercise problem, I am giving only a hint, not a full solution.  Try solving it yourself.


Are all decidable languages mapping reducible to its complement? I dont think this is true, take the language with a single element L = {0}, then the complement L' would have infinitely many strings (everything that isn't 0). So if it were true that A is mapping reducible to its complement, everything in L' can be obtained via a computable function from some element in L, i.e  010 is in L' however there is no x in L that gives f(x) = 101, since theres only one element, 0, it maps to one result.

Would this be correct?

Let $L_1,L_2$ be two languages over $\{0,1\}$. A (computable) mapping reduction from $L_1$ to $L_2$ is a computable function $f\colon \{0,1\}^* \to \{0,1\}^*$ such that for all $x \in \{0,1\}^*$ it holds that $x \in L_1$ iff $f(x) \in L_2$.

In your example, $L_1 = \{0\}$ and $L_2 = \overline{\{0\}}$, there does exist a mapping reduction, given by
$$
f(x) = \begin{cases} 1 & \text{if }x = 0, \\ 0 & \text{if }x \neq 0.\end{cases}
$$
Clearly $f$ is computable, and you can check that $x \in L_1$ iff $f(x) \in L_2$.

Hence your example doesn't work. You can check, however, that $\emptyset$ and $\{0,1\}^*$ are two examples of languages not reducible to their complement. Indeed, these are the only examples, which you can try to prove.


When do you use amortized time complexity and when to use unamortized? This is my guess:
-Use amortized because we want to know the "averaged" complexity over n operations assuming the operation is going to be used frequently
-Use unamortized when you know the operation is going to be used rarely

You can find the motivation for the amortized analysis from this reference:

The motivation for amortized analysis is that looking at the worst-case time per operation can be too
pessimistic if the only way to produce an expensive operation is to "set it up" with a large number
of cheap operations beforehand.

Hence, unamortized (asymptotic) analysis means considering time complexity of an algorithm (instead of each operation) when each operation can be counted in constant time.


Dijkstra to favor solution with smallest number of edges if several paths have same weight You can modify any graph $G$ so that Dijkstra's finds the solution with the minimal number of edges thusly:

Multiply every edge weight with a number $a$, then add $1$ to the weight to penalize each additional edge in the solution, i.e.

$w'(u,v)=a*w(u,v)+1$

This does not work for all values of $a$; $a$ needs to be at least $x$ for this to work. If $a$ is not this minimum number, it might not choose the shortest path. How do I find this minimum value $x$?

Ps. This was done recreationally, I'm done with homework long ago.

Given a graph $G = (V,E,w)$, we define $G'=(V,E,w')$ with $w'(e) = aw(e) + 1$ where $a = |E| + \varepsilon$ for some $\varepsilon \geq 0$ as proposed in the comments of the question.

  Lemma
  Let $P$ a path in $G$ with cost $C$, i.e. $w(P)=C$. Then, $P$ has cost $aC + |P|$ in $G'$, i.e. $w'(P) = aC + |P|$.

The lemma follows directly from the definition of $w'$.

Call the result of Dijkstra on $G'$ $P$, which is a shortest path in $G'$. Assume $P$ was not a shortest path with fewest edges (among all shortest paths) in $G$. This can happen in one of two ways.

$P$ is not a shortest path in $G$.
Then, there is a path $P'$ with $w(P') < w(P)$. As $|P|,|P'| \leq |E| \leq a$, this implies that also $w'(P') < w'(P)$ with above lemma¹. This contradicts that $P$ was chosen as shortest path in $G'$.
$P$ is a shortest path but there is a shortest path with fewer edges.
Then, there is another shortest path $P'$ -- i.e. $w(P) = w(P')$ -- with $|P'| < |P|$. This implies that $w'(P') < w'(P)$ by above lemma, which again contradicts that $P$ is a shortest path in $G'$.

As both cases have led to a contradiction, $P$ is indeed a shortest path with fewest edges in $G$.

That covers one half of the proposition. What about $a < |E|$, i.e. $a = |E| - \varepsilon$ with $\varepsilon \in (0,|E|)$?

Actually, we also need that $a$ or all weights in $G$ are integers. Otherwise, $w(P') < w(P)$ does not cause the weights in $G'$ to be at least $|E|$ apart. This is not a restriction, though; we can always scale $w$ with a constant factor so that all weights are integer, assuming we start with rational weights.


In programming languages, generally we do not distinguish relations and functions. Is there a better way to deal with these two concepts? When we write a mathematical formula, the rule $a=42$ (when we say let $a=42$) and testing them (when we write something like $\ldots \mathrm{if} x=42$) is written in a same equal sign. I think that both of them are representing some relation. However, while programming, we write = for the first circumstance and == for the second, and == is actually the infix representation of the equivalent testing function. Should they be treated as the same thing?

Previous question:

Are programming languages confounding relations and functions?

p.s. I have been asking this a few hours ago on StackOverflow, but they told me that it was on a wrong venue.

For example, the equivalent sign = has a lot of meanings, including returning a boolean value that tests whether to expressions are equal to some extent, setting up a rule that both side are equal, and assign the right side to the left side. And notations such as < and || are generally parsed as boolean operators. What's more, they do not distinguish predicates and boolean functions.

In my opinion, this is not a very elegant way to treat the 'rules'. I think notations like ≤ should be thought to be a relation, which means a≤b implies $(a,b)\in R_\leq$, where $R_\leq \subset S^2$ and $S$ is the domain of $a$ and $b$. Mathematically, ≤ is not a function at all (If it is, it should be something maps from a subset of $S^2$ to $\{True, False\}$). It is just representing some rules.

However, while programming, we generally do not realize the difference between them. We may consider k = a < b as a simpler way to write something like k = True for a<b, False otherwise. However, I believe that this makes things confusing in some circumstances, for example, the use of =.

I have seen a lot of imperative and functional language that do not seem to respect these differences. Am I correct in this point of view? Is there a better way to solve this?

Let $A$ be any set. Then, its powerset $\mathcal{P}(A)$ is isomorphic to the function space $A\to \mathbb{B}$ where $\mathbb{B}=\{\sf true, false\}$.

Indeed, the isomorphism is given by mapping each subset to its own characteristic function.

$$
\begin{array}{lcl}
\mathcal P A & \leftrightarrow & (A \to \mathbb B) \\
X & \mapsto & \lambda a. {\sf if}\ a\in X\ {\sf then\ true\ else\ false} \\
\{a|g(a)={\sf true}\} & \leftarrow\!\shortmid & g
\end{array}
$$

Since relations are sets of pairs, relations too can be seen as binary functions whose codomain is $\mathbb B$.

In most programming languages, as you realized, we don't really find propositions, sets, or relations, but we instead find their isomorphic counterparts: booleans, unary boolean functions, binary (or more) boolean functions.

This choice is mostly suggested by the fact that everything we compute ultimately is represented by a few bits. It is therefore very efficient for a computer to represent the truth values associated to propositions. Further, it is convenient to be able to write e.g. b = b or (y < 5) without using a conditional. (Actually, using a conditional for that usually reveals that the programmer does not understand that boolean expressions are indeed expressions, and not special syntax that is relegated to conditional or loop guards. This phenomenon also shows up in the infamous if b==true ... where the programmer often thought that we have to use at least one boolean operator in the guard, since we usually need that.)

In programming languages, there are some theoretical contexts where we do separate propositions from booleans, though. For instance, in the calculus of inductive constructions, as implemented in Coq, we find a Prop type for propositions, and a bool type for booleans. Very roughly, this allows the programmer to deal with propositions that can not be automatically checked by the computer, e.g. $\forall a,b,c\in\mathbb N.\ (a+b)\cdot c = a\cdot c + b\cdot c$
is a Prop. Even if the computer can not check them, we can still mathematically prove them. Note that we can not turn a Prop into its bool truth value since we have no way to check $\forall n$ or $\exists n$. (Actually, there's no such a thing as its "truth value" since the logic is constructive, but I'll be silent about this.) By comparison, we get two forms of n < 4 comparisons: one which is a Prop and can be used in logic, and another one which is a bool and can be used in programs.


If someone was designing a computer language, why would they require static members to be defined outside the class? I am new to C++ and just learned that "The declaration of a static data member in the member list of a class is not a definition. You must define the static member outside of the class declaration, in namespace scope."

I am curious about why this is. Are there particular design advantages to making the rules of the language in this way? I am not asking: "tell me what Stroustrup was thinking when he made C++" -- which I know is an unfair question on these forums. I am asking: if someone sat down to make a computer language, why might they require that static data members are defined outside of the class. What are the advantages of this? What are the disadvantages? What kinds of costs would this incur? Why would someone put this quirk in their language? (Also I'm curious, but I know it's not totally appropriate to ask here: how did this quirk end up in C++).

Such language design solution makes sense, because class body is basically a declaration, which normally has to be in the header file. All definitions has to appear in cpp files, where class instances are actually used. If you allow static members to be defined inside class body, then you mix declarations with definitions. So I would require this to make separation between declarations and definitions clear.

In terms of this separation it is fine to initialise static const class members inside class body. Basically, you are defining some constant and it could be equivalently done with some #define directive.

It doesn't seem that this restriction is due to the limits of the language or a compiler. Java doesn't have this restriction and allows definitions inside the body of a class for any static data member (not const only).

Update: C++11 relaxes the restriction and supports non-static member in-class initialisation. Static members still have to be defined outside.


Graphs with bounded degree and small max independent set Graphs with degree $\Delta$ have a maximum independent set of size $\alpha \geqslant \frac{n}{\Delta}$ where $n$ is the number of vertices.
But, are there graphs such that $\alpha \approx \frac{n}{\Delta}$, or even $\alpha = c \frac{n}{\Delta}$ for some constant $c \leqslant 1$?

First of all, the correct bound is $n/(\Delta + 1)$. This is tight for unions of cliques of size $\Delta+1$. If you want a connected graph, take a union of $\Delta$-cliques and connect them in a path or a cycle. This gives $n/\Delta$, so there is a small loss over the lower bound $n/(\Delta+1)$. If you want a connected regular graph, add a matching to the previous graph.


Perspective-Three-Point Questions I'm following this explanation on the P3P problem and have a few questions.

In the heading labeled Section 1 they project the image plane points onto a unit sphere. I'm not sure why they do this, is this to simulate a camera lens? I know in OpenCV, we first compute the intrinsics of the camera and factor it into solvePnP. Is this unit sphere serving a similar purpose?
Also in Section 1, where did $u^{'}_x$, $u^{'}_y$, and $u^{'}_z$ come from, and what are they? If we are projecting onto a 2D plane then why do we need the third component? I know the standard answer is "because homogenous coordinates" but I can't seem to find an explanation as to why we use them or what they really are.
Also in Section 1 what does "normalize using L2 norm" mean, and what did this step accomplish?

I'm hoping if I understand Section 1, I can understand the notation in the following sections.

Thanks!

1 & 3. Not related to OpenCV. In this context, projecting into the unit sphere is the same as normalizing, which is making the vector's L2 norm (AKA the Euclidean norm or commonly marked as $||u||_2$ or in short $||u||$) equal 1. This is done to simplify the term in the beginning of step two: $\cos{\alpha} = \frac{v*u}{||u||\cdot||v||}=v*u$

2. Before you divide the vector with the focal length (distance between the plane and $P$), the projected point is a point in space that is on the image plane. This point would change if the focal length changes, but what you really want here is a point that is independent of the focal point, since it shouldn't matter to the pose of the $ABC$ triangle. Dividing with the focal length here is like changing the focal length to 1.


Why does $A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ generate a context free language for regular $L$? How can I prove that the language that the operator $A$ defines for regular language $L$ is a context free language.

$A(L)= \{ w_1w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$, where $x^R$ is the reversed form of $x$.

I understand that since $L$ is regular so does $L^R$.also on my way for a CFG I can reach $w_1$ by the CFG of $L$ concatenation with the one of $L^R$ for making $w_2$. so far I have a CFG, but what promises me that $|w_1|=|w_2|$? how can I generate a grammar that will also keep that in addition to the other conditions?

Let $A'(L)= \{ w_1 \sharp w_2: |w_1|=|w_2|$ and $w_1, w_2^R \in L \}$ where $\sharp$ is a new symbol.

$A'(L)$ is the intersection of context-free language $\{ w_1 \sharp w_2: |w_1|=|w_2|\}$ and regular $L\sharp L^R$, therefore it is context-free. $A(L)$ is a homomorphic image of $A'(L)$, so it is context-free as well.

I prefer this proof to others as it is "higher-level".


Why do I need a base case for n=3 when solving a d&c recurrence? I was reading CLRS' book on how to use the substitution method to solve recurrences, where they have the following example:

$T(n) = 2T(\lfloor{\frac{n}{2}}\rfloor) + n$  where
$T(1) = 1$

They assume that $T(n) = O(n \log n)$ and go on to prove it by using induction.

I understand the inductive step, but I do not understand how they find the base case.

For $n=1$ we have $T(1) \leq c1 \log 1 = 0$, which is wrong because $T(1) = 1$. So we can not use $T(1)$ as a base case.

For $n=2$ we have $T(2) = 2T(1) + 2 = 4$, so $4 \leq c2 \log2$. The last inequality holds for every $c \geq 2$.

In the book they write that we also need $n=3$ to be the base case. However, they do not really explain why. Why isn't $n=2$ sufficient?

They do not want $T(1)$ to occur as a base case as it causes troubles. $T(3)$ depends on $T(1)$, so if they didn't take $T(3)$ as a base case in addition to taking $T(2)$ as one, they'd run into trouble when applying the inductive step to $T(3)$ as the hypothesis does not hold for $T(\lfloor{\frac{3}{2}}\rfloor)=T(1)$.


Two-head one way finite memory machine accepts non-regular languages I'm having trouble proving, or understanding why a two-head one-way finite memory machine could accept a non-regular language– for instance, $(w \mid w \in (a,b)^{*}, w= a^i b^i, i\geq 0)$.

For clarity, a two-head one-way finite memory machine works as follows –    it has  a   finite  control and a read-only input tape. The input tape  contains a  string, with a  special blank symbol at the right end. The  machine starts in the start state with both heads on the first symbol of    the input string. In one step the machine reads the current symbols under the two read heads, moves one or both of the heads one position to    the right, and  changes state. Each step of the machine is uniquely determined  by  its current state and the symbols read by the two heads. (That is, the machine  is deterministic.)  The machine accepts the input string    if  it  reaches an  accepting   state.

Just a "visual" Hint :-D

H1: v
    A A A B B B $
H2: ^

H1:   v
    A A A B B B $
H2: ^

H1:     v
    A A A B B B $
H2: ^

H1:       v        // found "B" ... let's
    A A A B B B $  // count both sides
H2: ^

H1:         v
    A A A B B B $  // ... go on ...
H2:   ^

H1:           v
    A A A B B B $  // ... go on ...
H2:     ^

H1:             v
    A A A B B B $  // H1 is on $, H2 on (the first) B ...
H2:       ^


Split graph in two parts, such that most nodes have even number of edges We have given graph of at most $200$ nodes, we want to split the given graph in two parts, such that the number of nodes with even number of edges is maximized, note that the edges that are between nodes of different parts are destroyed and not counted.

All possible splittings are allowed, even the one where all nodes are in one part. Each node should be in one part, we are required to print the nodes of one part.

This given graph has $5$ nodes, and the splitting made here is best because all nodes have even number of edges in the same part.

My idea was to do BFS over the nodes and when we find node with odd number of edges to put one node in the other part, but I can't come up with some strong idea.

By induction , we can prove that a partition exists with all nodes having even degree within the partition.
If all vertices have even degree , then we are done (Just partition it into the whole graph and an empty graph)
Otherwise let $v$ be a node with odd degree , now modify the graph by inverting the neighbourhood of $v$ (If $a$ and $b$ are neighbours of $v$ , then if they have an edge , remove it otherwise add it) and also remove $v $ from the graph , for the new graph , split it into 2 parts $A$ and $B$ such that all nodes in $A$ and $B$ have even degree , add $v$ back to $A$ if $A$ has even neighbours of $v$ , else add it to $B$. This works because in $A$(Or $B$ if we added $v$ to $B$) all degrees are even except for neighbours of $v$ which become even after adding $v$


A comparison operation for lists, based on P(a > b) Consider two lists $A$ and $B$, both containing $n$ numbers. A comparison operation can be defined based on the probability of uniformly selecting an element $a$ from list $A$ and an element $b$ from list $B$ such that $a>b$.

More precisely, define
$$ Q(A,B) = \sum_{i,j} \text{sign}(a_i-b_j)$$
If $Q(A,B) = 0$, then we can say the lists "tie". If $Q(A,B)>0$ then $A$ "beats" $B$, and likewise $Q(A,B)<0$ can be said as $A$ "loses" to $B$.

The naive way of calculating this comparison of lists involves checking each pair of elements and thus takes $n^2$ time.

  Is there a faster way to calculate this?

Note, that somewhat non-intuitively, $A$ can still beat $B$ even if the average value of $A$ is less than $B$. (Also, even more non-intuitive, this comparison operator is non-transitive. Known as "intransitive dice", you can have dice such that A beats B, B beats C, C beats A.)

I believe if we take the $O(n \log n)$ hit to sort $A$ and $B$ first, then there should be a better way to calculate the comparison. But I'm having trouble filling in the pieces.  Hopefully this is a useful hint instead of a red-herring.

Let $A \cup B$ denote the union of $A$ and $B$.  Sort $A \cup B$ into increasing order, keeping track for each element which list it came from.  Now for each element of this sorted list, annotate it with the number of elements of $A$ that are smaller than it and the number of elements of $B$ that are smaller than it.  Those annotations can be filled in with a single linear scan (starting from the start of the list, and scanning left-to-right, and keeping track of the number of elements of $A$ and $B$ seen so far).  Then you can compute the sum from those annotations: for each $i$, you can compute $\sum_j \text{sign}(a_i-b_j)$ directly from the annotation.

This algorithm takes $O(n \log n)$ time: $O(n \log n)$ time to sort, plus $O(n)$ for the scan, plus $O(n)$ time to add up the sums.


This costs minimization problem, is it solvable in polynomial time? I have the following problem: I have $c$ conflicts, named $(c_1, \ldots, c_c)$, where each conflict $c_i$ has certain size $s_i\in\mathbb{N}_0$: the number of times conflict $c_i$ has happened. Also, I have $m$ conflict resolution methods, named $(m_1, \ldots, m_m)$. Each method $m_j$ cannot be used more than $u_j\in\mathbb{N}_0$ times, and each time you use it, you have to pay $p_j\in\mathbb{N}_0$ dollars, but you get that each conflict $c_i$ connected to $m_j$ is reduced by $\min(r_{ji}, s_i)$ units ($s_i \leftarrow s_i - \min(r_{ji}, s_i)$, for each $c_i$ connected to $m_j$).
Once some $s_i=0$, the corresponding $c_i$ must be removed, and once some $u_j=0$, node $m_j$ cannot be used anymore so it can be removed as well.

The problem is solving all conflicts (making every node $c_i$ dissapear after making $s_i=0$) by repeated uses of the available methods, expending a minimal amount of money.
For example, if we call $E$ our total expended money (with an initial value of $0$), and, for the sake of simplicity, assume that every $r_{ji} = 1$, one use of $m_2$ implies the following updates:
E <- E + p
u2 <- u2 - 1   # If u2 becomes 0, remove m2 from the graph.
s3 <- s3 - 1   # If s3 becomes 0, remove c3 from the graph.
s4 <- s4 - 1   # If s4 becomes 0, remove c4 from the graph.
s5 <- s5 - 1   # If s5 becomes 0, remove c5 from the graph.

It's guaranteed that all conflicts can be solved. In other words, each $s_i\leq\sum_j(\{r_{ji}*u_j : m_j\text{ is neighbor of }c_i\})$.
Can this problem be solved polynomically? My guess is yes by using first the method that has the least "cost-per-conflict". In other words, at each iteration, make one use of the $m_j$ that minimizes $p_j/\sum_i(\{min(r_{ji},s_i) : c_i\text{ is neighbor of }m_j\})$ and afterwards remove all nodes that became $0$.
But, since the removal of conflicts increases the "costs-per-conflict" of the surviving methods for the next iteration, I'm not sure if this eager algorithm will lead to an optimal solution or whether a solution algorithm requires dealing with combinatorial explosion to be optimal.
In other words; I'm not sure if such eager algorithm causes that early eager choices will force an unneccesary number of uses of more expensive methods later, avoidable by not taken so eager choices earlier, like any other NP-hard problem.

It's a bad practice to use the same variable for two purposes, so I'll say that you have $C$ conflicts $(c_1, c_2, \dots, c_C)$ and similarly $M$ conflict resolution methods. To simplify, let $r_{ji} = 0$ if $c_i$ and $m_j$ are disconnected.
Suppose $t_j$ is a variable indicating how many times method $m_j$ was used we can phrase your problem as
\begin{align}
\min \quad&\sum_{j}p_jt_j\\
\text{s.t.}\quad&\forall i: \sum_j r_{ji}t_j \geq s_i\,,\\
&\forall j:0\leq t_j \leq u_j\,,\\
& \forall j:t_j \in \mathbb{N}_0\,.
\end{align}
What if instead we assume we always start by using every $m_j$ as much as possible, and $n_j$ represents the number of times we do not use $m_j$ (compared to the maximum allowed). Note that $t_j = u_j - n_j$. Substituting gives us
\begin{align}
\min \quad&\sum_{j}p_j(u_j-n_j)\\
\text{s.t.}\quad&\forall i: \sum_j r_{ji}(u_j-n_j) \geq s_i\,,\\
&\forall j:0\leq(u_j-n_j) \leq u_j\,,\\
& \forall j:n_j \in \mathbb{N}_0\,,
\end{align}
which is equivalent to
\begin{align}
\max \quad& \sum_{j}p_jn_j\\
\text{s.t.}\quad&\forall i:  \sum_j r_{ji}n_j \leq -s_i + \sum_j r_{ji}u_j\,,\\
&\forall j:0 \leq n_j \leq u_j\,,\\
& \forall j:n_j \in \mathbb{N}_0\,.
\end{align}
But this is exactly the $M$-dimensional bounded knapsack problem. Thus your problem is NP-hard, but you also get to benefit from the existing literature that give very good practical solvers.