What does Lambda Calculus teach us about data? In Lambda Calculus, the distinction between data and code doesn't seem to exist. Is there something fundamental about this, or purely Lambda Calculus's thing?

Some context: as a software developer, I got used to the concept of data so much that I never considered its true nature. I'd very much appreciate any references that could help me deeper understand the role of data in computation.

You should turn the question around and ask what is not data. After all, code is just more data, is it not?

Perhaps a useful view from a programming point of view is that of a value. Say that in a programming language a value is a piece of information or data which can be stored, passed around as arguments and results of functions, they can be dynamically generated at runtime, etc.

Typical types of values are int, char, bool, various arrays of these, lists, trees, etc. In many languages functions are not values. For instance, in C you cannot pass a function as an argument or return it as a result. (Caveat: a pointer to a function is not a function!) Programming languages in which functions are values are called functional programming languages. Examples include Haskell, OCaml, SML, scheme, racket, javascript, and many others.

We can reformulate "there is no difference beween code and data" as "functions are values". So it really is a design choice as to whether code should be considered data. In functional programming languages this is the case, while in many others it is not.


Efficient algorithm to fulfil a set of coordinate constraints I have a set of labelled points and a set of distance constraints between pairs of points, consisting of a lower and upper distance bound. There is definitely an arrangement of the points in 3D space that fulfils all distance constraints.

I wish to generate arrangements of the points where all constraints are fulfilled. Any approach is allowed as long as each arrangement is independently generated from the others.

What algorithm is most suitable? Mainly in terms of efficiency.

As an extension, how would I incorporate constraints on the angle defined by three points? And on the dihedral angle defined by four points (the dihedral angle between points ABCD is the angle between the plane defined by ABC and the plane defined by BCD)?

The simplest approach (in terms of programming effort) might be to try using an existing graph layout tool.  Those solve a related problem: given a graph with distances on the edges, try to find the best layout to draw the graph on the plane.  You can treat your problem as an instance of the graph layout problem: we have one vertex per point, and for each pair of points $v,w$ with distance bounds $[\ell,u]$, we create an edge $v \to w$ with length $(\ell+u)/2$.  However, this does have some limitations: typical graph layout algorithms try to get the distances between vertices correct, but also try to avoid edges that cross each other; whereas in your case you don't care about crossings.  So, your problem might be easier.

Another possibility is to apply the ideas used for graph layout to your problem.  There are several algorithmic techniques for graph layout.  For instance, you could use a spring-based model, where you have a spring between each pair of vertices that have a distance bound, and the spring tries to keep those pair of vertices a suitable distance apart.

A third approach is to use black-box mathematical optimization.  Introduce an objective function $\Phi$ which, given a set of locations for the points, calculates a penalty value (how "badly" the arrangement violates your constraints), and then try to find an arrangement that minimizes $\Phi$.

For instance, suppose for each pair $v,w$ of points, you have a lower bound $\ell_{v,w}$ and an upper bound $u_{v,w}$.  You could define

$$\Phi(x_1,\dots,x_n) = \sum_{i,j} \frac{[||x_i - x_j||_2 - (u_{i,j} + \ell_{i,j})/2]^2}{(u_{i,j} - \ell_{i,j})^2},$$

and then use some optimization technique to find an arrangement $x_1,\dots,x_n$ that minimizes $\Phi(x_1,\dots,x_n)$.  For instance, you could try using hillclimbing, gradient descent, or other convex optimization methods.  This approach might be sensitive to the initial values for $x_1,\dots,x_n$, so you might want to repeat it multiple times with different random choices for the initial value, and take the best result.

Finally, you could try using simulated annealing.

The latter two approaches can be easily adjusted to incorporate angle constraints, simply by modifying the objective function appropriately to add a term that penalizes angles that differ from the desired value.


Converting context-free grammar to chomsky normal form I'm trying to prove that the following CFG can be converted to a CNF:

S -> aAB
A -> aAa
A -> bb
B -> a

Here below is how I've managed so far:

Step 1: add a new start state

S0 -> S
S -> aAB
A -> aAa
A -> bb
B -> a

Step 2: remove epsilon rules

There are no such rules in this CFG.

Step 3: remove non-terminal to non-terminal rules

S0 -> aAB
S -> aAB
A -> aAa
A -> bb
B -> a

Step 4: make right-hand-side not contain more than $2$ non-terminals or $1$ terminal:

S0 -> BC
S -> BC
A -> BF | EE (A -> aAa and A -> bb in one line)
B -> a
C -> AB
E -> b
F -> AB

So this is where I got confused. I have now both C and F that go to AB. If I've done this correctly that would mean that either C or F can simply be removed. Or, of course, I've done something wrong in this procedure.

You're right to be cautious, but there is nothing wrong.

A context-free grammar is in Chomsky Normal Form if and only if every rule is of the form:

A → BC,  or
A → a,   or
S → ε,   where S is the start symbol.

Consider the grammar

S → TU
S → UT
T → a
U → a

Is this a valid context-free grammar in Chomsky Normal Form?

Yes, it is.  Each rule is of one of the allowed forms.

But - you say - T and U have the exact same rules; one can be replaced with the other!

Congratulations: you have invented a normal form!  A grammar is in Byfjunarn Normal Form if and only if it has no two different nonterminals for which the rules have the exact same right hand sides.

This is clearly a normal form: in fact, normalizing grammars into this form is so easy that we do it routinely, without even thinking about it.

But the algorithm you're using to bring arbitrary grammars into Chomsky Normal Form doesn't. Why should it? Grammars can be in Chomsky Normal Form without being in Byfjunarn Normal Form; the example proves it.  Yes, it would be easy to modify the algorithm to bring grammars not only into Chomsky Normal Form, but also into Byfjunarn Normal Form.  But nobody asked it to.  Except you.

Just let the poor algorithm go about its ways.  You know what to do once it's finished :-)


How to generate snowflakes of a fixed area as challenges for the FridgeIQ puzzle? I have been presented a set of FridgeIQ by a friend and she has planted an idea in my head.

FridgeIQ is a geometric disection puzzle consisting of 16 polygonal tiles as seen in the terrible picture near the bottom of this post

The shapes of the tiles are based on a square grid with the occasional diagonal across one of the grid fields. The total area of all the tiles is 40 such grid units. Each tile is identified by a single unique letter.

In the box comes a set of challenges, each giving a subset of the tiles and a shape to create. For example one challenge is: "construct a square using the tiles BDQSYJN". Which I have done in that picture and I have some left-over tiles that were not part of that particular challenge.

In addition to the standard challenges my friend has presented me with an extra set of target shapes which finally are the point of this question. I have attached another picture showing one of them in solved state.

These extra challenges all use the complete tile set, so their total area is 40 units, and they all have fourfold mirror-symmetry. Not all of them are as simple like the one in the picture, some have a hole or holes, but they are all connected.

I shall call these shapes "snowflakes" because they in a way resemble decorative snowflakes cut out of folded paper to generate the symmetries. Especially the ones with holes.

I have been asking myself: How many such shapes with these constraints are there that can actually be made from the given tiles?

Snowflakes per se there are infinitely man. But I believe the set of connected ones with finite area made only of half-unit triangles must be finite. Propably enormous, but finite. The solveable ones are a subset of those.

What would be a good algorithm to generate them? I do not expect there to be an efficient way, nor do I believe the universe has enough time left to actually make them all. But I would love to find at least some new ones.

Here's some unfinished thoughts so far:

As a first step I have built a simple recursive-backtracking solver that reproduced my manual solutions (and found loads of alternative ones). So even if it would be terribly inefficient I could just generate snowflake-shapes at will and use my solver to check them.

I have been thinking that it would suffice to generate one eighth of the shape, one half-quadrant, with a total area of 10 units. Symmetry provides the rest. Note that the solution does not have the same symmetry when considering individual tiles, only when the complete shape is taken into account.

To generate candidate shapes I could just put 20 half-unit-triangles into the half-quadrant. Hopefully in some systematic fashion. Most of those arrangements will not be compact enough and be unsolvable, though. And without a good idea for weeding them out their numbers are absolutely intractable.

Another approach would be to just generate combinations of the tiles and check them for symmetry. Again the algorithm would have to favour symmetric layouts or the exploding combinatorics mean I can never hope to find even a single new layout.

Any ideas? Keywords for searches and/or pointers to literature are also appreciated.

Thank you very much.

SAT solvers are my favorite "big sledgehammer" to apply to this kind of problem, so let me describe how you could use a SAT solver for this problem.

Let's constrain the shape to fit within a 15x15 grid (say), and express the problem of finding a valid shape as a SAT problem.  It gets a bit messy, so you'll have to be willing to tolerate that, but the approach is powerful.   Introduce boolean variables $x_{i,j,k}$, with the intended meaning that $x_{i,j,k,r}=1$ means that we rotate tile $k$ into orientation $r$ and then put its upper-left corner in the grid cell at coordinates $(i,j)$.  We'll now write down some boolean formulas that characterize what it means for this to be a valid snowflake.

There a bunch of requirements to count as a valid snowflake; I'll sketch how to express each one as a boolean formula:

