Turing recognizable language between languages that aren't recognizable?

The answer is no, of course.

Consider, for instance, the following languages:

$L_1 = \{ \langle M \rangle \# \langle M \rangle \mid \, \text{$M$ is a TM which does not halt on input $\langle M \rangle$} \}$
$L = \{ \langle M \rangle \# \langle M \rangle \mid \, \text{$M$ is a TM} \}$
$L_2 = L \cup \{ \langle M \rangle \# w \mid \, \text{$M$ is a TM which does not halt on input $w$} \}$

Then it is easy to see neither $L_1$ nor $L_2$ are recursively enumerable (i.e., Turing-recognizable), despite $L$ being even context-sensitive. (In fact, you could even make $L$ context-free by replacing the second $\langle M \rangle$ with its reversed copy.)

The upshot is that set inclusion (on its own) tells us very little about the sets involved being recursively enumerable or not, unless the symmetric difference between them is finite. In the case of $L_1 \subseteq L \subseteq L_2$, we do know, for instance, that $|L \setminus L_1|$ or $|L_2 \setminus L|$ being finite implies that $L_2$ is also not recursively enumerable.


What is the significance of reverse polish notation?

I've used RPN several times for rapid prototyping, e.g. of programs that have to read and interpret a user-supplied mathematical expression.

Whereas regular mathematical notation would require at least a recursive parser (think brackets, operator order, etc...), an RPN parser is basically a stack with a switch-like statement. I guess it's this combination of simplicity and expressive power that led HP to use it initially.

This is, however, usually for rapid prototyping and for convenience. I would never assume that a user can, or wants to, understand RPN.


Some questions regarding methods for solving pushdown automata problems

Your first solution is fine. I would not call this cramming into one state, it is kind of elegant to handle all this at the same place.
For your second problem, yes you can add 55 extra states. But also here you can use a single state instead, by coding that state into the topmost stack symbol. Simply have many stack symbols $A_0$, $A_1$ to $A_{55}$ (or so) and replace $A_i$ by $A_{i+1}$ until 56 is reached.
In general every pushdown automaton can be replaced by one having at most two states.


Decidability of the language of all TMs whose languages reduce to a fixed decidable language

Let $L_1$ be a decidable language. Consider the class of Turing-recognizable languages

$$\mathcal{S} = \{ L \mid L \mbox{ reduces to } L_1 \}$$

This class is non-trivial in the sense of Rice's theorem, as no recognizable but undecidable language can be an element of $\mathcal{S}$, and since we obviously have that $L_1 \in \mathcal{S}$.

You can now apply Rice's theorem to get that $L_p$ is undecidable.


Does any one know what this problem is called?

This is an example of a constraint satisfaction problem. The variables of the problem are the "colors" of the elements of $A$, where $B$ is the set of colors. For each set $T \in S$ and each $(k+1)$-subset $T'$ of $T$, there is a constraint stating that the elements of $T'$ cannot all have the same color.

If $k=1$ and all $T \in S$ have cardinality $2$, then this is just graph coloring. You can similarly put graph hypercoloring in this framework.


Buses usually connect the central processing unit (CPU) with peripheral devices, like memory or other Input/Output devices.

To activate a memory you need to do two things:
- specify the cell in the memory you want to write to / read from  (that would be the address)
- give the data to write to the memory, or take the data from the memory (this information would go over the data bus)
- control the memory: tell the memory if this is a read or a write, etc.

So as you can see, in both READ and WRITE you must specify the address you want to write to, or to read from. So the address bus is uni-directional: from the CPU to the MEMORY.

The information itself goes in both directions. In a READ it goes from the memory to the CPU, and in a WRITE it goes from the CPU to the memory. Hence, the data bus is bi-directional.

The control bus is usually uni-directional: the CPU is the master and the peripherals are slaves. "Controlling" in the other direction goes via the interrupts mechanism.

Finally, as you mention, buses are just connected wires. 16bit means that there are 16 wires connected in parallel. So an address bus of 16bits can specify any address between 0 (=16 times 0) to $2^{16}-1=65535$ (=16 times 1). The data bus is capable of carrying 16bit of information, etc.


Distribution of $(X_1,X_2)$ if $X_1\pm X_2$ are two independent $N(1,4)$

Let $Y = (Y_1,Y_2)$ be two i.i.d. $N(1,4)$ variables. Then $Y$ is a multivariate normal distribution, and so any affine transformation of $Y$ is a multivariate normal distribution. In particular, if we define $X_1 = \frac{Y_1 + Y_2}{2}$ and $X_2 = \frac{Y_1 - Y_2}{2}$ then $X = (X_1,X_2)$ is a multivariate normal distribution which satisfies $X_1 + X_2 = Y_1$ and $X_1 - X_2 = Y_2$. In other words, it is the random variable you're interested in.
It is routine to calculate
$$
(X_1,X_2) \sim N\left(\begin{pmatrix} 1 & 0 \end{pmatrix}, \begin{pmatrix} 2 & 0 \\ 0 & 2 \end{pmatrix}\right),
$$
that is, $X_1 \sim N(1,2)$ and $X_2 \sim N(0,2)$, and $X_1,X_2$ are independent.


Why is the complexity of BFS & DFS frequently written as O(V+E) vs. O(max(V,E))

While they are equivalent from a big-$O$ perspective, I think that the former is preferable as it directly connects with how the algorithms are implemented. To see this, let's consider fully connected graphs vs. graphs with multiple components, including vertices which are completely disconnected.

In order to cover the former, $O(E)$ is completely sufficient. $O(V)$ is not, as every edge must be traversed. For the latter case, one must also consider all the disconnected vertices, so one has an additional complexity of $O(V)$. Thus, together we have $O(V+E)$.

From an informative standpoint it's clearer that we need to process all edges and vertices. By taking $\max$ it would seem to imply that it's sufficient to look at just edges or vertices. This is often why when we have algorithms dealing with multiple parameters they're all explicitly spelled out - $O(m+n)$ vs $O(m + log n)$ for example, even if $m > n$, because this matters; how does the algorithm behave if I change one of the parameters and leave the other untouched.


Is there a name for this tree traversal?

For a binary tree that is triple order; each node is visited three times in pre- in- and post-order.  Knuth cites it from a paper by Lindstrom and Dwyer; it can be done without a stack by updating the tree in place.


Producing an algebric equation from a graph

We can start from $\sin(x)$ which has a nice regular graph. To avoid negative values you can simply use the absolute value $|\sin(x)|$. This produces a graph similar to your but with constant height.

To decrease height as $x \to \infty$ we want to multiply that function by something that decrements. For example $\frac{1}{1+|x|}$ goes to $0$ as $x \to \infty$ and is symmetric. So $\frac{1}{1+|x|}|\sin(x)|$ is something similar to what you want with a maximum height of $1$.

If you multiply by a constant $A$ you "set" the maximum height to $A$. If you want to change the width of the bumps you can simply multiply the argument of the $\sin$ function, for example $\frac{A}{1+|x|}|\sin(2x)|$ will have maximum height $A$ and a width that is half the width of the normal $\sin$, while using $\sin(x/2)$ would produce a bump that is twice the width of the normal $\sin$.

See this wolfram alpha's graph for an example result.

You can also change the degradation of height by setting a different power for the $|x|$. For example using $\frac{1}{1+x^2}$ you'd have a faster drop to $0$, while using $\frac{1}{1+\sqrt{|x|}}$ would produce a slower change in height.


Is huffman-encoding with distinct frequencies of symbols unique?

2 3 4 5 is a counterexample:

4 5 5 (combine 2 and 3 to make 5, and reorder)

Now there are 2 choices for 4 to partner with: either the original 5, or the one formed by 2+3.


Does there always exist equivalent (M)(I)LPs with and without objective functions?

Yes (assuming you truly did mean "if" rather than "if and only if").

Add any objective function you want (e.g., 1, or the sum of the variables, or anything), then feed it to a MILP solver and see whether it returns 'Feasible' or 'Infeasible'.  Then the resulting MILP is feasible if and only if the original MILP was feasible.  Any optimal solution to the resulting MILP is feasible and thus also a feasible solution to the original MILP problem, and consequently represents a valid pure Nash equilibrium.


Route planning for a car driver picking up people using public transport

A generalized version of this problem is likely $NP$-complete, however given that very few people are sharing the same car, you can probably get away with an exact, exponential time algorithm.

Assuming your road network is given as a graph, for every node you will want to store:

The earliest time each person using public transport can get to that node
For every subset of people sharing the car, what is the earliest time the car can get to that point with that subset of people in it

Basically, if you have $n$ persons and one car, you would get a graph with $2^n+n$ "layers" (one layer for each subset and one layer for each person using public transport).

You can use a Dijkstra-like algorithm to compute these values. You do a multi-start search, starting from the homes of all the people involved. Whenever the car gets to a new node you check whether any people are ready to join the car, if so, you branch (the car continues without picking them up, but also moves to any layers in the graph that can be reached by picking people up). Whenever a person gets to a new node, you check whether the car has already reached that node (and also branch).

Note it is not really branching, but rather pushing more nodes on to the priority queue.


Algorithm to find number of covering sets

Is using the Inclusion-Exclusion-Principle (also called Sieve-formula) too inefficient?
According to the principle, if the union of any $L+1$ sets out of $S_{1}, S_{2}, \ldots S_{M}$ is bigger than $W$ then the number you are looking for is
$$
\sum_{n=1}^{L}{(-1)^n \sum_{i_{1},\ldots,i_{n}} \binom{N - |S_{i_{1}} \cup \ldots \cup S_{i_{n}}|}{W -  |S_{i_{1}} \cup \ldots \cup S_{i_{n}}|}}
$$
Edit: The complexity is around $M^{\frac{W}{|S_{i}|}}$ if the $S_{i}$s are close to being disjoint and around $2^M$ if the $S_{i}$s are close to being equal, so probably to big indeed.


Your process is a textbook example of a branching process. Starting with one $E$, we have an expected $3/2$ many $F$s, $9/4$ many $T$s, and so $9/8$ many remaining $E$s in expectation. Since $9/8 > 1$, it is not surprising that your process often failed to terminate.

To gain more information, we need to know the exact distribution of the number of $E$-offsprings, which is given by the following generating function (see the Wikipedia article linked to above):
$$
h(z) = \frac{33}{128} + \frac{7}{16}z+ \frac{15}{64}z^2 + \frac{1}{16}z^3 + \frac{1}{128}z^4.
$$
This implies that the extinction probability is $d \approx 0.717778143742483$ (by solving $h(z) = z$). This is an upper bound on the probability that your procedure terminates.

We can easily recover your numbers by considering iterates of $h$. The probability that the process terminates in $3k$ steps is $h^{(k)}(0)$. So computing $h(0),h(h(0))-h(0),h(h(h(0)))-h(h(0))$ and so on, we recover the figures in your table.

When $k$ is large, $h^{(k)}(0) \approx d$. We can compute $h'(d) \approx 0.882115879977412$. We have
$$
\frac{d - h^{(k)}(0)}{d - h^{(k-1)}(0)} =
\frac{h(d) - h(h^{(k-1)}(0))}{d - h^{(k-1)}(0)} \approx h'(d).
$$
It follows that
$$
d - h^{(k)}(0) \propto h'(d)^k.
$$
Therefore the probability that the process terminates in exactly $3k$ steps is
$$
h^{(k)}(0) - h^{(k-1)}(0) =
[d - h^{(k-1)}(0)] - [d - h^{(k)}(0)] \propto h'(d)^{k-1} - h'(d)^k \propto h'(d)^k.
$$
Empirically, we can check that the constant of proportionality is roughly $0.0248011196615094$.


A tree edge $uv$ with $u$ as $v$’s parent is a cut edge if and only if there are no edges in $v$’s subtree that goes to $u$ or higher

We must prove two directions: (i) if $uv$ is a cut edge, then there is no edge from $v$'s subtree to $u$ or higher and (ii) if there is no edge from $v$'s subtree to $u$ or higher, then $uv$ is a cut edge.

For (i), if there was an edge from $v$'s subtree to $u$ or higher, then the removal of $uv$ would not increase the number of connected components contradicting the fact that $uv$ is a cut edge. To prove (ii), since every path from any vertex in a subtree of $v$ to a vertex that is $u$ (or higher than $u$) must use the edge $uv$, we see that $uv$ is indeed a cut edge.


The Partition Problem: Reducing to prove NP-Completeness

Partition is equivalent to a special case of the subset-sum problem: $S$ can be partitioned into two sets $A$ and $B$ such that $\sum_{x \in A} x = \sum_{x \in B} x$ if and only if $\exists S' \subseteq S$ such that $\sum_{x\in S'} x = \frac{1}{2}\sum_{x \in S}x$.

Proof of $\implies$: Given $A$ and $B$ that partition $S$ and are such that $\sum_{x \in A} x = \sum_{x \in B}$ you must have $\sum_{x \in S}x =\sum_{x \in A} x + \sum_{x \in B} x = 2 \sum_{x \in A} x \implies \sum_{x \in A} x = \frac{1}{2}\sum_{x \in S}x$. The claim follows by picking $S' = A$.

Proof of $\Longleftarrow$: Given $S' \subseteq S$  such that $\sum_{x\in S'} = \frac{1}{2}\sum_{x \in S}x$ you must have $\sum_{x\in S \setminus S'} x = \sum_{x \in S}x - \sum_{x \in S'}x = \frac{1}{2}\sum_{x \in S}x$. The claim follows by picking $A=S'$ and $B = S \setminus S'$.

To show that this special case of subset sum (i.e. partition) is in $\mathsf{NP}$ notice that a subset $S' \subset S$ such that $\sum_{x \in S'} x = \frac{1}{2}\sum_{x \in S}$ is a yes-certificate.

