Algorithm: Dimension increase in 1D representation of Square Matrix Consider the matrix with dimension $m \times m$:

$$
M =
\begin{array}{cc}
1 & 1 & 1 \\
0 & 1 & 1 \\
1 & 0 & 1 \\
\end{array}
$$

Its 1-D representation:
$$ M^* = \begin{array}{cc} 1 & 1 & 1 && 0 & 1 & 1 && 1 & 0 & 1\end{array}$$

Now, another dimension added, so that the matrix becomes:

$$
N =
\begin{array}{cc}
1 & 1 & 1 & 0 \\
0 & 1 & 1 & 0 \\
1 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
\end{array}
$$

$$ N^* = \begin{array}{cc} 1 & 1 & 1 & 0 && 0 & 1 & 1 & 0 && 1 & 0 & 1 & 0 && 0 & 0 & 0 & 1\end{array}$$

Update
The data structure can be any linear data structure (Array, Single LL, Double LL) not necessarily contiguously linear. The goal is to dynamically add or remove dimensions from the Matrix with least number of operations.

The best I can think of is to repopulate $N^*$ in $\theta(N^2)$ every time a new dimension is added.

There is a simple solution, but it requires a different 1D
representation of your matrix $M$. You suppose it is stored in an
arbitrarily long 1D array $A$, so that new elements can be added.

Then the elements of the matrix $M$ are stored such that: $M[i,j]$ is
stored in $A[k]$ with $k=(j-1)^2+i$ if $i\leq j$ and $k=i^2-j+1$
otherwise.

Other similar formulae are also possible.

The idea is to stores in order the successives layers of increased
matrix size starting with the $1\times 1$ matrix.

Storing order of a $3\times3$ matrix is described here, each element of the matrix being its index in $A$. The first index $i$ is the line index of matrix $M$ representation:

  1  2  5
   4  3  6
   9  8  7

When you increase the size $m$ of the matrix, you only have to add the new
layer at the end, i.e. add the representation of the last row and last column
at the end of the used part of array $A$. The cost is linear in $m$.

Explanation

The initial version of the question asked for a linear data structure,
without explicitly allowing for linked-lists, which I do not consider
more linear than anything else, the memory having generally a linear
address space. Hence I assumed the idea was to use, as efficiently as
possible, a one dimensional array $A$, without trying to mimic pointers.

I started looking for an efficient way to store (and retrieve) the
elements $M(i,j)$ of the matrix $M$ in $A$, so that extending the
matrix with an extra dimensional layer for the highest values of the
indices, could be done cheaply ... the cheapest being to add the new
layer right at the end of the existing matrix, so that the cost would
be no more than the number of elements to be copied.

To do that, while keeping a uniform indexing scheme requires to have
done it uniformly, starting from the $1\times 1$ matrix. The question
being somewhat imprecise regarding constraints, I assumed that keeping
each line in one contiguous piece is not really required.

The placement of the elements of matrix $M$ in the linear array $A$ is
illustrated by the above $3\times 3$ matrix, where each element has
the value of its index in $A$.

This organization is such that the index in $A$ of an element $M(i,j)$
of the matrix $M$ does not depend on the size of $M$, but only on $i$
and $j$. Taking $p=max(i,j)$, the placement in $A$ of the
upper-lefmost submatrix of $M$ of size $p$ is independent of the rest
of the matrix $M$. The element $M(i,j)$ is either on the rightmost
column of that submatrix if $i\leq j$, or on its last line otherwise.
Furthermore, the first $(p-1)^2$ elements of array $A$ are already
used to store the upper-left submatrix of size $p-1$. One uses the
next $2p-1$ elements of the $p^{th}$ row and $p^{th}$ column, which
contain element $M(i,j)$. This can be done in different ways, and the
proposed formula stores these $2p-1$ elements in top-down and
right-to-left order.

Note: the first version of the formulae used $p=max(i,j)$ explicitly to
compute the squares, a remnant of my initial search for a
solution. But @WeaklyTyped remarked rightly that the test comparing
$i$ and $j$ does the job, allowing to replace $p$ by $i$ or $j$,
according to the test result.

Actual use of the representation

One characteristic of this representation is that it preserves random access (access time is constant and independent of indices and
matrix size), which is not usually the case with list
representations. However it does not require
multiplication for indexing the array $A$, since only addition and
integer squares are needed. Integer squares can be memorized in a
linear array, or can be computed with addition only if successive
square values are needed in a loop, for example to read a line or a
column of the matrix, using the formula $(p+1)^2=p^2+2p+1$.

But, as usual, the usefulness of such a representation is highly
dependant on the operations needed and their frequency.

Note: this representation was found independently, but it may have been used before. Pointers to the literature are welcome.

A better solution with pointers

(Added July 1st 2014, after the answer was accepted)

The layer approach described in the previous algorithm seems more
effective than most pointer based representations for two reasons:

given $i$ an $j$, it allows access of element $M[i,j]$ in constant
time;
it has no overhead in space for storing pointers (not to mention
possibly greater garbage collection costs).

However, the last statement is not completely true. We chose to use an
array $A$ of "sufficient" length because that initially (in the first
version of the question) seemed a given constraint. But, if we relax
that constraint, it is clear that it is a costly solution in space
since the array $A$ must have a size sufficient to store the largest
version of the matrix $M$ that may be used.

Actually, there is something absurd about the solution presented
above, if it is to be more than an intellectual exercise (but the context and
motivations of the question were not given). If the array
$A$ has the maximum size that will ever be needed, why not simply code
the maximum sized matrix in it, and use at any time only the indices
that are actually needed, given the current matrix size $m$?

Since pointers are (now) allowed, this is a good motivation for
attempting to get the benefits of the solution presented above, without its
absurd drawback.

The idea is quite simple: keep the layer structure presented above,
but store the layers separately, rather than contiguously in the same
array.

So a matrix $M$ of size $m$ is implemented as $m$ arrays $L_p$ with $1\leq
p\leq m$, each $L_p$ having $2p-1$ elements corresponding to the
elements $M[i,j]$ of $M$ such that $max(i,j)=p$.

In order to access $M[i,j]$, one only has to compute $p=max(i,j)$ to
locate $L_p$, and then index appropriately with $i$ or $j$ inside
$L_p$ to get the right element. Actually, as in the first algorithm
above, it may be faster just to have two cases based on a comparison
between $i$ and $j$.  I do not get into the detailed formulae, that
are somewhat obvious to work out.

However this require an extra structure to find a pointer to $L_p$
when $p$ is known.

Three obvious ideas come to mind:

The first idea is to use an array of links to the $L_p$ layers,
which is indexed by $p$. The drawback is that the size of the array must be
the maximum possible value for $m$, but that is not as bad as the
maximum values for $m^2$. The advantage is that accessing any
element $M[i,j]$ will still be in constant time.
The second idea is to use a linked list, which avoids the constant
size array. However, the list has to be followed sequentially to get
the right layer $L_p$. Hence accessing any element $M[i,j]$ will on
the average be in linear time with respect to the current size
$m$. Note that, with this solution, it is better to access the list
from the end corresponding to the largest value of $p$. Firstly, that
is where layers are added or removed. Secondly, assuming that all
elements of $M$ have equal chance of beeing accessed, the
probability of finding an element in layer $L_p$ is proportional to
$(2p-1)/m^2)$, hence a higher probability for higher values of $p$.
Indeed, accessing the list from the higher value of $p$ is on
average twice as fast as accessing from the lower values of $p$
(proof left as an exercise). But access is linear in $m$ in both
cases.
In order to reduce access time, the accessing structure can be a
balanced tree. The size of the tree is linear in $m$, as it is with
a simple list, but the time complexity of finding the right $L_p$ is
now logarithmic in $m$, hence also for accessing an element
$M[i,j]$. While building this balanced tree, it is better to give to
each $L_p$ a weight proportional to $2p-1$ to account for its
probability of being the right layer. However, I have not checked
how much of a difference it makes.

But actually, trying to build a sophisticated balanced tree is
probably self-defeating sophistication, because it may have to be
maintained, and it may require more computation to be explored.  A
better solution is probably a widely branching tree that is walked
very simply by indexation.

Using a tree of indexing arrays

(I have no idea whether this has an official name in textbooks)

The nodes of the tree are arrays of length $2^d$, so that we can build
a balanced tree with nodes of degree $2^d$. The leaf nodes are arrays
of pointers to matrix layers, and the other nodes are arrays of
pointers to other arrays (or nothing).  Without going into details,
given a layer number $p$, The binary representation of $p$ is cut into
chunks of size $d$ which are used as indices for the arrays while
walking down the tree to find the layer $L_p$. With a value for $d$ of
3 or 4, this should give simple and fast access for matrices of
significant size.


Advice needed. NLP and ML. Where to start? Hi fellow computer scientists,

I just began my journey to the world of ML and NLP so please bear with me. I'm hoping to find some guidance here. I would be very grateful if anyone could point me in the right direction (reading materials, lectures, specific algorithms, tools, etc.) for solving the following list of problems:

Spell checking, grammar checking, proofreading with ML
Text generation on a given topic with ML
"Artistic Style Transfer" for articles (if it is even possible), i.e. "transfer" Shakespeare's writing style onto a given text.

I've done some learning already but neither of this helps:

ML lectures by Andrew Ng
Hacker's guide to Machine learning
Udacity's Introduction to Deep Learning

As far as I can see, your reading list lacks specific NLP introductions. A really good starting point is Dan Jurafsky and Chris Manning's Coursera course (for example here https://www.youtube.com/watch?v=nfoudtpBV68 ). This specifically covers spell checking in one of the first videos.

In general, spell checking is a rather easy task, while (convincing) text generation is a lot harder. Grammar checking should be easy in theory but I'm not sure about that. Concerning proofreading, I'm not completely sure what you mean by that. Does this extend over spell and grammar checking, in your point of view?

Artistic style transfer is possible although I'm not sure what the current state of the art. You could be more luckily diving into stylometry (https://en.wikipedia.org/wiki/Stylometry) there.

A really good NLP text book to start with is Jurafsky and Martin: Speech and Language Processing (specifically covering generation). 1st edition is publicly available as pdf (just google). But there is also a 2nd edition and they are currently working on a 3rd (the chapters they are done writing are freely available as well).


How can instruction fetch and decode pipeline stages run simultaneously in a CPU with dynamic branch prediction? I have recently been investigating CPU pipelining and branch prediction and have a question about how exactly these fit together.

If, for example, instructions are meant to be fetched in one stage of the pipeline and decoded in the next while the next instruction is fetched simultaneously, how is it possible for the pipeline to proceed without a stall when dynamic branch prediction is in operation?

As an instruction must be decoded before branch prediction can occur or be deemed unneeded, and as any prediction must be made before the next instruction can be fetched, how can an instruction be decoded while the next instruction is fetched in the same clock cycle?