Each tile must be used exactly once.  In other words, for each $k$, exactly one of the $x_{i,j,k,r}$'s must be true; this is is a one-out-of-n constraint.  See Encoding 1-out-of-n constraint for SAT solvers for some techniques for encoding this as a boolean formula (or if you use Z3, see https://stackoverflow.com/q/43081929/781723).
The shape must be symmetric. To help check this, let's introduce auxiliary boolean variables $y_{i,j}$, with the intended meaning that $y_{i,j}=1$ means that the grid cell at coordinates $(i,j)$ is covered by some tile.  It is easy to express $y_{i,j}$ as a logical-or of a subset of the $x$'s (namely, all the $x_{i',j',k,r}$ such that placing tile $k$ in orientation $r$ at position $(i',j')$ will also cover $(i,j)$; knowing the shape of each tile, you can precompute all such $x$'s; there will be 160 of them).  Moreover, let's require this to have fourfold symmetry around the origin.  That means $y_{i,j} = y_{-i,j} = y_{i,-j} = y_{-i,-j}$ holds for all $i,j$.
No two pieces overlap.  This involves a bunch of constraints of the form $(\neg x_{i,j,k,r}) \lor (\neg x_{i',j',k',r'})$, for all $i,j,k,r,i',j',k,k',r,r'$ such that placing tile $k$ at coordinates $(i,j)$ in orientation $r$ would overlap with placing tile $k'$ at coordinates $(i',j')$ in orientation $r'$.  (This can be easily precomputed based on the shape of tiles $k$ and $k'$.)

This gives you a bunch of boolean formulas.  Write down the conjunction of all of them, and then feed it to an off-the-shelf SAT solver and ask the SAT solver to find a satisfying solution for you.  This will then correspond to a snowflake.

For implementing this stuff, I find Z3 a very convenient API to a SAT solver.

This will find one snowflake.  What if you want multiple of them?  There is a straightforward way to generate multiple solutions: after you have found one solution, you generate what's called a "blocking clause" and add it to the list of constraints (i.e., conjoin it to the formula).  The "blocking clause" just says "not that one I already know of".  For instance, if you already have a satisfying assignment that assigns values $c_{i,j,k,r}$ to each $x_{i,j,k,r}$, then the blocking clause is the formula $\lor_{i,j,k,r} (x_{i,j,k,r} \ne c_{i,j,k,r})$.  You can repeat this to obtain multiple solutions: each time you find another solution, you generate another blocking clause, add it to the formula, and apply the SAT solver again.  Some SAT solvers even have special support for incrementally adding additional constraints that is more efficient than starting the search from scratch, though that might not be necessary.

Well, that's the idea, anyway.  But here I have to confess that I lied.  There is one requirement that I've left out so far: connectivity.  You said you want each snowflake to be connected.  That's messier to implement in a boolean formula, though also possible.  The crude hack is to generate many candidate snowflakes as above, check each for connectivity, and keep only the connected ones.  However, this might not work very well.  So, let me describe how to encode the connectivity constraint in SAT.  Beware; it gets messy, so hold onto your hat.

The shape must be connected. The main idea will be to pick a particular grid cell, require that it be present, and require that every other covered grid cell be connected to it.  Let's say we require that the grid cell at the origin $(0,0)$ be covered.  Then we can introduce auxiliary variables $z_{i,j,s}$, with the intended meaning that $z_{i,j,s}=1$ means that grid cell $(i,j)$ can be reached by starting at the origin and then taking $s$ steps across adjacent covered grid cells.  This constraint can be encoded in SAT by noting

$$z_{i,j,s} = y_{i,j} \land (z_{i-1,j,s-1} \lor z_{i,j-1,s-1} \lor z_{i+1,j,s-1} \lor z_{i,j+1,s-1}).$$

We'll adopt the convention that $z_{i,j,0}=1$, and if $(i,j)$ is outside of the 15x15 bounding box then by convention $y_{i,j,s}=z_{i,j,s}=0$  (we don't introduce extra variables for that, we just replace those terms with "false").

Finally, for each $i,j$, we add the constraint that $y_{i,j} \implies \lor_{s=0}^{39} z_{i,j,s}$.  This ensures that every covered cell is reachable.  (Note that if it is reachable, it is reachable in at most 39 steps, so we only need to go up that high.  In practice, I suspect that 19 or even 9 are probably large enough.)

That ensures connectivity.  However, there's a potential catch: this requires everything to be connected to the origin, so it only generates snowflakes that cover the origin.  We also want snowflakes that have a hole at the origin.  I think you can fix this by iterating over all possibilities for the 'anchor point' (one grid cell that you'll require to be covered and require everything to be connected to), and solving the SAT instance for each possible anchor point.  (To avoid duplicates, if you like you can add additional constraints to ensure disjointness of solutions.  For instance, solve one SAT system where you require $(0,0)$ to be covered and everything to be connected to $(0,0)$; solve another where you require $(0,1)$ to be covered and everything to be connected to $(0,1)$ and you require $(0,0)$ to be uncovered; another where you require $(0,2)$ to be covered and everything to be connected to $(0,2)$ and you require $(0,0)$ and $(0,1)$ to be uncovered; and so on.)

Lastly, in the above I assumed that your shapes are collections of squares, i.e., they either completely cover a grid cell or don't touch it at all.  Of course, this isn't valid for your tiles, due to those diagonal pieces.  So, I suggest that after breaking down the 15x15 region into 225 small squares, you break down each square into four triangles.  Then, instead of using the $y$'s to record which grid squares are covered, you'll need to adjust the definition of the $y$'s and the above formulas to record which triangles are covered.  Everything should go through with some straightforward adjustments.

Phew.  I told you it would get messy.  The basic idea here is that we are taking each of the conditions for a shape to count as a valid snowflake, writing them down in boolean logic, and then letting the SAT solver find solutions that meet all of those requirements.  SAT solvers today are amazing and contain clever and powerful strategies to automatically find solutions that meet your requirements.  Researchers have spent decades coming up with better algorithms and improving the engineering of the tools; you can't hope to duplicate that, so rather than trying, you can build on all of their work and apply it to your specific situation.


Tower Of Hanoi Time Calculation I have been trying this Towers of Hanoi question since last week but never able to come with the right approach towards the solution.

The setup is the standard Towers of Hanoi, except that moving the smallest disk costs one unit of time, moving the second-smallest disk takes two units of time and so on.

What is the total minimum time solving towerOfHanoi?

Starting from this system:

$$ \begin{cases} T(1) = 1 \\
 T(n) = 2T(n-1) + n \end{cases} $$

To use repertoire method to solve the system, we'll generalize it as this:

$$ \begin{cases} T(1) = \alpha \\
 T(n) = 2T(n-1) + \beta n + \gamma \end{cases} \tag 0 $$

The result must look like this:

$$ T(n) = A(n) \alpha + B(n) \beta + C(n) \gamma $$

I. Let's try T(n) = 1
$$ \begin{cases} T(1) = 1 = \alpha \\
 T(n) = 1 = 2T(n-1) + \beta n + \gamma = 2 \cdot 1 + \beta n + \gamma \end{cases}$$
Thus:
$$ (\alpha, \beta, \gamma) = (1, 0, -1) $$
Which means that
$$ T(n) = A(n) - C(n) = 1  \tag 1 $$.

II. Now try T(n) = n
$$ \begin{cases} T(1) = 1 = \alpha \\
 T(n) = n = 2T(n-1) + \beta n + \gamma = 2n - 2 + \beta n + \gamma \end{cases}$$
Thus:
$$ (\alpha, \beta, \gamma) = (1, -1, 2) $$
Which means that
$$ T(n) = A(n) - B(n) + 2 C(n) = n  \tag 2 $$.

III. Also, for $ (\alpha, \beta, \gamma) = (1, 0, 0) $:
$$\begin{cases} T(1) = 1 \\
T(n) = 2T(n-1) = 2^n \end{cases}$$
Which means that
$$ T(n) = A(n) = 2^{n-1}  \tag 3$$.

From (1) and (3):
$$ 2^{n-1} - 1 = C(n) $$

Now from this equation and (2):
$$2^{n-1} - B(n) + 2 (2^{n-1} -1) = n$$
$$2^{n-1} - n + 2^n -2 = B(n) $$

Final result for $ (\alpha, \beta, \gamma) = (1, 1, 0) $:
$$ T(n) = A(n) + B(n) $$
$$ T(n) = 2^{n-1} + 2^{n-1} - n + 2^n -2 $$
$$ T(n) = 2^{n+1} - n - 2$$


Proving that Turing Machine M runs in time $O(2^{dn})$ I'm trying to solve this question in order to review for my exam, and this one has got me a bit stumped. From the looks of it, it seems like a fairly straight-forward question, but I can't figure out what steps to begin with.

Let $M$ be a linear-space Turing machine consisting of a single tape. We say $M$ is a linear-space Turing machine if M halts on every input, and if there are constants $c$ and $n_{0}$ such that for all inputs $x\in \Sigma^{\ast}$ of length $n\geq n_{0}$, $M$ running on $x$ visits at most $c\cdot n$ tape squares.
Prove that for some constant $d$, $M$ runs in time $O(2^{dn})$.

I have a couple of ideas to begin with. First, my intuition tells me that I just have to build an algorithm that runs according to those rules and accepts/rejects in time $O(2^{dn})$. Secondly, theres a hint that tells me to "consider the number of configurations", however, I'm not sure on how to incorporate that.
Thank you in advance for any help.

Your intuition is problematic, for the following reason: you are given a specific machine $M$, not a language. Therefore, if you describe an algorithm that runs in $O(2^{dn})$ and decides the same language, you effectively prove that $L(M)$ is decidable in $O(2^{dn})$, but that does not imply that $M$ itself runs in that time frame.

As the hint suggests, consider the number of possible configurations of $M$: recall that a configuration of a TM consists of the contents of the tape, the position of the head, and the state. Given that the alphabet of the machine is fixed, and that the tape used in the run of $M$ on $x$ is of size $c\cdot |x|$, try to bound the number of possible configurations (expressed in the size of $M$ and $|x|$)

Now, recall that $M$ always halts. What does that mean about the sequence of configurations it goes through in its run on $x$?

Combining these two observations you will get the answer. Comment if you need more hints.


Is this counting language context free? Let $\Sigma = \left\{ 0,\,1,\,2\right\}$. I want to look at the following language: $L=\left\{ xyz \, | \,  |x|_0 + |z|_0 = |x|_2 +|z|_2 \wedge y \in \left\{ 1 \right\} ^{*} \right\}$.

I would like to prove or disprove $L$ being context-free

I'm having a very hard time to construct a context-free grammer for $L$, so I attempted to build a non-deterministic PDA.

My attempt goes in the direction of: If i want to sum the zeroes from $x$ and $z$, and fron this sum to substract the  sum of $2$s from both $x$ and $z$, I can do it differently:

I can count the number of $0$s from $x$ by inserting a #, then remove one # for every $2$ I count, if negative I'll push @ . Then I will do the same with $z$.

The points are:

I'm not sure if this idea will work?
If this language is CFL, I have no idea how to begin constructing a CFL grammer for it?

Your idea is correct. After all, $|x|_0 + |z|_0 = |x|_2 + |z|_2$ if and only if $|x|_0 + |z|_0 - (|x|_2 + |z|_2) = |xz|_0 - |xz|_2 = 0$. Note, however, you must (ab)use nondeterminism correctly so as to guess where $y$ is so as to know what belongs to $x$ and what to $z$.

Producing a CFG from a PDA is, unfortunately, not easy in general. There are cases in which, given a CFL, it is (much) easier to construct one than it is to construct the other. Having experience in these kind of exercises might give you a sudden flash of inspiration; failing that, you can always resort to the standard construction.
In this particular case, your "flash of inspiration" could have come from taking a closer look at the equation on the number of zeroes and two's. The idea is the equation holds for the empty word and we can produce symbols while conserving it; that is, for example, if you generate a zero for $x$ (i.e., $|x|_0$ is increased by one), then you also want to generate a $2$ somewhere so the equation still holds. Hence, a CFG with the following set of productions suffices:
$$\begin{align*}
S &\to X_0 S X_2 \mid X_2 S X_0 \mid X S X \mid Y \mid \varepsilon, \\
X_0 &\to X 0 \mid 0 X, \\
X_2 &\to X 2 \mid 2 X, \\
X &\to 0 X 2 \mid 2 X 0 \mid 1 X \mid X 1 \mid \varepsilon, \\
Y &\to 1 Y \mid \varepsilon
\end{align*}$$
A brief reasoning to make sure every word $w = x y z \in L$ is generated: The ones in $x$ and $z$ are generated by $X$, so we can exclude them. Further, any neighboring pair $02$ or $20$ may be generated by $X$ (and we include $X$ everywhere it is possible for such a pair to appear). Removing all such pairs, the only possible word left is of the form $x = 0^n$ and $z = 2^n$ or $x = 2^n$ and $z = 0^n$, and we can generate $w$ by using the appropriate rules for $S$ containing $X_0$ and $X_2$.


Are time complexity of followng codes equivalent? Implemented is done in C++.

Supposing we have defined a class T with no restrictions and three functions cond, next and f returning bool, void and anything respectively, are

for(T k = T(); cond(); next())
    f();

and

{
T k = T();

while(cond()) {
    f();
    next();
}
}

So, I would like know that time complexity of the following algorithms are same?