To see that this special case of subset sum is still $\mathsf{NP}$-hard consider an instance $\langle S, T \rangle$ of subset sum where $S$ is a (multi-)set and $T$ is the target value. Let $M = \sum_{x \in S} x$.

Create a new instance subset sum $\langle \overline{S}, \overline{T} \rangle$ where $\overline{S} = S \cup \{ M-2T \}$ and $\overline{T}=M-T$.

If there is a solution $S' \subseteq \overline{S}$ to $\langle \overline{S}, \overline{T} \rangle$ then $\sum_{x \in S'} x = \sum_{x \in \overline{S} \setminus S'} x= M-T$ (since the sum of the elements in $\overline{S}$ is $2(M-T)$). At least one of $S'$ and $\overline{S} \setminus S'$ contains element $M-2T$, call this set $S^*$. Then the $S^* \setminus \{M-2T\}$ is a subset of $S$ and the sum of its elements is $(M-T)-(M-2T)=T$, showing that the original instance $\langle S, T \rangle$ is a yes instance.

On the other hand, if there is a solution $S' \subseteq S$ to $\langle S, T \rangle$, then the set $S' \cup \{ M-2T \}$ is a subset of $\overline{S}$ and the sum of it's elements is $T + (M - 2T) = M-T = \overline{T}$, showing that $\langle \overline{S}, \overline{T} \rangle$ is a yes instance. This concludes the proof.


Is there any uncountable Turing decidable language?

Every language over a finite (or even countable) alphabet is countable. Assuming your Turing machine alphabet is finite, any language it can possibly accept is countable.


Determining the optimal threshold value for a one-dimensional decision stump classifier

There is a straightforward algorithm that runs in $O(N)$ time, by scanning from left-to-right and right-to-left.  Basically, it takes advantage of a simple recurrence relation for $B(\cdot)$ and $C(\cdot)$.

Let $t_0,t_1,\dots,t_N$ denote a sequence of $N+1$ candidates for the threshold (i.e., $t_i \in [x_i,x_{i+1})$, etc.), as you articulated in the question.  Our job is to find the value of $i$ that maximizes $B(t_i)+C(t_i)$.

I claim we can compute the $N+1$ values $B(t_0),B(t_1),\dots,B(t_N)$ in $O(N)$ time, using a left-to-right scan.  This is because, given $B(t_{i-1})$, it is easy to compute $B(t_i)$.  In particular, notice that $B(t_i)$ can be written as the summation

$$B(t_i) = \sum_{j=1}^i 1[y_j=0].$$

In other words $B(t_i)$ is the count of how many of the first $y$'s are equal to zero.  Thus we get the recurrence relation

$$B(t_i) = B(t_{i-1}) + 1[y_i=0]$$

with the base case $B(t_0)=0$.  This allows us to compute all of the $B(t_i)$'s in $O(N)$ time.

We can similarly compute the $N+1$ values $C(t_0),C(t_1),\dots,C(t_N)$ in $O(N)$ time, by scanning from right-to-left.  Here we take advantage of a recurrence relation that computes $C(t_i)$ given $C(t_{i+1})$.  The details are similar to that for $B(\cdot)$.

The result is that we can compute the sequence of $N+1$ values $B(t_0)+C(t_0),B(t_1)+C(t_1),\dots,B(t_N)+C(t_N)$ in $O(N)$ time.  Then it is easy to find the largest value in that list.  The running time in total is $O(N)$ time.

I don't think you can do any better than $\Theta(N)$ worst-case running time, since you may need to examine every item (in the worst case).  Therefore,the method I have outlined above appears to be asymptotically optimal (up to constant factors).


Help Finding Loop Invariant From For Loop

See this question on Stack Overflow. You should provide reference for an algorithm when you did not write it, at least explain how you came up with it if you "created" it.

Terminology: this question is about finding the majority element of an array.

The invariant at step $i$ is:

A occurs at least in val cells of v[0..i]
The remaining (i + 1 - val) cells can be discarded without changing the majority element.

The algorithm is easy to accept as correct when you understand that if you remove two different elements of the array, then it keeps its majority element.


Update labels of a tree depending on ancestors of nodes in linear time

how we can preserve the information across multiple calls.

Excactly; we use a standard trick of functional programming and add additional parameters to the recursion.

Idea: Store (a copy of the) call stack in an array. Then, all ancestors of the current node are accessible in $O(1)$ time. You can do BFS or DFS.

Details: The main procedure starts at the root and creates an empty array of sufficient size:

relabel(T : Tree) {
  relabelH(T, 0, new Tree[T.size])
}

The second parameter stands for the current index in the array (i.e. recursion depth) which we use to determine the index of the $k$th ancestor. The actual work is done here:

relabelH(T : Tree, level : Int, ancestors : Tree[]) {
  ancestors[level] = T
  T.label = ancestors[max(0, level - T.label)].label

  for c in T.children {
    relabelH(c, level + 1, ancestors)
  }
}

Correctness: You can show by induction that ancestors[0..level-1] always contains the current node's ancestors in order from root to parent. Hence, the label update is correct. All nodes are reached (we do DFS) so the procedure is correct.

Running time: Every line in relabelH is executed once per visited node. Every individual line runs in constant time, assuming a reasonable implementation of Tree. The main call relabel(T) takes linear time (array initialization) plus the cost of the call to relabelH. In total, we get a running time in $\Theta(n)$ with $n$ the number of nodes (T.size).


Intuition of lower bound for finding the minimum of $n$ (distinct) elements is $n-1$ as dealt with in CLRS

Every match has exactly one winner and one loser. If every element except the winner must lose at least one match, there must be at least $n-1$ matches, as otherwise there would be a match with two losers. So, at least $n-1$ matches are nessecary to determine a winner, i.e. $n-1$ comparisons are nessecary to determine the minimum.

The explanation given in the book is valid, but I personally prefer another approach. (which does require some elementary graph theory) Suppose you draw the graph with the elements as nodes and you draw an edge for each pair of elements that your algorithm compares. Note that it is impossible to know which of a pair of elements is smaller if there is no path between them in this graph. So, if we have determined the minimum, this graph must connected. Any connected graph on $n$ nodes has at least $n-1$ edges, so there must have been $n-1$ comparisons.


What mathematics can be interesting for these CS areas?

For the field of A.I. and machine learning, I would recommend you to explore and learn more about these topics:

Statistics
Probability
Stochastic processes
Bayesian Data Analysis
Convex Optimization
Graph Theory

With your math background, you could easily pick any good machine learning book and learn the required math that you don't have as you go. Kevin Murphy's new book, Machine Learning: A Probabilistic Perspective, covers most of these topics and it serves as a good introductory textbook to machine learning.

I personally learned a lot from Dephne Koller's book, Probabilistic Graphical Models. It also covers most of the previously mentioned topics, but, as the book's name suggests, it focuses on graphical models.

Although both of these books have enough math to keep you busy for a while, you might find "The Elements of Statistical Learning", by Hastie et al. more useful if you want to focus more on the mathematical part of the machine learning.


How much math background do you need to understand how category theory is applied to Haskell?

The first step is to learn category theory without regards to Haskell (and if you don't have it, Haskell without regards to category theory). A book such as Lawvere's Conceptual Mathematics is a good start. Awodey is also recommended, and Leinster's recent Basic Category Theory.


Is this language Recursively Enumerable or Not RE?

$L = \{\text{<M, k>| M is a Turing Machine and } |w \in L(M) :  w \in a^*b^*|
 \geq k \}$

Now we want to find whether $L$ is $RE$ or not.

Yes, indeed your interpretation of language $L$ is wrong.

$L$ is a language of strings of form $\langle M, k \rangle$ where $M$ is turing machine which accepts atleast $k$ strings of form $a^*b^*$.

So, now it's easy to see that $L$ is indeed $RE$. For that we can run $M$ on all strings of form $a^*b^*$ by using dove tailing approach. If $\langle M, k \rangle \in L$ then eventually $M$ will accept $k$ strings of form $a^*b^*$. And at that point we will accept $\langle M, k \rangle$.

So as per your question answer is that $L$ is $RE$.


Showing asymptotic lower bound on log of recurrence

Your sequence $T(n)$ is, in fact, the Catalan numbers, as show on the On-Line Encyclopedia of Integer Sequences. You can also take a look at the Wikipedia article on Catalan numbers, which shows its many applications in combinatorics.
$$T(n)=C(n-1)=\frac{(2(n-1))!}{n!(n-1)!}\sim \frac{4^{n-1}}{n^{3/2}\sqrt{\pi}}.$$
In particular,
$$\log T(n) = (n-1)\log 4 - \frac32\log n - \frac12\log\pi + o(1),$$
or,$$\log T(n) \sim n\log 4.$$


Median of two sorted arrays of different size in logarithmic time?

Given two sorted arrays $A[1],\ldots,A[\ell]$ and $B[1],\ldots,B[m]$, the goal is to find the median. Let's assume for simplicity that $n := \ell+m$ is odd, and that all elements are distinct. Therefore we are looking for the element which has exactly $\frac{n-1}{2}$ below it in both arrays.

Given an element in one of the arrays, it is easy to find whether it is the median, smaller than the median, or larger than the median. For example, suppose that the element in question is $A[i]$. There are $i-1$ elements below it in $A$. If it were the median, then there would be exactly $j := \frac{n-1}{2} - (i-1)$ elements below it in $B$, which would put it between $B[j]$ and $B[j+1]$. Checking whether this holds, there are three cases:

$B[j] < A[i] < B[j+1]$. In this case $A[i]$ is the median.
$A[i] < B[j]$. In this case there are fewer than $j$ elements below $A[i]$ in $B$, and so there are fewer than $\frac{n-1}{2}$ elements below $A[i]$. In other words, $A[i]$ is smaller than the median.
$A[i] > B[j+1]$. Symmetrically, in this case $A[i]$ is larger than the median.

Suppose that the median belongs to the array $A$. Using the test described above, we can find it using binary search: we start with the middle element of $A$. If it is the median, we're done. If it is larger than the median, we continue with the middle element of the first half of $A$, and if it smaller than the median, we continue with the middle element of the second half of $A$. Continuing in this way, we will eventually find the median in at most (roughly) $\log_2 \ell$ steps.

What if the median doesn't belong to $A$? Our algorithm will get stuck. Since this is an identifiable situation, this suggests an algorithm which finds the median:

Try to find the median in $A$ using binary search.
If the binary search algorithm gets stuck, find the median in $B$ using binary search.

Note that if the first step fails, the second must succeed. The overall running time is $O(\log \ell + \log m) = O(\log n)$.


Is it because the cohorts don't employ timeout concept in 2PC?

Yes, in one case they can not use a timeout. It is described in the paper too (II.B.1):

  The Two-Phase Commit Protocol goes to a
  blocking state by the failure of the coordinator when the
  participants are in uncertain state. The participants keep
  locks on resources until they receive the next message
  from the coordinator after its recovery

In practice that 'uncertain state' means voting 'yes'. After a cohort votes 'yes', there is no going back, it waits for the global decision. (Other cases are fine: by voting 'no', the given cohort immediately knows that the global decision is also a 'no', and if the coordinator dies even before initiating the voting round, cohorts may decide voting 'no' based on a timeout)


How to design xml schema for digital circuits?

A simple example.

Assume the following circuit in symbolic notation:

Cir = ((A OR B) AND (C OR D)) OR (NOT(D) AND F), where OR , AND, NOT etc can be realized with serial/parallel connections etc..

XML scheme proposition:

<circuit>
    <gate-or>
        <element>
            <gate-and>
                <element>
                    <gate-or>
                        <element>A</element>
                        <element>B</element>
                    </gate-or>
                </element>
                <element>
                    <gate-or>
                        <element>C</element>
                        <element>D</element>
                    </gate-or>
                </element>
            </gate-and>
        </element>
        <element>
            <gate-and>
                <element>
                    <gate-not>D</gate-not>
                </element>
                <element>F</element>
            </gate-and>
        </element>
    </gate-or>
</circuit>

This is an example xml-scheme where the root element is circuit and can have gates or elements as children and each gate (eg gate-or or gate-and) can have elements as children etc..

Of course this is very verbose , a yaml or json representation scheme would be lighter


Blum's speedup theorem showing unclassifiable complexity languages?

If a language is decidable then it is accepted by some Turing machine. The running time of that Turing machine is by definition time-constructible. So any computable function has a time-constructible upper bound by definition.


Do not understand a lemma regarding dinics algorithm

"How does it look like after $\sqrt{m}$ iterations?"

To see this, we need a property: the number of layers increases by at least $1$ after each iteration.  In other word, the shortest distance from $s$ (source) to $t$ (sink) increases by at least $1$. This is the key property of Dinic's algorithm. I'll put the proof at the end. (Please help if anyone has a better way to arrange these contents. I don't want to let the proof occupy too much space.)

So after $\sqrt{m}-1$ iterations, $G_L$ has at least $\sqrt{m}+1$ layers, because there are at least $2$ layers at first, one for $s$ and one for $t$. This means there are at least $\sqrt{m}$ "edge layers" between the vertex layers. So the edge layer with the least number of edges has at most $\frac{m}{\sqrt{m}}=\sqrt{m}$ edges. One more thing you should notice is this edge layer forms a $s$-$t$ cut in the residual graph with capacity at most $\sqrt{m}$. (You can't jump across any layer, so you must pass this layer.) According to max-flow-min-cut theorem, capacity of maximum flow in the residual graph is at most $\sqrt{m}$. So we need at most $\sqrt{m}$ more iterations. In conclusion, the total number of iterations is $O(\sqrt{m})$.

Proof of the key property:

Suppose at some iteration we have residual network $G_f$ and its corresponding level graph $G_L$, and after one iteration we have residual network $G_f'$. To prove that $s$-$t$ distance in $G'_f$ is longer, first let's see the difference between $G_f$ and $G_f'$: if an edge $(u,v)$ is saturated, $(u,v)$ is removed and $(v,u)$ is added. Note that the blocking flow only contains edge in $G_L$, so $(u,v)$ is a "foward" edge in $G_L$, and $(v,u)$ is a "backward" edge in $G_L$. Here "forward" means the edge moves from lower level to higher level in the level graph.

Consider a shortest path from $s$ to $t$. Each edge $e$ on this path has three possibilities:

$e\notin G_f$. In this case $e$ is new, so it's "backward" in $G_L$ according to our claim above.
$e\in G_f$ but $e\notin G_L$. In this case, $e$ can't be forward. Otherwise it would be contained in $G_L$. (Note that a forward edge can't jump across a layer because the level graph is constructed based on shortest distance.)
$e\in G_L$. This is the only possible forward edge, which increases the level by exactly $1$.

Consider the level in $G_L$ of each vertex on the $s$-$t$ path. The level increases by at most $1$ after each step. So the shortest path from $s$ to $t$ in $G_f'$ is never shorter than the shortest path in $G_L$. Furthermore, it should be strictly longer: if the distance is the same, it means the shortest path in $G_f'$ only consists of type $3$ edges. This means we can find an unsaturated path in $G_L$, which violates the definition of blocking flow.

Therefore, the number of layers is strictly increasing.


Turing machine Representation for string of 3 letters

The language you are trying to decide here is xxx: that is, three copies of x. What is x? Well, it can be anything in $\Sigma *$: any string in your alphabet. (Usually this means "any binary string", but you can also use a different alphabet, the principle will be the same.)

So you're looking for any string which consists of something repeated three times. So strings in the language include 111, and 000, and ε (the empty string), and 100100100, and 101011010110101.

As for the machine that recognizes this, recognizing the language xx : $x \in \Sigma *$ is a classic demonstration of the power of Turing machines (since this language is neither regular nor context-free). Try starting from that machine and seeing what changes you'd need to make for xxx.


Running time and stack depth of a lisp recurrence

The time and other resources (such as stack consumption) needed to run an with the argument $x \in \mathbb{N}^*$ is the sum of:

the resources needed to compute (- k 1) with k bound to $x$;
the resources needed to compute an with the argument $x-1$;
the resources needed to compute (if (= k 0) alpha (+ (* beta $y$`) kappa))` where $y$ is the value returned by the recursive call to an.

Let $T(x)$ be the running time of this computation. For $x \gt 0$, by the analysis above, $T(x) = T(x-1) + C$ for some constant $C$ (assuming that the arithmetic operations take constant time). A very simple induction shows that $T(x) = C \, x + T(0)$, i.e. $T(x) = \Theta(x)$. The same goes for stack consumption.

There is more than one stack push per recursive call, (3 in a naive interpreted Lisp such as Emacs Lisp), but that doesn't affect the $O$ or $\Theta$ analysis. Other than this minor detail your analysis is correct.

Are you sure that you typed the right code? Emacs has a fairly low limit on stack usage but even it can sustain more recursive calls (up to 123 in Emacs 23 where max-lisp-eval-depth is 500).


How to prove correctness of a shuffle algorithm?

First, let us make two maybe obvious, but important assumptions:

_.random_item can choose the last position.
_.random_item chooses every position with probability $\frac{1}{n+1}$.

In order to prove correctness of your algorithm, you need an inductive argument similar to the one used here:

For the singleton list there is only one possibility, so it is uniformly chosen.
Assuming that the list with $n$ elements was uniformly chosen (from all permutations), show that the one with $n+1$ elements obtained by your technique is uniformly chosen.

From here on, the proof is wrong. Please see below for a correct proof; I leave this here because both the mistake and the following steps (which are sound) might be educational.

It is useful to derive a local (i.e. element-wise) property that has to hold, because arguing about the whole permutation is painful. Observe that a permutation is uniformly chosen if every element has equal probability of being at each position, i.e.

$\qquad \displaystyle \mathop{\forall}\limits_{\pi \in \mathrm{Perm}_n} \operatorname{Pr}(L = \pi) = \frac{1}{n!} \quad \Longleftrightarrow \quad \mathop{\forall}\limits_{i=1}^n\ \mathop{\forall}\limits_{j=1}^n \operatorname{Pr}(L_i = j) = \frac{1}{n} \qquad (1)$

where $n = |L|$ and we assume for the sake of notational simplicity that we insert $\{1,\dots,n\}$ into the list.

Now, let us see what your technique does when inserting the $n+1$st element. We have to consider three cases (after the swap):

One of the elements in the list, not swapped, i.e. $i \in \{1,\dots,n\}$ and $j \in \{1,\dots,n\}$
One of the elements in the list, swapped, i.e. $i = n+1$ and $j \in \{1,\dots,n\}$
The new element, i.e. $i \in \{1,\dots,n+1\}$ and $j = n+1$

For each case, we compute the probability of element $j$ being at position $i$; all have to turn out to be $\frac{1}{n+1}$ (which is sufficient because of $(1)$). Let $p_n = \frac{1}{n}$ be the probability of one of the first $n$ elements being at any position in the old list (induction hypothesis), and $p_s = \frac{1}{n+1}$ the probability of any position being chosen by random_item (assumptions 1, 2). Note that the coice of the list with $n$ elements and picking the swap position are independent events, so the probabilities of joint events factor, e.g.

$\qquad \displaystyle \operatorname{Pr}(L_i=j, i \text{ swapped}) = \operatorname{Pr}(L_i=j)\cdot \operatorname{Pr}(i \text{ swapped}) = p_np_s$

for $i,j \in \{1,\dots,n\}$. Now for the calculations.

We only consider the old $n$ elements. Such an element $j$ is at position $i$ if and only if it was there before the last insertion and $i$ is not selected as swap position, that is

$\quad \displaystyle \operatorname{Pr}(L_i = j) = p_n(1-p_s) = \frac{1}{n}\cdot\frac{n}{n+1} = \frac{1}{n+1}$.
Here we consider that one of the old elements is swapped to the last position. Element $j$ could have been at any of the old positions, so we sum over all probabilities that $j$ was at position $i$ and $i$ is chosen as swap position, that is

$\quad \displaystyle \operatorname{Pr}(L_{n+1} = j) = \sum_{i=1}^n p_np_s = \sum_{i=1}^n \frac{1}{n}\cdot\frac{1}{n+1} = \frac{1}{n+1}$.
The new element ends up at position $i$ if and only if $i$ is chosen as swap position, that is

$\quad \displaystyle \operatorname{Pr}(L_i = j) = p_s = \frac{1}{n+1}$.

All turned out well, your insertion strategy does indeed preserve uniformity. By the power of induction, that proves that your algorithm creates uniformly distributed permutations.

A word of warning: this proof breaks down if the inserted elements are not pairwise different resp. distinguishable, because then the very first equation is no longer valid. But your algorithm is still valid; every permutation with duplicates is generated by the same number of random executions. You can proof this by marking duplicates (i.e. making them distinguishable), perform above proof and remove the markings (virtually); the last step collapses equal sized sets of permutations to the same.

As Steven has remarked correctly in the comments, above proof is fundamentally flawed as $(1)$ does not hold; you can construct distributions on the set of permutations that fulfill the right-hand, but not the left-hand side¹.

Therefore, we will have to work with probabilities of permutations, which turns out to be not that bad after all. The assumptions on random_item and the inductive structure outlined in the very beginning of the post remain in place, we continue from there. Let $L^{(k)}$ denote the list after $\{1,\dots,k\}$ have been inserted.

Let $\pi' \in \mathrm{Perm}_{n+1}$ an arbitrary permutation of $\{1,\dots,n+1\}$. It can be written uniquely as

$\qquad \displaystyle \pi' = (\pi(1), \pi(2), \dots, \pi(i-1), n+1, \pi(i+1), \dots, \pi(n), \pi(i))$

for some $\pi \in \mathrm{Perm}_n$ and $i \in \{1,\dots,n+1\}$. By induction hypothesis, $\operatorname{Pr}(L^{(n)} = \pi) = \frac{1}{n!}$. Furthermore, random_item picks position $i$ with probability $\frac{1}{n+1}$ by assumption. As the random choices of $\pi$ and $i$ are (stochastically) independent, we get

$\qquad \displaystyle \operatorname{Pr}(L^{(n+1)} = \pi') = \operatorname{Pr}(L^{(n)} = \pi) \cdot \operatorname{Pr}(i \text{ swapped}) = \frac{1}{(n+1)!}$

which we had to show. By the power of induction, that proves that your algorithm creates uniformly distributed permutations.

For example, assign every permutation in $\{(1, 2, 3, 4), (2, 3, 4, 1), (3, 4, 1, 2), (4, 1, 2, 3)\}$ probability $\frac{1}{4}$ and all others $0$. There are also examples that assign every permutation a non-zero probability.


Will the future quantum computers use the binary, ternary or quaternary numeral system?

The other answers are nice, but none address the question: what numeric base(s) might quantum computers use? I will answer in two parts: first, the question is a little subtle, and second, you may use any numeric base, and then you work with qutrits or in general with qudits, which lead to qualitatively new intuitions! Or at any rate, I will try to make the case that they do.

A quantum bit isn't just a $0$ or a $1$, it's a bit more complex than that. For example, a quantum bit may be in the state $\sqrt{\frac{1}{4}}|0\rangle+\sqrt{\frac{3}{4}}|1\rangle$. When measured, you will measure the outcome $0$ with probability $\frac{1}{4}$ and the outcome $1$ with probability $\frac{3}{4}$. The 'superposition' you talked about is $\sqrt{\frac{1}{2}}|0\rangle+\sqrt{\frac{1}{2}}|1\rangle$, but in general any pair of complex numbers $a$ and $b$ will do, as long as $a^2+b^2=1$. If you have three qubits, then you can entangle them, and the state will be

$$a_0|000\rangle + a_1|001\rangle+a_2|010\rangle+a_3|011\rangle+a_4|100\rangle +a_5|101\rangle+a_6|110\rangle +a_7|111\rangle$$

But when you measure this three-qubit system, your measurement outcome is one out of these 8 states, that is, three bits. This is this really weird dichotomy where on the one hand quantum systems seem to have this exponential state space, but on the other hand we only seem to be able to 'get at' a logarithmic part of the state space. In 'Quantum Computing Since Democritus', Scott Aaronson probes this question by matching off several complexity classes to try and understand how much of this exponential state space we can exploit for computation.

Having said that, there is an obvious complaint to the answer above: all the notation is in binary. Qubits are in a superposition of two base states, and entangling them doesn't change that much, because three qubits are in a superposition of $2^3$ base states. It's a legitimate complaint, because one usually thinks of $\texttt{unsigned int}$ as a number, and only remembers that it is implemented as a 32-bit string as an afterthought.

Enter the qutrit. It is a vector in $\mathbb{C}^3$, in other words, it consists of three base states rather than two. You operate on this vector with a $3\times 3$ matrix, and all the usual things done in quantum computing don't change much, because any operation expressed in terms of qutrits can be expressed in terms of qudits, so it's really just syntactic sugar. But some problems are much easier to write down and/or think about when expressed as qudits instead of entangled qubits. For example, a variation of the Deutsch-Josza problem might ask, given an oracle for a function $f\colon \{0,\ldots, kn-1\}\rightarrow \{0,\ldots, k-1\}$, is this function constant or balanced, given that one is promised to be the case? This function naturally takes one $k$-qudit register as input. To solve it, you must apply a Fourier transform to this $k$-qudit, like so: (if this goes over your head, don't worry, it's just for illustration)

$$|a\rangle \mapsto \sum_{u=0}^{k-1}e^{i2\pi\frac{au}{k}}|u\rangle$$

If you want to express this in binary, you end up with a gate that does this on numbers $0\ldots k-1$ and acts trivially (does nothing) on all numbers $\geq k$, which is slightly less contrived than doing it this way. Similarly, consider a Bernstein-Vazirani variation where the oracle computes an in-product in some radix $r$. If $r=2$, then we know how to do it. But if $r=5$, the problem is much easier to solve by hand using several $5$-qudit registers. Some problems are easier if you have several different qudit registers, e.g. one $5$-qudit register and one $2$-qudit register.

In summary, yes, you are free to consider other numeric bases, and in the right setting that will make your life easier, for the same reason that thinking about numbers in terms other than their binary expansion helps you with normal computers. I felt compelled to answer because while most answers explained that a qubit has something to do with two base states when measuring but infinite in principle, no answer mentioned that the OPs suggestion of using other bases is legitimate and in fact really happens (for example, in Quantum walks on graphs, Aharonov et al. use a subroutine that takes a qubit and an $n$-qudit as input)


How to do product construction with 2 DFA which has dead state

The product construction works for any two DFAs. There is nothing special you need to do. The resulting automaton would have many dead states and so won't be minimal, but that doesn't affect its correctness.


A cache is a copy of a "chunk" of main memory of a given size that is held in a faster ram closer to the CPU.

In the example given each cache block holds a chunk that is 16 bytes in size and there are a total of 64 blocks available.   When a CPU accesses an address if it's not already in cache, the data is copied from main memory into the cache in 16 byte chunks.  When the cache load selects a cache block, it ignores the lower 4 bits of the address (for a 16 byte block) then it uses the next 6 bits of the address (for 64 locations) to determine which block to use and the remaining bits of the address are used as a TAG to keep track of the addresses currently cached.  It fills the block with the 16 bytes starting at the accessed address with the lower 4 bits zeroed.

The math used in the explanation is based on the physical processes...  Dividing by 16 ignores the lower 4 bits.  Using the modulo of 64 on the result uses the next 6 bits as an index into the cache.  The explanation didn't deal with tagging, but that wasn't really part of the question which was "Which cache block is it using?".

So consider the CPU accesses address 1205 (Using an address that doesn't start at the beginning of a cache block for a little more clarity.):

A 16 bit address 1205 in binary is 0000010010110101.

Ignoring the lower 4 bits, the memory's block address is 1001011

Since the cache is 64 blocks it uses the next 6 bits to select which cache block to use.  In this case 001011 is used.  This is block number 11.

The remaining bits, 000001, are used in a tag to indicate which memory block is in the cache.

The data is then loaded from the cache into the CPU using the lower 4 bits 0101 as an index (or the 6th byte of the block).

If a subsequent access is for address 1210, or binary 0000010010111010, the tag will match and the cache system won't have to access main memory for the data.  It's already in cache and can be used quickly, the CPU just has to use the lower 4 bits of the address 1010 to load the 11th byte from the cache block...

If, however a future access is for address 9403, or binary 0010010010111011, this address also selects cache block 11 so the previous data is overwritten with 16 bytes of data from main memory beginning at 9392 (lower 4 bits zeroed), the new tag for the block is 001001, and the CPU loads the byte from 1011 in the cache block.


Efficient algorithm for retrieving the transitive closure of a directed acyclic graph

The fact that our graph is acyclic makes this problem much simpler.

Topological sort can give us an ordering of the vertices $v_1,v_2,\dots,v_n$ such that, if $i < j$, then there is no edge from $v_j$ back to $v_i$. We've listed the vertices such that all edges in go "forward" in our list.

(edited to fix analysis and give slightly faster algorithm)

Now we just go backwards through this list, starting at the last vertex $v_n$. $v_n$'s transitive closure is just itself. Also add $v_n$ to the transitive closure of every vertex with an edge to $v_n$.

For each other vertex $v_i$, going from the end backwards, first add $v_i$ to its own transitive closure, then add everything in the transitive closure of $v_i$ to the transitive closure of all the vertices with an edge to $v_i$.

The running time is $O(n+m+nm) = O(n^3)$ in the worst case, with $n$ the number of vertices and $m \in O(n^2)$ the number of edges. Topological sort takes time $O(n+m)$. Then we do another $O(mn)$ work in the backward pass: As we go backwards through the list, for each edge, we have to add up to $n$ vertices to somebody's transitive closure.

Note that you can get a nice constant-factor speedup by representing everyone's transitive closure by bit-arrays. Say you only had $n=64$; then you would use a single 64-bit int where bit $i$ is 1 if $i$ is in my transitive closure and 0 otherwise. Then the part where we add everything in $i$'s transitive closure to $j$'s is really fast: We just take $c_j$ |= $c_i$. (Binary OR operation.)

For $n > 64$, you'd have to keep them in arrays and do some arithmetic, but it would be much faster than an Object set.

Also, I know the big-$O$ in the very worst case is still $O(n^3)$, but to beat this in practice you'd have to have something much more complex. This algorithm also does very well on sparse graphs.


initially you have:
Q={A, B, C, D, E}
dist(A)=0, dist(B)=dist(C)=dist(D)=dist(E)=inf
previous(A)=previous(B)=previous(C)=previous(D)=previous(E)=undefined

from Q the vertex with min distance is A. Therefore you choose A and you do
(dist(A)+length(A,B)

your remove A from Q, now you have
Q={B, C, D, E}
In Q the vertex with the min dist is C with dist(C)=5, so you pick C
the only vertex adjacent to C is D so you have
(dist(C)+length(C,D)

you remove C from Q, now you have
Q={B, D, E}
the vertex with the min dist in Q is B so you pick B
(dist(B)+length(B,D)

you remove B from Q, now you have
Q={D, E}
the vertex with the min dist in Q is D so you pick D
(dist(D)+length(D, E)

you remove D from Q, now you have
Q={E}
the vertex with the min dist in Q is E so you pick E
No neighboors
remove E from Q
Q is empty and the algorithm terminates
previous(E)=D
previous(D)=B
previous(B)=A
so this is your shortest path from A to E

I skipped the distance checking for the previous vertex for simplicity (it is always equal), the algorithm performs this check. I think you confuse picking a vertex from the set Q and changing the distance of a vertex. They are two different things. The fact that you are assigning a distance at some point to a vertex does not mean that it will be final. It will be final only when this vertex have the minimum distance in the set Q and it will be the one to be picked next and removed. I hope I am clear.


Domain theory: Definition of isomorphisms

I think I have found an answer to my question, by proofing that the monotonicity of $f$ and $f^{-1}$ imply the continuity of $f$ and $f^{-1}$.
Please correct me if I made a mistake – I will give you some days to check my proof before I accept my own answer.

Lemma: If a function $f \colon M \to N$ between two cpos is monotonic, the inequality

$$\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\} \leq f\left(\bigsqcup\{ m_0, m_1, m_2, \dots\}\right)$$

holds for all chains $m_0, m_1, m_2, \dots$. This is well known and easy to show, so I will skip the proof of this.

Let $f \colon M \to N$ be now a bijective function between two cpos and let it, and its inverse $f^{-1}$, be monotonic.
By the above lemma we have already one side of inequality to proof the continuity of $f$. It remains to show that

$$f\left(\bigsqcup\{ m_0, m_1, m_2, \dots\}\right) \leq \bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\}$$

holds for all chains $m_0, m_1, m_2, \dots$ in $M$.
Since $$\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\} = f\left(f^{-1}\left(\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\}\right)\right),$$

and both $f$ and $f^{-1}$ are monotonic, the above inequality is equivalent to

$$\bigsqcup\{ m_0, m_1, m_2, \dots\} \leq f^{-1}\left(\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\}\right).$$

However, again by above lemma we have

$$ f^{-1}\left(\bigsqcup\{f(m_0), f(m_1), f(m_2), \dots\}\right)
\geq \bigsqcup\{f^{-1}(f(m_0)), f^{-1}(f(m_1)), f^{-1}(f(m_2)), \dots\}
= \bigsqcup\{ m_0, m_1, m_2, \dots\}.$$

So $f$ is continuous. You show the continuity of $f^{-1}$ in the same way.


Proving asymptotic notations for functions

The first thing to do is to try to develop an intuition for whether the claim is true or false. Very roughly, $f=\Omega(h)$ says that $f$ is bigger than $h$, and $g=O(h)$ says that $g$ is smaller than $h$.  In both of those statements, "bigger" really means "at least as big as" and I've left off the conditions of "up to a constant factor" and "for large enough inputs".

So, if $f$ is bigger than $h$ and $g$ is smaller than $h$, is $f$ bigger than $g$? Intuitively, it ought to be. Since we've simplified, we might have gone wrong, but our intuition is that we should try to prove that the statement is true, rather than trying to find a counterexample.

Apply the definitions and you get that (try it on your own, first!)...

   ... there are constants $c$ and $d$ such that, for all large enough $n$, $f(n)\geq c\,h(n)$ and $g(n)\leq d\,h(n)$. Therefore, $f(n)\geq \tfrac{c}{d}g(n)$ for all large enough $n$, which is to say that $f=\Omega(g)$.


Is there an alternative to full factorization for testing the Polya conjecture?

You can use a sieve to significantly improve the running time. Decide on a number $N$, say $N = 2^{30}$. Initialize an array of length $N \times 2$ bits: one to keep track of the parity of the number of prime factors, and the second to mark which numbers have been visited. Now run an algorithm similar to the sieve of Eratosthenes. The running time equals the total number of prime factors of all numbers up to $N$, which is roughly $N\log\log N$.

With this information in hand, it is easy to check for violations of the conjecture.


Is there any language that can be Turing-reduced to all languages?

Every Turing-decidable language is Turing-reducable to every language.
According to the definition in Wikipedia,

Given two sets $A,B \subseteq \mathbb{N}$ of natural numbers, we say $A$ is Turing reducible to $B$ and write
$$A \leq_T B$$
if there is an oracle machine that computes the characteristic function of $A$ when run with oracle $B$.

Now if $A$ is decidable, the oracle machine can decide $A$ even without the use of the oracle, so $A$ is Turing-reducible to every language.


implementing ExtractMin on a Max-heap in O(log(n)) time

Suppose that there is an algorithm that examines a complete max-heap (i.e. one in which all leaves have the same depth) and outputs the minimum without accessing all leaves. Whenever the algorithm examines the value of an internal node, hand it the value 2, and whenever it examines the value of a leaf, hand it the value 1. The algorithm misses at least one leaf $\ell$, and so cannot tell the situation in which all leaves have the value 1 from the situation in which all leaves but $\ell$ have the value 1, and $\ell$ has the value 0.


How do I find the intersection of subgraphs in a directed acyclic graph efficiently?

The more efficient algorithm you're looking for is breadth/depth-first search.


You have mentioned the temporal ordering of events, then you may have known about temporal logic [1] such as LTL [2] and CTL [3]. Temporal logic allows you to reason about time and thus temporal ordering of events. For instance (from [1]), one may wish to say that whenever a request is made, access to a resource is eventually granted, but it is never granted to two requestors simultaneously.

The greatest advantage of using LTL or CTL to express the properties of the system is that you can automatically verify them. This process is known as model checking [4].

There are quite a few of model checkers [5]. For instance, in SPIN, systems to be verified are described in Promela (Process Meta Language), which allows one to specify "atomic blocks" (Is this your intention of What transactions need to be atomic?)?

As for the producer/consumer problem, it has been extensively studied in the context of model checking. This lecture note uses it as an example for SPIN (you can easily find other resources). In addition, [6] verifies an edition written in SystemC, and [7] verifies it using TLA+.

[1] temporal logic (wiki)

[2] LTL (wiki)

[3] CTL (wiki)

[4] model checking (wiki)

[5] model checkers (wiki)

[6] Verifying SystemC: a Software Model Checking Approach

[7] An Example of Debugging Java with a Model Checker (web page)


How can we form a graph from this problem?

If you just want the visualization, then have a look at this


A problem to maximize the number of edges in a cycle while minimizing the total weight

This is NP-complete, since an instance $(V,E)$ of the NP-complete problem Hamiltonian Path can be reduced to it: Turn each vertex in the original HP instance into a pair of vertices $a_i, b_i$ connected by a low-weight edge, with one vertex in each part of the bipartite graph, and add a high-weight edge $a_ib_j$ for each edge $v_iv_j$ in the original graph. Finally add $O$. Solve your instance and delete $O$: the original graph has a HP iff $2|V|−1$ edges remain.

All this is to say there is almost certainly no polynomial-time algorithm to solve your problem (since if there was, Hamiltonian Path, and every other NP-complete problem could also be solved in polynomial time).  Adapting an algorithm for solving TSP sounds reasonable to me.


Since HOL Light is based on $\lambda$ Calculus and HOL Light is typed and as we know there is untyped $\lambda$ Calculus and typed $\lambda$ Calculus, HOL Light starts by parsing something close to untyped $\lambda$ Calculus, creating pre-terms. Then it applies a typing checking and typing phase, along with resolving overloaded operators resulting is something closer to typed $\lambda$ Calculus. Obviously HOL is much more than typed $\lambda$ Calculus, but the point here is to understand what pre-term means with regards to parsing.

The only reference I have found for this is in

Lectures on the Curry-Howard Isomorphism
Section 1.2 Pre-terms and $\lambda$-terms.

Specifically how this is done in HOL Light is in the parser module:

The pre-terms are created with

let ptm = (parse_pteterm << lex << explode) input

and the type checking, etc. is done with

let term = (term_of_preterm << (retypecheck [])) ptm


What is the time complexity Big-O of this algorithm?

The second for-loop while be executed N + N/2 + N/4 +....+ N/N

, the first for-loop decides how much the second for-loop will be executed.

When i = 0, j loops until N

, i = N/2, j loops until N/2

, And so on

, The Big O notation of N + N/2 + N/4 +....+ N/N will be O(N)


Generating bit sequence containing every possible of length 1...n

Such a sequence (for arbitrary $k$-ary encodings) is known as a De Bruijn sequence. For the case of the binary encodings, the De Bruijn sequence has length $2^n$. As the output is exponential, this problem is clearly not in $P$, but it lies in $EXP$, as it can be constructed via a Hamiltonian path along the De Bruijn graph (see also here)


Why are regular expressions defined with union, concatenation and star operations?

1) If we also allow intersection and complement, then the resulting expressions are sometimes called extended regular expressions; as the regular languages are closed under boolean operations nothing is gained by them. It is just syntactic sugar. A similar conclusion holds for the reverse operation. Part of the reason why on first instance all the other operations are not mentioned is the goal of keeping the definition as simple as possible, so that (inductive) proofs do not have to take care of to many cases. Another cause might be that if we allow certain operations, but others not, in some cases very distinct (subregular) language classes result, for example if we consider extended regular expression without the star operator, then we get a proper subclass of the regular ones, the so called star-free or aperiodic languages, see wikipedia:star-free language.

2) If we keep items 1. - 6. but just alter item 4. in using intersection instead of union, we get a proper subclass of the regular languages. For example we could no longer describe the language $L = \{a,b\}$ as it would involve the union of $\{a\}$ and $\{b\}$ (see proof below). If we allow complementation, things change as we have union back by DeMorgan's laws.

3) This was partly answered by me in 1), but what you mean when you say that this definition is preferred? I know definitions where 2. is omitted (as we have by 6. that $L(\emptyset^{\ast}) = \{\varepsilon\}$), or 3. is omitted (as we have $\emptyset = L(\overline{ X^{\ast} }$)), or both are omitted; so this one is not the minimal possible definition (it gives us also some syntactic sugar as we have extra symbols to describe $\{\varepsilon\}$ and $\emptyset$).

EDIT: My first mentioned comment in 2) was wrong, languages in the inductive closure under $\circ$, $^{\ast}$ and $\cap$ do not neccessarily are subsets of $x^{\ast}$ for some $x \in X$, for example consider $L(a\circ b) = \{ab\}$. Nevertheless we have that $L = \{a,b\}$ could not be describes by such an expression. I will give a proof, namely I proof that
if $L = L(R)$ for some expression with the modified 4th item, then if $X = \{a,b\}$ (and hence $a\ne b$)
$$
 \{a,b\} \subseteq L \Rightarrow ab \in L.
$$
The proof goes by induction on the expression $R$. For the base case it holds vacuously, now suppose it holds for $L(R_1), L(R_2)$.
If $L = L(R_1 \cap R_2) = L(R_1) \cap L(R_2)$ and $\{a,b\} \subseteq L$,
then $\{a,b\} \subseteq L(R_i), i = 1,2$ hence by induction hypothesis we have $ab \in L(R_1) \cap L(R_2)$. If $\{a,b\} \subseteq L(R_1\circ R_2) = L(R_1)L(R_2)$ then as $a = a\cdot \varepsilon = \varepsilon\cdot a$ we must have $a\in L(R_1)$ and $\varepsilon \in L(R_2)$ or vice versa. Suppose the first case. If $b \in L(R_1)$, then $ab \in L(R_1)$ by induction hypothesis, hence $ab = ab\cdot \varepsilon \in L(R_1)L(R_2)$. Now suppose $b \in L(R_2)$, then we have $a\cdot b \in L(R_2)L(R_2)$ by definition of $L(R_1)L(R_2)$. Lastly if $a,b \in L(R_1^{\ast})$, then $a \in L(R_1)^n$
and $b \in L(R_2)^m$ for some $n,m > 0$. If $n = m = 1$ we find $ab \in L(R_1)$ by induction hypothesis, so suppose $n > 1$, but this gives $a \in L(R_1)$, similar either $m = 1$ or $m > 1$ gives $b \in L(R_1)$ and the induction hypothesis gives $ab \in L(R_1) \subseteq L(R_1^{\ast})$. $\square$

Remark: One commonly used conclusion: If $a = uw$, then $u = a$ or $w = a$. This follows as $1 = |a| = |uw| = |u| + |w|$, hence $|u| = 0$ and $|w| = 1$ or $|u| = 1$ and $|w| = 0$. In the first case we have $u = \varepsilon$ and hence $a = w$.


NP-Hard problems which are not NP-Complete

No. E.g. the Halting problem is a decision problem which is NP-hard but not in NP and therefore not NP-complete.
In normal usage yes, because an NP-complete problem must be in NP and NP is a class of decision problems. But see Decision problems vs “real” problems that aren't yes-or-no.


Converting S->aTbS|epsilon T->aTb|epsilon to chomsky normal form

Our grammar $G$ has following two production where $S$ is start symbol.

$S\rightarrow aTbS \vert\epsilon$

$T\rightarrow aTb|\epsilon$

Now to convert it to chomsky normal form (CNF) we have to perform following steps:

If there is some production having $S$ in it's right side($S\rightarrow aTbS$ in this example) then add new start symbol $S_0$ and production rule $S_0 \rightarrow S$ to $G$.
Then remove null production from $G$:
So, after removing null production $G$ will have following productions:

$S_0 \rightarrow S$

$S \rightarrow aTbS|abS|aTb|ab$

$T \rightarrow aTb|ab$
Now we have to remove unit production from $G$. But there are none of them.
Then if there is production containing both terminal and nonterminals on RHS then introduce new non-terminal for the terminal appearing there and replace occurence of terminal in that RHS by this non-terminal. example will make this clear.

we, have this $S \rightarrow aTbS$ production. So we add production $A \rightarrow a$
and $B\rightarrow b$ to G. and then rewrite production $S \rightarrow aTbS$ as $S \rightarrow ATBS$

Doing same for all production we will have production set of $G$ as follow:

$S_0 \rightarrow S$

$S \rightarrow ATBS|ABS|ATB|AB$

$T \rightarrow ATB|AB$

$A \rightarrow a$

$B \rightarrow b$
Now we handle the case where RHS of production contains more than 2 non-terminals.
What we do is simple. We just keep first non-terminal as it is and introduce new
nonterminal for remaining part. Again example will make this clear.

We have this $S \rightarrow ATBS$ production. So we introduce new non-terminal $C$
and add production $C\rightarrow TBS$. Then modify original production as
$S\rightarrow AC$.

Note here that now we have to do this process for newly introduced production also.
i.e $C\rightarrow TBS$ will be converted to $C\rightarrow TD$ for instance and we
have to add $D \rightarrow BS$

Now after this step $G$ will contain following productions:

$S_0 \rightarrow S$

$S \rightarrow AC|AD|AE|AB$

$C \rightarrow TD$

$D \rightarrow BS$

$E \rightarrow TB$

$T \rightarrow AE|AB$

$A \rightarrow a$

$B \rightarrow b$

So now grammar is in CNF. But one thing is still remaining. Original grammar produces empty string but this grammar does not. For that add production $S_0 \rightarrow \epsilon$ to $G$.


Why whenever a caller or client modifies a library collection class, all iterators are made invalid?

The question is "why".

There are two problems: First, you would have to define how an iterator that doesn't become invalid would change if the underlying container changes. That will be an interesting problem. Some languages have iterators that can iterate through hash tables, enumerating all (key, value) pairs in some order. Now imagine you insert an item into the hash table, the number of items becomes too large, and the whole hash table is re-hashed, and you need to define how the iterator is modified in a meaningful way.

Second, if the iterators need to stay valid, you need to keep track somehow which iterators are involved with which underlying container. That's not too difficult, but costs time and space. Together with the first problem, it's much easier to just declare any iterator as undefined after a change.

PS. If you copy / paste this as an answer to a homework question, your teacher will most likely trace it back to this post.


Simplifying SOP: implementing OR with NAND

Unfortunately, you've gotten as far as you can get on this problem.

(Note: I'm going to write AND, OR, NOT, and NAND as $\wedge \vee \neg \uparrow$ respectively, since the standard sum/product/overbar notation tends to end up with lots of stacked bars, and I don't like those.)

You currently have:

$$(a \wedge \neg b) \vee (\neg a \wedge b) \vee (a \wedge b)$$

At this point, you could use NANDs to build all those NOTs and ANDs and ORs…but building an OR was your goal in the beginning! Normally, going into sum-of-products form is exactly the right next step to take, but here you're stuck, because you started with a simple sum in the first place.

It turns out the simplest way to build an OR gate out of NANDs is exactly what you were doing at first.

$$\neg a = a \uparrow a$$

$$a \vee b = \neg a \uparrow \neg b$$

$$a \vee b = (a \uparrow a) \uparrow (b \uparrow b)$$

To my knowledge, nobody's ever found a way to build OR with less than three NANDs, and I very much doubt it's possible (though I wouldn't know how to prove that).


Without a flag that tells you whether an address is a group address or a host address, you can't tell whether it's a group address or a host address.
Remember, a switch only sees the source address and the destination address. It does not have any extra information. So, it needs to be able to tell just by looking at the address whether to multicast the frame or not.


Is the implementation relation between an interface and a class an instantiation or inheritance relation, or neither?

From notes I have from university, here is an explanation I found useful that may help

  An interface, or protocol as it is sometimes called, is a device that is used to allow unrelated objects to interact with one another, by implementing an agreed upon system of behavior. When a class implements an interface, the class agrees to implement all of the methods defined in the interface. Interfaces are useful since they capture similiarity between unrelated objects without forcing a class relationship.

The important line is the bottom, there is no class relationship between classes that impliment an interface. You cant view it in the same way you would with instances of classes and abstract classes. These give a direct relation in terms of object type and subtype.  It is not a guarantee of relation between objects but instead a guarantee of functionality.

To your bullets I would say; Neither, not really, and it is not really like either metaclass or abstract class at all.


Is {xy | x, y ∈ Σ∗ and x contains more a’s than y} regular?

Since the language does not specify what $x$ and $y$ are, you can always let $y=\varepsilon$, i.e., the empty string, then the language only requires $x$ to contain at least 1 $a$. So equivalently, the language is

$\{x\in\Sigma^*\mid x\text{ contains at least 1 }a\}$.

Now it is easy to build a DFA to accept this language.


In Real RAM precision is infinite, this comes straight from definition: it uses exact real numbers. As you have noticed this is purely theoretical model. It is also worth notting that real-RAM model gives enormous computational boost from standard RAM model where each cell uses only fixed length, called machine word.

For hardware (practical one), using something like IEEE754, these are not real numbers, but fixed-precision representation, with sign, significand and exponent. Common float has about seven digits of precision. There are types using 24, 32, 64, 80, 128... bits.

If you want to model something with practical indication in mind, do not use real-RAM as it is too powerful.


Constructing regular expressions with given substring requirments

Hint: Replace each sub-expression of the form $\Sigma^* A \Sigma^* B \Sigma^* C \Sigma^*$ with a union of expressions of the form $\Sigma^\alpha \Sigma^* A \Sigma^\beta \Sigma^* B \Sigma^\gamma \Sigma^* C \Sigma^d \Sigma^*$ for appropriate $\alpha,\beta,\gamma,\delta$.

Notice also the point of the exercise, namely that (plain) regular expressions aren't a good fit for describing passwords. We would really appreciate being able to intersect regular expressions (do you see how that helps?).


You can reduce from independent set. Given a graph, have a variable for each vertex, and for each edge, add the four clauses
$$ x \lor y, x \lor \lnot y, \lnot x \lor y, \lnot x \lor \lnot y, $$
where $x,y$ are the variables corresponding to the vertices connected by the edge. I'll let you complete the proof.


Closure of regular languages under interchanging two different letters

Suppose that you guess that $\sigma$ and $\tau$ should be exchanged, where $\sigma$ appears before $\tau$ (in the original word).
You start reading the input word, letter by letter. When you encounter $\tau$, you can optionally act as if you read $\sigma$. Later on, when you encounter $\sigma$, you can optionally act as if you read $\tau$. From that point on, you accept the word if the original DFA accepted it.
Here is how to implement this in an NFA. Let the original DFA have states $Q$, initial state $q_0$, final states $F$, and transition function $\delta$. We construct a new NFA whose states are $\Sigma \times \Sigma \times Q \times \{0,1,2\}$. The initial states are $\{(\sigma,\tau,q_0,0) : \sigma \neq \tau\}$. The final states are $\Sigma \times \Sigma \times F \times \{2\}$. The most complicated bit is the transition function $\delta'$:

For $\kappa \neq \tau$, $\delta'((\sigma,\tau,q,0),\kappa) = \{ (\sigma,\tau,\delta(q,\kappa),0) \}$.
$\delta'((\sigma,\tau,q,0),\tau) = \{ (\sigma,\tau,\delta(q,\tau),0), (\sigma,\tau,\delta(q,\sigma),1) \}$.
For $\kappa \neq \sigma$, $\delta'((\sigma,\tau,q,1),\kappa) = \{ (\sigma,\tau,\delta(q,\kappa),1) \}$.
$\delta'((\sigma,\tau,q,1),\sigma) = \{ (\sigma,\tau,\delta(q,\sigma),1), (\sigma,\tau,\delta(q,\tau),2) \}$.
$\delta'((\sigma,\tau,q,2),\kappa) = \{ (\sigma,\tau,\delta(q,\kappa),2) \}$.


Without the context of the excerpt, I found it confusing since it seemed to depend on fairly specific implementation details. This is, in fact, the case. These course notes give a decent overview of this and related terminology.

A primary index refers to an index stored in sorted order on the sorting key of data stored in blocks. To look up a value, you do a binary search on the index which will produce a pointer to the block, and then you can do a binary search on the data in the block. If the data wasn't in blocks, there would be no point to this as you could just do binary search directly on the data file. (With a primary index, while the contents of the blocks need to be in sorted order, the blocks themselves don't necessarily need to be.) This index is not dense since it stores a pointer to a block which will typically contain multiple records, so there is not a one-to-one correspondence between index entries and records.

If you wanted to lookup data based on a key that the records are not sorted on, then you couldn't rely on records between index entries being in the same block, thus an index entry would be required for each specific record. This would be a dense index.

So the thing to note is that this terminology is referring to a specific way of storing and indexing data, namely as a collection of sorted blocks. "Primary index" has nothing to do with "primary key" in this terminology. A primary index depends on how the data is actually sorted (assuming it is sorted) which doesn't at all need to be based on the primary key, e.g. you may sort by a timestamp. There is no need for a "primary index" to exist at all.

A B-tree (and its variations) is just a different indexing approach entirely. You can still potentially apply the "dense index"/"sparse index" terminology to it. For example, if your data is sorted on the key the B-tree index is indexing, then it could just as well store only pointers to blocks and then perform a binary search within the block once fetched. This arrangement would produce a sparse index. You could easily imagine different arrangements that would produce a B-tree index that is dense.

I think you are viewing "primary index" as being more widely applicable than it is. I know I was at first which was the source of my confusion. In the context in which it applies, it is a reasonable term, but "primary index" is way too uninformative to stand alone.


Efficient algorithm for simple constraint satisfaction problem

There is unlikely to be any efficient algorithm.

Your first class of constraints are monotone exactly-1 CNF clauses.  Your second class of constraints are monotone CNF clauses.  The monotone part indicates that negated literals aren't allowed (you can't have $x_1 - x_3 = 1$ or $x_1 - x_4 \ge 1$).

Thus, in the special case where you have only type-2 constraints, the problem becomes #monotone-SAT.  Unfortunately, this problem is known to be hard.  #SAT is #P-complete, and monotone #SAT is #P-complete as well: it is #P-complete even for monotone 2CNF clauses (i.e., type-2 constraints with only two variables).   It is also known that it is NP-hard to approximate the number of solutions.  As a result, there is unlikely to be any  efficient solution unless the number of variables and constraints is fairly small.  Of course, your problem (with a mixture of type-1 and type-2 constraints) is potentially even harder.

So what can you do, to make the best of the situation?

One approach is to code this as an instance of #SAT, and try applying some off-the-shelf #SAT solver.  You can encode type-1 constraints in SAT using the methods described at Encoding 1-out-of-n constraint for SAT solvers.

Or, you could express the constraints as a BDD and then apply model-counting methods for BDDs.  I expect this to perform worse than a #SAT solver, but you could try it.

Another approach is to use an approximation algorithm.  There are existing algorithms for approximate-#SAT, though they too will hit a limit if you have too many variables and/or clauses.


I don't see how there should be any negative consequences of this. To see why, you can "vectorize" your feature matrix so that you still have scalars for each "new" feature. That is, instead of a matrix of n features each with k values, you have a vector of length n×k with scalar features. SVMs with a mixture of categorical/integral + real components is standard.


Is there any undecidable language that is countable?

Your premise is incorrect. The set of all words, $\Sigma^*$, is countable (as long as the alphabet is countable, and we usually refer to finite alphabets anyway).

Every language is a subset of $\Sigma^*$, and thus every language is countable. In particular, there are undecidable and unrecognizable languages.


Why octal and hexadecimal? Computers use binary and humans decimals

Octal (base-8) and hexadecimal (base-16) numbers are a reasonable compromise between the binary (base-2) system computers use and decimal (base-10) system most humans use.

Computers aren't good at multiple symbols, thus base 2 (where you only have 2 symbols) is suitable for them while longer strings ,numbers with more digits, are less of a problem. Humans are very good with multiple symbols, but aren't that good in remembering longer strings.

Octal and hex use the human advantage that they can work with lots of symbols while it is still easily convertible back and forth between binary, because every hex digit represents 4 binary digits ($16=2^4$) and every octal digit represents 3 ($8=2^3$). I think hex wins over octal because it can easily be used to represent bytes and 16/32/64-bit numbers.


On FPTAS and many one parsimonious reductions

Regarding number 1: The reduction to 3-SAT in the Cook-Levin theorem is many-one and parsimonious. There's no FPTAS for 3-SAT unless $\mathcal{P=NP}$, yet any problem in $\mathcal{NP}$, including those with a FPTAS, reduce to it in the fashion you describe.
With respect to number 2: I don't know many problems with FPTAS's but I strongly suspect that, if you look through a few and the reductions that prove them to be $\mathcal{NP}$-complete, you'll quickly find a counterexample. That's because I don't see any connection between being able to count solutions and being able to approximate them.


Do undecidable languages exist in constructivist logic?

Yes. You don't need the excluded middle to derive a contradiction. In particular, diagonalisation still works.

Here is a typical diagonalisation argument by Conor McBride. This particular diagonalisation is about incompleteness, not undecidability, but the idea is the same. The important point to notice is that the contradiction he derives is not of the form "P and not P", but of the form "x = x + 1".

Of course, now you might be wondering whether constructive logic admits "x = x + 1" as a contradiction. It does. The main property of a contradiction is that anything follows from a contradiction, and using "x = x + 1", I can indeed constructively prove "x = y" for any two natural numbers.

One thing which might be different about a constructive proof is the way in which "undecidable" is defined. In classical logic, every language must either be decidable or undecidable; so "undecidable" simply means "not decidable". In constructive logic, however, "not" isn't a primitive logical operation, so we cannot express undecidability this way. Instead, we say that a language is undecidable if assuming that it is decidable leads to a contradiction.

In fact, even though "not" isn't a primitive in constructive logic, we typically define "not P" as syntactic sugar for "P can be used to construct a contradiction", so a proof by contradiction is actually the only way to constructively prove a statement of the form "not P" such as "language L is undecidable".


Understanding integer factorization is NP

The flaw in your reasoning is in considering $n$ as the size of the input.
The input is a number $n$ and its size in memory is $\lfloor \log_2(n) + 1 )\rfloor$ bits.

