Proving language in Space Complexity I'd like to know if I have the right intuition and my answer is headed the correct way.

I am given a function
$ f = \{0, 1\}^* \rightarrow  \{0, 1\}^* $ that is computable in space $O(\log n)$ assume that for every $x \in \{0, 1\}^*$, $f$ is length preserving, $|f(x)| = |x|$.

Define
$$L = \left\{ x\#y \mid \ x, y \in \{0, 1\}^*, |x| = |y|, \ \text{and} \ f(x) = f(y)\right\}$$

I am suppose to prove that $ L \in  {\sf DSPACE}(\log n) $.

Please correct me if my intuition is incorrect.

My solution would be to build a decider $M$ which is a Turing machine.

$M$ takes inputs $x$ and $y$, run the function $f$ on input $x$ and $y$ and if the lengths of the two strings are equal then accept, otherwise reject.

Now the Turing machine runs in $ O(\log n) $ because the function $f$ is computable in $ O(\log n)  + O(\log n) = O(\log n) $ and comparing the length returned by the function is $ O(1) $
Thus the language is decidable by a Turing machine that is run in $ O(\log n) $ and only takes Space $ O(\log n) $.

Here is a rough idea how to solve this. You compare $f(x)$ and $f(y)$ character by character. Your tape is devided into 4 pieces. The first one is for simulating  $f(x)$ the second one for $f(y)$, then you have two parts, one that counts which character of $x$ you are currently computig, and another $O(\log n)$ area that helps you to navigate. Now the programm looks like this

Determine $|x|$ and $|y|$ (store it in binary!)  and check if there are the same.
Compute the first character of $f(x)$ by simulating it on your machine. Store the output in a TM-state. Pause the Computation of $f(x)$.
Walk $|x|+1$ step to the right.
Simulate $f(y)$ until you get the first character, check if it coincides with the start of $f(x)$, if no reject, otherwise continue.
Walk $|x|$ steps left.
Repeat the steps 2.-5. until you check $f(x)=f(y)$ completely.


Variant of the "Stable Roommates Problem" when room has not 2 but "n" mates I'm looking at the name of a variant of the Stable Roommates Problem, when the rooms have more than 2 mates, ie for example 6 to 8. Does this problem has a specific name? A well-known algorithm?

To summarize, the problem is the following: Given a set of $n$ people, and a symetric $n\times n$ affinity matrix between each person, find an optimal disjoint set partition of the people into $m$ groups of a given size, maximizing the global "affinity score" (the sum of each pair affinity in each group).

Why this question? I'm organizing a wedding ceremony with around 60 people, grouping people into tables of 6 to 8. Each person pair has an affinity weight, ranging from $-\infty$ (they can't stand each other) to $+\infty$ (they better be together).

This question is somehow related, but unfortunatly does not have any answer.

The stable roommates problem is to find a perfect matching in a non bipartite graph which is "stable". "Perfect" means that every one is assigned to a pair. "Stable" means that it does not exist 2 persons which would prefer to be together instead of their assignement. Note that the stable roommates may have no solution.

Now about your problem, the point is to define the "stable" statement on groups of 6 or 8. And as you said, you want to maximize the global affinity score which is quite different from looking for a stable situation.

Globally your problem is a "graph partition" which is NP-complete, and there is no "efficient" way to find a solution better than try all combinations. Some heuristic algorithms can provide very good results nevertheless.


Does converting adjacency matrix representation of graph of size $n \times n$ to adjacency list always require $O(n^2)$ time? Assume that I have the adjacency matrix representation of a graph in $0,1$ values. Does converting it to a corresponding adjacency list representation always have a time complexity of $O(n^2)$?

"Nothing is always."

Without any prior knowledge, the worst case time-complexity of converting an adjacency matrix representation of a graph in 0,1 values to a corresponding adjacency list representation is $\Theta(n^2)$.

However, if we know the graph is a sparse matrix with number of edges $m=o(n^2)$ and its adjacency matrix is stored in some compressed format like Yale format, then we can expect a conversion takes $o(n^2)$ time.


Time complexity of set intersection This problem involves the time-complexity of determining set intersections, and the  algorithm must give output on all possible inputs (as described below).

Problem 1:  The input  is a positive integer $m$, and two  unordered subsets $A$ and $B$ of $\{1,\dots,n\}$. The size of the input is $n+ |A| +|B|$.

Output: The set $A \cap B$, the intersection of $A$ and $B$.

As all  infinitely many  possibilities  are ranged through,  with  the size of output $n = m + |A| + |B|$,   is there a linear-time  algorithm that on any $(n,A,B)$, outputs  $A \cap B$? Is there an $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients? (Worst-case complexity.)

Problem 2:  The input  is a positive integer $m$, and  $j$ unordered subsets $A_1, \dots, A_j$  of $\{1,\dots,n\}$. The size of the input is $n+ |A_1| + \cdots + |A_n|$.

Output: $A_1 \cap  A_2 \cap \cdots \cap A_n$, the intersection of $A_1, \dots, A_j$.

As all infinitely many  possibilities  are ranged through,  with  the size of output $n = m + |A| + |B|$,   is there a linear-time  algorithm that on any $(n,A,B)$, outputs  $A \cap B$? Is there an $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients?  (Worst-case complexity.)

Are there references to the time complexity of these problems? I’m interested in the particular algorithms themselves, but if anyone knows that complexities above are linear-time or $n P(\log n)$ algorithm, where $P$ is some polynomial with integer coefficients, I’d be grateful to hear from you.  ( I’m less interested in algorithms that involve hash functions, but as long as such an algorithm works on all possible inputs, a hash function algorithm is okay.)   I’m not a computer scientist student but an older person learning things as they come along in work-in-progress.

Your post contains two problems. I will only address the first.

There is a simple $O(n)$ algorithm for computing $A \cap B$, which involves an array of length $n$.

Another algorithm sorts $A \cup B$ to find the intersection in time $O(n\log n)$. In contrast to the previous algorithm, this algorithm can be implemented using only comparisons. There is a matching $\Omega(n\log n)$ lower bound in the algebraic decision tree model; see for example lecture notes of Otfried Cheong.


For each particular $c,N,M$, this can be solved explicitly by constructing a DFA accepting the language. The general case may also be approached heuristically, though the dependency structure makes heuristic estimates harder to make.

The case $N = 1$ can be solved explicitly. Suppose that the alphabet is $\{0,\ldots,c-1\}$. Represent each word $w_1\ldots w_n$ as the sequence of differences $x_1\ldots x_n$, where $x_1 = w_1$ and $x_i = w_i - w_{i-1} \pmod{c}$ for $i > 1$. Your language then becomes
$$
\epsilon + \{0,\ldots,c-1\}((\epsilon + 0 + \cdots + 0^{M-1})\{1,\ldots,c-1\})^*(\epsilon + 0 + \cdots + 0^{M-1}).
$$
The corresponding generating function is
$$
1 + cx \cdot \frac{1}{1-\frac{x^M-1}{x-1}\cdot(c-1)x} \cdot \frac{x^M-1}{x-1} =
\frac{x^{M+1}-1}{cx-1-(c-1)x^{M+1}}.
$$
The asymptotic growth of the number of words is controlled by the smallest (in modulus) root of $(c-1)x^{M+1}-cx+1$. If this modulus is $\alpha$, then the growth rate of the sequence (under reasonable assumptions) is $\Theta((1/\alpha)^n)$.

Plotting a few of the polynomials $(c-1)x^{M+1}-cx+1$ reveals that there are two real roots in $[0,1]$. We are interested in the one near $1/c$. Suppose that $x=(1+\epsilon)/c$ is a root. Then
$$
1 = cx - (c-1)x^{M+1} = 1+\epsilon - \frac{c-1}{c^{M+1}} (1+\epsilon)^{M+1},
$$
and so
$$
\epsilon = \frac{c-1}{c^{M+1}} (1+\epsilon)^{M+1}.
$$
This shows that $\epsilon$ is exponentially small in terms of $M$, and so we can approximate $(1+\epsilon)^{M+1}$ by $1+(M+1)\epsilon$ to obtain the equation
$$
\epsilon \approx \frac{c-1}{c^{M+1}}(1 + (M+1)\epsilon)
$$
whose solution is
$$
\epsilon \approx \frac{\frac{c-1}{c^{M+1}}}{1-(M+1)\frac{c-1}{c^{M+1}}} = \frac{c-1}{c^{M+1}-(c-1)(M+1)} \approx \frac{c-1}{c^{M+1}}.
$$
Since $1/x = c/(1+\epsilon) \approx (1-\epsilon) c$, altogether we obtain that the number of words of length $n$ in which no symbol repeats $M$ times is $\Theta(\alpha^n)$, where
$$ \alpha \approx c - \frac{c-1}{c^M}. $$

Carrying this sort of analysis for $N > 1$ seems significantly more difficult.


Microsoft Singularity : why closed I'm talking about this one research project:

but MS closed it in 2008. I've read many articles about it, about high perfomance (30+% faster against tradinional monolithic kernels), much more secure etc. So it should be really a revolution in OS designing. Why they did it? I would be really happy if they didn't... So only one question i have: why? Was "effective managers" who destroyed it or some else? I'm thinging about it for many strenuous months...

First you need to understand the goals of Microsoft Research.

  Our labs are unique among corporate research facilities in that they
  balance an open academic model with an effective process for building
  research results into product development. This approach, unique among
  corporate research facilities, pays off for Microsoft as enhancements
  to virtually every product and service it offers and as entirely new
  lines of business for the company. At the same time, it produces
  significant technological and intellectual advances across the
  spectrum of computer science.

from: Inventing the Future of Computing

Second you need to see how these ideas are translated into current projects.

  Windows 7. The latest version of Microsoft’s flagship operating system
  incorporates a number of “under the hood” technologies from Microsoft
  Research that contribute to the product’s improved performance,
  reliability and usability. These include enhancements to handwriting
  recognition, graphics performance, networking and security.
  Additionally, the product development team made use of a number of
  Microsoft Research technologies to write and test code efficiently and
  more thoroughly identify potential security issues.

See: Bringing Innovations to Life and Making Computers More Capable and Useful

Lastly you need to understand that Singularity has been used as a springboard for other projects:

  Microsoft describes Singularity as a research project "which
  demonstrated that modern programming languages and software
  engineering techniques could fundamentally improve software
  architectures." Singularity ended up spawning and/or influencing a
  number of other operating system research projects at Microsoft,
  including Barrelfish, Helios, Midori (Wikipedia) and Drawbridge.

from The father of Microsoft's Singularity OS moves on


Checking if the mimimum is unique We have a finite poset and its subset $S$.

We can enumerate elements of $S$ using an iterator.

I need to check if there are more than one minimal elements of $S$ (regarding the above poset).

The best thing I came up with is to construct the graph of all elements of $S$ and then check it for minimal elements. But this:

requires to enumerate all elements of $S$ (while I would prefer to interrupt the calculating in the middle as soon as we get $2$ minimal elements);
may use much memory.

Is there a better way (without enumerating all $S$)?

You cannot avoid enumerating all elements. Consider the following two posets, with elements $x,y,z_1,\ldots,z_n$:

$x,y < z_i$ for all $i$.
$x,y < z_i$ for all $i < n$, and $z_n < x,y$.

The first poset has two minima, and second only one. You can only tell the difference by enumerating over all elements.