I'm not familiar with C++ but it looks like that both codes are equivalent, for loop and while loop has the same power.

In your examples, in both cases you first you initial the variable k, and  the loop doesn't stop as coud() condition holds, inside the loop there is a call to f(); method, and finally to next();.


Random generator considerations in the design of randomized algorithms It is well known that the efficiency of randomized algorithms (at least those in BPP and RP) depends on the quality of the random generator used. Perfect random sources are unavailable in practice. Although it is proved that for all $0 < \delta \leq \frac{1}{2}$ the identities BPP = $\delta$-BPP and RP = $\delta$-RP hold, it is not true that the original algorithm used for a prefect random source can be directly used also for a $\delta$-random source. Instead, some simulation has to be done. This simulation is polynomial, but the resulting algorithm is not so efficient as the original one.

Moreover, as to my knowledge, the random generators used in practice are usually not even $\delta$-sources, but pseudo-random sources that can behave extremely badly in the worst case.

According to Wikipedia:

  In common practice, randomized algorithms are approximated using a pseudorandom number generator in place of a true source of random bits; such an implementation may deviate from the expected theoretical behavior.

In fact, the implementations of randomized algorithms that I have seen up to now were mere implementations of the algorithms for perfect random sources run with the use of pseudorandom sources.

My question is, if there is any justification of this common practice. Is there any reason to expect that in most cases the algorithm will return a correct result (with the probabilities as in BPP resp. RP)? How can the "approximation" mentioned in the quotation from Wikipedia be formalized? Can the deviation mentioned be somehow estimated, at least in the expected case? Is it possible to argue that a Monte-Carlo randomized algorithm run on a perfect random source will turn into a well-behaved stochastic algorithm when run on a pseudorandom source? Or are there any other similar considerations?

It is well known that the efficiency of randomized algorithms (at least those in BPP and RP) depends on the quality of the random generator used. I have to disagree. What a good pseudurandom sequence ensemble gives you is a guarantee on the performance of the algorithm run a random sequence from the ensemble, compared to a trully random sequence. If you don't have such a guarantee, you can't conclude that the algorithm will work poorly - you just don't know.

Is there any justification of this common practice? It works.

Is it possible to argue that a Monte-Carlo randomized algorithm run on a perfect random source will turn into a well-behaved stochastic algorithm when run on a pseudorandom source? Complexity theory suffers from two shortcomings. The first one is that it is very hard to prove anything (for example, P vs. NP is open). The second one is that it is mostly concerned with worst-case analysis. Put together, these two limitations rule out complexity theory as a good model for the behavior of algorithms in practice.


multiple sequence alignment using HMM and simulated annealing Can anyone help me with Multiple Sequence Alignment (MSA) using Hidden Markov Model (HMM) by giving an example or a reference except these 2 references:

1-Eddy, Sea.R., et al.Multiple alignment using hidden markov models, 2-Boer Jonas, Multiple alignment using hidden Markov models, Seminar Hot Topics in Bioinformatics.

I know that there are 3 states: match, deletion and insertion and I know the emission probabilities and transitions probabilities can be learned by viterbi algorithm but what is vague is that if I want to do multiple alignment I need to have HMM and if I want to have HMM I need to have aligned sequences but we know that sequences are unaligned and also with simulated annealing we can Enter randomness to the model and have better solutions and also this algorithm is different with E-M algorithm and I have another question how many states our model of HMM for this problem should have at the first step, does the number of states change during the time of convergence or it is fixed from the first??

If anybody can help me to understand what really happens in this MSA with HMM I'll appreciate.

I should explain that there have been found more sequences of DNA,RNA and protein but there are less information about structures and functions of each protein so we do MSA to understand the similarities between sequences and find out whether they are homologous (have a same ancestor) or not and find out the unknown structure and functions of sequences.

part of this question already has an answer in  multiple sequence alignment using HMM and simulated annealing
and about the number of states in HMM it is a challenge yet.


When would one use equational dynamics? I'm trying to sort out in my mind the different ways of assigning semantics to a programming language. There are two main methodologies: operational semantics and denotational semantics (I asked a previous question on the relationship between the two).

It seems to me that an operational semantics is the same as defining a dynamics for the language - that is, defining how programs are evaluated. I know two different ways of doing this: equational and structural.

A structural dynamics defines evaluation via a system of transition rules (I believe beta reductions are the canonical example). An equational dynamics only specifies reductions indirectly, by defining when one expression is equal to another. (I'm going through the trouble of defining these terms because I am uncertain how standard the terminology is).

But I can't figure out why both systems are needed. I personally prefer structural dynamics, but it feels very subjective. What are the advantages and disadvantages between the two systems?

What you call "equational dynamics" is not actually an operational semantics, it's an equational theory. As you note, equations by themselves do not tell us how to run programs. However, they are needed because we want to express the idea of program equivalence. For instance, an optimizer replaces a piece of code with an equivalent piece of code (which is hopefully more efficient). But what does "equivalent" mean here?

We can use observational equivalence: two programs are equivalent if we can make exactly the same observations about them. In other words, they behave the same way. This kind of equivalence is defined using operational semantics.

An alternative is to start by prescribing equivalences. We want certain programs to be equivalent, usually because we have some mathematical understanding of how things are supposed to work. For instance $\beta$-reduction $(\lambda x . e_1) e_2 = e_1[e_2/x]$ is an equation which expresses the mathematical meaning of $\lambda$-abstraction. In practice is is often easier to come up with equations than with an operational semantics. (For instance, when Matija Pretnar and I worked on Eff, we knew exactly what the equations were because we were actullay trying to turn equational theories into a programming language. Also, when Alonzo Church came up with the $\lambda$-calculus he wrote down equations that expressed the mathematical properties of functions and function application.) The problem then is to find an operational semantics which respects the equations, but at the same time does not introduce (too many) observational equivalences that are not implied by the equations.


Can Turing Machines decide on computability? Can a Turing Machine decide whether an arbitrary real number is computable or not? Does this even follow from the solution of the Halting problem? If not, who proved it?

A real number cannot be input into a Turing machine, since it is an infinite object. There are various models for providing a Turing machine with oracle access to real numbers, but these are by definition computable.

You could imagine a Turing machine given a ZFC definition of a real number, and in that case it's undecidable. For example, given a Turing machine $T$, you could define a number $x$ as follows: if $T$ doesn't halt in $n$ steps then the $n$th bit of $x$ is zero. Otherwise, it is the $n$th bit of Chaitin's constant. So $x$ is computable if and only if $T$ never halts.


Proof that "local" minimum spanning tree is "global" minimum spanning tree I'm trying to understand a proof from the book "Graph Theory with Application to Engineering & Computer Science" by Narsingh Deo.
The chapter is about trees in non oriented graphs.
A bit of terminology so that you can understand the theorem and the beginning of the proof from the book:
The author calls minimum spanning trees, shortest spanning trees.
The author calls a branch of a spanning tree any edge of the tree.
A chord of a spanning tree is any edge of the underlying graph that is not in the tree.
A fundamental circuit associated to a spanning tree is a circuit formed by adding one of its chords to a spanning tree (for the author a "circuit" is a closed path, there is no repetition of vertices, it's what most other sources I've read call a cycle). So, a fundamental circuit associated to a spanning tree is a actually a cycle formed by adding one of its chords to a spanning tree.
The distance between two spanning trees $S$ and $T$ of the same graph is (regarding $S$ and $T$ as sets of edges), is $|S\setminus T|$ (which happens to be equal to $|T\setminus S|$).
There's a step in the proof of Theorem 3-16 that I don't understand.
Theorem 3-16:
A spanning tree T (of a given weighted connected Graph G) is a shortest spanning tree (of G) if and only if there exists no other spanning tree (of G) at a distance of one from T whose weight  is smaller than that of T
Proof:
Let $T_1$ be a spanning tree in G satisfying the hypothesis of the theorem (i.e. there is no spanning tree at a distance of one from $T_1$ which is shorter than $T_1$). The proof will be completed by showing that if $T_2$ is a shortest spanning tree (different from $T_1$) in G, the weight of $T_1$ will also be equal to that of $T_2$. Let $T_2$ be a shortest spanning tree in G. Clearly, $T_2$ must also satisfy the hypothesis of the theorem (otherwise there will be a spanning tree shorter than $T_2$ at a distance of one from $T_2$, violating the assumption that $T_2$ is shortest).
Consider an edge $e$ in $T_2$ which is not in $T_1$. Adding $e$ to $T_1$ forms a fundamental circuit with branches in $T_1$. Some, but not all, of the branches in $T_1$ that form the fundamental circuit with $e$ may also be in $T_2$; each of these branches in $T_1$ has a weight smaller than or equal to that of $e$, because of the assumption on $T_1$. Amongst all those edges in this circuit which are not in $T_2$ at least one, say $b_j$, must form some fundamental circuit (with respect to $T_2$) containing $e$.
I'm stuck at the last sentence I just quoted:
"Amongst all those edges in this circuit which are not in $T_2$ at least one, say $b_j$, must form some fundamental circuit (with respect to $T_2$) containing $e$."
I don't see why among those cycles, there should necessarily be one that contains $e$. Why is that?

If we remove $e = (x,y)$ from $T_2$, then it breaks into two connected components, say $T_{2,x},T_{2,y}$. There is a unique path in $T_1$ from $x$ to $y$, which together with $e$ forms a fundamental cycle of $T_1$. The path starts at $T_{2,x}$ and ends at $T_{2,y}$, hence at some point it crosses between the two. Adding the corresponding edge to $T_2$ would result in a fundamental cycle containing $e$.


How is ARC consistency un-done after a recursive failure condition? Taking this as an example:

bool SolveSudoku(int grid[N][N])
{
    int row, col;

    // If there is no unassigned location, we are done
    if (!FindUnassignedLocation(grid, row, col))
       return true; // success!

    // consider digits 1 to 9
    for (int num = 1; num <= 9; num++)
    {
        // if looks promising
        if (isSafe(grid, row, col, num))
        {
            // make tentative assignment
            grid[row][col] = num;

            //RUN ARC CONSISTENCY HERE ......?

            // return, if success, yay!
            if (SolveSudoku(grid))
                return true;

            // failure, unmake & try again
            grid[row][col] = UNASSIGNED;

            ////REMOVE ARC CONSISTENCY HERE ......?
        }
    }
    return false; // this triggers backtracking
}

Given the backtracking algorithm with CSP's, I would like to add ARC consistency to make it smarter.

For example:

  "When we want to assign the digit 'd' to cell s1, we use assign(cells,
  s, d).  ...but I also want to eliminate this possibility from its
  peers  (like Forward Checking does, tell me something new!). If the
  elimination causes one (or some) of the peers going down to only one
  possibility, which we call d2, we want to assign d2 to it, and by
  doing that,  eliminate d2 from all of its peer's peers, and that could
  make another chain  reaction. This chain reaction is simply called
  constraint propagation:  placing a constraint on one cell can cause
  further constraints to be placed on  other cells."

Can the process of arc propagation end up leading to a solution by
itself or even a false solution? What is done in those cases?
In the likely event the next recursive call on the next variable returns false (no values worked out for that variable), how do I
undo all the changes the arc consistency did?

The obvious answer is: take a snapshot (checkpoint) of your state before applying the arc consistency inferences; recursively explore that option; and then if it is a failure, restore the state back to your snapshot.