Thus, $O(\sqrt n)$ is not polynomial in the size of the input.

In order to be polynomial, you would need an algorithm with time complexity $O(\log^k n)$ which would correspond to a polynomial algorithm of order $k$ w.r.t. the size of the input.


Consider using Monte Carlo method for computing quadrature. It is good choice when you need not so precise approximation and dimension of the domain is large.

You definitely should provide more details.


What is meant by "solvable by non deterministic algorithm in polynomial time"

Adding to Shitikanth's answer,
a nondeterministic algorithm is one that has multiple choices in some points during its control flow. The actual choice made when the program runs is not determined by the input or values in registers, or if we are talking about Turing machines, the choice is not determined by the input value and the state; instead an arbitrary choice among the possibilities can be made in a given run of the program. Thus multiple runs of the same algorithm on the same input can result in different outputs.

The point of using a non-deterministic algorithm is that it can make certain guesses at certain points during its computation. Such algorithms are designed so that if they make the right guesses at all the choice points, then they can solve the problem at hand.

A simple example is primality testing. To decide whether a number $N$ is not prime, one simply selects non-deterministically a number $n\le\sqrt{N}$ and checks whether $N$ is divisible by $n$. For any composite number, this algorithm finds a factor of the number by making the right guess.

The polynomial time part means that if the nondeterministic algorithm makes all the right guesses, then the amount of time it takes is bounded by a polynomial.


