Solution of complex recurrence relation Do anyone have any idea how to solve this recurrence?$$T(k) = \sum_{i=1}^{k/2} {k \choose i}T(i)T(k-i)$$

I am working with this kind of recurrence for the first time and don't have much idea of how to proceed. But, for beginning I was trying to guess the solution and use substitution method. But, in the guessing part itself I am stuck. It seems like the solution should be exponential to $k$.

Everything becomes much simpler if when $n$ is odd we stop the sum at $\lfloor n/2 \rfloor$, and when $k$ is even we discount the term corresponding to $k/2$ by a half. In that case you can write
$$ 2T(k) = \sum_{i=1}^{k-1} \binom{k}{i} T(i) T(k-i) $$
and so, putting $T(0) = 0$, we get that for $k \geq 2$,
$$ 2T(k) = \sum_{i=0}^k \binom{k}{i} T(i) T(k-i). \tag{1}$$
(When $k = 1$ this reads $2T(1) = 0$.)

Now define the exponential generating function
$$ P = \sum_{n \geq 0} T(n) \frac{x^n}{n!}. $$
Put $T(1) = c$. The identity (1) implies the equation
$$ 2(P-cx) = P^2. $$
Solving the quadratic, we obtain
$$ P = 1 - \sqrt{1 - 2cx} = 1 - \sum_{n \geq 0} \frac{(2n)!}{(1-2n)(n!)^24^n} (2cx)^n = \sum_{n \geq 1} \frac{(2n)!(c/2)^n}{(2n-1)n!} \frac{x^n}{n!}. $$
We conclude that for $n \geq 1$,
$$
T(n) = \frac{(2n)!(c/2)^n}{(2n-1)n!} \sim \frac{1}{\sqrt{2} n} \left( \frac{2c}{e} n \right)^n.
$$
The first few terms (starting with $T(1)$) are
$$
c,c^2,3c^3,15c^4,105c^5,\ldots
$$


Minimise simultaneous equation remainder I'm not sure if this is the right place to ask, or what the right terminology to use is. The problem I have is this:
I have a vector for example:
v = [1,4,5,6,3,1,4,5,6,7,...7]

and I have a set of other vectors for example:
a1 = [0,0,0,0,0,1,2,3,0,0,...0]
a2 = [0,0,0,0,1,2,5,0,0,0,...0]
a3 = [0,0,0,2,2,3,0,0,0,0,...0]
a4 = [0,0,1,1,1,0,0,0,0,0,...0]
...
an = [0,0,1,1,1,0,0,0,0,0,...0]

I want to find out what linear combination of the vectors is closest to v. I define the distance of two vectors to be the sum of the absolute differences of each of its elements. For example the distance between [1,2,3] and [2,2,2] is abs(1-2) + abs(2-2) + abs(3-2) = 2.

Does such an algorithm exist? If it doesn't exist, are there any algorithms that could get me close to a solution?

Ideally I would like an integer multiple of each vector, does such a solution exist with integer multiples?

This problem is an instance of linear programming.

If you allow fractional multiples then it can be solved in polynomial time using standard techniques for linear programming.

If you require integer multiples the problem is (strongly) $NP$-complete. There is a very easy reduction from 1-in-3-SAT. Let the dimension of the vectors be equal to the number of clauses, let the target vector be $(1,\ldots,1)$ and for every variabele create a vector $a_i$ that for each clause it appears in has a $1$ in that position (and a $0$ otherwise). You can achieve distance $0$ if and only if the formula is satisfiable.


Derive Turing Machine with high level description So I have been going over Turing machines for my revision and came across an old worksheet with the question:

Derive a Turing Machine using high level description with stages to decide on the following language {<,>|           }.

I thought I understood Turing machines and CNF until I came across this but I can't figure it out. There is no answer sheet for this so I was wondering could someone answer it with steps to guide me through it so I can understand?

Its easy to check that $C$ is given in Chomsky Normal Form, because you just have to iterate through the production rules and make sure each one of them satisfies the definitions for being a CNF production.
Then, the harder part is deciding whether $C$ can produce $s$ or not.
Notice, that a CNF will derive a word with length $n$, in exactly $2n-1$ steps. (every production will either transform a variable to the letter corresponding to it, or will create one new variable)
Keeping this in mind, we can just iterate through all production chains that contain $2n-1$ steps (for $n=|s|$), and check whether we saw $s$ or not. If $s\in L(C)$, then we will see it, since $s$ can be derived with $2n-1$ steps. And if $s\notin L(C)$ we won't see it, therefore the algorithm is correct.


How to find the square with the highest total sum I have an integer matrix of size 4n x 4n. I need to select a part of the matrix of size n^2 from which adds up to the most.

For example if n = 3. I have a matrix of size 12 x 12. In the below picture, you can clearly see that n^2 square (outlined in red) adds up to the most. For simplicities sake, I made all the numbers 5, expect for 9 of the boxes which are 9999 so its clear that that is the n^2 squares that add up to the most.

My approach to solving this problem was to essentially create a n^2 square and brute force the entire 4n x 4n matrix. However, that runs in O(n^4) time complexity. How can I do it in O(n^2)?

Try building a summed area table—a table where the value in each cell is the sum of all the values above and to the left, inclusive, of the cell in the original table. See if you can figure out an $O(n^2)$ solution from that.


Deterministic and randomized communication complexity of set equality Two processors $A, B$ with inputs $a \in  \{0, 1\}^n$ (for $A$) and $b \in  \{0, 1\}^n$
(for $B$) want to decide whether $a = b$. $A$ does not know $B$’s input and vice versa.

A can send a message $m(a) \in  \{0, 1\}^n$ which $B$ can use to decide $a = b$. The communication and computation rules are called a protocol.

Show that every deterministic protocol must satisfy $|m(a)| \ge  n$.
State a randomized protocol that uses only $O(\log_2n)$ Bits. The protocol should always accept if $a = b$ and accept with probability at most $1/n$ otherwise. Prove its correctness.

For the first point, try a counting argument. How many different messages $m(a)$ can $B$ receive, if $|m(a)|<n$? How many different strings can $A$ have?

For the second point, try first analyzing the trivial randomized protocol (randomly fixing $\log(n)$ positions of the string and sending these bits of $a$). Clearly, this protocol always accepts if $a=b$. Assume $a\neq b$, what is the probability that $\log(n)$ randomly picked bits are the same? Does that suffice?


What are the guidelines/tips for calculating the complexity of a chained-recursive function? Any help will be appreciated, as I wasn't able to find much about it online in the last few days and I can't seem to write a suitable recurrence relation for this kind of functions..
Are there any tips or general guidelines for calculating the complexity (time/space) for functions of the following form?
int f1(int n)
{
    if(n < k) // for an arbitrary k
        return 1;
    return f1(f1(n/2) + f1(n/3) - f1(n/5));
}

Or:
int f2(int n)
{
    if(n < k)
        return k;
    return f2(g(n/k));
}

int g(int n)
{
    // Some code of known complexity here to calculate an arbitrary c
    return f2(n/c);
}

Specifically, recursive functions that call themselves with their own return value as a parameter (e.g func(func(value)); )
Thank you in advance for any assistance provided.

I cant think of one simply way to solve such questions, but I can show you a way to start tackling the questions and making them simpler.
In such cases, that $f$ recursively calls itself with their own return value, the running time of $f$ might depend heavily on its output. So contrary to usual complexity computation tricks, here we want to know precisely what the output of $f$ is. For example, we can prove by induction that f1 will always output 1.
Now, replace each inner recursive call to $f$ with the value it returns. In the f1 case, we replace f1(f1(n/2) + f1(n/3) - f1(n/5)) by f1(1+1-1) which is simplified to f1(1). This means that we did a total of 4 calls to $f$, and for each call to $f$ we know exactly what the input was. Here, in this example, the inputs are $n/2,n/3,n/5,1$.
Finally, we can start calculating the time complexity: since we know how many recursive calls happened and what input was there for each recursive call, we can build a recursive formula for the time complexity. In the case of f1, it will be: $T(n)=T(n/2)+T(n/3)+T(n/5)+T(1)+c$, since we add a recursive call with the input of f1 for each time f1 was invoked.
This can be solved using traditional techniques, such as the master theorem.


Techniques to create a PDA for a language that is the conjunction of two languages When I was working with finite automata, I figured out that we can put together two FA two build a new one that is the intersection between the two. This is possible because regular languages are closed under intersection. Now, I am having many difficulties in drawing PDAs especially the ones that are apparently the intersection of two other PDAs. For example, suppose I am asked to build the PDA for $$\{w \mid w \text{ is a palindrome and w has at most two 0s } \}$$

I think I would be able to build a PDA that recognises palindromes (which is one of the easiest ones), and also one that recognises a language that has at most two $0$s. But I am having many difficulties in building a PDA for the language above.

Apparently CFG are not closed under intersection, so I suppose there's no mechanical way of coming out with a solution for an intersection of two languages. Since this might be the case, do you have any suggestions on how could I start thinking on how to draw a PDA that is apparently the intersection of two other languages?

Note that I am asking for techniques to come up with PDAs for languages that are the conjunction of other simpler languages and not for a solution for the particular case above.

The intersection of a CFL and a regular language is itself a CFL.  There is a standard construction for computing this intersection.  It's documented in automata theory textbooks; look in your favorite automata theory textbook, and you should find it there.


Efficient algorithms for checking non-emptiness of the language of a Turing machine I know that language non-emptiness is TM recognizable, and one can perform a BFS to find an input string that TM accepts, if there is any. But, what is the most efficient algorithm for that?

The problem is undecidable. There are no algorithms for it, so there are no efficient algorithms.