Whether this is efficient depends upon the size of the state and the amount of work done during the recursive call.  For this particular application (Sudoko), I suspect you don't have much state, so I expect this will be a perfectly reasonable solution.

In more complex situations, you can use more sophisticated data structures that support undo/rollback.  For instance, persistent data structures are one way to make rolling back to a prior version faster, in some cases.  Partial persistence is enough; you don't need full persistence or confluent persistence.  However, for simple cases like this one, the overhead of persistence might outweigh any gain from avoiding copying the state.

If you want us to recommend a more efficient solution than the naive copying approach, you'll need to specify in greater detail what sort of data structures you need for this application (e.g., for storing the set of constraints).


Find a simple path visiting all marked vertices Let $G = (V, E)$ be a connected graph and let $M\subseteq V$. We say that a vertex $v$ is marked if $v\in M$.  The problem is to find a simple path in $G$ that visits the maximum possible number of marked vertices. The associated decision problem is: is there a simple path that visits every $v\in M$?

The problem is obviously more general than the problem of finding a Hamiltonian path in an arbitrary graph, so it is NP-hard.

I see no obvious strategy; one can't simply disregard the unmarked vertices, since they (and their incident edges) may be part of the optimal path.  Indeed, omitting them may disconnect the graph completely.

My questions:

Does this problem have a well-known name?
Are there any good approximation algorithms, heuristics, or simple reductions to problems I might know more about?
Where can I find this problem discussed in the literature?

This problem is close to Steiner tree problem, just by two restriction:

Instead of tree we have path.
Is not necessary to have shortest path which contains required node.

There is a recent work1 on similar topic, the only difference with your problem statement is they are looking for shortest path which contains all required vertices. They name it Steiner Path problem.

1:
Shanti Swaroop Moharana, Ankit Joshi, and Swapnil Vijay. Steiner path
for trees. International Journal of Computer Applications, August
2013. Published by Foundation of Computer Science, New York, USA. (doi)


Number of possible search paths when searching in BST I have the following question, but don't have answer for this. I would appreciate if my method is correct :

Q. When searching for the key value 60 in a binary search tree, nodes containing the key values 10, 20, 40, 50, 70, 80, 90 are traversed, not necessarily in the order given. How many different orders are possible in which these key values can occur on the search path from the root node containing the value 60?

(A) 35 (B) 64 (C) 128 (D) 5040

From the question, I understand that all nodes given have to be included in traversal and ultimately we have to reach the key, 60. For example, one such combination would be :

10, 20, 40, 50, 90, 80, 70, 60.

Since we have to traverse all nodes given above, we have to start either with 10 or 90. If we start with 20, we will not reach 10 (since 60 > 20 and we will traverse right subtree of 20)

Similarly, we cannot start with 80, because we will not be able to reach 90, since 80>60, we will traverse in left sub tree of 80 & thus not reaching 90.

Lets take 10. The remaining nodes are 20, 40, 50, 70, 80, 90. Next node could be either 20 or 90. We cannot take other nodes for same earlier mentioned reason.

If we consider similarly, at each level we are having two choices. Since there are 7 nodes, two choices for first 6 & no choice for last one. So there are totally

$2*2*2*2*2*2*1$ permutations = $2^6$ = $64$

Is this a correct answer?
If not, whats the better approach?
I would like to generalize. If $n$ nodes are given then total possible search paths would be $2^{n-1}$

If looking for the key 60 we reach a number $K$ less than 60, we go right (where the larger numbers are) and we never meet numbers less than $K$. That argument can be repeated, so the numbers 10, 20, 40, 50 must occur along the search in that order.

Similarly, if looking for the key 60 we reach a number $K$ larger than 60, we go leftt (where the smaller numbers are) and we never meet numbers larger than $K$. Hence the numbers 90, 80, 70 must occur along the search in that order.

The sequences 10, 20, 30, 40, 50 and 90, 80, 70 can then be shuffled together, as long as their subsequences keep intact. Thus we can have 10, 20, 40, 50, 90, 80, 70, but also 10, 20, 90, 30, 40, 80, 70, 50.

We now can compute the number, choosing the position of large and small numbers. See the comment by Aryabhata. We have two sequences of 4 and 3 numbers. How many ways can I shuffle them? In the final 7 positions I have to choose 3 positions for the larger numbers (and the remaining 4 for the smaller numbers). I can choose these in $7 \choose 3$ ways. After fixing these positions we know the full sequence. E.g., my first example has positions S S S S L L L the second has S S L S L L S.

You ask for a generalization. Always the $x$ numbers less than the number found, and the $y$ numbers larger are fixed in their relative order. The smaller numbers must go up, the arger numbers must go down. The number is then $x+y \choose y$.

PS (edited). Thanks to Gilles, who noted that 30 is not in the question.


Reference introductory books or articles to Game Semantics Where can I find introductory books, articles, notes or slides on Game Semantics?

I have searched a lot on the internet but I'm not satisfied by the material I found. It either is too informal, or it assumes too much knowledge of/attitude to other kind of semantics, and it's hard to follow for a beginner.

Ideally the material shouldn't have any prerequisites, except a little of game theory and few concepts of semantics.

Examples of the material that I've found are:

Notes on Game Semantics: These are quite good, but they lack a bit of formalism at the beginning and I find some explanations or examples difficult to follow.
Tutorial on Game Semantics: Slides; they lack oral explanations.

I know three introductions that may satisfy your criteria. All of them will use some Category Theory, but the first one (by Jürjens)  is actually quite light on that side -- he actually defines what categories and morphisms are in the context of game semantics, on page 111 (11th page of the article). You may want to read this one first, and then the others.

Games in the Semantics of Programming Languages -- an elementary introduction by Jan Jürjens.
Game Semantics by Abramsky and McCusker.
Semantics of Interaction (arXiv:1312.0121v1 [cs.LO]) by Abramsky.


Does a Hadamard Gate have uses outside of pure and evenly mixed states? The standard usage cases for the Hadamard gate seem to be passing a pure $|0\rangle$ or $|1\rangle$ state in to get an even amplitude (probability) mixed state which has either matching or mismatching phase.

The other use of course, is to take such an even amplitude mixed state, pass it through the Hadamard gate, and get back a pure $|0\rangle$ or $|1\rangle$ state.

This of course scales up to multiple qubits.

Are there any other usage cases for the Hadamard Gate?  I'm wondering if say you had an uneven amplitude qubit, would passing it through a Hadamard Gate do anything useful?  Or the same question with multiple qubits, that had varying amplitudes of states.

Thanks!

I don't know of any explicit use of the Hadamard gate in circuits other than to introduce or take away superposition, but here are some interesting applications:

The Hadamard gate is the single-qubit version of the Fourier Transform*, and the Fourier Transform is very useful.
Instead of using the Hadamard at the end of a computation to get back the original basis, you can measure the system in the Hadamard basis instead of the standard basis.
The set of $\{\text{CNOT}, \text{Hadamard}, \text{rotation by 45 degrees}, \frac{\pi}{8}\text{-gate} \}$ is a universal quantum gate set. That is to say, any quantum gate can be approximated arbitrarily well by repeated application of gates from this set.
If you prepend and append two Hadamard gates to a CNOT gate, you reverse the role of control bit and target bit.

*Demonstration: The quantum Fourier transform is defined as follows. Take a system of $n$ particles in the standard basis, and put it in state $|k\rangle, 0 \leq k \leq 2^n-1$. Then applying the Fourier Transform $F$ yields a big superposition:

$$ F|k\rangle = \sum_{u=0}^{2^n-1}e^{i2\pi\frac{u\cdot k}{2^n-1}}|u\rangle $$

Take $n=1$ and $k\in\{0,1\}$, and you see that $F|0\rangle = |+\rangle$ and $F|1\rangle=|-\rangle$. As you can see, it is performs exactly the same transformation as a Hadamard gate. Moreover, for any number of qubits $n$, the Fourier still behaves as the Hadamard only for the state $0$, on which it acts as follows:

$$ F|0\rangle_n = \sum_{u=0}^{2^n-1}e^{i2\pi\frac{u\cdot 0}{2^n-1}}|u\rangle_n = \sum_{u=0}^{2^n-1}e^{0}|u\rangle_n = \sum_{u=0}^{2^n-1}|u\rangle_n $$

I have not normalized my states in these examples, but you should definitely do so on an exam.


Why are finite automata defined as ordered $n-tuples$ and not as sets? First off, I should mention that I am a new contributor on this site and as such, please bear with me if this has been asked and answered before. I searched to the best of my ability to find similar questions and didn't find any.

The Question

Consider the definition of a deterministic finite automaton given below:

  A deterministic finite automaton $M$ is an ordered $5$-tuple $
 (Q,\Sigma, \delta, q_0, F)$ where:

  $Q$ is the set of input states;
  $\Sigma$ is a finite set of input symbols;
  $\delta\colon Q \times \Sigma \to Q$ is the transition function;
  $q_0$ is the initial state
  $F$ is the set of final states

My main question is, would it be inaccurate to define $M$ as the set $ \{Q,\Sigma, \delta, q_0, F\}$ of five elements?
I arrived at this question when wondering if a DFA must necessarily be ordered since n-tuples are, by definition, ordered. In other words, the tuple $(Q,\Sigma, \delta, q_0, F)$ is, by definition, different from $(Q,\Sigma, \delta, F,q_0)$. But what if we define its elements the same way as given in the definition above? Will it be a DFA? If it will, then can a DFA be instead defined as a set?

A DFA fundamentally has five components, and those components aren't interchangeable. You can't freely swap the set of final states and the set of input symbols, for example, without just making a mess of everything.

The standard representation just says "those five things make a DFA". In other words, a DFA is just those five things in sequence, nothing more or less. The order matters, not because the input symbols have to come before final states, but because you need to know which is which and not get that wrong. Without an order, you wouldn't know that.

But, if you wanted to represent a DFA as some sort of dictionary instead, like $\{``Q":\{\ldots\}, ``\Sigma":\{\ldots\},\ldots\}$, that would be perfectly fine. Or a list of pairs, or really any way you like that makes it clear what's what.


Solving recurrences by substitution I'm going through Cormen et al.'s Introduction to Algorithms and I am a little thrown off by some of the subtleties of solving recurrences with the substitution method.  Given the recurrence:

$$ T(n) = T(\lfloor n/2 \rfloor) + T(\lceil n/2 \rceil) + 1, $$

We guess that the solution is $T(n) = O(n)$. Thus we try to show that $T(n) \le cn$. By substituting our guess, we are left with,

$T(n) = cn + 1$, which is not $\le cn$.

Makes sense. But then in the next paragraph, he writes that if we guess for $T(n) = O(n^2)$,  we can make the solution work. However, wouldn't the solution still be off by a constant of 1, since:

$$T(n) = O(n^2) = 2c(n/2)^2 + 1?$$

Or am I not substituting correctly for $O(n^2)$? Seems like I'm missing something trivial about this.

Assuming for simplicity that $n$ is even, if we guess that $T(n) \leq C^2n$ then we can prove our guess by induction (for powers of 2) for an appropriate value of $C$ since
$$
T(n) = 2T(n/2) + 1 \leq C(n/2)^2 + 1 = \frac{C}{4} n^2 + 1
$$
is smaller than $Cn^2$ as long as $C \geq 4/3$ (assuming $n \ge 1$).