Which classifier is more accurate for a SVM classification?

You should take a look at Feature selection and algorithms that automate this process. It's okay if you are new to ML and don't understand the entire feature selection process, just get the proper intuition and then you can use a library to automate the process.

The key idea of having a Learning algorithm is so that it can find the patterns ... the most you can do, is help him out by providing lots of (non-redundant) data and having a good preprocessing step, that usually involves stuff like feature selection, and normalization.

On a friendly note, when implementing learning algorithms, you should not try to modify your dataset just by 'looking' at it, unless you have concrete metrics that testifies it needs modifications, many a  times, it has been the case, that the learning algorithm put high bias towards features that did not appear to be even remotely 'related' to the classification process. Always try to do a feature selection step before trying any modifications on your data.


What sorting algorithm should be used for this array?

An inversion in a permutation $\pi(1),\ldots,\pi(n)$ is a pair of indices $i < j$ such that $\pi(j) < \pi(i)$. Denote the number of inversions by $I(\pi)$. In your example, $I(123546) = 1$. It is well-known that insertion sort runs in time $O(I + n)$ on a permutation of length $n$ having $I$ inversions. Due to this guarantee, insertion sort is asymptotically optimal when the number of inversions is small, $I = O(n)$.


If a machine recognizes language L, can it also recognize L*?

