Are physical laws uncomputable in any type of computation (according to this article)? It seems that this article (https://arxiv.org/pdf/1312.4456.pdf) proposes that laws of physics are uncomputable (i.e., they could not be reproduced on a computer), but I'm not sure about it.

In some part of the article it says:

  If
  we expand the set of computational devices that we use to define computational complexity,
  then the consequences of the known laws of physics can in principle be elaborated in
  polynomical [sic] time on classical and quantum computers.

  If we restrict our attention to laws whose consequences can be evaluated in polynomial
  time, then the problem of finding concise expressions of physical laws is no longer
  uncomputable.

So, what is it saying? That laws of physics are uncomputable? That laws of physics could not be reproduced in a computer? That laws of physics could not be reproduced in any type of computer?

Also, in the conclusions it says:

  This chapter reviewed how uncomputability impacts the laws of physics. Although
  uncomputability as in the halting problem arises from seemingly esoteric logical paradoxes,
  I showed that common and basic questions in physics have answers that are uncomputable.
  Many physical systems are capable of universal computation: to solve the question of
  whether such a system has discrete or continuous spectrum in a particular regime, or
  whether it is gapped or gapless, requires one to solve the halting problem. At a more
  general level one can think of the all scientific laws as providing concise, easily unpacked
  descriptions of obserbational [sic] and experimental data. The problem of finding the most
  concise description of a data set is uncomputable in general, and the problem of finding
  the most concise description whose predictions are easily evaluated is NP-complete.

So, what can we conclude from this? Also, what does it exactly mean that "finding the most concise description whose predictions are easily evaluated is NP-complete"?

The reasoning given in the paper is too vague to be of much value. The question whether laws of physics are computable cannot be decided by a philosophical discussion. It already takes some hard physics and math to even properly formulate the question.

Let me give an analogy. It is impossible to travel faster than light, right? But if I shine a laser at the moon and move it fast enough, the laser dot on the moon will move faster than light. So how is this possible? We have a contradiction in physics. Or do we?

It is easy to have a discussion about computability in the real world, or computability of the laws of physics, at the level of the previous paragraph. For instance, the very nice and seriously presented result on the Undecidability of the spectral gap is easy to misinterpret, because the devil is in the details. The actual experiment cannot be set up because it requires unrealistic conditions. If we approximate the experiment, then the theorem does not hold anymore. But this does not stop people from misinterpreting the result.

For a more reasonable account of computability of the laws of physics I recommend A computable universe, in which you can find discussions of many aspects of computability. If you are interested in computability of the laws of physics then the Matthew Szudzik's contribution The Computable Universe Hypothesis.

Personally I would say that the question "is the universe computable" is ill-formed, because this is not a falsifiable statement. The question "are the laws of physics computable" makes more sense, but one really has to be careful how it is phrased.


How to deal with cost variation in a dynamic graph when applying Dijkstra What are the methods to deal with variations in cost in a dynamic graph when applying Dijkstra? For instance, I select the shortest path in a graph, however, the weight of this path changed after I selected (I made the selection using an estimate). How do I deal with this variation?

So if I get this right, you computed Dijkstra for your whole graph (that has no negative cycles) and then you are interested in the shortest path between two specific points. You used estimates, and after choosing the shortest (estimated) path, you compute the real path length (you don't do this before for performance reasons I guess).

Now here are my thoughts on this:

The real path length will very likely vary from the one you computed using estimates. That's why it is called estimates. So you first have to decide whether you are interested in the definitely shortest path or if it is sufficient to find a most likely or approximately shortest path.
For most applications the latter case is sufficient and hence your solution works.
If not, you have some possibilities. You could ignore the decreasing performance and just compute Dijkstra with the real values. This would be the easiest solution.
The best solution that comes to my mind is:

Estimate the length of all edges
Compute Dijkstra
Find shortest path between the desired nodes
If the shortest path contains one or more estimates: Compute the distances between all nodes along the shortest path and replace the corresponding estimates with your results. Go to 2.
Break; the computed path is indeed the shortest path


Monotone boolean satisfiability with at most k 1s is NP-Complete I am to prove that monotone boolean formula satisfiability checking when at most k variables are set to 1 is an NP-Complete problem.  Proving that it is in NP is easy, but I'm having difficulty showing that it is in NP-Hard.  I have seen this, but I would rather not use its solution, as the textbook for the course I am self studying does not present Dominating Sets as an NP-Complete problem.  The NP-Complete problems presented in my book(Dasgupta, Papadimitriou, and Vazirani) are the following: 3SAT, Traveling Salesman, Longest Path, 3D-Matching, Knapsack, Independent Set (related to Dominating Set from what I understand), Vertex Cover, Clique, Integer Linear Programming, Rudrata Path, and Balanced Cut.

From my understanding of the problem, if you restrict the clauses to 2 literals each, then this directly parallels the vertex cover problem, and is thus NP-hard.  I was wondering if there was any way that I could use this fact to say that the unrestricted problem is also NP-Hard.  I intuitively feel that this should work, because the restricted version is a subset of the restricted version, so in at least some cases the problem is NP-hard.  Since you always take the worst case scenario, could you extend this to NP-hardness for the unrestricted problem?  If so, how would I word that (this is for a self study, not to be turned in), in the proper form?  Because my above explanation has a roundabout method of showing the point.

tl;dr Can you prove that something is np-hard by showing that a subproblem is np-hard?  I intuitively feel like you should, but want to confirm.

Let $L'$ be a restriction of $L$, say $L' = L \cap D$. Here $D$ is a restriction on the inputs such as "all clauses have two literals each".

Suppose that $L'$ is NP-hard. Then for every language $M$ in NP, there is a polytime reduction $\varphi$ from $M$ to $L'$ such that $x \in M$ iff $\varphi(x) \in L'$. If $\varphi(x) \in D$ for all $x$, then $\varphi(x) \in L'$ iff $\varphi(x) \in L$, and so $\varphi$ is also a reduction from $M$ to $L$.

Usually NP-hardness proofs go by reduction from some specific NP-complete problem $M$. If the polytime reduction $\varphi$ from $M$ to $L'$ showing that $L'$ is NP-hard satisfies the property $\varphi(x) \in D$ for all $x$ (in other words, its range is [contained in] $D$), then the reasoning in the preceding paragraph shows that $\varphi$ also proves that $L$ itself is NP-hard.

For example, in your case $L$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone Boolean formula that can be satisfies by setting at most $k$ of the literals to TRUE; $D$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone 2CNF; and $L' = L \cap D$ is the set of pairs $\langle \psi,k \rangle$ such that $\psi$ is a monotone 2CNF that can be satisfied by setting at most $k$ of the literals to TRUE. Any reduction $\varphi$ showing that $L'$ is NP-complete whose range is $D$ also shows that $L$ is NP-complete.

To check that you understand the argument, try to see what goes wrong when we take $L'$ to be, say, 3SAT, and $L$ to be the language of all 3CNFs.

Finally, here is a trick that you can use to emulate SAT in your setting. Suppose that some CNF $\varphi$ has variables $x_1,\ldots,x_n$, some of them possibly appearing negated. Consider $\psi = \varphi' \land (x_1 \lor y_1) \land \cdots \land (x_n \lor y_n)$, where $\varphi'$ results from replacing $\lnot x_i$ by $y_i$. Then $\varphi$ is satisfiable iff $\psi$ is satisfiable by a truth assignment in which at most (or exactly) $n$ variables are TRUE.


Use substitute algorithm to prove T(n) =4T(n/2) + n^2 compact lower bound how to use substitute algorithm to prove T(n) =4T(n/2) + n^2 compact lower bound.
this is a algorithm of my class home work,but i dont know how to solve it.

Let's assume that $n$ is a power of 2 (otherwise the recurrence isn't really defined all the way), with a base case at $n=1$. Then
$$
\begin{align*}
T(n) &= n^2 + 4T(n/2) \\ &=
n^2 + 4(n/2)^2 + 16T(n/4) \\ &=
n^2 + 4(n/2)^2 + 16(n/4)^2 + 64T(n/8) \\ &= \cdots
\end{align*}
$$
Note that $n^2 = 4(n/2)^2 = 16(n/4)^2$. If $n = 2^m$ then after $m$ steps we will reach $4^mT(n/2^m) = 4^mT(1)$, with $m$ copies of $n^2$ tagging along. Therefore
$$
T(n) = mn^2 + 4^mT(1) = n^2\log_2 n + n^2 T(1).
$$


Deciding whether a CFG is parity absent Suppose that $\Sigma = \{c_1, \dots, c_m\}$ is some finite alphabet and supposing $s \in \Sigma^*$, let $\mathcal{I}_j(s)$ denote the number of instances of character $c_j$ in $s$. Call a string $s$ odd-parity absent iff $|\{j : \mathcal{I}_j(s) = 0\}|$ is odd. That is, $s$ is odd-parity absent iff an odd number of characters from the alphabet are missing from $s$. Call a language $L \subseteq \Sigma^*$ odd-parity absent iff every string in $L$ is odd-parity absent.

Now, suppose that $G$ is a CFG. I'd like to come up with an algorithm for deciding whether or not $L(G)$ is odd-parity absent.

I thought it'd make things simpler if we first convert $G$ into an equivalent Chomsky-normal form grammar. Now, If I could determine what types of terminal strings each variable yields in the grammar (e.g., variable $A$ yields strings with a's and strings with a's and b's, etc.) then I could just inspect the right-hand sides of the start variable rules. But $A$ of course can yield a whole bunch of different variables along the way to derive a string of terminals, and each of those variables can yield a whole other bunch of different variables along the way, etc.

One option to generate the parse tree of the grammar, and check all the leaf strings if they are odd-parity absent. Even if you have recursive rules, one application of each rule is enough, because multiple occurrences of the same element does not affect the result.

However, there might be an easier way. Consider the following grammar on {a,b,c,d,e} alphabet with the following rules:

S -> A | B
A -> Abc | C
B -> cd | De
C -> aa
D -> b

Now you can assign odd-parity variables to each state. For example, a string at state S has number of missing instances = m (m=5 in this case). Let's denote it with p(S)=5.

From the first rule, p(A)=p(B)=p(S)=5. At the second rule, p(A) becomes 3, because at the first branch it eliminates 2 missing characters. Also p(C)=3, because p(A)=p(C), all other elements are missing.

