Why are these (lossless) compression methods of many similar png images ineffective? I just came across the following thing: I put multiple identical copies of a png image into a folder and then tried to compress that folder with the following methods:

tar czf folder.tar.gz folder/
tar cf folder.tar folder/ && xz --stdout folder.tar > folder.tar.xz (this one works well for identical images, however for similar images the gain is zero)
zip -r folder.zip folder/

When I checked the size of the .tar.gz, .tar.xz, .zip I realized that it is almost the same as the one of folder/.
I understand that a png image itself may have a high level of compression and therefore cannot be compressed further. However when merging many similar (in this case even identical) png images to an archive and then compressing the archive I would expect the required size to decrease markedly. In the case of identical images I would expect a size of roughly the size of a single image.

Have a look at how compression algorithms work. At least those in the Lempel-Ziv family (gzip uses LZ77, zip apparently mostly does as well, and xz uses LZMA) compress somewhat locally: Similarities that lie far away from each other can not be identified.

The details differ between the methods, but the bottom line is that by the time the algorithm reaches the second image, it has already "forgotten" the beginning of the first. And so on.

You can try and manually change the parameters of the compression method; if window size (LZ77) resp. block/chunk size (later methods) are at least as large as two images, you will probably see further compression.

Note that the above only really applies if you have identical images or almost identical uncompressed images. If there are differences, compressed images may not look anything alike in memory. I don't know how the PNG compression works; you may want to check the hex representations of the images you have for shared substrings manually.

Also note that even with changed parameters and redundancy to exploit, you won't get down to the size of one image. Larger dictionaries mean larger code-word size, and even if two images are exactly identical you may have to encode the second one using multiple code-words (which point into the first).


How do I show this variant of the longest path problem is NP-hard? The problem is as follows:

"Given a weighted graph G and a path p, show that p is the longest simple path in G."

I'm thinking a reduction from HAMPATH would work, but after 3 hours of racking my brain over this, I have no idea how to do it. What makes the reduction difficult is that I'd need to somehow "know" the path, since the input to this longest path variant requires the path along with the graph.

Any tips/hints/help would be appreciated.

Hint 1. The graph doesn't have to be connected.

Hint 2. Mouse-over the following for a slightly more detailed hint.

   Arrange for there to be two components. One of them has quite a long path, which you can easily find.


How many different (full/complete) in-order binary-trees do exist? Given be a binary tree whose elements printed in-order results in [1,2,3,4].
Q1: How many different binary-trees do exist?
Q2: How many different complete binary-trees do exist?
Q3: How many different full binary-trees do exist?

For Q1 I was able to find a solution, by using the catalan number formula:
c(n) = (2n)! / ((n + 1)! * n!) → c(4) = 14.

For Q2 and Q3 however I was not able to find an answer to those problems.
Do general formulas for n elements even exist?

Definition of full and complete.

Q1: How many different binary-trees do exist?
A1: c(n) = (2n)! / ((n + 1)! * n!) → c(4) = 14

Q2: How many different complete binary-trees do exist?
A2: Exact one:

;       (3)        L0: full
;      / | \
;   (2)  |  (4)    L1: full
;   /|   |   |
; (1)|   |   |     L2: not full (Node 2 is missing right child)
;  | |   |   |
;  1 2   3   4     Complete?: Yes, because all (but last) levels are full.

Q3: How many different full binary-trees do exist?
A3: If n is odd: c((n-1)/2) else 0. n = 4 therefore 0. Reference

Thanks to YuvalFilmus for the help!


time complexity when power is involved in iteration How do I calculate the time complexity of the following method? Would you please provide explanation? I know it's going to involve sqrt(n) * <something>. I Just don't know what that <something> is.

public void timeComplexity(int[] arr){
    int n = arr.length;
    int sqrt = (int) Math.sqrt(n+1);
    for(int i=2; i<sqrt; i++){
        for(int k= (int) Math.pow(i,2); k < n; k+=i){
            //do some constant time work
        }
    }
}

Also consider the following two variations:

k starts at i (k=i or k=3) instead of k= (int) Math.pow(i,2).
k is incremented by some constant k++ instead of the variable i k+=i

You are interested in several different variants. I'll show you how to estimate the running time in the first one, you do the rest. In fact, I will only estimate the number of times that the inner loop is run, which is
$$
\sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \left \lceil \frac{n-i^2}{i} \right \rceil.
$$
To obtain this, you need to figure out the number of iterations in loops of the form for (x = a; x < b; x += c) (assuming $a \leq b$ and $c \geq 1$), which is a nice exercise.

Using $x \leq \lceil x \rceil < x+1$, we see that the sum above can be bounded by
$$
\sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \frac{n-i^2}{i} \leq
\sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \left \lceil \frac{n-i^2}{i} \right \rceil <
\lfloor \sqrt{n+1} \rfloor-2 + \sum_{i=2}^{\lfloor \sqrt{n+1} \rfloor-1} \frac{n-i^2}{i}
.
$$
Using $m = \lfloor \sqrt{n+1} \rfloor - 1$, we can evaluate the left sum as follows:
$$
\sum_{i=2}^m \frac{n-i^2}{i} = n \sum_{i=2}^m \frac{1}{i} - \sum_{i=2}^m i =
n (H_m-1) - \frac{m(m+1)}{2} + 1,
$$
where $H_m$ is the $m$th harmonic number. It is well-known that $H_m = \log m + O(1)$, and so we can estimate the sum by $\frac{1}{2}n \log n - \Theta(n)$, skipping a few steps. A similar bound holds for the right sum, since the additional term is only $\Theta(\sqrt{n})$. Altogether, we deduce that the inner loop runs $\frac{1}{2}n\log n - \Theta(n)$ many times.


Algorithm to compact/simplify ranges? I'm trying to create an algorithm in C# that given a list of ranges (segments) it produces a compacted list of them:

Example 1

Input:
[1, 3], [2, 6]

Output:
[1, 6]

Example 2

Input:
[1, 2], [2, 3]

Output:
[1, 3]

Example 3

Input:
[1, 2], [4, 6], [2,4]

Output:
[1, 6]

Too visualize the problem better, this problem is similar to this:
if you have a shop that opens from Monday to Tuesday and from Tuesday to Sunday, then you can say that your shop opens from Monday to Sunday. This is what the algorithm should do: to simplify the ranges and give the minimum set of merged ranges.

I'm absolutely lost on how to approach this problem. Thanks in advance.

Make a list of all $2n$ beginning and ending points of the $n$ ranges.  Record each as a (position, type) pair.
Sort this list by position, with starting points comparing below ending points when positions are equal.
Loop through the sorted list, incrementing a counter variable (initially zero) whenever you see a beginning point and decrementing it whenever you see an ending point.  On a 0->1 transition of this variable, output the current position as a starting point.  On a 1->0 transition, output the current position as an ending point.


Is $A\odot B\odot C = A\oplus B\oplus C$? (The notations used:

$\oplus$ is XOR operator
$\odot$ is XNOR operator)

I was solving a problem, where they asked which of the given options give equation for the difference of full subtractor. The circuit in the solution option was:

For me the first line:

  $(x'y'+xy)'z'+(x'y'+xy)z$

