Stratification of Bisimilarity : $\sim$ does not coincide with $\sim_\omega$ I am reading Sangiorgi's paper On the origins of bisimulation an coinduction.
Definition 2.5, on page 5, defines Stratification of Bisimilarity:

Let $W$ be the states of an LTS. We set:

$\sim_0 \overset{\text{def}}{=} W\times W$

$s\sim_{n+1} t$, for $n\geq 0$, if:
(1) for all $s^\prime$ with $s \overset{\mu}{\rightarrow} s^\prime$, there is $t^\prime$ such that $t \overset{\mu}{\rightarrow} t^\prime$ and $s^\prime\sim_n t^\prime$;
(2) the converse, that is, whenever for all $t^\prime$ with $t \overset{\mu}{\rightarrow} t^\prime$, there is $s^\prime$ such that $s\overset{\mu}{\rightarrow}s^\prime$ and $s^\prime\sim_n t^\prime$.

$\sim_\omega \overset{\text{def}}{=} \bigcap_{n\geq 0}\sim_n$

The paper follows with the remark that, in general, $\sim_\omega$ does not coincide with $\sim$ (the usual bisimilarity), and provides the following example (Example 2.6 in the paper) to highlight that:
We take the LTS with $\{a\}$ as the set of (arrow) labels, and the set of states is $\{a^0, a^1, \dots, a^\omega, s, t\}$, and the transition function $\overset{a}{\rightarrow}$ is the least function such that:

$a^\omega\overset{a}{\rightarrow}a^\omega$
$\forall n\geq 1, a^n\overset{a}{\rightarrow} a^{n-1}$
$\forall n\in\mathbb{N}, s\overset{a}{\rightarrow} a^{n}$
$\forall n\in\mathbb{N}, t\overset{a}{\rightarrow} a^{n}$
$t\overset{a}{\rightarrow} a^{\omega}$

which is represented in this picture:

The example then states:

It is easy to prove, by induction on $n$, that, for all $n$, $s\sim_n t$, hence also $s\sim_\omega t$.

However, I do not understand how that holds, even for $\sim_1$: $s\sim_1 t$ if (from item (2)):
whenever for all $t^\prime$ with $t \overset{\mu}{\rightarrow} t^\prime$, there is $s^\prime$ such that $s\overset{\mu}{\rightarrow}s^\prime$ and $s^\prime\sim_0 t^\prime$. Let's take $a^\omega$ as $t^\prime$, we indeed have $t\overset{a}{\rightarrow} a^\omega$. So, we have to find $s^\prime$ such that $s\overset{a}{\rightarrow} s^\prime$ and $s^\prime \sim_0 a^\omega$.
Hence my question : which state is suitable for such $s^\prime$, since $s\not\overset{a}{\rightarrow} a^\omega$ ?

I found the answer of my question when writting it, which once again prove the effectiveness of writting down properly the question we have.

To show that $s \sim_1 t$, to map $a^\omega$, one can take any $a^i$ we want (e.g. $a^0$): by definition,
$\sim_0 \overset{\text{def}}{=} W\times W$, and therefore we indeed have that $s\overset{a}{\rightarrow} a^0$ and $a^0\sim_0 a^\omega$.
Something to notice is that, for each $n$, we have $a^\omega \sim_n a^m$ for $m\geq n$. Therefore, to show that $s\sim_{n+1} t$, to show item (2), one can simply take $a^n$ as $s^\prime$ when we take $a^\omega$ as $t^\prime$. The rest of the proof is trivial.


Understanding Amdahl's Law calculation I have a homework problem: Calculate the overall speedup of a system that spends 40% of its time in calculations with a processor upgrade that provides for 100% greater throughput.

Which is a pretty straightforward calculation with Amdahl's Law

$S =  \frac{1}{(1-f)+(\frac{f}{k})} $

$f$ = fraction of work performed by component = .40

$k$ = the speedup of new component = 1.00

$S$ = overall system speedup

Plugging in my values I get

$S =  \frac{1}{(1-.4)+(\frac{.4}{1})} $

$S = 1 $

Which from my understanding mean's there is no speed up in the system. I am unsure if my calculation is wrong or my understanding of Amdahl's Law because I would think this processor upgrade would've provided at least some system speedup.

My book gives an example where $S = 1.22$ means a $22\%$ increase in speed so I think I am interpreting the answer correctly, which implies I did my calculation wrong, but that also seems correct.

"100% greater throughput" means a (local) speed-up by factor $k=2$.


How can simulated annealing be related to the vehicle routing problem? I have been searching through internet how could simulated annealing to solve the vehicle routing problem, but didn't find anything that made it clear to me. Most of what I found are research papers intended to solve some specific variation of the routing problem.

So I would appreciate if someone can make some kind of explanation of possible ways two things can be related and give some links that to so.

Simulated annealing is an optimization paradigm, in which (very roughly speaking) you start with some solution, and then try to make local changes that improve it, sometimes making a local change even if it doesn't improve.

Vehicle routing is an optimization problem. It is likely that the simulated annealing paradigm can be applied to it, probably in many different ways (corresponding to different notions of local change).


An algorithm to find the closest match between 2 arrays of RGB pixel tuples So I'm looking for a bit of an abstract algorithm and I'd appreciate any references to read up on. This is a bit tough to explain but I'll try my best.

Suppose we have 2 arrays of RGB pixel tuples-

A -> {(56, 39, 75), (125, 222, 32), (156, 201, 102)}

B -> {(125, 195, 93), (53, 31, 67), (118, 219, 48)}

I'd like the sort the second array in such a way that for each index of the 2 arrays, the corresponding RGB tuple pairs have the least deviation in value such that the optical difference between the 2 tuples is imperceptible to the human eye. For example, the difference between (122, 36, 18) and (126, 31, 25) is imperceptible, this is what we want.

For the example arrays A and B, I think sorting B like so will keep the arrays as optically identical as possible-
{(53, 31, 67), (118, 219, 48), (125, 195, 93)}

Constraints

Both arrays are of same length
The RGB pixel tuples themselves must remain unchanged, only their order in the array should be changed.
The first array must remain unchanged, only the second should be sorted accordingly
There may not be enough optimal elements in the second array to provide a perfect/good match, in this case the least amount of sacrifices will be preferred. The end goal is for the new pixel array to be as identical to the original array as possible. The least amount of sacrifices will ensure that the arrays of pixels, when turned into a picture, will look as identical as possible.
Note: By the word "sacrifice", I mean when the deviation in 2 pixel tuples is enough for the human eye to notice a difference.

You can't satisfy both goals.  Suppose $A=[10,20,30]$ and $B=[10,20,30]$; then you presumably want the modified $B$ to be $[10,20,30]$.  Now suppose $A=[10,20,30]$ and $B=[10,30,20]$; then you presumably want the modified $B$ to be $[10,20,30]$.  The original A and the modified B are the same in both cases, so there is no way to tell from them what the original $B$ was (both remain a possibility).


Depth of binary tree with few single children The node of a binary tree is called a single child if it has a parent but does not have a sibling. The root is by definition not considered a single child.

Let $T$ be a binary tree of size $n$, and let $k$ be the number of vertices in $T$ that are single children.
Is it true that if $\frac{k}{n}\leq \frac{1}{2}$
then the height of $T$ is $O(\log n)$?

You can construct a tree with no single children which has height $(n-1)/2$:
.


A question on encoding Assuming there is a machine which can effectively calculate functions not computable by a TM (or the Church-Turing thesis as false) What can we say about aTM solving a problem encoded by this machine...

Q1.  Is there a not trivial example of a Turing decidable problem which still remains decidable once encoded with a non-Turing computable function?

Q2. Is there a counter example?

Q1. The empty language is decidable however you encode it.

Q2. Represent the natural number $n$ as the encoding of the $n$th Turing machine that halts when started with a blank tape. Under this encoding, any set of natural numbers, except for $0$ and $\mathbb{N}$ is undecidable.


Improve algorithmic complexity We have an array of N size. We have to perform Q queries on it, in which each Query contains and Index I for which we do:

for j=I+1 to N:
  if A[j]<A[I]:
    A[j]=0

The Queries are not independent of each other so we need to use the changed Array everytime.

I have given a lot of thought but was able to come up only with brute force solution with complexity of O(Q*N). Can anyone tell a better solution?

Eg:-

Array- 4 3 4 3 2, Query-3 2
After Query 1(Index 3, element 3)- 4 3 4 3 0
After Query 2(Index 2,element 4)-4 3 4 0 0

Solving this problem benefits from geometrical intuition. Think that for each index $i$, the pair $(i, A[i])$ represents a point in 2D-space. Also we can think that assigning $A[j]=0$ is the same as removing the point $(j, A[j])$ from this space. Now a query with index i means removing all points that are left and below of point $(i, A[i])$.

Now the set of removed points can be represented with a set of points $(i_1, A[i_1]), (i_2, A[i_2]), \ldots, (i_k, A[i_k])$, for which $i_p < i_{p+1}$ and $A[i_p] < A[i_{p+1}]$ for all $1 \le p < k$. A point $(j, A[j])$ is removed if there is some $p$ for which $i_p < j$ and $A[i_p] > A[j]$. The picture https://en.wikipedia.org/wiki/Maxima_of_a_point_set#/media/File:Maxima_of_a_point_set.svg from Wikipedia might gives intuition for this (though it is left-right mirrored compared to our definition).
This set representation can be maintained with a balanced binary search tree. We can check in $O(\log n)$ time if a point $(j, A[j])$ is removed by finding the largest $i<j$ such that $(i, A[i])$ is in the set, and checking if $A[i] > A[j]$. For performing the query in your problem, first check if the given point $(i, A[i])$ already is removed. If it's not, insert it into the set in $O(\log n)$ and repeatedly check if the next element with $j>i$ has $A[j] < A[i]$, and remove it. This can be done in $O(k \log n)$, where $k$ is the number of removed elements, so the amortized complexity if $O(\log n)$.

In summary, your queries can be answered in $O(\log n)$ amortized complexity.


No need to rename a free variable in substitution? I wonder if the following two substitutions are correct:
$$(x\,y)[x:=y] = (y\,y)$$

$$ \lambda y. (x\,y) [x:=y] = \lambda z.(y\,z)$$

They are what I understand from http://en.wikipedia.org/wiki/Lambda_calculus#Substitution.

Although I can follow the rules there mechanically, I wonder why there is no renaming of $y$ to $z$ in the first substitution, while there is in the second?

Is it  correct that in substitution $E[x:=M]$, if both $E$ and $M$ have some free variable with the same name, there is no need to rename the free variable in $E$, just as in the first substitution? Thanks.

Yes, it is all correct.

Lambda-calculus may be just taken as a formal system, with rules to be
followed. Period.

However, it may be useful to try to understand intuitively why the
rules are what they are.

So the following is very informal and should be taken as an attempt at
answering intuitively.

Consider whether the following expressions are equivalent:

$y$ and $z$ : they are not equivalent because a substitution on $y$ has
no effect on $z$, and conversely. The variables $y$ and $z$ are free
variables. They stand for themselves, or for
whatever value is associated to them in an environment where you
evaluate the expression, or by a substitution. Changing a free
variable for another (it is not renaming in such a case) will change
what you get in the environment, or by applying a substitution (which
amounts to the same).
$\lambda y. (x\,y)$ and $\lambda z.(x\,z)$ : they are equivalent
via alpha conversion. When applied to the same argument, and more
generally when used in the same context, they will always give the
same result. The variables $y$ and $z$ are bound variables. Renaming
a bound variable can be done at any time,
independently of the context, without ever changing the behavior of
the $\lambda$-abstraction.