At the third rule, p(B)=3 and p(D)=4. Fourth rule indicates p(C)=2 (2 a's, but the same element). Finally, p(D)=3.

Checking all ending states, p(B)=3, p(D)=3, and p(C)=2, which means the grammar has odd-parity. Verbally, there might be strings that end up with 3 elements missing, if they end up in state B or D.

In this way, you can decide if the grammar is odd-parity absent, just by looking at the grammar. The pseudo-code would be:

consumed_elements_set(S)={}
for each rule X with L as left-hand side:
    for each state R on the right hand side:
       consumed_elements_set(R)=consumed_elements_set(L)+terminals(X)
       p(R)=m-size(consumed_elements_set(R))
for each final state F:
    if p(F) is odd:
       print "not odd-parity absent!"


The order of growth analysis for simple loop What would the order of growth for this loop be:

int sum = 0;
for (int n = N; n > 0; n /= 2)
    for(int i = 0; i < n; i++)
        sum++;

The first loop seems to run for $\log N + 1$ times and the second loop runs $n$ times.

So is the correct answer $O(n \log n)$?

When the iterations of the inner loop depend on the outer loop, it's better to sum over the amount of iterations of the inner loop. There is no need to overcomplicate this and think of logarithms just because the outer loop has logarithmic behavior.

Iterations

In this example, we can see the number of iteration the inner loop performs is halved in each step of the outer loop:

$N$ iterations of the inner loop
$\frac{N}{2}$ iterations
$\frac{N}{4}$ iterations
$\dots$
$\frac{N}{2^i}$ iterations
$\dots$
1 iteration

as the outer loop iterates.

Formalizing

Factoring $N$, we get:
$$ N(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{N})$$

Knowing that:
$$\sum_{i=0}^\infty \frac{1}{2^i} = 1 + \frac{1}{2}+ \frac{1}{4}+ \frac{1}{8}+\cdots = 2$$

we can conclude that:

$$ N(1 + \frac{1}{2} + \frac{1}{4} + \frac{1}{8} + \dots + \frac{1}{N}) < 2N$$

Which is why the algorithm's complexity is bounded by $\mathcal{O}(N)$

Since the algorithm performs at least $N$ steps (assuming $N \geq 1$), it follows that the runtime behavior is also described by $\Omega(N)$, which implies that it is in $\Theta(N)$


What questions can denotational semantics answer that operational semantics can't? I am familiar with operational semantics (both small-step and big-step) for defining programming languages. I'm interested in learning denotational semantics as well, but I'm not sure if it will be worth the effort. Will I just be learning the same material from a different point of view, or are there insights I can only gain from understanding denotational semantics?

There is no real agreement what characterises denotational semantics (see also this article), except that it must be compositional. That means that if $\newcommand{\SEMB}[1]{\lbrack\!\lbrack #1 \rbrack\!\rbrack} \SEMB{\cdot}$ is the semantic function, mapping programs to their meaning, something like the following must be the case for all $n$-ary program constructors $f$ and all programs $M_1$, ..., $M_n$ (implicitly assuming well-typedness):

$$
 \SEMB{f(M_1, ..., M_n)} = trans(f) (\SEMB{M_1}, ..., \SEMB{M_n})
$$

Here $trans(f)$ is the constructor corresponding to $f$ in the semantic domain.
Compositionality is similar to the concept of homomorphism in algebra.

Operational semantics is not compositional in this sense. Historically, denotational semantics was developed partly because operational semantics wasn't compositional. Following D. Scott's breakthrough order-theoretic denotational semantics of $\lambda$-calculus, most denotational semantics used to be order-theoretic. I imagine that -- apart from pure intellectual interest -- denotational semantics was mostly invented because at the time (1960s):

It used to be difficult to reason about operational semantics.
It used to be difficult to give axiomatic semantics to non-trivial languages.

Part of the problem was that the notion of equality of programs was not as well-understood as it is now. I'd argue that both problems have been
ameliorated to a substantial degree, (1) for example by bisimilation
based techniques coming from process theory (which can be seen as a
specific form of operational semantics) or e.g Pitts work on
operational semantics and program equivalence, and (2) by the
developments of e.g. separation logic or Hoare logics derived as typed
versions of Hennessy-Milner logics via programming language embeddings
  in typed π-calculi. Note that program logics (= axiomatic semantics)
are compositional, too.

Another way of looking at denotational semantics is that there are many programming languages and they all look kind-of similar, so maybe we can find a simple, yet universal meta-language, and map all programming languages in a compositional manner to that meta-language. In the 1960s, it was thought that some typed $\lambda$-calculus is that meta-language. A picture might say more than 1000 words:

What is the advantage of this approach? Maybe it makes sense to look
  at it from an economic POV.  If we want to prove something
  interesting about a class of object program  we have two options.

Prove it directly on the object level.
Prove that the translation to the meta-level (and back) 'preserves' the
property, and then prove it for the meta-level, and then push the result back to the object level.

The combined cost of the latter is probably higher than the cost of
  the former, but the cost of proving the translation can be
  amortised over all future uses, while the cost proving the property
  for the meta-level is much smaller than that of the proof on the
  object level.

The original order-theoretic approach to denotational semantics has so far not lived up to this promise, because complicated language features such as object orientation, concurrency and distributed computation have not yet been given precise order-theoretic semantics. By "precise" I mean semantics that matches the natural operational semantics of such languages.

Is it worth learning denotational semantics? If you mean order-theoretic approaches to denotational semantics, then probably not, unless you want to
work in the theory of programming languages and need to understand older papers. Another reason for learning order-theoretic approaches to denotational semantics is the beauty of this approach.


Question related to Hilbert's 10th problem Given $n \in \mathbb{N}$ and  $p,q \in \mathbb{N}[x_1,\ldots,x_n]$  one can define the following formula in the language of formal arithmetics

$$\varphi(n,p,q) = \forall x_1 \cdots \forall x_n : \neg (p(x_1,\ldots,x_n) = q(x_1,\ldots,x_n))$$

I would like to show that there are infinitely many triples $(n,p,q)$ such that neither $\varphi(n,p,q)$ nor $\neg \varphi(n,p,q)$ is a theorem of formal arithmetic.

In showing this I can use the fact that the problem of deciding if a polynomial $r \in \mathbb{Z}[x_1,\ldots,x_n]$ has a natural zero is undecidable.

Knowing the above fact we know that there is a polynomial $r \in \mathbb{Z}[x_1,\ldots,x_n]$ such that neither $$\varphi' = \forall x_1 \cdots \forall x_n : \neg (r(x) = 0)$$ nor $\neg \varphi'$ is a theorem. (Here the quantifiers are over the naturals which I am not sure if I can use deliberately?)

Once we have such $r$ we can write it as $$r(x_1,\ldots,x_n) = p(x_1,\ldots,x_r) - q(x_1,\ldots,x_n)$$ for $p,q \in \mathbb{N}[x_1,\ldots,x_n]$ and hence $\varphi(n,p,q)$ and $\neg \varphi(n,p,q)$ are also not theorems since $\varphi$ is logically equivalent to $\varphi'$ and we have shown that this is not a theorem.

Once we have one such triple $(n,p,q)$ we have infinitely many of them since we can just take $(n,p+k,q+k)$ for $k \in \mathbb{N}.$

Since I never did such things before I am wondering if the above reasoning is correct?

As pointed by Yuval and cody there are easy solutions to get infinitely many Diophantine equations that are not provable nor refutable (let's say in PA).

However these syntactic solution result in provably equivalent sets, i.e. sets that the theory can prove they are equivalent. You can consider these as padding arguments. Another way is adding a variable which is not used at all.

You can also play with adding or removing some strings explicitly (finite variations of the set).

If you want to get Diophantine equations that are "essentially" different (e.g. the sets are not Turing equivalent) then that is more challenging and I think knowing that there is an independent Diophantine equation is not enough, you will need the fact that every r.e. set can be encoded as a Diophantine equation (or something similar).

ps: since you only care independence it is more natural to represent these formulas as Diophantine equations not their negations.


Example of two undecidable languages that cannot be mapping reduced to each other I want to find two undecidable languages $A$ and $B$ that $A$ cannot mapping (i.e. many-one) reduce to $B$, $B$ cannot reduce to $A$. One of my thought is to let $A$ be the halting problem, let $B$ be some non-Turing-recognizable language, then it is clear that $B$ cannot reduce to $A$, but I don't know which $B$ can I pick to show that $A$ cannot reduce to $B$

There is no known natural example of such a pair, and indeed there are various results in computability theory suggesting that such a pair does not exist. So to whip up an example one has to do some work.
Below, $\Phi_e$ is the $e$th oracle machine according to some standard enumeration (in older texts this is often written "$\{e\}$," which ... yeah).

The simplest approach (indeed, the easiest I know) is via mutual diagonalization: we build inductively a pair of increasing sequences of finite binary strings $$\sigma_0\prec\sigma_1\prec\sigma_2\prec ...\quad\mbox{and}\quad  \tau_0\prec\tau_1\prec\tau_2\prec ...$$ such that for each $i$ there do not exist infinite binary sequences $f,g$ extending $\sigma_i,\tau_i$ respectively such that $\Phi_i^f=g$ or $\Phi_i^g=f$.

Proving that such sequences in fact exist is a good exercise.

Taking $$a=\bigcup\sigma_i,\quad b=\bigcup\tau_i$$ we then have that $a$ and $b$ are Turing-incomparable. (Thinking about this construction a bit, we can in fact ensure that $a,b$ are Turing-reducible to the halting problem.)

A better result is that there are computably enumerable sets which are Turing incomparable (the Friedberg-Muchnik theorem). This is much harder to prove, however; it was the first example of a priority argument.
Yuval Filmus commented that a pair of "random" languages should probably work. There are multiple senses in which this is true - in particular, the set of pairs of infinite binary sequences which are Turing incomparable is both comeager and of full measure in the space of all pairs of infinite binary strings (with the usual topology and measure). The former observation is basically just the mutual diagonalization argument above, slightly tweaked; the latter is a bit harder to prove. (In general, in computability theory measure is more complicated than category.)

In fact, the proofs of the observations in the previous paragraph actually yield stronger results without significant changes: namely, we get that for every noncomputable infinite binary sequence $f$ the set of infinite binary sequences Turing-incomparable with $f$ is both comeager and of full measure in the space of all infinite binary sequences.


Supporting data structures for SAT local search WalkSAT and GSAT are well-known and simple local search algorithms for solving the Boolean satisfiability problem. The pseudocode for the GSAT algorithm is copied from the question Implementing the GSAT algorithm - How to select which literal to flip? and presented below.

procedure GSAT(A,Max_Tries,Max_Flips)
  A: is a CNF formula
  for i:=1 to Max_Tries do
    S <- instantiation of variables
    for j:=1 to Max_Iter do
      if A satisfiable by S then
        return S
      endif
      V <- the variable whose flip yield the most important raise in the number of satisfied clauses;
      S <- S with V flipped;
    endfor
  endfor
  return the best instantiation found
end GSAT

Here we flip the variable that maximizes the number of satisfied clauses. How is this done efficiently? The naive method is to flip every variable, and for each step through all clauses and calculate how many of them get satisfied. Even if a clause could be queried for satisfiability in constant time, the naive method would still run in $O(VC)$ time, where $V$ is the number of variables and $C$ the number of clauses. I'm sure we can do better, hence the question:

  Many local search algorithms flip the variable's assignment that maximizes the number of satisfied clauses. In practice, with what data structures is this operation supported efficiently?

This is something I feel like textbooks often omit. One example is even the famous Russell & Norvig book.

The needed data structure is an occur list, a list for each variable containing the clauses the variable occurs in.  These lists are built once, when the CNF is first read.   They are used in steps 3 and 5 below to avoid scanning the whole CNF formula to count satisfied clauses.

A better algorithm than flipping every variable is:

Make a list of only the variables that occur in the unsatisfied clauses.
Choose a variable $x$ from this list.
Count how many clauses that contain $x$ are satisfied.
Flip $x$.
Count how many clauses that contain $x$ are satisfied.
Unflip $x$.
Subtract the result of step 3 from step 5 and record it for $x$.
Repeat steps 2-7 for the rest of the variables found in step 1.
Flip the variable with the highest number recorded in step 7.

A reference for the data structure (often also known as an adjacency list) is for example Lynce and Marques-Silva, Efficient Data Structures for Backtracking SAT solvers, 2004.


Kleene plus in Thompson's construction Is there a direct way to represent Kleene plus(+) using  Thompson's construction algorithm?
When I studied Thompson's construction I learned how to transform concatenation, union and kleene star of regular expresions directly into a NFA.
In wikipedia(and other websites) I found the same thing I learned in college(nothing about Kleene plus):Thompson's construction
In a non-direct method we can always transform $R^+$ in $RR^*$ and then use Thompson construction.
There is a website that transform regular expressions into NFA. They claim to use Thompson-McNaughton-Yamada algorithm. Here they transform $a^+$ into:

Is this some kind of extension of Thompson's construction algorithm?

It's technically an "extension" in the sense that Ken Thompson's original paper (ACM DL subscription required) doesn't mention it. This is presumably because his regular expression compiler didn't support "+" syntax in 1968.

However, pretty much every textbook presentation of Thompson's algorithm (e.g. see Bruce Watson's 1995 review paper on FA construction) mentions it. It's likely that no one person "extended" the method in Thompson's paper, or the "extension" was done by Thompson when he decided to support "+".


What does atomicity mean in distributed systems? In a distributed system, how atomic operations are done when network connections inherently have the Two Generals problem?

Does atomicity have a different meaning in this context?

There is one primary meaning of the word "atomicity", and one additional property that some people use on occasion.

The primary meaning is that a complex operation (usually called a "transaction"), which requires multiple parties to take action, either happens or doesn't happen. It can't happen only in part.

One classic example (because this is one domain where atomicity is more important than most other considerations) is transferring money from one bank account to another bank account at a different bank. Think of the banks as communicating agents (possibly involving other agents, like an arbitrator or broker). Conceptually, one bank needs to subtract some amount from a number held somewhere, and the other bank needs to add the same amount. The important part is that either both pieces of arithmetic happen or neither happen. What is not allowed is for money to be created or destroyed.

The additional property that some people add is that all agents, or at least the initiating agent, must be able to know in a timely manner whether the transaction happened or didn't happen. Think of a file system sync operation, for example. If that operation returns and signals that it was successful, the client can assume that any data and/or metadata written to the file system before the sync operation has been committed to secondary storage.


Given 5 curves, find the maximum total you can get for each possible level Problem

Constraints

I have a collection of curves, $C$. It is a two dimensional array. The inner array contains rational numbers, where the next is greater or equal to the previous.

$$C_{k.i} = v\\
\{k \in \mathbb{Z}: 0 \le k \le 5\}\\
\{i \in \mathbb{Z}: 0 \le i \le 99\}\\
\{v \in \mathbb{N}: 0 \le v \le 1\}\\
C_{n.i} \le C_{n.j}\\
\{j \in \mathbb{Z}: i \le j \le 99\}
$$
I have $n$ levels.

$$\{n \in \mathbb{Z}: 0 \le n \le 5 * 99\}$$

Example

C = [[i / 100 for i in range(100)]] * 5
n = 20

Task

For a given $n$ split it into five non-negative integer indexes. Which are used to index each curve and sum the result to get the total, $t$.

$$
n = a + b + c + d + e\\
t = C_{1.a} + C_{2.b} + C_{3.c} + C_{4.d} + C_{5.e}$$

For each $n$ find the maximum $t$ for a given $n$. And what the values for $a$, $b$, $c$, $d$ and $e$ are.

Solution

The way I solved this was through brute force:

Build list of tuples to store the maximum, $o$.
These tuples are (total, list of products).
Find the value for all products of $a$, $b$, $c$, $d$ and $e$.
For each product find the total of the curves, $t$.

If $o_{n.0} = t$ append [(a, b, c, d, e)] to $o_{n.1}$.
Otherwise if $o_{n.0} \lt t$ set $o_{n}$ to (t, [(a, b, c, d, e)]).

Output $o$.

In Python this can be expressed as: (variable names correlate with the ones defined above)

import itertools

o = [(-1, [])] * 495
for prod in itertools.product(range(100), repeat=5):
    n = sum(prod)
    t = sum(c[i] for c, i in zip(C, prod))
    if o[n][0] == t:
        o[n][1].append(prod)
    elif o[n][0] < t:
        o[n] = (t, [prod])

This runs in $ki^k$ time, which is rather slow.

Question

I think the performance can be improved by using caching or a fancy algorithm.
Can this algorithm's performance be reduced by an order of magnitude?

Ideas

I though running through all values of $n$ adding the highest value $v$ to a running total.
And adding the running total to the output.

This would run in $O(kn)$ time.

But this doesn't work correctly as if there are any curves that start off with a small gradient then the gradient increases to overtake all the other curves. It wouldn't be selected.

I thought about finding the maximum value a curve can be at the provided level.
Then running through output and the maximum curve from $n$ backwards to see if there are any other totals that are greater than the current one.

This seems like it might work, and might run in $O(n^2)$ time, which is significantly smaller than $O(ki^k)$.

However I think it has similar problems to the above solution that I can't think of yet.

I've thought about vectorizing the curve into, $l$, straight lines. I'm not sure what this complexity is, but I'll call it $v$.
From this it is easy to compare vectors to see which have greater starting points, and then a greater coefficient.
Precomputing the intersections, $s$, also allows you to know when to switch to a different vector efficiently.

I've not fully thought this through, but it seems like it could be something like $O((lk + s)n + (lk)^2 + v)$.

It's easy to achieve $O(n^4)$ running time: iterate over all possible values of $a,b,c,d$, set $e=n-a-b-c-d$, compute $C_a+C_b+C_c+C_d+C_e$, and keep the best one found so far.

You can achieve $O(n^3)$ running time and $O(n^2)$ space with a meet-in-the-middle algorithm:

Step 1. Create an empty hash table.  For each $d,e$ such that $d+e\le n$, add an entry to a hash table keyed on $d+e$ mapping to the value $C_d+C_e$; if it already has an entry for the key $d+e$, replace the existing entry if $C_d+C_e$ is larger than whatever was previously there, otherwise do nothing.  (Save the value of $d,e$ whenever you update the entry, too.)

Step 2. For each combination $a,b,c$ such that $a+b+c \le n$, look up the key $n-a-b-c$ in the hash table.  This gives you $d,e$ that maximizes $C_d+C_e$, subject to the requirement that $d+e=n-a-b-c$, i.e., that $a+b+c+d+e=n$.  Now compute $C_a+C_b+C_c+C_d+C_e$.  Keep the best combination you ever see.

You can achieve $O(n^2)$ time and space by keeping Step 1 above and replacing Step 2 with

Step 2'.  For each combination $a,r,s$ such that $a+r+s=n$, look up the key $r$ in the hash table to find $b,c$ such that $b+c=r$ and look up the key $s$ in the hash table to find $d,e$ such that $d+e=s$.  Compute $C_a+C_b+C_c+C_d+C_e$ and keep the best combination you ever see.  You can iterate over all such combinations $a,r,s$ by iterating over $a,r$ such that $a+r \le n$, then setting $s=n-a-r$.  There are $O(n^2)$ such combinations of $a,r,s$, and this algorithm does $O(1)$ work per combination, so the total running time is $O(n^2)$.


Is the time reversal symmetry of non-deterministic computations important? A deterministic computation can only be run backward in time, if all transitions are one-to-one. This restriction is absent for non-deterministic computations. Hence it seems to me that non-deterministic computations be can run both forward and backward in time. But because the output becomes the input for the reversed computation, and the only output for a decision problem is "yes"/"no", this time reversal symmetry seems pretty useless for decision problems.

Now I wonder whether there is some class of computational problems for which this fact would translate into a corresponding useful property. Something like the fact that "P = co-P", which is a useful property of decision problems for deterministic computations.

  Is there a computational problem type for which the time reversal symmetry of non-deterministic computations turns into a useful property for certain problem classes?

The computational problem types I have in mind here are the different types of requested output like

decision problem
optimization problem
search problem
counting problem
function problem

because the different types of expected input (that come to my mind) like

offline/online problem
(non-)promise problem

seem to be closely tied to the computational problem itself, so that they are probably not helpful for general symmetry considerations.

The time reversal symmetry is already important for decision problems. It translates into reversal of the accepted language. The trick is to replace total functions by partial functions, and don't consider "yes"/"no" as output of the problem. Instead, the "yes"/"no" is derived from the existence of a path between start and end state. This is explained for finite automata in my answer to the question "Why is non-determinism useful concept?", and elaborated for more powerful machines like pushdown automata, Turing machines and probabilistic machines in my answer to the question "What is the difference between non-determinism and randomness?".

This raises the question whether deterministic context-free languages are closed under the reversal of $L$, because this is the only one of the examples where the deterministic and the non-deterministic languages are not identical.

The importance of the time reversal symmetry is not necessarily limited to the decision problem. It might be possible to also work out its consequences for the counting problem and the function problem.


Can a two-stack PDA accept language $a^nb^mc^nd^m$ which is not context-free? Can a two-stack PDA accept language $L=\{a^nb^mc^nd^m \mid n \geq m\}$, which has no context-free grammar?

I don't believe this has a context-free grammar, but please correct me if I'm wrong.

A two-stack PDA is equivalent in computing power to a Turing machine. Since a Turing machine can accept that language (stated without proof), a two-stack PDA can as well. The actual definition of such a machine is left as an exercise :)


Optimal algorithm to distinguish given black box access This is a variant of this question. Consider two probability distributions $D$ and $U$, over $n$-bit strings, where $U$ is the uniform distribution. Assume that $D$ and $U$ are far apart in total variation distance, ie,
\begin{equation}
d_{\text{TV}}(D, U) \geq \frac{2}{3}.
\end{equation}
We are not given an explicit description of $D$: we are only given black-box access, ie, we are only given a sampling device that can sample from $D$. Consider a sample $z \in \{0, 1\}^{n}$, taken from either $D$ or $U$. We want to know which one is the case and to do that, we consider polynomial-time algorithms that use the sampling device. I am looking for a single optimal deterministic algorithm that works optimally for all $D$.
Let $A$ be this optimal algorithm. For each $D$, our algorithm $A$ is optimal in the sense that
$$
\Pr_{z \sim D} [A(z) = 1] \geq \frac{3}{4}, \\
\Pr_{z \sim U} [A(z) = 0] \geq \frac{3}{4},
$$
Output $1$ is interpreted as "the sample comes from $D$, and output $0$ is interpreted as "the sample comes from $U$."
Let $A$ use the black-box sampling device a polynomial number of times (at most) and get samples $z_{1}, z_{2}, \ldots, z_{k}$ from $D$, for some polynomial $k$. My intuition is that, if this best algorithm decides that $z$ indeed came from $D$, then it must be true that $z_{i} = z$ for at least one $i \in [k]$. In other words, since we know nothing about $D$ or its support, we have to "see" $z$ at least once in the samples we collect from $D$ to ascertain that $z$ indeed came from $D$. How do I mathematically formalize this statement?
Also, does this same intuition hold if we are given a polynomial number of samples as input (taken from either $D$ or $U$) instead of just one and are also given access to a black-box sampler for $D$?

You need $\Omega(2^n)$ samples in order to accomplish your task.
Consider an algorithm that gets $m$ samples from $D$ and then another sample, either from $D$ or from $U$, and has to guess which it is. Its input thus consists of $m+1$ samples $X_1,\ldots,X_m,Y$.
We will generate the distribution $D$ at random by choosing a random set $V \subseteq \{0,1\}^n$ of size $2^{n-2}$ and letting $D$ be a uniform sample from $V$. Note that $d_{\mathrm{TV}}(D,U) = 3/4$.
Consider now the following two distributions:

Distribution $\mathcal{D}$: Choose $D$ at random as above. Generate $m+1$ samples from $D$.
Distribution $\mathcal{U}$: Choose $D$ at random as above. Generate $m$ samples from $D$ and one sample from $U$.

Let $S$ be the set of vectors appearing in the first $m$ samples. We can describe the distribution of the final sample as follows:

Distribution $\mathcal{D}$: With probability $|S|/2^{n-2}$, output a random element in $S$ (each one is output with probability $1/2^{n-2}$). Otherwise, output a random element not in $S$.
Distribution $\mathcal{U}$: Output a random element.

To see where the alternative description of $\mathcal{D}$ comes from, notice that given $S$, the conditional distribution of $V$ is a random set of size $2^{n-2}$ containing $S$. When sampling a random element from $V$, we have a probability of $|S|/2^{n-2}$ to choose one of the elements from $S$, with probability $1/2^{n-2}$ each. Otherwise, we choose an element from $V \setminus S$, which given the distribution of $V$, is just a random element not in $S$.
This shows that the TV distance between the two distributions is
$$
\mathbb{E}\left[|S|(1/2^{n-2} - 1/2^n)\right] < \frac{m}{2^{n-2}}.
$$
In particular, any algorithm whatsoever will behave almost the same in both cases unless $m = \Omega(2^n)$. Indeed, your algorithm $A$ satisfies
$$
\Pr_{\mathcal{D}}[A=1] - \Pr_{\mathcal{U}}[A=1] \geq \frac{3}{4} - \frac{1}{4} = \frac{1}{2},
$$
showing that the variation distance between $\mathcal{D}$ and $\mathcal{U}$ is at least $1/2$. This is only possible if $m/2^{n-2} \geq 1/2$, that is, if $m \geq 2^{n-3}$.


Why no DPDA can accept Palindrome? (according to this proof) This proof is from the book "Introduction to Languages and the Theory of Computation" by John C. Martin.

My question is from the pink part at the second page:

  It follows in particular that no sequence of moves can cause M to empty its stack.

and further, it talks about  $y_x$ that is my second question. I can't understand what $y_x$ is.

I'll appreciate it if someone please describe me the whole proof.

No sequence of moves may empty the stack, this is seen as follows. Since the PDA is deterministic, its computation is determined by its input. So we have to argue that the computation on $x$ will not empty the stack. If it would empty the stack, then the PDA blocks, and can no longer continue. But observe that $xx^R$ is a palindrome, so there should be an accepting computation on $xx^R$. This implies that the computation on the prefix $x$ should not block.

Your second question. For input $x$ we can look at all continuations $xy$. For each $y$ determine the stack height that is obtained. We choose an $y$ for which this is minimal and call this specific string $y_x$ (to indicate it depends on $x$).


Is there a search engine over Artificial Intelligence and Machine Learning -related sites? Sometimes it is necessary to dig into Artificial Intelligence or specifically Machine Learning problems to make a research. Common googling (in my own experience) usually doesn't help much due to a lot of irrelevant or paid material among the results. Google Scholar in contrast is limited to scientific publications only, sometimes it is too narrow.

I wonder if there is a kind of dedicated search engine over AI- and ML-related sites?

I was not able to find a mentioned search engine, but I was able to make it myself with a help of Google Custom Search. I made a custom search engine with *.edu, *.ac.uk, *.edu.au and so on sites and domain zones, 145 in a total at this moment. From my point of view that search engine gives much better result pages, than an ordinary search. Also, the search index is almost spam-free and paid content -free.

There is a feature, that allows one to inspect what sites are included in the index, to comment them and to vote for or against them (to purge unrelevant site from the index, for example). Also, everyone is welcome to suggest new sites using a special form on the site. In short, it has all very basic machinery needed to make such scoped search engine to be community driven.

Try it at http://neatserpent.com/

Give me your feedback, please.
Do you find it helpful and better than ordinary search engine?
Would you use it?

Please, spread the word, if you like it.


Why not to take the unary representation of numbers in numeric algorithms? A pseudo-polynomial time algorithm is an algorithm that has polynomial running time on input value (magnitude) but exponential running time on input size(number of bits).

For example testing whether a number $n$ is prime or not, requires a loop through numbers from 2 to $n-1$ and check if $n$ mod $i$ is zero or not. If the mod takes O(1) time, the overall time complexity will be O(n).

But if we let $x$ to be the number of required bits to write the input then $x = \log n$ (binary) so $n = 2^x$ and the running time of the problem will be O($2^x$) which is exponential.

My question is, if we consider the unary representation of input $n$, then always $x=n$ and then pseudo-polynomial time will be equal to polynomial time complexity. So why we never do this?

Furtheremore since there is a pseudo-polynomial time algorithm for knapsack, by taking $x=n$, the knapsack will be polynomial as a result P=NP

What this means is that unary knapsack is in P.  It does not mean that knapsack (with binary-encoded numbers) is in P.

Knapsack is known to be NP-complete.  If you showed that knapsack is in P, that would show that P = NP.

But you haven't shown that knapsack is in P.  You've shown that unary knapsack is in P.  However, unary knapsack is not known to be NP-complete (indeed, the standard suspicion is that it's most likely not NP-complete).  Therefore, putting unary knapsack in P does not imply that P = NP.

So which problem should we care more about, knapsack or unary knapsack?  If your motivation is based upon practical concerns, then the answer will depend on the size of the numbers you want to solve the knapsack problem for: if they're large, then you certainly care more about knapsack than unary knapsack.  If your motivation is based upon theoretical concerns, then knapsack is arguably more interesting, because it allows us to get a deeper understanding -- it allows us to make the distinction between size vs magnitude -- whereas unary knapsack prevents us from making that distinction.

To answer the follow-up question about the dynamic programming algorithm for the knapsack problem:

Yes, the same dynamic programming algorithm can be applied to both knapsacks and to the unary knapsack.  Its running time is polynomial in the magnitude of the numbers, but exponential (not polynomial) in the length of the numbers when encoded in binary.  Thus, its running time is polynomial in the length of the input when the input is encoded in unary but is not polynomial in the length of the input when the input is encoded in binary.  That's why we do consider this dynamic programming algorithm to be a polynomial-time algorithm for unary knapsack, but don't consider it to be a polynomial-time algorithm for (binary-encoded) knapsack.

Recall that we say an algorithm runs in polynomial time if its running time is at most some polynomial of the length of the input, in bits.


Big o notation for sublinear algorithm in streaming algorithm Excuse me if this is obvious.
At 1:55 of this Coursera video on streaming algorithms (see pasted image below for relevant slide), the professor mentions sublinear storage. I get the $N^{\alpha}$ but I don't get the $log^{O(1)} N$. I take it that $O(1)$ is a constant which we could set it as $k$ for example.

Does he mean that we can have $(log N)^k$ or taking $log N$ a total of $k$ times? I have read the sublinear portion of wikipedia which makes me believe it it is more like $(log N)^k$
How does this relate to $N^{\alpha}$ mentioned on the same line? Is this an alternate notation or another possible space complexity for other streaming algorithms?

A function $f$ is $\log^{O(1)}N$ if there exists a constant $k$ such that $f(n) \leq \left(\log N\right)^k$ (and not $\underbrace{\log … \log}_{k\text{ times}} N$), so you were right on this point.
The notation $N^{\alpha}$, $\alpha < 1$ is NOT another notation for $\log^{O(1)}N$ but another complexity family. If you chose $0 < \alpha < 1$ and $0 < k$, $\log ^kN$ will always be $o(N^{\alpha})$.


is this NPC Prob? Minimum count of distinct values at all matrix columns provided only in-row swap operation I am searching for an algorithm for this! Cannot find anything useful in textbook so far. Thanks in advance!

  Question: The input is a $N \times K$ matrix, where $N$ and $K$ are positive numbers( usually $N$ is a large number, $K$ is a small number). Each row of the matrix contains distinct values, but each column may contain duplicate values.
  For $i = 1, 2, \cdots, K$, let $m_i$ denote the count of distinct values at $i$-th column and define $\rho := min(m_1, m_2, \cdots, m_K)$.
  If we can swap any two numbers within each row, how to minimize $\rho$ provided you can perform any number of the given operations(swaps)?

  Can this problem be NP-complete in terms of $N$??

For example: in a $4\times3$ matrix
$$
\begin{matrix}
1&2 & 3\\
3&4& 5\\
4&5& 7\\
6&7& 8\\
\end{matrix}
$$
Since only swaps within a row are allowed, we can swap 1 and 2 in the first row,
but cannot swap 1 in the first row with 4 in the second row.
I think after performing a few swaps, one optimal solution we can get is
$$
\begin{matrix}
1&2 & 3\\
4&5& 3\\
4&5& 7\\
6&8& 7\\
\end{matrix}
$$
where $m_1 = 3, m_2=3, m_3 = 2$,
Hence the minimum count of distinct values of all columns is $\rho = 2$.

The first thing we have to do is define a decision version of your problem, like for example:

Is it possible to swap the elements inside the rows of the matrix so that in at least one column the number of distinct elements is less or equal than $\rho$?

Well, the first thing to take into account is that this problem is just asking if we can swap elements inside the rows in order to find a column where the number of distinct elements is less or equal than $\rho$.

We are going to reduce the decision version of 3HITTING SET to the decision version of your problem. 3HITTING SET is an np-complete variant of minimum hitting set where all subsets have only three elements. Hitting set is like the inverse of set cover. In minimum set cover you cover members of the universe with subsets and in miminum hitting set you cover subsets with members of the universe. That means that if an element appears in a subset, that subset is covered by the element. The objective is to find the minimum number of elements inside the universe that are enough to cover all subsets.

A decision version of 3HITTING SET will be:

Is it possible to cover all subsets with at most $\rho$ elements of the universe?

Now with the reduction:

We simply convert each subset of the hitting set problem into a row of your problem. That is we create a matrix $A$ .Then, for each subset $i$ that belongs to the hitting set instance, we create a row $i$ inside the matrix $A$. And then for each element $j$ that belongs to the universe in the hitting set instance being reduced, we create a number inside the matrix, this number will be inside row $A_i$ if the element $j$ that belong to the universe appears inside the subset $i$ in the hitting set instance.

If there is a hitting set of size $\rho$, then we will have a matrix where we can form a column by swapping with at most $\rho$ distinct elements.

The reason for this is that if we can cover the sets of the hitting set instance with $\rho$ elements then we can form a column with $\rho$ or less distinct elements inside the matrix by picking the numbers that were mapped to elements of the universe in the hitting set instance and swapping them inside the rows of the matrix so that they are all in the same column.

For the other direction, that is, for the cases in which there is no minimum hitting set instance with at most $\rho$ distinct elements we have to show that those cases are converted in our reduction into matrices where we can´t form a column with at most $\rho$ elements by swapping numbers inside rows.

If on those instances we could, by swapping numbers inside rows, create a column with at most  $\rho$ elements inside the matrix; that would mean that there exists $\rho$ elements that can cover the subsets in the hitting set instance. This is a contradiction

The reason is that we have mapped every element of the universe in the hitting set instance to a different number inside the matrix and also we have mapped every subset into a different row inside the matrix. So if we could form a column with at most $\rho$ distinct elements by swapping elements inside the rows, that will mean that there is at least one of those numbers inside each row. Because each subset of the hitting set instance was mapped to a different row and each element of the universe is mapped to a different number inside the matrix, that will mean that we can cover the subsets with those $\rho$ elements in the hitting set instance.


Ford Fulkerson maximum flow for all vertices Suppose we have a graph $G(E,V)$ with a source node $s$. Now for any $t\in V \setminus s$ I can find the maximum flow from $s$ to all possible $t$ by using the Ford Fulkerson algorithm $|V|-1$ times, once for each $t$. I feel like there must be a faster way to compute all $|V|-1$ max flows that makes use of dynamic programming techniques. Any ideas?

"J. Hao and J. B. Orlin. A faster algorithm for finding the minimum cut in a directed graph." provides an algorithm to compute the min cut for a fixed s on the source side with time-complexity $O(nm \log(n^2/m))$, by reducing the complexity of multiple s-t cuts for varying sinks to the complexity of a single call to the Push-Relabel max-flow algorithm.

This might be adaptable to a version where you can store all the intermediate min-cut values (=max-flow values) for all sinks along the way.


Can 3-coloring be reduced to 3-clique? I'm a slight disagreement with my professor over whether or not a certain reduction is possible. He asked us to reduce the problem of 3-Coloring to the problem of 3-Clique. The problem is that I'm fairly confident that 3-Coloring is NP-Complete, while 3-Clique is P. Correct me if I'm wrong (which is very likely), but for any k-clique where the k is fixed, is $V^k$, meaning the 3-clique is $V^3$, right? I asked my professor about this and his response was:

"3-clique is definitely not in P.  You (apparently) have to examine all thrices of vertices to settle the matter."

And I still don't understand how this is not a $V^3$ operation.

If I figured out a way to reduce 3-coloring to 3-clique wouldn't I be millionaire?

You are correct.

3-clique can be solved in $O(n^3)$ time, whereas 3-coloring is NP-hard.

So there can be no "poly-time reduction" from 3-coloring to 3-clique, unless $P=NP$.


Pumping Lemma for $L=\{a^{2k} b^n b^k \mid k\ge0, n\ge0\}$ $L=\{a^{2k}b^nb^k\mid k\geq0, n\geq0\}$ over alphabet $\{a,b\}$

How do I prove that $L$ is not regular using Pumping Lemma? All the examples I've come across had same exponents all around, and I'm a bit confused how should I write this down.

Should I start with $w=\{a^pb^pb^p\mid p\leq k, p\leq n\}$ where $w$ is a subset of $L$, or how should this be tackled?

Choose for example the word $x=a^{2k}b^{k}\in L$ ( with $|x|=3k\ge k$)
Possible partitions of $x=uvw$ are $u=a^l,\;v=a^s,\;w=a^mb^{k}$ with $s\ge 1,\; l+s\le k$ and $l+s+m=2k$
Now lets look at $uv^2w=a^{2k+s}b^k$ which is clearly not in $L$. If $s$ is odd, than the number of $a$'s is odd and therefore $uv^2w\notin L$. If otherwise $s$ is even, then the number of $b$'s would have to be larger than $(2k+s)/2$, which it is not ($k<(2k+s)/2)$. Therefore $uv^2w\notin L$ holds for each $s\ge 1$.

$\rightarrow$ $L$ is not regular.


Dependent type system with different computation model There exist various Turing-equivalent models of computation, such as lambda calculus, Turing machines, or register machines.

It seems that dependent type systems (like Coq, Agda, Idris, homotopy type theory) all have a lambda-calculus-based model of computation at their core. That's because they use term substitution ($\beta$-reduction) to relate the typing model to the computation model.

Can we swap out the lambda calculus at the core of dependent type systems for other computation models?

Or more generally, can we formulate a type system that lets us plug in our own computation model and its inference rules, subject to some set of consistency rules?

Yes, realizability theory allows you to model dependent type theory based on a variety of computational models, such as: Turing machines (with or without oracles), various $\lambda$-calculi, topological models of computation, sequential functionals, game-semantics computational models, and many others.

References:

Jaap van Oosten: Realizability: an introduction to its categorical side, Studies in Logic and the Foundations of Mathematics, vol. 152, Elsevier, 2008
You could also peek in Section 1.1. of my PhD thesis.


Using closure properties, prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular I'm trying to prove that $L=\{a^kb^ra^m|k,r,m\ge0 \text{ and } m=k+r\}$ is not regular and, although it's trivial to prove it via pumping lemma, I'm having troubles trying to find a way to prove it via closure properties (for example a union of $L$ and another regular language which may give a non-regular language).
It simply doesn't occur to me any language to use alongside $L$ (I guess I lack some imagination...)

Consider the intersection of your language $L$ with the regular language $L' = \{b^r a^m \mid r,m \ge 0 \}$.
Then $L \cap L'$ contains all the words of the form $a^k b^r a^m$ where $k=0$ and $m=k+r=r$. That is, $L \cap L' = \{ b^r a^r \mid r \ge 0  \}$, which is a well-known non-regular language.


Construct a context-free grammar for a given set of words I have seen a few years back a nice and simple algorithm that, given a (finite) set of words in some alphabet, builds a context-free grammar for a language including these words and in some sense "natural" (e.g., the grammar doesn't produce all words in the alphabet). The algorithm is very simple,  it has something like 3--4 rules for grammar transformation attempted on each new word. Any help in finding it would be appreciated.

I think you might be referring to Sequitur.

Edit It has been suggested by other commenters that I leave more information for posterity. Fair point.

Sequitur is an algorithm by Craig Neville-Manning and Ian Witten (of Managing Gigabytes fame). It's linear time in the size of the input sequences (although so is the memory usage), and satisfies the twin properties of parsimony (no redundant rules are derived) and utility (every rule is useful).

However, it can't (IIRC) discover arbitrary nesting structure. So a prototypical expression grammar, where an expression can contain an expression, is too much for it. But it will discover word boundaries in English text, and repeat regions in DNA. It's also useful for finding dictionaries for data compression (which is one of Witten's major research interests).


Where can I find CS problem set resources? I am trying to learn to program and I don't just want to learn syntax, but rather learn and practice breaking up and solving problems. Now, I want to know where can I go to get hold of material that ranges in programming problems from beginner to intermediate and hopefully even further so that I can train my problem-solving skills. Any tips or advice on how to train problem-solving skills would be highly appreciated too.

i don't know how far along you are in your learning but I found that actually coding is the best way.
try Scratch. it is a graphical interface for code that jigsaws together only in ways that are syntactically correct so, as you have asked, you can learn to structure code and create anything you like without learning an actual language. it makes understanding simple coding very easy. Enjoy


Finite Language Closure Properties Let L={F| F is a finite language over Σ}
which of the following operation is not closed for L?

a. intersection

b. union

c. complement

d. none of the above

I thought the ans as d as all finite languages are regular and since regular languages are closed under all hence d seemed apt to me. But ans given is C
which is correct C or D? and Why?

There are infinitely many strings over any alphabet, so if you pick any finite language, there are infinitely many strings not in it. In other words, there are infinitely many strings in the complement of any finite language.


Easy-to-describe example of uncomputable function After teaching my philosophy of cognitive science undegraduates what a Turing machine is, I mentioned that there are functions that can't be computed using a Turing machine.  A curious philosophy major asked for an example of such a function.  Most of the students in the class are not CS students and need not be mathematically adept, so I am limited as to what I can say, except to those students who want to hear more outside of class.

The only example of a particular function that is uncomputable that I could come up with off the top of my head was the halting problem, but that would have required a substantial digression, and it would seem quite obscure to most of the students if I walked them through it.  It would also not be sufficiently useful to explain to the class why there must be uncountably many functions that are not Turing-computable.  (First step: teach the countable/uncountable distinction.)

Is there an example of an uncomputable function that's relatively easy to describe and understand--more so than the halting problem?

A classic example of an uncomputable function is The Busy Beaver Problem: For each N, consider all N-state Turing Machines over the alphabet { [blank], 1 }; over all of those machines which always halt when started on a blank tape, find one which leaves the maximum possible number of 1's on the tape once it has halted; then f(N) is that number of 1's.


Which part of Go(lang) is in Crystal(lang)? Reading Crystal Programming Language They says it is inspired from many programming language and Go.

I would like too know which part of Golang, since it is not its syntax.

I simply asked @asterite, one of the developers of Crystal, at IRC #crystal-lang (the log is here).

He said the answer is CSP, the concurrency model. For example, both Go and Crystal use channels for communications.


What is the bitwise xor of an interval? Let $\oplus$ be bitwise xor. Let $k,a,b$ be non-negative integers. $[a..b]=\{x\mid a\leq x, x\leq b\}$, it is called a integer interval.

What is a fast algorithm to find
$\{ k\oplus x\mid x\in [a..b]\}$ as a union of set of integer intervals.

One can prove that $[a+k..b-k]\subseteq \{ k\oplus x\mid x\in [a..b]\}$ by showing that $x-y\leq x\oplus y \leq x+y$.

Edit: I should specify the actually input and output to remove ambiguity.

Input: $k, a, b$.

Output: $a_1, b_1, a_2, b_2,\ldots,a_m,b_m$. Such that:

$$
\{ k\oplus x\mid x\in [a..b]\} = \bigcup_{i=1}^m [a_i..b_i]
$$

Here's an efficient solution based on BDDs

Find $n$ such that $k,a,b < 2^n$. Create $n$ boolean variables, one for each position in an $n-bit$ number
Write out a boolean formula representing every number in that interval. For example, if $n=4$ (so that we are only considering possible inputs in $[0..15]$), then the interval $[2..4]$ can be written as $\neg x_0 \wedge ((x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (\neg x_1 \wedge x_2))$ --  there is a $0$ in the $8$'s position, and either the next three bits read $100$, or the next two bits read $01$. Note that this is equivalent to partitioning the interval into subintervals aligned with powers of $2$.
Represent the boolean formula as a BDD
Similarly, write $[k..k]$ as a boolean formula. Use standard BDD algorithms to XOR the two BDDs.
Read the intervals out of the BDD. For example, if $n=5$, and we take the path in the BDD corresponding to setting $x_0=1,x_1=0,x_2=1$, and find that we have reached a true leaf (i.e.: a five-digit binary number that starts with 101 is in the set no matter what its lower two digits are), then the interval $[20..23]$ is in the set.

Depending on the application, you might want to leave the set as a BDD rather than reading it out back into intervals, as the BDD representation may be much more compact.

There is also a more elementary and direct solution. Note that XOR'ing by $k$ is equivalent to sequentially XOR'ing by each bit of $k$. Break $k$ into bits, and break $[a..b]$ into subintervals aligned with powers of two, and see what happens to each subinterval. You can work this out, and implement it efficiently using segtrees, but I expect that it will be equivalent to the BDD solution, which is faster and allows for the use of standard libraries.

Analysis

Analyzing BDDs is slightly tricky, but I'll have a go.

$[a..b]$ can be represented using at most $2\lceil\log(b-a)\rceil$ power-of-2-aligned subintervals. I'm not sure how to properly show it, but visualizing the resulting BDD, we see it will have a sort of "triskelion" structure, with size $O(\log(b-a))$.

Let $n=\max(a,b,k)$. XORing each subinterval by $k$ will preserve the subinterval, but may move it. Since each subinterval takes $O(\log n)$ space to represent  and there are $O(\log n)$ of them, this lets us bound the size of the resulting BDD as $O((\log n)^2)$. I believe this gives us a $O((\log n)^2)$ bound on the entire operation, but don't quote me on that -- the runtime is proportional to the size of the intermediate BDDs, and I'll have a bit more thinking to do to determine what happens there.


Which priority queue implementations are stable? I can't answer this question. It seems simple but I really don't know how to approach it.
Here it is:

A priority queue is said to be stable if deletions of items with equal priority value occur in the order in which they were inserted. Which of the following priority queue structures are stable:

linked lists ordered in increasing priority (key)
balanced search trees (e.g., 2-3 trees)
heaps
leftist heaps

Explain why, or give counter-examples.

I don't need a full solution just a way to approach this problem. I would prefer to solve it on my own.

Here's how I would suggest that you approach the problem.  Try running each data structure by hand on some small examples.  Then, based on those examples, see if you can form any conjecture about which data structures are stable and which ones aren't. For the ones you suspect are stable, try proving it.  For the ones that you suspect are not stable, try to come up with a counterexample to demonstrate that they're not stable.


Don’t understanding argument on words of a certain form In my book they use the following argument which I don’t understand :

  Let $L$ be a langage such that there is $m_1, ..., m_k \in \Sigma^*$ such that $ L \subset m_1^*...m_k^*$. Now choose the minimum $n$ such that there exists $l_1,..., l_n$ such that every word of $L$ is a prefix of a word in $l_1^*...l_n^*$.
  Hence by the minimality of $n$ there exist a word $u \in L$ such that $u$ is not a prefix of a word in $l_1^*...l_{n-1}^*$.

What I don’t understand is why such an $u$ exist. I don’t see why the minimality of $n$ prove the existence of such an $u$...
For example if I take $L = ab^*c^*d$ then I think the minimal $n$ is $4$ with the words $l_1 = a, l_2 = b, l_3 = c, l_4 = d$ and in this case such an $u$ clearly does not exist.

So is my book wrong or I am completely missing something here ?

Thank you !

I think the book is right.  In your example, the word $u=abcd$ satisfies the conditions: it is not a prefix of a word in $a^* b^* c^*$.

In general, I think that proof is valid.  I'll try to explain why the minimality of $n$ proves the existence of such a word $u \in L$. If there did not exist such a word $u \in L$, then that would mean that every word $u \in L$ is a prefix of $l_1^* \cdots l_{n-1}^*$, which in turn would mean that $n$ wasn't the minimum possible (we could have used $n-1$), which contradicts how $n$ was chosen in the second sentence.  That's a contradiction.  If you start from an assumption and derive a contradiction, then you can conclude that the assumption must have been wrong.  In particular, the only alternative that remains possible is that there does exist such a word $u \in L$.

Put another way, there are only two possibilities: either there does exist such a word $u \in L$, or there doesn't.  I've shown why the second choice is always impossible.  That means the first choice must actually always be true.


Do data structures help to reduce complexity of operations, at the cost of something else? I often heard that using data structures help to reduce (time or space) complexity of some operations.

I wonder if that is achieved at the cost of something else?
When solving a problem, is something still conserved, over all
choices of data structures and algorithms, just like the
conservation of energy? Such as some kind of overall (time or space)
complexity of an algorithms and a data structure being used?

To represent a collection of integers, you can use an array with one word of memory per element. For instance, say $A = [0,1,7,10]$. Alternatively, you could use an array $B$ to represent the same collection in the obvious way: $B = [1,1,0,0,0,0,0,1,0,0,1]$. Searching for element $x$ in $A$ takes $\Theta(n)$ time (or perhaps just logarithmic time if $A$ is indeed sorted), but you can do the same in $B$ in $O(1)$ time by just looking at $B[x]$, i.e. just indexing $B$ at position $x$. This is a tradeoff: by using more memory for $B$, you get faster lookups. Time-memory tradeoffs like this are often encountered.

Sometimes, one can show that to solve a problem, you must always no matter what spend some time, memory, or other resource to solve it. In such results, one must always specify the model of computation used. For instance, there is a well-known decision tree lower bound of $\Omega(n \log n)$ for sorting. So in this model, you absolutely can't beat this bound no matter what you do.


Diophantine equations and P=NP It was proven that the problem of determining whether a given Diophantine equation has a solution is undecidable (and therefore has no polynomial time algorithm). But we can check proof certificates (that is, solutions to the equation) in linear time by plugging in our solution and evaluating. So the problem is in NP. Why does this not imply P $\neq$ NP?

Every problem in NP is decidable. Since determining whether Diophantine equations have solutions is undecidable, it cannot be in NP.  Therefore, although the solution to the equation is a certificate, the size of this certificate is not bounded by any polynomial in the size of the input.


Context Free Grammar for language The language is $L = \{a^{i} b^{j} c^{k} \;|\; k \neq 2j\}$. I'm trying to write a grammar for this language, what I have so far is:

$S \rightarrow AT_{1} \;|\; AT_{2} \;|\; AT_{3} \;|\; AB \;|\; AC$

$A \rightarrow aA \;|\; \varepsilon$

$B \rightarrow bB \;|\; \varepsilon$

$C \rightarrow cC \;|\; \varepsilon$

$T_{1} \rightarrow bbB'T_{1}c \;|\; \varepsilon $   (for $2j > k$)(1)

$B' \rightarrow bB' \;|\; b$

$T_{2} \rightarrow bT_{2}ccC'\;|\; \varepsilon$ (for $2j < k$)

$C' \rightarrow cC' \;|\; c$

$T_{3} \rightarrow bT_{3}c \;|\; \varepsilon$ (for $j = k$)

the problem that I am having is, the string $bbccc$  can't be generated although valid, in that case $j = 2$ and $k = 3$  so $2\times 2 > 3$  corresponding to production rule (1), how can I fix this?

Production for $\{b^jc^k\; |\; j\neq 2k \}$ can be written as

$B\rightarrow bBcc\;|\;bB_1\;|\;cB_2$

$B_1\rightarrow bB_1\;|\;b\;|\;c\;|\;\epsilon$

$B_2\rightarrow cB_2\;|\;c\;|\;\epsilon$

You can see that it can't accept $bbcccc$. We can use $B\rightarrow bBcc$ twice but the final $B$ would have to be substituted with either b or c.

It accepts $bbccc$ as $B\rightarrow (bBcc) \rightarrow b(bB_1)cc \rightarrow bb(c)cc$

For even number of cs $B\rightarrow bBcc$ can be used. For odd number of cs, an extra $B_1\rightarrow c$ can be used.

So $\{a^ib^jc^k\; |\; j\neq 2k \}$ has the following grammar

$S\rightarrow AB$

$A\rightarrow aA \;|\; \epsilon$

$B\rightarrow bBcc\;|\;bB_1\;|\;cB_2$

$B_1\rightarrow bB_1\;|\;b\;|\;c\;|\;\epsilon$

$B_2\rightarrow cB_2\;|\;c\;|\;\epsilon$

Note: i can be 0 but j and k can not be 0 simultaneously.


Potential General Model of Computation with Physics? I posted a question about a month back regarding the significance of Turing machines (relative to other models of computation). In that post, I mentioned vaguely some conversion between an input string and a physical system as a model of computation. (I just got my BS in CS, so it's likely I have no idea what I'm talking about.)

Would the following be a valid, or at least meaningful, general model of computation:

Let $ f: Z \mapsto Z$ be a function. Then, $f$ is computable iff for all integers $a$, there exists a bijection $P$ from the integers to formal physical systems (Classical mechanics?), such that when $P(a)$ is "set into motion", it reaches and equilibrium or static state $s$ where $P^{-1}(s) = f(a)$.

If this makes sense, please let me know.

It would be meaningful, if you properly defined "formal physical system", "set in motion", and so on, in a mathematical way. Pretty much anything can be made meaningful in mathematics (which is what this sort of theoretical computer science really is).

The question is, is it useful?

It would seem that the functions computable by Turing machines are a subset of this new class, since you can make a Turing-complete physical computer with enough rolling marbles. (Or, if you allow transistors in your "formal physical systems", I could just use "my laptop at the moment when I run this Python code" as the system.)

Then, are there things your physical systems can do that Turing machines can't? Given that a Turing machine can simulate classical mechanics to arbitrary precision, given enough time and memory, I'm inclined to say no.

Finally, are your physical systems easier to work with mathematically? The answer seems like a pretty solid "no", given how much calculus is involved in classical mechanics, compared to the simple state-machine-plus-memory of a Turing machine.

So while you could in theory use physical systems to define computability, there doesn't seem to be an advantage to doing it this way.


In which direction should I carry out a reduction when proving decidability/recognizability? Definition:

  $\text{A fuction}\ f: \Sigma^* \to \Sigma^*\ \text{is a reduction from
Language A to language B if}\ w\in A \iff f(w) \in B\ \text{for every}\ w \in \Sigma^*$.

My question is which direction should I take in order to reduce a problem to another the other?

From what I've been reading I concluded we can prove that $A \leq_m B$ is we can use the TM of $B$ in order define the operation of the TM of $A$.

Let suppose I want to show that any co-recognizable language $L_k$ reduces to $\overline{HALT} = \{(\langle M \rangle, w): M(w)\ \text{doesn't halt}\}$, that is $L_k \leq_m \overline{HALT}$.

Then if $T$ is the machine working on $w \in L_k$ then I think we can make it work in this way

T on input w
  Run M on w;
     If M(w) = Halt
        Then Halt;
     Else
        Loop;

So if $w \notin \overline{HALT}$, then $M(w)$ halts and $T(w)$ halts $\implies w\notin L_k$.

If $w \in \overline{HALT}$, then $M(w)$ doesn't halt and $T(w)$ doesn't halt $\implies w\in L_k$.

Now suppose I want to prove that any co-recognizable language $L_k$ reduces to $L_{all} = \{\langle N \rangle: N\ \text{halts on every input}\}$.

My idea was to show that $\overline{HALT} \leq_m L_{all}$ and then by transitivity follows that $L_k \leq_m L_{all}$.

So I have to ''use'' the machine $R$ operating on $L_{all}$ to define a machine $P$ operating on $\overline{HALT}$.

Bu then I found this post Is the language of Turing Machines that halt on every input recognizable? which confused me a bit. There is shown that, indeed, $\overline{HALT} \leq_m L_{all}$ $(\overline{H} \leq_m AH$ in the notation of the cited post), but using the machine operating on $\overline{HALT}$ (with its corresponding input) to define the machine operating on $L_{all}$. To my eyes, it looks like the other way around.

So I'm lost.

One thing that gives peace to my soul is that all $m$-complete language are isomorphic. So probably I could shield myself behind this, assume that $L_{all}$ is $m$-complete in the class of co-recognizable language just as $\overline{HALT}$, and show what was shown in the post above. I mean, loosely speaking, assume the direction of reduction doesn't matter.

But if I don't want make this assuptiom (that $L_{all}$ is m-complete and therefore isomorphic) and just show that $\overline{HALT} \leq_m L_{all}$. Is valid to go from $(\langle P\rangle, w) \to R$

When we reduce a language A to a language B, we take an instance $x$ of A and transform it into an instance $f(x)$ of B so that $x \in A$ iff $f(x) \in B$. The way to remember that this is the correct direction is that shows you how to decide A if you can decide B. This is the normal, everyday life meaning of "reduction".

The linked answer does exactly that – it transforms an instance of $\overline{HALT}$ to an instance of $L_{all}$, thus reducing $\overline{HALT}$ to $L_{all}$.


Proof that median of an array is the number that minimizes the sum of manhattan distance to all points Given a sorted array A, the problem is to find a number that minimizes the sum of Manhattan distance to the numbers in the array. I found that the median of A is the solution, but was not able to come up for a proof or explanation for the same ( i.e why its not mean).

Any help is highly appreciated.

marks the set of numbers P={P1,P2,P3,..,Pn}

need to find number X:

|P1-X|+|P2-X|+...+|Pn-X|=D, which minimizes D.

the fact that X is the median can be shown using induction on the number of numbers n in P.

Base: n=1: trivial to see that the median is P1 and |P1-P1|=D=0 is minimal (D>=0).

now suppose that this holds for all P of size |P|=n, we need to show that this holds for |P|=n+1.

In other words:

given that |P1-X|+|P2-X|+...+|Pn-X|=D is minimal when X=Pm is the median of P={P1,..,Pn} show that |P1-X|+|P2-X|+...+|Pn-X|=D is minimal when X=Pm' is the median of P={P1,..P(n+1)).
notice that there are two cases m'=m+1 (n is even) or m'=m (n is odd).

I suggest drawing a simple example using n=3 and n+1=4 on an axis. Can you see why this must hold?


Why is $\forall x \in \mathbb{N}\ \Phi(x,x)$ unary but $\Phi$ is binary? May anyone explain me why $\forall x \in \mathbb{N}\ \Phi(x,x)$ is unary but $\Phi$ is binary?
In my latest exam I wrote that the universal function $\Phi^n(x_1, x_2, ..., x_n,y) = \psi^n_y(x_1,x_2,...,x_n)$ is unary because its $n+1$ parameter is a constant referring to the number of the S-program ($y$), but my teacher corrected me writing: "Pay attention: $\Phi$ is binary (and its second parameter is not a constant), but $\Phi(x,x)$ is."

A lot of confusion arises because the sloppy notation and imprecise terminology involving free and bound variables. Let me try to clear some of it up.
The title of your question wrongly claims that $\forall x \in \mathbb{N} \,.\, \Phi(x,x)$ is a function, which it is not. It is a truth value. Let us see why this is the case.
Suppose someone defined $f$ by writing down
$$f(x,y) = x^2 + 3 y,$$
where $x$ and $y$ range over $\mathbb{N}$. First of all, it would be more precise to define $f$ like this:
$$f = ((x, y) \mapsto x^2 + 3 y).$$
The right-hand side is read as "the function which maps $(x,y)$ to $x^2 + 3 y$". The variables $x$ and $y$ are bound, i.e., we get the same function if we rename them, for example $(u, v) \mapsto u^2 + 3 v$ is equal to $f$.
The function $f$ is binary because it takes two arguments.
With $f$ defined as above:

The expression $f(x, y)$ is not a function! It is a number. Indeed, you would have no trouble claiming that $f(x,y) \in \mathbb{N}$, would you? However, this number is parameterized by two free variables $x$ and $y$. Thus, which number it is depends on $x$ and $y$.

The previous remark maybe becomes clearer if we contemplate the fact that $f(3, 4)$ is not a function but a number, and so is $f(u,u)$ where $u \in \mathbb{N}$ is a free variable.

We can fix just one of the arguments to get a unary function, for example $x \mapsto f(x, 7)$ is unary because it is a map $\mathbb{N} \to \mathbb{N}$.

The expression $f(x, 7)$ is not a function! It is a number, parameterized by the free variable $x$.

Next, consider the definition
$$g = (x \mapsto x^2 + 3 y).$$
The function $g$ is unary because it takes one argument. However, $g$ depends on the free variable $y$. (Some people may call this $y$ a "constant", or call $x$ an "argument" and $y$ a "parameter", but let us not do that. We will stick strictly to the terminology "$x$ is a bound variable" and "$y$ is a free variable".) We may rename the bound variable but not the free one:

$(u \mapsto u^2 + 3 y)$ is equal to $g$
$(u \mapsto u^2 + 3 v)$ is not equal to $g$ because $y$ and $v$ are different free variables
$(y \mapsto y^2 + 3 y)$ is not equal to $g$ because the free variable $y$ does not appear in it.

Some people might define $g$ above like this:
$$g_y = (x \mapsto x^2 + 3 y).$$
They want to indicate that $y$ is a free variable in the definition of $g$. In our notation, this would correspond to
$$g = (y \mapsto (x \mapsto x^2 + 3 y))$$
so that now $g$ is a unary function without free variables. When we apply $g$ to $y$ by writing $g_y$, we again get a unary function, this time wit one free variable $y$. By the way, writing $g_y$ instead of $g(y)$ is just cosmetics.
Consider
$$\Phi = ((u, v) \mapsto u < 7 \lor (v + u^2 > 6).$$
Then $\Phi$ is a binary function because it maps from $\mathbb{N} \times \mathbb{N}$ to $\{\bot, \top\}$. It should be clear that:

$\Phi(x,x)$ is not a function. It is a truth value parametrized by the free variable $x$.

$x \mapsto \Phi(x,x)$ is a unary function mapping from $\mathbb{N}$ to truth values $\{\bot, \top\}$.

$\forall x \in \mathbb{N} \,.\, \Phi(x,x)$ is not a function. It is a truth value. Indeed, we can plug in $\Phi$ and get $\forall x \in \mathbb{N} \,.\, x < 7 \lor (x + x^2 > 6)$, which is false (a truth value, not a function).

What I think you really wanted to ask was this: why is $\Phi$ binary but $x \mapsto \Phi(x,x)$ is unary? Is the answer not obvious, once we use correct notation that does not mess up free and bound variables?
Regarding the discussion with your teacher, there you need to correctly indicate which things are supposed to be free variables and which ones arguments of functions. You wrote:
$$\Phi^n(x_1, \ldots, x_n, y) = \Psi_y^n(x_1, \ldots, x_n).$$
I am sure you can see such thigs in textbooks, but they are a bit sloppy. To be very precise, we need information on which things in $\Psi$ are supposed to be free variables and which ones are arguments. I would guess that what is meant is that
$$\Psi_y^n : \underbrace{\mathbb{N} \times \cdots \mathbb{N}}_n \to \mathbb{N},$$
which means that
$$\Psi : \mathbb{N} \to (\mathbb{N} \to \underbrace{\mathbb{N} \times \cdots \mathbb{N}}_n \to \mathbb{N})).$$
We see that $\Psi$ is a unary function, $\Psi_n$ is a unary function, and $\Psi^y_n$ is an $n$-ary function with free variables $n$ and $y$.
If we read your definition as
$$\Phi = (n \mapsto ((x_1, \ldots, x_n, y) \mapsto \Psi_y^n(x_1, \ldots, x_n)))$$
then $\Phi$ is an unary function and $\Phi_n$ is an $(n+1)$-ary function with free variable $n$.


Lemma 2 in Knuth's "Notes on Open Addressing" I'm trying to read Knuth's Notes on Open Addressing, and I don't quite follow the proof of Lemma 2.

The set-up
We're thinking about hashing $k - 1$ keys into a size $N$ array, with collision resolution via linear probing. In particular, we're considering sequences of hash values $a_1, ..., a_{k-1}$ ($1 \leq a_i \leq N$). All we keep track of is variables $X_1, ..., X_N$, where $X_i = 0$ if the $i$th entry of the array is open, and $X_i = 1$ if the $i$th entry of the array is storing a key.

Example
Suppose that $N = 5$, $a_1, a_2, a_3 = 1, 4, 1$. Then $X_1 = 1$, $X_2 = 1$, $X_3 = 0$, $X_4 = 1$, $X_5 = 0$.

Definition
$\begin{bmatrix} n \\ k \end{bmatrix}$ is the number of sequences $a_1, ..., a_k$ ($1 \leq a_i \leq n$) such that no overflow step occurs. The overflow step is when a key hashes to an index near the end of the array, but because $X_{\text{hash}} = X_{\text{hash} + 1} =  ... = X_N = 1$ already, we have to try to insert the key at the beginning of the array $X_1$.

In Lemma 1 Knuth proves that, for $0 \leq k \leq n + 1$, $\begin{bmatrix} n \\ k \end{bmatrix} = (n + 1)^k - k (n + 1)^{k - 1}$.

Definition
$Q(N, k, t)$ is the number of sequences $a_1, .., a_{k - 1}$ ($1 \leq a_i \leq N$ satisfying (*): $X_{N - t - 1} = 0$, $X_{N - t} = ... = X_{N - 1} = 1$, $X_N = 0$.

Proof of lemma 2
Lemma 2 states that
$$Q(N, k, t) = \begin{bmatrix} N - t - 2 \\ k - t - 1 \end{bmatrix}
\begin{pmatrix} k - 1 \\ t \end{pmatrix}.$$

If $a_1, ..., a_{k-1}$ satisfies (*), then there is a subsequence, of length $t$, which falls into the range $X_{N - t}, ..., X_{N - 1}$. The complementary subsequence, of length $k - 1 - t$, falls into the range $X_1, ..., X_{N - t - 2}$. Knuth counts the number of each such subsequence, and the number of combining these two subsequences together to produce $a_1, ... a_{k - 1}$.

My question
He seems to argue that

$$Q(N, k, t) =
\begin{bmatrix} t \\ t \end{bmatrix}
\begin{bmatrix} N - t - 2 \\ k - t - 1 \end{bmatrix}
\begin{pmatrix} k - 1 \\ t \end{pmatrix}.$$

But $\begin{bmatrix} t \\ t \end{bmatrix} = (t + 1)^t - t(t+1)^{t-1} = (t + 1)^{t - 1} \not = 1$, so I don't see how the conclusion holds.

I think that the notes have been reported incorrectly. Indeed CruiskeenLawn, you are right. I've found some very old notes
here which report the correct result. Indeed, in your copy, they simply forgot to add $\left[\begin{matrix} t\\ t\end{matrix}\right]$ term.
The Lemma you are looking for is on Page 2.


Time complexity and space complexity in recursive algorithm "The designer of an algorithm needs to balance between space complexity and time
complexity." - Comment on the validity of the statement in the context of recursive
algorithms.

This is a question from my university's previous paper. But i couldn't find a decent answer. Actually i am confused about how can a developer minimize the time-complexity for any recursive function. I get that if there is a tail-recursion then space complexity can be minimized. But can't get the idea of time-complexity.

One thing comes in mind is memoization. Simple well studied problem for this is Fibonacci numbers, simple recursion is as follow:

fib(int n)
{
  if (n < 3)
    return 1;

  return fib(n-1) + fib(n-2);
}

But with memoization, we can use an auxiliary array to get rid of extra calls:

f[1]=f[2] = 1;
fib(int n)
{
  if (n < 3)
    return 1;

  if (f[n] == 0)
     f[n] = fib(n-1) + fib(n-2);

  return f[n];
}

This simple change, reduces the time from $\Theta(\phi^n)$ to $\Theta(n)$.

The memoization technique sometimes uses more memory, but very faster in time, and one of a tradeoffs that software developer should be care about it is this.

Explanation of the memoization of Fibonacci numbers:

First we create an array $f$, to save the values that already computed. This is the main part of all memoization algorithms. Instead of many repeated recursive calls we can save the results, already obtained by previous steps of algorithm. As shown in the algorithm we set the $f[1],f[2]$ to $1$.

In the first if we actually check whether we are in the start or not. But we can remove this if statement. But for make it simpler to read I left it.

In the second if, we check if the value of fib(n) is already computed or not. This prevents us from multiple call for the same number, for example suppose we want to compute f(6), then in normal recursion we have the first recursion tree as shown in the following figure and in the memoization version we have the second tree. The reason is, in memoization we just compute the green vertices one time and then we save them into the memory (array $f$) and if needed we fetch them later.

In the following figure, green nodes are parts which are necessary to be computed (in this way), yellow nodes are precomputed ones, and red nodes are the nodes that are repeatedly computed in the first recursion.

As is clear from the image, in the normal case we have just precomputed f(1) and f(2), but in the memoization case, all functions for less than $n-1$ are precomputed, and this causes exponentially smaller recursion tree. (In memoization number of red nodes is zero, which is exponential in the normal recursion).


Third Normal Form and Boyce Code normal form I know that this is not a question answer site but for sake of explaining my doubt I have to post the entire question..

  Consider the following statements.

If relation R is in 3NF and every key is simple, then R is in BCNF
If relation R is in 3NF and R has only one key, then R is in BCNF

Both 1 and 2 are true
1 is true but 2 is false
1 is false and 2 is true
Both 1 and 2 are false

Ans given is $a$, but how can it be so?

I agree with the first statement but for the second one consider that we have a relation $R={\{A,B,C,D\}}$ where $AB$ is the key, and say $C->B$ then it satisfies $3nf$ right? But  it is $NOT$ in $BCNF$ right? as here we have $non-prime$  $deriving$  $a$  $prime$  $attribute$

$S_1:$ If relation R is in 3NF and every key is simple, then R is in
BCNF.
$S_2:$ If relation R is in 3NF and R has only one key, then R is in BCNF

Both statements are correct.
Your counterexample is as follow:
$R(A,B,C,D)$ where fds that hold are $FD = \{AB \rightarrow CD, C\rightarrow B\}$.
Now, this example does not satisfy premice of any of the statement because there are two candidate keys i.e $\{AB\}, \{AC\}$.


How to convert finite automata to regular expressions? Converting regular expressions into (minimal) NFA that accept the same language is easy with standard algorithms, e.g. Thompson's algorithm. The other direction seems to be more tedious, though, and sometimes the resulting expressions are messy.

What algorithms are there for converting NFA into equivalent regular expressions? Are there advantages regarding time complexity or result size?

This is supposed to be a reference question. Please include a general decription of your method as well as a non-trivial example.

There are several methods to do the conversion from finite automata to regular expressions. Here I will describe the one usually taught in school which is very visual. I believe it is the most used in practice. However, writing the algorithm is not such a good idea.

State removal method

This algorithm is about handling the graph of the automaton and is thus not very suitable for algorithms since it needs graph primitives such as ... state removal. I will describe it using higher-level primitives.

The key idea

The idea is to consider regular expressions on edges and then removing intermediate states while keeping the edges labels consistent.

The main pattern can be seen in the following to figures. The first has labels between $p,q,r$ that are regular expressions $e,f,g,h,i$ and we want to remove $q$.

Once removed, we compose $e,f,g,h,i$ together (while preserving the other edges between $p$ and $r$ but this is not displayed on this):

Example

Using the same example as in Raphael's answer:

we successively remove $q_2$:

and then $q_3$:

then we still have to apply a star on the expression from $q_1$ to $q_1$. In this case, the final state is also initial so we really just need to add a star:

$$ (ab+(b+aa)(ba)^*(a+bb))^* $$

Algorithm

L[i,j] is the regexp of the language from $q_i$ to $q_j$. First, we remove all multi-edges:

for i = 1 to n:
  for j = 1 to n:
    if i == j then:
      L[i,j] := ε
    else:
      L[i,j] := ∅
    for a in Σ:
      if trans(i, a, j):
        L[i,j] := L[i,j] + a

Now, the state removal. Suppose we want to remove the state $q_k$:

remove(k):
  for i = 1 to n:
    for j = 1 to n:
      L[i,i] += L[i,k] . star(L[k,k]) . L[k,i]
      L[j,j] += L[j,k] . star(L[k,k]) . L[k,j]
      L[i,j] += L[i,k] . star(L[k,k]) . L[k,j]
      L[j,i] += L[j,k] . star(L[k,k]) . L[k,i]

Note that both with a pencil of paper and with an algorithm you should simplify expressions like star(ε)=ε, e.ε=e, ∅+e=e, ∅.e=∅ (By hand you just don't write the edge when it's not $∅$, or even $ε$ for a self-loop and you ignore when there is no transition between $q_i$ and $q_k$ or $q_j$ and $q_k$)

Now, how to use remove(k)? You should not remove final or initial states lightly, otherwise you will miss parts of the language.

for i = 1 to n:
  if not(final(i)) and not(initial(i)):
    remove(i)

If you have only one final state $q_f$ and one initial state $q_s$ then the final expression is:

e := star(L[s,s]) . L[s,f] . star(L[f,s] . star(L[s,s]) . L[s,f] + L[f,f])

If you have several final states (or even initial states) then there is no simple way of merging these ones, other than applying the transitive closure method. Usually this is not a problem by hand but this is awkward when writing the algorithm. A much simpler workaround is to enumerate all pairs $(s,f)$ and run the algorithm on the (already state-removed) graph to get all expressions $e_{s,f}$ supposing $s$ is the only initial state and $f$ is the only final state, then doing the union of all $e_{s,f}$.

This, and the fact that this is modifying languages more dynamically than the first method make it more error-prone when programming. I suggest using any other method.

Cons

There are a lot of cases in this algorithm, for example for choosing which node we should remove, the number of final states at the end, the fact that a final state can be initial, too etc.

Note that now that the algorithm is written, this is a lot like the transitive closure method. Only the context of the usage is different. I do not recommend implementing the algorithm, but using the method to do that by hand is a good idea.


If $L$ is a $CFL$, then why isn't $L^*$ also $CFL$ I was studying closure properties of CFLs and I came across this. I want to understand why $L^*$ is not a CFL, can anyone explain me in depth with simple examples?

In fact, if $L$ is context-free then so is $L^*$. The easiest way to see that is using context-free grammar. Every context-free language $L$ is generated by some context-free grammar $G$ with starting symbol $S$. Now add a new starting symbol $S'$ and the productions $S' \to S'S|\epsilon$. The new grammar $G'$ is also context-free and generates $L^*$.


On $1$-way functions and formalizing my intuitions about them Let $a: \{0, 1\}^* \to \{0, 1\}^*$ be a $1$-way function and $b: \{0, 1\}^* \to \{0, 1\}^*$ be a $1$-way permutation.

Now, it makes intuitive sense to me that $a \circ b$ should be a $1$-way function, but I am having problems formalizing this. What would a rigorous proof of this look like? Or are my intuitions wrong and this is simply not a true statement?

What would a rigorous proof look like?  It would start with the assumptions that are given, and derive the conclusion you want to derive, with each step being logically and rigorously justified.

How should you approach this?  Start with the definitions.  If you know what the definition of a 1-way function is, then you know what you have to prove, to prove that $a \circ b$ is a 1-way function.  Start by trying to prove that, using the assumptions you are given.  You'll probably use a reduction at some point: if there exists an adversary against $a \circ b$, then....

This is a basic question, which suggests to me you should either review the material in your textbook on reduction-based proofs of security, or check whether you have the mathematical maturity for this topic.


Help: Context Free Grammar Construct the CFG given the following language:

$$\{a^i \; b^j \; c^k \;|\; i = j \; or \; j = k \}$$

The answer should be the following:

$$
\begin{align}
&S \to WQ  \mid XY \\
&W \to aW  \mid ε \\
&Q \to bQc \mid ε \\
&X \to aXb \mid ε \\
&Y \to cY  \mid ε
\end{align}
$$


Can SSL be hacked if we know some of plain data? As I know, SSL/HTTPS is two stage, first stage is public key encryption/decryption which transfers key of the second stage which is symmetric. It is true we don't have key, but we can have some of plain data and guess key so (at least some of messages), do you agree it is possible so?

Thanks!

No, it is not possible. Any modern encryption algorithm is designed so that even even if you have some ciphertext and part of the corresponding plaintext, it is unfeasible to find any information (other than the length) about the part of the plaintext that you don't know. This is true even if you get to choose all of the plaintext except one bit, and you get the corresponding ciphertext and you want to find the bit that you don't know. This property is called indistinguishability under chosen-plaintext attack (IND-CPA for short).

Unfeasible is a technical term, meaning that it requires an amount of computation that cannot be performed in practice. The theoretical definition is that the complexity of the attack is more than polynomial over the size of the key. In practice, key sizes are chosen so that it would take more than the total computational power available in the world for more than a lifetime to break the key (for example, it would take a billion PCs more than the age of the universe to break a 128-bit key).

Note that I simplified the definitions a bit; the actual definitions are fairly complex and subtle. If you want to understand them precisely, read a cryptography textbook.

In practice, this assumes that:

There is no flaw in the protocol, such as using the same key for different purposes or accepting invalid output, that could lead to the implementation acting as an oracle.
There is no flaw in the implementation, that could lead to secret information leaking directly or indirectly.
The algorithm genuinely has the IND-CPA property. It is in fact not known whether any encryption algorithm (apart from the very unwieldy one-time pad) has this property. In practice, people use algorithms that cryptographers have spent many years trying very hard to break, and failed.

In practice, most security flaws related to cryptography are due to implementation bugs. A minority are due to protocol weaknesses, and modern protocols tend to be designed with more attention than protocols designed 20 years ago. Flaws in modern encryption algorithms are extremely rare.