looked more like $x\odot y\odot z$. But I know the difference of full subtractor is $x\oplus y\oplus z$. So I tried to evaluate both separately:

  $x\oplus y\oplus z$
  $= (x'y+xy')\oplus z$
  $= (x'y+xy')'z+(x'y+xy')z'$
  $= (x'y)'(xy)'z+(x'y+xy')z'$
  $= (x+y')(x'+y)z+(x'y+xy')z'$
  $\require{enclose}= \enclose{updiagonalstrike}{xx'z}+xyz+x'y'z+\enclose{updiagonalstrike}{yy'z}+x'yz'+xyz'$
  $= xyz+x'y'z+x'yz'+xy'z'$   ...equation$(I)$

  $x\odot y\odot z$
  $=(x'y'+xy)\odot z$
  $=(x'y'+xy)'z'+(x'y'+xy)z$ (This is same as first line in the equations given in the figure above)
  $=(x'y')'(xy)'z'+(x'y'+xy)z$
  $=(x+y)(x'+y')z'+(x'y'+xy)z$
  $\require{enclose}=\enclose{updiagonalstrike}{xx'z}+xy'z'+x'yz'+\enclose{updiagonalstrike}{yy'z'}+x'y'z+xyz$
  $=xy'z'+x'yz'+x'y'z+xyz$    ...equation$(II)$

To my eyes, both equations $(I)$ and $(II)$ looks the same. So I went to wolframalpha and prepared truth table for both of them.

$x\oplus y\oplus z$

$x\odot y\odot z$

And they correctly look complement of each other. Then why the given answer and my calculations equates $x\odot y\odot z$ with $x\oplus y\oplus z$? What stupidity I am doing here?

Yes, $x\odot y\odot x = x\oplus y\oplus z$, where $\oplus$ is the XOR operator and $\odot$ is the XNOR operator.

In fact, it is easy to see that both sides of the equation are always equal. Note that $a\odot b$ tests whether $a$ is the same as $b$ while $a\oplus b$ tests whether $a$ is different from $b$. So we know $a\odot b= \overline{a\oplus b} = \overline a\oplus b$. So, $x\odot y\odot z = (x\odot y)\odot z =\overline{x\oplus y}\odot z = \overline{\overline{x\oplus y}}\oplus z = x\oplus y\oplus z$. (We do not even use the associativity of $\odot$ nor that of $\oplus$.)

Let $n\geq 1$. We can show the following easily by induction on $n$.
$$x_1\oplus x_2\oplus\cdots\oplus x_n = (\text{ number of true's in } \{x_1,\, x_2,\, \cdots,\, x_n\} \text { is odd }) $$
$$x_1\odot x_2\odot\cdots\odot x_n\, = (\text{ number of false's in } \{x_1,\, x_2,\, \cdots,\, x_n\} \text { is even }) $$

So in general, we have the following, which can be shown directly by induction on $n$ as well.
$$\begin{align}
\text{for odd } n,\ \
&x_1\oplus x_2\oplus\cdots\oplus x_n = x_1\odot x_2\odot\cdots\odot x_n\\ \text{for even } n,\ \
&x_1\oplus x_2\oplus\cdots\oplus x_n = \overline{x_1\odot x_2\odot\cdots\odot x_n} \end{align}$$

Now let us come to the real question. Why does wolfram alpha give a completely different output for $x\odot y\odot z$ at http://www.wolframalpha.com/input/?i=x+xnor+y+xnor+z?

As Peter Taylor has noticed on that web page, Wolfram parses "x xnor y xnor z" very differently from what we might have expected, "(x xnor y) xnor z". Wolfram parses it as "Not(x Xor y Xor z)" in text notation or, what is the same, "¬($x \underline\vee y\underline\vee z)$" in symbolic notation. This is not mentioned in its documentation for Xnor operator at http://mathworld.wolfram.com/XNOR.html nor at http://www.wolframalpha.com/input/?i=xnor. One might suspect this is an implementation bug of Wolfram.

However, it turns out this is a feature by design (or possibly an unintentional side-effect) of Wolfram. Its documentation for Operator Input Forms shows the following lines, where the small wedges at the end of each line means "built-in meaning exist".  So after all Wolfram has decided to treat "x xnor y xnor z" as "not(xor(x,y,z))" instead of the more common "(x xnor y) xnor z" as a surprise to unsuspecting users such as OP and me! (Of course, "more common" is only in the eyes of some people. It is quite possible Wolfram's interpretation is more common in other situations.)

One might wonder why Wolfram has made such a strange and uncommon choice. Here is my speculation, my pure shallow speculation.

Wolfram defines Xor for multiple argument as "true if an odd number of its arguments are true and false otherwise", probably along the approach of a BooleanCountingFunction. It also parses and evaluates expressions such as "x1 xor x2 xor x3 xor x4 xor x5" (which everyone agree must be "((((x1 xor x2) xor x3) xor x4) xor x5)") as "Xor(x1, x2, x3, x4, x5)", which is easier to define and faster to compute especially when the number of arguments becomes larger. All is going well without inconsistency for Xnor. Xnor looks very similar to Xor. So, (again just my speculation), Wolfram chooses to define Xnor in a similar way to Xor ( and in fact, in a similar way to Or, And, too). Since BooleanCountingFunction only deals with the number of true values, it choose to to define and compute both Xnor(x1,x2,...,xn) and "x1 xnor x2 xnor ... xnor xn" as whether the number of the true values are even, which is also the negation of Xor and which is, at least indeed, the same as x1$\odot$x2 in the case when $n=2$. However, the resulting value of, for example, "x1 xnor x2 xnor x3" as computed by the negation of Xor(x1,x2,x3) is exactly the opposite of the value of "(x1 xnor x2) xnor x3"! In fact, Wolfram's value of "x1 xnor ... xnor xn" and our value of x1$\odot\cdots\odot$xn are the same when n is even and different when n is odd, for any truthy value of x1, ... and xn.

Moreover, there exists a somewhat similar problem for the NAND operator, but to a much less extent since NAND is not associative. Wolfram treats "x nand y nand z" as "x nand (y nand z)" instead of "(x nand y) nand z" (probably for another good reason). You can check the outputs by Wolfram, http://www.wolframalpha.com/input/?i=x+nand+y+nand+z, http://www.wolframalpha.com/input/?i=(x+nand+y)+nand+z and
http://www.wolframalpha.com/input/?i=x+nand+(y+nand+z)

In conclusion, be careful when you use Wolfram to compute logic formula involving XNOR and NAND, especially if you have more than one such operator or more than three arguments. You will want to double check.


CLRS RAM model Description I'm seeking some clarification on a description of the RAM model in CLRS on page 23, section 2.2 (Analyzing Algorithms).

Firstly, it is mentioned that we assume integers are represented with $c\cdot\log_2 n$ bits for some constant $c\geq 1$. Now take the integer value $2$, would it not be the case that we would need more than $\log_2 2=1$ bit to represent the integer value $2$? Since we must express two as $(10)_2$? Perhaps the constant $c$ is supposed to account for this discrepancy.

Secondly I'm a bit confused by this statement:
"We require $c \geq 1$ so that each word can hold the value of $n$, enabling us to index the individual elements...". I understand that if $c$ were $0$ or negative then that would not make any sense, however, are we also to assume then that $c$ must be an integer?

Any intuitive descriptions of these basic properties would be great or relevant examples someone can come up with.

In the RAM model, variables hold a machine word, and operations on machine words take $O(1)$ time. The question is how big should a machine word be. In the variant of the RAM model used in CLRS, a machine word should be large enough so that a variable can count from 1 to $n$ (this is the meaning of the phrase "enabling us to index the individual elements"). To count from 1 to $n$ you need roughly $\log_2 n$ bits, or more accurately, $\log_2 n + O(1)$ bits. This is why we need $c \geq 1$; note that $c$ need not be an integer.

In the RAM model, indexing an array requires that the index is held in a single variable (or at least, this is one reasonable definition). This is why it is important that the machine word is large enough to index all arrays that could appear in an algorithm. If we only consider polynomial time algorithms, then all arrays have polynomial size, and so require indices of size $\Theta(\log n)$. This is the bare minimum needed to make the RAM model useful. It turns out that a larger machine word is not usually necessary, and so $\Theta(\log n)$ is a good choice.

Another reason that we want machine words to be able to hold indices (even if we somehow modify the indexing operation to handle an index spread across several machine words) is that we want a loop of the form

for i from 1 to n:
     if i equals j then do something that takes O(1) time

to run in time $O(n)$. This implies that the operation of incrementing an index should be $O(1)$, and that the operation of comparing two indices should be $O(1)$. So we want our machine words to be large enough to contain an entire index.


Lambda calculus as the language of universal logic - connectives vs functions in lambda calculus? I am reading http://okmij.org/ftp/gengo/applicative-symantics/AACG1.pdf and there is defined language TL (see last row in the table on page 4). It seems to me from this definition of TL, that lambda calculus is the language of universal logic - each connective (unary, binary, ternary, etc.; quantifiers can be expressed in this language as well - as unary functions) is just another function (of type t->t->t - for binary connective) and the only difference between this simple function and connective function is the following: connective functions have constraints in the form of logical rules (e.g. connective or quantifier introduction or elimination rules), simple functions have no such rules.

So - my questions are:

Do I understand correctly, that lambda calculus is (can be) the language of Universal Logic (in the tradition of https://link.springer.com/journal/11787)? If no, then why not? If yes, then why there is no wide adoption of lambda calculus in the Univeral Logic community?
Do I understand correctly that connectives are just another functions with the constraints. Is it possible to defined constraints on other functions (simple functions) in the lambda calculus without changing the base logic? I.s. how logical rules for connective functions differ from the user-defined additional rules/constraints for simple functions?

So - the fully hierarchy of the logics can be defined purely by the introduction of connective functions in lambda calculus and by the additional rules on them. So simple?

Of course, I am aware of Curry-Howard isomorphism but its talk about "propositions as types, proofs as lambda terms" is somehow disconnected with the straight appearance of lambda calculus as the language of universal logic. Maybe there exists answer that connects my feelings about lambda calculus as the language of universal logic with the CHI.

You are on your way to discovering the Curry-Howard correspondence.


When talking about the length of a path in a graph, what exactly is a skip? I'm studying for a final and when looking for the shortest path in a graph from one vertex to another, what is meant by k-skips?

One website defines it as the ability to change the weight of one edge to zero, as if you don't include it in the path distance.

Another one defines it as:

  $P*$ is a k-skip shortest path from s to t, if it includes at least a vertex out of every k consecutive vertices in P

Which I can't seem to understand. I would appreciate some clarification in the matter.

The second definition that you quote is informal, and open to interpretation. Fortunately, the same paper On $k$-skip shortest paths by Tao, Sheng and Pei contains a formal definition, Definition 2 on page 4.

That said, $k$-skip is not a common term, and doesn't really have a universally accepted definition (or indeed, any universally known definition), except perhaps in work following up on the Tao et al. paper mentioned above.


For what $N$ does $2^N$ overflow? Consider the following computation: 2^N (TWO TO THE POWER OF ‘N’, for Int. N>0),
being executed on a processor with 32 bit internal, user and ALU registers.
The registers rightmost bit is bit 0 and the leftmost bit(the sign) is bit 31.
WHAT is the SMALLEST value of ‘N’ that will cause the Overflow Status Flag (V) to be set?

Seems like the calculation should be as simple as plugging values in for N but I don't quite understand if there are any other components to take into account, any help is appreciated.

You don't explain how $2^N$ is calculated, so I'm assuming you repeatedly multiply by 2 (or equivalently, you repeatedly add the number to itself, or shift it left). Here's how this process looks on a 4-bit signed register. You start with $0001$, the answer for $N=0$. Doubling it, we reach $0010$, the answer for $N=1$. Doubling again, we reach $0100$, the answer for $N=2$. Doubling again, overflow occurs (why?).

If the register was unsigned, we could double one more time, obtaining $1000$, the answer for $N=3$. Then we would overflow when doubling again (why?).

I believe you now have the tools to solve your own exercise. I won't verify your answer, so no point asking about it below.


Bipartite graph matching with multiplicities Let's say we have N people, each of them holds several colored cards (for each color and person pair the number cards held is no more than one). We want algorithm determine how to take exactly one card from each person (denote this set of taken cards S), so the following function would be maximal: number of colors satisfying condition - there is at least k cards of this color in S.

In case of k=1 it's well-known problem of maximal matching in bipartite graph.

In case of k>1 this "matching" must have vertices of degree k on on side of bipartite graph. (It can be reformulated as a problem of finding maximal disjunct covering subset of specific set of coverings (in general case i think it's NP-complete?).

Does anyone know if this problem for k>1 NP-complete or can be solved in polynomial time (specifically for k=2)?

For k=2 it's Rainbow_matching, so it's NP-complete.

For all colors X make cliques of all people holding color X, and color it's edges with X.


Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? How? Is $n^3$ an asymtotically tight bound of $(n^{2.99}).(\log_2n)$? If so then how?

No. $n^{2.999}\log_2n$ is tighter, for example.


Proving big-theta complexity with constants in $f(n)$ I am working through a problem in which I have to prove that a particular $f(n) = \Theta(g(n))$. I know that for this to be true there need to exist positive constants $c_1$, $c_2$, and $n_0$ such that for all $n \geq n_0$, $c_1g(n)\leq f(n) \leq c_2g(n)$. Simply put, the goal is to pick values for the constants such that the above inequality holds. As a side note, $n$ must be a positive integer, and $c_1$ and $c_2$ can be any positive real number, correct? I haven't been able to find clarity over that.
Now, suppose the $f(n)$ has some undefined constants $a$ and $b$, such as $f(n) = n^a + n^b$. Note that this is a throwaway example. My question is this: do we need to define $c_1$ and $c_2$ in terms of the constants $a$ and $b$, or do we need to pick an actual numerical value for $c_1$ and $c_2$, and by extension, values for $a$ and $b$? The former is much more difficult to do.
I apologize in advance for the poor formatting (I simply placed any math in italics, which I know is not correct). This is my first ever post on CS stack exchange. Also, I would like to state that there was a serious attempt at researching into the above, but I couldn't find examples of how to prove $f(n) = \Theta(g(n))$ when $f(n)$ has other constants. If anyone has resources related to this, I would be very grateful.
I would appreciate any and all help. Looking forward to potential responses.

You can find the definitions of big O notations on Wikipedia. They agree with your definition of big $\Theta$.
As for your actual question, the answer is actually quite subtle. Sometimes it is possible to find constants $c_1,c_2,n_0$ which work for all values of the parameters. For example, in your case, all $n \geq 1$ satisfy
$$
1 \cdot n^{\max(a,b)} \leq n^a + n^b \leq 2 \cdot n^{\max(a,b)},
$$
and so you can say that $n^a + n^b = \Theta(n^{\max(a,b)})$.
(As a side note, you can also say that $n^a + n^b = \Theta(n^a + n^b)$, or that $n^a + n^b = \Theta(n^a + 2n^b)$; but usually we aim at the simplest possible expression, or an expression of a particular form, say $n^\alpha \log^\beta n$.)
In other cases we are not so lucky. For example, $\log^k n = O(n)$ for all $k$, but the relevant constants depend on $k$. Sometimes this makes no difference, but in other cases it is important to know that the constants depend on $k$. When it does matter, we sometimes use the notation $O_k(n)$ to stress that the hidden constants depend on $k$. This is not completely standard, but pretty common. When the hidden constants are independent of some parameter, we can explicitly say so – $n^a + n^b = \Theta(n^{\max(a,b)})$, where the hidden constants are independent of $a,b$.
In your case, since you are only interested in an isolated estimate, you don't care about the dependence of the hidden constants on the parameters. So for you, $\log^k n = O(n)$ holds, even though the hidden constants depend on $k$, since for any particular $k$ this statement holds. This is the usage in the master theorem, for example – the constants there depend on the parameters, but usually it makes no difference, because the parameters are fixed in any given application, in the vast majority of circumstances.


Finding all (weighted) cycles through a given vertex For a connected undirected graph $G$, given a particular vertex $v$, is there a known (efficient) algorithm to find all simple cycles in $G$ that contain $v$?

In my case, I have weights for every edge.  Ideally I'd like to be able to compute, for every $v \in V(G)$, the product of the edge weights over all cycles that go through $v$. Doing this to some level of approximation would still be very helpful.

Is this a known result?  Any pointers would be very helpful.

Enumerating all cycles might take exponential time

There cannot be any efficient algorithm for enumerating all cycles that contain $v$.  There could be exponentially many algorithms that go through $v$.  Therefore, any algorithm for enumerating all cycles could potentially take exponential time.

If the graph is very small and efficiency is not important, you could enumerate all cycles that go through $v$ using depth-first search or breadth-first search starting from $v$.  Or, you could use Johnson's algorithm: see Find the Simple Cycles in a Directed Graph.

You can't compute the cycle-sums you want efficiently

Now for some more bad news.  You want to compute the sum over all simple cycles, of the sum of edge-weights in the cycle.  Unfortunately, this cannot be done efficiently, either.  This problem is #P-hard, which means there is no hope for a polynomial-time algorithm for it.

Here's a proof of #P-hardness, by reduction from the problem of counting the number of simple paths from $s$ to $t$ (which is a #P-complete problem).  Let $G$ be a graph, and vertices $s$ and $t$ be specified.  Add new vertices $u,v$ and edges $(t,u)$, $(u,v)$, and $(v,s)$.  Label each edge with the weight 0, except that the edge $(u,v)$ will be labelled with weight 1.  Now suppose you had an efficient algorithm to compute the sum over all simple cycles, of the edge-weights in that cycle, for the resulting graph.  Then its output would be exactly the number of simple cycles in this graph, or equivalently, exactly the number of simple paths from $s$ to $t$ in $G$.  Thus, any polynomial-time algorithm for your problem would immediately imply a polynomial-time algorithm for counting the number of simple paths from $s$ to $t$; since the latter is #P-hard, your problem must be #P-hard, too.

For more details on #P-hardness of counting simple paths, see, e.g., https://cstheory.stackexchange.com/q/20246/5038, https://stackoverflow.com/a/5570751/781723, How hard is counting the number of simple paths between two nodes in a directed graph?.

So, the bad news is: there is no efficient algorithm for your problem, and I can prove it.

Time to look for some alternative: e.g., find some way to avoid solving your problem, or hope that your graph will be extremely small (so that exponential-time algorithms are acceptable), or look for an approximation algorithm, or something.  But you're not going to find an algorithm to solve your problem that is efficient on general graphs.

Other miscellaneous comments

It's important to phrase your question so you ask for what you really want.  It sounds like what you really want to know is whether it's possible to compute the sum of the edge weights over all cycles that go through $v$.  If that's what you really want, don't ask whether it's possible to enumerate all cycles through $v$; ask whether there's an algorithm to do what you really want.  There might be a better way to do what you really want, without enumerating all cycles.

(Incidentally, if you are summing over all cycles of any length, it is important to restrict your sum to simple cycles.  If you don't restrict to simple cycles, then there are infinitely many cycles and the sum is going to be either $+\infty$ or $-\infty$.)

For instance, it is possible to efficiently compute the sum of the cycle weights over all cycles of length $k$ (not necessarily simple) that go through $v$, where the weight of a cycle is the product of the edges in $v$.  Here's how.

Here's the key idea.  Let the matrix $M$ represent the adjacency matrix for the graph, i.e., $M_{i,j}$ holds the weight on the edge $(i,j)$, or $0$ if there is no such edge.  Let $e_i$ denote the vector that is $1$ in its $i$th component and $0$ in all other positions.  Let $x = M^k e_v$.  Then $x_j$ is a sum, over all paths from $v$ to $j$ of length $k$, of the products of the weights along each such path.  Thus, $x_v$ is a sum of the weights of all of the cycles of length $k$ that go through $v$.  The running time is polynomial.

Unfortunately, this is not restricted to simple cycles, so it is not what you  want.  Also, this approach ends up multiplying the edge weights along a single cycle, rather than adding them, so it is also not what you want for that reason.  Nonetheless, it shows how some problems of this form can potentially be solved in polynomial time without enumerating all cycles.


EM algorithm for two Gaussian models This is about basic machine learning which I do not understand clearly.

I have 2 Gaussian models $G_1$ and $G_2$ and given a list of data as below.

(1, 3, 4, 5, 7, 8, 9, 13, 14, 15, 16, 18, 23)

I do not know which numbers were generated by which $G_i$ model, but I want to do Expectation Maximization for clustering.

So, what are the hidden variables? and how to perform Expectation and Maximization steps?

Could you show some calculation or short Python code of the likelihood metric? (Perhaps 2 iteration)

I got the basics of EM algorithm from here, but I cannot apply to this question. http://www.nature.com/nbt/journal/v26/n8/full/nbt1406.html

$\newcommand{\I}{\mathbb{I}}\newcommand{\E}{\mathbb{E}}$Given our observed variables $x = \{x_i\}$, hidden variables $z = \{z_i\}$ and distribution parameters $\theta = \{(\mu_j, \sigma_j)\}$, let's define the complete-data log-likelihood as
$$
\begin{align*}
\ell_c(\theta) &= \sum_{i=1}^n \log \Pr[x_i, z_i|\theta] = \sum_{i=1}^n \sum_{j=1}^k \I[z_i = j] \log \Pr[x_i, z_i = j| \theta]\\
&= \sum_{i=1}^n \sum_{j=1}^k \I[z_i = j] \log (\Pr[x_i|\theta_j] \Pr[z_i=j|\theta])
\end{align*}
$$ where $\I[\cdot]$ is the indicator function, $\Pr[x_i|\theta_j]$ is the probability of observing $x_i$ given the $j$th Gaussian and $\Pr[z_i=j|\theta]$ is the mixing weight of the $j$th distribution (i.e., the probability of observing the $j$th hidden variable). This is the model we have if we somehow knew which Gaussian generated a given data-point. We obviously don't know, so we would like to compute the expected value of this complete-data log-likelihood. That is, what is the expected outcome of this full-knowledge formulation? To do that let us define the $Q(\theta^t|\theta^{t-1})$ function as
$$
\begin{align*}
Q(\theta^t|\theta^{t-1}) &= \E\left[\sum_{i=1}^n \sum_{j=1}^k \I[z_i = j] \log \Pr[x_i, z_i = j| \theta]\right]\\
 &= \sum_{i=1}^n \sum_{j=1}^k \E[\I[z_i = j]] \log \Pr[x_i, z_i = j| \theta]\\
&= \sum_{i=1}^n \sum_{j=1}^k \Pr[z_i = j | x_i] \log \Pr[x_i, z_i = j| \theta]\\
&= \sum_{i=1}^n \sum_{j=1}^k \underbrace{\Pr[z_i = j | x_i]}_{r_{ij}} \log (\Pr[x_i|\theta_j]\underbrace{\Pr[z_i = j| \theta]}_{\pi_j}).\\
&= \sum_{i=1}^n \sum_{j=1}^k r_{ij} \log \Pr[x_i|\theta_j] + \sum_{i=1}^n \sum_{j=1}^k r_{ij} \log \pi_j.
\end{align*}
$$
Computing $r_{ij}$ for the E-step is done by simple Bayes theorem,
$$ r_{ij} = \frac{\pi_j \Pr[x_i|\theta_j^{t-1}]}{\sum_{j'=1}^k \pi_{j'} \Pr[x_i|\theta_{j'}^{t-1}]}.$$
Now for the M-step we would like to compute the mixing weights $\pi$ and parameters $\theta$ that maximize $Q$. Luckily for us, we can optimize for each independently as seen by the final formulation! By taking the derivative of $Q$ wrt $\pi$ with the Lagrange constraint that $\sum_j \pi_j = 1$ we have
$$
\pi_j = \frac{\sum_{i=1}^n r_{ij}}{n}.
$$

In order to optimize $Q$ wrt $(\mu_j, \sigma_j)$ lets look at the part only dependent on them (ignoring some constants).
$$
\sum_{i=1}^n r_{ij} \log \Pr[x_i|\theta_j] =
-\frac{1}{2}\sum_{i=1}^n r_{ij} \left(\log \sigma_j + \frac{(x_i - \mu_j)^2}{\sigma_j}\right)
$$
Using this information helps when taking the derivative of $Q$ wrt to each parameter. Finally we have,
$$
\begin{align*}
\mu_j &= \frac{\sum_{i=1}^n r_{ij} x_i}{\sum_{i=1}^n r_{ij}},
&\sigma_j &= \frac{\sum_{i=1}^n r_{ij} x_i^2}{\sum_{i=1}^n r_{ij}} - \mu_j^2.
\end{align*}
$$

In your case, $x = (1, 3, 4, 5, 7, 8, 9, 13, 14, 15, 16, 18, 23)$, $z = (z_1,\dotsc, z_{13})$, $k=2$, and $\theta = ((\mu_1, \sigma_1),(\mu_2, \sigma_2))$. EM begins by randomly initializing $\pi = (\pi_1, \pi_2)$ and $\theta$ and then alternating between E-step and M-step. Once the parameters haven't changed much (or better the observed-data log-likelihood hasn't changed much) you can stop and output your current values $\theta^t$ and $\pi$.

One benefit from using $|\ell(\theta^t) - \ell(\theta^{t-1})|$ over $||\theta^t - \theta^{t-1}||$ as a stopping condition is for bug checking. EM guarantees that the likelihood will always monotonically increase; therefore, you can simply check the values each iteration to much sure that your likelihood is greater than or equal to last iteration's. If it isn't, then something is wrong.

Finally one important thing to note is that computing a MLE for a mixture of Gaussians will tend to overfit. One way to overcome this is by incorporating priors for $\pi$ and $\theta$ and then computing the MAP estimate instead. This would only change the M-step; however, its derivation is dependent on which prior you choose.

EDIT: Since it is clear you are more interested in just a working example than really understanding any of this here is Python code that will run EM for a basic GMM. Running this in ipython gives:

In [1]: import em

In [2]: x = (1, 3, 4, 5, 7, 8, 9, 13, 14, 15, 16, 18, 23)

In [3]: em.em(x, 2)
Out[3]:
(array([ 0.49645528,  0.50354472]),
 array([ 15.89753149,   5.10207907]),
 array([ 3.8611819 ,  2.65861623]))

where the final output are the mixing weights, means for each Gaussian, and stdevs for each Gaussian.


Optimizing cheap functions on mixed search space Assume we have a really cheap function $f$ that is defined on a mixed parameter space and we want to find a minimum.
For example

$\operatorname{arg\,min}\limits_{x_1,x_2,x_3} f(x_1,x_2,x_3)$

with

$x_1 \in \mathbb{R}, \ x_2 \in \{1, \ldots, 10\}$ and $x_3 \in \{\text{'a'}, \text{'b'} \}$.

and we have no assumptions on monotony in any dimension or likely local optima.
How can I find the values that minimize the function without much computational overhead?

In general you can't. Optimization is a tricky business and proper solutions are only known if your $f$ and/or your search space belong to some restricted class.

You can try various heuristics. Things to google for include "genetic algorithms", "evolutionary algorithms", and "simulated annealing".


Natural Language Parser that can handle syntactic and lexical errors I have some background in natural language processing and I know that all parsers (top down or bottom up, or mix), at least when I studied just about a few years ago, cannot handle any error. A small error like a grammatical one or a spelling one will result in unexpected parsed tree.

This is unacceptable in natural language in most cases. Thus I have been trying to find a way to make a new one with a different approach.

The basic general abstract idea is that I will use a top down dynamic programming approach.
Given a string of text with $n$ tokens, several top down fillers will be generated. These fillers will look at the tokens to see if they can find and fill constituents that they are missing. Because of this, these fillers might leave gap after they have found everything they need. This is supposed to make the parser more robust.

An example will be best to illustrate this idea:

Given the sentence: I saw the ordinary thing.

One top down filler can be. $S \rightarrow Subj - Verb - Object$.
This filler will try to look for span that it can use to fill its expectation of seeing a $Subject$ followed by $Verb$ and $Object$. This means it will deployed three other fillers in sequence. The first one is $Subj$. This filler will scan and add to the cache three possible subjects which are $I$, $saw$, $thing$. $I$ is put in span $[1,1]$, $Saw$ in span $[2,2]$, $thing$ in span $[5,5]$. This will result in a total of three potential pending parse trees. Then with each of these pending parse tree, $Verb$ filler is deployed to scan the span after each possible subject. $Object$ filler is deployed to scan the rest.

With the above approach, sentences such as I .. eh... saw the big thing
or similar constructs do not cause problem because fillers look for what they need and fill them into the tree. This problem is dealt with when all fillers have completed. Fillers that leave lot of gaps (unused tokens) will not generate parses having high score compared to parses generated by fillers that use up all tokens.

This is also my approach to deal with subject-verb agreement and male-female as well as singular-plural agreement. You deal with them at the ranking stage so that you can give your parser much better error tolerance. Sentences such as Maybee they ehh can get something can still be parsed. One resulting parse will just not use Maybee. The top parses will then be used again, this time to look for unused tokens. Unused tokens will be processed with spelling correction, did-you-mean style. One can see how it works with incorrect sentences like This is a valide argument. Even incorrect sentences like They did got it are still parsed ok.

There will be other fillers which cannot find all they need such as conditional sentence filler. $CondS \rightarrow "If" - S - ["then"] - S$. Some filler such as imperative $ImpS \rightarrow ["Please"] - Verb - Object$ will complete most of the times because it can find all it needs abeit leaving gaps, but then it is a ranking problem to make sure that the correct one is returned.

So my Question is:

Has anyone ever thought of this approach? Any reference papers?
If nobody used it before what may be the potential problem?

I assume you already know about dynamic programming parsing, aka chart
parsing. This is usually defined for Context-Free grammars (CFG), but
can be extended to other grammatical formalisms, where it can make
more or less sense, depending on the structural complexity of these
algorithms. There are various papers describing chart parsing for
specific formalisms, particularly in the computational linguistic
literature. One general view of the underlying structure common to all
these algorithms is described in a 1995 paper by Lang, and to be found
in the Grune-Jacobs book, relies on a very simple view of parsing as
an intersection of two languages: the first is the singleton regular
language containing the sentence $w$ to be parsed, and the second being
the language $L$ for which we are given a grammar $G$. The idea is
that a single sentence $w$ can always be read as a FSA (or a regular
grammar) as in the following example for the sentence $abac$
$$q_0 \stackrel{a}\longrightarrow q_1 \stackrel{b}\longrightarrow q_2
\stackrel{a}\longrightarrow q_3 \stackrel{c}\longrightarrow q_f$$

Using this FSA $A_w$ and the grammar $G$ of the language $L$ (assume
first $L$ to be a CF language, and $G$ a CFG), the old cross-product
construction due to Bar-Hillel, Perles and Shamir (1961) to prove
closure of CFL with regulr sets can be used with $A_w$ and $G$, and
yield a new CF grammar $G_w$, which naturally generates only $w$ when
$w\in L$, or the empty language $\emptyset$ when $w\notin L$. The
important point is that, when $w\in L$, the grammar $G_w$ generates
$w$ with exactly the same parse trees as the original grammar $G$, up
to a renaming of non-terminal, though the correspondence between
non-terminals is kept (let us ignore details). In other words, we just
described a parser that yield a parse forest $G_w$ from which all the
parse trees for $w$ can be extracted, simply by using the grammar
$G_w$ as a generator.

As it turns out, the dynamic programming chart parsers are just
optimized variants of this very basic construction called parsing as
intersection.

The nice point about it is that it lends itself to many variations.
Closure under intersection with regular languages is a very common
property, so that this is a guide for producing parsers for a great
variety of formalisms, though it makes effective sense only for those
that have a simple generating structure (loosely). Typically it works
very well for tree adjoining grammars (TAG) an other mildly context
sensitive languages.

Another point is that, rather than parse only strings, one can parse
complete regular sets, keeping only the sentences that are also in the
context-free language. And it is largely compatibles with the many
"optimization" techniques commonly found in chart parsing

This is very important in natural language processing (NLP), and
particularly in speech processing, since the result of the first pass
of speech processor to identify the spoken words is usually not a
single string of words, but what is usually called a word lattice
(see Ambiguity and sharing in Natural Language Parsing, which is
actually the title of an answer to a question).

The interesting point is that a word lattice (see diagram in previous
reference) may be seen as a FSA that recognizes all the candidate
sentences (after noise processing) that could be the sentence to be
parsed. But chart parsing can be applied as well, as can the
intersection construction.

Now, it may well be that the word lattice contains spurious words to
be eliminated, or completely garbled sequences corresponding to
arbitrary number of missing words, or misunderstood words. That can be
modeled as a General Sequential Mapping (GSM) that does some editing
on the input sentence, adding, removing or substituting words,
possibly in a (finite) contextual way. Both regular and context free
languages are preserved by GSM mapping. Typically, the editing GSM can
be applied to the word lattice, yielding a new regual language and its
FSA (possibly even with cycles).  Then the parsing process is applied
to that new FSA.  This part is, I think, what you mainly wanted to
describe in the question.

The next point is that not all proposed sentences, or not all
corrections have the same likelyhood. Actually, word lattices may be
weighted structures that give weights to the corresponding sentences
in proportion to some likelyhood they they are correct.

Then the editing GSM can also have weighted transition corresponding
to some standard likelyhood that such error may have occurred.

Finally, the (CF) grammar of the language itself may be weighted.

The dynamic programming construction can use these weight (possibly
probabilities) to determine what are the most likely parses of the
given input according to the grammar used.

Note that I have been skipping the morphological analysis that
recognizes words, and uses similar techniques to end up with the word
lattice.

I am also skipping the use of attributes or feature structures, that
can combine with the process, provided they meet some algebraic
constraints.

The algebraic constraints (that concern also the numerical weights)
are related to the algebraic structures of the grammars themselves.
Typically, a CF derivation backbone (that is more than CF languages)
relies on semiring structures.

A CF rule such as $X\to VXW | aV$ may be read as an equation of the
 form $X = V\cdot X\cdot W \cup \{a\}\cdot W$ where the wariables take
 their values in sets of sentences (i.e. in languages). The domain of
 languages is a semi-ring under the two operations: Union "$\cup$" and
 concatenation "$\cdot$". And a context-free grammar is a specific kind of equation in that domain.

You should find more on this use of semirings in Goodman's "Parsing Inside-Out 1998.

There are some other references in my answer to the question "Is there a favoured data structure for storing ambiguous parse trees
in Natural Language Processing?"


Prim's Minimum Spanning Tree implementation $O(mn)$ or $O(m+n \log n)$? I am reading Prim's MST for the first time and wanted to implement the fast version of it .

$m$ - The number of edges in the graph

$n$ - The number of vertices in the graph

Here's the algorithm :

1) Create a Min Heap of size $V$ where $V$ is the number of vertices in the given graph. Every node of min heap contains vertex number and key value of the vertex.

2) Initialize Min Heap with first vertex as root (the key value assigned to first vertex is $0$ ). The key value assigned to all other vertices is $\infty$ .

3) While Min Heap is not empty, do following

…..a) Extract the min value node from Min Heap. Let the extracted vertex be u.

…..b) For every adjacent vertex $v$ of $u$, check if $v$ is in Min Heap (not yet included in MST). If $v$ is in Min Heap and its key value is more than weight of $u-v$, then update the key value of $v$ as weight of $u-v$.

Now my point is during implementation ( I am doing in C++) in step 3(b) I have to check whether the vertex is there in the heap or not . As we know , searching in a heap is done in $O(n)$ time . So in the main while loop which will run ( $n$ number of times ) although extract-min is $O(\log n)$ but the search ( whether $v$ is min heap or not takes time proportional to size of the heap ( although it is decreasing in each step ) .

So is it correct to say that the above algorithm is $O(m+n\log n)$

In your step 3b, you have to carry out at most $\deg(u)$ many decrease-key key operation. Thus in total you need $\sum \deg(u) = 2m$ many decrease-key operations. A single decrease key runs in $O(1)$ amortized time (Fibonacci Heaps). Thus the total running time is $O(m+n\log n)$. If you are not using Fibonacci heaps the running time is slower. Something like $O(m \log n )$.

I do not see how you got to $O(m+n\log n)$ by following your arguments. Also its unclear how you can do all the decrease-key key operation for one step in $O(n)$ time.


Handling epsilon productions in recursive descent parsing I am working on a recursive descent parser for lambda calculus. In my grammar, after removing left-recursion, I am left with the following two productions:

# APPLICATION  -> ATOM APPLICATION'
# APPLICATION' -> ATOM APPLICATION' | ε

Both APPLICATION and APPLICATION' correspond to the same type of node in the AST. How should I handle parsing the second production? I know that choosing between two alternatives for a production is performed by looking up the next token in buffer, but the epsilon production confuses me.

EDIT:

Here is current implementation (Ruby) that fails to left-associate applications.

require_relative 'token.rb'
require_relative 'ast.rb'

class Parser
    def self.call(tokens)
        new(tokens).send(:parse_expr)
    end

    def self.to_proc
        method(:call).to_proc
    end

    private
        def initialize(tokens)
            @tokens = tokens
            @l = -1
        end

        def parse_expr
            if lookahead.type == :tklambda
                return ExprNode.new([parse_abstraction], @l)
            else
                return ExprNode.new([parse_application], @l)
            end
        end

        def parse_abstraction
            match_token(:tklambda)
            id = parse_identifier
            match_token(:tkdot)
            expr = parse_expr
            return AbstrNode.new([id, expr], @l)
        end

        def parse_identifier
            id_token = match_token(:tkid)
            val = id_token.value
            return IdNode.new(nil, @l, val)
        end

        def parse_application
            left_child = parse_atom
            first_atom = [:tklparen, :tkid] # FIRST(ATOM)
            # application -> atom application'
            while !lookahead.nil? and first_atom.include?(lookahead.type)
                return AppNode.new([left_child, parse_application], @l)
            end
            # application' -> atom application' | ε
            return left_child
        end

        def parse_atom
            if lookahead.type == :tklparen
                match_token(:tklparen)
                expr = parse_expr
                match_token(:tkrparen)
                return AtomNode.new([expr], @l)
            else
                return AtomNode.new([parse_identifier], @l)
            end
        end

        def match_token(type = nil)
            if !type.nil? and lookahead.type != type
                raise "Unexpected token at #{@l + 1}. Expected: #{type}, "\
                      "got: #{lookahead.type}."
            end
            @l += 1
            return @tokens[@l]
        end

        def lookahead
            return @tokens[@l + 1]
        end
end

You need to know FOLLOW(APPLICATION'), and it has to be disjoint to FIRST (ATOM).

Actually, you only have to know that the sets are disjoint, in which case the epsilon action becomes the default.

Personally, I wouldn't bother with two functions:

Application:
    v := Atom()
    if lookahead token in FIRST(ATOM):
        return ApplyNode(v, Application())
    else:  (* default case *)
        return v

That corresponds with your grammar, but it might not correspond with your intended language. Normally, lambda application is left-associative, not right-associative, but of course it is impossible to express left-associative expressions with an LL(k) grammar. Fortunately, it is easy to write a recursive descent parser which left-associates. That's usually done with a local variable and a while loop: (Technically, the parser is doing a tree-rewrite in order to fix the associativity, but the mechanism is so simple that hardly anyone sees that it is even there.)

  Application:
     v := Atom()
     while lookahead token is in FIRST(Atom):
         v := ApplyNode(v, Atom())
     return v


Reduction from 2-SAT to 2-XOR-SAT? 2-SAT is unsatisfiable iff it contains unsatisfiable XOR-2-SAT.

So, first, we just need to combine every clause that contains share same variables (both of them). Then, all of those which remain uncombined are "uninteresting" (don't affect satisfiability).

Example:

$\Phi = (x \lor y) \land (\overline x \lor \overline y) \land (x \lor \overline z)\land(\overline x \lor z)\land (\overline y \lor z)\land (y \lor \overline z)\land (z \lor t)$

Now I can replace this formula by equisatisfiable (under log-space reduction):

$\Phi' = (x \oplus y)\land(x \oplus \overline z)\land(y \oplus \overline z)$

As you can see, clause $(z\lor t)$ was removed as "uninteresting".

Ah, well, I need to see if there are cycles in implication graph. So, finding a cycle in directed graph that contains two given vertices is $\mathsf{NL}$-complete problem, right?

This method doesn't work since you can't always pair clauses as in your example.

According to Wikipedia, 2SAT is NL-complete. In particular, this means that it is not in logspace unless L=NL, which is considered unlikely.


How to construct an NFA Ai for the given Regular property P1 and P2? Let AP = {a; b; c}.
Consider the following regular safety properties:
(a) P1: If a becomes valid, afterwards b stays valid ad infinitum or until c holds.
(b) P2: Between two neighbouring occurrences of a, b always holds.
Construct an NFA Ai for each property Pi such that L(Ai) = BadPref(Pi).
Hint: You may use a symbolic NFA with propositional formulae over the set AP as
transition labels.

In the above question,

What is symbolic NFA?
What would be the propositional formula for P1 and P2?
How to construct an NFA from the above two statement?
Are there any concrete steps to do it?

The NFA for bad prefixes would be just the negation of an NFA right?
I have the solution for it, but I don't understand how did they arrive at the solution.
It would be great if somebody could explain or provide a link on how to do it?
Note: I hope it's not related to LTL since it is not part of the syllabus. Anyways, I believe that one can only construct NBA from the LTL or CTL formula right?
Thank you very much.

We have several definitions and notations here, let's go through these first:

We are given a set of atomic propositions AP. It is not said here explicitly, but usually this means we are interested in languages that have as alphabet the power set of AP. So for AP = {a,b,c}, our alphabet would be Sigma = { {}, {a}, {b}, {c}, {a,b}, {a,c}, {b,c}, {a,b,c} }.

As you can see, writing out this power set alphabet can be a lot of work. For this reason, there is an alternative notation based on propositional formulas. Consider a propositional formula phi over the variables AP. We can take a symbol x from Sigma and in phi set all atomic propositions contained in x to true and all other atomic propositions to false. Then we evaluate phi and it becomes true or false. We can understand phi to refer to all those x from Sigma for which phi evaluates to true.
For example, the formula phi="a and not b" refers to the symbols {a} and {a,c}. The formula phi="a" refers to the symbols {a},{a,b},{a,c},{a,b,c}. The formula phi="not a" refers to the symbols {},{b},{c},{b,c}. The formula phi="not a and not b and not c" refers only to the symbol {}. The formula phi="true" refers to all symbols from Sigma. The formula phi="false" refers to no symbol (not to be confused with the symbol {}). And so on ...
This logic is the notation used on the NFA edges in your example.

We call a language L over finite words "regular" if there is a NFA that accepts L.

We call a language L over infinite traces a "safety property" if every trace not in L has a bad prefix, meaning a finite prefix w, such that no infinite continuation of w is in L.

We call a safety property "regular" if the language of its bad prefixes is regular. Note we are dealing with two different notions of "regular" here, one for languages of finite words and one for safety properties over infinite traces.

General approach
You are dealing with the problem of going from an informal description of a safety property to a formal description of the language of its bad prefixes. There is no general rule for how to do this, but remember that on an intuitive level, a safety property means "some bad event never happens". The language of the bad prefixes is then exactly those finite words for which "the bad event happens at some point". Your approach would therefore be to analyze what the "bad event" is.
(This is a general problem in model checking of course, when going from informal descriptions to a formal model there is a risk of not perfectly capturing the original description.)
Consider P1: The bad event is "a becomes valid and afterwards b is valid only finitely many steps and becomes false before c becomes true". We can turn this into a slightly more verbose description: "a becomes valid, afterwards we see some b's but no c's and then we see no b and no c". We can use this description to derive a formal definition for "the bad event happens at some point". I personally find regular expressions more intuitive than NFAs, so I would first try to build a regular expression and then build the NFA from that afterwards:
(true)* a (b and not c)* (not b and not c) (true)*

This regular expression describes all finite words where at some point the bad event happens. We use the (true)* at the beginnging and the end because we do not care what happens before or after the bad event. The regular expression is already very close the NFA in your example, in general it should be easy to build NFAs from such regular expressions. You can see that the notation based on propositional formulas makes this much more compact compared to writing out the symbols explicitly, e.g. writing "a" is shorter than writing the full regular expression ({a} + {a,b} + {a,c} + {a,b,c}).
This is not the only solution, instead of requiring to see (b and not c)* before seeing (not b and not c), it would also suffice to require to see (not c)* before seeing (not b and not c). This would result in the regular expression:
(true)* a (not c)* (not b and not c) (true)*

The only difference to the first solution would be that instead of requiring to match the first (not b and not c) we see, we could also skip over some (not b and not c)'s because they also match (not c), as long as we match a (not b and not c) eventually. So in a way the first solution is the better one because the resulting NFA is more deterministic.
Consider P2: The bad event would be having two a's such that in between at some point b does not hold. Turning this into a slightly more verbose description, we would get "we see a, afterwards we see some b's without seeing a, then we reach a point where we see neither b nor a, afterwards we see any symbols until we reach the closing a". Turning this into a regular expression for "the bad event happens at some point" gives us:
(true)* a (b and not a)* (not b and not a) (true)* a (true)*

Again this is very similar to the NFA in your example, it should be easy to see how to construct an NFA from such an expression. As before we could also obtain an alternative solution, by relaxing the (b and not a)* to (not a)*, the only difference would be that this would allow to skip over some (not b and not a), as long as we match one eventually. Also, we could strengthen the middle (true)* to (not a)*, requiring us to match the first closing a instead of allowing to skip over some a's before matching the closing a:
(true)* a (not a)* (not b and not a) (not a)* a (true)*

Regarding the number of states
Since you asked about how to know the number of states: I would first try to obtain some NFA and then check if it can be simplified. For the NFAs in your example, I see no way to further reduce the number of states, but in general minimizing NFAs is a hard problem (reference), so there is no efficient algorithm for that. Of course, if you obtain a fully deterministic automaton, you can apply the standard algorithm for minimizing DFAs.


Need for an augmented grammar The question is under the concept of LR parser.
Suppose the original grammar is
S->AA
A->aA|b

Is it necessary to add an additional rule S'->S to make it as augmented grammar?
In short, I want to know the use of augmented grammar.

Yes, if you follow the canonical conversion of augmented grammars, a first step is adding a new start symbol $S'$ and the production $S' \to S$, since the algorithm may later "change" $S$.

However, it may not be necessary at all times. If you ask whether or not it is necessary specifically in this case, why don't you try without it and check if you get a valid answer?


How to restore a broken minimal spanning tree? We're given $T$ a minimal spanning tree (MST) of a non-directed, connected graph $G=(V,E)$ with non-negative weights for each edge $e \in E$. Let $e^* \in T$ be an edge in $T$ and let $G'=(V,E')$ be the graph which we get after removing $e^*$ ($E'=E\setminus \{e^*\}$). $G'$ is also connected.

I need to propose an algorithm which will run in $O(|E|)$ time and will restore $T$ such that it will yield an MST $T'$ for $G'$.

I'm really not sure if I'm in the right direction but this is what I thought of:

Let $e^*=(u,v)$.

a) We mark $e^*$ and remove it from $T$ and b) find the connected component of node $v$ by using BFS algorithm on $T$.

Now we have 2 connected components:

the first starts from $v$ let's call it $S = T\setminus e^*$
the second is $V\setminus S$

Clearly $e^*\notin S$ and $e^* \notin V\setminus S$. Also $S\neq V$ because otherwise we'd get a connected graph after the removal of $e^*$ of $n-1$ edges which would mean that there were $n$ edges in $T$ which is a contradiction since $T$ is a tree.

c) Then we start looking for a minimal edge $e'$ from $u\in V\setminus S$ to $v\in S$.

d) Once we found  $e'$ we'll add it to $T$ and we'll get $T'$.

I'm having trouble with running times.

a) we need to traverse $G$ in order to find $e^*$ so it's the running time of BFS which is $O(|E|+|V|)$ and because $G$ is connected ($|E| \ge |V|-1$) then the time is $O(|E|)$.

b) BFS again so $O(|E|)$.

c) This could also be $O(|E|)$ because in the worst case the graph could be something like this:

d) is O(1).

This is just to confirm that OP has, in the course of updating his question, arrived at a well-written correct "algorithm which will run in $O(|E|)$ time and will restore $T$ such that it will yield an MST $T'$ for $G'$".


Does "in-place" for $n$ items imply space dominated by $n$? Does the characterisation of an algorithm for $n$ items as in-place imply space ∊ $ο(n)$

formally
informally ("among coders")?

There are two common ways to analyze computation, corresponding to two different machine models. One model is the one taught in classes on computability and complexity theory: it is the Turing machine model. In this model, the machine has a read-only input tape, a write-only output tape, and several work tapes, and we only measure space on the work tapes.

A different (and more realistic) model is used in classes on algorithms and data structures: it is the word RAM model. There are several ways to define space usage in this model - one obvious way is the number of memory cells accessed beyond the input cells. In this model, one could define an in-place algorithm as one which uses $O(1)$ space (in this model we measure space in machine words of length $O(\log n)$, where $n$ is the length of the input), though this ignores stack usage (which will be simulated in the RAM model using a stack whose memory usage counts).

You haven't defined what in-place means for you, and you haven't defined how you measure space. Without such definitions, it is impossible to answer your question. However, I have outlined above definitions of both concepts for which in-place implies sub-linear (even constant) space.


Are there any type constructors which are *not* functors? So I'm almost done teaching myself category theory. One of the main take-aways for me is that type constructors (higher-kinded types) are endo-functors.

But it this always the case? What's throwing me off is Haskell's Functor typeclass:

class Functor f :: * -> * where
   fmap :: (a -> b) -> (f a -> f b)

If all type constructors were a priori functors, there would be no need to define a special type-class. But I can't think of any type-constructors that fail to satisfy the Functor type-class: product, sum, function, list, set, option, etc.

I also cannot imagine the utility of a type-constructors that is "one-half" of a functor, i.e. it has a map from objects to objects, but no map between morphisms.

One obvious counterexample is a binary search tree. You cannot freely substitute the values in a binary search tree because a substitution might change the ordering (relative to Ord), or even replace the values with a type which is not an instance of Ord at all.

A possibly less-obvious example is a contravariant endofunctor. Consider:

data Tricky a = Tricky (a -> String)

Try writing a Functor instance for this.

But that doesn't mean you can't construct a functor-like class which it the type does satisfy. This Tricky type, after all, is a contravariant functor:

-- Somebody has probably already implemented this in a library
-- somewhere, with a better name.
class ContraFunctor f :: * -> * where
    contramap :: (b -> a) -> (f a -> f b)

instance ContraFunctor Tricky where
    contramap f (Tricky t) = Tricky (t . f)

and like fmap, it must satisfy some axioms which are left as an exercise.

What's interesting, though, is that you can usually come up with a functor-like class (and its axioms, of course) which applies type substitutions in a principled way, from the types of the functions which comprise their API.

The full details are beyond the scope, but it's based on a remarkable property of a polymorphic function is known as the "free theorem". Any polymorphic function has a theorem that it satisfies simply by virtue of being polymorphic, and the theorem is mechanically derivable from its type.

What the theorem essentially states is that a polymorphic function commutes with a type substitution. This is what "polymorphic" really means.

Let's take reverse as an example:

reverse :: forall a. [a] -> [a]

There are no constraints whatsoever on the type of a, so it will commute with any type substition:

forall f :: A -> B. fmap f . reverse = reverse . fmap f

(Remember, . is function composition in Haskell.)

This is true for any types A and B. In a deep sense, this is what the "forall" actually means in the type of reverse.

Now consider sort:

sort :: forall a. Ord a => [a] -> [a]

The problem here is that Ord is a constraint on the type of a. What this means is that this is a constraint on any type substitution: it must be a homomorphism of Ord.

forall f :: A -> B.
    (forall x y : A, compare x y = compare (f x) (f y))
    => fmap f . sort = sort . fmap f

That extra precondition, that f is an Ord-homomorphism, intuitively means that f is a function which preserves the order. This should make sense: if a type substitution doesn't change the ordering of elements, then that type substitution commutes with sort.

But here's my favourite example of all. Suppose that F and G are functors. Now consider this function:

eta :: forall a. F a -> G a

The free theorem of this function is:

forall f : A -> B.  fmap f . eta = eta . fmap f

Note that the two fmaps are different instances; the first one is the instance for G and the second is the instance for F. What this is saying is that eta, by virtue of its type alone, is a natural transformation.


Matching a set of paths to an incrementally generated graph I am working on an approximate matching problem, where I have a set of paths in an unknown graph (A) and a partial graph (B), where B is generated incrementally during the matching process (and can be potentially infinite).

The problem is to match the maximum number of edges in the paths to the smallest graph B. The matching should be such that the order in which the edges appear in the paths is preserved in the graph, and each path is matched to a distinct path in the graph. This distinctness requirement comes from the fact that each path in graph A must have a corresponding path in graph B but might not generated yet.

The graph nodes are immaterial and the edges have non-unique labels upon which matching is performed. Also, the paths to be matched can have arbitrary edges added/deleted while matching is to the graph B. If the solution does not meet a threshold (X% of edges matched), we can query an oracle, that generates a slightly bigger (i.e., more complete) graph but the goal is to minimize the queries as the graph can potentially be infinite.

Example:

Paths:
-A-> -B-> -C->
-A-> -D->

Graph:
-A-> -X-> -B-> -C->

Result:
Matched: A-A, B-B, C-C
Unmatched: D

Query Oracle (A-D?) gives resulting graph.
-A-> -X-> -B-> -C->
 |-D->

Result:
Matched: A-A, B-B, C-C, D-D

I tried to lookup standard solutions from assignment and graph isomorphism but didn’t find anything similar. So, here is a solution I came up with:

I am using a branch and bound algorithm to match every edge in the paths to every edge in the graph (M X N table). For each possible assignment, I am keeping track of which other assignments are possible containing with the particular assignment
The bounding condition (& feasibility) is defined by the same ordering of the edges in the graph as it is in the paths. Also, two paths cannot be mapped such that they violate each others ordering.
If we are not happy with this solution, we can query the oracle, get a bigger graph and repeat 1 & 2. Otherwise, the technique outputs the possible edge mappings.

My question is that I am not sure if my solution still falls under branch & bound algorithms, as it no longer follows the standard branch & bound tree structure. Also, it would be great if anyone can point out optimizations or a better way to do this.

Note: At every iteration, N changes and the table grows horizontally. The biggest inefficiency is in step #2, which needs to be recomputed at every stage for safety (e.g., a loop being added in the graph invalidates previous solutions).

I'll outline a solution to your problem.  There are two key insights: (1) each path can be analyzed independently of all the others; (2) the best match can be computed using dynamic programming.  I'll start with a simpler version of your problem and build up to a solution for the full problem.

Finding the best match for a single path

Suppose we have a single path (from graph A) and we want to find its best match in graph B.  This can be solved with dynamic programming.

Let $P$ denote the path from graph A, and $P_k$ denote the prefix of the graph containing its first $k$ edges.  If $v$ is a vertex in $B$ and $k$ is a natural number, define $f(k,v)$ to be the number of edges present in the optimal match of $P_k$ inside graph B, such that the match ends at vertex $v$.  Then $f(k,v)$ follow the following recursive relation:

$$f(k+1,w) = \max(\max \{f(j,v) : v \to^* w,j \le k \}, 1 + \max \{ f(j,v) : v \to^* v' \to w, j \le k\})$$

where the former max is taken over all $v$ such that $w$ is reachable from $v$ in B, and latter max is taken over all $v,v'$ such that $v'$ is reachable from $v$ in B and there is an edge from $v'$ to $w$ in B whose label is the same as the label on the $k$th edge of $P$.  Also, we have the base case $f(0,v) = 0$ for all $v$.  Finally, notice that the number of edges matched in the optimal match for $P$ is given by $\max\{f(k,v) : v \in V\}$.

This recursive relation immediately gives us a dynamic programming algorithm to compute the number of edges matched in the optimal match for $P$.  You can also augment the algorithm to retrieve the match itself, if desired.

The running time is polynomial.  Suppose the path has length $\ell$ and graph B has $n$ vertices and $m$ edges.  Then there are $O(\ell n)$ subproblems, and each subproblem takes $O(m \el)$ time to solve (on average), so the running time is $O(nm \ell^2)$.  [It might be possible to further improve the running time by decomposing B into strongly connected components and only computing $f(k,v)$ values for one vertex $v$ in each strongly connected component, but I haven't tried to optimize this algorithm.]

Note that this gives the exact optimum, not an approximation.  It's not a heuristic -- it always gives the optimal solution.

If you don't find the dynamic programming algorithm intuitive, here is another perspective.  You can think of this from an automata theory perspective.  Suppose the path has edge labels $e_1,\dots,e_{\ell}$.  Let $M$ be the automaton that accepts every subsequence of regexp $\Sigma^* e_1 \Sigma^* e_2 \Sigma^* \cdots \Sigma^* e_{\ell} \Sigma^*$ (this is a regular language, so it has a NFA, call it $M$).  Form the parallel composition of $M$ and B, using the product construction; call it $M'$.  Now look for the longest path in $M'$.  This is exactly the optimal match you are looking for.

Finding the best match for a collection of paths

Now suppose we have multiple paths and want to match them all to B.  Well, it turns out that the optimal way to match a collection of paths is to consider each path separately, finding the optimal match for that path in isolation (independent of all the other pairs), and then combine these matches.

So if we have $q$ paths, we can just invoke the algorithm above $q$ times, once for each path.  The running time will be $O(nm \ell^2 q)$.

Dealing with changes to B

In your problem, each time you find the best matches for a collection of paths, you then update B to get a new graph.  This can be easily handled by simply running the algorithm from scratch again on the new graph.  In each round, you run the $O(nm \ell^2 q)$-time algorithm from above on the current graph B.  Then, you use whatever technique you have in mind for growing the graph B, and start over again.  This doesn't let you re-use work from previous rounds, but it's a very simple technique, and it computes the optimal solution.


How to solve this recurrence involving binomial coefficients? How to solve the following recurrence involving binomial coefficients, where $c$ is a constant non-negative integer, and $n$ and $k$ are non-negative integers ($n \ge k \ge 0$)?

$$
A(n,k) = A(n-1,k) + A(n-1,k-1) + c, \\
A(n,0) = 1, A(n,n) = 1
$$

My Attempt:
Without the constant $c$ (or $c=0$), $A(n,k)$ is just $\binom{n}{k}$.

I have tried the generating function
$$
g(x,k) = \sum_{n=0}^{\infty} A(n,k) x^n.
$$
I need to evaluate
$$
\begin{align}
\sum_{n=0}^{\infty} A(n+1,k) x^n &= \sum_{n=0}^{\infty}\big(A(n,k)+A(n,k-1) + c\big)x^{n} \\
&= g(x,k) + g(x,k-1) + \frac{c}{1-x}
\end{align}
$$

On the other hand,
$$
\begin{align}
\sum_{n=0}^{\infty} A(n+1,k) x^n = \frac{1}{x} \big(\sum_{n=1}^{\infty} A(n,k) x^n\big) = \frac{1}{x}\big(\sum_{n=0}^{\infty} A(n,k) x^n - A(0,k)\big).
\end{align}
$$
How to handle with $A(0,k)$? How to establish an equation for $g(x,k)$?

Let us guess that $A(n,k) = \alpha \binom{n}{k} + \beta$. The recurrence reads
$$
\alpha \binom{n}{k} + \beta = \alpha \binom{n-1}{k} + \beta + \alpha \binom{n-1}{k-1} + \beta + c,
$$
from which we deduce $\beta = -c$. The base cases are
$$
\alpha \binom{n}{n} - c = \alpha \binom{n}{0} - c = 1,
$$
From which we deduce $\alpha = c+1$. All in all, the solution is
$$
A(n,k) = (c+1) \binom{n}{k} - c.
$$


What does "schema" mean? In a relational model,

a schema is something which specifies the name and data type of each field.
The word "schema" is also used in "conceptual schema", "physical schema" and "external schema".

What do "schema" mean separately in the above two cases? Are they
related?

Are they related to the "schema" in cognitive psychology?
Is "schema" used in other areas of computer science, such as
artificial intelligence, programming languages, ...?
What does "schema" mean in computer science besides database?

Thanks!

1. **What is Schema**-  In a relational database, the schema defines the tables, the fields in each table, and the relationships between fields and tables.

Yes, They are related to these 3 words,  "conceptual schema", "physical schema" and "external schema".

External schema for user views
Conceptual schema integrates external schemata
Internal schema that defines physical storage structures

No, It has no relation with "schema" in cognitive psychology

2. Yes, Schema used in other area also like in-

Programming & Algorithms -XML Schema , Schema (genetic algorithms)
Science- Body Schema, Image Schema
Mathematics- Axiom Schema (related to Mathematical Logic)

3.  Refer above point 1 & 2


Enumerate the terms resulting from decomposing a number by repeated divisions by 2 Consider a natural number $n>1$. We express it as $\lfloor \frac n 2 \rfloor + \lceil \frac n 2 \rceil$. We repeat the process for each of the two terms until all terms are 1 or 2. For example $9 = 4 + 5 = 2 + 2 + 2 + 3 = 1 + 1 + 1 + 1 + 1 + 1 + 1 + 2$.

There will be $2^{\lfloor \log_2 n\rfloor}$ terms because the decomposition forms a complete binary tree of height $\lfloor \log_2 n\rfloor$.

I am looking for an iterative form of this recursive process. The enumeration $a_0 = 0, a_{i+1} = \left\lfloor \frac {(i+1) \cdot n} {2^{\lfloor \log_2 n\rfloor}} \right\rfloor - a_i$ comes close because it does satisfy the following conditions: (a) each term is 1 or 2; (b) the sum of the first $2^{\lfloor \log_2 n\rfloor}$ terms is $n$. But the elements are not identical to the recursive decomposition form.

Any help would be welcome. Thanks!

Denote the total number of terms by $m = 2^{\lfloor \log n \rfloor}$. Suppose that $m_1$ terms are equal to $1$, and $m_2$ terms are equal to $2$. Thus
$$
n = m_1 + 2m_2 = m + m_2,
$$
from which we find that $m_2 = n-m$ and $m_1 = 2m-n$. So if you arrange the terms in nondecreasing order, the first $2m-n$ would be $1$, and the remaining $n-m$ would be $2$.


How to implement a prolog interpreter in a purely functional language? Is there a clear reference, with pseudo-code, on how to go about implementing a Prolog interpreter in a purely functional language? That which I have found so far seems to deal only with imperative languages, is merely a demonstration of Prolog implemented in itself, or offers no concrete algorithm to use for interpretation. I would be very appreciative of an answer.

Since Prolog = Syntactic Unification + Backward chaining + REPL

All three parts can be found in Artificial intelligence: structures and strategies for complex problem solving by George F. Luger. In the fourth edition of the book all three parts are implemented in LISP in Section 15.8, Logic Programming in LISP. He also puts the same code in his other books, but I don't have all of them for noting here. The code for his books can be found here.

Another source with all three parts can be found in Paradigms of artificial intelligence programming: case studies in Common Lisp by Peter Norvig. See Chapters 11, Logic Programming and 12, Compiling Logic Programs. The code for his book can be found here.

Another source is Structure and interpretation of computer programs by Hal Abelson, Jerry Sussman and Julie Sussman. See Section 4.4  Logic Programming. The site for the book is here and the code for the book is here.

It is not uncommon to find the unification algorithm with back chaining implemented in many applications if you know where to look; it is especially prevalent in type inferencing in functional compilers. Using the keywords unification or occurs helps to spot the functions. Also most implementations use unif for the name of the unification function.

For a version of Prolog, less the REPL, done in OCaml see Code and resources for "Handbook of Practical Logic and Automated Reasoning" - prolog.ml

A translation of the book code to F# can be found here.
A translation of the book code to Haskell can be found here.

In terms of finding the code, the unification algorithm is easiest to find, then implementations with back chaining imbedded in applications. Finding a fully functional implementation of Prolog in a functional language with an REPL is the hardest. Most of the time the code is not in a format for direct use within PROLOG; it is heavily customized to enhance performance, so you may find the code but it will not be worth the price to tease out the parts you want. My advice would be to read Luger's book and build it up from scratch in your language of choice, even if it means installing and learning LISP and translating to do so.

EDIT

Since this is a duplicate question from StackOverflow and the OP is new and in the comments says:

  To give more context, I'm attempting to implement type inference,
  however the intricate features in the type system of my language
  (Dependent types, refinement types, linear typing to name a few of the
  less common ones) make me feel that it would be useful to base my type
  inference off of the algorithms driving Prolog as to obtain a very
  general algorithm. I will note that I'm entirely self taught, so my
  knowledge is lacking in large areas.

I'll expand on this here, but realize the OP should ask a new question.

For some intro stuff see implementing type inference.

The best book I know on this is Types and programming languages by Benjamin C. Pierce.
The book's site is here. The resources with links to OCaml code is here. And recently started but mostly complete translation of this to F# is here.

Dependent types: pg. 462
Refinement types: pg. 207
Linear logic and type systems: pg. 109


Find the longest repeated pattern in a string I'm looking for an efficient algorithm to find the longest repeated pattern in a string.

For example, consider the following string of numbers:

5431428571428571428571428571427623874534.

As you can see, 142857142857 is the longest pattern which is repeated for a couple of times (at least twice) in this string.

The repeated string should not contain any re
any idea rather than brute-force?

The problem is surprisingly non-trivial. First, two brute force algorithms. A square ("repeated pattern") is given by its length $\ell$ and position $p$, and takes time $O(\ell)$ to verify. If we go over all $\ell$ and $p$, we obtain an $O(n^3)$ algorithm. We can improve on that by first looping over $\ell$, and then scanning the string with two running pointers at a distance of $\ell$. In this way, one can verify whether a square of length $2\ell$ exists in linear time, giving a total running time of $O(n^2)$.

Kolpakov and Kucherov developed an algorithm for finding all maximal repeats in a word in time $O(n)$ [1], and their algorithm can be used to find all maximal squares in time $O(n)$. A repeat is a subword of the form $w^kx$, where $k \geq 2$ and $x$ is a proper prefix of $w$. The largest square contained in that repeat is $(w^{\lfloor k/2 \rfloor})^2$. Using this formula, given all maximal repeats in a word (of which there are only $O(n)$ many), one can find the largest square.

[1] Kolpakov, R., & Kucherov, G. (1999). Finding maximal repetitions in a word in linear time. In Foundations of Computer Science, 1999. 40th Annual Symposium on (pp. 596-604). IEEE.


Minimum perfect matching with uneven vertices? Given this graph, what is the minimum perfect matching? What do you do, when there is an uneven number of vertices?

A perfect matching is one that includes every vertex so only graphs with an even number of vertices can have a perfect matching. If the number of vertices is odd, there is simply no perfect matching.


How to find the asymptotic runtime of these nested loops? i=n;
while(i>0) {
  k=1;
  for(j=1;j<=n:j+=k)
    k++;
  i=i/2;
}

The while loop has the complexity of $\lg(n)$ the j value of inner loop runs 1,3,6,10,15...
increase like 2,3,4,5,...

But how to find the overall complexity ?

$j$ satisfies the recurrence $j_k = j_{k-1}+k$. Note that another sequence, $s_k = k^2$ satisfies $s_k = s_{k-1} + 2k-1$.

$$j_k = \sum_{i=1}^k i = \frac 1 2\sum_{i=1}^k 2i = \frac 1 2(s_k+k)$$

This should give you enough to find the largest $k$ such that $j_k < n$.


What is an optimal algorithm? I'm a computer science newbie and I thought I understood cases and bounds when I first studied them. I would take worst case as upper bound and best case as lower bound, but now I know that they are two separate concepts, so now I came up with this assertion which I think is correct, but I want to sanity check it:

  An algorithm can be said to be optimal if the function that describes its time complexity in the worst case is a lower bound of the function that describes the time complexity in the worst case of a problem that the algorithm in question solves.

As of now what I understand is that the so called bounds are "interactions" between functions and that the "cases" are just particular functions arising from particular situations regarding an algorithm's performance or the number of operations needed to solve a problem. Would that definition of an optimal algorithm be correct?

EDIT: the question is more aimed towards the proper theoretical understanding of cases and bounds than the real life properties of an optimal algorithm that extend to other concepts.

There are various notions of optimality one can think of. One popular notion of optimality is worst-case running time, which is what you describe:

  An algorithm for solving a problem $P$ is asymptotically optimal with respect to worst-case running time if it runs in time $T(n)$, and any algorithm for $P$ runs in time $\Omega(T(n))$.

In fact, this notion is ambiguous, since it's not clear what the parameter $n$ is. Indeed, in some cases there are several relevant parameters, which we sometimes want to consider at the same time. This is the case with graph algorithms, in which there are two natural parameters: the number of vertices and the number of edges.

An additional point of ambiguity is the computation model against which everything is measured. In theoretical work, we usually consider the word RAM as our computation model, but other models are possible.

The definition above is about the asymptotic running time. This manifests itself in two ways. First, we only care about the time complexity of the algorithm up to constant factors. Second, we only care about the behavior for large $n$. In practice, sometimes $n$ is fixed, and then the definition above doesn't make any sense.

Whereas worst-case running time is a popular parameter, other parameters are also relevant. Some examples include average-case running time (whenever there is a natural input distribution) and memory consumption. Only you can say which notion of optimality is most relevant for you.


Is a TM that is simulated by a universal TM theoretically inherently slower than the TM itself? When a CPU simulates a certain program, as they do all the time, this is inherently slower than if the program would have been "baked in" into the hardware and computed directly. We know this from practical experience.

My question is: Is there some theoretical relationship that shows that a program that is simulated by a universal program, is inherently slower than that program executed by itself?

The way i see it, talking about slowdowns on simulations of a specific Turing machine $M_0$ doesn't make much sense. I could always just run $M_0$ and call this a simulation, which will result in no slowdown. I could also hardwire the code of $M_0$ , and in case the input was $M_0$, use some better algorithm (as D.W. did in his answer).

The more interesting question here is (in my opinion at least), what is the optimal slowdown achievable when simulating an arbitrary Turing machine $M$ on some input $x$ ? (asymptotically, in terms of $|x|$ and the length of the description of $M$)

We look at all possible inputs, and examine the worst case slowdown (perhaps for some machine $M_0$ you can do a better job, but here we consider the worst case running time).

More formally, Let $\mathcal{U}(\langle M\rangle,x)$ denote the universal Turing machine, which takes as input an encoding of a machine $M$ and some string $x$, and outputs $M(x)$, or does not halt in the case that the computation of $M$ on $x$ does not halt. We know that we can implement $\mathcal{U}$ in such a way that if the computation $M(x)$ requires time $T$, then $\mathcal{U}(\langle M\rangle,x)$ requires time $O\left(T\log T\right)$. Here the $O$ notation hides constants which depend on the number of states and the alphabet size of $M$ (but independent of $|x|$). Your question then translates to whether we can implement $\mathcal{U}$ such that the computation of $\mathcal{U}(\langle M\rangle,x)$  requires only $O(T)$ time?

It seems that for single tape machines, it is not known whether this $\log T$ factor is necessary, however for $k\ge 2$ tapes machines we can avoid it (proved by Furer, 1982). See this post by Kaveh for a detailed discussion and related quotes.


Time estimation for successful brute force attack If I have a password  =

"passwordPASSWORD"

and the time it takes to encrypt the password successfully is:

353259.545 nano seconds

is there a formula that can work out the time taken to successfully conduct a brute force attack on the password?
I was thinking:

AvrgTimeToEncrypt^PasswordType x PasswordLength ?

Passwords are not encrypted they are hashed with proper password hashing algorithms like Scrypt, PBKDF2, or better Argon2, the last is the winner of the 2015 password hashing competition.
I would like to assume that you use one of the above, however, the time that you measured implies the opposite. At least, you used an iteration count as little as possible.
The attackers are not like you - and they will never be - to check a single candidate password one at a time. They like to use as much as possible parallelization. See hashcat as a good example. CPUs, GPUs, ASICs, and FPGAs can be combined to find the target. Simple hashing can be searched massively in parallel even in a single GPU.
Therefore we need to mitigate these attacks as much as possible. The proper password hashing algorithms are memory-hard functions to prevent the massive parallelization and they have iteration count to increase the timing. With these, the attacker's massive parallelization is prevented and the search timing is crippled. Usually, the work factor is adjusted for the user's perspective so that the user does not wait so much for a login. For example, 400K iteration is for PBKDF2 may enough.

I was thinking:

AvrgTimeToEncrypt^PasswordType x PasswordLength ?

Once we forced the attacker to a single run on the single CPU thread, or one in a GPU, etc. we can talk about the timings a bit more precisely.
Let formalize as;

$\mathcal{S}$ as the password space.
$t$ is the execution time of a machine to test a given password hash and candidate from $\mathcal{S}$. (we use a uniform approach here, the timing will be different in a CPU, GPU).
$c$ is the number of machines that the attacker can use.

Now the search time of the space $\mathcal{S}$ is
$$ \frac{|S|}{t \cdot c}$$


Why do Θ-bounds not survive taking differences? $f_1$, $f_2$, $g_1$, and $g_2$ are functions such that:

$$f_1 = \Theta(f_2)$$
$$g_1 = \Theta(g_2)$$

I was able to prove that:

$$\frac{f_1}{g_1} = \Theta\biggl(\frac{f_2}{g_2}\biggr)$$

But I can't understand why the following statment is not necessarily true:

$$f_1 - g_1 = \Theta(f_2 - g_2)$$

The proof is by counterexample. Consider the following functions:

$$f_1(x) = 2x$$
$$f_2(x) = x+1$$
$$g_1(x) = x$$
$$g_2(x) = x$$

First, we can see that $f_1 = \Theta(f_2)$ and $g_1 = \Theta(g_2)$. Finding constants to prove the four big-Oh relationships involved is straightforward (in particular for $g_1$ and $g_2$).

Next, we can observe that $f_1 - g_1 = x \neq \Theta(1) = \Theta(f_2 - g_2)$.

Notice that the choice of $2$ and $1$ for the above functions is unimportant, so long as you choose them so that the difference between $f_1$ and $g_1$ is more than constant and the difference between $f_2$ and $g_2$ is constant.


Number of iterations of the Euclidean algorithm I have a doubt about the runtime of the Euclidean algorithm; the slide of my Professor says:

The calculation of $\mathrm{GCD} (a, b)$ stops at the most after $2\log_2 a$ iterations.

Since $\log_2 a$ is the size of the input,
calculation requires a linear number of iterations.
The algorithm therefore has polynomial runtime.

I don't get how he could deduce (2) from (1), and (3) from (2); until now, the only concept of theory that he gave us is that to represent a positive integer, we need $1+\log_2 x$ bits.

There's very little to deduce.

The number of iterations is linear in the size of the input because the size of the input is $2+\log_2 a + \log_2 b$ and the number of iterations is $2\log_2 a$, which is less than $2(2+\log_2 a + \log_2 b)$, so is less than twice the length of the input.  Hence, (2) holds.

Each iteration requires only a polynomial number of steps: all it does is tests and simple arithmetic operations, all of which can be done in time polynomial in the number of bits involved.  Therefore, the total required time is some linear function (the number of iterations) times some polynomial function (the cost of each iteration), which is another polynomial function. So (3) holds.


Highest Product of X Items How do you find the highest product of X items?
This should optimize for runtime complexity and protect from overflows from large products.

Inputs

An array of both positive and negative Ints representing potential products to the solution
An Int representing the number of products required for the solution

Output: An Int representing the highest product of X amount of numbers.

For example, for the highest product of 3 items, the input is iterated through while updating the following variables. After the iteration has completed in $O(n)$ time, the highest product of three variable is returned as the solution.

Lowest number
Highest number
Lowest product of two
Highest product of two
Highest product of three

Let the integers be $a_1,a_2,\dots,a_n$ sorted in decreasing order of magnitude, so $|a_1| \ge |a_2| \ge \cdots$, and suppose you want to find the product of $k$ of them that is as large as possible.
Then:

If $a_1 \times \cdots \times a_k$ is positive, it is the solution.

Otherwise, if $a_{k+1}$ is positive, the solution is $a_1 \times \cdots \times a_{k+1}$ (but omit $a_i$ from the product, where $a_i$ is the largest of the negative numbers in $a_1,\dots,a_k$, i.e., closest to zero).

Otherwise, if $a_{k+1}$ is negative and at least one of $a_1,\dots,a_k$ is positive, the solution is $a_1 \times \cdots \times a_{k+1}$ (but omit the smallest positive number of $a_1,\dots,a_k$ from the product).

Otherwise, if at least one of $a_1,\dots,a_n$ is positive, the solution is $a_1 \times \cdots \times a_{k-1} \times a_j$ where $a_j$ is the largest positive number in $a_1,\dots,a_n$.

If all of $a_1,\dots,a_n$ are negative and $k$ is odd, then the solution is $a_{n-k+1} \times \dots \times a_n$.

This can be computed in $O(n \lg k)$ time using a heap of size $k$.


Unrecognizability of HALT I am currently stuck on a question from Sipser's book of automata. The question goes like this:

  Consider the following language: V = {w|w = 0a for some a which is an
  element of HALT} U {w|w=1b for some b which is an element of
  complement of HALT }

  Prove that V is unrecognizable? Prove that complement of V is
  unrecognizable?

I kinda know that to prove them we have to use contradiction but I got stuck after that and haven't been able to come up with any solution up till now. Any pointers/hints would be appreciated.

If $V$ was recognizable then the language of Halting problem could be reduced to $V$ as following.

Let $M_V$ be a TM recognizing $V$, i.e, $M_V$ accepts $x$ if $x \in V$. Let $u$ be some string (description of a TM). Then we run $M_V$ on $0u$ and $1u$ by dovetailing. $M_V$ will eventually halt on one of these inputs since $u$ is either in $HALT$ or not in $HALT$. So, when it halts we simply check: if $M$ has halted on $0u$ then $u \in HALT$, else if $M$ has halted on 1u then $u \notin HALT$. Thus this implies that $HALT$ is decidable which is impossible.

Similarly for $\overline{V}$. Let $u$ be some string (description of a TM). If $M_{\overline{V}}$ accepts $0u$ then $u \notin HALT$. If $M_{\overline{V}}$ accepts $1u$ then $u \in HALT$.


What is the optimal way to solve the following optimization problem You are given a function $F$, which can take one or more positive integer operands.
Let $L=\{a_1,a_2\ldots a_n\}$.

We need to compute the function $F(L)$ using the least number of transformations/steps.
Computing $F(L)$ is not the main goal. Computing it in the fastest possible way is the goal.

Following rules are allowed to be applied to this function.

--> If $L$ has only one element say $x$, then the $F(L) = x$;

--> If all elements in $L$ are even then $F(L)=2F(L')$, where $L'$ contains all elements in $L$ divided by 2.
For example $F(4,8,10)= 2*F(2,4,5)$

--> If some elements in $L$ are odd and some are even, then $F(L)=F(L')$, where $L'$ has same odd elements as L, but the even elements in $L$ are made odd by removing the factor 2.
For example $F(6,9,20)=F(3,9,5)$

--> If any of the integers in the list is 1, then $F(L)=1$;

--> If two or more integers in $a_1,a_2\ldots a_n$ are same, then we can remove the copies and keep only one of them.
For example $F(4,5,6,5)=F(4,5,6)$

--> For any pair $a_i$ and $a_j$ where($a_i<a_j$), you can replace $a_j$ with $a_j-a_i$

$F(4,7,8)=F(4,(7-4),8)=F(4,3,8)$

It is easy to notice that this process terminates, because at each step, either the value one of the operands is reduced or the number of operands is reduced.

Given $L$ can there be a DP to optimize the number of operations needed to solve $F$, or is there a greedy strategy that is optimal or constant approximate of the optimal?

For example

Consider the following instance

$F(15,30,45)$

Depending on your choice, you can compute this value in several ways.

\begin{align*}
F(15,30,45)& =F(15,30,45-30)=F(15,30,15)\\
& =F(15,30)\\
& =F(15,30-15)=F(15,15)\\
& =F(15)=15
\end{align*}

which takes 4 iterations.

Another way is

\begin{align*}
F(15,30,45)& =F(15,30-15,45)=F(15,15,45)\\
& =F(15,45)\\
& =F(15,45-15)=F(15,30)\\
& =F(15,30/2)=F(15,15)\\
& =F(15)=15
\end{align*}

which takes 5 iterations.

I want an algorithm which finds the optimal solution.

Yes, there is a simple way to compute $F$.

Proposition: $F(a_1,a_2\ldots a_n)=\gcd (a_1,a_2\ldots a_n)$, where $\gcd$ is the greatest common divisor.

Proof: I will leave it as an exercise. Hint, the replacement of $a_j$ by $a_j-a_i$ whenever $a_i<a_j$ is very powerful.

Here is a simple and efficient algorithm to compute $F(a_1,a_2\ldots a_n)$.

Let $r = a_1$.
Iterate $i$ through $2,3, \cdots, n$, setting $r$ to $\gcd(a_i, r)$. Here $\gcd(a_i,r)$ can be computed by any of your favorite GCD algorithms such as Euclidean algorithm or binary GCD algorithm.
return $r$.


Can you determinize an NFA in PSPACE? QUESTION

Given some NFA $A$, can you simulate the determinization of it (using Subset-Construction for example) while remaining in $PSPACE$?

MORE DETAILS

I'm asking this as I want to be able to construct $\overline A$ (the complement of $A$) in poly-space complexity.

More specifically, I want to receive $\left <A,w \right >$ as input ($A$ is an NFA) and decide if $w \in \overline A$. So I want to construct $\overline A$ and simulate (in poly-space) $\overline A$ on $w$.

MY ATTEMPTS

I know that determinizing an NFA (using Subset-Construction) can blow up exponentially. But, I thought that the determinization and/or the simulation can happen "on the fly", where each step overrides the previous one.

Other then this thought, I can't manage to develop it into an actual algorithm (if it's at all possible).

Thank you.

The subset construction can be computed (and negated) in polynomial space. Remember that the output doesn't count as part of the space usage in bounded space computation.

Determinization can exponentially increase the number of states: the language of $0$–$1$strings such that the $k$th-from-last character is $0$ can be recognized by an NFA with something like $k+1$ states, but any DFA for that language has at least $2^k$ states.

So determinizing doesn't give you a polynomial space algorithm to determine if an NFA accepts its input.  But you can simulate all computation paths of the NFA simultaneously: as you read the input, just keep track of the set of states the automaton could be in, and see if that set includes an accepting state once you've read the whole input.