Efficiently compute parallel matrix-vector product for block vectors with FFTs? Assume I have $P$ processors, each having a different vector $v_p$ of size $N$, $p=1, ..., P$. I learned in this question/answer that for computing the matrix-vector product
$$w = (E\otimes I_N)v$$
in parallel, where $\otimes$ is the Kronecker product, $v = (v_1, ..., v_P)^T$ is the stacked vector consisting of all local vectors $v_p$, $E = (e_{pj})_{p,j}\in\mathbb{C}^{P\times P}$ some dense matrix and $I_N$ is the identity matrix of size $N\times N$, I can basically do $P$ parallel sums using binary trees.

$N$ is pretty large (say, $10^8$), in particular much larger than $P$ (which is only 10-100) and so large that $NP$ (the size of $w$ and/or all vectors $v_p$ together) does not fit into each processor's memory.

Depending on the application, the matrix $E$ could be a Fourier or DFT matrix, i.e. computing
$$w_p = \sum_{j=1}^P e_{pj} v_j$$
should be possible using an FFT. For each of the components of the vector $v_j\in\mathbb{R}^N$, the FFT would not change. Do I still have to do $N$ FFTs or is there a "block-wise" FFT idea/implementation?

Let's look at the case where $P=2$, for starters.  The FFT can be computed in a divide-and-conquer fashion, where first we compute the FFT of the even-numbered indices, then the FFT of the odd-numbered indices, and then combine them in a simple step (with a single layer of butterfly operations).

So, if the even-numbered indices are stored on one processor and the odd-numbered indices are stored on a second processor, then you could do this in parallel in a natural way, with the first processor doing the FFT on its own data, and the second processor doing the FFT on its own data; the final butterfly step requires only $\Theta(NP)$ data sent over the network.

If the data isn't partitioned that way, then the first step could be to send all the values at even-numbered indices to the first processor and the values at odd-numbered indices to the second processor, then do the above process.  In total it will require $\Theta(NP)$ data sent over the network and $\Theta(N \lg N)$ computation ($\Theta(N \lg N)$ computation at each processor to compute the FFT locally).

More generally, if $P$ is a power of 2, you can generalize these ideas in a similar fashion.  You send the data to the appropriate processor   ($\Theta(NP)$ data sent over the network), then compute the FFT locally at each processor ($\Theta(N \lg N)$ steps of computation at each processor), then combine them with $\lg P$ butterfly layers (requires $\Theta(NP \lg P)$ data sent over the network).

If $P$ isn't a power of two, you can pick the largest power of two that is smaller than $P$, and use that many processor (the remainder are left idle).


Minimal DFA with more states than its equivalent NFA I understand that using a bad case for subset construction as provided through an example in the book -  Introduction to Automata Theory, Languages and Computation, we can definitely have an NFA with $n+1$ states, and get a corresponding minimal DFA with $2^n$ states due to the power set logic.

But, my question is, is there a case where you can have an NFA  (with or without epsilon moves), with $n$ states, having an equivalent minimal DFA of $p$ states, where $p \neq 2^n \ and \ p > 2n$ ?

Consider the language $(0+1)^*0(0+1)^{n-1}$ over the alphabet $\{0,1,2\}$. It is accepted by an NFA having $n+1$ states, and its minimal DFA contains $2^n+1$ states.


Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem? Is there any advantage of using an Integer Linear Program over Backtracking in a combinatorial optimization problem?

I saw this Gurobi post that uses Integer Linear Programming to solve the traveling salesman problem.

I compared its runtime with a Backtracking algorithm written in python, and the Integer Linear Program seems to be faster?

Is the Integer Linear Program faster because Gurobi is implemented in C++ or is it faster because it uses heuristics, pruning and other optimizations to improve its runtime?

Integer linear programming can potentially be more efficient.  ILP solvers normally combine backtracking with many other methods, so for many problems ILP might be faster than backtracking alone.  There are no hard-and-fast rules about which will do better on every problem, though.  It's not just implementation in C++.


How to prove $\{ a^ma^lcb^{m+l}\mid m,l \in N \}$ is not regular using the Pumping Lemma? I need some help with my proof, because I'm not sure if the following works. Tips and Tricks are welcome since this topic is completely new to me and very difficult.

Task:
Prove that $M = \left\{ a^ma^lcb^{m+l}\mid m,l \in N \right\} $ with $\sum =\left\{ a,b,c \right\}$ is not a regular language using the Pumping Lemma.

Here is my try:
First of all I would like to write  $M= \left\{ { a }^{ m }{ a }^{ l }c{ b }^{ m+l }\mid m,l \in N \right\} $ as $ M = \left\{ { a }^{ 2n }c{ b }^{ 2n }\mid n \in  N \right\} $. Is this possible?

Proof:
Let $n\in N$ be fixed. Choose the word $w = { a }^{ 2n }c{ b }^{ 2n }\in M$ with $|w|\ge n$. Let $w=xyz$ be a decomposition with $y\neq \lambda $ and $|xy|\le n$. Then we have $x={ a }^{ 2i }$, $y={ a }^{ 2j }$ and $z={ a }^{ 2n-2i-2j }c{ b }^{ 2n }$ for $j\neq 0$ and $2(i+j)\le 2n$.

We choose $k=0$. Then we have $x{ y }^{ 0 }z = {  a }^{ 2n-2i }c{ b }^{ 2n }$. $\Longrightarrow x{ y }^{ 0 }z\notin M$ because $2n-2i\neq 2n$ for $j\neq 0$.
$\Longrightarrow$ M is not a regular language.

First of all I would like to write  $M= \left\{ { a }^{ m }{ a }^{ l }c{ b }^{ m+l }\mid m,l \in N \right\} $ as $ M = \left\{ { a }^{ 2n }c{ b }^{ 2n }\mid n \in  N \right\} $. Is this possible?

We have $a^ma^\ell cb^{m+\ell}=a^{m+\ell}cb^{m+\ell}$ so you can certainly write that as $a^ncb^n$ for some $n\geq 2$. But you can't write it as $a^{2n}cb^{2n}$ because $m+\ell$ isn't necessarily even.

The question originally contained a typo, as follows. I've kept my answer to that version of the question because it illustrates a common mistake, so will probably be useful to somebody.

  First of all I would like to write  $M= \left\{ { a }^{ m }{ a }^{ l }c{ b }^{ m+1 }\mid m,l \in N \right\} $ as $ M = \left\{ { a }^{ 2n }c{ b }^{ 2n }\mid n \in  N \right\} $. Is this possible?

No, you can't do that. Let $M=\{a^ma^\ell cb^{m+1}\mid m,\ell\in\mathbb{N}\}$ and $M'= \{a^{2n}cb^{2n}\mid n\in\mathbb{N}\}$. Any $a^{2n}cb^{2n}\in M'$ can be rewritten as $a^{(2n-1)}a^1cb^{(2n-1)+1}\in M$ (i.e.,  we can set $m=2n-1$ $\ell=1$), so $M'\subseteq M$.  However, take $m=2$, $\ell=1$ and we get $a^3cb^3\in M$, but this string is not in $M'$, which means that $M'\neq M$.

You've tried to prove that $M'$ is non-regular but that doesn't prove that $M$ is non-regular. For example, pick your favourite non-regular language $L$ over your favourite alphabet $\Sigma$. $L\subsetneq\Sigma^*$ but the fact that $L$ is non-regular certainly doesn't mean that $\Sigma^*$ is non-regular!

  Proof.

Your proof that $M'$ is non-regular is basically correct except for two small mistakes. First, you can't assume that $x$ and $y$ have even length: they need to have length $i$ and $j$, rather than $2i$ and $2j$. Remember that you need to show that every partition of the string as $xyz$ fails the pumping property, not just the ones where $x$ and $y$ have some particular property. Second, in your sentences about $xy^0z$, some of the $i$s should be $j$s.


Convertion from NFA to DFA I have converted nfa to dfa. But when I checked with some examples, it looks like it is wrong.

This is the full question.
Convert the nfa defined by
δ(q0, a) = {q0, q1}
δ(q1, b) = {q1, q2}
δ(q2, a) = {q2}
δ(q1, λ) = {q1, q2}
with initial state q0 and final state q2 into an equivalent dfa.

First, I made a table.

             a          b
ɸ            ɸ          ɸ
{q0}         {q0,q1}    ɸ
{q1}         ɸ          {q1,q2}
{q2}         {q2}       ɸ
{q0,q1}      {q0,q1}    {q1,q2}
{q1,q2}      {q2}       {q1,q2}
{q0,q2}      {q0,q1,q2} ɸ
{q0,q1,q2}   {q0,q1,q2} {q1,q2}

Finally, I have drawn dfa according to table above.

The bold line is accepting state.

Thanks for your help/

It looks like you have 3 symbols in your language: a, b, and \lambda.  But your transition table only has the symbols a and b.  You need to add \lambda to your transition table and integrate that into your diagram.  That should help some.


basic turing machine I'm trying to create a TM that changes all $a$'s to $b$'s and all $b$'s to $a$'s in a given string and then halts on the first blank space it encounters. What I have is:

$$ \langle q_1,a,b,q_1\rangle \\
\langle q_1,b,R,q_2 \rangle \\
\langle q_2,a,L,q_1 \rangle \\
\langle q_2,b,a,q_2 \rangle \\
$$