One problem I see with this is that a machine can only accept one language, so it might be problematic.

You are answering your own question: by definition¹, any given automaton accepts $L$ and $L^*$ if and only if $L = L^*$. This can happen -- examples include $L = \{ \varepsilon \}$ and $L = \Sigma^*$, for instance, but not as a rule.

It is not clear from your question if you understand the acceptance criterion of finite automata. The automaton has to be in a final state after reading the whole input, not in the beginning or at any time.

The language accepted by automaton $A$ is uniquely defined to be the set of words $w$ for which $A(w)$ is (an) accepting (computation).


Context free grammar for $L = \{w \text{ | }w \in \{a,b\}^*, |w|_a=|w|_b-1\}$

You can simply consider the following grammar: $$ S\to S_1 b S_1$$ where $S_1$ is the start variable of a grammar for the language of words $w$ with $|w|_a = |w|_b$. Correctness is self-explanatory.
So using the grammar you wrote, you get the following grammar:
$$ S\to T b T$$
$$ T \to aTbT| bTaT | \epsilon$$


Can parallel downloading with many ip's possible?

If the limitation is coming from the site, then it depends if the server allow you to resume partial downloads. If yes you can have two devices, one downloads the first part of the file, and the second one downloads the second part (telling the server it has already the first part).

The IP-address is given to you by your internet provider and it is unique. So you only have one and it can't be changed with software. (unless sometimes when you restart your router you can have a different one, but you can only have one at a time).