As an instruction must be decoded before branch prediction can occur or be deemed unneeded,

That can be avoided. The fetch stage can do prediction based purely on the current PC, without looking at the instruction. Branch Target Prediction also enters the picture here, otherwise without decoding the branch target would be unavailable. Accidentally applying branch prediction to an instruction that turns out not to be a branch is not a disaster, just something to detect and signal a misprediction if necessary.

So this can be done with no bubble.

As an example, here is a diagram of the pipeline of the RISC-V BOOM processor (source), showing PC going to next-line predictor and the I\$ in parallel

  any prediction must be made before the next instruction can be fetched

Why stop? Just keep predicting, it doesn't matter that the next instruction(s) have been fetched, flush them out if one of the later predictions "changes its mind". This gives you a lot of time to run slow but high quality predictors after the fast predictors. You could even do away with the fast predictors, but then there really would be a bubble for every "taken" prediction - an unconditional stall is overkill though, there's no reason to not at least fetch the next address (effectively predicting "not-taken").

As a practical example, AMD Bobcat takes several shots at branch prediction, some in parallel with decoding (Fetch3 through Fetch5):

In the BOOM diagram there are also several forms of branch prediction, but the Backing Predictor (the more complex predictor with higher accuracy) there is before decode rather than parallel with it.


Asymptotically Optimal Algorithms I am confused how to check if an algorithm I made is asymptotically optimal.

At the very least, the running time is constant at O(4). This is because you will need to check at least 4 names.

At the very most, the running time is linear at O(n).
This is from n + n + n/2 + n/2 + n/4 + n/4 + .... = 2n * (1 + 1/2 +...) < 2n. As we ignore constants its just O(n).

I checked on Wiki and it said that the algorithm should perform at worst a constant factor of the best algorithm. But if you invented an algorithm then how do I figure this out?

We usually only care about the worst-case complexity of algorithms. An $O(n)$ algorithm is usually asymptotically optimal (assuming $n$ is the input size), since most functions require you to read the entire input in some cases.

Another example in which you can prove asymptotic optimality is comparison-based sorting algorithms. A comparison-based sorting algorithm is a sorting algorithm whose only access to the data is a comparison oracle, which compares to data items. Any such algorithm must make $\Omega(n\log n)$ oracle queries in the worst case. Therefore a comparison-based sorting algorithm running in time $O(n\log n)$ is asymptotically optimal.

In most cases, however, we cannot prove that a given algorithm running in superlinear time is optimal, since we don't know how to prove running time lower bounds on general computation models. However, in some cases we can prove such lower bounds conditionally, that is, assuming some widely believed hypothesis. This is known as fine-grained complexity theory, and it indicates (conditionally) that the best algorithms for many problems are indeed asymptotically optimal.


Need explanation of Heap's Algorithm Okay I am trying to understand the Heap's Algorithm from the original research paper published by B.R Heap.

The most confusing aspect I found that while Heap says that the example described on the first page takes N=12 ie. example with 12 objects to provide a permutations for them.

But yet he says that the 12 objects are the letters A to Q. Now unless I have forgotten my counting totally, A to Q is 17 objects not 12. So am I missing something obvious ?

Secondly, can someone please explain the Table 1 given in the bottom of the first page ?

Thanks.

Pay no attention to the letter $Q$.  $Q$ is just a "short-hand" for "the $N$th letter".  Think of $Q$ as a kind of variable, rather than a letter itself.

In other words, ignore the Q bit, and keep reading.  If you like, think of it as A, B, C, ..., L, and pretend that was just a typo.  Keep reading.

Let me give you some advice about reading papers.  If you find some detail you don't understand, often you can keep reading and see if you can still understand what is going on.  Sometimes there will be a typo in the paper that is small or inconsequential.  Sometimes it's a detail but if you keep reading you can still understand much of the rest of the paper.  Sometimes the paper is actually correct and once you absorb the rest of the ideas in the paper, when you go back and re-read the paper you'll realize what the authors actually meant.  (Of course, occasionally you'll discover a serious fundamental flaw in the paper.  But don't jump to assuming that's the case; that should be your last hypothesis, rather than your first hypothesis.)

If you still can't understand the paper, try to find other papers that cover related topics -- e.g., that it cite or that cite it -- and build up your understanding of the area.  Then, come back and read the paper again.

Often, if you follow these strategies, you'll be able to work out what is going on.  These are useful skills -- they will make you more self-reliant and more effective at getting value out of the research literature.


Are there any languages without tokens? I know a lot of computer languages and they all use tokens. E.g. in very early BASIC you could say LET answer = 42, which is composed of seven tokens, LET, answer, =, 42, and three space tokens.

It seems that every character must be part of some token, including comments, which can be considered free-form tokens after the initial identifier.

Are there any languages completely or partially without tokens? Is it even possible for such a language to exist? What would it look like?

I agree with the commenters that your question is either ill-defined or nonsensical. It all hinges on what you mean by "tokens", and what it would mean to "not have tokens."

If you mean multi-character sequences that are "chunked" together into larger words, consider Brainfuck — or actually most esolangs, including my favorite, Befunge — where every "command" is a single character. However, on the other hand, many Brainfuck interpreters actually treat [-] as a single "chunk" meaning "set the current tape cell to zero", so in that sense maybe you'd call [-] a "token".