Proving a solution for the $n$-Queens Puzzle Given an $n$ x $n$ board, assume that $n \geq 5$ and that $n$ is not divisible by $2$ or $3$. Prove that the following positioning of $n$ queens $Q_0, Q_2, ..., Q_{n-1}$ works, i.e no two queens threaten each other:
For $0 \leq i \leq n-1$ we position the queen $Q_i$ on the field $(i, 2i \text{ } \pmod n)$.
Here we're using the ($x$-coordinate, $y$-coordinate) coordinate system, where $x$ describes the horizontal position, and $y$ the vertical. For example, in the formula above, $x$ would be $i$, and $y$ would be $2i \pmod n$.

My idea was to prove by contradiction and break up each case on how the queens are positioned to not threaten each other (horizontally, vertically and diagonally), but I can't see what follows. Can someone offer their thoughts or point me in the right direction?

Consider $i < j$ between 0 and $ n-1$. Of course, the first coordinate can’t be same for any two queens, hence they aren’t in same row.

Now, suppose, for the sake of contradiction, they lie on the same column. Then, $2(i-j) = nk$  for some natural $k$. Now, as n doesn’t contain 2 as it’s divisor, $k$ must be even. So, either $k$ is 0, which is not possible because that will contradict our assumption that $i$ and $j$ are not equal, or $k\geq 2$. In the latter case, $LHS = 2(i-j) < 2(n-1) < 2n \leq nk$, and hence $LHS \ne RHS$. Hence, we conclude that our assumption must have been incorrect and two queens positioned in this manner can’t lie on same column.

You still need to figure out the diagonal case.


Exact definition of average time complexity? Now I'm from a mathematical background, and I found CS people's definition of average time complexity a bit... confusing, to say the least.
Here is a definition that I feel comfortable with:
Consider a set $A$ of finite elements, with each $a\in A$ indicating individual input cases. There exists a function $T(a)\mapsto t\in\mathbb{N}$, i.e., running time for individual cases. Now we can define the average running time of input set to be simply
$$\overline{T}(A)=\frac{\sum\limits_{a\in A}T(a)}{\#A},$$
where $\#A$ denotes number of elements in $A$. For example, in QuickSort, we let $A_n=\{\text{array of $n$ unsorted integers}\}=\mathbb{Z}^n$.
But now we have to do an additional step. An integer can take on an infinite set of values, so we naturally consider the memory constraint and instead confine each integer $i$ to be $L\le i\le U$. Now $\#(A_n)=(U-L+1)^n$, and we have a clearly defined $T(\cdot)$, and we can try to figure out $\overline{T}(A_n)$, although this is a very tough combinatorics problem.
We can also consider $i$ to be a bounded real number, with the modification $\#(A_n)=\mu_{\text{Le}}(A_n)=(U-L)^n$, and
$$
\overline{T}(A_n)=\frac{1}{(U-L)^n}\int\limits_{a\in A_n}T(a)\,\mathrm{d}\mu_{\text{Le}}.
$$
What CS people did instead, is stating $T(a)
\le T(\text{head})+T(\text{tail})+cn$ for some $c$, then simply averaging $T(\text{head})$ and $T(\text{tail})$ for varying head or tail lengths. This is stating implicitly somehow varying head (or tail) lengths are "equally likely", with out even considering the constraint that makes $A_n$ finite. This is like saying you can pick an odd number from the set of all integers at "$50\%$ probability" without even bothering to define what this "probability" means!
So how is this average time complexity rigorously defined over an infinite, countable number of cases?
If average time complexity is dependent on a set of rules of translating clearly defined recursion to what is essentially an intuitive ad-hoc definition each time, how can we define average time complexity for arbitrary code?

Here is the definition of average-case time complexity of an algorithm:

Let $T(x)$ be the running time of some algorithm $A$ on input $x$. For every $n$, let $\mu_n$ be a distribution on inputs of length $n$. The average-case or expected time complexity of $A$ on inputs of length $n$ is $$T_{\mathit{avg}}(n) := \mathbb{E}_{x \sim \mu_n} T(x). $$

As you can see, in order to talk about average-case complexity, you have to specify a distribution. In the definition above I have alluded to the common case in which the complexity is parameterized by input length, but we could also have more parameters, or no parameters at all.
For comparison-based sorting algorithms, we usually consider the following distribution $\mu_n$: the uniform distribution on all $n!$ permutations of $1,\ldots,n$. However, we would obtain exactly the same notion of average-case complexity (for comparison-based algorithms) if instead we pick any atom-less distribution $\mu$, and define $\mu_n$ to consist of $n$ iid copies of $\mu$.
Unfortunately, no distribution on the integers is atom-less. This creates a problem, since if we generate $n$ iid copies of a distribution $\mu$ with atoms, then there is positive probability that the generated elements are not distinct. While comparison-based sorting algorithms can certainly handle this case, the situation becomes much less clean since the average-case time complexity now depends on $\mu$.
Finally, you seem to be quoting a quite informal average-case complexity analysis of quicksort. You can find rigorous analysis of the average-case complexity of quicksort (in fact, two different ones) in lecture notes of Avrim Blum.


PCA with Bishop's book I am reading PCA in Bishop's Pattern Recognition and Machine Learning pg. 562, here in Lagrange multiplier but I don't get it in the highlighted: I wonder is it $u_1$ or $u^T_1$?

Your help is appreciated!

You should take the gradient of the function, that is, the vector of partial derivatives with respect to all coordinates of $\mathbf{u}_1$, and equate it to the zero vector. Let us suppose that the individual coordinates of $\mathbf{u}_1$ are $u_1^1,\ldots,u_1^n$, so that (12.4) reads
$$
\sum_{i=1}^n \sum_{j=1}^n S_{ij} u_1^i u_1^j + \lambda_1 \left(1 - \sum_{i=1}^n (u_1^i)^2\right).
$$
The derivative with respect to $u_1^t$ is
$$
\sum_{i=1}^n (S_{it} + S_{ti}) u_1^i - 2\lambda_1 u_1^t = 2 (\mathbf{S} \mathbf{u}_1)_t - 2\lambda_1 u_1^t,
$$
since $S$ is symmetric. The gradient is thus
$$
\nabla (12.4) = 2\mathbf{S} \mathbf{u}_1 - 2\lambda_1\mathbf{u}_1.
$$
Equating it to zero, we obtain the condition $\mathbf{S} \mathbf{u}_1 = \lambda_1 \mathbf{u}_1$, that is, $\mathbf{u}_1$ is an eigenvector of $\mathbf{S}$ corresponding to the eigenvalue $\lambda_1$.


Reduction of SUBSET-SUM to SET-PARTITION There is a similar question that has been asked, but my question addresses particular detail of an answer.

I am trying to reduce SUBSET-SUM to SET-PARTITION. I found the following description:

SUBSET-SUM is defined as follows: Given a set X of integers and a target number t, find a subset Y from X such that the members of Y add up to exactly t. Let s be the sum of members of X. Feed X' = X U {s - 2t} into SET-PARTITION. Accept if and only if SET-PARTITION accepts.

What does "X' = X U {s - 2t}" (union?) and "Feed X' = X U {s - 2t} into SET-PARTITION" mean? How does this prove that SUBSET-SUM can be reduced to SET-PARTITION?

What you are doing here is adding a new element to your original set 'X'. The value for this new element is (s - 2t). Hence, X' now contains one extra element as compared to X.

The SET-PARTITION would "accept" if the provided set can be partitioned into two subsets with equal sum. We were already able to pick out a subset 'Y', from the set X, the sum of whose elements was 't'. If we include the extra element (s-2t) in this subset Y, the sum of its elements would now become ( t + s - 2*t ) = (s-t). This is also the sum of the elements which are remaining in the set (X - Y). Hence, X' can be divided into two subsets each of whose sum is (s-t).


Do a pair of parallel edges form a cycle in a graph Whenever there is a back edge, a cycle is detected.
Then, do a pair of parallel edges form a cycle in a graph? If no, why it is not a back edge?

Graph theory is notorious for having nonequivalent definitions of the same term being used by different authors in different places, so it is important to check the definition of the terms in your case. If you use the definition I'm familiar with
\begin{align*} &\text{A }\textit{cycle }\mathcal{C}\text{ is an alternating sequence of vertices and edges, beginning with a vertex }v_0\\ &\text{ such that no vertices or edges repeat except that }v_0\text{is both the first and last element}\\ &\text{of the sequence} \end{align*}
In that case if $G=(V,E,f)$, $v_1,v_2\in V$, $e_1,e_2\in E$ and $f(e_1) = f(e_2) = \{v_1,v_2\}$ then $v_1e_1v_2e_2v_1$ is a cycle in $G$.


Argmax in $k$-NN algorithm Given a query instance $x_q$ to be classified

Let $x_1,\ldots,x_k$ be $k$ instances which are nearest to $x_q$
$$ \hat{f}(x_q) \gets \operatorname*{argmax}_{v \in V} \sum_{i=1}^k \delta(v,f(x_i)), $$
where $\delta(a,b)=1$ if $a=b$, else $\delta(a,b)=0$ (Kronecker function).

If $f$ is an objective function to be optimized, why is argmax there? Can someone explain how this function gets updated. This is for $k$-nearest neighbor function.

Given a new point $x_q$, we find the $k$ closest points $x_1,\ldots,x_k$. Each one of them is associated with a cluster $f(x_1),\ldots,f(x_k)$. We assign $x_q$ to the most common cluster among $f(x_1),\ldots,f(x_k)$. The argmax equation is just a fancy way of expressing this idea: for any cluster $v$, the quantity $\sum_{i=1}^k \delta(v,f(x_i))$ is just the number of $x_i$'s which are assigned to cluster $v$, and the argmax picks up the cluster $v$ maximizing this parameter.


Loop variant for a while loop that occasionally doesn't decrease? I'm working on practice problems for a test I have, and every example of loop variant decreased with every iteration of the loop. On this one, the values remain the same when a < b. My attempts also got me a loop variant that has a chance of a negative since occasionally a becomes larger than b and vice versa. Any advice on attempting to find and prove the loop variant for this question?

def mystery(a,b):
# Precondition: a >= 0 and b >= 0
while a >= 0 and b >= 0:
    if a < b:
        a, b = b, a
    else:
        a = a - 1
return a

EDIT: For anyone who is interested in this question, my best solution is as follows.

$$f_{1} = a + 2b + 1$$

Just a hint for now, since this is a practice problem: consider a lexicographic combination of orders.

In some more detail: Suppose you have two maps $f_1:S\to D_1$ and $f_2:S\to D_2$ from your program states $S$ into well-founded ordered domains $(D_1,\le_1)$ and  $(D_2,\le_2)$. The lexicographic combination of $\le_1$ and $\le_2$ is the order $\le$ on $D_1\times D_2$ given by $(x_1,y_1)\le(x_2,y_2)$ iff either $x_1\le_1x_2$, or $x_1=x_2,y_1\le_2y_2$. It is also well-founded.

So if $f_1,f_2$ are such that

$f_1$ never increases, and
whenever $f_1$ does not decrease, $f_2$ does,

then the map $(f_1,f_2):S\to D_1\times D_2$ is a variant proving termination.


Would adding recursive named functions to Simply typed lambda calculus make it Turing complete? Say I have Simply typed lambda calculus, and add an assignment rule:

<identifier> : <type> = <abstraction>

Where <identifier> is the name of the function, <type> is the function type and <abstraction> is the abstraction to be assigned to the identifier.

Then I add a typing rule that says that when you see an assignment such as the above, you use a temporary type context, in which the declared type (the one in <identifier> : <type>) is associated with the identifier, to type check <abstraction> and then make sure the declared type equals the abstraction's type.

And finally I add another rule that would let me have a list of assignments on top of a lambda term which is the one I'd evaluate, such that all these assignments would be added to the global scope before the term is evaluated.

Seems to me that this alone would make it Turing complete since I'd be able to do stuff like:

stackoverflow: NUM -> NUM = λn:NUM.(stackoverflow n)
(stackoverflow 0)

And at the same time, everything I can define in this language would be "well typed" in the sense that it wouldn't be able to define infinite types (I wouldn't be able to define the Y combinator).