If there is a unique minimal element $z$, then $z < w$ for all other elements $w$ (since there is a minimal element below any given element). This allows us to use the following constant space algorithm, which assumes that the elements of the poset are $z_1,\ldots,z_n$:

Initialize $t \gets z_1$.
For $i=2,\ldots,n$: if $z_i < t$, let $t \gets z_i$.
Go over all elements again, and verify that $t \leq z_i$ for all of them.

There is a unique minimal element iff the verification succeeds.


How does BIRCH (Balanced Iterative Reduction Using hierarchical) CF Tree insertion algorithm work? I am studying Cluster Analysis and I came across BIRCH (Balanced Iterative Reduction Using hierarchical) http://en.wikipedia.org/wiki/BIRCH_(data_clustering) CF Tree insertion algorithm. I am confused what does branching factor(B), threshold for diameter of cluster in a leaf(T) means and in general how the algorithm works. It will be of immense help if someone can please explain it using an example. Thanks in advance.

Since you mentioned you haven't read it yet, I suggest you start by reading the original paper (which was linked to from the Wikipedia page).  For research-level contributions, that's often a helpful place to start, if you're having trouble finding a place to learn more.

Wikipedia also links to some slides on BIRCH.  That might be worth reading first to get an overview for what they're trying to achieve, before reading the original paper -- but you'll still need to read the original paper.  The slides are not a substitute for the paper, especially if you want to know the specifics of the algorithm.

You should not expect a textbook or slides to give this level of details.  They might try to give you the general idea or the overall intuition, but if you want to know the full details, it's likely that you'll need to read the original paper.  It's not unusual to find that you need to go to the primary sources, for recent research like this.


What is the difference between $ \alpha \to \alpha $ vs $ \forall \alpha. \alpha \to \alpha$? I was studying polymorphic types and I was finding the distinction with monomorphic types difficult to pin down (context CS 421). From the course I linked the have the following (vague attempt) at a definition:

  Monomorphic Types ($\tau$):

  Basic Types: $int,bool,float,string,unit, \dots$
  Type types: $\alpha, \beta, \gamma, \delta, \epsilon$.
  Compund Types: $\alpha \to \beta, int * string, bool list, \dots$

  Polymorphic Types:

  Monomorphic types $\tau $
  Universally quantified monomorphic types
  $\forall \alpha_1, \dots, \alpha_n . \tau $  (Question: is this not just universally quantified monomophism? If not what's the
  difference?)
  Can think of $\tau$ (I assume they mean monomorphic types) the same as $\forall . \tau$

I guess I find MANY things in this definition rather confusing. But was seems to be the core about my confusion is the difference between:

$$ expr: \alpha \to \beta$$

vs

$$ expr : \forall \alpha, \beta . \alpha \to \beta$$

I don't understand why they are not the same. What is the difference?

After writing this question I have some ideas of what might be going on and want to double check. Is what is going on that $\alpha \to \beta $ (the first one) saying that the expression $expr$ has a monomorphic type as its type (so it just has a real "fixed" type as a type)... Perhaps what's confusing me are type variables. Because nothing can be of a type "type variable". Type variables are just (meta) variables that can later be filled in with a real "basic type", right? So $\alpha \to \beta$ in my first example just stands for "some function type from one type to another but we have not decided which type to choose later, but the expression really just has a fixed basic type as a type once used in a real programming context". Is that right? So saying $fun x \to x$ has type $\alpha \to \alpha$ when reasoning in the meta-theory just means that the function really just has a fixed basic type except we have not specified it. While saying (in a more expressive type system) that $fun x \to x$ has type $\forall \alpha . \alpha \to \alpha$ means that that expression actually has the capability of encompassing all the monomorphic types at once. i.e. in the monomorphic version we actually have to define each identity function separately for each type (for the sake or argument) while in the polymorphic version we have only have 1 single programming construct for all of them...so the type variable basically just stands for a real monomorphic type (at least in the context of this definition).

I guess if we allowed type variables to be anything, then I'd be confused...I think my main worry is about type variables.

More rambling cuz I'm confused:

Lets look at this from FOL or as if we were trying to construct or define what an L-term is with an L-structure (see mathematical logic MATH 570). I think right now what confuses me is that this mapping between this vague definition of types (that seems to attempt to define an L-term) is not clear to me. Where is the recursion? What is the L-structure? This type definition is vague for me to really believe it. Something like this would be much better:

Related question: What does $ \forall \alpha_1, \dots , \alpha_n . \tau $ mean formally as a type?

$$\newcommand{\expr}{\mathsf{expr}}
\newcommand{\int}{\mathbf{Int}}
\newcommand{\List}{\mathbf{List}}
\newcommand{\let}{\mathbf{let}}
\newcommand{\id}{\mathsf{id}}
\newcommand{\in}{\mathbf{in}}
\newcommand{\map}{\mathsf{map}}
\newcommand{\string}{\mathbf{String}}
$$

It's not really possible to answer this without being a little more precise about the status of some things. To this end, let's be clear about distinguishing 'meta' variables from variables that may be part of the syntax of the language. I'll use Greek letters for meta variables and English letters for object variables. Term names will be sans-serif, like $\expr$, keywords/constants will be bold, like $\int$.

So, the two things you ask about actually become at least three things:
$$
\begin{align}
\expr &: α → β \\
\expr &: a → b \\
\expr &: ∀ a\ b. a → b
\end{align}
$$

The first is something you might see when discussing the simply typed lambda calculus. It does not have type variables in its object language at all, but it would be inconvenient to talk about particular concrete types all the time. So instead, people tend to talk about things in a schematic way, where meta variables stand in for arbitrary particular simple types. So, something like:

$$\frac{}{λx. x : α → α}$$

is actually a schematic statement, saying that $λx.x$ could be shown to have any type of the form $α → α$. But in a concrete derivation, each occurrence of $λx.x$ can only have a particular concrete type, like $\int → \int$. There is no universal identity function in the language, each occurrence of $λx.x$ stands for an identity function that only works on one type. Perhaps it might help to require annotating the lambda bound variable in this scenario, like so:

$$λ(x : \int). x$$

since now the notations for different identity functions are actually syntactically distinct.

Now, the obvious problem with this is that the concrete system is awful to work in. You can tell, because people are routinely writing schemas rather than concrete stuff. It is basically the type system of C, and schemas are like macros that automatically copy and paste your code, which is one way that people work around this awfulness in actual C (the other way being unsafe casting, which prevents the types from guaranteeing that your code actually makes sense).

To remedy this, we can move to #2, which is to make type schemas a well-defined part of the language. This is the approach of things like Hindley-Milner (HM), and the many languages based on it (ML, Haskell, ...). One way of looking at HM is that you add named definitions to the language itself, and these definitions are allowed to have internalized type schemas, rather than particular simple types. Then, when those named definitions are referenced, the schema can be instantiated to any concrete type necessary, and the fact that the schematic definitions are uniform in the choice of type ensures that they will work. So for instance:

$$
\begin{align}
\let\ &\id : a → a \\
      &\id = λ x. x \\
\in\ &(\id\ 5, \id\ \texttt{"hello"})
\end{align}
$$

This sort of system is a pretty strong sweet spot, because it is easy to implement and these sort of named schematic definitions cover a wide range of things that people want to write.

However, one deficiency is that these schematic objects are not first class. Expressions cannot be given a schematic type, only named definitions can, even though we somehow figure out that expressions are valid ways of implementing them. And we cannot take something with a schematic type as an argument to a function to be used at multiple instantiations. Even though:

$$λi. (i\ 5, i\ \texttt{"hello"})$$

seems similar to our term with $\let$ above, it is invalid, because $i$ is a lambda-bound variable, not a definition name.

So, the step to eliminating this discrepancy is to pass from type schemas: $$a → b$$ to quantified types: $$∀ a\ b. a → b$$.