The device which downloads the second part needs to be connected to a network with a different ip-adress (for example your neighbor's Wlan).

But i don't think this is very practical.


Using A* search with different heuristic values

This problem is known as the Target Value Search Problem (TVS) and it can be succintly described as follows:

Given a graph $G(V,E)$, two nodes $s$ and $t$ ($s, t\in V)$ and a target value $T$ find a path $P$ from $s$ to $t$ such that the cost of the path is as close as possible to $T$

Of course, $s$ and $t$ might be the same node (as in your case). Note that the problem is not asking for paths (or, alternatively routes) whose cost equals exactly $T$ but that no path with a cost closer to $T$ exists. This is known as solving the Target Value Search Problem optimally. As usual, the cost of a path is defined as the sum of the costs of all edges traversed in the path.

There are different variations of this problem. All of them are described in the paper:

Carlos Linares López, Roni Stern, Ariel Felner: Target-Value Search Revisited. IJCAI 2013

The specific case that interests you most has been also investigated. You can find a short summary of results in the paper:

Carlos Linares López, Roni Stern, Ariel Felner: Solving the Target-Value Search Problem. SOCS 2014

The best solution currently known (to the best of my knowledge) consists of applying a bidirectional search. From your considerations and the notes provided by other people contributing to this thread:

You are right! The problem is that you'd like to come back to the same node but the route to traverse when going back is in the closed list. This problem is specifically addressed in the backwards search suggested in the algorithm $T^*$
David Richerby is right also! A* should traverse a state space which is exponential.

In fact, regarding the second comment. A very simple baseline for solving this problem consists of either using A$^*$ or IDA$^*$ in the path space. IDA$^*$ naturally generates paths (and thus it traverses a state space which can be exponentially large); A$^*$ can do that also if you just ignore nodes in the closed list!

In both cases, a node is never re-expanded if and only if it is an ancestor of the current node. However, it seems to me that you might find this acceptable. In that case, you are forced to expand all nodes!

Hope this helps,


Context Free Grammer and PDA (Palindrome but without characters repeating in a row)

The language in question consists of all palindromes in which no two consecutive characters are the same. For example, $aa$ is a palindrome, but doesn't belong to the language since $a$ repeats; but $aba$ is OK.

When the alphabet consists only of $a$ and $b$, you can modify the grammar $S \to aSa|bSb|a|b|\epsilon$ of palindromes to accept your language by using two nonterminals $A,B$ which generate the following languages:

$A$ generates all palindromes starting with $a$ in which no two consecutive characters are the same.
$B$ generates all palindromes starting with $b$ in which no two consecutive characters are the same.

I'll let you complete the construction, and generalize it to larger alphabets.

(In the particular case of an alphabet of size 2, the language is actually regular, but this doesn't happen when the alphabet is larger.)

The simplest way to construct a PDA is to use to use the production construction: starting with a PDA for the palindrome language and a DFA for the language of strings with no repeated characters, you can construct a PDA accepting the intersection. This is a standard construction that appears in many textbooks.


Correct cost function of multi classification problem using neural network?

The loss function you have shown is not correct.  The correct one is

$$\begin{gather*} J(\Theta) = - \frac{1}{m} \sum_{i=1}^m \sum_{k=1}^K y^{(i)}_k \log ((h_\Theta (x^{(i)}))_k)  \end{gather*}$$

The loss function has a summation over $K$ because we must take into account all possible classes.  The neural network outputs $K$ values, $h_{\Theta}(x^{(i)})$, and the loss function should depend on all $K$ of those.  There is a single loss function because we are training a single neural network, and we need exactly one loss function per neural network; if you wanted to train $K$ neural networks, then you would use $K$ loss functions.

Define $z^{(i)}$ to be the class of $x^{(i)}$ according to the training set, i.e., we take $z^{(i)}$ to be the value of $k$ such that $y^{(i)}_k=1$.  Then
the loss function above is equivalent to

$$\begin{gather*} J(\Theta) = - \frac{1}{m} \sum_{i=1}^m \log ((h_\Theta (x^{(i)}))_{z^{(i)}})  \end{gather*}$$

which does not have a summation over $K$.

I suggest reading more about the cross-entropy loss.  See, e.g., https://rdipietro.github.io/friendly-intro-to-cross-entropy-loss/

There are some errors in your notation.  The training set has points $(x^{(i)},y^{(i)})$, not $x_i,y_i$.  Here $y^{(i)}_k$ means that $y^{(i)}=k$, not that $y^{(i)}_k=k$ (the latter would be circular, defining $y^{(i)}_k$ in terms of itself).


There seem to be several levels of such grammars.

If the number of possible $y$ is finite, then each $By$ can be coded as a separate variable (like $B_y$) and your grammar is basically a "compressed" context-free grammar.

In case of an infinite number of values the $y$ can behave like stacks of symbols (which can be pushed, popped and copied to other variables) a possible formalism is that of indexed grammars.

Even more is possible with attribute grammars, where the attributes can be operated on (you can add for instance the attributes of children). Moreover the values can be passed either up or down the derivation tree (synthesized or inherited).


What does it mean " The outer level page table need not be page aligned?

Having different subtable sizes for different levels of a multilevel page table just means that a different number of bits from the virtual address will be used. The size of each level's subtable is independent of the sizes of subtables in other levels. (Yes, "outer level page tables need not have same page size as inner page table".)

Each subtable would be aligned to its size and pointers to that table in earlier levels could exploit this to elide zero bits in the address. The index would still be provided by the selection of virtual address bits. (No, outer page tables entry will not have to contain frame number + offset.)

For example, with a 47-bit virtual address space with a 50-bit physical address space (8-byte PTEs), an 8 KiB subtable with entries pointing to a 16 KiB subtable whose entries point to a 64 KiB subtable that points to 8 KiB pages:

root 8KiB subtable entry physical address
   PA[49:13] = root_pointer[39:0]
   PA[12:03] = VA[46:37] // 8 KiB subtable index
   PA[02:00] = 000       // PTE is 8-byte aligned
16 KiB subtable entry physical address
   PA[49:14] = pointer_to_16KiB_subtable[38:0]
   PA[13:03] = VA[36:26] // 16 KiB subtable index
   PA[02:00] = 000
64 KiB subtable entry physical address
   PA[49:16] = pointer_to_64KiB_subtable[36:0]
   PA[15:03] = VA[25:13] // 64 KiB subtable index
   PA[02:00] = 000
page address
   PA[49:13] = PTE_in_64KiB_subtable[36:0]
   PA[12:00] = 0_0000_0000_0000  // 8 KiB aligned page

The above example assumes a fixed size associated with each level. With variable sizes, the size of the targeted subtable would have to be included with its pointer.

The subtable size could be determined by a subtable size number such that three bits would support eight different subtable sizes or using a single extra bit with the size boundary marked by the first set bit starting from the least significant bit (e.g., aa...aa_1000 would indicate a subtable eight times larger (three bits before the set bit) than the smallest size supported). The former allows additional alignment bits of larger subtables to be used to extend the physical address space or provide more metadata; the latter saves bits (two in the example) that can be used for metadata or larger physical addresses even for the smallest subtables. Supported subtable sizes could also be dependent on the level of the subtable or even the sizes (or other metadata provided) in previous levels, though that seems inappropriately complex.


Calculating the set field of associative cache

The memory has $128$M words = $2^{7+20}$ = $2^{27}$ words. Hence it needs needs $27$ bits for address space.

Each block has $64$ words, so the block offset = $2^6$ words. So Block offset field can be represented by $6$ bits.

Number of lines in the cache = $\frac{Cache Size}{Block Size}$ =Number of blocks = $32$K blocks = $2^{5+10}$ = $2^{15}$ blocks.

Number of sets in the cache = $\frac{Number of Lines}{Set Associativity}$ = $2^{15}$ blocks / $2$ blocks per set = $2^{14}$ sets. Hence number of bits to represent set field = $14$ bits.

Number of tag bits = $27 - (14+6) = 7$ bits.


Two-Sum - Range Allowance Algorithm Design

Create a Set searchSet to store the item's that have already been examined.

Iterate through the input Array of item capacities.
2a. Find the targetCapacity for the current item: totalCapacity - itemCapacity.
2b. Generate a targetCapacitiesArray plus and minus the totalCapacity and the range allowance provided.
2c. For each capacity in targetCapacitiesArray, see if each number is contained in the searchSet, and return true if found.
2d. Else, add the itemCapacity to the searchSet.

Return false if the entire input is iterated through without finding a match.


Do basic operators of RE (Union, Kleene star and Concatenation) have properties like associativity, commutativity, distrbutivity etc.?

There are several known axiomatizations of the equational theory of Kleene algebra, see lecture notes from a course by Dexter Kozen. These axiomatizations give you a complete set of rules that can be used to deduce any identity involving regular expressions. The first ones were given in a classic paper of Salomaa, and others are also known.


Why is a heap better than a linked list for implementation of a priority queue?

It only really matters in the limit: for small sizes, the difference isn't really important.

But if you're doing a large number of each operation, $O(\log n) + O(\log n) = O(\log n)$ is asymptotically faster than $O(n) + O(1) = O(n)$.


Proof for "It is my contention that these operations include all those which are used in the computation of a number"

A contention is something that one asserts to be true. Turing's contention here is essentially the Church–Turing thesis: that Turing machines can compute everything that can be reasonably computed. This isn't something that can be proven without a definition of "reasonably computed". But, even if one were to define that term, it would be arguable that the definition wasn't a good one and that, again, isn't something that can be proven.

Turing's paper includes a lot of material about computable sequences of numbers and also a sketch proof that Turing machines and the lambda calculus are equally powerful. That constitutes quite a lot of evidence for the original contention, though I didn't notice Turing explicitly mentioning this when I skimmed the paper just now.

In particular, one might choose to define "reasonably computable" as meaning "computable by any possible physical system." Well, Turing machines can simulate every physical process we're aware of, including quantum mechanics. But, of course, we can't prove that there are no physical processes we don't know about yet that can't be simulated by Turing machines.


Grammar types constraint after adding a couple of types (and a statement involving them) to a "typeless" language

There is no way to express that constraint with a context-free grammar. (It is, almost by definition, context-sensitive since the validity of z @ … depends on the presence of underlying z.)

So you are left with two choices:

Perform the validity check as a semantic action.
Modify the lexical scanner's categorization of tokens on the fly, by recategorizing z after underlying z is seen.

Option 2 is usually called the "lexical feedback hack" and that is precisely what it is. Sometimes it cannot be conveniently avoided, but this is not one of them.


Proving Progress for STLC with Linear and Unrestricted Types

Variables can be considered as values if the evaluation strategy is call-by-value. Otherwise said, it only makes sense to substitute a variable with a value (in call-by-value). I am unable to check if that is the case in the paper you refer to since I can't access it.


In describing the tokens of a programming language using RE, it is not necessary to have the $\epsilon$ or t. Why is this?

The empty set is only needed in order to describe the empty regular language. The set of tokens of a certain type is never empty, so the empty set isn't needed.

Similarly, the empty string is only needed to describe regular languages which include the empty string. The empty string isn't a token of any type, so the empty string isn't needed.

Here are some proofs. I will use the convention in which $\emptyset$ is the emptyset and $\epsilon$ is the empty string. I will use the following inductive definition of regular expressions over an alphabet $\Sigma$:

$\emptyset$ is a regular expression.
$\epsilon$ is a regular expression.
For any $\sigma \in \Sigma$, $\sigma$ is a regular expression.
If $r$ is a regular expression then $r^*$ is a regular expression.
If $r_1,r_2$ are regular expressions then $r_1+r_2$ is a regular expression.
If $r_1,r_2$ are regular expressions then $r_1r_2$ is a regular expression.

Two regular expressions are equivalent if they generate the same language. We denote this by $\approx$. The language generated by $r$ is denoted $L[r]$.

Lemma 1. Every regular expression is either equivalent to $\emptyset$ or to a regular expression without $\emptyset$.

Corollary 1. If a regular expression doesn't generate the empty language, then it is equivalent to a regular expression without $\emptyset$.

Note that every regular expression not involving $\emptyset$ doesn't generate the empty language.

Proof. The proof is by structural induction. The base cases $\emptyset,\epsilon,\sigma$ are obvious. Consider now a regular expression $r$ constructed inductively from one or two regular expressions $r_1,r_2$, which we can assume satisfy the dichotomy in the lemma. If $r_1,r_2 \neq \emptyset$ then there is nothing to prove, so assume that at least one of them is $\emptyset$.

$r = r_1^*$: in that case $r = \emptyset^* \approx \epsilon$.
$r = r_1 + r_2$: if $r_1=r_2=\emptyset$ then $r \approx \emptyset$. If $r_1 \neq \emptyset$ and $r_2 = \emptyset$ then $r \approx r_1$.
$r = r_1r_2$: in that case $r \approx \emptyset$. $\qquad\square$

Lemma 2. Every $\emptyset$-free regular expression can be written in one of the forms $\epsilon,s,s+\epsilon$, where $s$ is $\emptyset,\epsilon$-free and $\epsilon \notin L[s]$.

Corollary 2. If $\epsilon \notin L[r]$ and $L[r] \neq \emptyset$ then $r$ is equivalent to a regular expression not involving $\emptyset,\epsilon$.

Proof. Again the proof is by structural induction. The base cases $\epsilon,\sigma$ are obvious. Let us now consider a regular expression $r$ constructed inductively from $r_1,r_2$ which are of one of the forms $s_i,s_i+\epsilon,\epsilon$, where the $s_i$ satisfy the conditions stated in the lemma.

$r = r_1^*$: If $r_1 = \epsilon$ then $r \approx \epsilon$. If $r_1 = s_1 + \epsilon$ or $r_1 = s_1$ then $r \approx s_1s_1^* + \epsilon$.
$r = r_1 + r_2$: If $r_1=r_2=\epsilon$ then $r \approx \epsilon$. If $r_1=s_1$ and $r_2 = s_2$ then $r$ is already of the required form. Otherwise $r \approx (s_1+s_2) + \epsilon$.
$r = r_1r_2$: If $r_1=r_2=\epsilon$ then $r \approx \epsilon$. If $r_1=s_1$, $r_2=s_2$ then $r$ is already of the required form. If $r_1=s_1$ and $r_2=s_2+\epsilon$ then $r \approx s_1s_2 + s_1$. Similarly, if $r_1=s_1+\epsilon$ and $r_2=s_2$ then $r \approx s_1s_2 + s_2$. Finally, if $r_1=s_1+\epsilon$ and $r_2=s_2+\epsilon$ then $r \approx (s_1s_2 + s_1 + s_2) + \epsilon$. $\qquad\square$


Implementing general vertex folding procedure in an undirected graph

Take a look at the full version of the paper: http://www.sciencedirect.com/science/article/pii/S0304397510003609. What you want is described in Proposition 2.6.