I'm new to Turing machines, so I'm wondering if it makes sense to convert $a$'s to $b$'s and then send $b$'s into a different state; is there a sort of temporal sequencing here that will send the $q_1$-manufactured $b$'s (former $a$'s) into $q_2$ as well? If so, how can you get around this problem to construct a suitable machine?

Using your convention that the machine EITHER changes symbol OR moves Left/Right, then this is the machine you are looking for:

<q1,a,b,q2>
<q1,b,a,q2>
<q2,a,R,q1>
<q2,b,R,q1>

In other words, the machine alternates between the 'switch the letter' state and the 'move right' state.  [I am adopting the convention that the absence of a transition - say on space - is equivalent to halting; otherwise one needs another transition to cover that]


How to mathematically prove that a relation T(n)=T($\sqrt{n}$)+c is O(log(log(n))? following question, I understood the intuition behind how cutting down the size of input by square root on each iteration leads to O(log(log(n))) complexity.

I tried to derive it on paper.

Let T(n) = T($\sqrt{n}$) + c
$\implies$ T($n^{1/2}$)+2c
$\implies$ T($n^{1/4}$)+3c
$\implies$ T($n^{1/8}$)+4c
$\implies$ T($n^{1/16}$)+5c
.....upto n > 1

I noticed that the power of n becomes 1/2 times the last value.

How should I proceed from here on?
I need to derive that T(n) is O(log(log(n))).

Let $x = \log n$ and $Q(x) = T(2^x)$. You can rewrite your recurrence as follows:
$$
Q(x) = T(2^x) = T(n) = T(n^\frac{1}{2}) + c = T(2^{x/2}) + c = Q(x/2) + c.
$$

Which is easily solved using, e.g., the Master Theorem to obtain $Q(x) = \Theta(\log x)$. Substituting back:
$$
T(n) = Q(x) = \Theta(\log x) = \Theta(\log \log n).
$$


I/O in Theory of Computation I posted a question "Arbitrary Programs that halt" some days ago and now i think my doubt is a lot more clear.

I concluded that in any arbitrary program that halts, control flow operations, calculation operations ( 2+3 , "1 && 0", etc ) and memory assignment ( x:= "Hello" ) can be easily represented by Models of Computation such as Turing , RAM Machines, Lambda Calculus, etc.

But I/O operations such as reading input from keyboard/mouse/etc, writing output to monitor/speaker/network_device, don't really seem to have any relation to those models of computation, that is, i can't think of a way to simulate/emulate them there ( the only I/O operation that those models of computation could simulate is writing and reading from memory ) .    This reflects the fact that the programming languages were meant to access not only the CPU and the memory but the entire desktop PC ( including its additional I/O devices ).

At the same time, i've some people suggest that those I/O operations correspond to computations, in the Theory of Computation sense, and i'm thinking this is a problem because Turing-complete models of computation were mean't to possibly express ANY computation.

So, there are two possibilities  :
1 - Those I/O operations are not really computation and hence Turing-Complete models of computation are not required to express them, and also programming languages ( and our Desktops in general ) are modelling MORE than mere computation, they are modelling Computation + I/O.

2 - Those I/O operations are really "computation" and i simply don't know how to think of simulating them with Turing-Complete models of computation, that is, i can't seem a way to simulate the entire composition of a desktop PC ( CPU + memory + all external devices ) in those models of computation.

The first option seems more plausible to me, but i don't know.

What do you guys think about the relation between those I/O Operations and Computation ?

For Turing machines I/O corresponds to using the tapes:

a disk is a tape which has been rolled up
keyboard is the input tape
display is the output tape

A more interesting question is how to model interaction between machines using communications channels (that's a form of I/O), especially asynchronous communication. You can look up communicating sequential processes and $\pi$-calculus to learn about computational models that account for communication (and these are not the only ones).

The $\lambda$-calculus is a bit different because it does not have a direct notion of I/O. However, in any programming language we may simulate an input or an output stream by passing around extra lists of chacarters (or bits) which represent input and output streams. Here is an example in Haskell (but using only purely functional part if Haskell without any real I/O):

    -- Simulated IO in a purely functional way in Haskell

    -- A dataype of programs which perform simulated IO and return
    -- results of type a
    data SimulatedIO a =
        Result a
      | Output String (SimulatedIO a)
      | Input (String -> SimulatedIO a)

    -- Run a simulated IO calculation on the given input stream.
    -- Return the result, the remaining (unused) input, and output.
    run :: [String] -> SimulatedIO a -> (a, [String], [String])
    run input (Result a) = (a, input, [])
    run input (Output s c) =
      let (x, input', output) = run input c
      in (x, input', s : output)
    run (s:input') (Input c) = run input' (c s)

    -- Example
    greeter :: SimulatedIO Int
    greeter =
      Output "What is your name?" -- ask the user for his name
             (Input (\name -> -- read the name
                Output ("Hello " ++ name) -- greet the user
                       (Result (length name)))) -- return the length of user's name

    -- Execute the example with simulated input ["John", "Banana", "Orange"]
    example = run ["John", "Banana", "Orange"] greeter

    -- the result is
    --
    --    (4, ["Banana","Orange"], ["What is your name?","Hello John"])
    --
    -- 4 because "John" has four characters
    -- ["Banana","Orange"] is the unused input
    -- ["What is your name?","Hello John"] is the output


Simple proof that circuit satisfiability problem is NP-Hard $\newcommand{\np}{\mathsf{NP}}\newcommand{\cc}{\textrm{Circuit-SAT}}$I am having difficulty understanding the $\np$-hardness proof for $\cc$ in CLRS.

$\cc = \{\langle C \rangle : C \text{ is a satisfiable combinatorial boolean circuit} \}$
Lemma: The $\cc$ problem is $\mathsf{NP}$-hard.

Can anyone provide an easy-to-understand proof?

The (very) simplified version is that they convert any verification algorithm $A$ for a language $L \in \text{NP}$ into a circuit.

What they end up with is a circuit $C$ that, given a (binary) string $x$ is satisfiable (i.e. $C(x)=1$) if and only if $x \in L$ (i.e. there exists a certificate $y$ such that $A(x,y) = 1$).

They do this by encoding the working of the algorithm embodied by some Turing Machine (i.e. the transition function) as a circuit $M$. The total circuit $C$ is then a series of concatenations of $M$, where the input values to each iteration of $M$ is a binary encoding of the state of the TM embodying $A$.

As every bit of this (including the number of steps $A$ takes) is polynomially bounded by the size of $x$, the circuit can be constructed in polynomial time.

So what they give overall is a polynomial time way to construct a circuit simulating $A$ set by step that is satisfiable if and only if we can find some certificate that $x \in L$. Then if we could decide in polynomial time if $C$ is satisfiable we'd know that there's some certificate which proves $x \in L$, hence deciding $L$ in polynomial time.


Splay tree with odd number of rotations When inserting an item into a splay tree, rotations are performed in pairs based on either a zig-zag or zig-zig pattern. When there is an odd number of rotations to be performed, one could either do the extra rotation beginning at the leaf or save the extra rotation and do it at the root. Does it matter?

For example, in the attached image I insert a 4 into a BST, and "splay it"
it to the root. On the top of the figure, I first locate the zig-zig pair
at the leaf node and perform the zig-zag splay from the bottom leaving a final right rotation at the root. At the bottom of the figure, I first do the odd rotation starting from the leaf, and the then do a zig-zig splay to the root.

Which is correct? Or  will both lead to the usual splay-tree performance?

It really does not matter for the analysis. The key lemma for analyzing the splay-tree performance is the access lemma. It states that the amortized costs of a splay(x) operation is less than $1+3(r(t)-r(x))$, where $t$ is the root of the tree and $r(u):=\lfloor \log (\text{weight of $u$'s subtree}) \rfloor$.  The weight of a subtree is the sum of the weights of its nodes. (Weights (positive) will be picked depending on the application of the lemma.) The potential function used is $\Phi(T)=\sum_{x \text{ node of } T} r(t)$.

The proof of the access lemma looks at the costs of a single zig/zig-zag/zig-zig etc.  operation. You get

Costs of a zig or zag  operations are $1+3(r_+(u) - r(u))$, where $r_+$ is the rang after the operation and $u$ is the node rotated upwards.
Costs of zig-zig /zig-zag and symmetric operations are $3(r_+(u) - r(u))$.

If you add these differences up for the operations performed in a single splay(x), you get a telescope sum and what remains is $1+3(r(t)-r(x))$.

If you change the order of the rotations you will get the same sum. The only difference is that now the ''+1'' comes from the first rotation and not from the last rotation. You could even do the zig rotation in the middle. All further (classical) analysis relies on the access lemma.

However, the reason why you perform the single rotation last, is that you do not know if the depth of the node is even or odd in advance.


Modeling equality in an ILP Lets say we have integer variables $a \in\mathbb{Z}^n$  and  $M \in\{0,1\}^{n\times L}$. I am promised $a_i \leq L$, for some fixed constant $L$.  I want to model the constraint $$M_{i,j} \iff (a_i=j)$$
in an integer linear program.  What is the most efficient way to do this in an ILP?  In particular, can I do this without Big-M constraints and without breaking down each integer into its binary representation?

Currently I can see two ways to model this:

Option 1

We can apply the method described in the answer here to the constraint $M_{i,j} \iff (a_i-j=0)$.  This requires $1$ extra binary variable as well as  $4$ potentially large "Big M" constraints per $M_{i,j}$, thus resulting in $nL$ new binary variables and $4nL$ new big M constraints.

Option 2

We can break down $a_i$ into its bits using $\log L$ extra binary variables. We can also compute the corresponding binary bit breakdowns for each $0\leq j \leq L$. Let $bit^{(a)}_{i,k}$ be the $k$th bit of $a_i$ and let $bit_{j,k}^*$ be the $k$th bit of the integer $j$, so that
$$a_i = \sum_{k=0}^{\log L}2^kbit^{(a)}_{i,k}.$$

We now have the following logic:
$$M_{i,j} \iff (\forall k . 0\leq k\leq \log L \implies bit^{(a)}_{i,k} \odot bit_{j,k}^*)$$

Therefore

$$M_{i,j} = \bigwedge_{k=0}^{\log L} bit^{(a)}_{i,k} \odot bit_{j,k}^*.$$

We can use this post to NXOR the pairs of variables, storing their results as another variable $z=\{0,1\}^{\log L}$. We can AND these together using the constraints $$M_{i,j} \ge \sum z_i$$ $$M_{i,j} \leq  z_i \;\;\; \forall i$$

This creates $\log L$ new variables and 1 constraint for representing the binary breakdown of $a_i$. We then have $\log L$ XNOR variables, each which can be represented with 4 constraints. We can finally represent $M_{i,j}$ with  $\log L + 1$ more constraints. Therefore, we have a total of $5\log L$ constraints and $2\log L$ new variables per $M_{i,j}$, giving us a total of $5nL\log L$ new binary constraints and $2nL\log L$ new binary variables.

Is there some third option that is better than either of these two options?

I have several options for you.  Here is the simplest:

1.1 Direct Option

Use an inequality to enforce that one out of $M_{i,1},\dots,M_{i,L}$ are true:

$$M_{i,1} + \dots + M_{i,L} = 1.$$

Use a second inequality to link that to $a_i$:

$$a_i = M_{i,1} + 2 M_{i,2} + 3 M_{i,3} + \dots + L M_{i,L}.$$

2 Indirect Options

Alternatively, we could try to follow more closely to the approach you outlined, but using ideas from one-out-of-n constraints for SAT solvers.  In particular, the entries $M_{i,1},\dots,M_{i,L}$ are a one-hot encoding of a one-out-of-L constraint, and you want them to be consistent with an encoding directly as an integer.  There are standard techniques for enforcing one-out-of-n constraints for SAT, and you could using them with ILP as well.

2.1 Improved Binary Encoding

We can use the idea in https://cs.stackexchange.com/a/51512/755 to improve your option 2.  Let $a_{i,k}$ denote the $k$th bit of $a$.  We add the constraint

$$M_{i,j} \implies a_{i,k} \text{ if } bit^*_{j,k}=1,$$

otherwise add the constraint

$$M_{i,j} \implies \neg a_{i,k} \text{ if } bit^*_{j,k}=0.$$

Next, we add the constraint

$$M_{i,1} + \dots + M_{i,L} \ge 1.$$

This requires only $n+nL\log L$ constraints and $n\log L$ new variables, instead of $5nL \log L$ constraints and $2nL \log L$ new variables.

Commander Encoding

You could use a a recursive commander encoding to enforce that exactly one out of $M_{i,1},\dots,M_{i,L}$ are true.  Note that the constraint for "at most one variable in a group can be true" requires $O(m^2)$ clauses in SAT but can be represented in a single inequality in ILP, so the number of constraints needed will be smaller than for SAT.  Then, you could use any of the above techniques to link the $M$'s to the $a'$.

That said, I don't expect these indirect options to be worth implementation; my expectation is that the direct option will be more natural, and it is what I would try first.


Count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum count the number of ways numbers 1,2,…,n can be divided into two sets of equal sum.

This is my recursive algorithm, what is wrong here?:

int f(int sum,int i){//sum is the current sum, i is the current indx (<=n)
    if(i>n){
        return ((2*sum)==(n*(n+1)/2));//ie sum==totalsum/2
    }
    int cnt=f(sum,i+1)+f(sum+i,i+1);//move to i+1 or add i to sum and then move to i+1
    return cnt;
}

For example, if n=7, there are four solutions:
{1,3,4,6} and {2,5,7}
{1,2,5,6} and {3,4,7}
{1,2,4,7} and {3,5,6}
{1,6,7} and {2,3,4,5}
ie f(0,1)=7

Answer is f(0,1) for any n (n is globally defined)

Thanks!

You are counting the number of ordered pairs of sets $(A,B)$ such that the elements of $A$ (and of $B$) sum to $n(n+1)/4$.
Simply divide the result by $2$ to account for symmetries.

Besides, your algorithm has complexity $\Omega(2^n)$ so I doubt you'll meet the time constraint in the link you provided.

You can get an $O(n^3)$-time dynamic-programming algorithm as follows:

   Let $OPT[n, x]$ be the number of ways the numbers in $\{1, \dots, n\}$ can be partitioned into an ordered pair of sets $(A,B)$ such that the elements of $A$ sum to $x$ and those of $B$ sum to $n(n+1)/2 -  x$.

 Then, $OPT[0, 0] = 1$, $OPT[n][x] = 0$ if $n<0$ or $x<0$, and

 $$OPT[n,x] = OPT[n-1, x-n] + OPT[n-1, x]$$

 Now, assuming that $n(n+1)/2$ is even, the solution you are looking for is: $\frac{1}{2}OPT[n][ n(n+1)/4 ]$.


Big O of an algorithm that relies on convergence I'm wondering if its possible to express the time complexity of an algorithm that relies on convergence using Big $O$ notation.

Is it fair to say that we can't reason about an algorithm's scalability based on input size if we also have to rely on convergence - unless there's some facet of the algorithm's manner of convergence whereby we can mathematically prove that the number of iterations to reach convergence is related to input size (essentially showing that convergence of the algorithm is a function of the input size $N$)?

For instance, I'm using an algorithm called TextRank, which is based on PageRank - except each vertex is a sentence instead of a webpage and each edge represents the similarity between two sentences (or vertices). The algorithm iterates over the vertices in the graph, carrying out a computation to calculate the score of each vertex for an indefinite amount of iterations until the difference between scores from one iteration to the next is below a threshold (we've reached convergence).

I'm thinking that we cannot reason that an input of size N sentences will always converge in the same manner. Two different bodies of text with say $30$ ($N=30$) sentences, could theoretically require a noticeably different number of iterations over the graph to converge.

Is it possible to represent the limiting behaviour of the function in a polynomial expression due to reliance on convergence?

Usually we prove something about the rate of convergence.  For instance, we might prove that after $k$ iterations, the relative error is $1/2^k$.  Thus if each iteration takes (say) $O(n^2)$ time, and we want an answer that has relative error at most $\epsilon$, then we have found an algorithm whose running time is $O(n^2 \lg (1/\epsilon))$.  Notice how the running time now depends both on the input size and on the desired accuracy of the answer.

For instance, PageRank uses power iteration.  As you can see from the Wikipedia page on power iteration, it is possible to prove results about its rate of convergence (as a function of the first two largest eigenvalues $\lambda_1,\lambda_2$).


Genetic algorithm fitness function I'm trying to write some little code (POC for the selection/mutation operators) that uses a genetic algorithm to solve a global maximum for a function.

f(x_1...x_n) = M - (x_1 - a_1)^2 - (x_2 - a_2)^2 - ... - (x_n - a_n)^2

M a_i are constants. I have to find x_i such that f(x_i) = max(f) = M

My selection method is truncation (I select the top 100 fittest of a population of 500).
My crossover method is average. there is a 80% chance for crossover, other wise one of the parents is passed on.
My elite count is 5 (1% of the population)
There is a 3% chance for a mutation for an individual, the range of the mutation is [-0.3, 0.3]

My fitness function is f it self and my stopping condition is ABS(previous best fitness - current best fitness) <= 10^(-21)

You can find the code I wrote here.

The problem is that it converges before it reaches even an approximate solution.

What can I change in the solution approach so that the algorithm would converge on the maximum(f)?
(This is not my algorithm, it's a reduction of a problem I have at work.)

I haven't looked at your code, but a few observations.

Your selection method is very strong. If you generate 500 individuals at random and choose the best 100, within just a few generations you're going to have a population dominated by descendants of that initial 100 winners. In effect, you're very quickly focusing your search on the best 20% of a random sample. You probably need something like tournament or rank-biased selection instead -- something dramatically weaker than what you have.
The elite count is maybe a tad high as well. 5 might be OK, but certainly combined with your selection method, you have an algorithm that's basically designed to converge too quickly.
Averaging in crossover may or may not be harmful. It depends on where the optimal values of your parameters lie. Take a problem like "minimize f(x)=x^2 for x in [0, 100]". The optimal value of x in that problem is at 0, and averaging two parents will in this case always result in worse offspring than one of the parents you started with. For other problems, this may be helpful instead though. If you want to try something else, Simulated Binary Crossover (SBX) is often used for real-valued optimization problems. Alternately, one approach is to reduce the crossover rate and increase the mutation rate to provide a wider search of the parameter space.


proving L1* ∪ L2* ⊆ (L1∪L2)* x∈ L1* ∪ L2*  ⇔ x∈ L1* ∨ x ∈L2*  ⇔ x ∈(L1)* ∨ x∈(L2)* ⇔ x ∈L1* ∪ L2* ⇔ x∈(L1∪L2)*

Is it enough to prove it this way?

No. Your proof of $A\iff B$ is to claim that

$$A\iff \text{something} \iff \text{something else} \iff A \iff B\,.$$

The first two stages are irrelevant, since you get back to $A$. The final stage just asserts as true the exact thing you're supposed to be proving.

Try instead to prove that every string in the first language is in the second.


Is $ L = \{ a^n\ |\ a^n \not\in L_n \} $ Turing recognizable (recursively enumerable)? Say $ \Sigma = \{a\} $, $M_1, M_2, ... $ is an enumeration of all TMs that recognize languages over $\Sigma$ and $L_1, L_2, ... $ are respectively the languages that are recognized by those TMs. We construct the language $ L = \{ a^n\ |\  a^n \not\in L_n \} $. Is $L$ Turing recognizable (recursively enumerable)?

My thought process is this: Say $L$ is recognizable. Then given a string $a^k$, we find $L_k$ based on the enumeration of $L_i$'s, and then we run $M_k$ on input $a^k$ to find if indeed $a^k \not\in L_k$. We must accept if $a^k \not\in L_k$, but $M_k$ is not guaranteed to halt in that case. So $L$ is not recognizable.

Now I have 2 questions:
1) Is my thought correct?, and
2) How can I make this more formal?

Your thought falls short of a rigorous proof. It can hardly be considered correct intuition since it does not use the condition that each Turing machine is labelled with some number, although it does use the condition that each $k$ corresponds to a Turing machine. Your "proof" would work equally well if the condition "$M_1,M_2$,...  is an enumeration of all TMs" is replaced by "$M_1,M_2$,...  is an enumeration of some TMs"

Here is a formal proof.

Suppose $L$ is recognizable. Then by definition, $L$ is the language accepted by some Turing machine $M_k$ for some $k$.  Consider $a^k$.

If $a^k$ is not in the language accepted by $M_k$, then by definition of $L$, $a^k\in L$. By the definition of $M_k$, $a^k$ is accepted by $M_k$, which is a contradiction.
If $a^k$ is in the language accepted by $M_k$, then by definition of $L$, $a^k\not\in L$. By the definition of $M_k$, $a^k$ is not accepted by $M_k$, which is a contradiction.

Since we always get a contradiction, our assumption $L$ is recognizable must be wrong.

Here is an easier proof, as presented in your comment.

For all $n$, $L\not=L_n$, since $a^n\in L$ $\Leftrightarrow$ $a^n\not\in L_n$, i.e, the membership of $a^n$ in $L$ and the membership of $a^n$ in $L_n$ is different. Since $L_n$ for all $n$ enumerates over all recognizable languages, $L$ is not recognizable.

In fact, the construction of $L$ uses the classic technique to construct a non-member of a given set, the diagonal argument that was discovered/created by the great mathematician Georg Cantor. "It has been used in a wide range of proofs, including the first of Gödel's incompleteness theorems and Turing's answer to the Entscheidungsproblem. Diagonalization arguments are often also the source of contradictions like Russell's paradox and Richard's paradox." The proof of the undecidability of the halting problem can be considered as an application of the diagonal argument as well.


Why a TM with infinite states can decide the halting problem? Assuming we have a model of TM with an infinite number of states.
The domain and range of the transition function are also infinite.
Given a description of a TM $M$ and a string $w$ how can we use the new model to tell if $M$ ever stops when running on $w$?

If you are allowed infinite states and transition functions, then even a DFA could solve the halting problem (and in fact, any language). In this case, the DFA/TM can basically have a state for each possible pair of TM + word. If a certain state represents a pair where the TM halts on the word it would be an accepting state.

Notice that I don't give a constructive algorithm of how to build this TM/DFA, but it could easily be seen that such a TM theoretically exists and therefore decides the halting problem.

EDIT - more detail regarding the last point: by definition, a language is regular if there exists some DFA accepting it, even if we don't know how to build that DFA. If we allow infinite states, than all languages will be regular. The infinite-state-DFA I described above may seem confusing because we have no idea how to construct it, and in particular, how to choose which states are accepting and which aren't. However, it definitely still exists!

Another way to think about it is that the states of the DFA can be computed/built in "compile-time" and therefore we don't need to figure out whether a TM stops on a word in "run time". We determine what is accepting and what isn't before we even get any input, and when we do get an input, we will definitely halt on it because of the nature of DFAs. We don't need to simulate a TM on an input during the DFAs run!

Lastly, I want to emphasize that the confusion regarding DFAs which we have no algorithm to construct is valid even using the standard, finite-state model of DFAs. If we denote the halting problem by $H_{TM}$, then for all $n$, the language $H_n:=H_{TM}\cap \{0,1\}^n$ is a finite language and therefore regular! However, it can be proved that there is no general algorithm that takes $n$ as an input constructs a DFA for $H_n$, since otherwise we could decide the halting problem.


Working of the GHS algorithm Can someone explain the working of the GHS algorithm using the graph given below. GHS is a distributed algorithm for finding the Minimum Spanning tree of a graph. The description of which can be found here https://en.wikipedia.org/wiki/Distributed_minimum_spanning_tree

What I think is that the fragments(the nodes in a fragment are shown within curly braces) will be formed as follows:

Step 1: {1, 2}
        {5, 6} {3}  {4}

Step 2: {1, 2, 3, 4}
        {5, 6}

Step 3: {1, 2, 3, 4, 5, 6} //as 1 and 5 get connected.

But what my professor said is that 4 will become a part of the MST at the end. These are the steps that he told us.

Step 1: {1, 2}
{5,6}// this step is the same
{3}{4}

Step 2: {1, 2, 3}{5,6}{4}

Step 3: {1, 2, 3, 5, 6}{4}

Step 4: {1, 2, 3, 4, 5, 6}

Can you please tell me which version is correct?
The graph ->

Indeed.

Let the fragment at a particular stage be :
{1,2},{5,6},{3},{4}.

Now the fragment {1,2} will connect with the least weight outgoing edge which is 1-3 and fragment {5,6} will connect with the least weight outgoing edge which is 1-5 to create the fragment {1,2,3,5,6} and {4} and finally it connects to {4} with edge {2-4}.

Hope this helped.


Turing machine that can move right only $O(1)$ steps beyond input I need to prove that a Turing machine that can move only $k$ steps on the tape after the last latter of the input word is not equal to a normal Turning machine.

My idea is that given a finite input with a finite alphabet the limited machine can write only a finite number of "outputs" on the tape while a normal Turing machine has infinite tape so it can write infinite "outputs" but I have no idea how to make it into a formal proof.

Your machine uses $n + k = O(n)$ space. As such, it can be simulated by a linear bounded automaton. The latter is known to be weaker than a general Turing machine. For example, it cannot solve the halting problem for machines using $n^2$ space, a problem that Turing machines are able to solve.


Is the language $\{a^nb^{2^n}|n\geq 0\}$ Turing recognizable/decidable? I have proven that it is not regular and context free. But is it Turing decidable/recognizable? I'm thinking yes, as I am able to write a Java program for it, and by the Church-Turing thesis the power of the Turing Machine and a Java program is equivalent (or am I wrong here?).

You are right about the fact that being able to conceive a Java program for doing the job, then there must exist a Turing machine which will also recognize that language. However, you don't need the Church-Turing thesis to confirm your statement. You need something weaker, namely the fact that both Java and TM are acceptable programming systems and hence they are isomorphic (ie. they compute the same set of partial functions) by Roger's theorem.

The main point is that Roger's theorem is a theorem and Church-Turing thesis is not proven.


Methods, Routines, or Algorithms To Optimize Selection of String Compression Methods When encoding a a 2D Datamatrix barcode, I want the smallest output size. There are means to encode a compressed a string using some methods like C40.
Reference:

Here's a reference: https://en.wikipedia.org/wiki/Data_Matrix#Text_modes

Some sections of the string will compress more efficiently than others depending on the encoding method.

To be clear, I'm not trying to make my own compression scheme.

I want to compute the best combination of existing compression schemes. For example, I can individually use Ascii or C40 to encode an entire string. Each scheme has its unique benefits.

BUT I can also compress specific parts of the string with different schemes. So, switching back and forth between Ascii and C40 can result in a more efficient compression than C40 or Ascii alone.

QUESTION:
How do I optimize the selection of compression schemes for section of the input string. I would be comfortable narrowing it down to only combining c40 and ascii.

Are there any algorithms for scanning strings and and optimizing the result?

If you want to find the optimal combination, one approach would be to use dynamic programming.  Let $f(n,s)$ denote the length of compressing the first $n$ characters via some combination of compression methods, ending with the compression subsystem in state $s$.  Here $s$ represents both which compression method is currently being used (Ascii or C40) as well as its internal state (i.e., whether you are currently in set 0, set 1, set 2, or set 3).

Then you can compute $f$ recursively.  Applying memoization, we get a dynamic programming algorithm to compute $f$.  The resulting algorithm will take $O(n)$ time to compute the best compression.

How do you compute $f$ recursively?  Basically, when computing $f(n,s)$, you consider both possible cases for how to encode the $n$th character:

Case 1: Stick with the same compression method and state you had before, when encoding the $n$th character.  The cost of doing so is $f(n-1,s) +$ the number of bits to encode the $n$th character when in state $s$.
Case 2: Switch compression methods and/or state just before encoding the $n$th character.  The cost of doing this is $f(n-1,s') + $ the number of bits to switch from state $s'$ to state $s$ and then encode the $n$th character while in state $s$.

You should choose whichever of those provides a shorter encoding.  In other words, $f(n,s)$ is the smaller of these two quantities.  This gives a recursive algorithm for computing $f$, which can be memoized, yielding a solution that is essentially dynamic programming.

Since there are only 8 possible states (2 compression methods $\times$ 4 choices of the character set), the running time to compute $f(n,s)$ is $O(n)$.  This gives you a linear-time algorithm to find the best combination of compression algorithms for encoding any given string.


Generating sparse connected Erdős–Rényi random graphs Given a random graph $G(n, p)$, where $n$ is the number of nodes and $p$ is the probability of connecting any two edges, it is known that $t = \frac{\ln(n)}{n}$ is a threshold for the connectedness of the graph: if $p$ is greater than $t$ the graph will be almost surely connected, otherwise disconnected. The farther you move $p$ from the threshold the higher the chance that the resulting graph will be disconnected/connected (source: https://en.wikipedia.org/wiki/Erd%C5%91s%E2%80%93R%C3%A9nyi_model).
I am currently trying to output from an Erdős–Rényi process a graph that is as sparse as possible. In my case $n=10000$ and therefore $t=0.00092$, which means that a connected random graph of 10000 nodes should have on average 46000 edges. Through testing with igraph I could go as low as 37000 edges: $t=0.00074$. Now I'm stuck (because the probability of outputting a sparser graph is too low) and I don't know how to further lower the degree of the graphs. Is there a way to generate sparser random graphs? I know I'm already far below the threshold. In case no solution is found for this model what is the best way to generate a very sparse connected graph?

Brenday McKay suggests an algorithm on mathoverflow. He considers a fixed number of edges, but you can also sample from $G(n,p)$ according to his method. First, calculate $c_{n,m}$ for all $m$. Then sample $m$ in proportion to $p^m (1-p)^{\binom{n}{2}-m} c_{n,m}$. Then use his algorithm.
Gray, Mitchell, and Roughan, Generating connected random graphs, suggest an MCMC algorithm, and analyze it empirically.
Both of these algorithms are for sampling $G(n,p)$ random graphs conditioned on the result being connected. There are also many heuristics for sampling other distributions of random connected graphs in the sparse regime, where usually the focus is on generating some "random-looking" distribution rather than a specific one. For example, you can generate a $G(N,p)$ random graph and pick a connected component, or you can add a random spanning tree to a $G(n,p')$ random graph.


When and Why do I Rehash? I am studying hashing and reading the part of universal hashing. I have read that I want to draw a hash function from universal hash families when I rehash. When and why do I rehash?
One reason to rehash seems to be load factor or hash table size. When I want to lower the load factor and increase hash table size, then I need to rehash. Any other reasons, especially in real database development? Thanks!

One example is consistent hashing. The usual scenario used for motivation is assigning files to servers. To avoid having too many files associated with a single server, you map $n$ files to $m$ servers via some hash function $h:[n]\rightarrow[m]$. Suupose you add a new server or that an existing server crashes, then you would have to rehash all the files to maintain functionality (this entails actual copying of the contents). One solution that avoids this is mapping each file and sever to the unit circle, and associating each file with the first server met when moving anticlockwise. If $h:[n]\cup[m]\rightarrow \left\{(\cos t,sin t)| 0\le t\le 2\pi\}\right\}$ satisfies SUHA, i.e. $h(i)$ is uniformly distributed on the unit circle when $i$ is uniformly distributed over $[n]\cup [m]$, then the expected number of files moved after a crash is $\frac{n}{m}$.


anonymous lambda functions (functional programming) What are anonymous (lambda) functions? What is the formal definition of an anonymous function in a functional programming language?

In my simple terms, when I am programming in scheme/lisp I would say an anonymous (lambda) function is a function that is not bound to an identifier.

Is that all that you can say formally about a lambda function? I think there is more detail that can be added to this simple definition. Please elaborate, and thank you!

In the lambda calculus, all functions (terms) are anonymous. This is an essential property of the lambda calculus: you can compose complex functions from simpler ones without giving them names.

In programming languages, it is in most cases desirable to give names to functions, because this is the way we think and it makes code readable for humans. But compilation eventually removes the names when producing an executable (if we disregard debugging information).

If a language allows expressing anonymous functions (that is functions without names), it can give an advantage to both programmers and compilers: Programmers can often write shorter code, and compilers can better optimize, knowing that an anonymous function is used just at the given place and not anywhere else.


Meaning of the constants that appear in the Master Theorem The general formula for time complexity is $T(n) = aT(n/c) + bn^k$.

If $a> c^k$, the complexity is $O(n^{\log_c a})$.
If $a = c^k$, it is $O(n^k \log n)$.
If $a < c^k$, it is $O(n^k)$.

$a$ is the amount of times the recursive function is called, but what do $b$, $c$, and $k$ represent?

That is not the general formula for time complexity. There is no "general formula  for time complexity", any more than there is a "general formula for the answer."

Rather, the formula you give is a recurrence relation that can be used to compute the running time of certain divide-and-conquer–style recursive algorithms.  Specifically, it corresponds to a recursive function which, when given an input of size $n$, makes $a$ recursive calls, each on inputs of size $n/c$. If you pretended that the recursive calls were "free" (i.e., that they returned their answer in one computation step), then the algorithm would take $bn^k$ steps.


Formal languages: What is $2n_c$? I have got following question:

Determine whether the following language is context free or not:
$$L = \{ w \in \{a,b,c\}^*: n_a (w) = n_b (w) = 2n_c (w)\}. $$

What is the meaning of $2n_c$ in the above question?

This language is not CFL.

Consider the language $L \cap a^*b^*c^*$ . Assume that $L$ is CFL, now, as $ a^*b^*c^*$ is regular and CFL are closed under intersection with regular languages, $L \cap a^*b^*c^*$ would be CFL. But $L \cap a^*b^*c^* = a^nb^nc^{2n}$, which is not context free (The proof is similar to this). Hence the contradiction!

Thus the given language is not CFL.


Which unit (control unite or logic unit) issue instructions of load/store? I learned that the  CPU is composed of two units

and the machine’s instructions can be categorized into three groupings: (1) the data transfer group, (2) the arithmetic/logic group, and (3) the control group.

It could be concluded that Control Unit for the control group and Arithmetic/logic for the corresponding groups

How about the data transfer group? the data reside in register, which of the two units issue store/load command?

You definitely cannot associate a part of the architecture with an instruction class.

All instructions are concerned by the control unit as it fetches instructions and decode them.
Control instruction mostly concern the controller, but some computations may be done by the ALU. For instance, in branches, addresses are generally given by adding an offset to the program counter and that requires an adder that may be in the ALU. It is the same if a branch instruction has to perform a comparison to decide if branch must be taken or not.
once decoded, arithmetic/logic or data transfer instructions mostly concern the ALU part.

By the schematic that you gave (and my explanations) were true 40 years ago. Modern computers are much more complex. Control is somehow decentralized to allow execution of several concurrent instructions, instruction reordering, branch prediction, register renaming, etc. And the ALU is no longer a monolithic bloc but formed of several functional units dealing with specific computation, memory access, etc. You can find here the microarchitecture of a recent pentium (broadwell) and it is difficult to really identify the two units in your schematic.

So even more than in your question, it is impossible to associate an hardware unit with an instruction type.


Formal Binary String Regular Expression (each pair of 00 must have 11 before it) I'm trying to construct a regular expression for the language of binary strings in which every 00 must have at least two 1s before it.
I realize this can be done with lookbehinds using the following regex: ^(?:(?<=11)00(?!0)|(?<=1)0|1+)+$ , however I am now trying to construct a regular expression in the sense of formal language theory.
I currently have (0|)(11*0)*1* (or (0+ε)(11*0)*1* ), which gives me the language of binary strings without consecutive 0s, but am not quite sure how to get the 'conditional' part in without actually using a conditional.
Accepted:
0
1
10
11100
1100
Rejected:
100
1000
11000

Here is a way to describe a binary string in which every 00 must have at least two 1s before it.
It is a string that
$\quad$ starts with zero or one 0;
$\quad$ followed by zero or more blocks, where each block is
$\quad\quad$ either one or more 1s followed by a 0, such as 10, 110, 1110, etc,
$\quad\quad$ or two or more 1s followed by two 0s, such as 1100, 11100, 111100, etc;
$\quad$ followed by zero or more 1s.
Translated into regular expression, the description above becomes
$\quad$ (0|ε)(11*0|111*00)*1*

You might want to ask, how can we arrive that kind of description?
The observation here is that the number of consecutive 0s in the string is at most 2, a very small number. That indicates that we can break down the string by enumerate different possibilities of consecutive 0s. To paraphrase rici's comment, we could try using enumeration to simulate conditionals.

Of course, there is a mild stroke of luck involved in the approach above on that language.  As a last resort, we can always use a heavier machinery such as constructing a DFA for the language (which can be done in one or several ways) and then converting the DFA to a regular expression.


pipeline execution time Lets suppose that 20 percent of the instructions in a program are branch instructions.The static prediction of the jumps supposes that the jumps don't happen.

I should find the execution time in two cases : When 30 percent of the branches happen and when 70 percent of the branches happen I also should find the speedup of one case compared to the other and express it in percentage.

Thing is,how do I find the execution time here ? I usually find the execution time where the pipeline is separated in different phases and there is given the time for each phase ....

Edit : This is NOT homework.I found this in my computer architecture textbook and its not a familiar exercise.

With a static prediction of not-taken, when the branch is not taken (correct prediction) there is no penalty. When the branch is taken ("happens"), all the instructions that were fetched after the branch instruction are flushed from the pipeline (except for any branch delay slot instructions) when the branch instruction is evaluated. Instruction fetch restarts at the correct address.

With a simple five-stage pipeline (instruction fetch, decode, execute, memory, writeback) where branch direction and target are determined in the third (execute) stage and no branch delay slots are used, a taken branch will take three cycles (i.e., the instructions in the fetch and decode stages are flushed). If all other instructions have a cycles per instruction of one, then the total CPI would be the fraction of instructions that are taken branches times three cycles plus one minus that fraction (all other instructions including not taken branches) times one cycle (for 30% taken branches: 0.20*0.30*3 cycles + (1-(0.20*0.30))*1 cycle; for 70% taken branches: 0.20*0.70*3 cycles + (1-(0.20*0.70))*1 cycle). (This is simply the sum of the products for each instruction type of the number of cycles for that instruction type times the fraction of instructions of that type. For this case, the instruction types are taken branches (three cycles, 30% of 20%) and all other instructions (1 cycle, 100% - taken branch percentage).

The execution time (in cycles) is simply the CPI times the instruction count. The speedup factor would be the execution time for one case divided by the execution time of the other case. Subtracting one from the speedup factor and multiplying by 100 gives the speedup percentage. (If the factor is less than one, the speedup percentage will be negative. Negating this would provide the slowdown percentage.)


Problem of finding pairs of elements that co-occur in some number of sets I have a fairly general problem and I wonder if it has a name. The problem statement, as best I can put it, is the following:

  Let $I=\{i_1,i_2,...,i_n\}$ be a set of items. Let $C=\{C_1,C_2,...,C_m\}$ be a set of containers. Each container is unique and contains a set of items from $I$. Let $C_{a,b} \subseteq C$ be the set of containers that contain both $i_a$ and $i_b$. Find all $(i_a, i_b)$ pairs where $\left\vert{C_{a,b}}\right\vert \geq k$ for a given $k \in \mathbb{N}$.

If the items are people and the containers are times and places, then we are asking which people met at least $k$ times. If the items are groceries and the containers are shopping carts, then the problem is a variation of association rule learning. If the items are words and the containers are documents, then we are looking for a co-occurrence network.

You can look into bipartite graphs; the item-set relationships form this type of graph, and the process of clustering highly-connected nodes (loosely speaking) is called community detection (it's similar to frequent itemset mining).


Length-preserving one-way functions Unfortunately my background in computational complexity is still weak, but I am working on it.

As I understand, the question of existence of one-way functions is very important in the field.

Assume there are one way-functions, how it can be shown that there exist one-way functions which are length preserving?

Wlog let $g$ be a strong one way function, we will now construct a length preserving oneway function $f$.
Since $g$ is PPT computable by assumption, there is a polynomial $p$ s.t $|g(x)| \le p(|x|)$ for all $x$
Define
$$g'(x) = g(x)||10^{p(|x|) - |g(x)|}$$ this function always has $|g'(x)| = p(|x|)$. and is trivially strongly one way.
We now have to force $|x| = |f(x)|$.
This we can do by taking $p(|x|)$ bits as input and taking only $|x|$ of it into account, i.e
$f(x||y) = g'(x)$ for $|y| = p(|x|) - |x| + 1$.
Strong one-wayness of $f$ follows from the strong one-wayness of $g'$.
Had $f$ not been strongly one way, we could query a PPT adversary of $f$ for  $z = f(y)$  get $x = x_1 || \ldots || x_n$ back and try for each $m \in [n]$ whether $g'(x_1||\ldots||x_m) = z$ and eventually find a preimage of $z$ under $g'$  in polynomial time with non negligible probability. Conradiction.
See the original proof here.


What does Cellular Automata Pre-image problem actually means? I am reading about Cellular Automata and Computational Complexity and i found a related paper by F. Green, NP-Complete Problems in Cellular Automata.

In the 2nd page he lists three NP-Complete problems related to CA, the first  problem is:

  CA preimage : Given a subconfiguration of length $K$, is there a configuration that could have led to it in $K$ time steps ?

I am confused with the term "Sub-configuration" and its meaning, in the paper he states that a Sub-configuration is contagious states in a finite array.

1- Does it mean a structure like Rule 110 or 90 - ECA at length $K$ ?

2- Or does it mean a pattern generated after $K$ time step in a specific structure (i.e a pattern in rule 110) ?

3- Why the problem states that the subconfiguration's length should equal to the time steps it was generated in ?  what if the problem was solvable in $K$ time steps but with a constant time steps $Z$ ?

The way I understand it, the answer is your item #2.

That is, the specific CA is fixed (i.e., rule 90 or rule 110, or what ever), and given that fixed CA, one gives you a (sub)configuration, and asks whether there exists another configuration that leads to the input (sub)configuration within $K$ steps.

Indeed the description there (in the introduction of the paper) is very informal, but this is only because the
the problem is formally stated in section 3:

  CAP (CA Preimage problem):
  Given: A fixed CA $(Q,\delta)$ and a configuration substring $s$.
  Question: Is there a configuration substring $s_0$ such that $s_0 \vdash^{K} s$, where $K= |s|$?


How to analyse the worst-case time complexity of this algorithm(a mix of Bubble Sort and Merge Sort)? Suppose I have a sorting algorithm that sorts a list integers. When the input size(the number of elements) $n$ is odd, it sorts using Bubble Sort and for even $n$ it uses Merge Sort. How do we perform the worst-case time complexity analysis for this algorithm?
The context in which this question came about is when I was going through the analysis of MAX-HEAPIFY algorithm given in CLRS(3rd edition) on page 154. In the worst-case analysis, the author had assumed some arbitrary input size $n$ and then concluded that the worst case occurs when the bottom-most level of the heap is exactly half full. This threw me off since in various texts and articles, $n$ is assumed to be fixed when performing the worst case analysis(and even for best or average cases for that matter) and that the number of elements at the bottom-most level of a heap of $n$ nodes is fixed. In that light, I concocted this algorithm so as to have the worst case dependent on $n$.
My intuition tells me that the worst case time complexity for this algorithm is $\mathcal O(n^2)$ since that's the worst case runtime for Bubble Sort. But I want to know the precise mathematical formulation of the worst-case time complexity analysis for any algorithm. Any insight would be much appreciated.

Let $f(n)$ the maximum number of elementary operations performed by the algorithm when the number of elements to sort is $n$.
An upper bound to the worst-case complexity of the algorithm is $O(n^2)$ since there exists some $n_0$ and some constant $c>0$ such that for every $n \ge n_0$, $f(n) \le c n^2$.
Moreover, given some other function $g(n) = o(n^2)$ it is false that $f(n) \in O(g(n))$ since for all $c>0$, there always exists a sufficiently large $n$ for which $f(n) \ge c g(n)$.  In this sense, $O(n^2)$ is the smallest asymptotic upper bound you can hope to obtain.
Notice however that with this choice of $f(n)$ it is not true that $f(n) = \Omega(n^2)$ according to Knuth's definition of big Omega, while it is true in the Hardy–Littlewood definition.
The "problem" here is that $f(n)$ is not monotonically non-decreasing, while the functions considered in algorithm analysis usually are.
Of course you can define $F(n) = \max_{0 \le n' \le n} f(n')$ to get a monotonically non-decreasing function, which is probably what you have in mind when you think of the worst-case running time of the algorithm.
Then you have:
$F(n) = O(n^2)$ and $F(n)= \Omega(n^2)$ showing that $F(n) = \Theta(n^2)$.


Classes and Algebras: Which begat which? Way back in the day I took a course on discrete structures and learned about how the mathematical notion of an algebra is akin to the class data type.

But I didn't know enough at the time to ask whether algebras are used to model classes or whether classes are actually derived from algebras (historically, technically...in whatever sense of 'derived' you like).

Wikipedia and Google weren't much help. Anyone have any idea?

I'm not sure I fully understand your question, but I think you noticed that algebras (or more precisely algebraic signatures) and classes share a feature, namely that they both can be seen as specifying a bunch of operations. For example the algebraic construct group has three operations: multiplication, inverse and the constant $1$. Now you ask if algebras can be used to model classes.

The answer is negative at this point. Classes in the sense of OO programming are complicated beasts. They have features that algebras don't have, in particular computational dynamics. There are other features like inheritance, method overriding, mutable private members that also
don't lend themselves to easy algebraic description. For this reason, purely algebraic sematics of OO languages don't exist.

As to the historic question, I don't know. The development of types goes back to the end of the 19th century, a time when abstract algebra was in nascent form too


Does every language in BPP have a mapping reduction to ATM? Does every language $C$ in the class $BPP$ have a mapping reduction to $A_{TM}$?
$(C\leq _{m} A_{TM})$

$BPP$ is the class of languages that have a probabilistic $TM$ that accepts them with an error $\epsilon$ less than 1/3.

$A_{TM}$ is the acceptance language, takes as input a $TM$ description of $M$ and a word w, then determines if w is in $M$'s langugae. $A_{TM}$ is of course undecidable!

Yes.

Every decidable language reduces to $A_{\mathrm{TM}}$.

Every language in BPP is decidable because the definition requires that every execution of the probabilistic machine halts in polynomial time. So you can just simulate out all the possibilities and compute the probability that the machine accepts.


Finidng edges of convexhull from rectangles Green Boxes = rectangles
red dots = edge points
red lines = to be generated from convex hull algorithm

I have a problem with creating the convex hull algorithm.
I want to select or collect all the edges from these rectangles and draw convex hull around through these edges (See red dots from the Image).
To make my algorithm more efficient, I don't know how to deselect or eliminate the points (X black points) inside all rectangles.

Could someone give me a solution for this?

Thanks in advance

If you have $n$ rectangles, take the convex hull of the $4n$ points given by the corners of those rectangles.  This gives you exactly what you want, and you can use any standard algorithm for computing the convex hull.  There is no need to explicitly deselect individual corners -- let the algorithm for computing a convex hull take care of that.


Finding optimum point that minimizes maximum distance Does anyone know how I should approach this algorithm? It needs to have $O(n^3)$ complexity and I can only come up with an algorithm that has $O(n^4)$ complexity (of doing a n^2 min path from each vertex to $n-1$ other vertexes, and since I need to do this n times, it will be $n^4$ or so I think...

Input: Array $A[1...n][1...n]$ such that $A[i][j]$ gives length of edge(distance) between two points or $-1$ if there isn't and edge.
Output: a vertex $v$, such that distances(total lengths) to all other vertexes are minimized.

Can someone explain in pseudocode or in words how to do this?

you can use Floyd Warshall algorithm to find distance of every pair and then just use a simple for to find the sum of distance of any of vertices  and print the minimum of them


Lower bound time complexity for obtaining an arbitrary entry in a hashtable I just answered this question on StackOverflow, which asks for an efficient algorithm such that given a nonempty hashtable,
the algorithm should return a pointer to an arbitrary nonempty entry in the hashtable.
My answer was quite casual and I am not confident if my proof was correct.
I am rephrasing the problem statement below:

We are allowed to extend the insert()/remove() operations of a hashtable
We need to expose a get_arbitrary() operation that always returns a nonempty entry in the hashtable if it is nonempty, or nil if it is empty.
We are allowed to store extra data related to hashtable
Assume hash keys are uniformly distributed.
Assume insert()/remove() have memorylessly equal probability to be called on any key that exists in the hashtable.

This problem asks if it is possible to draw some relation on the lower bounds of the

time complexity of insert() $T_i(n)$
time complexity of remove() $T_r(n)$
time complexity of get_arbitrary() $T_a(n)$
space complexixty of any extra data we are storing, in addition to the original hashtable $S(n)$

One of the conjectures I thought of (as mentioned in the linked StackOverflow question) is $T_a(n) = O\left(\frac n{S(n)}\right)$,
but I am not sure if this is correct.
Also I am interested in knowing something can be said about how $T_a(n)$ relates to $T_r(n)$.

We usually assume that a reasonable proportion of entries in a hash table are used, or we would be wasting memory. If we know that a hash table is at least 20% full then we can just visit random locations until we find a used one , five or so in this case (starting with a random entry and checking consecutive entries wouldn’t work with badly distributed hash keys). You could do this if you re-hash the table with fewer slots if it gets to empty, or if you know that you never delete any hash entry.

You could have a bitmap of unused entries which would make the search faster by a large constant factor. You could create a linked list of the used slots if less than 20% of slots are used and maintain it until usage exceeds 50%, instead of re-hashing.


Recurrence with a function of n times T() The master method works well on problems like $T(n)=kT(an)+cn$, but it does not handle problems like
$$T(n)=n^{\frac{1}{3}}T(n^{\frac{2}{3}})+n^2$$
With the number of branches for each partition is a function of $n$. I wonder if there's a good solution to this kind of problems, I have no idea how to solve this, any help is appreciated!

You can use the more elementary method in which you expand the recurrence:
\begin{align}
T(n) &= n^2 + n^{1/3} T(n^{2/3}) \\ &= n^2 + n^{5/3} + n^{5/9} T(n^{4/9}) \\ &= n^2 + n^{5/3} + n^{10/9} + n^{19/27} T(n^{8/27}) \\ &= \cdots
\end{align}
This suggests that $T(n) = O(n^2)$. Indeed, let us try to prove by induction that $T(n) \leq Cn^2$:
$$
T(n) \leq n^2 + n^{1/3} \cdot Cn^{4/3} = n^2 \left(1 + \frac{C}{n^{1/3}}\right),
$$
which will be at most $Cn^2$ for any $C>1$ and large enough $n$ (depending on $C$).
Indeed, defining $S(n) = T(n) - n^2$, we have
$$
S(n) = n^{5/3} + n^{1/3}S(n^{2/3}),
$$
and so the same argument shows that $S(n) = O(n^{5/3})$ and so $T(n) = n^2 + O(n^{5/3})$. In the same way, we can get $T(n) = n^2 + n^{5/3} + O(n^{10/9})$, and so on.


How to formulate Traveling Salesman Problem (TSP) as Integer Linear Program (ILP)? Consider this distance matrix of an asymmetric TSP instance:
$$
\begin{matrix}
& c_0 & c_1 & c_2\\
c_0 & 0 & 1 & 2\\
c_1 & 2 & 0 & 1\\
c_2 & 1 & 2 & 0
\end{matrix}
$$

One optimal tour (with a total distance of 3) is clearly: $$ c_0 \rightarrow c_1 \rightarrow c_2 \rightarrow c_0$$

Now we can reformulate this as an ILP. Let $e_{i,j}\in\{0,1\}$ denote the presence or absence of the directed edge from $c_i$ to $c_j$ in the tour (0 - edge is not in the tour, 1 - edge is in the tour). Then we obtain the ILP by:

setting the objective $$\text{minimize}\;\;\; 1\cdot e_{0,1} + 2\cdot e_{0,2} + 2\cdot e_{1,0} + 1\cdot e_{1,2} + 1\cdot e_{2,0} + 2\cdot e_{2,1}$$
ensure that we arrive at city $c_i$ from exactly one other city and depart from $c_i$ to exactly one other city
$$\begin{align*}
e_{0,1} + e_{0,2} = 1\\
e_{1,0} + e_{1,2} = 1\\
e_{2,0} + e_{2,1} = 1\\
e_{1,0} + e_{2,0} = 1\\
e_{0,1} + e_{2,1} = 1\\
e_{0,2} + e_{1,2} = 1
\end{align*}$$
ensure we do not find a set of minor tours (we want a complete tour through all 3 cities) by enforcing the following constraints for the artificial variables $u_i$ (Miller-Tucker-Zemlin subtour elimination constraints):
$$\begin{align*}
u_1 - u_2 + 2\cdot e_{1,2} \leq 1\\
u_2 - u_1 + 2\cdot e_{2,1} \leq 1\\
\end{align*}$$

Is this transformation correct? Its probably not because when I try to use a Solver it says that the ILP is infeasible.

I tried to follow the steps on Wikipedia:
https://en.wikipedia.org/wiki/Travelling_salesman_problem#Integer_linear_programming_formulation

Edit 1

We can verify that there must be a solution to the ILP by the following considerations:

There are exactly 2 solutions to the equation system under 2.
$$\begin{align*}
\text{(1)}\;\;\;e_{0,1} = e_{1,2} = e_{2,0} = 1 \land e_{1,0} = e_{2,1} = e_{0,2} = 0\\
\text{(2)}\;\;\;e_{0,1} = e_{1,2} = e_{2,0} = 0 \land e_{1,0} = e_{2,1} = e_{0,2} = 1\\
\end{align*}$$

Since there are 6 variables and each variable can have only 2 values, we can easily verify this by testing all $2^6$ variable assignments.

Now we can observe that either $e_{1,2} = 0 \land e_{2,1} = 1$ or $e_{1,2} = 1 \land e_{2,1} = 0$ holds for the solutions.

In the first case we can satisfy the inequations under 3. by $u_1 = 2 \land u_2 = 1$ in the latter case by $u_1 = 1 \land u_2 = 2$.

Edit 2

This is annoying. I used another tool (LPSolve) to solve the exact same ILP and got the solution instantly. Seems that my transformation was correct and the tool is buggy.

You must have entered your ILP program into the ILP solver wrong.  It's easy to verify that the ILP program is feasible, using the procedure I outlined in the comments.  In particular, from the tour $c_0 \to c_1 \to c_2 \to c_0$ we get the assignment $e_{0,1}=e_{1,2}=e_{2,0}=1$ and $e_{1,0}=e_{2,1}=e_{0,2}=0$.  Setting $u_1=0$ and $u_2=1$, we find a feasible solution: you can easily check by hand that every one of your equations is satisfied.  So, you've done something wrong in entering it into the tool.

In the future, you should do that kind of sanity check on your own before asking here.


Question on digital DE-MULTIPLEXER! How does a demultiplexer ignore/discard/block the non-required outputs?
A demultiplexer channels the input to one of the outputs, but there are several outputs. When one output is selected (depending on the state of the select line(s)) then rest of the outputs are 0/low (am I right?).
Now, if the input is 0/low then the selected and non-selected outputs all becomes 0/low.
How does the demultiplexer perceive the final result in such a case??

Please explain in details (with reference to 1:2 demux if possible). Thank You!

It's just AND gates.  So, assuming $in$ is the input, $sel$ is your selector bit, and $out_1$ and $out_2$ are your two possible outputs, you would get:

$out_1 = in \land \lnot sel$

$out_2 = in \land sel$

The idea is that, if $in$ is $0$, out must always be $0$.  If $in$ is $1$, then we have to output it to the proper gate.   If you had a larger demux, you would simply have more selector bits.  So, for a demux with 16 outputs, we would need 4 selector bits: $sel1$, $sel2$, $sel4$, and $sel8$.  Output 10 would thus be a 5-input AND gate:

$out_{10} = in \land (sel_8 \land \lnot sel_4 \land sel_2 \land \lnot sel_1)$

The other outputs would be blocked because they would have different combinations of $sel1$, $sel2$, $sel4$, and $sel8$ ANDed into their outputs.


Examples for incomparable semi-decidable but undecidable languages In Schönig and Pruim's Gems of Theoretical Computer Science, the following statement is made:

  'Post's Problem', as it has come to be known, is the question of whether there exist undecidable, computably enumerable sets that are not Turing equivalent to the halting problem. In particular the answer is yes if there are two computably enumerable languages $A$ and $B$ that are incomparable with respect to $\leq_T$, i.e. such that $A\nleq_T B$ and $B\nleq_T A$.

The text goes on proving that there exists such languages $A$ and $B$.

Does this imply undecidable recursively enumerable sets are not isomorphic to the halting problem? Are there examples of such languages?

Some undecidable r.e. sets are isomorphic to the halting problem, for example the halting problem itself. Others are not, for example the one constructed by Friedberg and Muchnik using the priority method, a complicated kind of diagonalization. This set is not easy to describe, though one could argue that its description is "explicit". For some references, check out the Wikipedia article on simple sets, or any lecture notes on recursion theory.


How Can we make $O(N)$ order statistic queries with Fibonacci heap in $O(N)$? We have a Fibonacci heap with $N$ unique elements we want to make $O(N)$ order statistic queries (e.g., what is the element number 7 in this collection if it was sorted). Moreover, we know that the order statistic queries would be made in order (e.g., for $O(N)$ queries: what is elements number $1,3,5,\ldots,N$) .

How can we do it in $O(N)$ time ? We can't change the data structure in any way.

My thoughts:
1)The naive way is just to do delete min $N$ times but it would take $O(N \log N)$ so its not good enough.

2) if we could somehow use increase-key (if its min heap or decrease-key if its max heap) we would be able do find min in constant time increase its key so its larger than anything else in the heap we could avoid delete-min and its amortized bound of $O(log(n))$ entirely, but we are not allowed to modify the data-structure .

EDIT: sorry i didn't make it clear the heap don't have trees that waiting to be melded , otherwise its not possible since the heap could have N degree 0 trees and we cant sort N items in $O(N)$ time.

Well, you can build a Fibonacci heap in $O(N)$ time. Assuming you will get the proposed order statistic also in $O(N)$ time for the index set $\{1,2,3,\ldots,N\}$, then we can sort the stored set in linear time.

You probably know that (comparision based) sorting takes $\Omega(N \log N)$ time. Since you have no information about the universe of your elements you cannot use tricks like bucket sort or sorting on the word ram to get a linear time sorting algorithm. So you can't solve your problem in $O(N)$ time.


What is the difference between Hamming Distance and Manhattan Distance for non-binary data? What is the difference between Hamming Distance and Manhattan Distance for non-binary data (specifically I am comparing points in $\mathbb{R}^2$)? I understand Manhattan sums the absolute difference in the and x and y directions but doesnt hammming distance do the same thing?

The Hamming distance between two length-$n$ vectors is the number of coordinates in which they differ. I've only ever seen it on finite alphabets, i.e. vectors in $\Sigma^n$ where $|\Sigma|\in \mathbb{N}$. In theory there is no problem with extending this to $\mathbb{R}$, but you may have to be careful with how you use equality of floats for instance.
Specifically over $\mathbb{R}^2$, if we consider $x=(x_0,x_1)$ and $y=(y_0,y_1)$:
$$\begin{cases}
dist_\textsf{Manhattan}(x,y)=|x_0-y_0|+|x_1-y_1|\\
dist_\textsf{Hamming}(x,y)=\delta_{x_0,y_0}+\delta_{x_1,y_1}\end{cases}$$
Where $\delta_{a,b}=\begin{cases}1 \text{ if }a\neq b \\0 \text{ otherwise}\end{cases}.$
The two coincide in $\{0,1\}^n$, because in that case we have $\delta_{a,b}=|a-b|$.


Why is Graph Isomorphism downward self reducible? To say that graph isomorphism is downward self reducible means the following: There is an algorithm which decided graph isomorhpism for two given graphs of n vertices in polynomial time by accessing an oracle that solves graph isomorphism for (n-1) vertices.

To be clear, the oracle only tells 'Yes' or 'No'. It does not give us the isomorphism.

This problem appears as an exercise in Arora-Barak's chapter on Interactive Proofs.

How do I show that Graph Isomorphism is downward self-reducible?

My attempt is to start with an arbitrary vertex in $G_1$ and guess its image in $G_2$, and remove them and make an oracle call on the remaining graph. But now, I do not know how to proceed. These graphs being isomorphic may not necessarily mean that the original graphs are isomorphic.

This answer shows how to prove an easier variation, the case of (undirected loopless) multigraph isomorphism.
The problem of multigraph isomorphism is downward self-reducible
The simple idea is to merge two vertices in a way that distinguish those two vertices and edges involving them.

Let $G$ be a multigraph. If the sum of degrees of two vertices reaches the maximum, we will call an ordered pair of those two vertices a degree-maximum pair. For a degree-maximum pair $(u,v)$, construct $G_{u,v}$ as follows.

Its vertices are  all vertices of $G$ except $u$ and $v$, together with a new vertex $u_v$ which is understood as $u$ merged by $v$. Note that $G_{u,v}$ has one less vertice than $G$.

Its edges consists of two parts.

the edges of $G$ whose endpoints are neither $u$ nor $v$ with the same multiplicity. Let $m$ be the maximum multiplicity of these edges.
for all vertex $w$ of $G$ that is neither $u$ nor $v$, edge $\{w, u_v\}$ with multiplicity that is the sum of the multiplicity of $\{w,u\}$ in $G$ and the product of $m+1$ and the multiplicity of $\{w,v\}$ in $G$.

It is easy to see that if we are given a multigraph $G'$ that is isomorphic to $G_{u,v}$ for some multigraph $G$, we can reconstruct $G$ from $G'$ up to isomorphism.

Suppose we are given two graphs of $n$ vertices, $G$ and $H$. Use the oracle to compare $G_{u,v}$ with $H_{x,y}$ for all tuples $(u,v,x,y)$, where $(u,v)$ is a degree-maximum pair in $G$ and $(x,y)$ is a degree-maximum pair in $H$. Once the oracle return yes, we conclude $G$ and $H$ are isomorphic; otherwise the oracle always return no, in which case we conclude $G$ and $H$ are not isomorphic. It take polynomial time to construct $G_{u,v}$ from $G$ or $H_{x,y}$ from $H$. There are less than $n^2$ tuples. So the whole algorithm takes polynomial time. QED.

I am yet to find a proof that shows the problem of (non-multi)graph isomorphism is downward self-reducible.


Can the KenKen puzzle be solved using the same ideas as for Sudoku? There are many ways of solving Sudoku puzzles, however two good approaches are the Algorithm X and solving using Linear programming. Is it possible to solve the KenKen puzzle using Algorithm X (turning the problem into an exact cover problem) or using Linear programming and how could that be done if possible?

Edit:
Like the Sudoku, the KenKen puzzle has an NxN grid. Each row and column contain the numbers from 1 to N, so that a number can appear only once per row and per column (similar to the standard Sudoku). We define a "cage" to be a group of cells that are connected together and have a target and an operation. The idea is that all the numbers in the cage must be able to produce the target after applying the operation in between the numbers in the cage. There could be more than one instance of a number in a cage. The operations are +, *, -, /. At the beginning the cages are divided from the other cages by thicker lines on the field and the target, together with the operation is shown for each cage. The cages are wmpty, meaning that no of the grid entries are filled. There could exist a cage with only 1 entry - then the cage has no operation and has to be filled with that number. You have to solve this puzzle for a given cages with targets ans operations.

A link to the Wikipedia page of the puzzle, where an example could be seen: https://en.m.wikipedia.org/wiki/KenKen

I don't think there's a simple way to express KenKen as an exact cover problem, although it's certainly possible since exact cover is NP-complete.

I think it would probably be easiest to express it as a SAT instance. Expressing Sudoku as a SAT instance is not hard, and the arithmetic constraints can just be expressed as the disjunction of all of the possible values which would satisfy the constraint (which you would then need to convert to CNF).


Does the A* algorithm visit every node? I have been taught that the A* algorithm visits every node on the graph, like Dijkstra's does, prioritising nodes with the smallest cost. However, visualisations of the algorithm, such as this one, appear to show the algorithm stopping after finding the first path as the white blocks spreading out on the linked video do not cover the whole area before the path is highlighted, implying that not all nodes are visited.

Does the algorithm, therefore, not visit every node and instead stop after the first path is found? If so, is it not possible that a more optimum path could exist than the one found?

It only flood-fills the graph if there is no path to the end-node.

What would be the point of including a heuristic if you were just going to visit every node anyways?


Difference between SNN RL and DNN RL? In Reinfrocement Learning (RL) in Neural Networks (NNs), I've seen two approaches to Q-learning.

The first is to tile the state space with basis functions using Spiking Neural Networks (SNN) to represent reward. This approach is used in "A neural reinforcement learning model for tasks with unknown time delays" by Daniel Rasmussen and is expanded upon in "A neural model of hierarchical reinforcement learning" by the same author.

The second is to use Deep Neural Networks (DNN) to map the state space to the reward space, such as the various publications used by Deep Mind.

From what I've read so far, I believe the differences between these two approaches are as follows:

SNNs take less long to train
SNNs can be deployed on existing neuromorphic hardware
SNNs are more easily extended into continuous cases
SNNs do more inference between states
DNNs can map larger and higher dimensional state spaces
DNNs require less knowledge of the task for the programmer

Is this analysis accurate? Are there other differences that I've missed?

Daniel Rasmussen replied via email:

  SNNs take less long to train

  This really depends on the training method, and the implementation.
  If you just implemented an abstract DNN approach to solve the same
  task as is being solved in those NEF RL papers, it would be a pretty
  simple network and would train quite fast (almost certainly faster
  than with the simple PES rule).  On the other hand, if you recreated
  the internal structure of the SNN model, and trained it using a DNN
  approach (e.g., using something like nengo_deeplearning), I suspect
  that that would never converge to something useful.  So overall it's
  hard to say something useful to compare them in this sense, but I
  think if you had to commit to something, the DNN training methods are
  probably more efficient than SNNs.

  SNNs can be deployed on existing neuromorphic hardware

  Yep

  SNNs are more easily extended into continuous cases

  I'm not sure if this is true.  It is true that there aren't a lot of
  examples of people doing continuous state processing with DNNs, but
  that's also true of SNNs.  I'm not sure it's any easier or harder for
  DNNs than SNNs (it's just harder than the discrete case in both
  paradigms).

  SNNs do more inference between states

  Again, don't think this is true in general, it'll all depend on how
  things are implemented.

  DNNs can map larger and higher dimensional state spaces

  Also depends on the implementation, but it is true that DNNs tend to
  be more computationally efficient than SNNs (because they're not
  incorporating all those biological features).

  DNNs require less knowledge of the task for the programmer

  Not categorically true, but probably true in most cases.


A* optimality of the expanded node Suppose I have a admissible and consistent heuristic.

Is it true, that when I expand a node, I have guaranteed that the path I found to this node is optimal?

Look at this pseudocode from wikipedia:

function A*(start,goal)
 closedset := the empty set    // The set of nodes already evaluated.
 openset := {start}    // The set of tentative nodes to be evaluated, initially containing the start node
 came_from := the empty map    // The map of navigated nodes.

 g_score[start] := 0    // Cost from start along best known path.
 // Estimated total cost from start to goal through y.
 f_score[start] := g_score[start] + heuristic_cost_estimate(start, goal)

 while openset is not empty
     current := the node in openset having the lowest f_score[] value
     if current = goal
         return reconstruct_path(came_from, goal)

     remove current from openset
     add current to closedset
     for each neighbor in neighbor_nodes(current)
         tentative_g_score := g_score[current] + dist_between(current,neighbor)
         if neighbor in closedset
             if tentative_g_score >= g_score[neighbor]
                 continue

         if neighbor not in openset or tentative_g_score < g_score[neighbor]
             came_from[neighbor] := current
             g_score[neighbor] := tentative_g_score
             f_score[neighbor] := g_score[neighbor] + heuristic_cost_estimate(neighbor, goal)
             if neighbor not in openset
                 add neighbor to openset

 return failure

I suppose it should be true. Because of this:

if current = goal
     return reconstruct_path(came_from, goal)

If it wasn't true then this test would not guarantee me that the solution is optimal right?

What I don't get and the reason I am asking this question is this:

if neighbor in closedset
         if tentative_g_score >= g_score[neighbor]
             continue

If the neighbor is in closed list, it means that it has already been expanded. Why are they testing the scores then? Why would not the next condition work?

if neighbor in closedset
         continue

Please, let me contribute to this question with some observations. Most of them refer to the reply by Shaull.

First, and foremost, I found that the answer provided to the question pointed to by Shaull is a little bit strange. The property of monotonicity is defined there in a strange way and indeed, I posted a question ---note I am not saying that's wrong but just strange to me and not very common and frankly speaking, I am a little bit suspicious that it might be wrong.

In the original question I see various questions so let's go by steps.

First, consistency is usually defined as follows [Pearl, 1984]: a heuristic $h(n)$ is consistent if and only if $h(n) \leq c(n,n') + h(n')$ for every pair of nodes $n$ and $n'$ in the state space, where $c(n,n')$ stands for the cost of the shortest path joining $n$ and $n'$. I think it is clear that admissibility (i.e., $h(n) < h^*(n)$ where $h^*(n)$ is the true optimal cost of node $n$) is immediately implied from consistency if $h(t)=0$ where $t$ is the goal node. For this and other definitions see "Common Misconceptions Concerning Heuristic Search".

So far, no need to say "Suppose I have a admissible and consistent heuristic". It just suffices saying "Suppose I have a consistent heuristic".

Now, regarding your first question. If you have a consistent heuristic, there is no need to reopen nodes or, equivalently, everytime a node $n$ is expanded by A$^*$, the path discovered to it is necessarily optimal.

Proof: Let us assume this is not true and after expanding node $n$ through a path $\pi\langle s, n_1, n_2, \ldots, n_k, n\rangle$ there was another path $\pi'\langle s, n'_1, n'_2, \ldots, n'_l, n\rangle$ such that $g_{\pi}(n) > g_{\pi'}(n)$. Note that $f(n)=g(n)+h(n)$ so that from our assumption $f_{\pi}(n) > f_{\pi'}(n)$ since $h(n)$ takes the same value in spite of the path followed to node $n$. But this is impossible, since $n$ was expanded as a successor or the path $\pi$ so that $f_{\pi}(n) \leq f_{\pi'}(n)$. Of course, you might say that the error was committed somewhere along the path $\pi'$ because a node $n'_i$ had such a large value of $h(n'_i)$ that it was delayed in the OPEN list, but this is impossible by definition of consistency.

From here it should be obvious that the condition:

if current = goal return reconstruct_path(came_from, goal)

works smoothly since once the goal is about to be expanded it is guaranteed that the path discovered to it is optimal.

Regarding your second question, the reason of your post, Shaull already answered in the footnotes of his reply: if the heuristic function is consistent then nodes are never reopened and your condition:

if neighbor in closedset continue

is enough. However, in practice, it is just simply substituted by a different condition: when expanding a node, their children are only added to OPEN if it was never expanded (not in closedset) and also, it is not already in OPEN (not in openset). With the appropriate structures for managing the open and closed list this can be done very fastly. This trick make it unnecessary to use that statement.

But again, bear in mind what Shaull says, the pseudocode you show in your post is intended to work also with inconsistent heuristic functions. What you are asking for are, indeed, simplifications that result from the assumption of consistency.

Hope this helps,

[Pearl, 1984] Judea Pearl. Heuristics. Addison-Wesley. 1984


Does a megabyte represent (2^8)^1000000 bits in base2? Isn't that more than enough combinations to represent everything? Every introductory CompSci resource I can find goes through how 8 bits are in a byte, etc. So a byte can store some 2^8 values in binary. Then when asking about four bytes, we can assume this is (2^8)^4=2^32.

But I can't find anywhere if this pattern holds up until the total amount of hard drive or memory storage. For instance, if even a single megabyte can really hold (2^8)^1000000 bits, isn't this a number so large that it could store all data in existence everywhere in the universe many times over? The number of possible combinations from a number that large would surely never be reached. Yet in reality, we all know a megabyte isn't much.

I can't help but feel somewhere that the exponentiation must stop, and we instead multiply bytes together. Or is it really the case the numbers can get this big? Such as a gigabyte representing ((2^8)^1000)^3 bits?

If I can represent a number, let's say, 1 million in 32 bits, and I wanted to store 10^50 numbers this large, wouldn't the required bits be 2^32*10^50? First of all, I'd never need to store 10^50 of any unit of data on my hard drive, that's astronomically massive, and secondly, 2^32*10^50 is quite a small number, far below (2^8)^1000000. So what's really happening here that we need so much storage, and a megabyte isn't much?

A megabyte represents $8\cdot10^6$ bits. We can write $2^{8\cdot10^6}$ bit-strings using this much memory. But, this number is not the same as how many such bit-string we can store! Well, we can only store a single bit-string of size  $8\cdot10^6$ bits in $1$ megabyte.

To understand this better: consider a single page of a document. On a single-spaced page with 12 point font, we can put around 3000 characters. The number of possible pages that can be written in English on this single page of the document would be $26^{3000}$. But, how many characters can we actually write on such a page? quite simply 3000.


if a graph G(V,E) is connected $|E|\geq|V|-1$ If a graph G(V,E) is connected the number of edges is at least the number of Vertices-1.
It is pretty evident if you think about it but how do i prove it formally?

Imagine a process in which you start with the empty graph, and add the edges one by one. Keep track of the number of connected components. In the beginning, there are $|V|$ connected components. Each edge you add either belongs inside a connected component, or merges two connected components, and in any case, the number of connected components decreases by at most 1. Hence after adding $|E|$ edges, the number of connected components is at least $|V| - |E|$. If the graph is connected, $|V| - |E| \leq 1$, and so $|E| \geq |V| - 1$.


Does a generator really stops the execution at the machine code level, and does it not use the stack? Never have I heard of a partially executed function before.  But it seems the idea of it has been out for some time. Does a generator really stop execution at the machine code level, and that next time when the iterator is invoked, then there is a jump back to that machine code location to continue the execution?

Or is it done by having some private variables and states to control what to return? Is stopping execution of machine code and resuming to that location possible?

It seems quite strange, as

it differ from mathematics for what a function is. (in math, there is no partially executed function).
the traditional function will add to the stack, and once finished, everything is popped from the stack. But the generator is like a function that stays... so nothing is popped from the stack. So does it use something other than the stack for memory? (the heap?)

Example: JavaScript ES6 Generator:

function* generator() {    // note the asterisk
    yield 1;
    yield 3;
    yield 5;
}

const iterator = generator();

console.log(iterator.next());
console.log(iterator.next());
console.log(iterator.next());
console.log(iterator.next());

result:

{value: 1, done: false}
{value: 3, done: false}
{value: 5, done: false}
{value: undefined, done: true}

Example 2: a generator that can give an infinite number of changing color names:

function* generator() {
    const colors = ["red", "green", "blue"];
    let   i = 0;
    while (true) {
        yield colors[i];
        i = (i + 1) % colors.length;
    }
}

const iterator = generator();

console.log(iterator.next());
console.log(iterator.next());
console.log(iterator.next());
console.log(iterator.next());

result:

{ value: 'red', done: false }
{ value: 'green', done: false }
{ value: 'blue', done: false }
{ value: 'red', done: false }
  ...

It depends on the language implementation, but most do it by packaging the local variables of the generator function, together with the instruction pointer from where the last yield occurred, into a heap-allocated closure object. This is what is inside the opaque "generator object" that represents the stream of values in the language. The heap variables representing the saved instruction pointer and generator function locals are updated in place whenever the generator function yields, and reloaded to resume execution of the generator function whenever the next value is demanded from the generator.

It is important to remember that, when you get down to the machine code level, the computer has no concept of a "stack" and a "heap". Those are abstractions added by programming langauge runtime environments on top of the fundamental concepts of contiguous RAM and goto.

Generators are another feature that language runtimes can implement on top of these basic primitives. So the literal answer to the question "Does a generator really stop execution at the machine code level, and that next time when the iterator is invoked, then there is a jump back to that machine code location to continue the execution?" is yes, absolutely.

Generators are an instance of a more general concept called continuations and the call/cc operator. A continuation is often implemented as literally the state of the stack and instruction pointer packaged into a heap-allocated object.

Note that most programming language specifications allow the implementation total latitude as to how memory management works as long as the semantics of the language are conformed to. This is important for the implementation of lazy functional languages, which generalize the generator concept so that all data structures and subexpressions are generated lazily by default. These languages often have implementations that barely resemble the C locals+malloc model. Check out Simon Peyton Jones's books on the implementation of functional programming languages and the Spineless Tagless G-machine for more info. 1 2 3


What is the 2's complement answer of 16.5? According to this post it is saying Two's complement is only for integers, but in Wolframalpha is is saying the Two's complement of 16.5 is 0010000.1, how?

It seems that WolframAlpha is using fixed-point representation. In effect, it is doubling your number and then representing it as two's-complement.

In more detail, WolframAlpha is guessing that you are interested in fixed-point representations of the form
$$
xxxxxxx.x
$$
in binary, that is, 8 bits in total, with the "decimal" point at the fixed position between the 7th and 8th bits. Using two's complement, you can represent all numbers from $-64$ (represented as $1000000.0$) to $+63.5$ (represented as $0111111.1$).


Can a queue automaton recognize palindromes? Consider the language of even-length palindromes $L = \{ WW^R \mid W \in \{0,1\}^* \}$. This language is surely context free and I need an NPDA to recognize it.

But, what if we replace the stack with a queue which supports insert and delete operations? Can a queue automaton accept $L$?

The construction of a PDA except with a FIFO instead of a LIFO data structure attached can mimic any single tape TM as follows: it keeps the cell contents in the queue along with two special markers for the end of the tape and for the head of the TM. Every time you make a move, you just go through the entire queue and re-push everything you pop, making whatever slight modification in head position and tape contents you require.

So this is computationally equivalent to a Turing Machine, so in particular it can recognize $L = \{ww^R \mid w \in \{0, 1\}^*\}$.


How to show that cross entropy is minimized? This Question is taken from the book Neural Networks and DeepLearning by Michael Nielsen

The Question:
In a single-neuron ,It is argued that the cross-entropy is small if σ(z)≈y for all training inputs. The argument relied on y being equal to either 0 or 1. This is usually true in classification problems, but for other problems (e.g., regression problems) y can sometimes take values intermediate between 0 and 1. Show that the cross-entropy is still minimized when σ(z)=y for all training inputs. When this is the case the cross-entropy has the value:

C is the cost function

σ is the sigmoid function

y is the expected output of the network

I am not sure if I understand the question correctly.If σ(z)=y wouldn't the partial derivative of C with respect to the weights(or Bias) be equal to zero?This will imply that the weight is already at the correct value and the cost function cannot be reduced any further by changing the weight.

z is the weighted input to the neuron.(z=wx+b)

Where b is the bias and x is the activation of a neuron in the previous layer.(In this case it is the input to the network itself)

w is the weight value

You are calculating the so-called binary cross-entropy. Let $f(\cdot)$ be a sigmoid function. The binary cross-entropy between $y$ and $f(t)$ is

$$    F(t,y) = H(y,f(t)) = -y\log f(t) - (1-y)\log(1-f(t)). $$

When you compute the partial derivative of $F(t,y)$ with respect to $t$, you get:

$$    \frac{\partial F(t,y)}{\partial t} = f(t) - y $$

You reach the minimum when $f(t)=y$. In case of multiple variables, let:

$$    F(\vec{t},\vec{y}) = \frac{1}{n}\sum_{i=1}^n F(t_i,y_i) $$

so

$$    \frac{\partial F(\vec{t},\vec{y})}{\partial t_i} = \frac{f(t_i) - y_i}{n} $$

Now, if $t_i=\sum_j w_{ij}x_j+b_i$ is the activation, with the chain rule:

$$ \frac{\partial F(\vec{t},\vec{y})}{\partial w_{ij}}=\sum_k\frac{\partial F(\vec{t},\vec{y})}{\partial t_k}\cdot\frac{\partial t_k}{\partial w_{ij}}=\frac{1}{n}\cdot x_j\cdot[f(t_i) - y_i]$$


Prove consistency of maximum of two consistent heuristic functions? Suppose we have two heuristic functions $h_1$ and $h_2$ which are both consistent, that is,

$$h_i(n) \leq c(n,a,n') + h_i(n')\qquad \ i\in\{1,2\}\,,$$

where $c(n,a,n')$ denotes cost of reaching the successor node $n'$ with action $a$.
Can we conclude that the $h_3:=\max(h_1,h_2)$ is also consistent?