Can a trend of android phones slowing down after 2-3 years of usage be attributed to the low durability of RISC CPU used in them? Laptops, PCs (don't consider Apple products here) have processors that are mainly built on x86 and their life cycle is of the order of 5-10 years.
Or the frequent changing of smartphones has a perception/psychological side of it and not the durability issues of the hardware?

Android phones slow down because the software applications are rapidly changing. More features get added, and this makes the software consume more memory (RAM) and CPU time. Software keeps getting updated and each update results in it requiring more resources. In response to this, smartphone manufactures have increased the capabilities of the hardware they manufacture. RAM, CPU Frequency, number of cores are increased, and this increases the performance. Thanks to Moore's law, the hardware capabilities and performance tend to be increased without any noticeable increase in cost.
One more reason why smartphones need to be changed continuously is because the Operating System gets updated. Google and Apple allows users to update their Operating Systems by using the same phone only a limited number of times. After this limit, users have no other choice but to buy a new phone to use the newer operating systems. As the support of applications on older models of smartphones gets dropped, the user has no other choice but to upgrade to newer phones. This is known as planned obsolescence.
For x86, a similar phenomenon is observed, especially in Windows based laptops. As Windows keeps getting updated, you will observe that the laptop gets slower. This problem can be solved to some extent by increasing the RAM (which is not possible in the case of smartphones). For PCs, you can upgrade the CPU, GPU, RAM and storage, so they tend to be used the longest. For PCs, the Operating System can also be easily changed, and a lighter operating system can be used, which improves the performance.


Understanding a boolean expression in λ-calculus (NOTE: This is not a homework question at at all.  Rather, this was something that I thought that I understood (at least on the surface), but now appear to have no clue about, and am not currently finding any resources helpful.  I know that we typically like to see what people have tried, but I am honestly discombobulated enough at this moment that I am truly unsure about where to even begin.  If this turns out to be a duplicate that I haven't found, I would also be perfectly happy.  I just want to understand.)

Anyway, on to the question itself:

So, if $\lambda xy.x$ represents true, and $\lambda xy.y$ represents false, then I have been told that $(\lambda b.b \ \ \lambda xy.y \ \ \lambda xy.x)$ is a not function, because the expression

$(\lambda b.b \ \ \lambda xy.y \ \ \lambda xy.x) \  \lambda xy.x$ results in $\lambda xy.y$,

and the expression

$(\lambda b.b \ \ \lambda xy.y \ \ \lambda xy.x) \  \lambda xy.x$ results in $\lambda xy.x$.

Where I am stuck is that I don't see how to apply $\beta$-reductions here.  There are three expressions inside the parenthesis.  How is one of them chosen by applying the outer expression?

It's a very bad idea to omit parentheses. Correct is:
$$\lambda b . b (\lambda x y . y) (\lambda x y . x)$$
Next, it is confusing to reuse bound variables, so let me rename them:
$$\lambda b . b (\lambda x y . y) (\lambda u v . u)$$
And now we can apply this to $\lambda p q . p$ (which is just "true" with bound vraiables renamed yet again):
\begin{align*}
(\lambda b . b (\lambda x y . y) (\lambda u v . u)) (\lambda p q . p)
&=_\beta (\lambda p q . p) (\lambda x y . y) (\lambda u v . u) \\
&=_\beta (\lambda q . (\lambda x y . y)) (\lambda u v . u) \\
&=_\beta (\lambda x y . y).
\end{align*}
So we did get false. In every step there was exactly one $\beta$-redex. By the way, writing $A B C$ in $\lambda$-calculus means $(A B) C$ by convention.

I will leave the other one as exercise.


Given a set of LTL formulas, on which states does the Kripke structure hold? I'm currently learning about LTL and CTL formulas and to get a better understanding I try to manually interpret the formulas over a given Kripke structure. Since I'm not 100% sure if my results are correct I would appreciate if anyone can verify them.
Task:
I showed on which states the given LTL formular hold.
Some LTL notation notes:
$X$ equals $\bigcirc$
$G$ equals  $\Box$
$F$ equals  $\diamond$

$Fc = \{\}$
My interpretation: $Fc$ means that on all paths $c$ holds sometimes the future. Since all paths come along $t4$ it doesn't hold for any state.

$G(b \vee c) = \{\}$
My interpretation: For all paths holds globally b or c.

$G(Fb) = \{t0, t1, t2, t3, t4, t5, t6\}$
My interpretation: For all paths holds globally that eventually b will be true.

$G(b \Rightarrow (Xa \Rightarrow Xb)) = \{t0, t1, t2, t3, t4, t5, t6\}$
My interpretation: Since $Xa \Rightarrow Xb$ is true for every state the implication $b \Rightarrow (Xa \Rightarrow Xb)$ must hold for all states too sinde $? \Rightarrow true$ is always true.

$a U (b U c) = \{t1, t3, t4, t5\}$
My interpretation: Following paths are valid: aaaaabbbc, bbbbc, c, ccc. Therefore the states $t1, t3, t4, t5$ are valid.

So can anybody confirm my results?

A couple of comments:

Note that "in the future" is not strict, i.e. $Fb$ is also satisfied whenever $b$ itself holds.
Looks fine to me.
Also ok, though I'm not sure if your interpretation would be very enlightening in a more complicated Kripke structure.
"$Xa\Rightarrow Xb$ is true for every state" is a CTL-ism. What you want to say is that for every state along every path, if $a$ holds in this state and $b$ holds in the next state, then $a$ also holds in the next state.Is this the case?
Here you want some finite number (possibly $0$) of $a$s, followed by some finite number (possibly $0$) of $b$s, followed by a $c$. Is this what you see along every path starting in the states you give?


Is string spliting formally defined when the string delimiter is an empty string? Depending on the API/language you use, splitting the string "ABCD" using "" as a delimiter gets you:

["A", "B", "C", "D"] in Java, Javascript, and Go
["", "A", "B", "C", "D", ""] in Rust
["ABCD"] in C#
Fails with an Exception in Python3

From the perspective of formal language design, what is the correct result of such an operation? Is it defined?
Disclosure: This question was posted at stack overflow but was closed as opinion-based. I was directed to post my question here instead.

Given sequences $A = [a_1, \ldots, a_n]$ and $B = [b_1, \ldots, b_m]$, write $A + B = [a_1, \ldots, a_n, b_1, \ldots, b_m]$ for their concatenation. Given a sequence of sequences $C = [C_1, \ldots, C_n]$, write $\Sigma(C) = C_1 + \cdots + C_n$ for their concatenation.
Define a splitting of a sequence $X$ by a sequence $Y$ to be a sequence of sequences $Z = [Z_1, \ldots, Z_k]$ such that $Z_i \neq Y$ and $Z_i \neq []$ for all $i = 1, \ldots, k$, and
$$X = \Sigma [Z_1, Y, Z_2, Y, z_3, \ldots, Y, Z_k].$$
For example, $[[a], [], [b, c]]$ is a splitting of $[a, u, v, u, v, b, c]$ by $[u, v]$.
Splitting by the empty sequence is not unique: $[a, b, c]$ may be split by $[]$ in several ways, among others $[[a],[b],[c]]$, $[[a,b], [c]]$ and $[[a,b,c]]$. From a theoretical point this is a rather trivial and non-interesting observation. The implementors of various string libraries need to deal with splitting by the empty sequence somehow, and as you show, they do.


PTAS definition vs. FPTAS From what I read in the preliminary version of a chapter of the book “Lectures on Scheduling”
edited by R.H. M¨ohring, C.N. Potts, A.S. Schulz, G.J. Woeginger, L.A. Wolsey, to appear around 2011 A.D.

This is the PTAS Definition:

  A polynomial time approximation scheme (PTAS) for problem $X$ is an
  approximation scheme whose time complexity is polynomial in the input
  size.

and FPTAS definition

  A fully polynomial time approximation scheme (FPTAS) for problem $X$
  is an approximation scheme whose time complexity is polynomial in the
  input size and also polynomial in 1/$\epsilon$.

Then the writer says:

Hence, for a PTAS it would be acceptable to have a time complexity proportional to $|I|^{1/\epsilon}$ where $|I|$ is the input size;although this time complexity is exponential in $1/\epsilon$. An FPTAS cannot have a time complexity that grows exponentially in $1/\epsilon$ but a time complexity proportional to $|I|^8/\epsilon^3$ would be fine. With respect to
worst case approximation, an FPTAS is the strongest possible result that we can derive for an NP-hard problem.

Then he suggested the following figure to illustrates the relationships between the classes of problems:

Here is my questions:

From the PTAS and the FPTAS definition, how does the writer conclude that the FPTAS cannot have a time complexity that grows exponentially in $1/\epsilon$? and what difference does it make if it can have such time complexity?
A time complexity like $(n+1/\epsilon)^3$ is acceptable for FPTAS but it is not for PTAS, then why FPTAS is considered to be a subset of PTAS?
What does he mean by: an FPTAS is the strongest possible result that we can derive for an NP-hard problem.
In the aggregate I would like to know what exactly these to concepts mean and, what are their distinct properties.

Thanks in advance.

Let me answer your questions in order:

By definition, a problem has an FPTAS if there is an algorithm which on instances of length $n$ gives an $1+\epsilon$-approximation and runs in time polynomial in $n$ and $1/\epsilon$, that is $O((n/\epsilon)^C)$ for some constant $C \geq 0$. A running time of $2^{1/\epsilon}$ doesn't belong to $O((n/\epsilon)^C)$ for any $C$.  An algorithm whose running time is $O((n/\epsilon)^C)$ is better than an algorithm whose running time is only guaranteed to be $O(n^C e^{D/\epsilon})$, since the dependency on $\epsilon$ is better for the first algorithm. Furthermore, for any $E$, we can find an $1+1/n^E$-approximation in polynomial time using the first algorithm but not using the second (at least not with the given guarantee).
A problem in which an $1+\epsilon$-approximation can be found in time $(n+1/\epsilon)^3$ is definitely in PTAS, since for every $\epsilon$ this is $O(n^3)$ (exercise) and so polynomial in $n$.
What the authors meant here is that since an NP-hard optimization problem can't be solved exactly in polynomial time, the best we can hope for is for it to be $\epsilon$-approximable in polynomial time, and furthermore with a good dependence on $\epsilon$. Among the common complexity classes, FPTAS gives the strongest guarantee on the dependence on $\epsilon$. But in practice we sometimes get an even better guarantee: the running time is polynomial in $n$ and in $\log(1/\epsilon)$. So it's not strictly true that FPTAS is the strongest possible result; it's only the strongest possible result among the options PTAS,FPTAS,P. If we made up a new class LPTAS (corresponding to time polynomial in $n$ and in $\log(1/\epsilon)$), then that would be a stronger guarantee.
Given an NP-hard optimization problem, it can't be solved exactly in polynomial time; the best one can hope for is to approximate it efficiently. Some problems are NP-hard to approximate to some constant $C>1$. For others, it is possible to approximate the problem arbitrarily well in polynomial time, and these problems have a PTAS and so belong to the class PTAS. It might be that a $1+\epsilon$-approximation takes time proportional to $e^{1/\epsilon}$, and so we can only apply this efficiently for constant $\epsilon$. If the problem has an FPTAS (and so belongs to the class FPTAS), then we know that the dependency on $\epsilon$ is only polynomial, and so we can approximate efficiently to within $1+1/n^C$ for any $C$.


Metrics and algorithms for complexity of a graph I am interested in what sort of metrics are there that try to give a measure of how complex a given graph is, what are the corresponding algorithms, and what is their time complexity. A short description or list of relevant paper would be great.

It might help to say that I have two graphs and I want to somehow tell which one is ``more complex." I will use this metric as a heuristic, so I would like to try various metrics on empirical data. (It might help even more if I say that those graphs represent two FSMs.)

You can use all sorts of properties of a graph this way; obviously how good they are for you depends on your purpose.

Non-comprehensive list of graph attributes, for general undirected graphs:

Compare simple graph attributes: $|V|$, $|E|$, $\frac{|E|}{|V|}$; you must decide if more or less is considered "more complex".
Obviously if the graph has multiple components, you can use that, as a measure of simplicity or complexity; and/or you can consider it multiple separate graphs.
Treewidth of the undirected graph; computing the treewidth of a graph is exponential-time in the treewidth, $k$; however, you can set $k$ to a constant, and compute the treewidth quickly (wrt. size of the graph) and consider graphs with higher treewidth to be "complex"
How "planar" a graph is

Crossing number (NP-complete problem to compute)
Compare the resulting Kuratowski subgraphs when planarity testing fails (such forbidden graphs can be extracted quickly, but there can be a large number of such graphs)

Presumably a higher number means that there are more non-planar crossings required, thus it is more complex.
Sparseness, average vertex degree, vertex degree distribution

A low average degree, with a nice distribution can indicate an evenly sparse graph, thus perhaps lower "complexity". Easy to compute, simply average the degree of each vertex over all of them; distribution is slightly more complicated I suppose; depends on how you choose to do it; see wikipedia on degree distribution.
Average eccentricity (see wikipedia on Distance (graph theory)), eccentricity distribution
Diameter, radius ratios. Example: large diameter, low radius (see (see wikipedia on Distance (graph theory)); test ratios of these on "complex" and non-"complex" graphs, see if it diffrentiates.
Compare the dimensions of the graphs (NP-hard)
Have some subgraphs you consider "complex", and test for subgraph isomorphism in your actual graphs (NP-complete), or, use Maximum common subgraph isomorphism (NP-hard)
Perhaps some sort of compressibility/entropy measure, but this touches on isomorphism; the same graph can be layed-out or represented in a matrix multiple ways, not all of them equally compressible. A canonical graph labeling could help with this, but that is itself difficult.

Some ideas for an FSM:

Size (though note that you can have equivalent FSMs of different sizes; these measurements are about the graph complexity, not necessarily FSM complexity)
You can do a topological sort or level structure, and compare them that way; possible measures of complexity: depth, level-width.
You can do a DFS, and detect cycles; perhaps more cycles == more complex?

Counting cycles can be a hard problem (NP-hard). Perhaps you can find some relaxation for your specific graphs, for example if they are planar (I don't know that counting cycles in planar graph is any easier, but you would start searching for special cases based on what special cases you do know). There are some approximation algorithms for general cycle counting though. See Counting cycles in an undirected graph using DFS-XOR algorithm, (IEEE paywalled off); abstract:

  We present an algorithm for counting the number of cycles in an undirected graph. The given algorithm generates exact results but it is not guaranteed to run in a polynomial time. Afterwards, an approximated version from the algorithm guaranteed to run in a polynomial time was introduced. The obtained results was used to measure the entropy of graphs. Entropy represents robustness of the graph under analysis. An experiment is conducted to compare the results of our algorithm with the results of another algorithm based on the Donald Johnson backtracking algorithm.


Who was the first to show that there is a Universal Turing-Machine that uses a binary alphabet? The title says it all, I think.
We know there are universal Turing-machines that only use a binary alphabet.  But who proved this first?
Turing himself showed the existence of a universal Turing machine ... but did he also show that such a machine can exist using only a binary alphabet? Or was that someone else?
Or was it just 'obvious' to him and others that this would be the case, and hence no explicit 'first' proof or publication of this result exists?
Of course, it is obvious that you can represent any number using binary.
But, first of all, Turing-machines can compute things about things other than numbers. Indeed, all that matters is that the Universal Turing-machine is able to represent, in binary, whatever symbol set the Turing-machine to be simulated is using, and a program, again in binary, that describes the state-transitions of that machine-to-be-simulated. Of course, since all of those things are enumerable, all representations of those things can still be done in binary, that is still fairly obvious.
But what is far less obvious to me, is that you can do all the computations on those represented objects still using only two symbols. For example, you'll need some way to indicate separations between the objects, and as those objects change (e.g. when the machine-to-be-simulated changes a symbol on the tape), you'll need to change the corresponding binary representation, and since they are of variable length, you'll need to constantly shift the location of those objects on the tape that the Universal machine is working with.
Indeed, to me the tricky part is to come up with some clever way to encode any kind of Turing-machine and input tape that the Universal machine will take in at its input, and to somehow simulate the behavior of that machine, keeping track of what state that machine is in and where it is on the tape, again, all with just two symbols. Yes, we now know it can all be done, and I successfully went through this exercise myself. However, I thought it was all rather less than obvious.
Of course, I am no Turing ... and so was it obvious to Turing that it could be done? Reading his paper, I don't think Turing really proves this .. or even considers this. In his paper, for example, he still uses special symbols (i.e. not 0 or 1) to, for example, indicate the left boundary of the simulated tape.  But was it still so obvious to Turing that it didn't even deserve mentioning?
So, let me put it this way: is there a publication that can be considered the 'first' proof of the result that you can have a dully binary Universal Turing machine? I would be very interested in knowing what that is.
Thank you!

A large part of what is known goes unpublished, when it is considered trivial. What counts as trivial is, of course, different in different times and for different communities. For instance, we do not consider particularly interesting about binary numbers that they are as expressive as decimals, but that the machines that operate on binary representations are simpler.

In his famous 1936 article, Turing is satisfied with the premise that the alphabet of the machine is finite, which leads me to believe that differences beyond that are considered trivial by him, for general purposes.

He discusses the difference between machines with infinite and finite sets of symbols, and reaches the conclusion that using an infinite set of symbols would, at some point, make it impossible to concretely differentiate them from each other (which could be another way of illustrating the fact that real numbers can't be listed). He then states that the effect of this restriction is not very serious, because you can, at least to some extent, conveniently represent bigger alphabets by groups of symbols of smaller ones, considering that any effective computation can only use, in practice, what amounts to a finite number of symbols.

I suggest that you try to imagine how to simulate an $n$-symbol TM (I would start with $n=8$) on a two-symbol one. It is a good exercise.


Prove that the language L = {w1, w1w2, w1w2w3, ..} is regular, provided wi is in a regular language Let's assume that we're working over a finite alphabet $\Sigma=\{a, b\}$. How can one prove that $$L_2=\{w_1w_2...w_m| m ∈ \mathbb{N}, ∀i(w_i ∈ L)\}$$ is a regular language, provided that L is regular? By the way, L is a fixed language in the problem that I am solving, but it's regularity is trivial to prove so I have omitted it. This next step, however, I can't think of a valid way to prove. I would be glad if you guys could give me a hint.

Your language is known as $L^+$.

It is a very standard property of regular languages that if $L$ is regular then so is $L^*$; this can be proved in several ways, and you can find proofs in textbooks and online sources. Since $L^+$ is either equal to $L^*$ or obtained from it by removing $\epsilon$ (the empty string), then $L^+$ is also regular.


Intuition behind F-algebra I looked at here for getting an intuition about F-algebra, but I am still left with some questions.

Suppose I have a group signature as $\Sigma= (* : X \times X \rightarrow X, \thicksim: X \rightarrow X , e : \rightarrow X)$, with the following axioms in a unuiversal algebraic way:

$x ∗ (y ∗ z)  =  (x ∗ y) ∗ z$  (Associativity)
$e ∗ x  =  x  =  x ∗ e$   (Identity element)
$x ∗ (\thicksim x)  =  e  =  (\thicksim x) ∗ x$  (Inverse element)

A model of the above signature is an assignment of two functions to its function symbols, and a constant to its constant symbol, such that the above three laws hold.

My Question:

How the above structure with three axioms, can be encoded (represented) in an F-algebraic notion:

  1) What is my endo-Functor F and why is that?

  2) How these three laws are represented in F-algebra?

p.s.: I would appreciate if anybody refer to a textbook, or a document that I can read more examples to further understand the F-algebra concept.

Given a functor $F:Set\to Set$, an $F$-algebra is just a function $f:F(X)\to X$, where $X$ is some set known as the carrier set.

In your example, $X$ is the set of elements of some group.

The endo functor $F$ in this case is $$F(X)=X\times X+X+1.$$
Think of this as representing the three different operators.
The first component of the sum, $X\times X$, captures the arguments of $*:X\times X\to X$.
The second component, $X$, captures the arguments of $∼:X\to X$. The third component, $1$, captures the constant $e:1\to X$ – the $1$ represents a set with one element, thus the function $e$ picks out a single element of $X$.

To understand why these components are summed together, recall that there is an isomorphism $(A\to X) \times (B \to X) \equiv (A+B)\to X$ (where $+$ is disjoint union of sets).

The three functions above can be seen as an element of the set given by the product of their signatures: $$f=(*,∼,e):(X\times X \to X)\times (X\to X) \times (1\to X).$$ Using the isomorphism, we can find an equivalent function  $$f':(X\times X + X + 1)\to X,$$ which is $F(X)\to X$. Thus, an $F$-algebra.

To capture the notion of a group needs additional equations (the expected ones), which falls outside of the basic definition of an $F$-algebra, but are added in a trivial way.

Googling "Universal Algebra" will find you some online textbooks/notes. I'm not sure which ones are good.


Asymptotic estimate for $\sum_{k=1}^{N} {\frac{1}{k^2 H_k}}$ I am working on finding the asymptotic estimate for $$ \sum_{k=1}^{N} {\frac{1}{k^2 H_k}}.$$
All I know is that ${\frac{1}{k^2 H_k}}$ is convergent because $${\frac{1}{k^2 H_k}}<\frac{1}{k^2}$$ and $\frac{1}{k^2}$ is convergent.

Am I right to conclude that the asymptotic estimate for this is $O(\frac{1}{k^2})$?

Since the infinite series $\sum_{k=1}^\infty \frac{1}{k^2H_k}$ converges, an asymptotic estimate to your sum is simply $\Theta(1)$.

You can obtain a better estimate by estimating the tail:
$$
\sum_{k=1}^n \frac{1}{k^2H_k} = \sum_{k=1}^\infty \frac{1}{k^2}{H_k} - \sum_{k=n+1}^\infty \frac{1}{k^2H_k}.
$$
We can estimate the tail by
$$
\sum_{k=n+1}^\infty \frac{1}{k^2H_k} \leq
\sum_{k=n+1}^\infty \frac{1}{k(k+1)} = \frac{1}{n},
$$
and so
$$
\sum_{k=1}^n \frac{1}{k^2 H_k} = C - O\left(\frac{1}{n}\right),
$$
where $C = \sum_{k=1}^\infty 1/k^2H_k \approx 1.33275$.


What is the complexity of this subset merge algorithm? Updated Algorithm: There was a major flaw in my original presentation of the algorithm which could have impacted the results. I apologize for the same. The correction has been posted underneath.

The original algorithm posted had a major flaw in its working. I tried my best but could not get the desired accuracy in presenting the algorithm in pseudo code and/or Set Theory notation. I am thus posting python code, which has been tested and produces the desired results.

Note that my question, however, remains the same: What is the time complexity of the algorithm (assuming that powersets are already generated)?

# mps is a set of powersets; below is a sample (test case)
mps = [
        [       [], [1], [2], [1,2]     ],
        [       [], [3], [4], [3,4]     ],
        [       [], [5], [6], [5,6]     ]
      ]

# Core algorithm
# enumerate(mps) may not be required in languages like C which support indexed loops
len = mps.__len__()
for idx, ps in enumerate(mps):
    if idx > len - 2:
            break;
    mps[idx + 1] = merge(mps[idx], mps[idx+1])   # merge is defined below

# Takes two powersets and merges them
def merge (psa, psb):
    fs = []
    for a in psa:
            for b in psb:
                    fs.append(list(set(a) | set(b)))
    return fs

Output: mps[-1]   #Last item of the list

Running the above example will result in listing out the powerset of $\{1,2,3,4,5,6\}$.

EDIT:
Since your new algorithm is slightly different, I present a new complexity analysis.
I change the notation slightly of power-sets $P_a$ and $P_b$ to $P_1$ and $P_2$. Your algorithm generates a power-set $P = P(S_1 \cup S_2 \cup \cdots \cup S_n)$ where $P(S_i)=P_i$ given the power-sets $P_1, P_2, ..., P_n$.
In the body of the loop it performs the merge of two subsets $P_1$ and $P_2$.

What is the complexity of $\mathtt{merge}(P_1, P_2)$?

Define $|a|=\mathtt{len}(a)$ for a list $a$. The complexity of $\mathtt{set}(a) \mid \mathtt{set}(b)$ is $\mathcal{O}(|a|+|b|)$ according to Python Wiki for the union of two sets. The conversion $\mathtt{list}(\mathtt{set}(a) \mid \mathtt{set}(b))$ is asymptotically not worse than $\mathcal{O}(|a|+|b|)$, I guess it is either linear or sublinear depending how python implements it. Appending is constant, but since you are appending the whole list it is linear in terms of one list element as the whole list object will need to be copied in the memory, again $\mathcal{O}(|a|+|b|)$ . Thus the complexity of the loop body in a merge function is at most $\mathcal{O}(3(|a|+|b|)$ which is asymptotically equivalent to $\mathcal{O}(|a|+|b|)$.

The loop body in a merge function will be executed $|P_1||P_2|$ times. Thus the overall complexity of the merge function is $\mathcal{O}(|P_1||P_2|(|a|+|b|))$. Notice $a$, $b$ are elements of power-sets. Thus their lengths follow a binomial distribution. Therefore on average $|a|=0.5\log_2(|P_1|)$ and $|b|=0.5\log_2(|P_2|)$. This gives us

\begin{align}
\mathcal{O}(|P_1||P_2|(|a|+|b|))&=\mathcal{O}(|P_1||P_2|(0.5\log_2(|P_1|)+0.5\log_2(|P_2|))\\
&=\mathcal{O}(0.5|P_1||P_2|(\log_2(|P_1|)+\log_2(|P_2|))\\
&=\mathcal{O}(0.5|P_1||P_2|(\log_2(|P_1||P_2|))\\
&=\mathcal{O}(|P_1||P_2|(\log_2(|P_1||P_2|))
\end{align}
for the complexity of a merge algorithm for two power-sets $P_1$ and $P_2$.

Notice that the merge of $P_i$ and $P_{i+1}$ replaces $P_{i+1}$ for a power-set $\mathtt{merge}(P_{i}$,$P_{i+1})$ which is of length $2^{\log_2|P_i|+\log_2|P_{i+1}|}=|P_i||P_{i+1}|$.

After the first the first execution of the loop body in the main algorithm you will have executed $\mathcal{O}(|P_1||P_2|(\log_2(|P_1||P_2|))$ steps. $P_2$ has changed to $P_2'$ with the length $|P_1||P_2|$. After the second execution you will get another $\mathcal{O}(|P_2'||P_3|\log_2(|P_2'||P_3|))$ steps which is $\mathcal{O}(|P_1||P_2||P_3|\log_2(|P_1||P_2||P_3|))$ And then by the induction you finally get the complexity of the last step of the loop
\begin{align}
\mathcal{O}(|P_1||P_2|\cdots|P_n|\log_2(|P_1||P_2|\cdots|P_n|))&=\mathcal{O}(\Pi_{i=1}^n|P_i|\log_2(\Pi_{i=1}^n|P_i|))\\
&=\mathcal{O}(\Pi_{i=1}^n|P_i|\Sigma_{i=1}^n\log_2|P_i|).
\end{align}

The complexity of the whole program is the sum of these complexities.


Ε-R diagram with conditions , is it possible? I want to create a database and model it with an E-R diagram. This database should be about a library. An entity is the member of the library, where the member can borrow books from the library. However , the member cannot borrow more than 5 books and cannot borrow any more books , if he hasn't returned every book of which the time to return it has expired. Ιs it possible to model this condition with an E-R diagram?

This can be expressed in a one to many relationship with a 0..5 end:

LibraryPatron 1 <----> 0..5 BorrowedBook

Using relational algebra they can be expressed using check constraints as Renzo suggested.   Some ER tools may also allow you to express this as a constraint.


Find an asymptotic bound for $T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$ Given is the following recurrence relation:

$T(n)=n^2+T(\frac{n}{2})+T(\frac{n}{4})+T(\frac{n}{8})+...+T(\frac{n}{2^k})$

where $k$ is some constant and $n = 2^t$ for some $t\in \mathbb{Z}$.

I'm trying to find an asymptotic bound for $T(n)$.

My work so far:

First, I've tried to guess and prove by induction.
Then, I tried to solve using a recursion tree, but I couldn't find any obvious pattern to follow.

Assuming an appropriate base case, you can prove that $T(n) \leq \frac{3}{2} n^2$. (If this doesn't work for the base case, just increase $3/2$ to a large enough constant.)

Indeed, assuming this holds for $m < n$, we have
$$
\begin{align*}
T(n) &= n^2 + T(\tfrac{n}{2}) + T(\tfrac{n}{4}) + \cdots + T(\tfrac{n}{2^k}) \\ &\leq
n^2 + \frac{3}{2} \frac{n^2}{4} + \frac{3}{2} \frac{n^2}{4^2} + \cdots + \frac{3}{2} \frac{n^2}{4^k} \\ &=
n^2 \left(1 + \frac{3}{2} \left(\frac{1}{4} + \frac{1}{4^2} + \cdots + \cdots + \frac{1}{4^k}\right)\right) \\ &<
n^2 \left(1 + \frac{3}{2} \cdot \frac{1}{3}\right) \\ &= \frac{3}{2} n^2.
\end{align*}
$$


How to choose symbols to replace for this left-most derivation? I have a context free grammar such as the following:

$E→E+T | T$
$T→T×F | F$
$F→(E) | a$

Using the left-most derivation, the following can be derived:

$E⇒E+T⇒T+T⇒F+T⇒a+T$
   $⇒a+F⇒a+(E)⇒a+(T)$
   $⇒a+(T×F)⇒a+(F×F)$
   $⇒a+(a×F)=a+(a×a)$

I know what the left most derivation is and I know what the grammar notation means but what I am trying to understand is how should I substitute the symbols in correct order? For example:

I start with:

$E⇒E+T$

I substitute 'E' first on the left and it becomes:

$⇒T+T$

Then I need to substitute $T$ on the left and it becomes:

$⇒F+T$

Why $T×F$ wasn't chosen to replace $T$ and why $F$ in this case?

Also, in the very next step $F$ was replaced by $a$ and why it wasn't replaced by $(E)$?

The term "left-derivation" only pertains to choosing the left-most non-terminal in the sentential form.

It does not force you to choose the left-most rule; that would be silly since the rules are a set, i.e. they are unordered. Also, you couldn't derive that word at all then, now wouldn't you?

Also, keep in mind that there is no "choosing" going on. This is not a parsing algorithm; grammars only give you a declarative definition of languages. There exists a derivation that results in that word, and the one you have is an example.

Note that there are ambiguous grammars, that is grammars that have multiple left-most derivations for some words.

If you are really asking about how to find syntax trees algorithmically, take your pick; there are a lot, and then some.


Why are floats converted from different integers sometimes equal? I'm trying to understand the following algorithm:

int ubnd = Integer.MAX_VALUE
int lbnd = ubnd
while (fload)lbnd == (float)ubnd {
    lbnd = lbnd - 1
}
lbnd = lbnd + 1
print "$lbnd..$ubnd"

I don't see why for 63 iterations of the loop, we have (float)lbnd == (float)ubnd. It has something to do with the conversion of integers to floats, but I don't know what. I know that integers and floats both have 32 bits, but there must be a different way of storing them. Could someone help me out?

"float" and "int" in Java both use 32 bits. "float" can represent some numbers that "int" can't, like 0.5. Since 32 bits let you store exactly $2^{32}$ different values, it should be obvious that there must be "int" values that you cannot store in a "float".

"float" in Java, and "float" in many other language implementations, uses one bit for the sign, 8 bits for an exponent, and 23 bits plus one implicit bit for the mantissa. As numbers get bigger, the distance from one "float" to the next gets bigger. The 23 bit mantissa lets you store exactly the integers in the range $2^{23}≤x<2^{24}$, all the even integers in the range $2^{24}≤x<2^{25}$, all multiples of four in the range $2^{25}≤x<2^{26}$ etc.


Can we construct problems that can be solved in $\Theta(n^c)$ time, and tested in $O(n)$ time CS sometimes seems take for granted that $\mathcal O(\text{poly}(n))$ is "easy", while $\mathcal O\left(2^{poly(n)}\right)$ is "difficult". I am interested in research into "difficult" polynomial-time algorithms, where the best-case solution to the constructed problem runs in $\Theta(n^c)$, where $c$ can be chosen to be large; but the solution could be tested in $O(n)$ time.

Question:

  Given an integer $c$, can we construct problems that would:

  Take $\Theta\left(n^c\right)$ best-case-time to solve,
  While taking $\tilde{\mathcal O}(n)$ time, and $\tilde{\mathcal O}(n)$ space, to test a solution?

($\tilde{\mathcal O}(n)$ is soft-big-oh, meaning $O(n \log^k n)$ for some $k$)

Something I note - I might be mistaken somewhere here - is that presumably, if there is a $\mathcal O(n)$ algorithm to test the solution, then perhaps there can be a $\mathcal O(n)$ reduction to $\rm k\text{-}SAT$. If so, and, if $\rm P=NP$, and there was a polynomial-time algorithm, say ${\rm S{\small OLVE}}\left(\Phi(\mathbf x)\right) \in O({|\mathbf x|}^{\alpha})$ time, then I think this might contradict our $\Theta(n^c)$ problem, if $\alpha < c$.

The motivation would be to research the possibility of having a "one-way-function", that is linear(ithmic)-time computable, and best-case "difficult"-polynomial-time invert-able, where "difficult" means a high degree polynomial, instead of the usual exponential-time definition of "difficult"; perhaps this might be able to be used for cryptography even if $\rm P=NP$ (like "post-P-equals-NP-cryptography", similar to how there is a field of "post-quantum-cryptography").

If you believe in the exponential time hypothesis, then you can construct such an example by padding SAT. The ETH states that solving SAT on $n$ variables takes time $2^{\Omega(n)}$; let's say the time is $T(n)$. We can assume that SAT instances consist of at most $O(n^3)$ clauses, and so have length at most $\tilde{O}(n^3)$. Pad such an instance by adding $N = T(n)^{1/c}$ (where $c > 1$ need not be an integer) spaces. According to the ETH, the resulting languages requires time $\Omega(n^c)$ to solve in the worst case (the "best case" time complexity of a problem is almost always $\tilde{O}(n)$, depending on your model of computation and how devious the problem is), but witnesses can be verified in time $\tilde{O}(n)$ and $O(\log n)$ space; most of these resources are spent on checking that the input is well-formed.

The same idea would work even with much weaker hypothesis, such as P$\neq$NP; I'll leave you the details.


Finding a maximal independent set in parallel On a graph $G(V,E)$, we do the following process:

Initially, all nodes in $V$ are uncolored.
While there are uncolored nodes in $V$, each uncolored node does the following:

Selects a random real number and sends it to all its neighbours;
Compares its number to the number of its neighbours; if its own number is strictly smallest, then the neighbour paints itself red and notifies all its neighbours.
If a neighbour became red, then this node paints itself black.

For example:

Suppose the graph is a path: a-b-c-d-e.
Suppose the numbers in the first step are: 1-2-0-3-4.
Nodes a and c are painted red; nodes b and d are painted black.
In the second step, only node e remains uncolored; it is trivially minimal so it paints itself red.

MY QUESTION IS: what is the average number of steps that this process takes before all nodes are colored?

My current calculation leads me to an $O(1)$ estimate, which seems too good to be true. Here is the calculation:

Consider a node $v$ with $d$ neighbours. The probability that $v$ will be the smallest among its neighbours is $1/(d+1)$. If this happens, then $v$ and all its neighbours will be colored. So the expected number of vertices colored each step is $(d+1)/(d+1)=1$ per node. Hence the total expected number of vertices colored each step is $O(n)$, so in $O(1)$ time all nodes will be colored.

If this analysis is wrong (which is probably the case), then what is the actual number of steps?

EDIT: As noted by @JukkaSuomela, the algorithm described above is due to Metivier et al, 2011 and is explained and analyzed in these lecture notes. They prove that the run time is $O(\log n)$.

But, I am still not convinced that this analysis is tight. In all graphs I checked, it seems that the algorithm completes in $O(1)$ expected time.

My question is now: what is a worst-case graph in which this algorithm indeed requires $O(\log n)$ steps in average?

There is a minor mistake, the probability of $v$ being minimal is $1/(d+1)$. That doesn't change anything, but it is still worth pointing out.

The problem is that the events you are summing aren't disjoint. Consider two vertices that aren't adjacent but have a common neighbour. If both vertices end up being minimal amongst their neighbours, then the common neighbour gets counted as being coloured twice.

We need to examine what happens in a vertex more closely. Let's compute the probability (and thus expectation of the indicator variabele) of a single vertex getting coloured.

Assume for the sake of analysis that the graph is $d$-regular and contains no triangles or squares. We will compute the chance that a given vertex $v$ does not get coloured. There are $d+1$ possibilities: the $v$ might be the smallest amongst it neighbours, $v$ might be the second smallest, third smallest, and so on... We are not interested in the case that it is the smallest, since then it gets coloured.

If $v$ is the second smallest, there is one vertex that is smaller. The probability of this vertex being smallest amongst its neighbours is $\frac{1}{d}$ (and thus $v$ getting coloured). The probability of the remaining neighbours being smallest amongst their neighbours is 0 (since $v$ is smaller). The total probability (of $v$ not getting coloured) from this case is $\frac{1}{d+1}\cdot\frac{d-1}{d}$.

If $v$ is third smallest, there are two smaller vertices. The probability from this case is $\frac{1}{d+1}\cdot(\frac{d-1}{d})^2$.

Continuing on like this, we find that the probability that $v$ does not get coloured is $\frac{1}{d+1}\Sigma_{i=1}^d (\frac{d-1}{d})^i$. The probability of a given vertex getting coloured is thus $1-\frac{1}{d+1}\Sigma_{i=1}^d (\frac{d-1}{d})^i$. As $d\to \infty$, the probability becomes $\frac{1}{e}\approx 0.368$.

Hence the probability that a given vertex gets coloured is a constant, so the expected number of vertices that gets coloured in the first step is indeed $O(n)$.

That does not make the algorithm $O(1)$. Assuming the probability stays constant (which is not entirely justified considering nodes get coloured and no longer participate in the algorithm, the graph does not remain $d$-regular), in the $k$-th step there will be (in expectation) ${(\frac{1}{e})}^kn$ uncoloured nodes. The decay is exponential, so the algorithm takes $O(\log n)$ steps.

Perhaps somebody else will be able to offer a more precise analysis, but from my argumentation it seems likely the algorithm is $O(\log n)$.


Is the language $L=\{a^nb^mc^k | k \ge max (m,n) \}$ CF I'm trying to prove that the language $L=\{a^nb^mc^k | k ≥ max (m,n) \}$ is not CF. I consider the word $\alpha = a^pb^pc^p = uvxyz$ and i break the proof to the following cases :

1) if $vxy = a^l, b^l$ or $a^kb^l$ for some $k,l \le p$ i pump the word up, so
$a^l+s, b^l+s, s > 0 : l+s<p => \alpha \notin L$

2) if $vxy$ consists any $c$ then it can't consist any $a$s so if we pump down then $c^u, u = p - l, l > 0 => N_{c} < N_{a} => \alpha \notin L$.

But i keep thinking relying on my intuition that L is CF, because L build on the rule : if we print a then we print c, if we print b we print c, or we just print c. Looks like CF.
My question is is my proof wrong or my intuition?

Your intuitive argument is wrong. If you print a $c$ for every $a$ or $b$ you see, then the language will have $k\ge m+n$ rather than $k\ge \max\{m,n\}$.


Worst case running time to search for an element in a balanced BST with $n2^n$ elements What is the worst case running time to search for an element in a balanced binary search tree with $n 2^n$ elements?

The answer is $\Theta(n)$.

My answer:

To search an element in BST is $\log (n)$ so
$$
\begin{align*}
\log(n 2^n ) &=  \log(n) + \log(2^n) \\
            &=  \log(n) + n\log 2 & \text{(base is 2)} \\
            &=  \log(n) + n
\end{align*}
$$

  Why have they used $\Theta$ in the answer?
  And why only $n$?

You state that searching an element in a BST takes time $\log n$, but this is wrong on two counts. First, this is (roughly) the worst-case number of comparisons. Second, the running time itself isn't exactly $n$ but is roughly $C\log n$ for some constant $C$ that depends on the exact machine model (assuming that comparisons take constant time). For this reason, it is better to use $\Theta$ notation (look it up!) and state that the worst-case running time of element lookup in a BST is $\Theta(\log n)$, where $n$ is the number of elements in the BST.

In our case, the number of elements is $n2^n$, and so the running time is $\Theta(\log(n2^n)) = \Theta(\log n + n) = \Theta(n)$. Asymptotically, $n + \log n = \Theta(n)$, and so there is no need to explicitly mention $\log n$.


Shuffled Strings Dynamic Programming So I have this question:

  A shuffle of two strings X and Y is formed by interspersing the
  characters into a new string, keeping the characters of X and Y in the
  same order.
  Example would be

X = AND
Y = THE
Z = ATHNED -> A  N D
               TH E

So this would return true. I've seen solution to this using Dyanimc Programming, but I came up with just a purely iterative algorithm that runs in O(|Z|), but I'm guessing there must be something wrong with it  since all the solutions I've seen all use either memoization or DP.

Basic psuedocode for my solution (I omit some obvious base cases):

solution(X,Y,Z):
   i = j = 0
   for(k=0 to |Z|):
      if(either i or j out of bounds):
         return false
      if(Z[k] == A[i]):
         i++
      elif(Z[k] == B[j]):
         j++
      else:
         return false
   return true

Basically this just runs down string Z and marks off whichever string it came from, and when a character doesnt match either, it cant be an interleaved string.

Can someone pick this apart and tell me what's wrong and why I have to use DP?

Consider the following counter example

Let $A = aa$

Let $B  = aab$

Let $Z = aabaa$

Your code will return false while the answer is true.

This is because you are giving preference to matching $A$ before matching $B$. There is no property of the problem that says that it is optimal to match all characters to $A$ before $B$ in case the character can be in both $A$ and $B$.


Sort by typical position? Lets say, we have a lot of lists (sequences of variable length) of some limited set of elements:

[A, B, D, E, Q], [A, D], [A, C, E, F, G, H, Y, Z], [B, A, E, D, Z, Y], ...

The problem is to get the single order, based on "how typical" some position is, eg, in our case it can be (coincidence with alphabetical order is just a coincidence):

[A, B, C, D, E, F, G, H, Q, Y, Z]

But lets say [Z, Q, Y, C, B, A, D, E, F, G] is "surprising" order, far from being "typical".

The questions are:

are there any "official" CS terms for the situation (so I can do further searches)?
what are practically popular definitions / metrics for "how typical" (or "surprising") in the above description?

My idea so far is to count "average position", normalized to the max length of the list. Then the order will be by increasing normalized average positions. I feel, maybe term rank and some statistics' techniques are also applicable to this, but I am more interested in some easily (one pass) computable metrics. Any pointers?

One more idea is to calculate probability of every pair where one element is before another, and sort based on whether probability is less than 0.5 or more. But this may need a triangular matrix and a lot of computations. (For the example above, p(A before D|both occur) = 1, but p(A before B) = 0.5).

One gotcha may be that is some element is usual for the beginnings and ends, but never the middle, the average result may still be in the middle... But I guess it may be too subtle to satisfy.

For now, using very rough method:

def approx_position(position, length, master_length):
    return int(position * master_length / float(length))

seqs = ['A', 'B', 'D', 'E', 'Q'], ['A', 'D'], \
    ['A', 'C', 'E', 'F', 'G', 'H', 'Y', 'Z'], ['B', 'A', 'E', 'D', 'Z', 'Y']

master = []
for s in seqs:
    total = len(s)
    est_len = len(set(master) | set(s))
    for i, item in enumerate(s):
        if item not in master:
            new_pos = approx_position(i, total, est_len)
            master.insert(new_pos, item)

print master
# ['A', 'C', 'B', 'D', 'F', 'G', 'H', 'E', 'Y', 'Z', 'Q']
# when seqs in reversed order:
# ['B', 'C', 'A', 'F', 'E', 'G', 'H', 'D', 'Q', 'Z', 'Y']

NB. Python insert works on intervals between list elements. So 0 corresponds to the place before first element.

Not ideal, but at least almost one pass (one hidden pass in set union).

Something similar is for example discussed here:
https://stackoverflow.com/questions/4645874/merging-some-sorted-lists-with-unknown-order-sequence However, my problem is overdetermined, so the question is how to do relaxation, while the results are still near optimal (the criteria is part of the answer).

(trying to widen my horizons as it is usually hard to find a right term for something if one has never encountered that term before)

As I understand your question, your problem statement is:

  Given a set of ordered lists $\{L_1,L_2,\ldots,L_n\}$, learn the relation $r(a,b)$ for the partial order of each $L_1,L_2,\ldots,L_n$. Then use this learned relation to sort a new list.

So, in your example, the relation would be the lexicographical order. But your data set has some noise because the last list breaks the order in several places.

This seems to be a case of preferrence learning, and more specifically, object ranking.


Min-plus matrix multiplication implementation I had a look at topological sorting where they mention a possible parallel algorithm that relies on matrix multiplication, but using min-plus matrix multiplication:

  One method for doing this is to repeatedly square the adjacency matrix of the given graph, logarithmically many times, using min-plus matrix multiplication with maximization in place of minimization. The resulting matrix describes the longest path distances in the graph.

I had a look at min-plus matrix multiplication, but can't quite understand what $min$ is doing in the description of the algorithm:

  Given two $n \times n$ matrices $A = (a_{ij})$ and $B = (b_{ij})$, their distance product $C = (c_{ij}) = A \star B$ is defined as an $n \times n$ matrix such that $c_{ij} = \min_{k=1}^n \{a_{ik} + b_{kj}\}$. This is standard matrix multiplication for the semi-ring of tropical numbers in the min convention.

What is the $min$ function here? When I think of $min$, I think of it like $min(1, 2) = 1$. But how does that make sense if we are doing a sum?

So, in my implementation of regular matrix multiplication, finding the value for $c_{ij}$ looks like this:

    for j := 0; j < p; j++ {
        sum := 0

        for k := 0; k < m; k++ {
            sum += A[i][k] * B[k][j]
        }

        C[i][j] = sum
    }

But if I add a $min$ (or a $max$) function here, like so:

...
sum += min(A[i][k] * B[k][j])
...

That doesn't make sense at all.

So how would one describe an implementation of the $min$ function described in the article for min-plus matrix multiplication? It is the $min$ of what?

In the tropical semiring, the "addition" operation is the minimum, and the "multiplication" operation is addition.

If you want to adapt matrix multiplication to the tropical semiring, you literally need to replace every occurrence of $+$ with $\min$, and $*$ with $+$.

To this effect, look at the line:

  sum+= A[i][k]*B[k][j]

Let's rewrite it "properly", as:

  sum= sum+A[i][k]*B[k][j]

Then, in the tropical semiring, this becomes:

  sum= min(sum, A[i][k]+B[k][j])

And you're done.


What is the relation between NP/NP-hard problems and Recursive/R.E languages? any of them a subset of another? So i came upon this thread :

https://gateoverflow.in/57631/relation-between-np-recursive-and-recusive-enumerable

and the guy says  Every language in NP is recursive and Every language in NP is recursively enumerable.

but i dont get it, isn't NP the set of problems which we can only determine if a given answer is true  in polynomial? doesn't that mean if the answer is no we may not know?

So i'm kinda confused here and really can't put all these together

so overall my question is : can someone please tell me what is the relation between NP/NP-hard/NP-complete problems and Recursive/RE languages ?

i read about these stuff in different courses but non of them combined all of them together for a bigger picture

(also i know that Recursive languages are a subset of RE)

also based on this :
https://stackoverflow.com/questions/1857244/what-are-the-differences-between-np-np-complete-and-np-hard

NP should not be recursive because NP is set of problems which IF the answer is yes we can detect it in polynomial, but that thread doesn't say anything about what happens if its not  NP

Every problem in NP can be decided in exponential time (and so it is recursive). Recall that one of the definitions of NP goes via witnesses:

  A language $L$ is in NP if there is a polynomial $P$ and a predicate $f$ computable in polynomial time such that $x \in L$ if and only if there exists a "witness" $y$ of length at most $P(|x|)$ such that $f(x,y) = \mathrm{True}$.

(A predicate is a function which returns True or False.)

Let's suppose that $y$ is in binary.
Given an input $x$, in time $2^{P(|x|)}$ we can go over all potential witnesses $y$, and for each of them calculate $f(x,y)$. If $f(x,y) = \mathrm{True}$ for any of them, then $x$ is in $L$, and otherwise $x$ is not in $L$.


Is there a linear-time algorithm to determine if an array has duplicate entries that uses only constant extra space? Determining whether or not an array has duplicate entries has two straightforward solutions:

Build a hashset of entries, then search for elements in this hashset. This takes $\mathcal O(n)$ time and $\mathcal O(n)$ extra space.
Sort the array, then search for consecutive elements that are the same. This takes $\mathcal O(n \log n)$ time and $\mathcal O(1)$ extra space.

Is there an algorithm that can solve this problem with the best of both approaches, using only $\mathcal O(n)$ time and $\mathcal O(1)$ extra space?

Question Finding duplicate in immutable array in linear time and constant space is similar, but the solution to that question only works when the values come from the set $\{1, ..., n\}$; my values are large integers. Also unlike that question, I allow the input array to be modified and used as a workspace.

One strategy might be to attempt to turn the array into a kind of hashtable. However, this seems like it won't work because of the lack of empty space (which makes both moving objects into place hard, as well as getting $\mathcal O(1)$ queries.).

However, I suspect that this cannot actually be done, but I'm not sure how to go about proving it.

Suppose that your elements come from a domain of size $n^2$. Any algorithm using time $T$ and space $S$ corresponds to a branching program having depth $T$ and containing at most $T \cdot 2^S$ nodes. Theorem 6.13 of Time-space tradeoff lower bounds for randomized computation of
decision problems shows that
$$
T = \Omega\left(n \sqrt{\log \tfrac{n}{S + \log T}/\log\log \tfrac{n}{S + \log T}}\right).
$$
In particular, if $S$ is $O(\log n)$ (which corresponds to your $O(1)$ extra space, assuming you cannot modify the input) then $T = \Omega(n\sqrt{\log n/\log\log n})$.


Polynomial-Time Reduction I have read many resources, but I cannot understand what the polynomial-time reduction is. In everywhere, this is explained with standard-pattern sentences.

Please can anyone explain it in detailed version ?

I think your best bet is probably to get an introductory text on the theory of computation and/or take a course on the subject. I think the typical courses teach quite a lot before getting to polynomial time reduction, so you are most likely skipping over a lot prerequisite material. I'll try to give a common language understanding of what a polynomial time reduction is without too many details.

First you have to understand what a reduction is, so I would start here. To quote the linked wikipedia page:

  In computability theory and computational complexity theory, a reduction is an algorithm for transforming one problem into another problem. A reduction from one problem to another may be used to show that the second problem is at least as difficult as the first.

If you want to understand it precisely you should carefully read the definition section of the page. The situation where we are interested in reductions can be roughly described as attempting to encode problems that we know are "hard" or complete for a class as a newly defined problem that we are unsure about. This will prove that the new problem is at least as hard as the one that we know to be hard.

In the vaguest sense you can think of a polynomial time reduction as a reduction that requires $O(n^k)$ steps (for a fixed k). So we require polynomial time in order to transform any instance of the "hard" problem into an instance of the new problem. Again the wiki page gives a description of different types of polynomial time reductions.


How to prove graph isomorphism is NP? I know that Graph Isomorphism should be able to be verified in polynomial time but I don't really know how to approach the problem. Any help would be appreciated.

You haven't explained what graph isomorphism means for you, so let me assume that you mean the language of all pairs of graphs $(G_1,G_2)$ which are isomorphic.

Two graphs $G_1 = (V_1,E_1),G_2 = (V_2,E_2)$ are isomorphic if there exists a bijection $f\colon V_1 \to V_2$ such that $(x,y) \in E_1$ iff $(f(x),f(y)) \in E_2$.

You take it from here.


Why is there so little literature on partial order production? Please excuse or improve the poor title of this question.
My question is rather undirected, but I guess I am trying to find out if I might be missing a keyword for my problem.
So there is plenty of work on sorting algorithms.
Sorting is usually understood as creating a / the one correct total order given a set of elements X and their pairwise relationship x >= x' for all x in X. Or  actually >= is the total order and the task is to create a sequence or directed graph s.t. x comes after x' iff x>=x'.
Now you want to do the exact same thing, only >= does not define a total order over X, but only a partial order.
This seems like a very straightforward generalization that I can only imagine is required quite often. Still, under the term partial order production, I find only very little literature on the topic / task.
Am I missing something?
EDIT: Alternative Formulation
Given a set of elements X and a function f that returns the relationship between any two elements x,x' in X. Create a DAG with an edge x->x' if the relationship is >= and x'->x if the relationship f((x,x')) is <. Then create the transitive reduction of the DAG.

f(x,x') is either >= or <. This is normal sorting.

f(x,x') is either >=, < or ? (not comparable). This is partial order production.

I would say both are clearly ordering problems, given the relationship function f (the order) and the elements X to order.
Still you find so much on case (1) and hardly anything on case (2).

This is a very well-known problem, known as topological sorting.
Often it is difficult to find material on a subject because we don't know the proper terms to look for. That's why we have sites such as this.


Is this time complexity quasi-polynomial? I have been working in the time analysis for an algorithm and finally I got a curve that fits:

$O(2^{(\log_2(N)^{2.01})})$

N is the number of elements.

I'm right to say the above time complexity is quasi-polynomial?

Quasi-polynomial means different things to different people, but in many contexts it means a running time of the form $O(2^{O(\log^{O(1)} N)})$, to which your example conforms.


Genetic Algorithm, Neural Network, Deep Learning, Machine Learning Similarities and Applications? I am a computer engineering student and trying to get the idea behind all these Artificial Intelligence Concepts and applications. I know little theoretically about machine learning and some high level brief introduction of artificial intelligence as a whole and neural network. What i am interested in is knowing the similarities or difference between the concepts: Deep Learning, Genetic Algorithm/Programming, Artificial Neural Networks and Machine Learning. How do they relate or how they help each other? What are their particular applications?

I google a bit but could not satisfy myself with the answers i got. As a beginner i would like to know what particular part they each play in Artificial Intelligence field. What type of problem they each solve and how?

Update:

If the question is too broad, i am also expecting a broad answer.Even, if the broad answer is too much then can you please tell me any particular book perhaps that might contain overview of these topics, so that i can relate by myself and go on learning.

Here's a quick dictionary:

Machine learning is a very broad subject encompassing mainly algorithms whose goal is classifying inputs to different categories. For example, an automated post system has to be able to read letters and digits. After the characters are segmented into individual characters using techniques from computational geometry, a computerized algorithm converts the images into digits and letters. Such an algorithm is trained using classified examples, that is, many examples of each digit and letter which are shown to the algorithm.
Neural networks are a machine learning algorithm loosely based on the works of the nervous system, including the brain. They are examples of the paradigm of deep learning.
Genetic algorithms are used to solve optimization problems (i.e. find the most stable structure supporting a bridge). They are loosely based on evolutionary biology.


Longest path in a DAG: source to sink? Is the longest path in a (weighted) DAG always from a source to a sink? This seems correct to me by intuition, but I'm not 100% confident. Like, for example, if I had an array in which each index represented a node in topological order, and stored the length of the longest path with that node as its endpoint in the graph at that index, would the longest path in the graph always be stored in the last index?

First, notice that your topological sort comment isn't quite right, because other nodes can be sinks than the last node in a topological sort.

To your original question: Consider some path in a DAG that is not from a source to a sink. Can you show that this path can be made longer? (This implies that the longest path must be from a source to a sink.)

For example, if the path does not start at a source, then it has at least one incoming edge... (make sure you use the fact that the graph is a DAG).


How many different languages over the unary alphabet {a} are recognized by 2-state DFAs? I am struggling to answer the following question:

  How many different languages over the unary alphabet {a} are
  recognized by 2-state DFAs?

According to the textbook, the hint was to first calculate the number of 2-state DFAs over that alphabet and then see if any of those DFAs accept the same language.

I am able to calculate the number of 2-state DFAs over that alphabet (Because a DFA is defined as a quintuple $(Q, \Sigma, \delta, q_0, F)$, there are:

$Q$: 1 possibility (The number of states is already defined in the problem)
$\Sigma$: 1 possibility (The alphabet is already defined in the problem)
$\delta$: 4 possibilities (2 possible input states * 1 possible input character * 2 possible output states) = 4 possibilities)
$q_0$: 2 possibilities (The start state can be one of the 2 states)
$F$: 4 possibilities ($\emptyset$, $\{q_0\}$, $\{q_1\}$, $\{q_0, q_1\}$)

Total possibilities = 4 * 2 * 4 = 32. However, I am having trouble figuring out how many of the 32 DFA's accept the same language. The textbook says that there are 12 different DFAs that need to be considered due to symmetry, yielding 6 different languages—but I do not understand how the author got to that result.

There are many ways to perform this enumeration. Note first that you can count the number of cases in half by postulating that $Q = \{q_0,q_1\}$, that is, fixing which among the two states is initial; the choice doesn't matter due to symmetry. Now you are left with 16 possibilities. At this point there are many ways to cut the search space even further. Here is one of them.

Case 1: $\delta(q_0,a) = q_0$. In this case we don't care about $\delta(q_1,a)$, since $q_1$ is unreachable. This case gives the two languages $\emptyset$ and $a^*$, depending on whether $q_0$ is a final state or not.

Case 2: $\delta(q_0,a) = q_1$. Since $F = \emptyset$ and $F = \{q_0,q_1\}$ will give the languages $\emptyset$ and $a^*$, respectively, it suffices to consider $F = \{q_0\}$ and $F = \{q_1\}$. Together, there are 4 machines to consider:

$\delta(q_1,a) = q_1$, $F = \{q_0\}$: the language is $\epsilon$.
$\delta(q_1,a) = q_1$, $F = \{q_1\}$: the language is $a^+$.
$\delta(q_1,a) = q_0$, $F = \{q_0\}$: the language is $(aa)^*$.
$\delta(q_1,a) = q_0$, $F = \{q_1\}$: the language is $a(aa)^*$.

These are the six different languages produced by unary two-state DFAs.


Find the number of topological sorts in a tree Find the number of topological sorts in a tree that has nodes that hold the size of their sub-tree including itself.

I've tried thinking what would be the best for m to define it but couldn't get anything specific.

Maybe $\mbox{Number of sorts =}\prod\limits_{x\in \mbox{children}}\mbox{Number of sorts}(x)$
Meaning that starting at the root I call the the method recursively multilying each result by the previous children's result. When we reach a node with size 1 we assume that there's just 1 topological sort;

If this is correct I'd really appreciate some help with proving correctness and if not a explanation why and a clue could be nice :)

A clue then.

It seems you have to multiply with a multinomial coefficient in each step. Here the size of the subtree comes in handy.

Explanation: if children have certain topsorts, then these sequences may be shuffled in the topsort for the parent. We 'color' the positions where the various topsorts for the respective children are placed, and at each color we write one of the possible topsorts for that child.

Since the formula is used now in another problem, here it is explicitly.
Assume the tree  $t$ has $n+1$ nodes, and the subtrees $t_1, \dots, t_r$ of the children have $k_1, \dots, k_r$ nodes respectively (so $n=k_1+\dots+k_r$). Let $\operatorname{NoS}(t)$ be the number of topsorts of tree $t$. Then

$$\operatorname{NoS}(t) = {n \choose k_1, k_2, \dots, k_r}\prod_{i=1}^n \operatorname{NoS}(t_i) $$


Finding suitable NP-complete problem to reduce to my problem I've been given a set $S$ of natural numbers (non-negative integers) $s_1$, $s_2$,...,$s_n$ where $|S|=n$. My problem is to figure out if there is way to get a total sum of 0 when using all the numbers of $S$ but we get to "choose the sign" for each number: that is, for $s_i$ we get to choose if we're going to add or subtract $s_i$ from the total sum.

I've tried visualizing it using a directed cyclic graph with $n$ vertices where the only edges from $v_1$ to $v_2$ are $+/- s_1$ and the task is to traverse the whole graph, ultimately getting back to our starting node $v_1$ using a path with total weight 0.

What would be a suitable NP-complete problem to reduce into this one?

This problem is essentially just a rephrasing of the classic NP-complete problem PARTITION. If you can partition a set $S$ of natural numbers into two partitions $S_1$ and $S_2$ with equal sum, then $\sum_{s \in S_1} s + \sum_{s \in S_2} -s = 0$ and vice versa.


General number field sieve is slower then exhaustive search for 'small' numbers? In an attempt to understand the efficiency of the GNFS, I've been looking at runtimes.  The calculations seem to indicate the GNFS runs slower than exhaustive search for smallish n.  For example: suppose I want to factor the number 247 (ie 13 * 19).

To do this I can just check all the numbers (exhaustive search) below
$$ \sqrt{247} \approx 16$$ to see if they divide 247.

The General number field sieve has a runtime of
$$
\approx \exp \sqrt[3]{\frac{64}{9}} (\ln n)^{1/3} (\ln \ln n)^{2/3},
$$

So calculating the GNFS runtime...
$$
\approx \exp \sqrt[3]{\frac{64}{9}} (\ln 247)^{1/3} (\ln \ln 247)^{2/3},
$$
$$
\approx \exp \sqrt[3]{\frac{64}{9}} (5.5)^{1/3} (\ln 5.5)^{2/3},
$$
$$
\approx \exp \sqrt[3]{\frac{64}{9}} (5.5)^{1/3} (1.7)^{2/3},
$$
$$
\approx \exp (1.9 * 1.8 * 1.4),
$$
$$
\approx \exp (4.87) \approx 120
$$

This is obviously bigger than 16.  What am I missing here?

First of all, the number 120 that you got is completely meaningless. There is a scaling factor that can only be determined experimentally. Even worse, there are lower order factors which are probably very significant for such small numbers. Finally, the running time you quote is heuristic – it's just an educated guess.

You are correct that GNFS is a lot less efficient than trivial methods for small numbers. That's why you don't use it for small numbers. The better asymptotics kick in only for large enough numbers.


Solving recurrence $T(n) = T(n - 1) + n$ with substitution method How can I solve the following recurrence $T(n) = T(n - 1) + n$ with the substitution method?
I guess the solution is $\Theta(n^2)$ I try to demonstrate $O(n^2)$:
$$T(n) \leq O(n^2) \\  \leq c(n-1)^2+n \\ \leq cn^2+c-2cn+n$$
How can i continue?


how to prove a language is decidable Hopefully this is not a duplicate

How do I prove a Language L={a,b,c} is decidable or not

I read somewhere that if a turing machine accepts a language and halts on every input string then the language is decidable.

Having said that how do i design / prove that a turing machine accepts {a b c}

I am new to concepts of automata and compelexity so please don't kill me if this is too basic for a question

By definition, a language is decidable if there exists a Turing machine that accepts it, that is, halts on all inputs, and answers "Yes" on words in the language, "No" on words not in the language. Therefore one way of showing that a language is decidable is by describing a Turing machine that accepts it.

There are many offline and online resources on Turing machines. For example, here are some introductory slides on Turing machines: part 1, part 2.


For an NFA, can we always find a RAM? For an NFA, can we always find a RAM, which recognises the same language?

If RAM is a Random Access Machine (i.e., a rudimentary computer with registers, memory and assorted instructions), the answer is just "build a DFA that recognizes the same language, simulate that DFA in code". I.e., have a transition table that tells you the next state for each combination of state and input symbol; start in the start state, check if the state after consuming all input is final.
More abstractly: RAM is equivalent in computing power to a Turing machine. As regular languages are decidable, they can be decided by a (deterministic) Turing machine or a RAM.


When computing asymptotic time complexity, can a variable dominate over other? I want to express the asymptotic time complexity for the worst case scenario of sorting a list of $n$ strings, each string of length $k$ letters. Using merge-sort, sorting a list of $n$ elements requires $O(n\log n)$. Comparing two strings of length $k$ has a cost of $O(k)$. Therefore, the cost would be $O(kn\log n)$.

However, I know some restrictions about $k$ and $n$ due to the nature of the problem. In particular, I know that for any list, $0 \lt k \leq 20$, and $0 \lt n \leq 80000$. In other words, the number of words in a list might vary in a much larger range than the length of the words.

In that case, would it be correct to say that $n$ dominates over $k$ and therefore the cost could be expressed as $O(n\log n)$? Or does the fact that we are discussing asymptotic costs make those restriction meaningless (as we are describing how the algorithm is impacted by the growth of each variable, regardless of how much they can actually grow)? In general, if two variables are independent, is it possible to dismiss one of them from the asymptotic cost under certain circumstances?

First of all, if $k$ and $n$ are bounded then all complexities trivialize to $O(1)$. Hence a better assumption is something like $k = O(\log n)$. Under this assumption, you can, for example, say that $O(k + n) = O(n)$, and even $O(k + \log n) = O(\log n)$. However, you cannot say that $O(kn) = O(n)$, since it's not necessarily true! If $k = \log n$, then it's not true that $O(kn) = O(n)$. Instead, all you can say is that $O(kn) = O(n\log n)$.


Max independent set in planar graphs PTAS proof I've been searching a few hours for a proof to Max independent set in planar graphs beeing in PTAS but I couldn't find anything, I'm searching for one without any reductions and I wonder if anyone here can help me find one.

Thanks in advance.

I haven't got any paper, but looking through my favorite book regarding approximation algorithms i've got something.

It is named: The Design of Approximation Algorithms.
You find it free for download (even legal) on https://www.designofapproxalgs.com.

Take a look at page 269 (ff.) especially page 271 should be interesting for you as they describe and proof a PTAS for max independent set in planar graphs.

It might not be "front of the line" research or results but hope it helps.


Nearest Insertion Traveling Salesman Heuristic: is it faster to insert nearest nodes first? I am trying to implement the nearest insertion TSP heuristic. However, I am wondering if it matters which node I insert into the subgraph first.

For example, should I start with one node; calculate the distance between this node and the other nodes; and sort the other nodes by this distance? Then, I will insert the closest node (to the first node) first. Will this be faster than randomly choosing nodes to insert?

Inserting a random point instead of a nearest point can be faster, but then you are not following the nearest insertion heuristic anymore. The key is to realize that the point is not the runtime efficiency of the algorithm, but rather the quality of the solution obtained. Indeed, remember that we are dealing with an NP-hard problem.

The nearest neighbor heuristic should return considerably shorter tours than random insertion. In fact, we can prove that the ratio of the nearest insertion heuristic's solution to the minimum tour length is bounded by $O(\log n)$, where $n$ is the number of cities. No such guarantee exists for the random insertion that you propose, i.e., such a heuristic can return very long tours.


Interesting small SAT problems? I'm noodling around with making a hardware SAT solver on an FPGA, and I'm wondering if there are any interesting SAT problems smaller than, say, 50 variables both to stay within the limits of the FPGA board (namely the number of LEDs) and so I can brute-force if needed to get all possible solutions.  I looked into factorizing small integers, but it seems that even relatively small numbers quickly get in to the hundreds of variables.  Is there anything else I can look at besides random-SAT?

In general, you can look at hard combinatorial instances. If 50 variables is not a hard limit, try e.g., an instance arising from combinatorial block design having 105 variables described in [1]. The actual instance in DIMACS format is here provided by the authors. For the instance, the authors write in [1] that: "We issue a challenge for any solver to solve it in less than one day."

Something that will be not as hard, but still not entirely trivial is coloring Mycielski graphs. These are graphs with clique number 2, but the chromatic number can be arbitrarily large. Again, if 50 variables is really a hard limit, it seems the largest Mycielski graphs you can consider is the Grötzsch graph if you use the obvious encoding to CNF. The obvious encoding will have 33 variables if you test for 3-colorability (UNSAT), and 44 variables if you test for 4-colorability (SAT).

[1] Van Gelder, Allen, and Ivor Spence. "Zero-one designs produce small hard SAT instances." Theory and Applications of Satisfiability Testing–SAT 2010. Springer Berlin Heidelberg, 2010. 388-397.


Relation between mathematical functions and trees? I try to express datastructures in a form of mathematical functions. For example an array or a dictionary is just a function to me.
Is there a good way to model a tree in terms of functions?

A tree structure can be completely described by three functions:

a function that given a node $x$ returns the number of children of that node,
a function that given a node $x$ and index $i$ returns the $i$th child of that node, and
a function that given a node $x$ returns an associated value $v$ stored at that node.


3-SUM hardness vs lower bounds on the complexity I've recently encountered a new (for me) notion from computational complexity theory called 3-SUM hardness which is based on the conjecture that 3-SUM problem can not be solved in $O\left(n^{2-\varepsilon}\right)$ time where $n$ is the number of reals among which we should check whether three of them sum to zero. By giving reduction from 3-SUM we get that it is unlikely that our problem could be solved in subquadratic time. From the other hand we can prove the lower bounds on the complexity of solving our problem. Then what is the difference between these two notions ? Does it just mean that giving the reduction is simpler than obtaining lower bounds or in other words we have an additional assumption (which usually remains unproved for ages :-))in our pocket that helps us prove the lower bound.

The reason we need complexity assumptions like the 3SUM conjecture is that we cannot prove meaningful lower bounds in any non-trivial computational models. Our best lower bounds are in bounded depth models or in monotone models, or use techniques such as diagonalization which usually apply only to somewhat contrived problems. Whereas we have exponential lower bounds on circuit size for circuits of bounded depth and for monotone circuits, the best lower bound for SAT is linear.

Since we cannot prove meaningful lower bounds on interesting problems in unrestricted computation models, we use the paradigm of reductions: assume that a specific problem is hard, and conclude that other problems are hard. The most celebrated example is, of course, the theory of NP-hardness. It is easy to criticize this methodology: the hardness assumptions that we make are sometimes controversial. Things are particularly bad in cryptography, where sometimes the hardness assumption made in a paper is a thinly veiled version of the assumption that the construction suggested in the paper works.

3SUM hardness is not a new assumption, but has recently found new interest in the community. It explains the complexity of the best known algorithms for many different problems. As such, it is coming to be viewed as the analog of NP-hardness for problems inside P. As an added bonus, 3SUM hardness makes much more accurate predictions on the complexity of problems: rather than just stating that an NP-hard problem cannot be solved in polynomial time, 3SUM hardness allows us to determine the best exponents (smallest $\alpha$ such that the problem can be solved in time $O(n^\alpha)$) of certain problems.


Efficient way to reduce a binomial coefficient as a fraction Here is the full problem.

You need to calculate Euler's totient function of a binomial coefficient $C_n^k$.
Input
The first line contains two integers: $n$ and $k$ $(0 \le k \le n \le 500000)$.
Output
Print one number $\varphi (C_n^k)$ modulo $10^9+7$.

My thoughts:
It is known that $$\varphi(a)=a \prod_{p|a}(1-\frac{1}{p}) $$
where $p$ are prime numbers divide $a$.
Hence, if we can obtain somehow vector<int> multipliers that contains divisors of $C_n^k$ then we can easily do the following steps in order to calculate $\varphi(C_n^k)$:

Multiply all elements of that vector modulo $10^9+7$. Let's call the result by result
Then we can iterate through all prime numbers that divide any element of multipliers(these prime numbers can be obtained by a minor modification of sieve of Eratosthenes). Since $1-\frac{1}{p}=\frac{p-1}{p}$ we can update the result by:

result = divideMod(multiplyMod(result, p-1), p)

where divideMod and multiplyMod are functions doing corresponding operations modulo $10^9+7$.
And yes, we can do modulus division since $10^9+7$ is prime.
By doing all that stuff we get what we needed: $\varphi(C_n^k)$ modulo $10^9+7$. This all idea now requires just a vector multipliers. Here is my attempt to get it:
I need to write a function calculates the combinations number $C_n^k$. The function shouldn't return the total result of the operation(because it can be too large since $(0 \le k \le n \le 500000)$). It should return the vector<int> which contains divisors of that number. Let's do some math:
$$
C_n^k = \frac{n!}{(n-k)! k!} \\
=\frac{n(n-1)(n-2)...(n-k+1)}{k(k-1)(k-2)...1}
$$
So now I need to reduce this fraction. And the question is: what is the most efficient way to do this(in terms of time)?
I've tried the following. Consider the numerator and denominator are represented by vector<int> numerator={n, n-1, ..., n-k+1} and vector<int> denominator={k, k-1, ..., 1} respectively.
    vector<long> numerator(k);
    vector<long> denominator(k);
    for (int i = 0; i<k; i++) {
        numerator[i] = n-i;
        denominator[i] = k-i;
    }

    vector<long> multipliers;
    for (int i = 0; i < k; i++) {
        for (int j = 0; j < k; j++) {
            if (numerator[i] == 1)
                break;

            long greatest_common_divisor = gcd(numerator[i], denominator[j]);
            numerator[i] /= greatest_common_divisor;
            denominator[j] /= greatest_common_divisor;
        }
        if (numerator[i] != 1)
            multipliers.push_back(numerator[i]);
    }

As you can see I just go through all numbers in numerator and denominator and divide them by their greatest common divisor.
Time complexity of this algorithm is $O( k^2 log(nk) )$
It's too big and for this solution contest system returns time limit exceeded.($0 \le k \le n \le 500000$)
Does there exist more efficient way?

You store the numbers n-k+1 to n in an array.

Then for each prime number p ≤ k: Find which power of p is a factor of k! (Thats k/p + k/p^2 + k/p^3 ... ) Then remove that power from the array: Find the first number divisible by p (that would be the number at index 0 if n-k+1 is divisible by p, otherwise at index p - ((n-k+1) modulo p)). That number is divisible by p, possible by p^2 etc., and the next number divisible by p is at the index p higher).

You are now left with an array of k numbers that you need to multiply.


Most efficient algorithm to print 1-100 using a given random number generator We are given a random number generator RandNum50 which generates a random integer uniformly in the range 1–50.
We may use only this random number generator to generate and print all integers from 1 to 100 in a random order. Every number must come exactly once, and the probability of any number occurring at any place must be equal.

What is the most efficient algorithm for this?

Since other folks have given approximate solutions and solutions involving taking indeterminate numbers of deviates, how about a proof that there is no such algorithm that's guaranteed to only require a finite number of RandNum50() calls?

As others have noted, printing the numbers from 1-100 in random order is equivalent to printing a random permutation of these numbers; there are 100! of these permutations, and so any particular permutation must be output with probability $\frac{1}{100!}$.

But if we knew that our algorithm used at most $k$ calls to RandNum50 for some $k$, then we could argue as follows: firstly, pad out those computation paths that make fewer than $k$ calls to RandNum50 to make additional dummy calls (that is, calls where the returned value is irrelevant), so that all computation paths make precisely $k$ calls.  Any given sequence of $k$ results from our calls to RandNum50 must result in some output permutation, and so we can build an 'outcomes table' that maps any given sequence $(r_1, r_2, \ldots, r_k)$ of results from our calls into a particular output permutation.  Since each of these outcomes is equally likely (each of them has probability $\displaystyle\frac{1}{50^k}$), then the probability of getting any particular permutation out of our algorithm must be of the form $\displaystyle\frac{c}{50^k}$ for some $c$.  But $\displaystyle\frac{1}{100!}$ can't be of this form, because $100!$ doesn't divide $50^k$ for any $k$ (for instance, 3 divides $100!$ but can't divide any number of the form $50^k$).  This means that no possible distribution of outcomes to random-number calls can produce a uniform permutation.


Minimizing the iterative sum of pairs of numbers in a list Given the tuple (list, value):

$$\left(\left[x_1, x_2, \cdots x_n\right], y\right)$$

You may choose two adjacent values in the list to modify the tuple as:

$$\left(\left[x_1, x_2, \cdots x_{i-1}, (x_i + x_{i+1}), x_{i+2} \cdots x_n\right], y + x_{i} + x_{i+1}\right)$$

Iterate until:

$$\left(\left[\sum_i x_i\right], y + z\right)$$

What is the optimal set of choices that minimizes $z$?

Intuitively, you never want to operate on the largest number in the list.  But the largest number in this list changes as you add values together.  In other words, the optimal solution is not necessarily obtained by an optimal solution of a sub-problem.

A greedy solution would start by taking the smallest number in this list and adding it to the smaller of its adjacent numbers.  This solution, while close, is not equivalent to the value returned by brute force search.  This points to the fact the some locally optimal step is not globally optimal, which could be connected to the fact that the largest element of the list changes as values are added together.

I will assume that initially $y=0$, as this makes no difference in your problem.

Look at the very last two elements $a,b$ that you will apply your operation on:
The tuple is $([a,b], y$) and, at the next iteration, it will necessarily be $([a+b], $y+a+b$)$, since $a+b = \sum_{i=1}^n x_i$ is a constant, you only want to minimize $y$.

Notice that $a$  (resp. $b$) must have been obtained as a sum of some contiguous sequence of elements of your list starting from $x_1$ (resp. ending in $x_n$).

Calling $OPT[i,j]$ the minimum value of $y+z=z$ in your problem when the input instance consists of $([x_1, \dots, x_j], 0)$, we then obtain (for $n > 1$):

$$
OPT[1,n] = \sum_{h=1}^n x_h + min_{h=1,\dots,n-1}  \left\{ OPT[1,h] + OPT[h+1,n] \right\}
$$

and, in general:

$$
OPT[i,j] =
\begin{cases}
\sum_{h=i}^j x_h + min_{h=i,\dots,j-1}  \left\{ OPT[i,h] + OPT[h+1,j] \right\} & \mbox{if } j-i>0 \\
0 & \mbox{if } j-i = 0
\end{cases}.
$$

There are $O(n^2)$ subproblems and each requires taking a minimum over $O(n)$ elements, so your problem can be solved in $O(n^3)$ time via dynamic programming.


Find a lambda term satisfying two equations I'm just looking for the general idea on how to approach the following problem:

Find a term $\Delta=\lambda x.xUV$ such that:

$\Delta\Delta=K$
$\Delta K=S$

(it's a system of 2 equations, I didn't know how to format it properly)

Where $K=\lambda xy.x$ and $S=\lambda xyz.xz(yz)$

I think I need to use Bohm theorem but I don't know exactly how.

This is not directly a consequence of Böhm's theorem. Böhm's theorem states that for any strongly normalizing $A$ and $B$ that are not $\beta\eta$-convertible, there exists $\Gamma$ such that $\Gamma A = K$ and $\Gamma B = S$. You don't get to constrain $\Gamma = A$ or the required form $\lambda x. x U V$. There may be a way to use Böhm's theorem on a different term, but this particular system of equations can easily be solved manually.

If such a term exists then $\Delta K = K U V = U$, so to satisfy the second equation it is necessary that $U = S$.

Then $\Delta \Delta = (\lambda x. x S V) (\lambda x. x S V) = S S V V = S V (V V) = \lambda y. V y (V V y)$.
To satisfy the first equation, $V y (V V y) = K y = \lambda z. y$. One way to satisfy this is to take $V = \lambda y z z'. y$.

Finally, verify that $\Delta = \lambda x. x S (\lambda y z z'. y)$ satisfies the two equations.


Proving that a CFG generates a language Is a suitable way to prove that any given CFG generates (or not) any given language to draw its total language tree?

What if the tree is infinite? What would then be a better way to prove that a given CFG generates a given language?

Suppose that we have a context-free grammar $G$ and a set of words $S$, and we would like to prove that the language $L(G)$ generated by $G$ is precisely the set $S$. The most direct way of doing this is to prove $L(G) \subseteq S$ and $S \subseteq L(G)$, which amounts to showing:

For every $x \in L(G)$ we have $x \in S$.
For every $y \in S$ we have $y \in L(G)$.

How this is done depends on how the set $S$ is given, so there is no further, more specific advice that I can offer, except that drawing trees is not really going to result in a proof.


Does the SIFT feature be calculated in the original image or the corresponding octave(s)? Given there are 4 octaves(the 1st octave is the original image, the 2nd octave is half size of the original image, and so on.), does SIFT calculate the keypoint's orientation in the original image or the octave the keypoint extracted from?
For example, there is a keypoint found in the 3rd octave. Does SIFT calculate its orientation in the original image or in the 3rd octave (one fourth of the original image size)

Similar to 1st question, does SIFT calculate the keypoint descriptor in the original image or the octave the keypoint extracted from?

The orientation of a keypoint should be computed on the original image, smoothed accordingly to the scale of that keypoint. Luckily we already have the Gaussian pyramid at our disposal, so we can simply select the closest level of this pyramid and compute the orientation there. In other words, if you detect a keypoint in the 3rd octave, then you compute its orientation in the 3rd octave of the Gaussian pyramid.
And the same for descriptors.