The renaming in your example $ \lambda y. (x\,y) [x:=y] = \lambda
z.(y\,z)$ is needed because the $y$ in the substitution is a free
variable (possibly taking a value in whatever environment or
substitution may be provided). Without the renaming, it would be
undistinguisable from the bound variable of the $\lambda$-abstraction
once the substitution is performed. To avoid that, the bound variable
is renamed, since renaming it does not matter.

Contrarily, in the expression $(x\,y)[x:=y]$, both occurences of $y$
stand for the same free variable $y$ in the current environment. There
is no reason to try distinguishing them.


How to show that L = L(G)? Specifying formal languages by giving formal grammars is a frequent task: we need grammars not only to describe languages, but also to parse them, or even do proper science. In all cases, it is important that the grammar at hand is correct, that is generates exactly the desired words.

We can often argue on a high-level why the grammar is an adequate representation of the desired language, omitting a formal proof. But what if we are in doubt or need a formal proof for some reason? What are techniques we can apply?

This is supposed to become a reference question. Therefore, please take care to give general, didactically presented answers that are illustrated by at least one example but nonetheless cover many situations. Thanks!

Grammars are inherently recursive objects, so the answer seems obvious: by induction. That said, the specifics are often tricky to get right. In the sequel I will describe a technique that allows to reduce many a grammar-correctness proof to mechanical steps, provided some creative preprocessing is done.
$\newcommand{\lang}[1]{\mathcal{L}(#1)}
 \newcommand{\sent}[1]{\vartheta(#1)}
 \newcommand{\derive}{\mathbin{\Rightarrow}}
 \newcommand{\derivestar}{\mathbin{\Rightarrow^*}}
 \newcommand{\nats}{\mathbb{N}}$

The basic idea is to not restrict oneself to words of grammar and language; it is hard to grasp the structure of the grammar in this way. Instead, we will argue about the set of sentences the grammar can create. Furthermore, we will split one daunting proof goal into many small goals that are more tractable.

Let $G=(N,T,\delta,S)$ a formal grammar with non-terminals $N$, terminals $T$, rules $\delta$ and starting symbol $S \in N$. We
denote by $\sent{G}$ the set of sentences that can be derived from $S$ given $\delta$, that is $\alpha \in \sent{G} \iff S \derivestar \alpha$. The language generated by $G$ is $\lang{G} = \sent{G} \cap T^*$. Suppose we want to show that $L = \lang{G}$ for some $L \subseteq T^*$.

The ansatz

Here is how we go about that. We define $M_1, \dots, M_k \subseteq (N \cup T)^*$ so that

$\displaystyle \sent{G} = \bigcup_{i=1}^k M_i$ and
$\displaystyle T^* \cap \bigcup_{i=1}^k M_i = L$.

While 2. is usually clear by definition of the $M_i$, 1. requires some serious work. The two items together clearly imply $\lang{G} = L$ as desired.

For ease of notation, let's denote $M = \bigcup_{i=1}^k M_i$.

The rocky road

There are two major steps to performing such a proof.

How to find (good) $M_i$?
One strategy is to investigate phases the grammar works through. Not every grammar is amenable to this idea; in general,
this is a creative step. It helps if we can define the grammar ourselves; with some experience, we will be able to define
grammars more tractable with this approach.
How to prove 1.?
As with any set equality, there are two directions.

$\sent{G} \subseteq M$: (structural) induction over the productions of $G$.
$M \subseteq \sent{G}$: Usually one induction by $M_i$, starting from the one that contains $S$.

This is as specific as it gets; the details depend on the grammar and language at hand.

Example

Consider the language

$\qquad \displaystyle L = \{ a^n b^n c^m \mid n,m \in \nats \}$

and the grammar $G = (\{S,A\}, \{a,b,c\}, \delta, S)$ with $\delta$ given by

$\qquad \begin{align}
  S &\to Sc \mid A \\
  A &\to aAb \mid \varepsilon
\end{align}$

for which we want to show that $L = \lang{G}$. What are the phases this grammar works through? Well, first it generates $c^m$ and then $a^n b^n$. This immediately informs our choice of $M_i$, namely

$\qquad \begin{align}
  M_0 &= \{Sc^m \mid m \in \nats \} \;, \\
  M_1 &= \{ a^n A b^n c^m \mid m,n \in \nats \} \;, \\
  M_2 &= \{ a^n b^n c^m \mid m,n \in \nats \} \;. \\
\end{align}$

As $M_2 = L$ and $M_0 \cap T^* = M_1 \cap T^* = \emptyset$, item 2. is already taken care of. Towards 1., we split the proof in two parts as announced.

$\mathbf{\sent{G} \subseteq M}$

We perform structural induction along the rules of $G$.

I.A.: Since $S = Sc^0 \in M_0$ we anchor successfully.

I.H.: Assume for some set of sentences $X \subseteq \sent{G}$ that we also know $X \subseteq M$.

I.S.: Let $\alpha \in X \subseteq \sent{G} \cap M$ arbitrary. We have to show that whatever form $\alpha$ has and whatever rule is applied next, we don't leave $M$. We do this by complete case distinction. By induction hypothesis, we know that (exactly) one of the following cases applies:

$w \in M_0$, that is $w = Sc^m$ for some $m \in \nats$.
Two rules can be applied, both of which derive a sentence in $M$:

$Sc^m \derive Sc^{m+1} \in M_0$ and
$Sc^m \derive Ac^m = a^0Ab^0c^m \in M_1$.

$w \in M_1$, i.e. $w = a^nAb^nc^m$ for some $m,n \in \nats$:

$w \derive a^{n+1}Ab^{n+1}c^m \in M_1$ and
$w \derive a^nb^nc^m \in M_2$.

$w \in M_3$: since $w \in T^*$, no further derivations are possible.

Since we have successfully covered all cases, the induction is complete.

$\mathbf{\sent{G} \supseteq M}$

We perform one (simple) proof per $M_i$. Note how we chain the proofs so "later" $M_i$ can anchor using the "earlier" $M_i$.

$M_1$: We perform an induction over $m$, anchoring in $Sc^0 = S$ and using $S \to Sc$ in the step.
$M_2$: We fix $m$ to an arbitrary value and induce over $n$. We anchor in $Ac^m$, using that $S \derivestar Sc^m \derive Ac^m$ by the former proof. The step progresses via $A \to aAb$.
$M_3$: For arbitrary $m,n \in \nats$ we use the former proof for $S \derivestar a^nAb^nc^m \derive a^nb^nc^m$.

This concludes the second direction of the proof of 1., and we are done.

We can see that we heavily exploit that the grammar is linear. For non-linear grammars, we need $M_i$ with more than one variable parameter (in the proof(s)), which can become ugly. If we have control over the grammar, this teaches us to keep it simple. Consider as deterring example this grammar which is equivalent to $G$:

$\qquad \begin{align}
  S &\to aAbC \mid \varepsilon \\
  A &\to aAb \mid \varepsilon \\
  C &\to cC \mid \varepsilon
\end{align}$

Exercise

Give a grammar for

$\qquad L = \{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \nats, k \neq o, 2l = n, m \geq 2 \}$

and prove its correctness.

If you have trouble, a grammar:

   Consider $G = (\{S,B_r,B_l,A,C\}, \{a,b,c\}, \delta, S)$ with productions

 $\quad \begin{align} S   &\to bSb \mid B_l \mid B_r \\     B_l &\to bB_l \mid bA \\     B_r &\to B_r b \mid Ab \\     A   &\to aAaa \mid C \\     C   &\to bcC \mid bcbc   \end{align}$

and $M_i$:

   $\quad\begin{align}     M_0 &= \{ b^i S b^i \mid i \in \nats \} \\     M_1 &= \{ b^i B_l b^o \mid o \in \nats, i \geq o \} \\     M_2 &= \{ b^k B_r b^i \mid k \in \nats, i \geq k \} \\     M_3 &= \{ b^k a^i A a^{2i} b^o \mid k,o,i \in \nats, k \neq o \} \\     M_4 &= \{ b^k a^l (bc)^i C a^{2l} b^o \mid k,o,l,i \in \nats, k \neq o \} \\     M_5 &= L   \end{align}$

What about non-linear grammars?

The characterising feature of the class of context-free languages is the Dyck language: essentially, every context-free language can be expressed as the intersection of a Dyck language and a regular language. Unfortunately, the Dyck language is not linear, that is we can give no grammar that is inherently suited to this approach.

We can, of course, still define $M_i$ and do the proof, but it's bound to be more arduous with nested inductions and what not.
There is one general way I know of that can help to some extent. We change the ansatz to showing that we generate at least all
required words, and that we generate the right amount of words (per length). Formally, we show that

$\displaystyle \sent{G} \supseteq L$ and
$\displaystyle |\lang{G} \cap T^n| = |L \cap T^n|$ for all $n \in \nats$.

This way, we can restrict ourselves to the "easy" direction from the original ansatz and exploit structure in the language, ignoring overcomplicated features the grammar may have. Of course, there is no free lunch: we get the all new task of counting the words $G$ generates for each $n \in \nats$. Lucky for us, this is often tractable; see here and here for details¹. You can find some examples in my bachelor thesis.

For ambiguous and non-context-free grammars, I'm afraid we are back to ansatz one and thinking caps.

When using that particular method for counting, we get as a bonus that the grammar is unambiguous. In turn, this also means that the technique has to fail for ambiguous grammars as we can never prove 2.


A Reduction from XORSAT to 2-SAT Does anyone know of a non-trivial reduction from XORSAT to 2-sat since they are both in P?  (By non-trivial I mean one that does not just solve the instance of XORSAT and map it to a fixed instance of 2-sat.  Rather I'm looking for a way to solve XORSAT by a different method other than just using Gaussian Elimination or some other method of linear algebra.)

Your problem can be posed more formally as follows: Is there a weak reduction from XORSAT to 2SAT? Here weak can be, for example, logspace or AC$^0$.

We know that 2SAT is NL-complete under AC$^0$ reductions, while restricted versions of XORSAT (say 3XORSAT) are $\oplus$L-complete under AC$^0$ reductions, see this paper proving a refined Schaefer dichotomy theorem. Although NL$\subseteq \oplus$L non-uniformly (see this answer), we don't expect the converse to hold, and in particular we don't expect there to be a weak reduction from $\oplus$L to NL. Unfortunately I'm unaware of any concrete results in this direction.

Summarizing, it is expected that there is no weak reduction from XORSAT to 2SAT, but I'm not sure there's much technical work supporting this conjecture.


Bijective algorithm(s) that can shuffle a range of numbers back and forth I've spent the last hours trying to come up with an algorithm that shuffles an ordered set of numbers (i.e a simple range of numbers) in a way that I can retrieve from a shuffled value the original value that was on that position without the need to store all relationships between shuffled values and their counterparts.

The statement above may not make any sense to you, but I've learned some terms while trying to find such algorithm that may help me to describe what I mean...

First of all I believe that this algorithm/function is bijective, which means it is deterministic and one member of $A$ has only one correspondent member of $B$ and vice-versa:

Another peculiarity is that input and output domains are exactly the same so, following the above example, $A$ = $B$ = $D$ with $D$ being a range from $m$ to $n$.

To sum everything up (sorry I'm pretending that I know math):

$D = \{x \in \mathbb N\ | m \le x \le n \}$

$
\forall x \in D  \land \forall y \in D\\
f(x) = y \implies \exists  g(y) = x
$

What could be done to simply implement $f$ and $g$ ?

The closest solutions I've found are some kind of block cipher which I'm unable understand nor tweak to achieve the desired behavior which is much simpler.

As one last attempt to explain this, here is a simple use case:

Consider integer codes that can range from 1 to 2^31
On the backend these codes are used sequentially, getting increased one by one
Instead of sending one of these codes for a client, our function picks another code from that range to represent the original one
Despite we need to use those codes sequentially we are only sending the random values for the clients so it looks random from his perspective
When we receive this code back the from the client we're able to tell the original code
We would also be able to change the way that these codes are "shuffled", so different codes could be exposed over time while leaving the original ones untouched on our side

Sorry if I wasn't clear enough or destroyed math notations forever.

The subject is called format-preserving encryption,

and your last bullet point is addressed by tweaks.

Simple
http://web.cs.ucdavis.edu/~rogaway/papers/feistel.pdf

http://arxiv.org/pdf/1208.1176.pdf

http://web.cs.ucdavis.edu/~rogaway/papers/sr.html
Complex


Data structure to insert, update and sort indexes by frequency and query an index for a particular cumulative frequency Here is the description of the data structure I am looking for:

Initial Original Data

Index | Frequency |
  1         3
  2         1
  3         7
  4         2
  5         6

Now it should be kept Sort-ed by their frequency inside the data structure like this,

Index | Frequency | Cumulative Frequency |
  2         1               1
  4         2               3
  1         3               6
  5         6               12
  3         7               19

Now, if I Insert a new entry item (index 6) with frequency of 2, the data structure should maintain it like this:

Index | Frequency | Cumulative Frequency |
  2         1               1
  4         2               3
->6         2               5
  1         3               8
  5         6               14
  3         7               21

Now, a frequency increase of 3 at Index 2 should Update the structure as following:

  Index | Frequency | Cumulative Frequency |
|   2           1               1
|   4           2               2
|   6           2               4
|   1           3               7
|-> 2        1+3 = 4            11
    5           6               17
    3           7               24

You can see above that the frequencies can repeat in many indices. (see index 4 and  6 above).

Now my Query to find the index that contains a cumulative frequency should be resulted in the following way

Query(cumulative frequency) | Result (Index at the data structure)
            3                       6
            1                       4
            20                      3
            7                       1

I have already explored Fenwick Tree (Binary Indexed Tree). It has a very efficient, O(log(n)), way to insert and update frequency at an index and to find the index for a specfic cumulative frequency. But I did not find a way to keep the Indexes sorted by their frequency.

Other structures like Treap, Red-Black tree can store the frequency in a sorted way but I could not find a way to search the index with the specific cumulative frequency using those data structures.

This can be easily handled using a standard balanced tree data structure, augmented with a Fenwick tree and a hashmap:

Store the items in a binary tree.  Each leaf stores information about a single item.  The leaves should be stored in increasing frequency, i.e., sorted by frequency, from least frequent to most frequent.
To help compute the cumulative frequency, augment the binary tree to store some additional information in each node.  In each node, store the sum of the frequencies of all of the items underneath it (i.e., of all of the leaves under that node).  These values can be easily updated as the tree changes.  This is basically the idea behind Fenwick trees for computing prefix sums.
Also, add a hashmap that maps from the value (what you call "index") to the associated leaf where that index is found in the binary tree.

Now you can support all of the operations you mentioned efficiently.  If you use a standard balanced binary tree data structure, the running time for all operations is $O(\log n)$:

Sort: All of the items are already stored in sorted order, sorted by increasing frequency, so this happens automatically.
Insert: You can insert a new item into the tree in $O(\log n)$ time.
Update: You can increase the frequency of a particular item by deleting it from the tree, increasing its frequency, and inserting it into the new location.  In a balanced binary tree, this takes $O(\log n)$ time, since deletion can be done in $O(\log n)$ time, as can insertion.
Query: You can now find the first index $i$ where the sum of the frequencies of the first $i$ leaves is at least $t$, by using binary search.  Note that you can efficiently compute prefix sums of the frequencies by using the extra values stored in each node of the tree.  Therefore, binary search suffices, and can be done in $O(\log n)$ time.

There are many balanced binary tree data structures, including red-black trees, AVL trees, 2-3 trees, etc.  They all have the property that standard operations are guaranteed to take at most $O(\log n)$ time.  You can use any of them for your purposes.


Where does entanglement fit into quantum computing? I've been reading up on quantum computing online from various sources, including this link http://twistedoakstudios.com/blog/Post2644_grovers-quantum-search-algorithm.

I get how quantum gates work, destructive interference, and how you can simulate a quantum computer using matrix math and complex numbers.

Does entanglement have a use in quantum computing?  I haven't yet seen anything explicitly talk about entanglement and whether it's used in QC, but I feel like it's possible it might be implicitly stated and I could be missing it - or maybe not!

Thanks!

The entanglement of quantum particles is, implicitly or explicitly, the reason why quantum computing is so fast. You will know by now that a qubit (implemented for example as a photon's polarization) can be represented as a unit vector of two complex numbers, and that it may be manipulated by a 2-by-2 matrix of complex numbers. If you have two quantum systems described by their respective state vectors $|a\rangle$ and $|b\rangle$, which describe the two systems in isolation, their composite state is described by the tensor product of these two vectors: $|a\rangle \otimes |b\rangle$. If you operate on $|a\rangle$ with matrix $U$, you get the composite state $(U|a\rangle) \otimes |b\rangle$, and so forth.
Entanglement comes when you operate on this composite state and bring it to a state which cannot emerge as the tensor product of two state vectors. For example, the state $\frac{1}{\sqrt{2}}(|00\rangle + |11\rangle)$ is not the tensor product of any two vectors (verify this as an excercise). In such states, measuring qubit $|a\rangle$ has an effect on $|b\rangle$. For example, if you performed a partial measurement (that is, a measurement of ostensibly only one qubit) on the most significant bit of $\frac{1}{\sqrt{2}}(|00\rangle+|11\rangle)$, and you measured it to be $0$, then measuring the least significant bit will yield $0$ with certainty, too, and vice versa.
A good first example for studying entanglement is Deutsch' problem, where the algorithm goes from $(|0\rangle+|1\rangle) \otimes (|0\rangle - |1\rangle)$, a state which can be expressed as the tensor product, to a state which can no longer be expressed as any tensor product, using an operator which cannot be expressed as the tensor product of two operators.


Hoare triple: Loop invariant and correctness The following Hoare triple in which variable a is an array of integers, and len, max, i, n, j and m are integer-valued variables. Provide a loop invariant (using predicate logic) suitable for proving partial correctness
of the Hoare triple. Explain in words why it is a loop invariant and why it is sufficient
to prove partial correctness.

$$\begin{align*}
&\{0 < len \} \\
&i = 0;  \\
&n = 1;  \\
&j = 0;  \\
&m = 1;  \\
&\textbf{while}\;(i+n < len)\;\{ \\
&\quad\textbf{if}\;(a[(i+n)]-a[(i+n-1)] ≤max)\;\{ \\
&\quad\quad n = n+1; \\
&\quad\quad \textbf{if} (m<n)\;\{ \\
&\quad\quad\quad j = i; \\
&\quad\quad\quad m = n; \\
&\quad\quad \}\;\textbf{else}\;\{skip\} \\
&\quad\ \}\;\textbf{else}\;\{ \\
&\quad\quad\quad i=i+n; \\
&\quad\quad\quad n=1; \\
&\quad\ \} \\
&\ \} \\
&\;\{0≤j∧1≤m∧(j+m)≤len∧ \\
&\quad\quad (∀ k : Z · ((j < k ∧ k < j+m) ⇒ (a[k] − a[(k−1)] ≤ max )))\}
\end{align*}$$

I tried to use loop rule and get the invariant I by the third premise:

$$\{I \land \lnot b\} \; [] \; S \; \{Q\}$$

b is len ≤ i+n, but postcondition Q is too complex.
Then I try to create two table to find rule, one table predicate a[(i+n)]−a[(i+n−1)]≤max, and predicate len = 6, then I get the program will terminate at fifth loop, and another table predicate a[(i+n)]−a[(i+n−1)]>max also len =6, I get the same answer that terminates at fifth loop. In addition, I tried one time ≤max and one time >max, then I get the same answer. So here I find a part of invariant which is loop times = len - 1. From above is what I did, but I have no idea about how to go next step.

I believe the loop invariant is the same as the postcondition, except with j and m swapped with i and n, respectively. That statement can be proven true at the start and end of each loop. This is true partially by virtue of the fact that the final implication is trivially true when n = 1 (as in the outer else condition), because no k value is in the range.

The fact that j and m are only ever assigned from i and n while the invariant is true, and the postcondition is true prior to the loop, implies that the postcondition holds.

Another key observation is that i+n < len implies i+n+1 ≤ len, so the proposed invariant holds true, even after the loop condition fails.

I hope that helps.


Number of equivalence classes in $P$ I am currently taking a course which involves computational complexity. I was told that polynomial equivalence (polynomial time reduction) divides P into exactly 3 equivalent classes, namely $\phi$ , $\Sigma^*$ and $P - \{\phi,\Sigma^*\}$. I am unable to figure out how this is true, specifically how if $L_1,L_2 \in P, L_1 \sim_P L_2$. I think there's a simple fact/idea I am missing out on, but I don't know what it is.

Suppose that $L_1 \in \mathsf{P}$ and $L_2$ is non-trivial. Pick $y \in L_2$ and $z \notin L_2$ arbitrary. The following is a polynomial time reduction from $L_1$ to $L_2$:

Input: $x$.
Check whether $x \in L_1$.
If so, output $y$.
Otherwise, output $z$.

This runs in polynomial time since $L_1 \in \mathsf{P}$.


Is it common in the literature to define regular languages and serialization languages as programming languages? Often when I create programs I use operating-programming language such as Bash for automating OS operations, structure ("markup") language such as HTML to define structures, styling language such as CSS to style structures, and programming (behavior defining) language such as JavaScript, to define the "nature of interaction" with programming by user interface.

But there are two other types of languages I sometimes use when creating programs:
Regular languages such as POSIX basic regular extensions or PERL compatible regular extensions, and Serialization languages such as JSON or YAML; from my experience, it is reasonable to assume that the former type can be combined with generally all operating-programming languages and behavior defining languages, while the latter type I usually combined with JavaScript.

Is it common in the (Computer Science) literature to define regular languages and serialization languages as programming languages (as sharpening the behavior of a program)?

No. In formal language theory, a language is just a set of strings, and it has nothing to do with programming. Note also that the things that programming languages such as Perl call "regular expressions" are more powerful than the regular expressions used in computer science and can define some non-regular languages.


Computing FOLLOW sets for a LL(1) grammar I am trying to learn compiler design. But I get confused when I have to deal with computing the follow set specifically for the empty word.

Given the grammar:

S-> ABC
A-> Aa|b
B-> Bc|d
C-> Ce|f

I've come up with the following first and follow sets:

1 S->ABC   First(1)-{b}
2 A->bA'   First(2)-{b}
3 A'->aA'  First(3)-{a}
4 A'->E    Follow(4)- ??
5 B->dB'   First(5)-{d}
6 B'->cB'  First(6)-{c}
7 B'->E    Follow(7)- ??
8 C->fC'   First(8)-{f}
9 C'->eC'  First(9)-{e}
10 C'->E   Follow(10)- ??

Please help me determine the follow sets I've indicated with ??. Is there a formula I can use to determine the follow sets?

The follow set of something translates to asking: what symbol can come next in the string we are trying to read with the grammar rules the machine has?

Let's say we take a string "abba". The input tape symbol will end the string with $ as the delimiter. So we can say that 'a', 'b', 'b', 'a' and '$' are the symbols that the read/write head of the parser will see while evaluating this string. I am taking the below production rules for this grammar.

S->AB
A->ab|a
B->baB|E

The string "abba" can be evaluated in the following manner:

S->AB
 ->abB
 ->abbaB
 ->abbaE

In the above case, Follow(A) = {b,$}.

'b' is part of the set because B's production follows A's production, S->AB, and whatever is the first letter that B produces will follow the last letter A produces.

Similarly, $ is part of the set because of B's epsilon production.
When B is evaluated using rule B->E, then for Follow(A) there is no first letter produced by B.

In such a case where the Follow(A) is an epsilon production,

S->AE | using B->E

Then Follow(A) becomes Follow(S) which is $.

If you look at the string "abba", once the last a is read the only symbol that can come after the string is $.

As a generalization, if X->ABC and C->E, then Follow(B) = Follow(X).

In your question's example, evaluating Follow(A') results in only two possibilities where A' is on the RHS and can have a following symbol. Below are the two productions that can result:

A->bA'
A'->aA'

Unfortunately, out of the two one is Follow(A') = Follow(A') as per the rule I have mentioned in last line of the answer.

Hence we can only consider the other follow which is

Follow(A') = Follow(A)

i.e.

Follow(A) = First(B)

In a practical sense, if we have

S->ABC

and

A-> bA'
A'->aA'|E

Then whenever we have an A production, it will further lead to either A -> baA' or A->b (if we take A'->E).

In both cases the only thing that can follow A' is whatever is the first of B.

In a similar manner we can compute the same for Follow(B') and Follow(C').


Sequential History in Herlihy and Wing's Linearizability paper I've been reading Herlihy and Wing's paper Linearizability: A Correctness Condition for Concurrent Objects (ACM Transactions on Programming Languages and Systems, 12(3):463–492, 1990; PDF) and there's one piece of the paper that is a fairly small detail, but on which I'm stuck anyway. They define a sequential history as one satisfying two conditions:

First event of $H$ is an invocation
Each invocation, except possibly the last, is immediately followed by a matching response. Each response is immediately followed by a matching invocation.

Question 1 Since an invocation and response match iff they have the same object and process, does "each response is immediately followed by a matching invocation" imply that all events in a sequential history share the same object and process (since each event matches the prior event)?

Question 2 Later in section 2, they offer the following as an example of a sequential history, even though it involves multiple processes:

q Enc(x) A
q Ok() A
q Enq(y) B
q Ok() B
q Deq() B
q Ok(x) B
q Deq() A
q Ok(y) A
q Enq(z) A
q Ok() A

I suspect that the definition of sequential history actually doesn't include the constraint "each response is immediately followed by a matching invocation" but maybe it does and I'm just misreading it. In either case, thanks for any enlightenment anyone can provide!

I've come to the conclusion that the constraint "each response is followed by a matching invocation" should omit the word "matching", and the paper should be read as if it weren't there. My evidence for this is that related literature and conference proceedings seem to omit it, either literally or effectively.

For example, the proceedings Principles of Distributed Systems: 14th International Conference (Google Books) includes a summary of a sequential history and linearizability and omits the second constraint completely:

  History $H$ is called Sequential if the first event of $H$ is an invocation, and each invocation, except possibly the last, is immediately followed by a matching response.

Another conference proceedings that I found, Networked Systems: Second International Conference (Google Books) includes the second constraint without the word "matching":

  A history is sequential if its first event is an invocation, and then (1) each invocation event, except possibly the last, is immediately followed by the matching response event, and (2) each response event, except possibly the last, is immediately followed by an invocation event.


Are there any open source SAT solvers with UNSAT core extraction algorithm built in? Just like the title says. I need to use a SAT solver on a series of CNF formulas but not only do I need an answer of the type satisfiable/unsatisfiable but also some subset of clauses whose conjunction is still unsatisfiable (the unsatisfiability core).

I have read somewhere that it is possible to hack the code of some SAT solver (like MiniSAT) to produce UNSAT core, but I don't feel competent enough to actually do it. I was hoping that somebody else have already done it and have uploaded the code somewhere, but either that is not the case or I suck at Googling.

MUSer2 is probably the tool for extracting minimal unsatisfiable cores (MUS) currently. It treats the SAT solver as a black box, so you can plug in any solver you want.

If you want a solver with MUS extraction capability, the newest version of PicoSAT comes with a utility tool PicoMUS that does the job.


How to prove finding two paths that are at least k edges apart is NP-hard? Let $G=(V, E)$ be an unweighted, undirected, and connected graph. Given two start vertices $s_1$ and $s_2$ and two end vertices $t_1$ and $t_2$ is there a path from $s_1$ to $t_1$ and $s_2$ to $t_2$ such that the closest number of edges between the two paths is at least $k$? Two paths are $k$ close if the minimum of the shortest distances between any vertex on the first path to any vertex on the second path is $k$.

I was thinking of reducing from 3SAT and letting the first path represent the variables and the second path represent the clauses, but I am unsure where to go from there.

You can reduce from 3SAT.

The graph has two parts. One part is the "variable" part. For each of the variables $v_1,\ldots,v_n$ there are two three vertices $v_i^+,v_i^-,v_i$, and this part consists of the following edges, for $i \in [n]$:

$$(v_{i-1},v_i^+),(v_{i-1},v_i^-),(v_i^+,v_i),(v_i^-,v_i)$$

Here $v_0$ is a new vertex, identified with $s_1$, and $v_n$ is identified with $t_1$.

The second part is the "clause" part. For each of the clauses $C_1,\ldots,C_m$ there four vertices $w_j^1,w_j^2,w_j^3,w_j$, connected much as before, with $s_2$ and $t_2$.

We connect $v_i^b$ with $w_j^r$ via a path of length $k$ (for some large enough constant $k$) if the literal $v_i^b$ (either $v_i$ or $\overline{v_i}$, according to $b$) is the opposite of $j$'th literal in $C_j$.

Also, we take all the mindpoints of these paths, and connect all of them (making them into a clique).

We can think of an $(s_1,t_1)$-path as a truth assignment, and of an $(s_2,t_2)$-path as identifying a satisfied literal in each clause. The minimal distance is more than $k$ if this is indeed the case, and only $k$ otherwise.

You also need to verify that there is no point for the paths to cross between the parts. If only one of the paths crosses, then the two paths will be close together (at some constant distance, which for large enough $k$ will be smaller than $k$) immediately after the crossing. If both cross, then the midpoint clique will ensure that they are at distance at most 1.


Proving/Disproving that language L is non-regular/CFL Here are three examples of questions I run into. I'm not looking for solutions.

  If $L$ is CFL then $L' = \{ ww^R | w \in L \}$ is non-regular.
  If $L$ is non-regular then $L' = \{ ww^R | w \in L \}$ is non-regular too.
  If $L_2, L_3, L_4$ are regular languages and $L_1 \cup L_2 = L_3$ and $L_1 \cap L_2 = L_4$, then $L_1$ is regular.

The problem I'm facing here is that I'm having hard time to figure out what how to prove such claims.

Lets say I'd like to prove claim 1, I can't seem to understand what exactly should I prove?
If I assume that $L'$ is regular, then what way can I follow that will lead me to contradiction? I would go for the intersection with CFL language, but this won't help me as CFL is closed under intersection with regular languages. So I'm pretty lost here.

Take claim 3 for example, after spending a lot of time trying to find a counter-example, I have strong feeling that this claim is true. (please don't tell me if I'm wrong, this post is not about the answers). Yet I couldn't find out what exactly should I prove? Of course that $L_1$ is regular but in what way may I do that?

I hope you get my situation. What I'm asking from you is to describe how would your proof be written in the above claims? What would you try to archive in your proof?

Thanks a lot for your time.

In fact it turns out that there is no simple method to prove things like this. Except when you want to disprove a statement, then a well-chosen counter example suffices. But also here there are no guidelines how to find them. Experience and trial and error, I would say. In your three questions I see three different approaches.

For (1) go look for a counter-example. Since the statement is true for most languages, you have to look for trivial special cases, but still contradicting the general claim.

For (2) you can try contra-positive. Instead of $A \Rightarrow B$ consider the equivalent $\lnot B \Rightarrow \lnot A$. This is then a (somewhat exotic) closure property. Can you recover $L$ from $L'$?

And I am afraid that (3) looks like simple Boolean set algebra. It is in fact the most straightforward of the three questions.


Is the language $K=\{u \in\{0,1\}^n\mid n \geq 0, \forall_{v \in\{0,1\}^n} (u+v) \in L \}$ regular? For two words $w,v \in\{0,1\}^*$ of equal length, let $w+v \in\{0,1,2\}^*$ denote the word in which the $i$-th word is the sum of $i$-th position of $w$ and $v$, as follows: if $w=a_1 \ldots a_n$ and $v=b_1 \ldots b_n$, then $w+v=c_1 \ldots c_n$, where $c_i=a_i+b_i$ for each $i\in \{1, \ldots, n\}$.
Assume $L \subseteq \{0,1,2\}^*$ is a regular language. Decide whether the language $$K=\{u \in\{0,1\}^n\mid n \geq 0, \forall_{v \in\{0,1\}^n} (u+v) \in L \}$$ is regular.

I would appreciate any hint as I don't know how to start. I know that the every word u+v can be easily converted to be over the alphabet $\{0,1\}^*$ such that
$h(a_i) = 0$ if $a_i=0$ and $h(a_i) = 1$ if $a_i=1$ and
if $a_i = 2$, then $h(a_{i+1})=a_{i+1}+1$. Then $u+v$ is just binary addition.

It might be easier to consider the complement of your language:
$$
\overline{K} = \{ u \in \{0,1\}^* : \exists v \in \{0,1\}^{|u|} \text{ s.t. } u+v \in \overline{L} \}.
$$

You can now easily convert an NFA for $\overline{L}$ to one for $\overline{K}$ by replacing all edges labelled $1$ with edges labelled $0,1$ and all edges labelled $2$ with edges labelled $1$.

I'll let you figure out why this works.


Circular Doubly Linked List find length with single pointer I have pointer to circular doubly linked list with random values of 0 or 1.
Example: [{prev,0,next},{prev,0,next},{prev,1,next},{prev,0,next}...]
I have a single pointer to the first item of the list.
I need to find the length of the list without to create any additional pointers.
In addition, I can change the values of each node between 0 to 1 or 1 to 0.

I thought about Josephus Circle algorithm - with no success.

My main problem is that I don't even know what end of a circle/circular list is.
If you think about that, you will understand it is not an easy question.

I think the following algorithm would do it:

Start by setting the value in the first node to $1$.
Follow next pointers until you encounter a node with value $1$, while keeping a counter $c$ of how many nodes you have encountered.
Set the value of the node to $0$ and follow prev pointers for $c$ steps

If the value of the node (which should be the first node) is now $0$, the list has $c-1$ elements,
otherwise, follow next pointers for $c$ steps and continue with step 2.


Methods for Finding Asymptotic Lower Bounds I've found in many exercises where I'm asked to show that $f(n)=\Theta(g(n))$ where the two functions are of the same order of magnitude I have difficulty finding a constant $c$ and a value $n_0$ for the lower bound.  I'm using Corman's definition of $\Theta$:

$$\exists c_1,c_2>0\in\mathbb{R}:\forall n\geq n_0: 0 \leq c_1 g(n)\leq f(n)\leq c_2 g(n)$$

Showing the upper bound usually doesn't give me too much trouble, but for the lower bound I allot of times find myself using limits.  And even though I'm getting the right answers, I'm a bit worried that my method isn't very rigorous and that maybe I'm doing a bit of hand waving in the process.

For example, problem 2.17 from Skiena's Algorithm Design Manual:

Show that for any $a,b\in \mathbb{R}: b>0$ that $(n+a)^b = \Theta(n^b)$

In this case I used limits to help find both constants.

For the upper limit I decided to look for some $c$ such that $(n+a)^b \leq c^bn^b$.  So taking the $b$th root of each side and dividing by $n$ I have $\frac{n+a}{n}\leq c$ which gives me $1 + \frac{a}{n} \leq c$.  For any $a\in\mathbb{R}$, $\lim_{n\to\infty }1+\frac{a}{n}=1$.  If I pick $n_0>|a|$, then for $a<0$ the expression approaches 1 from the left starting arbitrarily close to $0$.  If $a>0$ then the expression approaches 1 from the right starting arbitrarily close to 2. So choosing $c=2$ will satisfy the inequality and we have $c_2=2^b$.

Now for the lower bound.  I'm looking at the same expression except with the inequality pointing the other way.  In this case I'm trying to find $n_0$ and $c$ such that $c\leq 1+\frac{a}{n}$.  The value of $n_0$ has to be greater than $|a|$ because otherwise we would have $c\leq 0$ which isn't allowed.  This puts us in the same range of values between $0$ and $2$ approaching 1 from each side.  So I choose any $c,n_0$ such that $n_0>|a|$ and $0 < c\leq 1-|\frac{a}{n_0}|$.  So I could choose $n_0=3|a|$ and $c=\frac{2}{3}$.

Thus we have $0 < (\frac{2}{3})^bn^b \leq (n+a)^b \leq 2^bn^b$ for any $n \geq 3|a|$.

Is there an easier way to do this?

Normally when looking for upper limit constants where the two functions are of the same magnitude I simply eliminate negative lower order terms and change positive ones into multiples of the highest order term such as :

$$3n^2+15n-5\leq 3n^2+15n^2=18n^2$$

But when looking for the constant for the lower bound I find myself typically resorting to looking at limits.  Is there any kind of short cut to finding the lower bound constant like there is for the upper bound constant?

You can codify your method in the following lemma.

Lemma. If $f(n)/g(n) \rightarrow C$, where $C > 0$, then $f(n) = \Theta(g(n))$.

The proof is the same as the one you gave. After you prove this lemma once and for all, you can use it forever. That's actually a good way of verifying $f(n) = \Theta(g(n))$.

Note that the converse to the lemma isn't true. For example, let $f(n) = n$ and let $g(n) = \exp\lfloor\log n\rfloor$. The ratio $f(n)/g(n)$ moves inside the interval $[1,e)$, and in particular does not tend to a constant limit.


Prove that the following language is not a regular language Prove that the following language is not a regular language:
$L = \{ 0^x1^y | x, y \geq 1\text{ and } x \geq y\vee (x < y \wedge y \mod x = 0)\}$
Is there anyone to prove this ?

Assume towards contradiction that the language is regular.
Let a be the "pumping length" given by the pumping lemma.
Let $p \geq a+2$ be a prime number. Consider the word: $w=0^p1^p \in L$.
By the pumping lemma, it can be written as $w=xyz$ where $|y| \geq 1$,
$|xy| \leq a $, $xy^nz \in L \ \ ,\forall n \geq 0$.
Consider $w' = xy^0z$.
Note that the length of zeros in w' is strictly less than p, and that the length of ones in w' is still exactly p. Also note that the length of zeros in w' is at least 2 since $z$ itself contains at least two copies of zero. Therefore, the number of zeros in w' is $ 1 < k < p $.
But in order to be in $L$, $w'$ has to satisfy $p \ \ mod \ \ k = 0$, which is equivalent to $k | p$ - contradiction!


Does 1NF require that there can be no duplicate rows? From Database   System Concepts, by  Silberschatz, Korth and Sudarshan :

  A domain is atomic if elements of the domain are considered to be
  indivisible units. We say that a relation schema R is in ﬁrst normal form (1NF) if
  the domains of all attributes of R are atomic.

From https://stackoverflow.com/a/724032/156458

  1NF is the most basic of normal forms - each cell in a table must contain only one piece of information, and there can be no duplicate rows.

If I am correct, "there can be no duplicate rows" in the second definition means exactly that there must exist at least one candidate key in the relation schema.

I wonder if the two definitions of 1NF above are the same?

In particular, is it correct that "there can be no duplicate rows" can't be implied by "the domains of all attributes of R are atomic"?

Thanks.

Updated:

This book seems to say that having a primary key implies atomic  and is it correct?

  In first normal form (INF), related attributes are organized into
  separate  tables, each with a primary key. A primary key is an
  attribute or set of attributes that uniquely defines a tuple. Thus, if
  a table is in INF, entities  within the data model contain no
  attributes that repeat as groups. W. Kent  has explained that in INF,
  all occurrences of a record must contain the  same number of fields.
  In INF, each data cell (defined by a specific tuple  and attribute) in
  the table will contain only atomic values.

What was called 1NF in the past is considered nowadays part of the definition of the Relational Data Model itself: each attribute must be a single value, neither composed, nor repeated. When we talk about relations we assume implicitly this fact, since structures with non-flat attributes are not considered proper relations.

Note, however, that there exists alternative models, called non-1NF models or NRC which are based on the concept of relations with possibly other relations as values inside tuples (so it is a kind of Nested Relational Model). Such models, presented in the scientific literature but not implemented in commercial systems, are in some sense a sort of “bridge” towards the late object-oriented data model, that allow more complex kind of data (and that have a concept of association which differs from that of foreign key).

A different aspect is that relations are sets, and not multisets (that is they cannot contains duplicate rows). This is a basic principle of the Relational Data Model: we assume that a relation is just a set, stop. For more details, see this answer.

But you should keep in mind the these are mainly theorical aspects, useful when reasoning about relations, about languages to operate on them (for instance the Relational Algebra), and about theories developed on them (for instance the Normalization Theory).

In practice, however, things can be quite different: for instance in Relational Database Management Systems you can have “relations” without keys or unique attributes, so that they can have duplicate rows. Also, you can have composed data types for attributes of records, like arrays (or, worse, people sometimes put multiple values in an attribute maybe as a single string with commas separating the intended values).


Can the definition of regular languages be simplified? Wikipedia says

  The collection of regular languages over an alphabet Σ is defined
  recursively as follows:

  The empty language Ø is a regular language.
  For each a ∈ Σ (a belongs to Σ), the singleton language {a} is a regular language.
  If A and B are regular languages, then A ∪ B (union), A • B (concatenation), and A* (Kleene star) are regular languages.
  No other languages over Σ are regular.

I think that if it is closed under concatenation, then it must be closed under Kleene star, because we can take B to be A. So the definition can be without being closed under Kleene star?

No. Closure under concatenation means that, if $A$ and $B$ are regular languages, then so is the language of strings formed by concatenating taking one string from $A$ and one from $B$. Closure under Kleene star means that, if $A$ is a regular language, then so is the langauge formed by taking any finite number of strings from $A$ and concatenating them.

If you delete Kleene star then every regular language would be finite. The reason is that any given regular language must be formed by a finite number of operations from the basic languages ($\emptyset$ and singletons). But any language whose definition involves no Kleene stars and only $k$ concatenations can only contain strings of length at most $k$, so it must be finite (it has at most $|\Sigma|^k$ strings in it).

Since there are infinite regular languages, the languages formed without Kleene star are a strict subset of the regular languages.


Big O notation comparison with constant time So,  I'm new to this whole asymptomatic notation with respect to algorithms. So say you have a $f(n) = 1/n$ and $g(n) = 1$,  would it be OK to say that $f(n)$ is not equal or is not an element of $O(g(n)) $?
 I say this because I'm actually drawing an analogy with another example.  Say in my second example $f(n) = n$ and $g(n) =n^2$ then I'm sure that $f(n)  = O(g(n))$.

In fact, $1/n = O(1)$. Recall the (simplified) definition of big O: for positive functions $f,g$, $f(n) = O(g(n))$ if there exists a constant $C > 0$ such that $f(n) \leq Cg(n)$ for all $n$. In your case, the constant $C = 1$ would do since $1/n \leq 1$ for all $n$.

The fact that $f(n) = O(g(n))$ just means that $g(n)$ is an upper bound on $f(n)$, i.e., that $g(n)$ grows at least as fast as $f(n)$. The two functions need not have the same order of growth.


Will a node with no incoming arc or no out coming arc affect the maximum flow? So in a maximum flow question, say if we have a node which is not $s$ nor $t$, if it has no incoming arc, can we delete it without affecting the maximum flow? What if it has no output arc? How so?

Yes, you can. If it has, say, no outcoming edge, there can be no flow routed over this node. Otherwise the flow conservation constraint for this node ($v$)
$$\sum_{(u,v) \in E} f_{uv} - \underbrace{\sum_{(v,w) \in E} f_{vw}}_{= 0} = 0$$
is violated if you have incoming flow.


Prove that PP is closed under complement I found this proof in Wikipedia, but one of the most important steps in it  doesn't make any sense to me. I'll explain:

  By the definition of PP there is a polynomial-time probabilistic
  algorithm A with the property that ${x\in L\Rightarrow \mathrm {Pr}
 [A(x) =  1]>\frac{1}{2}} $ and ${x\not \in L\Rightarrow \mathrm {Pr} [A(x) = 1]\leq \frac{1}{2}}$.

  Let $f(|x|)$ be the
  polynomial upper bound on the running time of A on input x. Thus A
  makes at most $f(|x|)$ random coin flips during its execution. In
  particular, $ x\in L\Rightarrow {\mathrm  {Pr}}[A(x) = 1]\geq \frac{1}{2}+\frac{1}{2^{{f(|x|)}}}$.

I understand that:

By definition of PP, ${x\in L\Rightarrow \mathrm {Pr}
 [A(x) =  1]>\frac{1}{2}} $. It means that if indeed $x \in L$, more than half of the possible coin flip combinations would cause the algorithm to accept.
The algorithm's running time is bound by $f(|x|)$, then the probability of getting some specific combination of coin tosses (that accepts or rejects, we do not know) is bound by $(\frac{1}{2})^{f(|x|)} = \frac{1}{2^{{f(|x|)}}}$.

But why is it so obvious that $ x\in L\Rightarrow {\mathrm  {Pr}}[A(x) = 1]\geq \frac{1}{2}+\frac{1}{2^{{f(|x|)}}}$?

That one specific combination of coin flips could easily be one of the half that was already counted in the definition of PP, and in that case, it would not make any sense add together "half of the possible coin flip combinations and one specific combination". What am I missing here?

$\frac{1}{2^{f(|x|)}}$ is the granularity of the probabilities. The probability distribution is over the possible outcomes of the coin flips. If you flip two coins for example, the probability that you accept can't be exactly 0.501. It's either 0 (you never accept), 1/4 (one coin flip combination leads to acceptance), 1/2 (two combinations make you accept), 3/4 or 1.

So if you require the probability to be greater than 1/2 you know that it's at least $1/2 + \frac{1}{2^{f(|x|)}}$.


How can I solve $T(n) = 2T(\sqrt{n-1} + 2) + 1$ recurrence using tree method? The recurrence I have is

$T(n) = 2T(\sqrt{n-1} + 2) + 1$

I don't know how to solve it. I didn't find much on the internet with square roots in recurrences especially with constants inside of it. I'm supposed to find the height of the tree but I have no idea how.

I need to solve this recurrence only using trees. And I can't find anything about solving recurrences with trees and square roots as parameters.

You could try upper and lower bounding the work done in your recurrence tree by two other simpler recurrences.

For instance, this is the function/rate by which your recurrence input decreases at each level: $$f(n) = \sqrt{n-1} + 2$$

We can find a function the decreases faster, for example

$$f_1(n) = \sqrt{n} \leq \sqrt{n-1} + 2 = f(n) \quad \forall n \geq 4$$

We can also find a function that decreases slower, for example

$$f_2(n) = 2\sqrt{n} \geq \sqrt{n-1} + 2 = f(n) \quad \forall n \geq 4$$

Thus with $f_1(n) \leq f(n) \leq f_2(n)$ we can construct two other recurrences based on these new functions:

$$\begin{align*}
T_1(n) & = 2T_1(\sqrt{n}) + 1\\
T_2(n) & = 2T_2(2\sqrt{n}) + 1\\
\end{align*}$$

We can then bound our original recurrence by these:

$$T_1(n) \leq T(n) \leq T_2(n)$$

So if you can solve these recurrences, then you can bound $T(n)$ appropriately, because these will lower bound and upper bound the depth of the recursion tree respectively.

I wanted to work through this a bit further for my own satisfaction. Not quite a recursion tree analysis, but I think this function is interesting so I worked through it.

The first $T_1$ we can solve relatively easily with a domain transform:

$$\begin{align*}
T_1(n)       & = 2T_1(\sqrt{n}) + 1\\
T_1(2^{2^k}) & = 2T_1(2^{2^{k-1}}) + 1\\
S(k)         & = 2S(k-1) + 1\\
             & = \Theta(2^k)\\
T_1(n)         & = \Theta(2^{\log \log n})\\
             & = \Theta(\log n)
\end{align*}$$

The second $T_2$ is a little trickier, but not much. Let's unwrap this a bit:

$$\begin{align*}
T_2(n) &= 2T_2(2\sqrt{n}) + 1\\
       &= 2\left(2T_2(2\sqrt{2\sqrt{n}}) + 1\right) + 1\\
       &= 4T_2(2^{3/2} \cdot n^{1/4}) + 3\\
       &= 4\left(2T_2(2 \cdot (2^{3/2} \cdot n^{1/4})^{1/2}) + 1\right) + 3\\
       &= 8T_2(2^{7/4} \cdot n^{1/8}) + 7\\
       &= \vdots
\end{align*}$$
The pattern starts to emerge and we can perform another domain transform (obviously, to be formal you should prove that the pattern holds by induction, but I'm omitting that).

Let $n = 4^{2^k + 1}$ and when we apply $2 \sqrt{n}$ we get:

$$\begin{align*}
2 \sqrt{4^{2^k + 1}} & = 2 \sqrt{4} \sqrt{4^{2^k}}\\
                     & = 4 \cdot 4^{2^{k-1}}\\
                     & = 4^{2^{k-1} + 1}
\end{align*}$$

Now with this we do the domain transform:
$$\begin{align*}
T_2(n) & = 2 T_2(2 \sqrt{n}) + 1 \\
T_2(4^{2^k + 1}) & = 2 T_2( 2 \sqrt{4^{2^k + 1}}) + 1\\
S(k) & = 2 S(k-1) + 1\\
     & = \Theta(2^k)\\
T_2(n) & = \Theta(2^{\log_2(\log_4(n) - 1)})\\
       & = \Theta(\log n)
\end{align*}$$

With this we see:

$$\begin{align*}
T_1(n) &\leq T(n) \leq T_2(n) & \forall n \geq 4\\
c_1 \log n &\leq T(n) \leq c_2 \log n & \forall n \geq 4\\
\implies T(n) & = \Theta(\log n)
\end{align*}$$


Flow of control? or Control of flow? In most PL textbooks (even in language specifications) statments like if, while, for, break are categorized as flow of control statements.
However, it is not consistent; i.e. sometimes the same text uses control-flow statement (note the dash), or control flow statment, I read sentences that says control flows...

I understand those statements control the flow of execution, hence control of flow. But many texts (even wikipedia) says otherwise, implying control is something that flows in a program

What is the formal, language-agnostic definition of this concept in CS, if any?

I am not sure what you mean by "language-agnostic definition of this concept in CS"; such notions are rarely (if ever) rigorously defined. Someone uses them first, others pick them up and eventually they become standard vocabulary. That's ho we get conflicting notation all the time.

In this case, I don't see an either-or. Both makes sense, depending of how you look at it. The semantics of the language control the flow of execution, i.e. determine which statement is executed next. But as this control -- once it is implemented in a processor -- only looks at the current statement, it flows along, that is control flows.


Semi decidability proof I'm studying for my theory of computation exam and came accross the following question:

Construct an appropriate Turing machine for the following language and prove or disprove it's semi-decidability:

$A := \{w \in \{0, 1\}^*\  |\  \exists x \in \{0, 1\}^* .f_w(x) = |x| \}$

The way I interpret this is that $A$ consists of all TM encodings $w$ which describe a TM $M'$ that for at least one input $x\in\{0, 1\}^*$ outputs the length of $x$. So now I try to come up with a TM $M$ for $A$, this TM should simulate TM encodings $w\in\{0, 1\}^*$ and check whether the TM $M'$ it simulates computes $f(x) = |x|$ for at least one $x$. In order to do this, $M$ would have to try computing all possible inputs for $M'$ and check if $f(x) = |x|$ is true for at least one input, if such an input $x$ exists than $M$ will terminate and accept the encoding of $M'$ which is $w$. If such an input $x$ doesn't exist then $M$ will keep simulating $M'$ forever and therefore won't halt. Hence I conclude that $A$ is semi decidable since it halts if a solution exists and otherwise doesn't.

Does this make any sense?

Also, since I need to prove/disprove $A$'s semi-decidability, I conclude that $A$ is not decidable (Rice's theorem), is that correct?

What you have to do is systematic search for a string $x$ such that $f_w(x) = |x|$ or in other words $M_w(x) = |x|$. Given $w$ your TM $M$ should try ALL  input strings $x$, not just to simulate  $M_w$ on a single $x$.

If you wait $M_w(x)$ until it halts then you ($M$) may stuck in case $M_w$ does not halt on $x$. So, that option is not possible.

One possible way is to systematically try all pairs $(x,i)$ which means  "simulate $M_w(x)$ for $i$ steps". Your strings may be encoded an put in one to one correspondence with integers. So a pair $(i,j)$ means simulate $i$th string $s_i$ for $j$ steps on $M_w$. Each time you simulate $(i,j)$ you check if after $j$ steps $M_w(s_i)$ halts and if yes then compare its output with $|s_i|$. If the output is equal to $|s_i|$ then ACCEPT and halt, otherwise you go to the next pair $(i,j)$. Thus so on until you ($M$) find a pair $(i,j)$ such that $M_w(s_i)$ halts after $j$ steps and its output is equal to $|s_i|$.

In other words, you simply give a chance to your machine $M$ to run on every $x$ for a certain number of steps, and after running for the certain number of steps you check if it halts and if it halts you compare its output with the input length.

Now to prove that it is semi-decidable notice that if indeed there is $x$ such that $f_w(x) = |x|$ then there are integers $m$ and $n$ such that $s_m = x$ and $M_w(s_m)$ halts after $n$ steps. You will eventually find that pair $(m, n)$ after a finite number of steps since you systematically try all pairs $(i,j)$. If such pair does not exist at all then your machine never halts and will run forever. Thus that set is semi-decidable.    Similar post


How can I solve this constrained assignment problem? The assignment problem is defined as follows:

  There are a number of agents and a number of tasks. Any agent can be
  assigned to perform any task, incurring some cost that may vary
  depending on the agent-task assignment. It is required to perform all
  tasks by assigning exactly one task
  to each agent in such a way that the total cost of the assignment is
  minimized.

The number of tasks is larger than the number of agents.

My problem statement though imposes an additional constraint on the above.

  Each task belongs to exactly one 'category'. Each 'category' has an
  associated maximum number of tasks that can be assigned. Enforce this
  constraint on the earlier definition.

For a layman's example, consider this -

  A restaurant serves n customers (agents), and has on it's menu m
  possible dishes (tasks), with m > n. Each customer gives his
  preference for each of the m dishes, which is the cost for this
  particular assignment problem. Find a solution which minimizes cost
  i.e. which gives each customer a dish that is as high on their
  preference as possible.

  Additionally, each dish belong to a certain cuisine (category). The
  restaurant can only make a certain number of dishes per cuisine.
  Enforce this constraint on the problem above.

I understand that this is a very specific problem, but any help would be appreciated.

I am currently solving the first part of the problem using the Hungarian Algorithm for assignment.

This can be formulated as an instance of minimum-cost flow problem.  Have a graph with one vertex per agent, one vertex per task, and one vertex per category.  Now add edges:

Add an edge from the source to each agent, with capacity 1 and cost 0.
Add an edge from each agent to each task, with capacity 1 and cost according to the cost of that assignment.
Add an edge from each task to the category it is part of, with capacity 1 and cost 0.
Add an edge from each category to the sink, with capacity given by the maximum number of tasks assignable in that category and cost 0.

Now find the minimum-cost flow of size $t$, where $t$ is the number of tasks.  There are polynomial-time algorithms for that.


Reductions among Undecidable Problems Im sorry if this question has some trivial answer which I am missing. Whenever I study some problem which has been proven undecidable, I observe that the proof relies on a reduction to another problem which has been proven to be undecidable. I understand that it creates some kind of an order on the degree of difficulty of a problem. But my question is - has it been proven that all problems which are undecidable can be reduced to another problem which is undecidable. Is it not possible that there exists a undecidable problem which can proved to have no reduction to any other undecidable problem (Hence to prove the undecidability of such a problem, one cannot use reductions). If we use reductions to create an order on the degree of computability then this problem cannot be assigned such a degree.

As Hendrik Jan mentioned, there are in fact different degrees of undecidability. For example, the problem of deciding whether a Turing machine stops on all inputs is harder than the halting problem, in the following sense: even given an oracle to the halting problem, we can't decide whether a given Turing machine stops on all inputs.

One important technique used to show relations like these is diagonalization. Using diagonalization, given a problem $P$ we can always find a harder problem, namely the halting problem for Turing machines with an access to a $P$ oracle. The new problem $P'$ is harder in the following sense: a Turing machine with an oracle access to $P$ cannot solve $P'$. In that sense there is no "hardest" problem.


Find least connected sub-graphs For example the nodes in this graph should be separated into two groups (A,B,C) and (D,E,F,G).

By looking at a graph of citations, assuming that most citations are papers from the same field, can we separate papers into fields?

You could define what "least connected" means (precisely) in a variety of ways, where the precise definition chosen may affect the output of the algorithm (and there is no unique correct definition for this). But you may wish to look into Community Detection algorithms. The general intuition of Community Detection is to find a set of sub-graphs that maximises the ratio of edges within the sub-graphs versus edges between sub-graphs. Depending on the precise definition, this may be a difficult (NP-complete) problem, and so various algorithms rather use approximate (heuristic or greedy) approaches.

Five popular Community Detection algorithms are described here and should be a good starting point for your work.


Big Oh where $g(n)$ is $n^2-n$ I have to solve the following $n^2+n \in O(n^2−n)$.

I did it this way:
$n^2+n \in O(n^2−n) = n^2 \in O(n^2−n) = n^2 / n^2-n = 2n / 2n-n$ which is infinite.

I don't know if this is correct because the $-n$ in the $O$ notation is confusing me and I haven't found anything about it online. I know if this would be at example -1000 that $n^2+n \in O(n^2−n)$ would be correct.

Could someone explain it to me ?

$f \in O(g)$ means there's $n_0$ and $c>0$ such that $n>n_0$ implies $f(n) \leq cg(n)$.

Note that for $n>2$, we have $n^2 \geq 3n$.

Then, for $n>2$, we have:
$$
\begin{align}
2(n^2 - n) & = n^2 - 2n + n^2 \\
& \geq n^2 - 2n + 3n\\
& = n^2 + n\\
\end{align}
$$

Summarizing: for $n>2$, we have $n^2+n \leq 2(n^2-n)$. Thus $n^2+n \in O(n^2-n)$.


Finding stages in routing algorithm I have an undirected graph where I need to find routes of minimum cost in a point to multi-point, but where cost can be reduced by creating intermediate "packs" of routing terminals. I am currently unable to accurately and in reasonable time locate where I can pack my terminals.

In the whole problem, from a connected graph $G$, a node $s$ and a set of nodes $t$ we are looking for a collection of path that have the following properties:

All elements of $t$ must have a path to either $s$ or an intermediate point. These paths are weighted the sum of their arc distance.
If an element of $t$ have a path to an intermediate point, there must be between 3 and 5 paths from distinct nodes of $t$ to that point.
All intermediate points must have a path to the $s$. These paths are weighted the double of the sum of their arc distance.
We look for an algorithm approaching or computing exactly a minimum weight solution.

Note that because the weight is being proportional to distance, we will admit a minimum weight solution is easily found once the intermediate points, along with the set of $t$ nodes that have a path to it, are know.

For example in this graph I'd expect the algorithm to return me a pack $\{t1, t2, t3, t4, t5\}$ on node $p$ because it would be the minimum cost setup:

Total cost here being 7 for routing $t$ points + 6 for routing the intermediate point = 13, much less than if all $t$ were routed to the source (5*4 = 20) and a bit less than if they were packed at point 3 (5*2 + 2*2 = 14)

We need to find as close as possible to the optimal setup, but in our actual datasets, there is usually over 400 terminals, and we can't enumerate all possible partitions of 3 to 5 terminals to compute a routing. How can I efficiently find these intermediate stage routing points (where to "pack" my terminals) ? Is there any existing research or algorithms on the matter ?

I don't know whether there is an efficient (polynomial-time) algorithm for this problem.   I wouldn't be surprised if it is NP-hard.

One approach would be to formulate this as an instance of integer linear programming, and then apply an off-the-shelf ILP solver to find the best solution it can within some fixed amount of time.  This gets awfully ugly.  You could introduce a bunch of zero-or-one variables to represent the solution, write down constraints (inequalities) to capture that they are consistent, express the cost of a solution as a linear combination of these variables, and then use the ILP solver to minimize the cost.  However, writing down the set of inequalities might get super messy.

Alternatively, it might be possible to apply heuristics for weighted set cover or weighted exact cover to this problem.  Given any candidate combination of 3..5 terminals and a candidate location for the intermediate point, you can easily compute the cost of connecting them.  Consider this as a "set" that covers those terminals and that intermediate node, and whose cost is equal to the computed cost.  There are $n_1 \times ({n_2 \choose 3} + {n_2 \choose 4} + {n_2 \choose 5})$ many such "sets", where $n_1$ is the number of internal nodes and $n_2$ is the number of terminals.  This is $O(n^6)$, where $n$ is the number of nodes in the graph.  Now the goal is to find a cover, i.e., a subset of "sets" that covers each terminal exactly once and that covers each internal node at most once.

In principle you could then try applying any algorithm for exact cover.  However, I suspect this will be far too slow, as there will be a few hundred billion possible "sets" or so.

An alternative might be to apply a heuristic or approximation algorithm for set cover.  For instance, consider the greedy algorithm for set cover: at each step, it chooses a set that minimizes the cost of the set divided by the number of terminals that are newly covered by that set and haven't been covered yet (best "bang-for-the-buck").  This gives a solution that is not too much more expensive than the optimal solution.

Moreover, you can implement the greedy algorithm efficiently, without enumerating all sets.  At each step, we have already covered some of the terminals and some of the internal nodes, and we want to choose the next set with the best bang-for-the-buck ratio.  This seems feasible.  One naive way to do that is to iterate over all possible choices for the location of the intermediate point, and for the number $k$ of terminals (3..5), and then find the $k$ closest uncovered terminals to that intermediate point; each gives you a candidate set.  Also find the closest uncovered terminal to $s$; this gives you another candidate set (with no intermediate point).  Among these candidates, take the one with the lowest bang-for-the-buck ratio and add it to your solution so far.  If you precompute all-pairs shortest paths (e.g., with the Floyd-Warshall algorithm), then each step can be implemented in $O(n^2)$ time.  You need to do at most $n$ steps, so the total running time will be $O(n^3)$.

This might give a highly suboptimal solution, but it is at least one solution, and it should be relatively efficient with your parameter settings.

Alternatively, it might be possible to use local search or simulated annealing to optimize your solution.  The key requirement is to have a way, given a current solution, to find a way to perturb the solution in a random way.  The algorithm then tries this many times, hopefully gradually decreasing the cost of the solution over time.  In your situation, one way to random perturb a candidate solution is to either (1) randomly pick three terminals that currently aren't part of any pack and merge them into a pack, (2) randomly pick a terminal that currently isn't part of any pack and a pack of size 3..4, and merge them into a single pack, or (3) randomly split a pack of size 4..5 into a pack of size 3..4 and a terminal that isn't part of any pack.  You could then try simulated annealing together with such a choice of perturbation (neighborhood relation).  There might be smarter ways to choose the perturbation that makes those algorithms more effective.

Maybe someone else will be able to come up with a better approach.


Is switching quantifiers allowed in this instance? In Logic In Computer Science (2nd Edition - Michael Huth and Mark Ryan), exercise 2.4.12.k is the following:

  For each of the formulas of predicate logic below, either find a model which
  does not satisfy it, or prove it is valid.

This one is difficult:

  (∀x ∃y (P(x) → Q(y))) → (∃y ∀x (P(x) → Q(y)))

Not only am I not sure how to prove this, I'm not sure whether it is valid or not. I came across this question when revising for an exam and always hit a dead end with it.

Any suggestions or insight is appreciated.

The key issue here is whether switching quantifiers is okay. Turn the top-level implication around and see what happens then.

As for this formula, think about what the left- resp. the right-hand side say.

Left: "Every $x$ has a $y$ so that... holds."
Right: "There is a $y$ so that ... holds for all $x$."

In particular, the left-hand side allows different $y$ -- one for each $x$ -- while the right-hand side requires a single $y$.

With this off the table, try to figure out whether

$\qquad \left(\forall x. \exists y. P(x,y)\right) \to \left(\exists y. \forall x. P(x,y)\right)$

holds for all predicates $P$. If so, your original questions is answered, and if not it should be easy to modify a counter-example to have the necessary form of an implication.

   For the simplified formula, there is a simple counter-example: every natural number has a successor, but there is no natural number that is successor to all natural numbers.

Try to utilise this before lifting the next spoiler!

   No luck? Well, that is to be expected. The "simplified" formula was a trap as it is not really a simplified formula, as you have hopefully figured out. It allows you to set $x$ and $y$ in relation which your formula does not: the (inner) implications can be read as disjunction, i.e. $\lnot P(x) \lor Q(y)$, so $P$ and $Q$ can fulfill the disjunction independently of another.

Can you prove that the formula holds now?

   If the left-hand side is fulfilled -- if it is not, the whole formula is trivially fulfilled -- all $x$ fulfill $\lnot P(x)$ or there is (at least) one $y$ that fulfills $Q(y)$ (to rescue the failing $x$). In either case (they can overlap!) the right hand side is fulfilled. In particular, if $\lnot P(x)$ is true for all $x$, $y$ can be chosen arbitrarily (on the right-hand side), else choose one of the rescuers. Be aware that the empty element domain -- if allowed -- is a special case.


Relation between hardware and software I'm very interested in computing and programming. I have done a lot of programming with different languages although I have a question nobody was able to answer until now.

I question myself how is software related to hardware. to be more specific what are the basic mechanisme which make it possible for hardware to understand software code?

for example : when you put on the computer it starts at a certain point in the register and feeds it into the apu. afther that I'm stuck ....

edited the question

This is quite a difficult question to answer. I would comment if I could.
The first problem is that you have not defined what you mean by a computer? Are you talking about the electrical based computers we know today or are you also including mechanical computers in your question? Here's a wiki link about the Difference Engine. The difference engine is completely mechanical but you can still technically 'program' it although it does not directly follow the paradigms of today.

Most parts of your question relate to one specific problem: How does the processing unit of a computational device work in a general way in accordance to the modern idea of software? I will give a general overview of what processor do.

A computer has three general operations: input (The input the user puts in, which includes data and what operation is wanted to be done), processing (the processor taking the input and operating on it) and output (what information is returned to the user). So what is inputted into a computer at the lowest level is some data and what is called an op-code or instruction. This is instruction is part of a collection stored in the processor (either electronically or via some other physical means) which has a defined algorithm associated with it. These instructions are considered 'basic' or low level. When something much more complicated is required to be processed, it is broken down into small parts which use these instructions to produce the desired computation in the end. Mechanical processors, specifically gearing based systems work in a similar way but accept input differently. The gears shift according to an algorithm to produce a result from a specific sequence of gear shifts initially (which is the input).

Here's a link to a Intel Lesson Series on Microprocessors

Another explanation of the CPU

From what I can gather the software you are talking about are the programs you see running on a computer. These are considered to be high level software, which are very complex when looking at this software from the perspective of a processor. Essentially the tools used to make this software and the software itself is broken down into a set of instructions for the processor to process at some point in the execution chain. With modern software there are many layers of abstraction to get from the processor to what the user sees. See this Wikipedia article about abstraction (It's the most comprehensive I could find): https://en.wikipedia.org/wiki/Abstraction_(computer_science)

Modern compilers such as gcc take human readable code and turn that into executable code which the operating system then executes. During execution the operating system will call processor instructions (which is a few abstraction levels down) in accordance to the executable code which the compiler produced.


Cache and Main Memory As we know that average access time is given by

t=p*(tc)+(1-p)*(tc+tm)

where t represent the average time, p is the hit ratio , tc is the time to access the data from the cache and tm is time to retrieve data from main memory.
I was wondering wouldn't it be possible to decrease this time to

t=p*(tc)+(1-p)*(tm)

if we search for the data in both the cache and the main memory in parallel?

It would be possible for that access, but nevertheless, it is not a good idea.

Even with relatively small caches, the cache miss rate of most programs is well under 10%. If a designer did what you proposed, what would likely happen is

access 1 is looked up in the cache while a memory access is started;
the cache reports the lookup is a success;
the next instruction that wants to access memory now cannot proceed. It could look up the cache, but (with your scheme) it would need to look up memory at the same time, and the memory subsystem is still working on access 1. (In fact, in has just started working on it.)

The point is that the memory subsystem cannot possibly support as anywhere near
as many lookups per second as the CPU can issue. One of the points of the cache is reduce the load on it to level it can support.


Notation within gaussian function On our lecture slides we have two different notations of the gaussian function.
First it gets introduced as follows:
$$p(x_n|\theta) = \frac{1}{\sqrt{2\pi}\sigma}exp\{-\frac{(x_n-\mu)^2}{2\sigma^2}\} \text{ with } \theta=(\mu,\sigma)$$
But later it is used like this:
$$\frac{1}{\sqrt{2\pi}\sigma}exp\{-\frac{||x_n-\mu||^2}{2\sigma^2}\}$$
What is the difference between $$(x_n-\mu)^2$$ and $$||x_n-\mu||^2$$ or are they equal?

The notation $\|x_n - \mu\|^2$ stands for the squared $L_2$ norm of the vector $x_n - \mu$.
The squared $L_2$ norm of the $d$-dimensional vector $v = \begin{pmatrix} v_1 & \cdots & v_d \end{pmatrix}$ is $$\|v\|^2 = v_1^2 + \cdots + v_d^2. $$
In particular, when $d = 1$, we have $\|v\|^2 = v_1^2$.
The formula you state works for the Gaussian multivariate distribution, when the various variables are independent and have the same variance $\sigma^2$. The formula in the general case is a bit more complicated.


How can I prove that the language of a read-only Turing machines is regular? I find this,
but I can't complete it, is there any other solution for it?

According to wikipedia, a read-only Turing (rTM) machine is a two-way finite automaton (2FSA). Two-way finite automata accept regular languages, and we are done.

Unfortunately, it is not that simple.

A Turing machine is allowed to wander into the area of the tape that consists of blank cells. This a 2FSA cannot do, usually it has end-of-tape markers. (Turing machines in general do not have these markers, otherwise they would be equivalent to linear-bounded automata.) Now a simulation of a rTM machine by a 2FSA is straightforward for the written part of the tape. For the blank parts we need transitions to code that the machine leaves to the right in state $q$, making a computation on blanks, returning in the rightmost cell in state $q'$. These are fixed by the machine, and do not depend on the actual input. Similarly for the left part (is the tape is two-sided infinite). Then there are accepting transitions that recognize that the rTM walks off the tape, does not return, but halts (and accepts). Non-halting non-returning excursions in the blank part can be ignored, they do not add to the accepted language.


What does "deterministic" mean in the context of memory management? At the time of writing, Wikipedia describes determinism as:

"a deterministic algorithm is an algorithm which, given a particular input, will always produce the same output, with the underlying machine always passing through the same sequence of states"

That aligns with my interpretation of determinism as a natural scientist.

If a program contains a benign race condition and its control flow varies depending upon the outcome of the race, is it deterministic? I would say not. However, many people describe thread-safe reference counting, such as shared_ptr in C++, as deterministic even though threads race to decrement the reference count to zero and the winner is responsible for executing the destructor.

The Wikipedia page about garbage collection lists determinism as an advantage of reference counting compared to tracing collection and determinism is also referred to here. On the other hand, people have blogged rants explaining why this is wrong.

So what does "reference counting is deterministic" mean, if anything?

So what does "reference counting is deterministic" mean, if anything?

It means it is deterministic in the absence of multiple threads. Threads almost always ruin this sort of determinism, with or without a race condition, memory collection or whatnot: in one run, thread A, can be scheduled first a bit, then another thread, B gets scheduled a bit; in a second run, the OS can schedule the threads to run in the opposite order, thus almost all threaded programs  inherently lose this determinism.

Therefore "race condition" and "threads" usually put a procedure out of the scope of this use of this meaning of determinism.


Probability of k-clique in a random graph I need to find the order of the minimum k = k(n) such that the probability of having at least 1 k-clique in a random graph $G(n, \frac{1}{2}$) is $\mathcal{O}(\frac{1}{n})$.
$X_k$ is the random variable which count the number of k-cliques in a random graph.
I already know $E[X_k] = \binom{n}{k}(\frac{1}{2})^{\binom{k}{2}}$.
I don't know exactly how to find the exact value of k.
I know $P[X_k \geq 1] \leq E[X_k]$ for Markov inequality but I'm not sure that this is helpful.
Thanks in advance

The value is $2\log_2 n - 2\log_2\log_2 n + O(1)$.

Let $k_0$ be the maximal value such that the expected number of cliques of size $k_0$ is at least 1. A boring calculation shows that $k_0 = 2\log_2 n - 2\log_2\log_2 n + O(1)$. It is a classical result that with high probability, $G(n,1/2)$ contains a $(k_0-1)$-clique. This implies that $k > k_0-1$. On the other hand, it is known that the expected number of cliques of size $k_0+1+C$ is $O((\log n/n)^C)$ for any constant $C$ (this is because the expected number of cliques drops by $\Theta(\log n/n)$ near $k_0$). This shows that $k \leq k_0+3$. We conclude that $k_0 \leq k \leq k_0+3$.

You can probably decrease the length of this interval by 1, following the proof of the classical result which shows concentration of the clique number of two values rather than three.


How was Idris' `rewrite` implemented? I know in Agda, rewrite is a syntax sugar that desugars to a with abstraction.
For example, if we have (I'm using the Data.Vec from the standard library):

$$
\DeclareMathOperator{Set}{Set}
\DeclareMathOperator{xs}{xs}
\DeclareMathOperator{where}{where}
\DeclareMathOperator{proof}{proof}
\DeclareMathOperator{data}{data}
\DeclareMathOperator{rev}{rev}
\DeclareMathOperator{ff}{ff}
\DeclareMathOperator{lemma}{lemma}
\DeclareMathOperator{intro}{intro}
\DeclareMathOperator{id}{id}
\DeclareMathOperator{refl}{refl}
\DeclareMathOperator{params}{params}
\DeclareMathOperator{Vec}{Vec}
\DeclareMathOperator{rewrite}{rewrite}
\DeclareMathOperator{with}{with}
\DeclareMathOperator{revrevid}{revrevid}
\begin{align*}
& \revrevid : \forall \{n \ m\} \{A : \Set n\}
    (a : A) (v : \Vec A \ m) \rightarrow
    \rev (v \ {:}{:} ^r a) \equiv a \ {:}{:}\rev v \\
& \revrevid \ \_ \ [] = \refl \\
& \revrevid \ a \ (\_ \ {:}{:} \ \xs) \ \rewrite \revrevid \ a \ \xs  = \refl
\end{align*}
$$

This will be desugared to:

$$
\begin{align*}
& \revrevid : \forall \{n \ m\} \{A : \Set n\}
    (a : A) (v : \Vec A \ m) \rightarrow
    \rev (v \ {:}{:} ^r a) \equiv a \ {:}{:}\rev v \\
& \revrevid \ \_ \ [] = \refl \\
& \revrevid \ a \ (\_ \ {:}{:} \ \xs) \with \ \rev (\xs \ {:}{:}^r \ a) \ | \ \revrevid \ a \ \xs \\
& ...  \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ \ | \ {.}(a \ {:}{:} \rev \xs) \ | \refl = \refl
\end{align*}
$$

But in Idris, there's nothing like a with abstraction, or a dot pattern (which are available in Agda).
So how does Idris' rewrite implemented? Is that just a syntax sugar or a language feature which cannot be implemented in pure Idris code?

I talked to be5invis and he said it's implemented using replace.

replace is something like this in Agda: $$ replace : \forall \{a \ b\} \rightarrow (a \equiv b) \rightarrow P \ a \rightarrow P \ b $$
or, using universal polymorphism: $$ replace : \forall \{n\} \{a \ b : Set \ n\} \rightarrow (a \equiv b) \rightarrow P \ a \rightarrow P \ b $$

This is obvious, in both Agda and Idris.

And we use it like this:

$$
\begin{align*}
& proof : \ (a \equiv b) \rightarrow P \ a \rightarrow P \ b \\
& proof \ theory \ pa = replace \ theory \ pa
\end{align*}
$$

While rewrite in is just a mixfix version of replace, so, the code above can be written like this:

$$
\begin{align*}
& proof : \ (a \equiv b) \rightarrow P \ a \rightarrow P \ b \\
& proof \ theory \ pa = rewrite \ theory \ in \ pa
\end{align*}
$$

In conclusion, rewrite is syntax sugar which desugars to replace, while replace is a library function that can be implemented by anyone.
So there's nothing special.

Actually, Idris desugars it to a function like this:

rewrite__impl : (P : a -> Type) -> x = y -> P y -> P x
rewrite__impl P Refl prf = prf


Is it possible for a hash table's load factor to exceed 100%? Using probing, is it possible for for a hash table's load factor to exceed 100%? I don't too much about Hash Tables. Is this possible?

The load factor of a hash table is defined as:

$$\lambda = \frac{n}{k}$$

where $n$ is the number of items stored in the table and $k$ is the number of buckets. So the load factor is greater than 1 if there are more entries than buckets.

Storing more than one entry in a bucket is very common. The most familiar example is separate chaining (e.g. a linked list of entries in the bucket), used for in-memory hash tables.

For disk-based hash tables (as found in database servers or some file systems or file management systems), a "bucket" is typically a page (possibly a disk page or a virtual memory page) in size, so for typical use cases, you can easily fit more than one item into it. A scheme such as extendible hashing is typically used to manage buckets in a way that minimises disk traffic.


How does TCP manage to discard segment received from a source other than the one with which the connection has been established? It is known that TCP is a connection oriented transport layer protocol of the TCP/IP suite. But TCP (and UDP) operate over a connection less network layer protocol, the IP (internet protocol). What this means is that in TCP, if a sender sends data to the receiver, at the network layer, the receiver will accept the packet, without bothering about the source IP address of the packet. The receiver network layer then strips-off the IP-header from the received packet (and the IP address information of the source and the destination get stripped along with it), and passes off the remaining segment to the transport layer.

Now the doubt arises is, since the IP address information has been stripped away from the packet before forwarding it to the transport layer, how does the TCP sitting at the transport layer manage to decide from which IP address the information has come, when the only address details the transport header contains is the source and destination port numbers of the processes running on the respective hosts?

"Stripped away" is not strictly correct. A TCP packet is an IP header followed by the TCP-specific data. The IP-level information is needed, and used. In particular, the source IP address is needed (as you say) to decide which currently open TCP conversation should receive the packet that has just arrived.