So my questions are, is this really Turing complete? And, am I missing something when I say everything would be "well typed" (like for instance, I could define the Y combinator in a way I haven't yet realized or is there any gotcha in this type system)?

If all you have this definition rule (which doesn't perform any computation), it won't help you. You also need a way to use this definition, like you did in your code example: you implicitly used another language construct, where a definition is available in the next line.

To make things precise, I'll consider a construct which combines a definition with a way to use that definition — a “let … in …” construct (a recursive one, since the function is available while you're defining it).

$$\frac{
  \Gamma, f \colon T \vdash M : T \qquad
  \Gamma, f \colon T \vdash N : T' \qquad
}{
  \Gamma \vdash (\mathtt{let\:} f \colon T = M \mathtt{\:in\:} N) : T'
}$$

From a typing perspective, it doesn't matter whether $T$ is a function type or whether $M$ is an abstraction. These restrictions would ensure that you can find a nice execution semantics (the general rule like phrased above allows recursive definitions like let x : int = x + 1 in x which cannot be usefully evaluated, but you can always define such cases as looping forever).

With this language construct, you do have a Turing-complete language, and you can define a fixpoint combinator (even with the abstraction restriction).

let Y : (int→int)→(int→int)  = λg. g (Y g) in …

$Y$ is a fixpoint combinator over the integers. You can make a similar definition at any type.

You can't make a polymorphic fixpoint combinator. This restriction comes with the simply typed lambda calculus. If you added polymorphism (which in itself does not allow recursive functions, for example System F is normalizing), you could get a polymorphic fixpoint combinator with a suitably generalized recursive let construct.


Sorting in a probabilistic order Given a list of real numbers $p_1, \dots, p_n$, I am looking for a most efficient algorithm to sort this list in a "probabilistic ascending order", meaning that $p_i < p_j$ implies that it is likely for $i$ to be placed before $j$, but not certain. In principle, every permutation is a possible output, but the less sorted the permutation is, the less likely it is to occur.

The best solution I could come up with is to modify selection sort. Instead of selecting the minimal element in every step, you select a random element with probability proportional to $\frac{1}{p_i}$. This has quadratic complexity of course, so I was wondering if there are better alternatives.

One of the popular models for biased permutations is the Mallows model, dating to a paper of Mallows from 1957. Lu and Boutilier, quoting Doignon et al., give the following recipe for sampling a permutation according to the Mallows distribution, given a parameter $0 < \phi \leq 1$:

Start with the permutation 1.
Insert 2 into position 1 with probability $\frac{\phi-\phi^2}{1-\phi^2}$, and into position 2 with probability $\frac{1-\phi}{1-\phi^2}$.
Insert 3 into positions 1,2,3 with probabilities
$\frac{\phi^2-\phi^3}{1-\phi^3},\frac{\phi-\phi^2}{1-\phi^3},\frac{1-\phi}{1-\phi^3}$, respectively.
Insert $4,\ldots,n$ in an analogous manner.

When inserting $x$ into position $i$, what you do is shift positions $i,\ldots,x-1$ one step forward, and insert $x$ in the resulting empty spot.

The probability to obtain a permutation $\pi$ is proportional to $\phi$ raised to the number of inversions in $\pi$ (the Kendall $\tau$ distance between $\pi$ and the identity permutation).

Another popular model is the Plackett–Luce model from 1959. There are other models, for example Tallis–Dansie.


Can maximal number in poset be more than one? In poset maximal number is defined as:
An element 'a' belongs to 'A 'is called a maximal number if there is no element 'c' in 'A' such that a is less than c.

but it again says that there can be more than one maximal number. How can it be possible?

Consider for example the poset of all subsets of $\{1,2,3\}$ of size at most $2$ ordered according to inclusion. The maximal elements in this poset are $\{1,2\},\{1,3\},\{2,3\}$.

For an even more striking example, every antichain (set in which no two elements are comparable) is a poset in which all elements are maximal and minimal. For example, consider the poset of all subsets of $\{1,2,3\}$ of size exactly $2$ ordered according to inclusion. There are three elements $\{1,2\},\{1,3\},\{2,3\}$, and all are maximal and minimal.

It is always possible to add a maximal element to a poset so that it contains a unique maximal element. See if you can figure out how.


Finding common structure in strings I don't even know the right words to describe my problem, so I'll start with an example:

"aabaa", "ccrcc", "ffaff" are equivalent to some extent, because they all have the same length and follow the same formula: twice one letter, once another letter and finally twice the first letter again.

As I said, I lack even the vocabulary to describe this commonality of structure, so the first part of my question is: what is this kind of structure called and how is it studied?

The second part of my question is: do you know of an algorithm to transform a string into a representation of its structure? Or maybe more simply, an algorithm that would assess if two strings share the same structure?

What you're describing seems to be isomorphisms between strings. (Note that there happens to be a more complicated notion that is also called 'string isomorphism', but that isn't what we're talking about here.)

You can 'describe the structure' of these strings as follows: replace each character with the number of different characters excluding itself before it in the original string. If you do this for the three strings you mentioned, you get the string '00100' in all three cases.

This also gives an algorithm to test whether two strings are isomorphic: apply the above transformation on both strings and test whether the results are equal.


solving a problem with induction The original question is the following

  prove that $2·\sum_{i=0}^{n-1} 3^{i} = 3^n-1$ for all n $\geq$ 1

I know that I have to prove by induction and have successfully done the base case, my IH is the following:

Assume $2·\sum_{i=0}^{n-1} 3^{i} = 3^n-1$ holds for all n $\geq$ 1 to prove $2·\sum_{i=0}^{n} 3^{i} = 3^{n+1}-1$

then I did this:
$2·\sum_{i=0}^{n} 3^{i} = 2·\sum_{i=0}^{n-1} 3^{i} +3^n$

then by my IH: $2·\sum_{i=0}^{n-1} 3^{i} +3^n = 3^n-1+3^n $

after this I struggle to continue, I know I have to find a way to rewrite it to $3^{n+1}-1$ and I know this is equal to $3·3^n-1$ but I don't see how to get from the one to the other. Anyone who can help?

edit: I mistook a 2 for a 3, can anyone help now?


Do cryptographic hash function solve clustering problems with linear probing? I understand in open addressing hash tables some clustering will always happen just by random chance, even if the input data is perfectly random, leading to some "best possible" lookup performance hit (for an open addressing scheme).

If the hash function is of low quality, and we use linear or quadratic probing, we may observe "primary" and "secondary" clustering effects that make clustering, and therefore lookup performance, worse.

My question is: would using a cryptographic hash function result in linear / quadratic probing having the "best possible" lookup performance, effectively eliminating primary and secondary clustering problems?

Cryptographic hash functions are not better than any hash functions with good distribution and "avalanche effect" (eg xxHash) on this regard.

Do they ensure "best possible" lookup performance? In the way you defined that, yes.

Do they eliminate clustering problems? No, clustering is a probabilistic effect that becomes worse as you insert more entries into your hash table, even if they are perfectly distributed. And this effect is already accounted in formulas    of average lookup complexities for linear/quadratic ht algorithm for a given ht load.


For what kind of data are hash table operations O(1)? From the answers to (When) is hash table lookup O(1)?, I gather that hash tables have $O(1)$ worst-case behavior, at least amortized, when the data satisfies certain statistical conditions, and there are techniques to help make these conditions broad.

However, from a programmer's perspective, I don't know in advance what my data will be: it often comes from some external source. And I rarely have all the data at once: often insertions and deletions happen at a rate that's not far below the rate of lookups, so preprocessing the data to fine-tune the hash function is out.

So, taking a step out: given some knowledge about data source, how can I determine whether a hash table has a chance of having $O(1)$ operations, and possibly which techniques to use on my hash function?

Hash table lookup can always be $O(1)$ for static sets, see the 2002 paper by Arne Andersson and Mikkel Thorup: Dynamic ordered sets with exponential search trees

  Firstly, we give the ﬁrst deterministic polynomial-time (in n)
  algorithm for constructing a linear space static dictionary with $O(1)$
  worst-case access cost (cf. perfect hashing). As mentioned earlier, a
  linear space data structure that supports member queries (neighbor
  queries are not supported) in constant time can be constructed at a
  worst-case cost $O (n^2 W)$ without division [30]. We show that the
  dependency of word size can be removed.

In the general case, Andersson et al provide an algorithm for hash-indexed data structures that support lookups and updates in $O(\sqrt{\log n / \log \log n})$. Furthermore, they prove that this bound is optimal. So we know exactly how close we can get to $O(1)$ in the general case.


How can recursion tree split a problem into smaller pieces that do not add up? If I have a recurrence equation:
$$T(n) = 3T\big(\frac{n}{4}\big) + cn^2$$
It says it splits a problem of size n into 3 subproblems of size n/4. Then it keeps splitting it until the problem size at the leaves is 1 or less. The first part that does not make sense to me is how can you split a problem of size n into 3 problems of size n/4. To me it seems that there are now 3 problems of size n/4, but where is the remaining 1/4 of n? Who is solving that?
Also, the number of leaves is
$$n^{\big(\frac{loga}{logb}\big)}$$
Assuming n=1000, it can be calculated that there are 235 leaves. So 235 problems of size 1 are solved, how are the rest of 765 solved?
I have a feeling that I have misunderstood some principle, but I do not know what exactly.

Here is a very simple example: binary search.
We are looking for an element $x$ inside a sorted array $A$. We compare $x$ to the element at the middle $m$ of $A$. If $m = x$, we're done. If $m > x$, we recurse on the left half, and if $m > x$, we recurse on the right half. The recurrence for the worst-case running time is
$$ T(n) = T(n/2) + O(1), $$
whose solution is $T(n) = O(\log n)$.


What is the appropriate algorithm for bipartite matching with constraints? I have a problem that is a bit complex, and I don't know what method/model I should use to express it (much less solve it).

Let's say we have a lot of employees and a few jobs to be done. Each employee ranks the jobs they want most.

Easy. Bipartite matching, with weighted edges. Or Hungarian algorithm. Right?

Now things become more complicated. Instead of one job each day, an employee has to do 4 jobs in a day. The same single ranking they gave will be taken into account for the other 3 jobs they receive (no repetitions).

Since each employee must have 4 jobs, and there are many more employees than jobs, each job can have multiple people assigned to it for each period.

More complicated: each job has a maximum of employees it can accommodate (different for each job).

More complicated. Now jobs are skill based. Each employee has not only a preference ranking, but a skill class they belong to, low, med, or high. So each job has a phase for the low-skilled, the medium-skilled, and the high-skilled, with a skill level repeated for the fourth phase, as needed.

The objective is to make sure every employee ends up with the most of their highest ranked choices.

Does there exist some framework for solving such problems? Is there a way to adapt bipartite matching for all of these constraints?

The problem as described still seems amenable to doing a bipartite matching with weighted edges if you adapt the graph setup as follows.

If an employee must do four jobs, represent the employee with four vertices in the graph.  Each job should be represented as four vertices in the graph, one for each needed skill level plus one repeated skill level.  Connect each employee vertex with the job vertex corresponding to the highest skill level the employee is capable of performing.  Don't connect an employee to more than one skill level within a job.  Example: if a job has two high skill phases, connect all the employee vertices for a given qualified employee to one phase or the other, not both.  The edge weights between the employee and job vertices should be the employee preference score for the job.

With this graph, a maximal bipartite matching should produce proper job assignments maximizing employee preferences while matching skills.


is the alignment between two sequences of points with 'no cross line' constraint an NP problem? Given two sequences of points(i.e. ordered points), connect the points in seq_A with the points in seq_B according to some rules. A point could be connected to 0, 1, or many points in the other sequence. But there should not be any line crossing. And each line could be assigned with a weight(controlled by relation between two connected points) and the overall weights should be as low as possible.

Is this an NP problem? Can this problem be reduced to any of Karp's 21 NP-complete problems?

Thanks to David Richerby. The constraints that were missing are that the number of points that are not connected to any points should also be as few as possible.

You could prove that something is in NP by reducing it to an NP-complete problem. However, it's usually much easier to just demonstrate a nondeterministic polynomial-time algorithm that finds a solution, and even easier to demonstrate a deterministic polynomial-time algorithm that verifies a given solution.

Now, the trivial answer to your question is "No, this is not in NP" because there's a type error. NP is a class of decision problems (i.e., problems where the answer is "yes" or "no"), whereas your problem is to compute some object that minimizes some criterion.  However, the decision version of your problem is in NP: this is the problem where you're given a target weight $w$ and asked if there's a solution with weight at most $w$. It's easy to check deterministically in polynomial time that a proposed solution does have weight at most $w$.

Beyond that, there's not much to say. Your problem seems under-specified to me because the trivial solution "Don't match anything at all" has weight zero, which is best possible as long as the weights are non-negative. If you tighten up the definition of the problem, my guess is that the non-crossing requirement constrains the problem so much that it will have a deterministic polynomial-time solution. For example, if you match the first element of sequence $A$ to anything other than the first element of sequence $B$, then the first element of sequence $B$ can't be matched to anything without crossing. This suggests that dynamic programming will give an efficient solution.


Shrinking Item 0-1 Knapsack problem I have encountered a variant of the knapsack problem with shrinking items.

Effectively, it is a 0-1 knapsack problem where the initial weight of each item is $W(n)+V(n)$ and their value is $V(N)$, but immediately after being put into the container the item shrinks by $W(n)$. This means that for every item IN the knapsack, weight and value are the same. (It is therefore also possible to look at this as a value-irrelevant "best fill only" 0-1 knapsack.)

So, in this case, one also needs to determine the proper order of items to insert and whether a specific item is legal in the combination before being put in the container.

I have already determined that order of insertion, given a valid collection, should be based on $W(n)+V(n)$ descending—but thus far I am failing to create a set of valid collections in anything under $O(2^n)$.

Dynamic programming solutions are failing me both because of the apparent interdependence of elements which makes memoization seemingly impossible.

I realize I have not given much here, but I could really use some help. How does one go about approaching this variant?

If curious, the actual application is that we have a large number of different electrical appliances that all cause a known power surge when turned on and afterwards draw a set amount of power. We never want to trip a breaker, so the surge needs to be taken into account when figuring out how many at most we can turn on.

Maybe I misunderstood you, but we can definitely find a dynamic programming solution, a very similar one to the one for knapsack itself. Let $T[i, b]$ denote the maximum profit that can be made for the first $1 \leq i \leq n$ items, and $b$ is the remaining weight of the knapsack. Here is the recurrence.

$$T[i, b] = \begin{cases} 0 & \text{if } i =0 \vee b = 0 \\ T[i - 1, b] & \text{if } w(i)  > b \\ \max \{T[i - 1, b], T[i-1, b-V(i)] + V(i)\} & \text{if } w(i) \le b \end{cases}$$

For the base case, the 0th item doesn't exist so we have no profit. Similar for having run out of space.

Next, if $w(i) := W(i) + V(i) > b$, then we obviously cannot add item $i$ to our knapsack, and must continue on.

In the last case, we have two choices, either not include the item, or include it. For the latter, we then have $b - V(i)$ weight remaining, and $V(i)$ extra profit.

This dynamic programming algorithm has a running time of $O(nB)$, which is pseudopolynomial. Returning $T[n, B]$ is your maximum profit for all your items.


How do you prove that the set of decimal representation of the 4 divisble natural numbers is regular? This is from an old exam, the last Task no one could solve correctly and I'm curious how it's done :p

Show that the set of decimal representation (without leading zeroes) of the divisible numbers by 4 (natural numbers) is regular.

By this thread How to prove a language is regular? I know that one can make a DFA to Show that a language is regular.

But is that possible at all because we have infinite natural numbers that are divisible by 4..

I cannot even imagine how that DFA would look like :o

Maybe there is another way of showing this, too?

Edit: Removed..

A decimal number is divisible by 4 if the number formed by its last two digits are divisible by 4. Stated differently, divisibility by 4 depends only on the last two digits. That should be enough for you to show that your language is regular.

The language of numbers in base $b$ divisible by $m$ is regular for all $b,m$, but that's somewhat harder to show.


Finding MST after adding a new vertex Let $G=(V,E)$ which is undirected and simple. We also have $T$, an MST of $G$. We add a vertex $v$ to the graph and connect it with weighted edges to some of the vertices. Find a new MST for the new graph in $O(|V|\cdot \log |V|)$.

Basically, the idea is using Prim algorithm, only putting in priority-queue the edges of $T$ plus the new edges.

I don't fully understand the reason it works. Why it has to be a minimum spanning tree? What about a case where the heaviest edge in $T$ is $9$ for example, and we have other edges in the graph (And not in $T$) with the same weight?

It was also claimed that $|V|-1$ of the edges must be from the old graph and the other one will be one of the new - I'm not sure it's even correct. What do you think?

As stated in your post, the idea is to use Prim's algorithm with only the edges from $T$ and the new edges, let's call them $E'$.

For the sake of simplicity, let's assume that $T$ is the unique MST. (This is not required, but it is easier to reason about correctness in this case.)

Now think about what would happen if we ran Prim's on the full graph after the new vertex and edges had been added. We would start with an arbitrary single vertex and successively add edges that are adjacent to the growing tree.

Here's the key idea: each edge that is added by Prim's on the full graph will either belong to $T$, or to $E'$. If at some step we tried to add an edge in $E$ but not in $T$, then $T$ would not be a (unique) MST.

Since we know that regular Prim's would only add edges from $E'$ and $T$, these are the only edges that need to be added to the priority queue.

As Hendrick Jan said in comments, it is certainly not the case that $|V|-1$ of the edges must be from the old graph, for all of the new edges may be less than the minimum weight edge in the old graph, in which case the MST would include all of the edges in $E'$.


Minimum number that cannot be formed by any subset of an array We have an array of Integers, $A[]$ and we have to find the minimum number that is not the sum of a subset of array using the elements from $L$ to $R$ indices. I was thinking of using coin change DP approach, and outputing the min number with value infinity. But the problem is that the sum of ranges can be as large as 109, and we have about 105 queries of the type $[L,R]$, so I was hoping there'd be a better approach. Can anyone point me in the right direction?

There are 105 elements in the array

Suppose the elements of the array are 1,1,2,7. Then for indices 1 and 4, the smallest number that cannot be formed as a sum is 5. since we can form all 1,2,3,4.

You can pre compute an array $B$ such that $B[0]=0$ and $B[i]=B[i-1]+A[i-1]$. That you can use $A[L,R]=B[R+1]-B[L]$ to speed up you computations.

Now you can enumerate all pairs $A[L,R]$ and insert them into some sorted data structure $T$, and then you will be able to enumerate all of them in a sorted fashion, and thus answer your question.

This will still be in complexity $O(n^2\log n)$ where $n$ is the size of $A$ but it will not change even if the numbers in $A$ are large. This is not fundamentally faster than proposed solution, I don't know if there is indeed a faster one.


Languages that are not subset, but are union Are there examples of regular languages $L_1$ and $L_2$, where $L_1$ and $L_2$ is not a subset of each other but  that $(L_1 \cup L_2)^* = L_1^* \cup L_2^*$ ?

Yes. Let $L_1=\{a\}, L_2=\{\epsilon\}$. Obviously both languages are regular and neither is a subset of the other. We then have
$$
(L_1\cup L_2)^*=(a+\epsilon)^*=a^*
$$
and since
$$
L_1^*=a^*,\quad L_2^*=\epsilon^*=\epsilon
$$
we have
$$
L_1^*\cup L_2^*=a^*\cup \epsilon = a^*
$$


Time complexity of generating the first n primes and their product Suppose that I have a turing machine that receives as input the string $1^{n\times n}$ (unary input), what is the time complexity of writing $p_1,...,p_n$ on the output tape, where $p_i$ is the i-th prime number (written in binary)? And writing the first $n$ primes  followed by their product (all written in binary)?

Since the input is of length $n^2$, it makes sense that the TM must read it at least once (to learn the value of $n$), and we have a trivial lower bound of $\Omega(n^2)$. It is my understanding that what you actually ask is "can we  complete the task with $O(n^2)$ steps as well"?

You suggest using the Sieve of Eratosthenes to mark primes. This is a clever idea. Indeed, a possible TM can run over the input. Each time it finds a 1, it writes its index on the output tape ($p_i$), and go through the input tape, zeroing any multiply of $p_i$. Then it goes back to index $p_i$ and repeat.

In order to know the index, we can assume the TM maintains a counter on the output tape (which is being "pushed" every time the TM outputs a new prime).

Now let's analyze the running time.

reading the input - $n^2$
For any prime we find (and we have $n$ of those:)

mark the input tape according to the Sieve of Eratosthenes: we need to go through approximately $O(n\log n)$ numbers due to the density of primes  - $O(n\log n)$
push the index and write the output - $O(\log n)$
counting exactly $p^i$ steps between two indexes we zero - $O(n\log^2n)$

Multiplying all primes - $O(n^2\log^{1+\epsilon}n)$

so the naïve solution above takes $O(n^2) + n\times [ O(n\log n) + O(n\log^2 n)]  + O(n^2\log^{1+\epsilon} n)= O(n^2\log^2n)$. In the above I assumed counting takes $O(n\log^2 n)$ since each step we need to subtract 1 from a $\log n$-long number, for every step in the sieve (which we bound to length $O(n\log n)$).

The time complexity of that algorithms is $O(n^2\log^2 n)$.

However, things can get better, as there are other ways of sieving.
Assuming a multitape TM,  the sieve of up to $k$ can be computed using $O(k/\log\log k)$ additions
(thus, with $O(k\log k/\log\log k)$ bit-operations) by [1].
By setting $k=O(n\log n)$, we can compute the sieve with $O(n\log n)$ steps.

However, computing the multiplication of $n$ numbers (of length $\log n$) will take $n \times O(MUL_{\log n})$ where $MUL_k$ is the time to multiply two numbers of length $k$. According wikipedia, $MUL_k \approx O(n\log n )$ [2]. This step alone is $\Omega(n^2\log n)$ and I don't see much hope to get complexity of $O(n^2)$.

 [1]: A. O. L. Atkin and D. J. Bernstein, "Prime sieves using binary quadratic forms" (free-access), Mathematics of Computation 73 (2004), pp. 1023–1030.
 [2]: ignoring the practically constant term of $2^{\log^* n}$.


Are there decidable non-trivial properties of a LBA's accepted language? The halting problem and therefore the acceptance problem are decidable for LBAs, but are the infinite extensions of these problems decidable?
Given a LBA, can you decide whether there exists an input on which the LBA halts?
Given a LBA, can you decide whether the LBA accepts a certain non-empty, non-finite language?

Given a Turing machine $M$, you can construct an LBA $A$ that given as input a word of length $n$, it simulates $M$ on the empty tape as long as $M$ uses up to $n$ space, and the moment $M$ exceeds space $n$, it enters an infinite loop. In contrast, if $M$ ever halts, then $A$ also halts. Thus $A$ halts on some input iff $M$ halts on the empty input.
You can try to show that the second property is undecidable using a similar argument.


Is there any difference between Time Complexity and Running time? Is time complexity and running time of the program/algorithm one and the same thing?
Also, running time sounds like 'computer complexity'. As, it utilizes all the resources and give tangible time that program took to run. So, can we say that running time is same as computer complexity?

The terms, as they are used in computational complexity theory are different.

Running time is a property of an algorithm. It is the maximum number of steps the algorithm can run for, as a function of the length of the input.

Time complexity is a property of a computational problem. It is, essentially, the running time of the fastest possible algorithm for that problem.

Thus, we might talk about the time complexity of the sorting problem, and the running time of heapsort.  Informally, people often refer to the "time complexity" of an algorithm. Strictly speaking, this is incorrect, but there's only really one thing it could mean.

Note that we usually only quote the asymptotic behaviour of running times and time complexities, since we're usually not interested in the exact function, and it's usually too hard to figure out, anyway.

Note also that, in applied computing, "running time" may refer to the time taken for some program to run, as you might measure with a stopwatch.


Is $\{\langle G,x\rangle \mid x\in L(G)\}$ context-free? Our problem is:

  Given a context-free grammar $G$ and a string $x$, decide whether $x\in L(G)$.

Is this language itself context-free?

If your language were context-free, then by intersecting it with a regular language, we would deduce that the following language would be context-free:
$$
\{ \langle G,x \rangle \mid \text{$x \in L(G)$ and $G$ contains a single production $S \to w$} \}
$$
However, this is just the celebrated language $\{ ww : w \in \Sigma^* \}$ in disguise, which is known not to be context-free. It follows that your language (using any reasonable encoding) is also not context-free.


How to train this neural network? I seek the neural network (NN) which satisfies the 100 equations (i=1,2...100)

$\sum_{j=1}^{2000} NN(A_{ij},B_{ij},C_{ij})=Q_i$.

Where A,B,C are 100x2000 matrices

So I know Q, A, B and C
How can one find the NN? (ie train it using this data)
I have a second datset to test it on.
I also have MATLAB neural network toolbox, but that is not a necessity for me to use that.

Let $w$ denote the weights of the neural network.  Define the objective function $\Psi$ by

$$\Psi(w) = \sum_i \left(\left(\sum_j NN_w(A_{ij},B_{ij},C_{ij})\right) - Q_i\right)^2.$$

Then, find $w$ that minimizes $\Psi(w)$ using gradient descent.  You can find the gradient of $\Psi(w)$ using backpropagation through the neural network.  You can use all the standard methods for speeding up training of neural networks: stochastic gradient descent, Adam or momentum or Adagrad, etc.

This is very similar to training neural networks for regression problems.  The only difference here is that you are summing the output of the neural network on multiple inputs.  It is straightforward to adjust the objective function to take that into account, as shown above.


Perfect shuffle in parallel processing How is Perfect shuffle a better interconnect scheme for parallel processing? For example if we consider a problem of sum reduction, I want to understand how this scheme is useful when implementing sum reduction in parallel , for example on a GPU?

The perfect shuffle alone has never been used as an interconnection network; it always included exchange links, in order to allow for a worst-case $O(\lg n)$ routing algorithm.
Algorithms for reduction, broadcast, parallel prefix, transpose etc are given in

Yosi Ben-Asher , David Egozi , Assaf Schuster, SIMD Algorithms for 2-D Arrays in Shuffle Networks.

Stone was the first researcher to provide algorithms for the perfect shuffle network, including algorithms for the FFT, matrix transpose etc.

This network has been used in several parallel machines, but mostly in multi-stage shuffle-exchange networks such as the Omega network (which uses the perfect shuffle between stages). An example is the IBM SP3 machine.

Note that these are message-passing algorithms, whilst you refer to a GPU, which is instead a shared-memory device.


Finding if the given language is regular or not I have the language $$L = \{a^mb^nc^o| \, m + n + o > 5\}$$

where $m,n,o$ are non-negative integers.

I have to find whether the language is regular or not.

My attempt:

I feel it should be non regular. For it to be regular, we'd have to keep track of how many $a's$, $b's$ and $c's$ we have seen. But the problem is that there can be infinitely many values of $a$, $b$ and $c$ for the given constraint, and we can't "remember" that number with finitely many states.

On the other hand, I also think that if we take the complement of the language i.e

$$L = \{a^mb^nc^o| \, m + n + o <= 5\}$$
We know that this is regular because there are finite number of solutions for the constraint. Now, since regular languages are closed under complement, we can say the former is also regular.

Which one of these methods is correct? I tried to prove it using Pumping Lemma, but to no avail.

$L$ is regular.

Here is a proof as hinted by your second method, which points out that we may take advantage of the fact that regular languages are closed under complement. Another useful fact is regular languages is closed under intersection. Let $F=\{a^mb^nc^o| m,n,o\in\Bbb Z_{\ge 0}, m+n+o\le 5\}$. As a finite language, $F$ is regular. Let $H = \{a^mb^nc^o| m,n,o\in\Bbb Z_{\ge 0}\}$. As expressed by the regular expression $a*b*c*$, $H$ is regular. Since $L= H\cap\overline F$, $L$ is regular.

We can also see that $L$ is regular by the following one-line regular expression that expresses $L$. It is wrapped into multiple lines for easier reading.

$
((a\{6,\}|a\{5,\}b+|a\{4,\}b\{2,\}|a\{3,\}b\{3,\}|a\{2,\}b\{4,\}|a+b\{5,\})c*)|\\
((a\{5,\}|a\{4,\}b+|a\{3,\}b\{2,\}|a\{2,\}b\{3,\}|a+b\{4,\}|b\{5,\})c+)|\\
((a\{4,\}|a\{3,\}b+|a\{2,\}b\{2,\}|a+b\{3,\}|b\{4,\})c\{2,\})|\\
((a\{3,\}|a\{2,\}b+|a+b\{2,\}|b\{3,\})c\{3,\})|\\
((a\{2,\}|a+b+|b\{2,\})c\{4,\})|\\
(a+|b+)c\{5,\}|\\
c\{6,\}
$

Now that we have shown $L$ is a regular, the first method must be incorrect. In fact, we do not have to keep track of how many a′s, b′s and c′s we have seen. All we need is to make sure that the total number of them is greater than 5. There is a difference between these two requirements.

By the same argument, we can see easily that for any integer $k$, $L_k = \{a^mb^nc^o|m,n,o\in\Bbb Z_{\ge0},\,m + n + o > k\}$ is a regular language.

Here is another similar fact. For any integer $s$ and $t$, $L_{s,t}=\{a^mb^nc^od^p|m,n,o,p\in\Bbb Z_{\ge0},\,m + o > s, n+p >t\}$  is a regular language.


AI: Heuristic function A* search I have an assignment in my university where I have to implement Uniform Cost Search and A* Search.

We have an input which includes a map and queries.

The map is weighted, directed graph, represented by an adjacency matrix. The queries include Uniform Cost Search and A* Search queries (Ex: Uniform(or A*) + initial location + goal location)

I cannot use heuristic functions based on physical distance because we have no knowledge and extra information about this graph except distances between vertices.

Is there any way to find a heuristic function in this case ?

(Is it possible to use prior results from Uniform Cost Search in the queries to extract information from the graph?)

You can use the depth as the heuristic function I guess. The start node is at depth 0, the ones adjacent to it will be at depth 1 and so on! As the function will explore nodes, the heuristic function value will gradually increase with depth and that will make the function to choose next node with more caution, so that overall cost (distance to next node + heuristic value) is least affected.

Edit: You can use powers of 2 where the exponent term will be the depth. So the start node has heuristic value 2^0 = 1, the nodes adjacent to it have heuristic value 2^1 = 2 and so on.


Sorting by repeated reversal Let $A$ be an array of $n$ integers containing the numbers $\{1, 2, \dots , n\}$ in
some arbitrary order. For integers $i$ and $j$ such that $1 ≤ i < j ≤ n$, let
$\mathrm{Reverse}(A, i, j)$ be a procedure that reverses the subarray $A[i], A[i +
1], \dots , A[j]$ of the array $A$ while leaving the remaining elements of the
array unaffected.
Prove that the following algorithm sorts the array $A$
and also terminates.
for i := 1 to n − 1
  while A[i] ≠ i do
    Reverse(A, i, A[i])

I am able to prove this if the elements are in descending order. Why does this algorithm work for an arbitrary order?

If the algorithm terminates at all then $A[i] = i$ for $i \leq n-1$, and so $A$ is sorted. Hence it suffices to show that the algorithm terminates. Furthermore, when reaching $i = i_0$, we know that $A[j] = j$ for $j < i_0$, and so $A[i_0],\ldots,A[n]$ is a permutation of $i_0,\ldots,n$, which is a smaller instance of the same problem. Hence it suffices to show that the inner while loop terminates when $i = 1$.
Suppose that the inner while loop never terminates when $i = 1$. Let $j$ be the maximal value which appears infinitely many times as $A[1]$. After finitely many iterations, $A[1] \leq j$ always. Since $A[1] = j$ infinitely many times, there must be some subsequent iteration in which $A[1] = j$. After that iteration, $A[j] = j$. In all subsequent iterations, $A[1] \leq j$, which ensures that $A[j]$ stays $j$, guaranteeing that $A[1]$ never equals $j$ again. However, this contradicts the definition of $j$.
The maximal number of iterations of the inner loop is A000375. There is no known formula!
I couldn't find the sequence for the maximal total number of iterations of the inner loop (over all $i$) on OEIS.