The idea is that the quantifier can bind variables and produce something that is a type in its own right. Then we can ascribe these types to expressions (and variables), rather than only to named definitions. If we do keep named definitions around (which really we probably should, although many type theories aren't presented that way), they no longer have a special status with respect to typing.

All our previous schematic definitions can be translated to this new system by putting all the quantifiers at the beginning of the schema:

$$
\begin{align}
\let\ &\id : ∀ a. a → a \\
      &\id = λ x. x \\
 \in\ &(\id\ 5, \id\ \texttt{"hello"})
\end{align}
$$

But now we can write a corresponding lambda expressions and make sense of their types:

$$
\begin{align}
(λi. (i\ 5, i\ \texttt{"hello"})) &: (∀ a. a → a) → (\int, \string) \\
λx. x &: ∀ a. a → a \\
(λi. (i\ 5, i\ \texttt{"hello"}))\ (λx.x) &: (\int, \string)
\end{align}
$$

There are subtleties/consequences to these steps that I haven't mentioned, but this is sort of the core idea. You might also make slightly different choices for notation. For instance, you might require writing the prefix $∀$ syntax for the schemas because it is clearer that it means the named definition works for every choice of instantiation of the variables, not for some unknown choice.


Variance of MAXSAT clause satisfiability For a given MAXSAT problem, it is trivially easy to compute the mean number of clauses satisfied for all assignments, or equivalently the expected number of clauses satisfied by a random assignment.

Is it likewise possible to compute the variance of the number of clauses satisfied? And I mean an exact computation, not an estimate.

In general, which moments are easy to compute, and which are hard?

I would prefer an answer for general MAXSAT but would also be interested in the special case of MAX-3-SAT.

Suppose that the MAXSAT instance consists of clauses $C_1,\ldots,C_m$. Denote by $X$ the expected number of clauses satisfied by a random assignment. Then
$$
\mathbb{E}\left[\binom{X}{d}\right] = \sum_{\substack{S \subseteq [m] \\ |S|=d}} \Pr[C_i \text{ is satisfied for all } i \in S].
$$
This gives a roughly $O(m^d)$ algorithm for computing the $d$th moment.


4-partition elements summation NP completeness How can we prove that the following problem $A$ is NP complete?

Given a set of integers $S={a_1, ..., a_n}$ and a number $D$, is it possible to find disjoint sets $S_1, S_2, S_3, S_4$ such that $S_1 \cup S_2 \cup S_3 \cup S_4=S$ and

$$ -\sum_{j=1}^{4}\frac{\sum_{a_i \in S_j}a_i}{\sum_{a_i \in S}a_i}\log_2(\frac{\sum_{a_i \in S_j}a_i}{\sum_{a_i \in S}a_i})\geq D$$

I was thinking on using some NP complete problem $B$ and showing that $B \leq_P A$, but I can't figure out what reduction would work.

Here is what I tried (simplified the problem to 2 sets):
Given a set $S$ of n elements, I tried to prove that $S \in \text{Partition-Problem} \iff  \langle S, 1 \rangle \in A$.
If $S$ is an instance of the partition problem, it means there are 2 subsets in $S$ that have the same sum ($n/2$). Therefore the expression in $A$ (with 2 sets instead of 4) evaluates to $-\log_2 (1/2)=1$. Then proving $S \in \text{Partition-Problem} \Rightarrow \langle S, 1 \rangle \in A$ is trivial. However I am still stuck at proving the $\Leftarrow$ part.

Let's say that the numbers $a_1,\ldots,a_n$ are non-negative, and sum to $A$. They induce a probability distribution on $\{1,\ldots,n\}$, in which the probability of $i$ is $a_i/A$.

Given a partition $S_1,S_2,S_3,S_4$, let $I$ be a random variable distributed as above, and let $X$ be the index of the set to which $I$ belongs (so $X \in \{1,2,3,4\}$).
Your condition then reads $$ H(X) \geq K, $$
where $H(\cdot)$ is the entropy function.

This suggests choosing $K = 2$, since we know that $H(X) = 2$ iff $\Pr[S_1] = \Pr[S_2] = \Pr[S_3] = \Pr[S_4]$.

We can now describe a reduction from PARTITION to your problem. Given an instance $b_1,\ldots,b_m$ of PARTITION, where $b_1,\ldots,b_m$ are non-negative integers summing to $B$, create an instance of your problem by adding two copies of $B/2$, and by taking $K=2$. The list $b_1,\ldots,b_m,B/2,B/2$ can be partitioned into four parts with equal sum (i.e., $H(X) \geq 2$) if $b_1,\ldots,b_m$ can be partitioned into two parts with equal sum.


Is this lambda abstraction created as a generator of a recursive function? In lambda calculus, a recursive function $f$ is obtained by

$$ f = Y g $$

where $Y$ is the Y combinator and $g$ is the generator of $f$ i.e. $f$ is a fixed point of $g$ i.e.  $f == g f$.

In The Scheme Programming Language, I saw an example implementing a recursive function $f$ that sums the integers in a list:

(let ([sum (lambda (f ls)
                  (if (null? ls)
                     0
                     (+ (car ls) (f f (cdr ls)))))])
(sum sum '(1 2 3 4 5)))  => 15

What is the mathematical derivation that drives to create the lambda abstraction

 lambda (f ls)
     (if (null? ls)
         0
        (+ (car ls) (f f (cdr ls))))

?
It looks like a generator of $f$, but not entirely.

Thanks.

If you look at the $Z$ combinator (because we're in an eager context), you have $$Z=\lambda g.(\lambda f.g(\lambda v.ffv))(\lambda f.g(\lambda v.ffv))$$

If you look at the code, we don't apply a fixed point combinator to sum, we simply apply sum to itself, so there's no reason for sum to be "generator".

You can also readily show that sum is (modulo currying) equal to $\lambda f.g(\lambda v.ffv)$ for some $g$, basically by replacing (f f ...) with (h ...) where h is the argument to $g$ in the definition for sum (minus the outermost lambda).


Finding values in a space that matches a relational query Assume we have 26 vectors ${A,B,C,....,Z}$ all have 1 million integers. given a query:
$$
\vec{query} = (r_a, r_b, r_c, ..., r_c)
$$
I want to find a match vector $\vec{m_{1 \times 26}} = (a, b, c, ..., z)$ that satisfies the following criterias:
$$
a \in A, b \in B, c \in C, ..., z \in Z \\
\text{and} \\
r_{a} = \frac{a}{\sum_{\theta \in m}{\theta}}, r_{b} = \frac{b}{\sum_{\theta \in m}{\theta}}, ..., r_{z} = \frac{z}{\sum_{\theta \in m}{\theta}}
$$
in which $\sum_{\theta \in m}{\theta}$ is basically sum of the values in vector m. In other words, let say given the amount of share each $a, b, c, ..., z$ has in my math vector m, I want to find the elements. Of course, one yet not feasible solution is checking all ${(10^6)^{26}}$ possible combinations and check if there exists any match. There could be multiple answers, but any of them is fine.
Example:
Let say all ${A,B,C,....,Z}$ are equal to each other and contains elements between $1$ and $10^6$ like $\{1,2,3,...,10^6\}$. given query $\vec{query} = (\frac{1}{26}, \frac{1}{26}, \frac{1}{26}, ..., \frac{1}{26})$, $m$ is one of the many possible solutions:
$$
\vec{m} = (1,1,1,...,1).
$$
My question is, what could be the fastest algorithm for solving this problem?

One approach is to guess $a$ (i.e., iterate over all possibilities for it, and the following for each possibility).  Then, you can infer the value of $b$, namely, $b = a r_b/r_a$, so test whether $b \in B$.  Do the same for each of $c,\dots,z$.  If they all work, then you have found a solution; otherwise, proceed on to your next guess at $a$.  This should give you approximately a linear running time if you use the right data structures for storing the vectors (e.g., a hashtable).
A similar approach is to compute the vectors $A/r_a$, $B/r_b$, ..., $Z/r_z$, and then look for an item that occurs in all of those scaled vectors, e.g., using a hashtable or a counter or by sorting and merging the sorted lists.


Simple property of DFAs Do you know if this simple property of a DFA is stated as a property (or theorem) in some Automata theory book (possibly with a particular name)?

Property: Given a DFA $A = \{ Q, \Sigma, \delta, q_0, F \}$, if $w = uv$ and the state of $A$ on input $w$, after scanning $u$ is $q_i$ (when the head is at the beginning of subword $v$); and $A' = \{ Q, \Sigma, \delta, q_i, F \}$ then $w \in L(A)$ if and only if $v \in L(A')$

Actually I think I have spotted this property in a book. It uses the "extended" transition relation $\delta^*$, i.e., for strings rather than single letters.

  Other properties you would expect $\delta^*$ to satisfy can be derived from
  our definition. For example, a natural generalization of the recursive
  statement in the definition is the formula
  $$\delta^*(q,xy) = \delta^*(\delta^*(q,x),y))$$
  which is true for every state $q$ and every two strings $x$ and $y$ in $\Sigma^*$.
  The proof is by
  structural induction on $y$ and is similar to the proof [...] in Example 1.27.

  John C. Martin, Introduction to Languages and the Theory of Computation, McGraw-Hill, 4th edition, c2011. Page 54.

I hope you agree with me that this matches the "machine" terminology you use in your question.


Signal translation with Seq2Seq model I'm currently doing some research on signal processing and I got a dataset which includes the signal in itself and its "translation".

So I want to use a Many-to-Many RNN to translate the first into the second.
After spending a week reading about the different option I have, I ended up learning about RNN and Seq2Seq models. I believe this is the right solution for the problem (correct me if I'm wrong).
Now, as the input and the output are of the same length, I don't need to add padding and thus I tried a simple LSTM layer and TimeDistributed Dense layer (Keras):
model = Sequential([
    LSTM(256, return_sequences=True, input_shape=SHAPE, dropout=0.2),
    TimeDistributed(Dense(units=1, activation="softmax"))
])

model.compile(optimizer='adam', loss='categorical_crossentropy')

But the model seems to learn nothing from the sequence and when I plot the "prediction", it nothing but values between 0 and 1.
As you can see, I'm a beginner and the code I wrote might not make sense to you but I need guidance on few questions:

Does the model make sense for the problem I'm trying to solve ?
Am I'm using the right loss/activation functions ?
And finally, please correct/teach me

I am skeptical that machine learning is the right tool for this problem.  I would look for a more direct solution, perhaps using peak detection or changepoint detection, or some other form of classical method for time-series analysis.
If you do use machine learning, cross-entropy loss is not the right loss for your problem, and you will definitely need to change that.


Find longest path in graph with N nodes and N edges We have given weighted undirected connected graph with $n$ nodes and $n$ edges, we want to find the longest path in it. Note that the path should be in each node at most once. Since the graph has $n$ edges clearly it has exactly 1 cycle, and removing 1 edge from this cycle will lead us to a tree.

Clearly we can iterate over all edges of the cycle and run dijkstra to find this path in tree. But this has complexity of $O(N^2)$ in worse case if the whole graph is cycle. I was thinking that greedy solution that we should remove always the edge with lowest weight that lies on the cycle. How to prove this greedy solution, is it correct at all?

The greedy solution is not correct.

Let me construct a graph with $5$ vertices, $A$, $B$, $C$, $D$, $E$.

$AB$ is an edge with weight $1$.

$BC$ is an edge with weight $2$.

$AC$ is an edge with weight $2$.

$AD$ is an edge with weight $100$.

$CE$ is an edge with weight $100$.

The longest (heaviest) path is $DABCE$ with weight $203$. After removing $AB$, which is the lightest edge of the cycle $ABC$, the longest path is $DACE$ with weight $202$.


Mental poker: proving dealt hand is fair I have just read mental poker, described in this fascinating paper(PDF) by cryptographic greats Adi Shamir, Ron Rivest, and Leonard Adleman.

Assuming I have a website, (TTP) how can I prove to the player that the hand dealt to him is fair? Most importantly how can I prove that I didn't bruteforce until an unfair hand is dealt to him to gain house edge, are there any C# implentations of such code?

I found out you can prove a hand is fair with the following method:

Every user has a randomly generated "secret" in an input field he can personally edit, before each card is picked all the secrets are sent to the server and hashed seperately, then all the secrets are hashed into a single hash which is used as a seed for the random functions.

Then all the players hashes are sent to every player and being displayed on that players screen, when it is safe, every player is also shown all the other players secret phrases this way:
A) Every player knows that the secrets weren't changed after the game since they have the hashes B) It is impossible for them to find the secrets and get an unfair advantage before it is safe to reveal the secrets C) They can now know that every card is dealt fairly


Cardinality of sets and strings -> confused I have a question regarding the cardinality of sets and strings.
If $ \Sigma^* $ is empty, the cardinality is 1, because the empty word $ \varepsilon $ is counted.
If $ \Sigma^+ $ is empty, the cardinality is 0, because the empty word is excluded from the set.
If $ \Sigma $ includes at least one symbol, the cardinality of $ \Sigma^* $ is inifite.
If I use a string without the definition of $ \Sigma $, for example to define a variable, then I have problems to understand the cardinality. So if I set a variable to a string: $ a = "a" $, the cardinality of the string is 1. But if I set a variable to an empty string: $ a = "" $, the cardinality is also 1, because "" is the same as the empty word $ \varepsilon $.
The first time I noticed this was in a book whereas the definition of Pumping Lemma allows $ i=0 $ for the pumped word-part $ y $. Which means for me that $ y^0 = \varepsilon $ is allowed, because $ \varepsilon $ counts with 1. At the same time, others sources mention that it's not allowed to define $ y = \varepsilon $ for the Pumping Lemma.
Is the book wrong with allowing $ i = 0 $, or are the other sources wrong by disallowing $ y = \varepsilon $? Or do I completely misunderstand this?
Thank you!

You are confusing the size of a set of things and the size of the things the set contains.
The empty set contains nothing. Its size (or cardinality of you want to be sesquipedalian) is 0.
A set of containing one thing has size 1. It doesn't matter whether the one thing is an elephant, a flea, or a string. If there is one thing, the cardinality is 1. That thing could even be a set, even the empty set. The empty set is a thing which contains nothing but it is not nothing. It is a thing, so it can be the element of another set.
A string is not a set, even though it consists of elements of a set of letters. It differs from a set in that its elements are ordered, and therefore might repeat. When we count the size, we count each repeated element too. But both a string and a set can be empty. The empty set has size 0 but it's also one thing. The empty string has size 0, and it is also a thing. (A different thing).
So,
$$\begin{align}\mid\{\}\mid&=0\\
\mid\{\{\}\}\mid&=1\\
\mid\{“”\}\mid&=1\\
\mid\{“”, \{\}\}\mid&=2\\
\end{align}$$
We usually talk about the length of a string (or other sequence) rather than its cardinality, but the two concepts are shown with the same operator (the pair of vertical bars above, also used for "absolute value"), because they are easily related. In fact, we can think of a string (or sequence) as a set of mappings, each integer in a contiguous finite range is mapped to a single character (or element of the sequence). Even though the two characters are the same, the mappings in $\{<1\to a>, <2\to a>\}$ differ (because the integers differ), and the two mappings clearly denote the string $aa$. The cardinality of the set of mappings is 2, just as is the length of the string.
The empty string corresponds to an empty set of mappings (as one might expect), so its cardinality is 0. (As we saw above, this is different from the cardinality of a set containing the empty string.)

Finally, your question about the pumping lemma is a different confusion, but still a confusion having to do with emptiness.
The pumping lemma states that $|y|>0$, so it is clear that $y$ cannot be  $\epsilon$. But it allows you to pump $y^i$ for any non-negative $i$. There is no contradiction here. $y^0 = \epsilon$ for any $y$, by definition. So the pumping lemma lets you produce a string where $y$ has been replaced with $\epsilon$ (in other words, deleted). That has nothing to do with the fact that the $y$ being eliminated actually existed in the original string. (Or perhaps it does, since eliminating nothing is a no-op.)


How to determine if a black-box is polynomial or exponential I have a problem which essentially reduces to this:

You have a black-box function that accepts inputs of length $n$.
You can measure the amount of time the function takes to return the answer, but you can't see exactly how it was calculated.
You have to determine whether the time-complexity of this function is polynomial or exponential.

The way I did this was by running thousands of random sample inputs of varying lengths through the function, then plotting them on a scatter plot with times on the y-axis and input length on the x-axis.

What are some metrics and methods I can use to determine if these points best fit to a polynomial curve or to an exponential curve?

(Similar question asking how to draw polynomial/exponential best fit lines in Python on Stack Overflow: https://stackoverflow.com/questions/23026267/how-to-determine-if-a-black-box-is-polynomial-or-exponential)

Theoretically speaking, this is impossible to accomplish, basically because "polynomial" and "exponential" are asymptotic concepts, and no prefix of the data guarantees anything about the behavior at infinity.

Practically speaking, you can try to compute $t(n)^{1/n}$ and so if it approaches a constant bounded away from 1. If so, it is exponential. To test whether it's polynomial, you see whether $\log t/\log n$ approaches a constant. These are only rough tests, of course, but they could be useful in practice.


Can a distributed algorithm be serial? Can  a distributed algorithm be serial?
For example if I have 3 distinct agents in a network would an algorithm that looks like this be considered a distributed algorithm?

    Process ABC
       If (you are agentA) then
           Do stuff
       Else if (you are agent B) then
           Wait until agent A has finished doing stuff
           Do other stuff
       Else if (you are agentC) then
           Wait until agent B has finished doing stuff
           Do your own thing
       EndIf
    EndProcess

To my understanding it should be considered as distributed as long as the agents don't share memory. Wouldn't being serial defeat the purpose of having a distributed algorithm though?

Distributed algorithms are sub-type of parallel algorithm. Different parts of algorithm executes simultaneously on different processors with minimum information sharing and minimum dependency among them. Although the difference between parallel algorithm and distributed algorithm is not very clear but in general parallel algorithm is used for speed-up and increase data handling capacity while distributed algorithm is mainly implemented for fault tolerance, scalability. But in your case, may be you are just storing data in different places (distributed) but the algorithm you are using is not a distributed algorithm.


Meaning of empty clause Why does the empty clause is logically equivalent to a contraddiction:
$\square \cup \square \Longleftrightarrow \perp$

and why the empty cube is logically equivalent to a tautology:
$\square \cap \square \Longleftrightarrow \top$ ?

You have to understand that this is a convention. Conjunctions and disjunctions are supposed to be applied to formulas. Sometimes we want to keep things general, so that we may have to allow "empty disjunctions" and "empty conjunctions", and to that purpose we define what they are.

Here is one way to see why this convention is used. Let us consider a binary commutative associative operation $\oplus\colon A\times A\rightarrow A$ on some set $A$. Suppose moreover that there exists an element $e\in A$ such that $\forall a\in A, a\oplus e = e\oplus a = a$.

Since the operation is associative, we can make sense of the expresion $\bigoplus_{i\in I} a_i $ when $I$ is a finite non-empty set, which we define to be $(\dots(a_{i_1}\oplus a_{i_2})\oplus\ldots\oplus a_{i_{n-1}})\oplus a_{i_n}$. Since we don't want to always have to specify what happens when $I$ is empty, we take the convention that $\bigoplus_{i\in I} a_i = e$ when $I=\emptyset$. Why is this convention useful? It allows to write things like $$\left(\bigoplus_{i\in I} a_i\right) \oplus \left(\bigoplus_{i\in J} a_i\right) = \bigoplus_{i\in I\cup J} a_i$$ even if $I,J$ are allowed to be empty sets (where we implicitly replace $J$ by some other enumeration $J'$ that is so that $J'\cap I=\emptyset$). If we were to take some other convention, we would always have to be careful when writing the expression above.

See how this general situation occurs a lot in mathematical writing:

the empty sum $\sum_{i\in I} a_i$ is taken to be $0$ when $I=\emptyset$, as $0$ is a neutral element for the addition of real numbers,
the empty product $\prod_{i\in I} a_i$ is taken to be $1$ when $I=\emptyset$,
in the example of formulas, consider the binary operator $\lor$. A clause is a disjunction of propositional variables, as you say, hence it can be written as $\bigvee_{i\in I} p_i$. When $I$ is empty, we want to define the empty disjunction as the neutral element for $\lor$. This element is $\bot$ (up to logical equivalence), as $p\lor \bot \Leftrightarrow \bot\lor p\Leftrightarrow p$ holds.
in the example of formulas and cubes, we want to give a meaning to $\bigwedge_{i\in I}p_i$. Following the same convention, we use the neutral element for $\land$, which is $\top$: indeed, for any proposition variable it holds that $p\land\top\Leftrightarrow\top\land p\Leftrightarrow p$.


How are artificial intelligence and Natural intelligence compared? I can remember reading that computer intelligence is heading (or maybe the most powerful ones already have) towards the Natural intelligence of a four-year-old child. But how are the two kinds of intelligence compared?

You are probably referring to ConceptNet (created by the Massachusetts Institute of Technology under its Artificial Intelligence program).

It's a software system / semantic network containing lots of things computers should know about the world, especially when understanding text written by people.

Researchers from the University of Illinois (research team led by Stellan Ohlsson) did a study on the ConceptNet 4 version of the AI and they discovered that its IQ level is the same as that of a 4-year-old child (somewhat... see below).

The chosen IQ test is known as the Wechsler Preschool and Primary Scale of Intelligence (third edition, WPPSI-III). It's commonly used in schools across the United States and is designed to measure the level of intelligence in five key categories and consists of 14 subtests (picture memory, similarities, object assembly, picture naming...).

  The  test  questions  (e.g. "Why do we shake  hands?")  were  translated into ConceptNet 4 inputs using a combination of the simple natural language processing tools that come with ConceptNet together with short Python programs that we wrote. The question answering used a version of ConceptNet based on spectral methods.

  The  ConceptNet system  scored  a  WPPSI-III  VIQ  that is  average  for a four-year-old child, but below average for 5 to 7 year-olds

  [CUT]

  The large variations among subtests and ordinary common sense strongly suggest that the WPPSI-III VIQ results do not show that "ConceptNet  has  the  verbal  abilities  a  four-year-old."

  Rather, children's IQ tests offer one objective metric for the evaluation and comparison of AI systems

(From Measuring an Artificial Intelligence System's Performance on a Verbal IQ Te st For Young Children - Stellan Ohlsson, Robert H. Sloan, György Turán, Aaron Urasky)


Mealy to Moore Conversion Consider an $m$ output, $n$ state Mealy machine. How many states does the equivalent Moore machine contain?

The answer is $mn$ but my argument is that the total number of output produced while reading a string of length $n$ ($n$ states) Mealy will produce $m$ outputs ($m$ transitions) but a Moore machine produces a output even in the initial state without any transitions. So to accommodate the first transition of the Mealy machine (the first output of the Mealy) we need another state in the Moore machine. So the answer should be $mn + 1$.

Can anyone tell where am I going wrong?

It is very simple to understand.

The Mealy machine has 'm' outputs that means total 'm' transitions possible.
Number of states are 'n'.
Hence, there are a maximum of m*n transitions possible in total.

All these transitions should be depicted in Moore machine as well, as the power of both are same.


Shortest path between 2 vertices using at most K edges using Bellman-Ford I'm a bit confused about stopping at Kth iteration on the Bellman-Ford algorithm to find the shortest path of at most length k from s to t.
Let me show you a graph and explain you what I understand:

At first iteration, I will have:

Shortest path to get to A is S->A (cost 1)
Shortest path to get to B is S->B (cost 4)
Shortest path to get to T is still unknown

At second iteration I will have:

Shortest path to get to A is S->A (cost 1)
Shortest path to get to B is A->B (cost 2(A->B) + cost 1(S->A) = 3) updated!
Shortest path to get to T is B->T

But now going to B takes 2 edges instead of 1, so going to T is 3 edges away now: S->A->B->T, and this has happened in 2 iterations.

What am I understanding wrong?

The bellman ford algorithm presents to us the cost of all the shortest paths from a source vertex to all the other vertices . For constructing the path we reconstruct it after the algorithm has terminated and returned to us the cost. We backtrack on our solutions and reconstruct the path so don't get confused if you don't get the correct path at an intermediate step of the algorithm.
(Just for some additional information while coding the algorithm you might have notices the use of an two dimensional array which stores solution at each step . the same is used to reconstruct the path.)

The recursive definition of the algorithm is

$\delta^{k+1}(v) = \min \Big(\delta^{k}(v), ~ \min_{x\in\mathbb{N} - \{v\}} (\delta^k(x) + w(x, v) ) \Big) $

For the example which you have presented

When the edge budget is $0$ :

The shortest path from S to T is $+\infty$.

When the edge Budget is $1$ :

we till have the cost to be $+\infty$.

When the edge budget gets $2$ :

We update the cost of our path to : $7$

When the edge budget is $3$:

We now get the following : $\min ( 7 , \min (6))$

Hence giving the final cost as $6$.


Invariant For Nested Loop in Matrix Multiplication Program I'm making a graduate thesis about proving correctness of program for multiplying 2 matrices using Hoare logic. For doing this, I need to generate the invariant for nested loop for this program:

for i = 1:n
    for j = 1:n
        for k = 1:n
            C(i,j) = A(i,k)*B(k,j) + C(i,j);
        end
    end
end

I've tried to find the invariant for inner loop first, but I can't find the true one until now. Is there someone can help me for finding the invariant for above program?

You need the line C(i:j) = 0 just before the innermost loop; otherwise, the code is incorrect.

Assuming that line is in place, here is the (strongest possible) invariant just before the assignment in the innermost loop:
\begin{align*}
C_{IJ} &= \sum_{k=1}^{n} A_{Ik}B_{kJ} & \text{for all $I$ and $J$ such that $1\le I < i$ and $1\le J\le n$}
  \\
\text{and}~~~ C_{iJ} &= \sum_{k=1}^{n} A_{ik}B_{kJ} & \text{for all $J$ such that $1\le J< j$}
  \\
\text{and}~~~ C_{ij} &= \sum_{K=1}^{k-1} A_{iK}B_{Kj}.
\end{align*}
(Yes, the whole thing.)  The invariant just after the assignment has $k$ in place of $k-1$ in the last sum, but is otherwise identical.


Algorithm for solving a mixed integer programming problem in polynomial time? I have the following mixed integer programming (MIP) problem:
$$
\begin{array}{rll}
\text{Maximize } & z=k \\
\text{subject to }
& a_ik - m_i \geq 0 & (i=1,\dots,n) \\
& b_ik - m_i \leq 1 & (i=1,\dots,n) \\
\text{where}
& k \in \mathbb{R}_{\geq 0}, m_i \in \mathbb{N}_0 & (i=1,\dots,n),
\end{array}
$$
where $a_i,b_i$ are non-negative real numbers such that $0 \leq a_1 < b_1 < a_2 < b_2 < \dots < a_n < b_n$ (defining $n$ "forbidden intervals" $(a_i,b_i)$), $k$ is an unknown repetition frequency, and $m_1,\dots,m_n$ are unknown integers (telling how many repetitions will occur before the different intervals).
(Alternatively, the MIP-problem can be rephrased as "Find the minimal $x \in \mathbb{R}_{>0}$ such that $mx\not\in(a_i,b_i)\ \forall\ m\in\mathbb{N},i\in\{1,\dots,n\}$". It is by defining $k=1/x$, and $m_i$ as the largest non-negative integer for which $m_i x \leq a_i$, that the MIP formulation can be obtained.)
I need to either come up with an algorithm to solve this problem in polynomial time, or prove that the problem is NP-hard (or NP-intermediate if not NP-hard, I guess). I have tried to come up with a poly-time algorithm but not been successful, but I don't really know how to prove NP-hardness either.
How can I prove that this problem is NP-hard, or alternatively, is there some algorithm with a polynomial (in terms of the input size, i.e., the size required to store the input in memory) worst-case time complexity that can solve it?
In general, how do one prove NP-hardness? What I understand, for a given problem H, if every problem in NP problem can be reduced H in polynomial time, then H is NP-hard. But how do I prove that this is the case? There has to be close to infinitely many problems in NP, so is it enough to show for one of the problems that are NP-complete that it can be reduced to H in polynomial time? Is there some list of NP-complete problems that I can look at to try to prove that this MIP problem is NP-hard?

Finding an upper limit for k is trivial. Let d be the minimum of $b_i - a_i$ over all i, then k ≤ floor (1 / d).
And for each k up to the upper limit, it is trivial to check that floor ($a_i \cdot k$) = floor ($b_i \cdot k$).


Halting problem - one issue that's bothering me To my knowledge, halting problem asks if there exists a program that decides whether a program being tested, given some input data (no matter what program it is, or what input data we give) will terminate or not. The answer to this problem is 'no'. In other words, there is no 'single' program that can verify it for all possible pairs (some algorithm, some input data).

But it doesn't mean we can't decide if particular program X will terminate or not.

I can't comment other answers yet, but one of them brought my attention:

  In practical terms, it is important because it allows you to tell your
  ignorant bosses "what you're asking is mathematically impossible".

Maybe you can tell me what that person meant? In my scenario, my ignorant boss can ask me to verify (actually, prove or disprove) if my program (that's a particular program) will terminate or not. And of course there are pairs (algorithm, input data) that can be proven to terminate (or never terminate).

The question is - can I prove it for every such pair (program, input data) separately? Even if the answer is yes, then there's a problem - there can be infinitely many 'input data'. So it's quite natural to ask - can I prove, for every algorithm, that this algorithm will terminate (or the opposite), no matter what input data I provide?

No, you cant prove this for every algorithm (Turing machine). This becomes a question about the nature of proofs rather than a question about computation.

Consider the following Turing machine $M(x)$: check if there exists a proof for the statement $\forall x \hspace{1mm} M(x)$ halts, of length $\le |x|$ (for explanation on the self reference, see Klenee's recursion theorem). If such proof is found, get into an infinite loop (otherwise halt).

Clearly you cant prove $M(x)$ halts for all $x$, since if you can find a proof of length $p$, it wont halt for all inputs of size $\ge p$. In addition, you cant prove $M(x)$ doesn't halt for some $x$, since this would mean there exists a proof for the halting of $M$ on all inputs (contradiction). The situation here is, that if our axiom system is consistent, then $M(x)$ halts for all $x$, but you cant prove it (meaning you can prove in your theory $T$ that if $T$ is consistent then $\forall x \hspace{1mm} M(x)$ halts, but you cant prove it halts without this assumption, unless your system is inconsistent).


Is a PDA as powerful as a CPU? This is a question I have stumbled upon in my exam revision and I find it intriguing:
My computer is blue and it has a massive graphics card and a DVD and every-
thing so which is more powerful: my computer or a Pushdown Automaton?

My Thoughts
When we talk about power I have assumed this to be computational power. I believe that a PDA has the computational power to equal the computational power of a CPU (cpu in this case is the core elements of a computer ie memory and processor). This is because a PDA utilises a stack which is memory(RAM) in a computer. The PDA has states as does a CPU and also the PDA calculates simple logic at each state. I realise that the PDA itself would be a complex series of states to emulate the computational power of the cpu and there would have to be a series of PDAs to compute different functions.
My Question:  I know that Turing machines are best used to simulate the logic of a CPU but am I right in saying that a PDA (Or PDA's) can be designed to be as powerful as a cpu?

If you count a CPU (as you imply in your text) as an unbounded memory and the processor, then no you can't model it as a PDA. A push down automaton (with one stack) can only recognize context-free languages, for example $\{a^n b^n c^n | n \geq 0\}$ cannot be recognized by a PDA, but presumably could be recognized by your blue computer with massive graphics card and DVD.

Typically, we think of your blue computer with massive graphics cards and DVD as a Turing Machine, because that often proves to be the best way to model it.

On the other hand, if you model your CPU without unbounded memory, then PDA is still not the right model. If your CPU has no memory or only a small (i.e. bounded) amount of on-chip memory, then it can only be in a finite number of states, and is better modeled as a DFA.


Prove that if for every vertex in $G[U]$ there is an edge in to every vertex in $G[V-U]$ then there is a path from every $u$ to every $v$ Given a connected directed acyclic Graph $G=(V,E)$ and a subset $U\subseteq V$. Prove that if for every vertex in $G[U]$ with out-degree zero there is an edge in $G$ to every vertex in $G[V-U]$ with in-degree zero, then there is a path from every $u\in U$ to every $v\in V\backslash U $.

I thought maybe to try a proof by contradiction- suppose that $u\in U$ and $v\in V\backslash U $ so there isn't a path $u\leadsto v$. Divide to four cases based on the out-degree of $u$ and the in-degree of $v$,
so when the out-degree of $u =$ the in-degree of $v= 0$, it is straight forward contradiction, but with the other case I'm having some trouble.
Maybe there is an easier way to prove the given proposition?

You can use a direct proof. There is no need to assume that the graph is connected.
Take any $u \in U$. We will construct a directed path $u_0\to\cdots\to u_\ell$ in which $u_\ell \in U$ has out-degree zero in $G[U]$, as follows. First, $u_0 = u$. Given $u_i$, if $u_i$'s out-degree in $G[U]$ is zero, then $\ell = i$. Otherwise, let $u_{i+1}$ be an arbitrary out-neighbor of $u_i$. Since $G$ is acyclic, the vertices $u_i$ do not repeat, and so the path must terminate eventually.
Similarly, for any $v \in V \setminus U$ there is a directed path $v = v_0 \gets \cdots \gets v_r$, where $v_r \in V \setminus U$ has in-degree zero in $G[V \setminus U]$. By assumption, there is an edge $v_\ell \to u_r$. Combining both paths with this edge, we obtain a path from $u$ to $v$.


Doubt in definition of closure under concatenation operation in Recursive Enumerative languages I recently started studying theory of computation.

Recusive enumerable language – closed under concatenation. Sir, I have a doubt regarding understanding of this.

Please Note - RE shortform i am taking for Recusively enumerative language

One way --> If L1, and L2 are RE s then L1.L2 is RE then RE is closed under concatenation.

Another way if we talk interms of strings,
If for all ‘a’ belongs to L1 and for all ‘b’ belongs to L2 then w=a.b belongs to L1.L2.

What about the other side? Please see if this is correct?

  For closure under concatenation, If w belongs to L1.L2 then all or some string splits of w into 2 make 1st part acceptance under L1 and 2nd string split acceptance under L2?

I was thinking, as L1 and L2 are REs we can make L1.L2 RE by concatenating L1 and L2 turing machines and make start state as start state of L1 and endstate as final state of L2. But when i am thinking in terms of string input i am getting confused

THe proof in my textbook says that we can non-deterministically split w into 2 parts so that each part accepted by Turing machines for L1 and L2 respectively. If string length is n, then we can have (n+1) kinds of 2 splits of w-string. Will the L1.L2 turing machine accepts all these n+1 types of w-splits? But this is what we need to prove right?

If $L_1,L_2$ are two languages over a common alphabet, then their concatenation is given by
$$ L_1 L_2 = \{ x_1 x_2 : x_1 \in L_1 \text{ and } x_2 \in L_2 \}. $$
If $L_1,L_2$ are r.e. then so is their concatenation. To see this, you can use the following algorithm. Given an input $x$, consider all possible partitions $x = x_1x_2$. For each partition, run a machine for $L_1$ on $x_1$ and a machine for $L_2$ on $x_2$; do this in parallel for all possible partitions. Accept if for some partition $x = x_1x_2$, you find that both $x_1 \in L_1$ and $x_2 \in L_2$.


Your image appears darker because standard RGB is used in transformation, with problem inherent to color - grayscale conversion as standard RGB transformation does not preserve luminance.

Simple modification is to switch RGB channels to color space using perceived luminance: $Y = 0.299*R + 0.587*G + 0.114*B$. That way, luminance and chrominance blurring will not result in darkening or artificial color bleeding.

Color spaces like Y'UV or RGB are non-linear, so make sure to use linear one, say sRGB or any perception-aware/ linear space.

If you can trade speed with accuracy, floating-point box filters are visually better. Given 5x5 blur is tempting, but does not approximate Gaussian Blur accurately enough.

Something is wrong with your code.
Images appears darker by bad color space, but not that much. I took python code found here as it is, and took your image, the result is darker in my opinion, but not visible to the point of shadow dark.

I haven't seen your picture while writing answer but, it seems to me that divisor used is bigger than the sum of cell values.


Calculate the number of cycles of a Cactus graph? Considering a cactus graph $G = (V, E)$, defined as:

  A graph is a cactus if every edge is part of at most one cycle.

There is a way to calculate the number of cycles in this graph given only $n= |V|$ and $m = |E|$?

I did some examples before posting this, but now I think I got somewhere.
If $G$ is connected, $m = n-1$ results that $G$ is a tree (we can not have less as $G$ will be disconnected). If $m > n-1$, then the number of cycles is equal to $m - n + 1$.

If $G$ is not connected, then we can take each connected component $C_{1}, ..., C_{k}$ and deal with them as a separated cactus graphs and then the number of cycles in the original graph is $\sum_{i=1}^{k} cycles(C_{i})$, where $cycles(H)$ is the function described above and $H$ a connected cactus graph.

Intuitively, I think that is because each edge added create exactly one cycle, as adding more than one cycle goes against the definition of the cactus. And to add a edge without adding a cycle you must connect a vertex that was previous isolated, not changing $m - n + 1$.

But I am not sure how to formalize this now.

If a graph is a cactus, then the number of cycles is $c = m-n+x$, where $x$ is the number of connected components and $c$ is the number of cycles.

The proof is by induction on the number of edges. If $m = 0$, then the graph contains no cycles, and furthermore $n = x$, and so $m-n+x = 0$.

Suppose now that $m > 0$, and remove an arbitrary edge $(u,v)$. There are two cases:

The edge was not on a cycle. In that case, removing the edge increases the number of connected components by one: otherwise, $u,v$ are connected by some simple path not involving $(u,v)$, which together with $u,v$ would form a cycle. Therefore by the induction hypothesis, the number of cycles in the new graph is $(m-1)-n+(x+1) = m - n + x$. Since the original graph has the same number of cycles by assumption, this proves the induction hypothesis in this case.
The edge was part of a unique cycle. In this case, removing the edge does not increase the number of connected components, since $u,v$ are connected by the rest of the cycle. By the induction hypothesis, the new graph has $(m-1)-n+x = m-n+x-1$ cycles. The original graph has one more cycle, for a total of $m-n+x$ cycles, proving the induction hypothesis in this case as well.


Confusion regarding the Definition of 2 Way Finite State Automata? Here is a description I read from one of the sources about 2WNFA:

"Unlike ordinary finite automata, a 2DFA needs only a single accept state
and a single reject state. We can think of it as halting immediately when
it enters one of these two states, although formally it keeps running but
remains in the accept or reject state. The machine need not read the entire
input before accepting or rejecting. Indeed, it need not ever accept or reject at all, but may loop infinitely without ever entering its accept or reject state."

I am unclear what it means by: "..The machine need not read the entire
input before accepting."

For example in the automata M = ({qo, ql, q2, q3, q4, q5}, {1}, δ, qo, {q5})
(δ is transition function, L=Left, R=Right) and the transitions being:

δ(q0, 1) = (q1, R);
δ(q1, 1) = (q2, R);
δ(q2, 1) = (q3, L);
δ(q3, 1) = (q4, L);
δ(q4, 1) = (q5);

Does the above 2WNFA, accept any string (example: "1") as the first 4 transitions can be ignored as they bring the machine back to the 1st character in the input string, thus for the last transition to the final accepting state a single 1 is enough? On other hand I think the language it accepts is empty?

Terribly confused because of the bidirection along with above explanation.

Unlike ordinary finite automata, a 2DFA needs only a single accept state and a single reject state.

Finite automata do not need more accepting states. Well, non-deterministic FA don't; just add two final states and appropriate $\varepsilon$-transitions. Deterministic FA, though, need multiple final states; above construction doesn't work, and Myhill-Nerode tells us that we indeed get multiple final states for some languages.

  Unlike ordinary finite automata, a 2DFA needs only a single accept state and a single reject state.

If you add rejecting states to finite automata (an easy enough exercise), neither do finite automata. Consider, for instance,

$\qquad L_0 = \{ w \mid w_1 = 0 \} \cap L$

for any regular $L$. Then, a finite automaton for $L_0$ can reject immediately if the first symbol is not a $0$.

In summary, I think the authors try to read meaning into arbitrary syntactical differences.

That said, note how 2DFA need a rejection state for the stated reason: there is no natural "end of computation".


Does there exist a Turing complete typed lambda calculus? Do there exist any Turing complete typed lambda calculi? If so, what are a few examples?

Yes, sure. Many typed lambda calculi accept only strongly normalizing terms, by design, so they cannot express arbitrary computations. But a type system can be anything you like; make it broad enough, and you can express all deterministic computations.

A trivial type system that encompasses a Turing-complete fragment of the lambda calculus is the one that accepts every term as well-typed (with a top type).
$$\dfrac{}{\Gamma \vdash M : \top}$$

More practically, statically typed functional programming languages have at their core a typed lambda calculus which allows a fixpoint combinator as well-typed. For example, start with the simply typed lambda calculus (or the ML type system or system F or any other type system of your choice) and add a rule that makes some fixpoint combinator like $\mathbf{Y} = \lambda f. (\lambda x. f (x\,x)) (\lambda x. f (x\,x))$ well-typed.
$$
  \dfrac{\Gamma \vdash f : T \rightarrow T}
        {\Gamma \vdash \mathbf{Y}\,f : T}
  \qquad
  \dfrac{\Gamma \vdash f : T \rightarrow T}
        {\Gamma \vdash (\lambda x. f (x\,x)) (\lambda x. f (x\,x)) : T}
$$
The rules as presented above are rather clumsy, as they make terms like $\mathbf{Y}\,f$ well-typed even though their constituents are not well-typed — they are not fully compositional. A simple fix is to add a fixpoint combinator as a language constant and provide a delta rule for it; then it is a simple matter to have a type system and reduction semantics with type preservation. You do get away from the pure lambda calculus into the realm of lambda calculus with constants.
$$\begin{gather*}
  \dfrac{}{\Gamma \vdash \textbf{fix} : (T \rightarrow T) \rightarrow T} \\
  \textbf{fix}\,f \to f (\textbf{fix}\,f) \\
\end{gather*}$$

Sticking to the pure lambda calculus, an interesting type system is the lambda calculus with intersection types.

$$
\dfrac{\Gamma \vdash M : T_1 \quad \Gamma \vdash M : T_2}
      {\Gamma \vdash M : T_1 \wedge T_2}
      (\wedge I)
\qquad\qquad
\dfrac{}
      {\Gamma \vdash M : \top}
      (\top I)
$$

Intersection types have interesting properties with respect to normalization:

A lambda-term can be typed without using the $\top I$ rule iff it is strongly normalizing.
A lambda-term admits a type not containing $\top$ iff it has a normal form.

See Characterization of lambda-terms that have union types for an insight as to why intersection types have such a remarkable scope.

So you have a type system that defines a Turing-complete language (since every term is well-typed), and a simple characterization of terminating computations. Of course, since this type system characterizes normalization, it is not decidable.

A remark on the rule names $(\top I)$ and $(\wedge I)$: they have no formal meaning, but they are chosen deliberately. the $I$ stands for “introduction”, because these are introduction rules — they introduce the symbol ($\wedge$ or $\top$) into the type below the line. Dually, you'll find elimination rules, when a symbol appears above the line but not below. For example, the rule to typecheck a lambda expression in the simply-typed lambda calculus is the introduction rule for $\rightarrow$, and the rule to typecheck an application is the elimination rule for $\rightarrow$.


Elegant approach to finding largest $n$ such that $n\lg(n) \leq 10^6$ I'm studying CLRS, and solving problems listed after each chapter. I'm curious about problem 1-1. That is right after Chapter 1.

The question is, what is the best way to find the largest integer $n$ such that $n \lg(n) \leq 10^6$.

The simplest but the longest one is substitution. Are there some elegant ways to solve this?

Some explanations: $n$ is what I should calculate - total quantity of input elements, $10^6$ - time in microseconds - total algorithm running time. I should figure out $n_{\text{max}}$.

We just solve $x \log x = 10^6$ and round down. This sort of equation typically does not have a closed form solution (so what, closed form solutions are so 18th century, we've got computers now), so we just feed this into a computer and we get $n \approx 87847.5$, so the answer is 87847.

You did ask for the most elegant approach, you know, and that would be to use the right tool.

Now, you could also wonder how you would compute this by hand if you found yourself in the middle of a jungle. You could use the iteration method (is this what you called substitution?). Write the equation in the form of a fixed point:
$$x = \frac{10^6}{\log x}$$
Start with any initial guess for $x$ and keep applying the right-hand side. With some luck, you converge. You find a python in the jungle and make it compute:

>>> import math
>>> x = 42
>>> for i in range(20):
...    print x
...    x = 1000000.0/math.log(x)
...
42
267546.386419
80018.8957423
88573.8173924
87784.0460781
87853.1196966
87847.0493964
87847.5826391
87847.5357949
87847.5399101
87847.5395486
87847.5395803
87847.5395775
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778

That was kind of slow. A better method would be Newton's method. We are looking for the root of $f(x) = x \log x - 10^6$. The derivative is $f'(x) = 1 + \log x$ so the Newton's method step is
$$x_{n+1} = x_n - \frac{f(x_n)}{f'(x_n)} = x_n - \frac{x_n \log x_n - 10^6}{1 + \log x_n}.$$
So now we get:

>>> x = 42
>>> for i in range(10):
...     print (x)
...     x = x - (x * math.log(x) - 1000000.0)/(1 + math.log(x))
...
42
211083.102152
91333.5177989
87852.9643949
87847.5395913
87847.5395778
87847.5395778
87847.5395778
87847.5395778
87847.5395778

Much better.


Why is Ibarra Kim for 0/1 knapsack an fully polynomial time approximation scheme (FPTAS)? According to one of my CS lectures, there is an fully polynomial time approximation scheme for the 0/1 Knapsack problem. A first version was developed by Ibarra and Kim, but there are several improved versions.

Also according to my lecture, an approximation scheme is called "fully polynomial time approximation scheme (FPTAS)", if its run time is polynomial in $1/\epsilon$ and polynomial in the encoding length of the instance (usually, the input size is denoted by $n$, such that the encoding length would be $\log n$).

The algorithm has running time $\mathcal{O}(n\log(n))+\mathcal{O}(n + (1/\epsilon)^2)$. I do agree on this being polynomial in $1/\epsilon$, but how is it polynomial in the encoding length of $n$?

The part $\mathcal{O}(n\log(n))$ of the run time is due to sorting the list of $n$ items. As far as I'm capable of judging this, this is polynomial in $n$, but not polynomial in $\log n$.

Where am I wrong?

The input to 0/1 knapsack is a list of $n$ items each with a weight $w_i$ and value $v_i$ with knapsack size $W$ and maximum value $V$.  Thus the input list has size $O(n (\log W + \log V))$.

So $n \log n$ is polynomial in the input.

The problem with the traditional dynamic programming solution of knapsack is not that it is exponential in $n$, but that it is polynomial in $W$ (or $V$), which makes it exponential in $\log W$.


NFA corresponding to the regular expression α = (a*b | ϵ) (b*(a | ϵ)) I'm currently studying for an upcoming exam in theoretical computer science, but one of the exercises is confusing me: in the exercise sheet it says that the NFA $$M=(\{z_0,z_1,z_2\},\{a,b\},\delta,\{z_0,z_1,z_2\},\{z_2\})$$ corresponding to the regular expression $\alpha=(a^*b|\epsilon)(b^*(a|\epsilon))$ is defined by
$$\begin{array}{c|ccc}
\delta&z_0&z_1&z_2\\\hline
a&\{z_2\}&\{z_1\}&\emptyset\\
b&\{z_0\}&\{z_0,z_2\}&\emptyset
\end{array}$$
where $\delta$ is the transition function.

I don't understand how this can be right - if I'm not mistaken, the word $bb$ is an element of $L(\alpha)$ but it's not an element of $T(M)$.

So... basically, my question is: is the exercise sheet flawed or am I misunderstanding the concept of regular expressions?

I think the inner pair of parentheses is out of place - without this pair of parentheses, we get the regular expression
$$\alpha=(a^*b|\epsilon)(b^*a|\epsilon),$$
which seems to satisfy $L(\alpha)=T(M)$... can anyone confirm this? (Sorry, I'm a beginner.)


Byzantine generals problem with signed messages (Lamport) I have some trouble understanding Lamport's paper about the Byzantine generals problem when it comes to signed messages. He showed that, with signed messages, the number of generals must be at least $m+2$ to tolerate $m$ malicious units\faults (for fewer generals, the problem is vacuous).If that's fulfilled it's guaranteed that the loyal generals make the same decision.

Now, I read a lot of papers where at least $2m+1$ generals are needed. The argument in these papers is that the loyal generals have to outnumber the malicious ones to make a majority vote (to get not only the same but the right result). But why isn't it sufficient to have $n \ge m+3$ with three loyal generals for majority vote?

Moreover, if $2m+1$ generals are needed for the majority vote, how can that work with three generals and one traitor? In both cases I need $m+2=3$ and $2m+1=3$ generals and (from what I understand) then I can only agree on the same but not on the correct value (majority vote with two loyal entities?).

I know that I have an error of reasoning here, but I really don't get it. Maybe someone can help me with that problem?

Maybe this is what confuses you -- mixing the byzantine agreement problem (broadcast: where there is one transmitter and multiple receivers) and the byzantine consensus (where every party starts with an input, and if all have the same input, this should also be their output). The bound of at most half traitors stems from the consensus requirement.

Say we have $n$ generals, out of which $t$ are traitors and $\ell=n-t$ are loyal. Assume general $i$ holds the input bit $b_i$

Now assume they all perform a distributed majority vote protocol. Is the protocol guaranteed to succeed?
This questions is actually not a well defined. The success of the protocol can be interpreted in two different ways:

All loyal generals output the same answer: $MAJ ( b_1, \ldots, b_n)$
All loyal generals output the same answer: $MAJ (L)$ where $L=\{b_i \mid $ general $i$ is loyal$\}$.

Note that using Lamport's result you mentioned, if $n>t+2$ then all the loyal parties are guaranteed to output the same output even if the traitors misbehave and don't follow the protocol, but which output do they output? Assume $\ell=3$ as you suggest, and assume they all hold the input $0$. The "traitors" can still force the loyal generals to output "1": they just set their input to $1$ and behave honestly! Remember that the loyal parties don't know who is loyal and who isn't (or even if there are traitors at all -- maybe everyone is loyal). From their point of view, there are $t$ votes for "1" and only 3 votes for "0", and since everybody behaves as supposed by the protocol -- the output must be 1! This suits interpretation number (1) above.

Thus, interpretation number (2) above makes sense only for the case where  setting the input of the traitors does not affect the majority.
A special case is the consensus problem: if all the $\ell$ parties hold (say) "0", we want to guarantee that they all outputs a 0. Of course, if $t>\ell$ then the simple "attack" described above will work. So we need $t<\ell$, or equivalently, $$n=t+\ell \ge t+(t+1)=2t+1.$$

In the most general case of byzantine major-vote,
the loyal parties may be split
(e.g., $\lfloor \ell/2\rfloor$ votes vs. $\lceil \ell/2\rceil$ votes). In this case, even a single traitor (playing honestly) can determine the result by himself.


Can Reduction for Undecidability/Decidability Problems Go Both Ways? This Problem sparked my question:
Does a TM $M$ enter state $q$ on input $w$?

I proved it was undecidable in this format using the Halting Problem as a subroutine:

If HALT
    simulate M on w and return result
 else
    return false

Since HALT is undecidable, this given problem is undecidable as well.

However, the given solution proved in the opposite way, by creating a decider for the problem, and using it as a subroutine to solve the Halting Problem.

Is my direction of the proof still valid, and can my approach be used to prove other undecidable problems (using a known undecidable problem as a subroutine rather than the other direction)?

When proving decidability of a new problem, you reduce the new problem
(i.e. a problem with unknown solution) to an old one (used as
subroutine) with a known solution, so that the techniques used to
solve the old one can be used to solve the new one.

But, when proving undecidability, you have to do the opposite. You
reduce the old problem, known to be undecidable, to the new problem
(used as subroutine), in such a way that, if the new problem has a
decision procedure, its use as a subroutine provides a decision procedure to the old
problem, known not to have any. Hence the new problem cannot have a
solution, and is undecidable.

In your example, you should have tried to show that if you have a
decision for your new problem, that you can use as subroutine, then
you ave a decision for the halting problem, which is not possible.

So proofs go both ways only in the sense that the contrapositive of a statement goes the other way. Decidability goes one way, and undecidability goes the other way.

However, it you can do the reduction both ways at the same time (either both for decidability or both for undecidability), then you have proved that the two problems are strictly equivalent, and that any solution for one is a solution for the other. When it goes only one way, this establishes that one problem is harder than the other (letting you work out which is which).

I guess that is about all I can say about the "direction"of the proof.


Is a subtree of a minimum spanning tree a minimum spanning tree of the subgraph spanned by the subtree? Let $G$ be a connected weighted undirected graph. Let $T$ be a minimum spanning tree (MST) of $G$. Consider removing an edge $e=(a,b)$ from $T$, which will give two subtrees $T_a$ and $T_b$, where $Ta$ contains the vertex $a$ and $T_b$ contains the vertex $b$. Now consider the subgraph of $G$, $G_a$, which contains the vertices of $G$ that are in $T_a$, and the edges of $G$ that have both endpoints in $T_a$.
Is $T_a$ an MST for the subgraph $G_a$?
Intuitively, I believe $T_a$ is an MST for the subgraph $G_a$, but I'm having a lot of difficulty proving the result.

Let’s prove this by contradiction. Say $T_a$ is not an MST of $G_a$, that means there is some cheaper MST $T_a^*$. However, if that were true, then by reconnecting $T_a^*$ to $T_b$ we would obtain a tree that spans $G_a$ that has a lower weight than the MST $T$, which is a contradiction.


reduce reduce and shift reduce error in LALR grammar I have to write a grammar for Pascal, and there is just one thing that is causing problems.

Lets say we have operators (sorted by priority from low to high):

Postfix ^.
Prefix ^.
[ ], and ., (same priority and left associative).
The only terminal is id, which is any lowercase letter.

Now let's say that an expression is:

Any id.
Any expression with the Postfix ^ operator.
Any expression with the Prefix ^ operator.
Any expression with . followed by id.
Any expression with [ and another expression and ].

Now I would like to know how can I make a LALR grammar without shift-reduce and reduce-reduce conflicts, OR if that can't be done how can I prove that it can't be done.

Some examples:

good:
a.b.c.d
a.b^.c
^a.b^
a.b^^[c]^^.d.e
^^a.b^.d.e^[]

bad:
a.^b.c

Without the prefix ^, this problem is easy to solve, but the prefix sign keeps getting me. Can anyone help? My solutions so far:

// this works without the prefix but it does not produce a.b^.c which is wrong.
A ::= B | A ^ ;
B ::= C | ^ B ;
C ::= id | C [ A ] | C . id;

So I thought that the prefix can only occur before the first dot, and between dots, there can only be a postfix ^ and brackets. So I came up with this:

A ::= B | A ^ ;
B ::= C | ^ B ;
C ::= id | C [ A ] |id D;
D ::= id E;
F ::= E | F ^;
E ::= id | F . id;

But this causes 3 conflicts.

I don't see any problem with your first grammar and bison doesn't complain on the rendering I've done of it.

I (and bison) see one conflict in your second grammar (which doesn't describe the same language as the first BTW). After having seen id id id with a pending ^, you don't know if your last id and the ^ should be an F, or if you should keep together the three id forming an A which will be gathered with the '^'.

Edit after your comment:

A direct rendering of your rules:

EXP ::= id | EXP ^ | ^ EXP | EXP . id | EXP [ EXP ]

will be ambigous — and thus have conflict(s) — because you don't state if the prefix version of ^ has priority over the other (postfix) operators. I don't remember how it was in Pascal, but you can get both effects with

EXP ::= POST | ^ EXP
POST ::= id | POST ^ | POST . id | POST [ EXP ]

and

EXP ::= PRE | EXP ^ | EXP . id | EXP [ EXP ]
PRE ::= id | ^ PRE

Edit again: a mixed version corresponding to my understanding of what you ask in the comment (I continue to find this confusing and I consider the complexity of the grammar — with post operators given twice — as a hint it is so :-) )

EXP ::= PRE | POST2
POST2 ::= PRE '^' | POST2 '^' | POST2 '.' id | POST2 '[' EXP ']'
PRE ::= POST | '^' PRE
POST ::= id | POST '.' id | POST '[' EXP ']'


Proving NP-completeness for a not so cheesy problem Let's say we have a matrix M[1..B, 1..B] (i.e., a square matrix) and a mouse in the upper left corner (1,1). We also have an integer A, which tells how many pieces of cheese there are in the matrix. The mouse can move from a given positon (i, j) either in the direction (i+1, j) or (i, j+1). When the mouse visits a given position (i,j), it collects all the given cheese immediately, so if it decides to return to an already visited position, it will already be empty. Additionally, the mouse can ONLY reverse/back ONCE when traversing the matrix, because we can assume that this mouse doesn't particularly like to change its mind.
So given all these prerequisites, the question is whether or not it is possible for the mouse to collect exactly A pieces of cheese, starting from the position (1,1) and ending up in the position (B,B)?
There should be a proof that this problem is NP-complete by showing it is in NP and by reducing the NP-complete problem Subset Sum.
For showing it is in NP I was thinking about maybe looping through the whole matrix and counting the total number of cheese and then maybe have some sort of boolean condition to check whether or not the amount of cheese the mouse has collected equals to the total amount of cheese located in the matrix and that this will take polynomial time to do. However, I am not sure this is the right way to do and I am even more unsure of how to reduce Subset Sum to this problem. Thus, I am grateful for your help and advice!

The problem is in $NP$ since a certificate is the path itself, which has length at most $2B-1 + 2 = 2B+1$.
Given an instance $\langle S, k\rangle$ of subset sum where $S = \{x_1, \dots, x_n\}$ is a set of integers and $k$ is the target value, you can create an instance of your problem by choosing: $B=n+2$, $M = \mbox{diag}(0, x_1, x_2, \dots, x_n, 0)$, and $A = k$.
Clearly any path in $M$ that collects $A$ pieces of cheese implies the existence of a subset $S' \subseteq S$ such that $\sum_{x_i} x_i = A = k$.
On the converse notice that, given any $S' \subseteq S$ satisfying $\sum_{x_i} x_i = k$, it is possible to find a path $P$ in $M$ with the sought constraints (actually, backtracking is not even required) that traverses $M[i+1, i+1]$ if and only if $x_i \in S'$. This shows that pieces of cheese collected by $P$ are exactly $k=A$.
Also notice that your problem can be solved by pseudopolynomial-time dynamic programming algorithm having complexity $O(A \cdot B^2)$.


Analysis of Pan-cake sorting i was implementing pan-cake sorting. We can implement it by taking largest element to start and flipping it recursively (Like selection sort).

However it is mentioned that the A[i]  has to be a permutation of [1, 2, ..., A.length].

My question is, what if A[i] is not a permutation of [1,2,..., A.length]?
How to solve that?

Let's suppose the input array is $A = [3,1,4,5,2]$.  When sorting this array using pancake sorting, only flips of prefixes of the array are allowed.  Flipping the first four elements, i.e. replacing $3145$ by $5413$, gives $A = [5,4,1,3,2]$. Then, flipping all five elements gives $[2,3,1,4,5]$, which brings the largest element to its correct position.  By repeating this process to bring the next largest element to the last-but-one position, and so on, the array can be sorted.

The number of flips required to sort an array of length $n$ is at most $2n-3$. This is because bringing the largest $n-2$ elements to their correct positions can be done using at most $2n-4$ flips (because at most two flips are required for each element, as mentioned in previous paragraph).  Finally, the elements in the first two positions can be sorted using at most one flip.

The problem of finding the minimum number of flips to pancake-sort an array is still open.


how to bound the probability that quicksort takes greater than n lg n time? I am working on exercise 12.4-5 of CLRS (Cormen et al, Intro to Algorithms 3rd ed)

  Consider RANDOMIZED-QUICKSORT operating on a sequence of n distinct input numbers. Prove that for any constant k > 0, all but O(1/nᵏ) of the n! input permutations yield an O(n lg n) running time.

By RANDOMIZED-QUICKSORT, they simply mean quicksort with the pivot randomly selected from interval being partitioned, as opposed to always being chosen as, say the last element or something.

A previous thread on this same question had a single answer, which consisted entirely of a dead link plus a working link that leads to a set of (in my opinion) poorly-written notes for an undergraduate class, that does not answer the question, only having a very brief discussion of a particular case of quicksort with n ≈ 20.

I'm not even sure how to rigorously pose the question; my best shot is this:

  Prove that for any k > 0, there exists positive constants a, b, and n₀ such that for all n > n₀, the probability that RANDOMIZED-QUICKSORT makes more than a n lg n comparisons is less than b /nᵏ:

A similar problem appears in Knuth's The Art of Computer Programming vol 3, Sorting and Searching, as problem 42 on page 137 (with some minor notational edits for clarity):

  For any real number c > 0, prove that the probability is less than exp(-c) that quicksort will make more than (c + 1)(n + 1)H comparisons when sorting random data, where H = 1 + 1/2 + 1/3 ... 1/n. (This upper bound is especially interesting when c is, say, nʰ, where h is small and positive).

The solution to this problem is given at the end of the book, and consists only of the following:

  This is a special case of a general theorem due to R. M. Karp, see JACM 41 (1994), 1136-1150, section 2.8. Significantly sharper asymptotic bounds for tails of the quicksort distributions have been obtained by McDiarmid and Hayward, J. Algorithms 21 (1996), 476-507.

I hunted down the Karp paper, and it indeed proves the result from the Knuth problem.

While CLRS seemingly refers to Knuth for a great deal of the former's material, it seems to be that the result that CLRS is asking us to prove is actually stronger than the result in the Knuth problem. In particular if we take the parameter c in Knuth's result to be any c(n) = ω(1), e.g. even something extremely slowly growing like c(n) = ln ln ln n, then the Karp result says that the probability is less than exp[-c(n)] that quicksort will make more than [c(n) + 1](n + 1)H comparisons. Since H = Θ(lg n), this number is Θ[c(n) n lg n], and since we have defined c(n) = ω(1), this number is ω[ n lg n ], with maximum generality. However, with the choice c(n) = ln ln ln n, the upper bound of the probability is exp[-c(n)] = 1 / ln ln n, which is a much weaker upper bound than what CLRS is asking for: less than O(1/nᵏ) for any constant k > 0.

My questions are the following: is my interpretation of the CLRS question (the quoted block above, immediately after I say "my best shot is this") correct? If not, what, specifically, is CLRS actually asking us to prove? Also, what is the relationship between the CLRS question and the Knuth question? Is the Knuth result weaker than the CLRS result? If so, does the  CLRS result draw on more recent published research than the 1994 Karp paper cited in Knuth's "answer"?

Also, some further relevant reading: the McDiarmid paper that Knuth's answer points to cites a 1991 paper by Rosler, who showed that

$$
\Pr\left[\left|\frac{Q_{n}}{E[Q_{n}]}-1\right|>\varepsilon\right]=O\left(\frac{1}{n^{k}}\right)
$$

where $Q_n$ is a random variable indicating the number of comparisons made by quicksort on an input of size $n$, $\varepsilon$ is a fixed constant, and $k$ is any positive real number. It seems likely that this is the source of the result asked for in the original CLRS problem, although the formulation of the probability in the above equation does not seem extremely obviously equivalent to the CLRS phrasing.

The exercise is extremely poorly worded. The problem is that Randomized-Quicksort is a randomized algorithm, and so it doesn't have a "running time", or rather, its running time is a random variable. I suspect that this is a typo, and that the intension was to analyze the deterministic Quicksort algorithm. Assuming this correction, here is a more formal version of the exercise:

  Show that for all $k > 0$ there exist constants $a_k,b_k$ such that for all $n$, there exists a subset $S \subseteq S_n$ (where $S_n$ is the set of all permutations of $1,\ldots,n$) of size at most $(a_k/n^k) n!$ such that for all $\pi \in S_n \setminus S$, the running time of Quicksort on $\pi$ is at most $b_k n \log n$.

In order to prove the exercise, presumably you need to use material from Theorem 12.4, which states that the expected height of a randomly built binary search tree of size $n$ (formed by choosing a random permutation in $S_n$ and adding the elements to a binary search tree in that order) is $O(\log n)$. You then argue roughly as follows:

When running Quicksort on a permutation in $S_n$, the running time is $O(nh)$, where $h$ is the height of the binary search tree formed from the permutation.
The argument of Theorem 12.4 can be strengthened to show that for each $k>0$ there exist $a_k,b_k$ such that when constructing a random binary search tree, the probability that the height exceeds $b_k \log n$ is at most $a_k/n^k$.
Putting the two ingredients together yields the problem.


Length of the certificate in complexity classes A nondeterministic machine trying to decide membership in a language
  is presented with a hint (called a "witness" or "certificate") which
  proves membership (no such witness is provided for elements outside
  the language; the definition is asymmetric).

So, if a non-deterministic algorithm can solve a problem in O(f(n)) time, does this mean the length of the certificate is f(n) [Since it could try all the possible combinations and the length of the shortest one will be f(n)]? And the input size is n?

Also, if a deterministic algorithm A exists that can verify a certificate in O(f(n)) time, how does this imply the existence of a non-deterministic algorithm that can solve the problem in O(f(n)) time?

I'm a little confused by your quote.

There are two equivalent definitions of the NP complexity class in terms of Turing Machines:

The class of problems for which a deterministic verifier exists whose runtime is bounded by a polynomial in the size of the problem input.
The class of problems for which a nondeterminstic decider exists whose (nondeterministic) runtime is bounded by a polynomial in the size of the problem input.

So a nondeterministic machine trying to decide membership in a language wouldn't be presented with a certificate; that's not what it means to decide membership in a language. It's the deterministic verifier that gets a certificate - a verifier over language L is a decider over the language of pairs of an element of L and a certificate proving the element in L (that's why the definition is asymmetric and there's no certificates for non-membership; the verifier only answers "yes this is an element of L together with a certificate for this element", or "no this is either not an element of L or not a certificate for this element").

That aside, on to your questions.

If the running time of the verifier in O(f(n)), then the certificate (in general) is also in O(f(n)). It's possible the verifier needs to read the whole certificate and then do some trivial computation with it that doesn't increase the big-oh complexity over the time needed to simply read the certificate. Particular verifier algorithms for particular problems may well have much shorter certificates (implying that their runtime is occupied with much more computation than simply reading the certificate). But you can't say anything in general about an unknown verifier's certificate length just from knowing its runtime (well, anything more specific than that it's certificate length bound must be short enough to be read within its run time bound).

You also ask about how the existence of a deterministic verifier for a problem implies the existence of a nondeterministic decider for the same problem. The implication actually goes both ways (which is why the two definitions of the NP complexity class are equivalent).

Given a deterministic verifier you can construct a nondeterministic decider. The verifier is a decider over the language <e, C(e)> (where e is an element of L and C is a function that computes a certificate for e). The machine we're trying to construct will be given e as input. If it could come up with C(e) it could simply run the verifier on the pair and it would have its answer.

But our decider has the advantage of nondeterminism. It can simply guess a value for C(e) and run the verifier, and nondeterminism implies that if there is such a value that leads to acceptance then the machine will have picked the correct one. The "guessing" can be (almost) implemented by having a state that nondeterminsitically writes a symbol from the alphabet (any symbol) on the current cell, moves the tape head right, and then nondeterministically chooses to remain in the same state or to move on to the verifier stage.

Since the certificates must be within O(f(n)) length, and all we do before running the verifier is write down the certificate, the runtime of this machine on an e that is in L is O(f(n)) + O(f(n)), which is simply O(f(n)).

The only catch is that if e is not in L, then there is no such C(e) that will lead to the verifier accepting. But we can't let our machine keep trying longer and longer guesses for C(e); our machine is a decider, so it is required to halt for all input. The machine needs to know when to give up; it must only be capable of generating a finite number of guesses for C(e).

This means that machine must be able to calculate an upper bound to the length of C(e), and only guess strings up to that length. This means that the upper bound has to be a total computable function of e. I'm not 100% certain if that's possible in general for verifiers with completely arbitrary runtime complexity O(f(n)), because f might not be a computable function, and the exact certificate length can be larger than f(n) because of the details big-oh notation abstracts away from (constants, lower-order terms, and the fact that the bound only has to apply for sufficiently large n; maybe someone who knows a bit more can add something here). But for verifiers with polynomial big-oh complexity, there always exists a polynomial in n which is strictly larger than the minimum certificate length for any e with length n.

So we can presume the existence of a nondeterminstic machine which for an element e of length n, calculates this upper bound, guesses any string whose length is within the bound, and runs the verifier on it. Since guessing a string within a polynomial bound takes at most polynomial time, and the verifier had a polynomial run time bound, and the sum of two polynomials is still a polynomial, the nondeterministic decider always halts within a polynomial bound.

The other direction (the existence of a polynomial nondeterminsitic decider implies the existence of a polynomial deterministic verifier) is much easier. Let the certificate for any e in L simply be a record of all the transitions used by the nondeterministic decider when processing e. All the verifier has to do is check that this record forms a valid path through the nondeterministic decider leading to an accept state. Since checking this doesn't require exploring all the nondeterministic possibilities, a deterministic verifier can do this with overhead of a constant multiplier over the nondeterministic decider's runtime (it only needs to check each transition against the decider's set of possible transitions, which is a constant).

I've answered a slightly weaker question than you asked, however. I've only shown that you can come up with a decider for verifiers with a polynomial runtime bound (although similar reasoning applies to exponential bounds, and most other functions that actually get used very often when talking about big-oh complexity). I also haven't shown that a verifier with runtime in O(f(n)) implies the existence of a decider with runtime in O(f(n)), even for polynomial f; all I've shown is that if the runtime bound of the verifier is a polynomial then the runtime bound of the decider is still a polynomial; it might be larger one. I don't actually know whether a verifier always implies a decider with the same runtime bound; I'd welcome an addition from someone who knows for sure either way.