On the other hand, if you consider single characters to be "tokens", then maybe we need to go the other direction, and find programming languages in which everything kind of flows together without divisions. The first thing that pops to mind is Inform 7 (yes, that's Inform 7 source code!), where meaning is conveyed through English prose. Obviously Inform 7 has a parser that deals in words, but those words don't directly correspond to anything like LET in Basic; it's more complicated than that.

Or, consider Piet, an esolang in which programs are expressed as two-dimensional pixel paintings. Does a pixel count as a "token"? Does a rectangle of pixels count as a "token"?

In the same vein — of trying to break away from the strictures of linear words and into more free-flowing worlds — consider noit o' mnain worb, a nondeterministic cellular automaton. It uses ASCII characters to represent cells in the automaton; but do those characters each count as a "token", or are the relevant building blocks of worb programs more like "corridors" and "gates"?

For that matter, consider Wireworld, a better-known cellular automaton. Does Wireworld count as a "language"? and if so, does "it" "have" "tokens"?

For that matter, consider the "language" in which ENIAC was programmed. It certainly didn't have "tokens"! But if you were to write down the plugboard configuration for a given "program", I suppose that you'd pick some way of writing it down that involved ASCII and a grammar of tokens. I don't guess you'd communicate the plugboard configuration with a pen-and-ink drawing. (But maybe you would! Who knows!)

For that matter, what would you say about plain old x86 machine code? That's a "computer language" if ever there was one... but it doesn't have "tokens", does it? All it has is a stream of bytes, one after the other, which are chunked together to form instructions. Or does an instruction (such as B82A0000 or C3) count as a "token"? Does it matter if the same set of bytes (or some of them, at least) could be reinterpreted by another part of the program as a piece of data, a jump address, et cetera?

Basically, you need to define what you mean by "language" and "token"; and once you do that, I think you'll find that your question answers itself.


Partial Range Query on Inverted File with Combined Index I am currently reading Multidimensional and Metric Data Structures by Hanan Samet for fun. The combined index is discussed on page 5-6. I do understand it in the sense that the inverted file itself is an index, and then we extrapolate another index by lexicographically ordering the attribute.

So, given a record with four attributes (Name, X, Y, Z), that is, the name and three dimensional point in space. If I created the inverted file such that it maps Name to the X,Y,Z attributes, then we can create another index by lexicographically ordering the attributes X,Y,Z. The possible orders would be XYZ, YXZ ZYX.

Do we order by the values of XYZ in the inverted file at all? Does the index of lexicographically ordered XYZ attributes point to the inverted index, which thus makes it combined?

Any help is greatly appreciated!

I don't think you've got the idea for an inverted file quite right.  If there are three attributes (X, Y, and Z), the natural approach is to have three inverted lists:

The first list maps from the value of X to the record (or from the value of X to the Name, if the Name is unique for each record and is how the record is identified).
The second list maps from the value of Y to the record (or from the value of Y to the Name, if the Name is unique for each record).
The third list maps from the value of Z to the record (or from the value of Z to the Name, if the Name is unique for each record).

So, if there are three attributes, we might end up with three inverted files.

See Figure 1.2 in the book for an example of an inverted file.

Now for the idea of a combined index.  A combined index for the attribute ordering XYZ would be a sorted list of records, where the sort order works as follows:

If two records differ in their X attribute, then order them by the value of their X attribute (and ignore their Y,Z attributes).
If two records have the same X attribute but differ in their Y attribute, then order them by the value of their Y attribute (ignoring their Z attribute).
If two records have the same X and Y attributes but differ in their Z attribute, then order them by the value of their Z attribute.

This is known as lexicographic order, where the attributes are taken in the order X,Y,Z.  You can think of this as XYZ-lexicographic order.  Once we sort using this particular order, we get a combined index for the attribute ordering XYZ.

Of course we could also form a combined index for other attribute orderings as well.  We might form multiple combined indices, each with a different attribute ordering.  The order in each combined index is different.  If there are $n$ attributes, we could have up to $n!$ different combined indices, corresponding to the $n!$ different permutations (orderings) on the $n$ attributes.  Nothing says we have to store all of those possible combined indices; we could store just one of them, or some of them, or all of them, or none of them.

A combined index is different from an inverted file.

However, you might notice that if you have a combined index for attribute order XYZ, then this obviates the need for an inverted file for attribute X, since you can use the combined index for XYZ in any place where you would have wanted an inverted file for X.

This is all explained pretty clearly in the book you cited.  I recommend you work through the example in Figures 1.1 and 1.2 in the book, to better understand inverted lists.


Is turing completeness related to recursive enumerable languages? I recently came across this term "Turing complete" in my study of morphogenesis models. When I looked up, it said that a turing complete machine can simulate a universal turing machine.

When I looked up for its relationship with recursive enumerable languages, I couldn't find anything substantial.

My question is:

  Will a turing computable machine always accept recursive enumerable
  languages?

Thanks in advance!

A language $L$ is computable if there is a Turing machine $M$ such that:

If $x \in L$ then $M$ halts on input $x$ with "YES" written on the output tape.
If $x \notin L$ then $M$ halts on input $x$ with "NO" written on the output tape.

A language $L$ is recursively enumerable if there is a Turing machine $M$ such that:

If $x \in L$ then $M$ halts on input $x$.
If $x \notin L$ then $M$ doesn't halt on input $x$.

As an example, consider the language HALT of all Turing machines that halt on the empty input. HALT is recursively enumerable, since given a Turing machine $M$, we can simulate it on the empty input. However, HALT is not decidable, as Turing showed using diagonalization.

Turing completeness is an informal concept (though it can probably be formalized). According tot he Wikipedia definition, a computing system is Turing-complete if:

Everything that can be computed by the system is computable (on a Turing machine).
Every computable language can be computed by the system.

However, we could just as well define Turing completeness with respect to recursive enumerability. The two definitions are probably equivalent for all reasonable computing systems.


What's the meaning of the name P/poly? I understand the normal definitions of the P/poly class, but I'm curious how the name came about.

The syntax of the name looks like a quotient group, but I can't think of any way to define P/poly that would use a quotient. Is 'A/B' defined to be something like "the class of problems that would be solvable as efficiently as those in A when given B amounts of advice"?

If the 'poly' in 'P/poly' refers to the polynomial amount of advice, why is it not 'P/P'? That is, why do we have two different abbreviations for 'polynomial'?

Your second intuition is correct, the $poly$ refers to the bound on the advice. The first definition of this class (that I can find) is in Karp & Lipton's "Turing Machines that Take Advice" (pdf), and in particular:

  We are mainly interested in $poly$, the collection of all polynomially-bounded functions... (p. 192)

Of course they don't give the reasons for choosing that name, so on the speculative part!

Firstly, it should be clear that $P$ and $poly$, although both derived most immediately from the word polynomial, have rather distinct meanings. $P$ as a name refers to deterministic polynomial time, and as a class is the set of all problems solvable in such. $poly$ however is a bound on the advice function, not a time-complexity statement.

This is where I speculate that the difference in names stems from; $P$ and $poly$ are quite separate concepts and it would only serve to confuse if we were to write $P/P$ - this notation would suggest some idea of $\bigcup_{k} DTIME[n^{k}]/\bigcup_{k} DTIME[n^{k}]$, which is certainly an incorrect impression to gives, whereas $P/poly$ immediately suggest $P$ which has something polynomial attached to it but is different to $P$.


What is the theoretical result of flattening a list containing only itself? Consider the following python code
X = [None]
X[0] = X

This has many fun properties such as
X[0] == X

and
X[0][0][0][0][0][0][0][0] == X

I understand how this works from a practical standpoint, as it's all just the same pointer.
Now, when flattening a list, we tend to convert things from
[[1, 2, 3], [[4, 5], [6, 7]], 8, 9]

to
[1, 2, 3, 4, 5, 6, 7, 8, 9]

In this case, I am considering flattening to be reducing a multi-dimensional list down to a single list of only non-list elements.
In practice, flattening this list would be impossible, as it would create an infinite loop.
This may be more mathematical in nature, but I'm unsure how to put it in mathematical terms. Suppose we could flatten this list, would the result simply be the empty list?
For context, I initially got this idea by considering the list
X = [[], []]
X[0] = X

It is clear to see that at each pass of flattening, the empty list that is the second element simply disappears. This lead me to think that the overall result, may be the empty list.
Could it be possible that flattening this list would theoretically produce an infinitely long list of the list itself, as in
X == [X, X, X, X, X, X, ..., X]

This is purely a fun thought exercise. Any insight and discussion on this would be appreciated.
P.S. Although I'm looking for an answer in plain terms, if anyone is more mathematically inclined, I would be interested to see how this problem could be formulated in some sort of set notation. Please feel free to point me to a relevant math exchange thread as well.
P.P.S. I would also be interested in a solid proof (not formal) to go along with the answer.

From a mathematical point of view, this is impossible: there is no such a thing as a set containing itself (in normal logic sense) or a vector who has itself as an element, so this question doesn't really mean anything outside the realm of using pointers in a list
BUT, on a second thought: I might be able to formulate what "flattening" is if you allow me to define things however I want.
Lets say our world is some graph $G$, nodes in it would be elements, and an edge $(v,u)$ would mean that the element $v$ contains the pointer to $u$. Then, in those terms, the array [[5,6],3,[7]] might look like this:

Flattening the graph in this sense means to take every non-direct child of the root node (the array's node) and make it a direct child of it.
Then, your array X looks like this:

And when you flatten it you would remain with the exact same graph, and therefore in this sense when you flatten X you would get simply X itself.
However, this is truly meaningless because it's only by the definition I just made up: you could have defined it in another way and it would have resulted in something else maybe!


Analysing Space Complexity I have to compute the space complexity of this function:

double foo(int n){
     int i;
     double sum;
     if(n==0) return 1.0;
     else
          for(i=0;i<n;i++)
              sum+= foo(i);
     return sum
}

What I have done:

When function is called, the activation record is created on the call stack. For $foo(n)$ let the size of AR be $x$.

$foo(0)$ does not place any recursive calls.
$foo(1)$ places 1 recursive call. Terminates at $foo(0)$.
$foo(2)$ places 2 recursive calls to $foo(0)$ and $foo(1)$.
$foo(1)$ places another recursive call.
Therefore total calls placed is 2+1.
$foo(3)$ places 3 recursive calls to $foo(0)$,$foo(1)$ and $foo(2)$. Therefore total calls placed is $3+0+1+3= 7$ recursive calls.
$foo(4)$ places 4 recursive calls. $4+0+1+3+7= 15$.

Hence we can see that $foo$ produces calls in the pattern: 0,1,3,7,15,31,...

This shows us that $foo(n)$ produces $(2^n)-1$ recursive calls.

If we count the total no. of recursive calls made by $foo(n)$ it becomes a geometric series and evaluates to approximately $(2^n)-n$.

Hence I am getting Space complexity to be $O(2^n)$.

However several books have merely listed the answer as $O(n!)$ without giving an explanation. I just want to know where I am going wrong in my approach.

In my opinion you are not quite right...

During the loop, when you return from foo(i), the spaces used by the call foo(i) is released (I mean, the stack pointer is back to the previous position).

So actually foo(i) only uses 1 more AR than foo(i - 1). The space cost should be O(n).

This can be verified by running the code with foo(25) and specify a stack of size 1 MB (disable all optimizations, of course). It will return normally within several seconds, without "stackoverflow". This is a proof that it's not using O(2^n) space.


$\mathsf{NL}$ versus $\mathsf{NL}[2]$ There is an equivalent definition for the class $\mathsf{NL}$ with verifier. Those verifiers are deterministic Turing machines that can read the witness tape only once in one way from left to right.

Given a function $f:\mathbb{N}\to\mathbb{N}$ we say that $\mathsf{NL}[f(n)]$ is the class obtained by the above definition but the verifier can read the witness $f(n)$ times for an input of size $n$ (i.e. when the verifier finished reading the witness the goes straight to the beginning of it).

We can see of course that $\mathsf{NL}=\mathsf{NL}[1]$.

The question is whether $\mathsf{NL}=\mathsf{NL}[2]$.

Clarification: Prove or Disprove that $\mathsf{NL}=\mathsf{NL}[2]$.

It is clear that $\mathsf{NL}\subseteq \mathsf{NL}[2]$. For the second part I tried to construct a verifier that can read the witness only once for $L\in \mathsf{NL}[2]$. I said that the verifier expects a witness of the form $w\sharp w$ and runs the $\mathsf{NL}[2]$ verifier for $L$ with $w$ and then when it finishes and wants to read it again with second copy of $w$. But the major problem with my approach is that maybe someone tricked me and put a non equal sub-witnesses and I won't be able to find out about this with $\log(n)$ space thus it does not work.

You can show that $\mathsf{NL}[2] \subseteq \mathsf{NL}$ as follows. We are given an $\mathsf{NL}[2]$ machine $M$, and we want to simulate it with an $\mathsf{NL}$ machine $M'$. The first that $M$ does is to guess the state $\sigma$ of $M'$ after it finishes reading the witness tape for the first time. It then simulates two copies of $M$, one starting at $M$'s initial state, and the other starting at $\sigma$. After going through the witness tape, it verifies that the first copy has reached $\sigma$, and that the second copy has reached an accepting state.

In this way you can show that $\mathsf{NL}[O(1)] = \mathsf{NL}$.


How does an image classifier select relevant features? I am trying to understand cascade classifiers for computer vision. I use OpenCV Traincascade for now and successfully trained some cascades.

However I am trying to grasp the whole process. One thing I do not understand about the cascade training is how the features are selected on each stage.

How does an image classifier select only relevant features?

There is no single answer.  A cascade is a very simple idea: it basically represents a bunch of classifiers, applied sequentially.

You are free to decide how each individual cascade will work.  You could design the cascade so that every classifier uses the same set of features.  Or, you could design the cascade so that each classifier has a different subset of features.  They're both considered cascades.

In the standard cascades I've seen used in computer vision, there is one set of features.  Each stage in the cascade is a single classifier which is trained on the entire feature vector.  Part of the training involves selecting a subset of the features (perhaps only a few features) to use at that stage of the cascade.  The training process is responsible for that, and there are many different algorithms for training out there.  One example is ADAboost, with decision stumps as the weak classifier; you could take a look at that to see how it works.


Designing solution to critical section problem with two semaphores vs single semaphore I came across following problem:

  Let two processes P1 and P2 are there:

+-----------------------+-----------------------+
| P1                    | P2                    |
| while(1)              | while(1)              |
| {                     | {                     |
|    //s1               |    //s3               |
|    //s2               |    //s4               |
|    //critical section |    //critical section |
|    signal(mutex1);    |    signal(mutex1);    |
|    signal(mutex2);    |    signal(mutex2);    |
| }                     | }                     |
+-----------------------+-----------------------+

  Lets mutex1 and mutex2 both are initialized to 1. So in order to avoid deadlock s1, s2, s3 and s4 (respectively) will be replaced by
  (A) wait(mutex2), wait(mutex1), wait(mutex1), wait(mutex2)
  (B) wait(mutex1), wait(mutex2), wait(mutex2), wait(mutex1)
  (C) wait(mutex1), wait(mutex2), wait(mutex2), wait(mutex2)
  (D) wait(mutex1), wait(mutex2), wait(mutex1), wait(mutex2)

Doubt

Given solution is D, which I understood why. But I am guessing whether having two semaphores mutex1 and mutex2 serve any special purpose in above code?
Does below single semaphore based programs achieve same as what is achieved by above code?

+-----------------------+-----------------------+
| P1                    | P2                    |
| while(1)              | while(1)              |
| {                     | {                     |
|    wait(mutex1);      |    wait(mutex1);      |
|    //critical section |    //critical section |
|    signal(mutex1);    |    signal(mutex1);    |
| }                     | }                     |
+-----------------------+-----------------------+

If only one semaphore is used to control the access to the critical section, it is not possible for deadlock to happen. That is why two semaphores are used in the problem statement since the problem is designed to, I assume, showcase deadlock.

A single-semaphore-based program can protect the critical section from concurrent access as well, as demonstrated by your program that uses a single semaphore.

However, some critical sections do require two or more semaphores to protect. Here is an example. There are only one fork and one knife. Each of the two diners must obtain both of them before entering the dining section. So there should one semaphore for the fork and another one for the knife. If the waiting operations of these two semaphores are not arranged in the same order for both diners, deadlock could happen. Note that one semaphore is not enough to deal with this situation correctly.


Finding the number of square prefixes of a string in linear time Let square denote a concatenation of two identical, nonempty
  strings. Given a string $w$, devise an $O(|w|)$
  algorithm that counts the number of prefixes of $w$ that are squares.

My initial idea was to use the prefix function $P$ from the Morris-Pratt algorithm ($P[i]$ is the length of the longest proper prefix of $w[1..i]$, being also its suffix), which can be calculated in linear time. Then, for each even index $i$ (we do not need to consider prefixes of odd length, as those obviously cannot be squares) the corresponding prefix $w[1..i]$ is a square if $P[i] = i/2$ and is not a square if $P[i] < i/2$.

Now, the missing case which I am unsure how to handle is $P[i] > i/2$. For example, let's consider the two strings: $abababab$ and $ababab$. The longest proper prefix-suffix of each of them is bigger than half the length of the string (6 and 4 correspondingly), yet the first one is a square and the second isn't.

Can anyone point me to an observation needed to resolve the missing part of the algorithm? Or is the idea to use the $P$ array wrong and a different approach should be applied to this problem?

Suppose there is an $O(|W|)$ algorithm that computes a slightly different prefix function: $Z[i]$ is the longest prefix of $W$ that is also a prefix of $W[i..n]$. Note then that your answer will simply be the count of indices $i$ such that $Z[i] >= i$, assuming 0-indexing.

Fortunately, such an algorithm exists and is quite elegant! It's (as always) a good idea to try to devise it on your own. If you get stuck, here's a pretty good explanation: http://codeforces.com/blog/entry/3107.


Minimising height of a 2-3-4 tree I'm wondering how a set  of keys  could  be  assigned  to  nodes  in a 2-3-4 tree  in  order  to  minimize  the  height of the tree?

Does the sequence of insertion matter with 2-3-4 trees?

The insertion order is relevant for the height of the tree.
Inserting (in this order) 1,2,3,4,5,6,7,8 gives a tree of height 3, while inserting these keys in the order 1,3,4,6,7,8,2,5 gives a tree of height 2.

In order to create a tree of minimal height, you can place the keys with ranks $\lceil \frac{n}4\rceil$, $\lceil \frac{n}2\rceil$, and $\lfloor \frac{3n}4\rfloor$ in the root, partition the remaining keys accordingly into the subtrees and apply the this recursively to each of the subtrees. Depending on the number of keys, you may have to shift a few keys around between leaves and their parents to make sure that all leaves are at the same level.


Maximum sum after splitting into subarrays taking difference of maximum and minimum of each one I was asked this in a hiring challenge that I gave today on HackerEarth:
Question/Problem statement:
Given an array, split them into several subarrays(possibly zero) such that you obtain maximum sum of difference between maximum and minimum in each of those subarrays.
Examples:
[1, 2 , 1 , 0, 5]

You can split them into 3 subarrays [1,2] , [1],  [0,5].
Through this split, you can obtain maximum sum like (2-1) + (1-1) + (5-0) = 6.
Another example:
[1,4,2,3]

You can split them into 2 subarrays [1,4] , [2,3].
Through this split, you can obtain maximum sum like (4-1) + (3-2)  = 4
Constraints:

Array length can be up to 106.
Array values can be between -109 to 109.

My attempt:
I made a brute force DP attempt which was partially accepted. Below is the approach.
long[] dp = new long[N + 1];

for(int i = N-1;i >= 0; --i){
    dp[i] = 0;
    int min = A[i],max = A[i];
    for(int j = i; j < N; ++j){
        min = Math.min(min, A[j]);
        max = Math.max(max, A[j]);
        dp[i] = Math.max(dp[i],max - min + dp[j + 1]);
    }
}

print(dp[0])

Issue:
Can anyone share with me how this can be solved efficiently?

Some case analysis shows that:

Without loss of generality, every subarray is monotone.
Without loss of generality, no monotone subarray is "broken", that is, joining two adjacent subarrays cannot result in a monotone subarray.

This reduces the number of options in dynamic programming to $O(1)$, and so should lead to an $O(n)$ algorithm.
(It seems that some case analysis is still needed. For example, if the array is $a,b,c$, where $a<b>c$, then the best solution depends on whether $a<c$ or $a>c$.)


Traveling salesman problem - negative distances allowed I am interested in the following version of TSP:

Assumption: TSP where the distances are non-negative. We know the algorithm A which computes the optional solution for such instances of TSP.
Task: State an algorithm that uses the algorithm A and computes an optimal solition for instances where negative distances are allowed.

Hint: Every TSP tour has the same number of edges. Use this to modify the weights in the graph in a way which affects all TSP tours in the same way.


Knapsack with an even number of items. I was asked in an interview to create a knapsack of only even items in n*C time, c being the capacity, n being the number of items to choose from. I tried approaching it with a third dimension, where it would be of height n and signify at each ij whether the knapsack with these maxes contains even numbers or not, but I think its incorrect and I can't code it.

Any suggestions?

You can keep two tables with $n$ rows and $C$ columns:

$DP_{even}$ that saves the best knapsack solution with an even number of itens.
$DP_{odd}$ that saves the best knapsack solution with an odd number of itens.

To fill $DP_{even}$ you look at the previous best solution of $DP_{odd}$ plus a new item, or of $DP_{even}$ if you don't take the item:
  $$DP_{even}[i, j] = max(DP_{odd}[i - 1,j - c[i]] +  v[i], DP_{even}[i - 1, j]) $$
The same idea goes for $DP_{odd}$
$$DP_{odd}[i, j] = \max(DP_{even}[i - 1,j - c[i]] +  v[i], DP_{odd}[i - 1, j]) $$

Your solution will be in $DP_{even}[n, C]$


CNNs: Why do the filters identify more complex features as the model goes on? I have a feeling that it's related to how different output layers are stacked up against one another? However, there's a missing link in that argument that I can't completely get to.

In a convolution neural network, every neuron in layer $i+1$ depends on few neurons in layer $i$. It thus aggregated local information for layer $i$. As you go through the layers, the subset of input that the neuron sees grows, and so the features depend on a larger part of the input. Eventually, neurons depend, in directly, on all inputs.


Given an array with N elements and an array of N indices find the lowest possible amounts of swaps So I have two arrays $d$ and $s$ with size $n \in \mathbb{N}$. Array $d$ contains the elements and array $s$ contains indices. Array $s$ contains all numbers from $0$ upto $n$ with no duplicates.

The indices in $s$ indicate where the elements in $d$ need to go. So the element at $d[q]$
needs to be at $d[s[q]]$ where $n > q \geq 0$.

The goal is to find the minimum amount of $q \in \mathbb{N}$ swaps such that the after all swaps are performed the above holds.

Hint: Assume you have four items that are in order a,b,c,d but you want them in order b, c, d, a. How many swaps do you need and why?

Then you generalise this to the whole array.


Without using the Time Hierarchy Theorem, is there any other way to prove P /= EXP I haven't found any way to show this was the case (that P/=EXP, without using the Time Hierarchy Theorem)
If you can find a way to show this, can you give a short explanation of this,and also if possible link a paper supporting  your conclusion.
Thank you so much

There is a way, actually! Kind of.

Consider two cases:

$P \not= NP$. This case is easy: then $P \not= EXP$, because $NP \subset EXP$.
$P = NP$. It is known that $P = NP$ implies that there is a language from $EXP$ that has circuit complexity of at least $\frac{2^n}{10n}$, so $EXP$ is not a subset of $P/\mathrm{poly}$ in this case, let alone $P$. I will recall the proof here with more details if it is necessary, but that question has already been answered, for example, here: https://mathoverflow.net/questions/57828/p-np-exp-has-circuit-size-o2n-n (the answer is pretty sketchy, though, so feel free to ask for more details).


What kind of NP problem would this be I have N by N symmetrical matrix with each side having the same items.

     A    B    C    D
A    0
B    4    0
C    8    3    0
D    3    1    8    0

In reality this would be much larger (100 x 100)

I am trying to find a subset of a fixed size in this matrix with the highest score. For example the selection ABC would be:

  AB = 4;
  AC = 8;
  BC = 3;
Total  15

It is kinda like traveling salesman problem, but with the final distance only determined by the final selection.

You can reduce clique (or independent set) to your problem, so it is NP-hard. Just take the adjacency matrix as your matrix, use the same parameter $k$ (the size of the clique), and declare that there is a clique in the graph if the maximum score is $\binom{k}{2}$.


Finding subgraph problem Is the following a familiar problem ? Given a graph $G = (V, E)$ and a capacity function $c:V \to \mathbb{N}$ find a spanning subgraph $H$ of $G$ such that $1 \leq deg_H(v) \leq c(v)$ for every vertex $v \in V$.

I would like to know if this is an NP-hard problem so any pointer to a similar problem (NP-hard or not) will be very appreciated as well.

Thank you,

GIlad

(This is edited after the conversation in the Comments below)
This is similar to degree-constrained subgraph problems. That is one direction to search in.

You can drop your 'spanning' requirement since you enforce a minimum degree of 1, which means every vertex has to be included in order to satisfy your degree constraints. It feels like it should be polytime with a max flow solution.


What is the relation between pure mathematics, applied mathematics and Cellular Automata? I was reading about pure mathematics and I am wondering if there is a relation between it and Cellular Automata.

  Broadly speaking, pure mathematics is mathematics that studies entirely abstract concepts.

For example, elementary cellular automata transforms an input of {3 cells} based on a rule set to a fractal like rule 90, how this will be described in pure mathematics perspective?

Another fractal like Pascal's Triangle can determine the coefficients that arise in binomial expansions, how it can be related to applied mathematics?

  Applied mathematics is a branch of mathematics that deals with mathematical methods that find use in science, engineering, business, computer science, and industry.

The use here of Pascal's triangle is determining the coefficients of binomial expansion, so how it can be related to applied mathematics?

The definitions given in Wikipedia are trying to convey a very abstract concept by means of examples, which, to my taste, isn't satisfactory.

Thus, before answering this question we'd need to ask ourselves why are there two in the first place.  And if there is a real need for two, then:

  How is mathematics (both pure and applied) possible?
  -- Immanuel Kant

History

The answer to the first question appears to be very involved.  In European tradition, the question goes back to Plato's distinction between the ideal and the concrete.  These roughly translate into analytic and synthetic in modern philosophical language.  Plato ultimately believed that mathematics is discovered rather than constructed, but this still puts mathematics in the realm of ideal due to Plato believing that only the ideal actually exists, and that the concrete is but an imperfect reflection of the ideal.  This was in stark contrast to the existing tradition of viewing mathematics as a practical skill of measuring and counting.

Since that time on, multiple attempts were made to either unify both, or to define one in terms of the other, or to completely dismiss one of the two.  Ultimately, in the beginning of the 20'th century the argument boiled down to the ability of defining the classical mathematics.  This split the philosophy of mathematics into logicism (with Frege as its forerunner), formalism (with Hilbert as its advocate) and psychologism (intutionism), the idea advanced by Brouwer.  Somewhat under-represented here are the universalist views held by Klein (no good online quotes, sorry).  The later is the view that synthetic and analytic truth are the same, and that when a seeming contradiction arises, it is probably because we either don't have a proper observation technique, or that we don't have a proper mathematical explanation for the observation.

The Problem

It all boils down to the question of what is truth, and are there different kinds of truths?  I will first give an example of the problem and then discuss it.

Stating that

$$
    \textit{bachelors are males}
$$

Imposes a restriction that the interpretation of "bachelors" must be a subset of the interpretation of "males", but this restriction doesn't result from logical construction of the sentence, rather it is our experience (and the reasoning non-included in this sentence) that all bachelors we've seen so far, and are likely to meet in the future will be male.  This is an example of synthetic truth.  While in this example it may look like it could be possible to resolve the problem by adding more logical predicates, the problem is in fact unresolved as of now.  More generally, this can be seen as the disparity between material implication and "real" implication.

Using material implication, typically denoted as $\implies$ we can obtain:

$$
\textit{water is wet} \implies \textit{sky is blue}
$$

And while the sentence is true in a pure logical sense.  From the perspective of non-logical, or extra-logical reasoning it is false, since the perceived properties of water have no immediate impact on the perceived color of the sky.

Lewis was, perhaps, the first to notice and try to address this general problem by creating more restricting logical systems.  Another way to approach this problem, and the stance taken by many contemporary philosophers is laid out in Two Dogmas by Quine.  To quote the later:

  Physical objects, small and large, are not the only posits. Forces are another example; and indeed we are told nowadays that the boundary between energy and matter is obsolete. Moreover, the abstract entities which are the substance of mathematics -- ultimately classes and classes of classes and so on up -- are another posit in the same spirit. Epistemologically these are myths on the same footing with physical objects and gods, neither better nor worse except for differences in the degree to which they expedite our dealings with sense experiences.

Put simpler: "pure" mathematics is just a convenience, a make-believe thing that doesn't have any factual content and has no bearings on what truth is.  Surprising as it may sound, we still use the terminology in its pre-Quinean sense.

Finally

When forced to define abstract and applied mathematics, I'd say that:

Applied mathematics is pure mathematics restricted to the synthetic truth.  I.e. the kind of mathematics that can be verified by experimentation.
Pure mathematics is the art of discovery of patterns.  The parallel between art and mathematics is not new, and, in fact, Hardy, the iconic pure mathematician holds that:

  I am interested in mathematics only as a creative art.

Your question

So, having dealt with preliminaries :) to answer your question!

Pure mathematics can find more than one interesting aspect of cellular automata to study.  There are so-called "free objects" in mathematics - those possess only one interesting property which defines them.  CA isn't one of those.  It is a whole area of research, so any example of its treatment in pure mathematics will not be exhaustive.  One such (non-exhaustive!) example is to represent this particular CA as a function in domains being CA's input and output, and study the function's behavior in the usual way (answering questions about totality, bijection etc.)
Pascal's triangle can be a subject of applied mathematics as you can easily build a physical model for it and convince yourself of the calculation that you do by means of counting the elements of the model.  Since, at least from my perspective, applied mathematics is the restricted version of pure mathematics, this means that regardless of your ability to build a physical model, this is still valid pure mathematics.

PS

The views expressed above are certainly biased and don't represent the absolute majority of the people involved in this field.  You would benefit a lot from reading literature dealing with subject matter.


Product of Lexical Specification I have a problem that asks me to consider the string abbbaacc. I'm supposed to figure out which of the following lexical specification produces the tokenization ab/bb/a/acc.

The options are:

A.
    a(b+c)*
    b+

B.
    ab
    b+
    ac*

C.
    c*
    b+
    ab
    ac*

D.
    b+
    ab*
    ac*

I just learned about REGEX, and I'm not sure about this, but to solve this problem would I just be trying see which options can make ab/bb/a/acc?

If that's correct, then would the answer be all four of them?

Since all four of them can match to ab/bb/a/acc:

A.
     a(b+c)* -> a, ab, acc
     b+ -> bb
B.
     ab -> ab
     b+ -> bb
     ac* -> a, acc
C.
     c* ->
     b+ -> bb
     ab -> ab
     ac* -> a, acc
D.
     b+ -> bb
     ab* -> a, ab
     ac* -> a, acc

I'm not sure if I'm doing this correctly.

There's not enough information here to answer the question, but I can prove a pretty good guess based on how tokenizers are typically implemented.  Generally the tokenizer will run through the list of patterns, trying each one I sequence.  If one of them matches it takes the longest possible match as a token, then starts over at the top of the list.  I surmise this is the implicit background for the question.

So forinstance if you have abbbaacc and the rules a(b|c)* and b+ in that order then you'd tokenize that as abbb/a/acc.


Is the minimal number of colors needed to color a graph some fixed number? Consider to following decision problem:

Input: Undirected graph $G=(V,E)$
Question: Is the minimum numbers of colors needed to color the vertices  (such that every two adjacent vertices aren't colored the same) exactly 2015?

Note that 2015 could be any fixed number. This number is not part of the input.
I need to understand what is the minimal complexity class that contain this problem, between $\sf P,NP,coNP,NP\cup coNP,\Sigma _{2} \cap \Pi _{2}, \Sigma _{2} \cup \Pi _{2}$.
I don't it's $\sf NP$ or $\sf coNP$ since I can't think of a verifier for both the language or it's complement. The problem is maybe in $\sf \Sigma _{2} \cap \Pi {2}$ since we can think of it as

exists $f$ some 2009-coloring function, for-all $g$, 2008-coloring function, $f$ is a correct coloring and $g$ isn't a correct coloring.

So by the above, it seems that the language is in $\sf \Sigma _{2}$, but the quantifiers order doesn't really matter here, so the language is also in $\sf \Pi _{2}$, I think.
And maybe the there is some deterministic polynomial-time algorithm?

The problem is always in $\Delta_2 = \Sigma_2 \cap \Pi_2$, as you mention. For some values of 2015 it is easier: deciding whether a graph has chromatic number 3 is NP-complete, and deciding whether a graph has chromatic number 2 or 1 is in P (since you can check whether a graph is bipartite in polytime).

Since deciding whether a graph has chromatic number 3 is NP-hard, so is deciding whether it has chromatic number 2015, by reduction: add a clique of size 2012, and connect it to all vertices; this increases the chromatic number by exactly 2012. So there is no hope for a polynomial time algorithm.


MAX 2-SAT is polynomial time reducible to 2-SAT? I know that 2-SAT is solvable in polynomial time and 2-SAT is NP-Hard.

I have issue about this statement:
MAX 2-SAT is polynomial-time reducible to 2-SAT. Can you explain to me how reduction looks like? I need the only intution about that, but not proof.

I think there is some confusion here. MAX-2-SAT is NP-Hard (and its decision version is NP-Complete), while 2-SAT is in P and hence also in NP. This means that 2-SAT is polynomial-time reducible to (the decision version of) MAX-2-SAT. The converse is not true unless P=NP.

Let $\phi$ be a 2-SAT formula with $m$ clauses.
If you really want to reduce an instance $\phi$ of 2-SAT to (the decision version of) MAX-2-SAT, then this simply amounts to checking whether at least $m$ (i.e., all) clauses of $\phi$ are satisfiable.


Failure of the Pumping Lemma On the Wikipedia page for the Pumping Lemma for Context-Free Languages, a language,
$$
\{b^j c^k d^l | j, k, l \in N\} \cup \{a^i b^j c^k d^l | i > 0, j = k = l\}
$$
is introduced. The pumping lemma proof for this supposedly fails because, given a string without a's, you can pump the b's and, given a string with a's, you can pump the a's.  In either case, all of the possible cuttings are pumpable according to the constraints of the language.

For example, given the string
$$
a^k b^k c^k d^k
$$
you can split vwx over |a| and pump, leaving |b| = |c| = |d|.

Why can the string
$$
a b^k c^k d^k
$$
not be used?

This seems to meet all the constraints of the pumping lemma, and you cannot split vwx across |a|.  If v = a then x must contain at least one b.  The string cannot be pumped for any i > 2 as the |b| will exceed the length of |c| and |b| will exceed the length of |d|.

Is there some reason that |a| > 1 or |a| = k?

The condition of the Pumping lemma is fulfilled for words of the form $ab^kc^kd^k$.

Pick $v=a$, $u=x = \varepsilon$, and $w$, $y$ arbitrary.


Is a compiler a kind of Gödel numbering program? Question: Is a compiler a kind of Gödel numbering program?
Wikipedia tells us that a compiler is: "In computing, a compiler is a computer program that translates computer code written in one programming language (the source language) into another language (the target language)". https://en.wikipedia.org/wiki/Compiler
Also wikipedia tells us: "a Gödel numbering is a function that assigns to each symbol and well-formed formula of some formal language a unique natural number, called its Gödel number". https://en.wikipedia.org/wiki/G%C3%B6del_numbering
Work done: My intuition says yes. Here is my line of thought: a programming language is a formal language. Every program is a well-formed formula and a compiler assigns each symbol of this formula to a binary representation of a number that the computer can read. (detail: a computer is a universal Turing machine, so it can perform arithmetic)
But, I don't know the details of how compilers work, so I came here to ask if my reasoning is correct.

No. Consider the following two C functions:
int f(int a) {
    return a * 2;
}

int g(int a) {
    return a + a;
}

If we're being a bit liberal here, both are "well-formed formula of some formal language". Yet most C compilers with optimization turned on will compile these two functions to the exact same code. This violates the uniqueness of a Gödel numbering.


Can languages that are not closed against the Kleene star be regular? I've been working on finding a regular expression for the following language for quite some time now ($\Sigma =\text{{0, 1}}$):

  $
\text{L = {w | the difference between the number of 0's and 1's in each prefix of the word is less than or equal to 1}}$

I haven't been able to find an expression for this particular language so far, so I was wondering if the language is regular at all.

The following came to mind, but I'm pretty dubious about its validity :

  Since $010$ belongs to said language, and by concatenation $010010$ does not, it would follow that this language isn't closed under Kleene star, hence it's not regular.

Am I wrong? If so, could you help with finding the solution to this problem?

Regarding the meaning of prefix in this context, the prefixes of the string $abcd$ are $\text{{$abcd, abc, ab, a$}}$.

No, your argument is not correct.

The "hence it's not regular" doesn't follow.  Not every regular language is closed under Kleene star.  Some regular languages aren't closed under Kleene star.  I think you've misunderstood the closure property: the closure property states "If $L$ is regular, then $L^*$ is regular".  Note that you can still have a regular language where $L \ne L^*$.

To learn how to solve this question correctly, you may want to check out our reference questions.  See especially How to prove a language is regular?, Show whether the language with almost as many 0 as 1 in every prefix is regular, Language where every prefix has almost equal a's and b's.


Is there a formal language of Combinatory Logic's expressions? The Combinatory Logic uses expressions of the form (x y) called "applications" (here, we have an "application of x to y"). Thus, the language of CL is a set of "parenthetic expressions", each looking like a string of variables to which pairs of balanced parentheses are multiply applied in an exhaustive manner (that is, you cannot insert yet another pair of parentheses).
Is there a grammar which defines this language?
(I am a novice in formal languages and I am not sure my question is correctly formulated)

The set of valid expressions in combinatory logic forms a computable formal language, and so can be described by a grammar. It is likely that this language is context-free, and so can be described by a context-free grammar.
More generally, we know the power of grammars exactly: a formal language can be described by a grammar if and only if it is recursively enumerable. So if there is an algorithm which enumerates all valid expressions in combinatory logic, then the language of all valid expressions in combinatory logic can be described by a grammar.
Even more generally, by definition, a formal language over an alphabet $\Sigma$ is just a collection of words over $\Sigma$. This means that any encoding of combinatory logic expressions which uses some fixed alphabet is automatically a formal language.


When does a PDA halt? In DFA/NFA the automaton halts when it finishes reading the string.

In a PDA there's the string and the stack. When the string is finished and there are symbols on the stack does it ignore them? Or does it have to pop them?

Or maybe does the behavior depend on whether the PDA is deterministic or not?

Here's an example to demonstrate where the ambiguity is.

It's a dumb example and it can be done with a DFA but just for demonstration.

This PDA should accept anything but the string aa.

It starts by inserting a $ to mark the bottom of the stack. Then it inserts 2 as. Then when it receives an a it pops one from a stack. It can do that twice.

Now at this point suppose that the input string was indeed aa, and that the machine reached state x and popped the two as. Now the stack has only $ in it.

Does it have to go to the next state (y) because there's a $ on top of the stack?
Or by non-determinism can it be either in x or in y?

If the latter is true then this is a wrong PDA for this language. It would accept everything.

The setup places $aa\$$ on the stack and puts the machine in state $x$. We then have this sequence of moves on input $aa$:

Consume the first $a$ and pop the stack. We're then still in state $x$ with stack contents $a\$$. No other move is possible.
Consume the next $a$ and pop the stack. We're then still in state $x$ with stack contents $\$$. No other move is possible.
Seeing a $\$$ on the stack, the only possible move is to pop the $\$$ and pass to state $y$.
In state $y$ with no further input, there are no possible moves, so the machine halts, in a non-accepting state.

Notice that there's no nondeterminism here: perhaps you were mistaken in your first bullet point: indeed there is a $\$$ in the stack at move (1), but it's not on the top of the stack.

The deeper question is exactly what model of a PDA is being used here: some people allow multiple accept states and say that the PDA accepts a string if it is in an accept state when the input has been completely consumed, others require that the stack be empty when the input has been consumed; some require a single accept state, some don't. All these models are equivalent, but you need to look closely at the definition you are using.


Inventory planning problem solved through dynamic programming I am working on problem (15-11) Inventory planning from Introduction to Algorithms (CLRS, 3rd Ed).

15-11: Inventory Planning, p.411
The Rinky Dink Company makes machines that resurface ice rinks. The demand for such products varies from month to month, and so the company needs to develop a strategy to plan its manufacturing given the fluctuating, but predictable, demand. The company wishes to design a plan for the next $n$ months. For each month $i$, the company knows the demand $d_i$, that is, the number of machines that it will sell. Let $D  = \displaystyle\sum_{i=1}^{n} d_i $ be the total demand over the next $n$ months. The company keeps a full-time staff who provide labor to manufacture up to m machines in a given month, it can hire additional, part-time labor, at a cost that works out to c dollars per machine. Furthermore, if, at the end of a month, the company is holding any unsold machines, it must pay inventory costs. The cost for holding j machines is given as a function $h(j)$ for $u = 1, 2, ... , D$, where $h(j) \ge 0$ for $1 \le j \le D$ and $h(j) \le h(j+1)$ for $j \le 1 \le D - 1$.
Give an algorithm that calculates a plan for the company that minimizes its costs while fulfilling all the demand. The running time should be polynomical in $n$ and $D$.

In other words, problem asks to create dynamic programming algorithm that solves this problem.
So far, I came up the the following solution, and not sure if it is any good.
Optimal sub-problem:
Let $MinCost(i,j)$ be the function that returns minimized cost of operation for past $i$ months, $j$ is the number of unsold machines left at the end of the month $i$.(Goal, is to calculate $MinCost(n,0)$, in other words, at the end of planning period(month $n$), there are no unsold machines.)
So, the DP recurrence is given by $MinCost(0,0) = 0$ and
$\quad MinCost(i,j) = \min\{MinCost(i-1,j-k) + c(k,j,i) + h(j) \mid 1 \le k \le D \}$
for $i+j > 0$; here, $c(k,j,i)$ is the function that calculates the costs of the production.
If my optimal sub-problem is correct, how do I create an algorithm to solve it?

CLRS give plenty of implementations in their chapter on dynamic programming, e.g. in the section on Rod cutting

recursive top-down (p363),
memoized (p365f) and
bottom-up (p366).

I suggest you try to adapt one of these.


Compute average case with best case is it correct to compute the average case time complexity of an algorithm by taking the mean of the best and worst cases ? My findings : for binary search, $\frac{\log (n) +1}{2}\in \Theta \left(\log (n )\right)\implies $ the average case is $\log (n).$

Not at all correct. For example for the naive Quicksort algorithm, anything close to the worst case is very, very, very rare. If the average time was between best and worst case, nobody in their right mind would use Quicksort.


Why do so many 8-Puzzle solving algorithms use DFS instead of BFS? I see so many 8 Puzzle Solvers use a stack instead of a queue. Why is that? If you are looking for the solution with the fewest number of moves, wouldn't the solution be at a shallower point in the tree, meaning that BFS would find it much quicker? Is there some subtlety to the problem that I'm forgetting that makes DFS a better approach?

I've been comparing performance times myself and it seems like BFS is consistently and significantly faster.

If the goal is to find the shortest solution to the 8-puzzle, DFS is indeed a very poor method.  It's not a matter of faster or slower; DFS is not correct (it finds a solution, but it's not guaranteed to be the shortest solution).  You could use BFS and that will work fine.  Even better is to use A* or some related algorithm; it will find the shortest solution even faster than BFS.

If the goal is to find any solution to the 8-puzzle, without regard to how many moves the solution takes, DFS is a fine method.  Actually, you could use either DFS or BFS for that.  The 8-puzzle has only 181440 reachable states, so the data structures won't grow too large.


λ -calculus : What is the most efficient in memory representation of functions? I would like to compare performance of function encoded (Church's / Scott's) vs classically encoded (assembler / C) data structures.

But before I do that I need to know how efficient is / can be function representation in memory. The function can be of course partially applied (aka closure).

I am interested in both the current encoding algorithm popular functional languages (Haskell, ML) use and also in the most efficient one that can be achieved.

Bonus point : Is there such encoding that maps function encoded integers to native integers (short, int etc in C). Is it even possible?

I value efficiency based on performance. In other words the more efficient the encoding is the less it influences performance of computation with functional data structures.

The thing is, there's really not much leeway in terms of function encoding. Here are the main options:

Term rewriting: you store functions as their abstract syntax trees (or some encoding thereof. When you call a function, you manually traverse the syntax tree to replace its parameters with the argument. This is easy, but terribly inefficient in terms of time and space.
Closures: you have some way of representing a function, maybe a syntax tree, more likely machine code. And in these functions, you refer to your arguments by reference in some way. It could be a pointer-offset, it could be an integer or De Bruijn index, it could be a name. Then you represent a function as a closure: the function "instructions" (tree, code, etc.) paired with a data structure containing all free variables of the function. When a function is actually applied, it somehow knows how to look up the free variables in its data structure, using environments, pointer arithmetic, etc.

I'm sure there are other options, but these are the basic ones, and I suspect almost every other option will be a variant of or optimization of the basic closure structure.

So, in terms of performance, closures almost universally perform better than term rewriting. Of the variations, which is better? That depends heavily on your language and architecture, but I suspect the "machine-code with a struct containing free vars" is the most efficient. It has everything the function needs (instructions and values) and nothing more, and calling doesn't end up doing large term traversals.

  I am interested in both the current encoding algorithm popular functional languages (Haskell, ML) use

I'm not an expert, but I'm 99% most ML flavours use some variation of the closures I describe, albeit with some optimizations likely. See this for a (possibly out of date) perspective.

Haskell does something a bit more complicated because of lazy evaluation: it uses Spineless Tagless Graph Rewriting.

  and also in the most efficient one that can be achieved.

What is most efficient? There is no implementation that will be most efficient across all inputs, so you get implementations that are efficient on average, but each will excel in different scenarios. So there's no definite ranking of most or least efficient.

There's no magic here. To store a function, you need to store its free values somehow, otherwise you're encoding less information than the function itself has.
Maybe you can optimize away some of the free values with partial evaluation but that's risky for performance, and you have to be careful to ensure that this always halts.

And, maybe you can use some sort of compression, or clever algorithm to gain space efficiency. But then you're either trading time for space, or you're in the situation where you've optimized for some cases and slowed down for others.

You can optimize for the common case, but what the common case is can change on the language, area of application, etc. The type of code that's fast for a video game (number crunching, tight loops with large input) is probably different than what's fast for a compiler (tree traversals, worklists, etc.).

  Bonus point : Is there such encoding that maps function encoded integers to native integers (short, int etc in C). Is it even possible?

No, this is not possible. The problem is that the lambda calculus does not let you introspect terms. When a function takes an argument with the same type as a Church-numeral, it needs to be able to call it, without examining the exact definition of that numeral. That's the thing with Church encodings: the only thing you can do with them is call them, and you can simulate everything useful with this, but not without a cost.

More importantly, the integers occupy every possible binary encoding. So if lambdas were represented as their integers, you'd have no way of representing non-church-numberal lambdas! Or, you'd introduce a flag to denote whether a lambda is a numeral or not, but then any efficiency you want is probably gone out the window.

EDIT: Since writing this, I've become aware of a third option for implementing higher-order functions: defunctionalization. Here, every function call turns into a big switch statement, depending on which lambda abstraction was given as the function. The tradeoff here is that it's a whole program transformation: you can't compile parts separately and then link together this way, since you need to have the complete set of lambda abstractions ahead of time.


Linearithmic lower bound for 1-D "distinct" closest pair of points problem The 1-D distinct closest pair of points problem is as follows: Given a set of n distinct integer points on real line, find a pair of points with the smallest distance between them, here the distance between two points p_i and p_j is absolute difference of their values, i.e, |p_i-p_j|.

A naive way to solve this problem is to sort the points and check distance of each consecutive points in sorted order and take the minimum of such distances and this takes O(nlog n) time.

My question is can we do better than that? Can we solve it in o(n log n)(note the little-oh) time? If not, then how to show an omega(nlog n) time bound for this problem?

Note that, if the distinctness criteria was not there we could have shown a lower bound using Element Distinctness Problem.

Given $n$ integer points $p_1,\ldots,p_n$, not necessarily distinct, consider the set of points $2np_1+1,2np_2+2,\ldots,2np_n+n$. The new points are distinct by construction, and the minimal distance is smaller than $n$ iff the original points were not distinct. So an algorithm for your problem can be used to solve element distinctness.


What are some real world examples of nearly sorted lists I found that sorting algorithms such as Insertion Sort and Djikstra's Smoothsort approach O(n) complexity when the list is nearly sorted. What are some real world scenarios where a list is nearly sorted?

What about log files described in AWStats logfile analyzer 7.5 Documentation?

  An error log file is not always completely sorted but only "nearly" sorted because of cache and writing log engines used by a server.


Correct nomenclature: Hamilton path, Hamilton's path or Hamiltonian path? What is the correct way?
Hamilton path, Hamilton's path or Hamiltonian path?
To be clear, I am referring to the correct way to name a graph such that there exists a single path (without repeated vertices) through all the vertices.

In Wikipedia it says "Hamiltonian path", whereas in an article I found "Hamilton path".

I have seen both Hamilton path (or Hamilton cycle) and Hamiltonian path (or Hamiltonian cycle). A graph, however, is always Hamiltonian (if it contains a Hamilton/Hamiltonian cycle). Consider for example the titles of two papers: Hamiltonian cycles in random regular graphs (Fenner & Frieze) and Generating and counting Hamilton cycles in random regular graphs (Frieze, Jerrum, Molloy, Robinson & Wormald). Alan Frieze apparently doesn't care too strongly about the issue.

However, I've never seen Hamilton's path or cycle.


Running time based on smallest subtree I've constructed an algorithm on (rooted) binary trees, where the running time at a node depends on the size of its smaller subtree, where we compute from each leaf upwards towards the root.
More specifically, at each node, a constant amount of time is required for each node in the smallest of its 2 subtrees.

The running time for a tree with $n$ nodes is then easily bounded by $O(n^2)$, however, I conjecture that the running time is bounded by $O(n \log n)$, since I think $\sum_{x\in V(T)}\min(|V_l(x)|, |V_r(x)|) \leq O(n \log n)$ holds.

How would I go about proving this?

A nice question!

As the OP has pointed out, it is enough to show the following inequality for any tree $T$ of $n\gt0$ nodes, where for any node $x$, $l(x)$ is the number of nodes in the left subtree of $x$ and $r(x)$ is the number of nodes in the right subtree of $x$.

$$\sum_{x\in V(T)}\min(l(x), r(x)) \leq n \log n$$

Proof by mathematical induction.

base case when $n=1$. Both side is 0.
Suppose it is true when the number of nodes in the tree is smaller than $n$. Let us consider a tree $T$ with $n>1$ node. Let the left subtree $T_l$ of the root node has $p$ node and the right subtree $T_r$ of the root node has $n-1-p$ node. There are two cases.

$p=0$ or $p=n-1$ is easy.
$p\neq0$ and $p\neq n-1$. (This case is only possible when $n\ge3$.) WLOG assume $p\le n-1-p$; otherwise we can switch the left subtree and the right subtree.

$$\begin{aligned}
&\sum_{x\in V(T)}\min(l(x), r(x)) \\
&= \min(p, n-1-p) + \sum_{x\in V(T_l)}\min(l(x), r(x))+\sum_{x\in V(T_r)}\min(l(x), r(x))\\
&\leq p + p\log p +(n-1-p)\log(n-1-p)\\
&= p + p\log p +p\log(n-1-p) + (n-1-2p)\log(n-1-p)\\
&= p + p\log (p(n-1-p)) + (n-1-2p)\log n\\
&\le p + p\log \left((\frac{n-1}2)^2\right) + (n-1-2p)\log n\\
&\le p + 2p\log \left(\frac{n}2\right) + (n-1-2p)\log n\\
&= (1- 2\log2)p + (n-1)\log n\\
&\le n\log n
\end{aligned}$$

Proof is done. Note that we have actually proved a tighter upper bound, $\frac1{2}n \log_2 n$.


Where can I find rules for source to source transformation optimization rules? Upon reading  Do source code optimizers exist? I knew that such programs existed but the ones I have worked with use a set of rules to drive a transformation algorithm. Ira Baxter provided a link to the tools running the algorithms with his answer but what I was more after from the question was the rules. In the comments Ira noted the  Irvine Program Catalog.

Are there any more papers, sites, etc. that list such rules?

I will accept any answer but have a preference for rules used with functional languages.

Martin Feather's thesis and papers (and similar theses from the 70s) are full of examples of
such rules for functional languages.  See http://dl.acm.org/citation.cfm?doid=357153.357154. (pdf)  Most of the formal types like such (functional) rules.

More recent would be any work by Martin Ward using his functional language WSL including his thesis.   See http://www.cse.dmu.ac.uk/~mward/martin/papers.

If I were you, I'd look to the Haskell community, which is always trying to optimize functional programs, and particularly to the Haskell compilers which implement many of these ideas.

But I get the impression you're looking for the the book of program optimization rules.  There are some pretty standard ones based basic algebra as applied to integers, etc.
And you can see a bunch of these coded explicitly for DMS in an example of how to define algebra to a program transformation system: Algebra as a DMS domain.

You aren't likely to find "the general book" for the following reasons:

Every syntax formalism in which rules are represented makes a choice about how to write down the details of the rules.  Nobody has agreed on a universal notation; that's not a flaw of software engineering, the mathematicians haven't figured this out yet either.  So any rules you find will be cast using a particular encoding scheme.  Unless you get the tool that uses this encoding scheme, you probably can't use the rules. (See the algebra example for a specific encoding scheme.)
"Optimizations" are essentially about equivalent sequences of operations where one sequence is "cheaper" than another by some metric (smaller number of steps, less computation, less memory, less heat, less code, ...)  The number of entities for which you can define operations is boundless:  booleans, naturals, floats, strings, structs, crossproducts, linkedlists, arrays, arbitary compositions of the above, each with predicates possibly constraining them to a subset (eg., all naturals less than 10).  The number of operations you define is equally boundless.  Which ones are worth writing down?
A variation on the above theme is that the syntax and semantics of the programming languages you want to manipulate are egregiously different (did we really need both Java and C#?), or deeply semantically different (COBOL and Prolog, for example), or just outright egregious complex (consider C++11).  So your rules need to be case in a form that is dependent on your target language syntax and semantics.  And there are thousands of those.
Source to source transformations seem to offer nirvana, but they have limitations. In particular, most ways you can represent a transformation to be matched against code, what it can match has a limited radius of the match.  If your optimization needs information from "far away", e.g., beyond the radius of what you can write in the rules, no single rule can realize your optimization.  You can only succeed by composing more than one rule (and you can succeed spectacularly in theory because Post systems are Turing capable, and most rewrites are Post systems almost trivially).   However, writing long strings of transformations to achieve an effect is much like writing long sequences of Turing machine steps: you really, really don't want to do that.  So in practice transformation systems usually offer the ability to compose arbitrary code procedures, and source transformations, that make "bigger" source-to-source transformations.  So now your real transformations are mixed code and rewrites.  Using code from one of those thousands of programming languages. (oops).

My belief (uh-oh, opinion coming up) is that source-to-source transformation tools are really useful, because you can build program manipulation engines with them more easily (by a lot!) than with any procedural code or any other techniques I know about.  The differences in syntax and semantics of the target languages means you are pretty much doomed to not find such transformations off the shelf (well, you can pray for C++ to become stable for 20 years, and then maybe you have a chance).  So, what is needed is a system which will let you define the rules you need, for the language you want to manipulate, relatively easily, when you need them. (And I've spent the last 18 years of my life building such a system).

Good luck finding the universal ruleset.


Is it possible to prove Language L context-free? Give a question:
Language L= {a^n b^(n+m) a^m}, where both n and m are >=0. Is L context-free or not.

If the answer is yes, can I use the following PDA to prove it?

Since {a^n b^(n+m) a^m}={a^n b^n b^m a^m}, in the PDA, we first push n a's onto the stack. Then, we pop n a's from the stack by reading n b's. Next, we push m b's onto the stack, and we pop m b's from the stack by reading m a's. Finally, the strings will be accepted in q5.

Conversely, if the language is not context-free, should i use pumping lemma to prove it?

Thank you!

S → AB
A → aAb | ε
B → bBa | ε

This will be the Grammar for that language which follows the context free grammar rules, so the language generated will be CFL.


How do I calculate the time complexity of this memoized algorithm? The problem is: count all increasing subsequence of s.
def main():
    print(count([3,2,4,5,4]))

def count(s: list) -> int:
    n = len(s)
    counter = 0

    result = {}

    if n == 0:
        return 0

    for i in range(n):
        counter += recurse(s[i+1:], s[i], result)

    return counter

def recurse(s: list, x: int, result: dict) -> int:
    n = len(s)
    counter = 0

    if n in result:
        return result[n]

    if n == 0:
        return 1

    for i in range(n):
        if s[i] > x:
            counter += recurse(s[i+1:], s[i], result)

    result[n] = counter + 1

    return counter + 1

Can anyone help me what is the time complexity of this algorithm?
What I know is T(count()) is O(n) * T(recurse(n)). Correct me if I'm wrong, T(recurse(s1, ...)) will be O(1) if I already calculated recurse(s1, ...) and that will make T(count(s)) = O(n).

Usually when trying to figure out a dynamic programming solution's time complexity, you need to find two values:

The number of elements that will be calculated (or a bound on this number. Notice that "elements that would be calculated" refers to the elements you save with the memoization technique)
The time it takes to process an item, assuming you know the results of every recursive call it would have done (or a bound on this number)

In your case:

The memoization saves elements up to $n=len(s)$ (every element in the dictionary is smaller or equal to $n$ and therefore you will calculate at most $n$ values)
Processing each element takes $O(n)$ time (in the recurse function, there is a for i in range(n):)

Therefore, for every new element you calculate (there are at most $n$ such values) you will spend $O(n)$ time, and thus the algorithm will take $n\cdot O(n)=O(n^2)$ in the worst case analysis.
Notice this is not an improvement from any naive algorithm that goes through every sublist - as by combinatorical counting there are ${n\choose2}={n!\over2!\cdot(n-2)!}={n\cdot(n-1)\over2}=O(n^2)$ different sublists


3-SAT to Max-2-SAT Reduction I'm trying to find reduction from 3-SAT to Max-2-SAT, so far no luck.
Let me first describe it.

3-SAT: Given a CNF formula $\varphi$, where every clause in $\varphi$ has exactly 3 literals in it, one should determine if there exist an assignment that satisfies it.
Max-2-SAT: Given a CNF formula, where every clause in $\phi$ has exactly 2 literals in it, and a positive number $k$, one should determine if there exist an assignment that satisfies at least $k$ clauses.

Let me first show what I have tried so far.
Given $\varphi=\wedge _{i=1}^{n}C_i$ where: $C_i=(l_{i_1}\vee l_{i_2} \vee l_{i_3})$,
I set: $\phi=\wedge _{j=1}^{3n}D_i$, where: $D_i=(l_{i_1}\vee l_{i_2})\wedge(l_{i_1}\vee l_{i_3})\wedge(l_{i_2}\vee l_{i_3})$ and $k=2n$.
It's quite easy to see that this will not work...
Although, if there exist an assignment which satisfies $\varphi$ it means there exist an assignment that satisfies $k=2n$ clauses in $\phi$, the second direction is not true.
I found several reductions online (such as this, for example), but none of them were useful since in my problem, each clause in $\phi$ must have exactly two literals, where in the link above, the formula can also contain 1-length clause in it.
I could really use some help here.

Hint: Replace a singleton clause $a$ with $a \lor b$ and many copies of $\lnot b \lor c$, $\lnot b \lor \lnot c$.

Reductions without extra variables don't work even when singleton clauses are allowed. There are five types of clauses: $\ell_1,\lnot \ell_1, \ell_1 \lor \ell_2$, $\ell_1 \lor \lnot \ell_2$, $\lnot \ell_1 \lor \lnot \ell_2$. Suppose that $k$ of $\ell_1,\ell_2,\ell_2$ are true. The probability that a random clause of each type is true is:
$$
\begin{array}{c|cccc}
k&0&1&2&3\\\hline
\ell_1 & 0 & 1/3 & 2/3 & 1 \\
\lnot \ell_1 & 1 & 2/3 & 1/3 & 0 \\
\ell_1 \lor \ell_2 & 0 & 2/3 & 1 & 1\\
\ell_1 \lor \lnot \ell_2 & 1 & 1/3 & 1/3 & 1\\
\lnot \ell_1 \lor \lnot \ell_2 & 1 & 1 & 2/3 & 0
\end{array}
$$
We would like to take a convex combination of these rows which is of the form
$$ \begin{array}{cccc} \alpha & \beta & \beta & \beta \end{array} $$
However, all such convex combinations have $\alpha = \beta$.


Constructing preorder traversal from postorder of a Binary Search Tree in O(n) We are given postorder traversal of a Binary "SEARCH" Tree (in an array) and we want to find (print) its preorder traversal.

A very naive solution is to check from end until we find element less than root so we can find left and right subtree and call the function on them. This is $O(n^2)$. Another way is to generate the BST from its postorder and then generate the preorder from postorder. it is $O$$($$n log n$$)$ because for generating tree we need $O(n log n)$ and for preorder traversal we need $O(n)$ and $O(n + n log n ) = O(n logn)$.

I think we can do it better in $O(n)$ because there is a lot known about the nature of the binary search tree and this extra information must help somehow. but I don't know how to use information we know about BST and implement this problem in $O(n)$.

This can indeed be solved in $O(n)$ time. What you mentioned (checking value of root, calling recursively for left and right subtree) almost works, the issue is just that we don't know the size of the right subtree, so we cannot immediately recursively solve the left subtree as we don't know where it ends. But this is not an issue: Just recursively solve the right subtree first, then have that return the subtree's size.

The following C++ program should solve the problem in $O(n)$. Please note that while I tested a few inputs but there could be bugs, though the idea behind the algorithm works for sure.

#include <iostream>
#include <vector>
using namespace std;

// Finds preorder traversal of a subtree of a binary search tree given the postorder traversal
// res: Vector to write preorder traversal to
// postorder: Vector containing the postorder traversal
// j: Position in array to write last node in preorder traversal to
// hv: Maximum value of a node in this subtree
// lv: Minimum value of a node in this subtree
// b: Position where this subtree ends in the postorder traversal
// Returns size of the subtree called on
int preorder(int b, int lv, int hv, int j, const vector<int>& postorder, vector<int>& res) {
    if (b < 0 || postorder[b] < lv || postorder[b] > hv) return 0;
    int rs = preorder(b-1, postorder[b], hv, j, postorder, res); // Size of     right subtree
    int ls = preorder(b-1-rs, lv, postorder[b], j - rs, postorder, res); // Size of left subtree
    res[j - ls - rs] = postorder[b];
    return ls + rs + 1;
}

int main() {
    int n; // Size of the tree
    cin >> n;

    vector<int> po(n); // Postorder
    for (int i = 0; i < n; ++i) cin >> po[i];

    int lv = po[0]; // Minimum value in the tree
    int hv = po[0]; // Maximum value in the tree
    for (int i = 0; i < n; ++i) {
        lv = min(lv, po[i]);
        hv = max(hv, po[i]);
    }

    vector<int> res(n); // Preorder
    preorder(n-1, lv, hv, n-1, po, res);
    for (auto v : res) cout << v << ' ';
    cout << '\n';
}

This is clearly $O(n)$, since the function "preorder" gets called exactly once per node, and (outside recursive calls) does $O(1)$ work.


Optimization problem vs decision problem - reduction Assume we have an optimization problem with function $f$ to maximize.

Then, the corresponding decision problem 'Does there exist a solution with $f\ge k$ for a given $k$?' can easily be reduced to the optimization problem: calculate the optimal solution and check if it is $\ge k$.

Now, I was wondering, is it always possible to do the reduction (in polynomial time) the other way around?

For an example consider MAX-SAT: to reduce the optimization problem to the decision problem we can do a binary search in the integer range from 0 to the number of clauses. At each stoppage $k$ we check, with the decision problem solver, if there is a solution with $\ge k$.

There are a few conditions you would need to specify for this to even work, most importantly, that your function does have a maximum, otherwise you could try all k and end up going off into infinity. Likewise, you'd probably need to assume that f is only producing outputs on the integers or some other countable set.

If we're doing any sort of binary search, I think it is going to be exponential in the worst case unless we know an upper bound to start with. Assuming f returns numbers, finding the upper bound is going to be linear in terms of the maximum value. However, that means it's exponential in terms of the string-representation of the maximum value.

If we know an upper bound for the maximum of f, I can't see any reason why you couldn't do binary search to find it, but even then, it is polynomial in the upper bound, and could still be exponential in the length of the input, as opposed to the output.


Complexity of the algorithm to find occurences of a given number in a given array I have an algorithm that I think its complexity is O(n^2). However, our teacher insists that the algorithm takes O(n) time. How can it be? Here is the pseudo-code of the algorithm:

// A is the input array.
// |A| is the size of the input array.
i = 1
j = 1
m = 0
c = 0
while i < |A| {
    if A[i] == A[j]
        c = c + 1
    j = j + 1

    if j > |A|
        if c > m
            m = c
        c = 0
        i = i + 1
        j = i
}
return m

If we retain only the references to i and j, the code reduces to

i = 1
j = 1
while i < |A|
    j = j + 1
    if j > |A|
        i = i + 1
        j = i

This is equivalent to

for i in [1 |A|]
    for j in [i |A|]

... which is gone through about ${|A|^2 \over 2}$ times. So it is $\Theta(n^2)$: both $O(n^2)$ and $\Omega(n^2)$.

The algorithm appears to be looking for the maximum number of replicates in the array. There are faster ways to do so. A good hash map has (average) constant time access/update. So you can count how many of each thing are in the array in $\Theta(n)$ time. You can then find the maximum in $\Theta(n)$ time too.

So the problem admits a $\Theta(n)$ solution, but what you have been offered isn't it.


Linear time algorithm for least positive integer missing from array Design a linear time algorithm for finding the least positive integer missing from an unsorted array. Changes in the array are allowed.
For example, for the array -10,-1,2,3,6,30, the answer is 1.

I thought about finding the maximum and minimum numbers in the array (this is $\Theta(n)$), then a loop from the minimum number to the maximum number, and in every iteration, check if the current number is in the array, but this will take $\Theta(n^2)$.

Hint (if extra memory is allowed): It is enough to determine which of the elements $1,\ldots,n$ are in the input array. Using an auxiliary array, you can accomplish this in $O(n)$.


Can a Turing Machine tell if an input string is a description of itself? Can some Turing Machine $M$ with description $\langle M\rangle$, check if an input string $w$ is a description of itself? That is, can $M$ be constructed such that $M$ can tell if $w$ = $\langle M\rangle$?

The closest related problem I could find was: Can I construct a Turing machine that accepts only its own encoding?

But I want to consider the case where $M$ must recognize its own description as an intermediate step, and then accept or reject based on that and some additional criteria. Is this possible?

The answer is yes, and this is a standard application of the recursion theorem - the slogan for this theorem being, "you can assume at the beginning of your construction that you know what the index of the construction will be at the end."

Let me outline how it is applied in this case:

You have a description of the machine you want, with a "gap" - a point where you want to insert the code for the machine itself. This really defines a family of machines, where we have $M_k$ being the version where we stick in the number "$k$."

The process of building $M_k$, given $k$, is recursive; that is, the function sending $k$ to the index for $M_k$ is recursive.

Now on the face of it, that doesn't help since we just get an infinite regress: $M_0$ has index $5$, $M_5$ has index $17$, $M_{17}$ has index $2$, ... However, the recursion theorem lets us catch our tail. Let $f$ be the recursive function mentioned above, which sends $k$ to the index for $M_k$. Then by the recursion theorem, we get a fixed point for $f$: some $c$ such that the machine with index $c$ behaves identically to the machine with index $f(c)$.

But this means exactly that the machine $M_c$ - whose index is $f(c)$ - behaves as if it was given its own index! (Intuitively, it "thinks" it has index $c$, and that's good enough: index $c$ and index $f(c)$ are "the same.")