texts:
$A \rightarrow B C$

$C D \rightarrow E$

$B \rightarrow D$

$E \rightarrow A$

I have these Relations for R={A,B,C,D,E}

Now I have to calculate the closure $F^+$ and give the candidate keys

I came to these relations

$A \rightarrow A$

$A \rightarrow DC$

$A \rightarrow DE$

$A \rightarrow EE$

$A \rightarrow AA$

$A \rightarrow (DC)^{2^n}$

$A \rightarrow (DE)^{2^n}$

$A \rightarrow (EE)^{2^n}$

$A \rightarrow (AA)^{2^n}$

$C \rightarrow C$

$C \rightarrow A$

$C \rightarrow BC$

$C \rightarrow DC$

$C \rightarrow DE$

$C \rightarrow EE$

$C \rightarrow AA$

$C \rightarrow (DC)^{2^n}$

$C \rightarrow (DE)^{2^n}$

$C \rightarrow (EE)^{2^n}$

$C \rightarrow (AA)^{2^n}$

$D \rightarrow A$

$D \rightarrow BC$

$D \rightarrow DC$

$D \rightarrow DE$

$D \rightarrow EE$

$D \rightarrow AA$

$D \rightarrow (DC)^{2^n}$

$D \rightarrow (DE)^{2^n}$

$D \rightarrow (EE)^{2^n}$

$D \rightarrow (AA)^{2^n}$

$CD\rightarrow CD$

$CD\rightarrow A$

$CD\rightarrow BC$

$CD\rightarrow DC$

$CD\rightarrow DE$

$CD \rightarrow EE$

$CD \rightarrow AA$

$CD \rightarrow (DC)^{2^n}$

$CD \rightarrow (DE)^{2^n}$

$CD \rightarrow (EE)^{2^n}$

$CD \rightarrow (AA)^{2^n}$

$E\rightarrow E$

$E\rightarrow BC$

$E\rightarrow DC$

$E\rightarrow DE$

$E \rightarrow EE$

$E \rightarrow AA$

$E \rightarrow (DC)^{2^n}$

$E \rightarrow (DE)^{2^n}$

$E \rightarrow (EE)^{2^n}$

$E \rightarrow (AA)^{2^n}$

$B\rightarrow B$

$B\rightarrow E$

$B\rightarrow A$

$B\rightarrow BC$

$B \rightarrow DC$

$B \rightarrow DE$

$B \rightarrow EE$

$B \rightarrow AA$

$B \rightarrow (DC)^{2^n}$

$B \rightarrow (DE)^{2^n}$

$B \rightarrow (EE)^{2^n}$

$B \rightarrow (AA)^{2^n}$

AB

$AB\rightarrow AB$

$AB\rightarrow B$

$AB\rightarrow E$

$AB\rightarrow A$

$AB\rightarrow BC$

$AB \rightarrow DC$

$AB \rightarrow DE$

$AB \rightarrow EE$

$AB \rightarrow AA$

$AB \rightarrow (DC)^{2^n}$

$AB \rightarrow (DE)^{2^n}$

$AB \rightarrow (EE)^{2^n}$

$AB \rightarrow (AA)^{2^n}$

AC

$AC \rightarrow AC$

$AC \rightarrow C$

$AC \rightarrow A$

$AC \rightarrow BC$

$AC \rightarrow DC$

$AC \rightarrow DE$

$AC \rightarrow EE$

$AC \rightarrow AA$

$AC \rightarrow (DC)^{2^n}$

$AC \rightarrow (DE)^{2^n}$

$AC \rightarrow (EE)^{2^n}$

Could someone tell me if this is correct so far? I guess I have to give all these until ABCDE on the left side.

And how do I get the candidate keys then?


texts:
I am reading the paper "Understanding Random SAT beyond the Clauses-to-Variables Ratio" and at beginning of the page 2 say

  the hardest region corresponds exactly to a phase transition in a non-algorithm-specific theoretical property of the instance

I am a Spanish speaker.  Can you help to understand what means "non-algorithm-specific theoretical property of the instance".


texts: Give an example of a non-regular language $L$ such that $L^*$ is regular

texts: I can't think of an example of a non-regular language $L$ such that $L^*$ is regular. . Any help ?


texts: Find a maximum flow that also maximizes the flow over a specific edge

texts:
Let $G=(V,E,c,s,t)$ be a flow-network, where $s$ is the source, $t$ is the target, and $c:E\mapsto [0,\infty)$ defines the capacity of every edge in the network. Let $e=(u,v)$ be an edge in the network.
Describe an efficient algorithm to find a valid maximum flow $f$, such that $f(e)$ has a maximal value. (That is, if $f'$ is also a maximum flow, then $f'(e)\leq f(e)$).
I found someone asking the same question here, but the solution itself did not focus on achieving a good runtime complexity. The solution suggested augmenting paths that go through $(u,v)$ before any other paths, which is very intuitive and reasonable. However, I could not think of an efficient way of doing so. Ideally, I would want to adjust Dinic's algorithm so that paths from $s$ to $t$ that go through $(u,v)$ will be discovered first, but it is not simple.
I was also thinking of computing a maximum flow $f$ using Dinic's algorithm, and then adjusting it somehow so that $f(e)$ increases while $|f|$ stays unchanged. However, I could not think of an efficient way to do so.
I'd appreciate any help, thanks.


texts:
I read somewhere that the problem which asks whether or not a $CFG$ $G$ generates $1^*$ is decidable. The proof goes like this:

$1^* \cap G$ is context free since it is the intersection of a regular language and a $CFG$, therefore we can test if $1^* \cap G$ is empty since it is decidable to check if a $CFG$ is empty. If $1^* \cap G$ is empty, reject, otherwise, accept.

I have doubts however with this proof since it only shows that some string in $1^*$ is generated by $G$, but not whether $G$ generates all strings in $1^*$.
Moreover, if this proof is correct, we can use the same proof outline under the alphabet $\Sigma=\{0,1\}$ to show that $G$ generates $\Sigma^*$, or that $\Sigma^* \subseteq G$. However, it is known that it is undecidable whether $R \subseteq G$, where $R$ is a regular language, and $G$ is a $CFG$ (by setting $R=\Sigma^*$, and $\Sigma=\{0,1\}$.
But to show that a $CFG$ generates $1^*$ is decidable, the only way I can think of is to use something similar to the proof that it is decidable for a $PCP$ instance to generate some string in $1^*$ (i.e., $w=v$, where $w,v \in 1^*$), i.e. we can check if the $CFG$ has rule $S \rightarrow S1$, then accept. Otherwise, if it has rules of the form $S \rightarrow 1^aS1^b$ such that $a > b$, and rules of the form $S \rightarrow 1^cS1^d$ such that $c < d$, then accept... But is there a simpler way to solve this problem?


texts: Is there a way to modify Kadane's Algorithm such that we know the resulting subarray?

texts:
Kadane's Algorithm is an algorithm that solves the maximum subarray problem by clever dynamic programming. Is there a way to further modify the algorithm so that we would get to know the resulting subarray that produces the corresponding maximum sum?

PS: I don't know whether I should post this here, or Stack Overflow, or both.


texts: Possible ways to have cross and full edges in a mincut maxflow

texts:
I am trying to solve the following problem about maxflow mincut
it seems like my conclusion is incorrect and I am wonder where.

There is no graph just following question.

An edge e can be (x) always full, (y) sometimes full, (z) never full; it can be (x') always crossing, (y') sometimes crossing, (z') never crossing. So there are nine possible combinations: (xx') always full and always crossing, (xy') always full and sometimes crossing, and so on. Or are there? Maybe some possibilities are impossible. Let's draw a table:

Possible answers ---based on my conclusions

always full and always crossing. (true based on the image above)
always full and sometimes crossing.  (true based on the image above and the fact that we may have several crossing edges one of them may be full, all them if all edges in the min cut is 1 and one of the crossing edges is 2)
always full and never crossing. (false seems like there always must be a possibility of one of the ways to use edge with less capacity)
sometimes full and always crossing. (true if we have all edges in the mincut that are 1 and crossing edge is two)
sometimes full and sometimes crossing.( false since if we have many crossing edges that are 1 and one of them is 2 means that we might want to use the edge 2to flow more)
sometimes full and never crossing. (true easy to see and edge that sometime full but never crossing in a graph)
never full and always crossing. (true if all edges in a mincut is 1 and crossing edge is two)
never full and sometimes crossing. (true if we have many 2 crossing edges)
never full and never crossing. (true if we have a graph where one edge is 2 in min cut that never crossing)

Have asked this question on /math.stackexchange.com with no luck.

wording used.

The edge is full means in in any way we pump the flow the edge is always going to be full, basically if we have and C---(1)---A------(1)----B   and there is no other way to get to B other then going thru a then A is always full.   Somewhat full if we can have C---(1)---A------(1)----B  and if there is another way to get to b by doing  C---(1)---E---(1)----B  then edge is only sometime full. never full if we have C---(1)---E---(2)----B then most we can flow is 1 but b takes 2 then it never full.  The crossing part if we it can be the crossing edge in the min-cut from the cut to the sink. basically it and edge that connects the cut with the rest of flow.

Thanks.


texts: Can you write a program that alters another program semantically?

texts:
It is definitely possible to write a program that takes another program as an input and changes it syntactically, but does not alter the meaning.

But is it possible to write a general program $alter$ that alters the output of a given program $P$ for some input, i.e. $\exists x: P(x) \neq alter(P)(x)$? Edit: Let's add the assumption that $\exists k: P(k) \neq \bot$.

I was thinking about doing something simple like this:

alter(Program P)(x):
   k = findSomeInputWhereHalts(P)
   y = P(k)

   if (x == k)
     return y+1 // or something else except y
   else
     return P(x)

This requires that $P$ does halt for some input $x$, which is an OK requirement for me. But it seems that there is probably some other counterexample to this specific algorithm or it might be generally uncomputable, but I failed to figure it out.

Edit: How I imagined implementing findSomeInputWhereHalts:

findSomeInputWhereHalts(P):
    for each int n:
        for each int k <= n:
            y = run P(k) for n steps
            if (y is defined)
                return k

But this obviously never halts if $\nexists k: P(k) \neq \bot$ .


texts: Can Chomsky Normal Form have more than one terminal?

texts:
In formal language theory, a context-free grammar G is said to be in Chomsky normal form  if
$$ S → A B$$
$$ A → a $$
$$S → ε $$

My question is that if $B$ in the the form of
$$ B → abcd $$

where $abcd$ are terminal symbol, is this still in Chomsky Normal Form? ?


texts: What is the big-O complexity of an algorithm that evaluates all unique pairs of a list's items?

texts:
If I have a function that evaluates every pair of elements in a list, including pairs of an element with itself and with elements it has previously been evaluated against, the complexity of that function is, obviously, $O(n^2)$:

for (let i=0; i < n; i++) {
  for (let j=0; j < n; j++) {
    // this line will be executed n * n times
    operate(l[i], l[j]);
  }
}

However, if I have a variant of that loop that only considers pairs of elements  that have not yet been compared, is the complexity of that function still $O(n^2)$?

for (let i=0; i < n; i++) {
  for (let j=i+1; j < n; j++) {
    // this line will be executed (n * n-1) / 2 times?
    operate(l[i], l[j]);
  }
}

There are a few things about this that I still don't understand:

How can we calculate that the furthering reduction in j will divide the operations by 2? (I'm only inferring the $/2$ because I know that matchup tables have half the table redundant; I wouldn't know how to evaluate the reduction if, say, only even indices were compared against odd indices.)
Why doesn't that $/2$ matter? How do we determine the asymptote? How does $(n * (n-1)) / 2$ get reduced to $O(n^2)$? Are we just removing terms in reverse order of operations, by picking which one incorporates higher-order operations on variables (so $(n * (n-1)) / 2$ becomes $(n * (n-1))$, which becomes $(n * n)$)?
How does this generalize for $x$-tuples? If we're comparing triplets, is the complexity $O(n^3)$? Does it go up as $O(n^x)$? Is the non-asymptotic complexity still divided by 2 for orders of 3 or more? Would the numerator be $(n * (n-1) * (n-2))$? How would that be expressed generally for orders of $x$ (would it look like $(n * (n - 1) * ... * (n - (x - 1) ))$?)?


texts:
Show that the following graph is planar or not.

My first assumption is that this graph is not planar, but could not find a reasonable prove (except saying that I tried drawing it in different ways in plane, but couldn't).

We know that a graph is non-planar if it contains either K5 or K3,3 as minors. I tried getting I subdivision of this graph (by contracting some edges), but failed to get a K5 (which I think should be possible).

Any ideas anyone?


texts:
I have a matrix function, which roughly looks like this:
$$
Y_{i,j,k} = f(coef, A, B) = coef[i] * A_{i,j} * B_{i,k}
$$

def fn(coef, A, B):
    return np.einsum("i,ij,ik->ijk", coef, A, B)

Given, say, following values for coef, A, B:

coef = [1, 4, 16]
A = [
    [.11, .12],
    [.91, .52],
    [.31, .32]
]
B = [
    [.11, .12, .13],
    [.91, .72, .63],
    [.31, .52, .73]
]

3d matrix produced by function fn can be visualized like this (I'm just stacking together two slices horizontally, to make it possible to visualize a matrix in 2d):

heatmap(
    np.hstack((
        y[:,0,:],
        y[:,1,:]
    ))
)

Given a target (constant) 3d matrix, I need to find values for input parameters A and B such, that they restore element ranks along axis=0.

I was trying to solve this problem minimizing following objective function, using SLSQP implementation provided by scipy.optimize package:

$C=\sum_{j,k} |R_{jk}-\hat R_{jk}|$, where:

$R$ - given target constant matrix ranks
$\hat R$ - actual matrix ranks
$R = argsort(Y) $

def objective_fn(coef, A, B, expected_matrix):
    expected_ranks = expected_matrix.argsort(axis=0)
    actual_ranks = np.einsum("i,ij,ik->ijk", coef, A, B)
    diff = abs(expected_ranks - actual_ranks)
    return diff.sum()

It sort of works.

However, results don't always match expectations. It seems to me, that since objective ranking function is not differentiable, classic optimization using SLSQP may not be an optimal approach here.

Questions:

Are there any better ways to solve a problem like this?
Is it possible to use matrix decomposition/factorization here so
that result factor matrices have specified dimensionality?


texts: Time complexity of system of linear equations when distribution of variables are known

texts:
I have system of linear equations over binary field $GF(2)$. Suppose
there are $n$ equations with $n$ variables and equations are linearly independent.
Then we can solve using Gaussian elimination with $n^3$ complexity. We can improve this complexity using some advanced algorithms. Now suppose
we know few variables say $x_1, \ldots,x_m$ are zero with probability 0.9. Can we use
this information to improve time complexity?


texts: Formal notion of a call graph for Turing machines

texts:
To most computer programs one can assign a "call graph".
Is there a formal notion of call graphs of Turing machines?

Motivation is, that one could intuitively call a decidable language $L$ "irreducible" if every Turing machine which decides $L$ has a "trivial call graph" (Trivial here intuitively means, that the machine $M$ which decides $L$ can not call another machine $M'$ during the computation on words). This would intuitively correspond to the notion that "irreducible problems" cannot be solved by breaking them up into smaller problems, for example by divide and conquer.

Another motivation is to understand the concept of composition of Turing machines, which is "equivalent" to understand what is meant when one speaks of "subroutines" (which one could call a "submachine").


texts: What is the complexity of finding e^(A) for a Hermitian matrix A?

texts: If A is a hermitian matrix of size NxN .What is the order of no. of steps required to compute e^(A).How to prove it?


texts: Fast multiplication with a full binary $n \times 2^n$ matrix

texts:
Let $A$ a $n\times n$ matrix, and X the full matrix of $n\times 2^n$ binary vectors (you can choose the order of the columns of X).

What is the fastest way to compute the product AX?


texts:
How does an ip prefix

90.0.0.0/4

translate to

0101∗

in binary

and

10.0.0.0/2

to this:

00*

I'm trying to understand it since a while now but I am unable to derive the logic.


texts: Is there an algorithm to find the best strategy for a game?

texts:
Let,

game be the state of a 2-player, turn based game
actions game player -> [move] be a function that gets the state of a game and returns all valid moves, where a move if a function move game -> game that updates the state of the game
state game -> state returns wether a game is incomplete, won by player1 or won by player 2

Countless games such as chess and tic-tac toe can be described this ways. Is there an algorithm that, given such description, returns the optimal strategy, where strategy takes the game state as input and returns the optimal move for that turn?


texts: Union of a regular and a non-regular language

texts:
Let's say we have $L_1$ which is a regular language and $L_2$ which is not.

I understand that if $L_1 \cup L_2 = \Sigma^*$ then $L_1 \cup L_2$ is a regular language.

Does that implicitly mean that if $L_1 \cup L_2 \neq \Sigma^*$ then $L_1 \cup L_2$ is non-regular?


texts: Greedy proof: Correctness versus optimality

texts:
I am really confused after surveying a bunch of material online about correctness versus optimality proof for greedy algorithms. Some website even uses both correctness and optimal in the same sentence!

From my best unconfirmed understanding, the optimal proof uses "greedy stay ahead" where I need to show that greedy algorithm constructs a solution set that is no worse than the optimal set

The correctness proof utilizes the swapping argument to show that any difference between output set A and optimal set OPT can be eliminated by swapping the items in the optimal set.

Can someone clarify if I must only use the "greedy stay ahead" proof method for the optimal proof and not the correctness proof? And must I use the swapping argument (with contradiction) to show that swapping items in the optimal set?

Greedy stay ahead: http://www.cs.cornell.edu/Courses/cs482/2007sp/ahead.pdf

Swapping: http://www.cs.oberlin.edu/~asharp/cs280/handouts/greedy_exchange.pdf (Note that author states that this proves correctness and ends with prove optimality)

Instance where swapping was used to prove optimality, greedy stay ahead used to prove correctness: http://test.scripts.psu.edu/users/d/j/djh300/cmpsc465/notes-4985903869437/notes-5z-unit-5-filled-in.pdf


texts: What would Dijkstra's shortest path algorithm complexity be with the following data structure?

texts:
Considering $n$ number of pieces of data, what would Dijkstra's shortest path algorithm time complexity be if it was stored using a data structure with following properties?

• delete the record with the minimum value of the key (complexity $O(log n)$);

• decrease the key of some record (complexity $O(1)$);

• find the record with the minimum value of the key (complexity $O(1)$);

• insert a new record (complexity $O(1)$).

I think it would be $O(nlogn)$, but am having trouble proving it. Does anyone have suggestions? Thanks!


texts: Is the Jacobian matrix calculation process correctly on this energy function?

texts:
When I implemented the paper Dynamic Fusion published in 2015 CVPR, I came into the trouble with how to solve the energy function:
$$E(W_t, V, D_t, \mathcal{E}) = \text{Data}(W_t, V, D_t) + λ\text{Reg}(W_t, \mathcal{E})$$
Where:

Wt is a set of 4x4 transformation matrix at time t;
V is a set of 3D vertices from canonical model;
Dt is a depth map at time t;
ε is used to find Wt matrices;
Data is a point-to-plane error;
Reg is a smooth term which enforce the two adjacent transformation matrix W to be similar.

To simplify the question, I try to solve the Data term and throw away Reg term.
$$E(W_t, V, D_t, \mathcal{E}) = \text{Data}(W_t, V, D_t)$$
Here is the Data term:
\begin{align*}
r &= \text{Data}(W_t, V, D_t)= \sum_u n_u^{\intercal}\cdot (v_u-vl) \\
where,\text{v}_u &= W_t×\text{v}(u)  \\
\text{n}_u &= W_t×\text{n}(u)
\end{align*}
All the information but $W_t$ is known, use Gauss-Newton to solve the parameter:
$$\begin{gather*}
\underset{W_t}{\text{minimize}}\ r^2 \\
W_t^{(t+1)} = W_t^t - (J^\intercal J)^{-1}Jr
\end{gather*}$$
It seems to me that I need to calculate the Jacobian matrix $J$, so I expand r in matrix form:
$where\ W_t=$
\begin{bmatrix}
    1  & -\gamma & \beta & t_x \\
    \gamma & 1 & -\alpha & t_y \\
    -\beta & \alpha & 1 & t_z \\
    0 & 0 & 0 & 1
\end{bmatrix}
$v, n, vl$ are all 4x1 vector. (sorry, I don't know how to display matrix multiplication)
If I print all of the calculation, there are about 50 values containing $(\alpha,\beta,\gamma,t_x,t_y,t_z)$ to sum up for one Data term. My question is, can I directly do partial differential to the parameters $(\alpha,\beta,\gamma,t_x,t_y,t_z)$ of a $W_t$ matrix to get Jacobian matrix $J$?  It it correct to update $W_t$ by $W_t^{(t+1)} = W_t^t - (J^\intercal J)^{-1}Jr$?
I cannot believe this is a good approach because it is kind of messy, and maybe inefficient.
Please give me some advice how to solve this energy function, and I am curious why researchers only give energy function without explicit deviation on how to solve the function. Because energy function deviation is a common knowledge? If so, which course teach about it? I really want to take a course. Thanks.


texts: While proving optimality of the A* algorithm, why can we change graphs?

texts:
In the original paper of A* algorithm, A Formal Basis for the Heuristic Determination of Minimum Cost Paths, the author proved the optimality of A* in Theorem 2, page 105.

However, I cannot understand the proof. The assumption is that we have a node in $G_s$ which is not expanded by algorithm A, but in the proof we change the graph to $G_{n,\theta}$, isn't it a problem?


texts: 2D random walk. Should both dimensions be independent?

texts:
My assignment is to compare several probability distributions in random walk algorithm. I'd like to analyse it in 2D linear space to make the concept more intuitive.

What is the correct approach in selecting consecutive positions of the particle? Do I choose both coordinates independently or the step length?


texts: Parikh's Theorem: CFL's "contain" regular languages?

texts:
The first sentence of the Wikipedia article for Parikh's Theorem states:

  "Parikh's theorem in theoretical computer science says that if one looks only at the relative number of occurrences of terminal symbols in a context-free language, without regard to their order, then the language is indistinguishable from a regular language."

I'm having some trouble understanding this sentence.  I understand that unary CFL's can be described as the union of finitely many arithmetic sequences.  Does this mean that if we apply a morphism $h$ to some CFL $L$ which, say, maps $a \longrightarrow a$ and $c \longrightarrow \epsilon$ for some $a \in \Sigma$ and for all $c \in \Sigma$ with $c \neq a$, then $h(L)$ is a unary regular language?  Could someone elaborate on this?


texts:
Given is a list of numbers.

Now you build different permutations of that list while there must not be two permutations where the sum of the numbers from any point of the row to the end/beginning is equal to the sum of numbers from any point of another row to the end/beginning.

E.g.

$1,2,3,4$
$2,3,4,1$
$4,3,1,2$

is allowed, while

$1,2,3,4$
$2,3,4,1$
$4,3,2,1$

or,

$1,2,3,4$
$2,3,4,1$
$3,4,2,1$

isn't because, in (2) $2+3+4$ in the second row $= 4+3+2$ in the third and,

in (3) $1+2$ of the first row $= 3$ of the third (analog $1 = 1$ or $3+4 = 4+2+1$ if you add the numbers in the opposite direction)).

What would be an appropriate algorithm to determine the maximum number of permutations fulfilling that criteria and print out one solution with that many permutations? Is some kind of greedy algorithm useful here, or can we somehow construct a graph out of that problem?

Until now I have only some brute force algorithms for solving the problem. Thanks for any tips on the algorithm in advance :)


texts:
I'm trying to prove the following lemma:

$c$ is a positive real number and $f, g$ are functions from natural numbers to non-negative real numbers. I'm trying to prove rigorously that:

$\Omega(cf(n))$ = $\Omega(f(n))$.

I know that it is obvious but I'm trying to construct a proof that is as complete as possible. My current approach is like this:

This lemma is equivalent to saying that: $f(n) \in \Omega(cf(n))$ iff $cf(n) \in \Omega(f(n))$.

We can also restate that as:

If $t(n) \in \Omega(cf(n))$ then $t(n) \in \Omega(f(n))$.
If $t(n) \in \Omega(f(n))$ then $t(n) \in \Omega(cf(n))$.

For 1.,

$(*)$ $\exists d_1, d_2 \gt 0, \forall n \gt n_0, n_1, \forall n \in N$:

$t(n) \ge d_1cf(n)$ and $t(n) \ge d_2f(n)$

Now let's fix $d_1, d_2$ and $n_0, n_1$ to be any constants that fulfils $(*)$, such that:
$n'=max\{n_0, n_1\}$ and $d_1c \ge d_2$, using this we can say that:

$t(n) \ge d_1cf(n) \ge d_2f(n)$ and hence the 1. is satisfied because $t(n) \in \Omega(cf(n)), \Omega(f(n))$. The proof of 2. is mutatis mutandis.

Do I have a mistake in my proof, is there a better/more elegant way to prove this lemma? Shortly how can I improve this?


texts: If $Q$ reduces to $L$ then $\overline{Q}$ reduces to $\overline{L}$

texts:
The following exercise is taken from Chapter 17 of Languages and Machines by Thomas Sudkamp:

  Let $Q$ be a language reducible to a language $L$ in polynomial time. Prove that $\overline{Q}$ is reducible to $\overline{L}$ in polynomial time.

I am not sure if my solution idea is correct. Anyone knows the correct solution of this exercise?

My idea is: I use the definition of NP-complete. Q is in NP class and L is NP-complete. The function f to reducible in polynomial time Q to L, is also the function f to reducible in polynomial time notQ to notL


texts: Show that the following languages are equal

texts:
I have the following exercise:

Prove that $\{ab,aba\}^*=\{\epsilon\} \cup \{a\}\{ba,baa\}^*\{b,ba\}$.

My idea was to write the words of each of the languages in the following way,for example for the left side:

$(ab)^{n_0}(aba)(ab)^{n_1}(aba)...(aba)(ab)^{n_k}$

And then I try to make assumptions to $n_i$ and $k$. I think this is leading somewhere in the but isn't really satisfying. Can someone give me a hint on how to approach such proofs in a better way?


texts: Proper terminology in Prolog/logical programming theory?

texts:
I have a good understanding of how to program using logic languages, but I'm currently writing up a paper describing some of my work, and I wanted to ensure that I wasn't abusing the proper terminology when describing logic languages. I have a few questions:

What exactly is a predicate? How does a predicate relate to rules/facts? I.e. are rules predicates but not all predicates facts and rules?
What is a clause, and how does it relate to a predicate?
When describing how a rule is tested/proven, what is the equivalent term for "calling a function"? Do we say that the rule is called, or that a goal is called?
What exactly is a goal? Is a goal equivalent to a query?

Like I said, I have a very good understanding of how Prolog works, just not a good knowledge of the right terms to describe the right things.


texts: Analyzing the time and space requirements of a Most Significant Digit first radix sort algorithm

texts:
In a previous question of mine, I asked how efficient is the Least Significant Digit first radix sort algorithm for sorting 32-bit integers. It turns out that the bounds are:

Time: $ \Theta (\frac{32}{k}(n+2^k))$

Space: $\Theta (2n + 2^k)$

I have read various articles online about the efficiency of sorting the numbers by loking at the first $k$ most significant digits, applying counting sort, and recursively looking at the next $k$ digits of every new group that was just created. Most of the articles suggest that the MSD approach is actually as efficient as the LSD approach and some times even more efficient because it is more cache efficient. I tried to do the time and space analysis to see if that is the case, at least theoretically.

MSD is recursive so in every level, we have to work with $n$ elements in total because the union of all the groups of that level is going to give you the input set. However, we also have to take into account the buckets, and in this case the total amount of bucket arrays that we will need is going to be logarithmic. We know that the bucket has $2^k$ elements and now we need to find the total amount of levels. In the first level, we have a problem of size $n$, in the second level a problem of size $\frac{n}{2^k}$, in the i-th level a probem of size $\frac{n}{2^{ik}}$. When does the problem size become 1? When $\frac{n}{2^{ik}} = 1 $ so when $i = \frac{log_{2}n}{k}$.

We have $\frac{log_{2}n}{k}$ levels and in every level we need a new bucket array and the input, $\Theta(2n + 2^k \frac{log_{2}n}{k}) = \Theta(2n + 2^{k-1} \log_{2}n)$. We have $2n$ because during the counting phase we need that extra temporary array.

Now what about the time? The problem with the time is that for every sub problem generated, we will have to scan through the entire bucket array to find the next sub problems!

In every level however, we will only have to spend $\Theta(n)$ time for reading stuff and writing from/to the input. However I am really stuck at this point.

In the first level, we have one problem, in the second level $2^k$ problems.. so in total we have

$\sum_{i=1}^{\frac{\log_{2}n}{k}}2^{ik}$ sub problems?? So the time is:

$\Theta(2n + 2^k\sum_{i=1}^{\frac{\log_{2}n}{k}}2^{ik})$

This looks very bad compared to LSD radix sort... Am I doing something wrong here?


texts: How does CNN deal with rotation invariant pictures?

texts:
I am trying to make a CNN model . Training the image . Want to know that When we apply kernel on image and take out the features of images. That features are rotation invariant or we have to apply some rotation invariant techniques? . Few person on stack overflow says that max pooling does rotational invariance , some person says that there is rotational invariant CNN architecture . Give me solid reason that how CNN deal with rotational invariant pictures ? Elaborate the answer .
In machine learning , we do some features extraction techniques like SIFT , SURF etc. and apply some algorithm on it, their features are scale and rotation invariant . How about in CNN ?


texts: Self reduction for fully introspective lambda calculus representations

texts:
For some representation scheme $\ulcorner \cdot \urcorner$, a self interpreter $R$ is a lambda expression where $R \ulcorner A \urcorner \underset{\beta}{=} A$, while a self reducer $E$ is a lambda expression where $E \ulcorner A \urcorner \underset{\beta}{=} \ulcorner {NF}_A \urcorner$ (${NF}_A$ being the normal form of $A$).

For compact representation schemes like Mogensen-Scott encoding, I can find research on both self interpreters and self reducers (like "Efficient Self-Interpretation in Lambda Calculus" by Mogensen, 1994). However, I'm looking for research on self reducers for fully introspective representation schemes like that from Barendregt ("Self-interpretation in lambda calculus" by Barendregt, 1991).

So far, I can only find research on self interpreters for this representation. So, I would really be glad if someone knew some research papers on lambda calculus self reducers for the less compact and fast strain of lambda expression representations.


texts:
The problem of conjunctive query containment is known to be NP-Complete (originated at Chandra&Merlin 1977). Typically it's shown by reducing 3SAT or 3-colorability into this problem, and the other direction is typically proven by declaring it "trivial" (as it indeed looks trivial to see that the problem is in NP).

My question is how to practically translate the problem of query containment of two datalog rules (plain, without constraints or equalities) into the boolean satisfiability problem (not necessarily in CNF),
 and by listing the solutions of that latter problem, to see which variable substitutions would recover the containment? In other words, how to solve this problem using a SAT solver in practice?


texts:
For the sake of simplicity, lets say I have a bunch of 2d points, each have X and Y. The points are distributed somewhat randomly but not completely, they will be biased to be closer to the world center (where ever that might be, completely random) and they are likely to have some kind of a shape. You can imagine that like a bunch of stars forming a galaxy around a black hole...

Now I need to process these points (each of them have a lot of calculations) and to optimize the processing, it would greatly help if I knew whether they were north of most of the other points or south, east or west and nort/south more or less than east/west. The exact specifity of the distribution is not important, right now I'm imagining 8 sectors (NNE, NEE, SEE, SSE, SSW, SWW, NWW, NNW like on the map).

2 simple but incomplete solutions to this are:

average the position of all the points creating the center of the collection and compare the position of each point to that. This has 2 problems. For one, 99% of the points could be in a tight circular group while one point could be waay far out somewhere. This would shift the center towards that point and in the worst case scenario, the 99% of the points would only be distributed between 2 sectors. Second problem is that the distribution doesn't have to be circular, they are just as likely to show up in the shape of a giraffe. Due to the long neck on the giraffe, the Y amplitude would be much greater than X so the processing will be incorrectly biased 50% of the time between X or Y.
Also compare the x and y of each point to a global min/max creating a bounding box, the bounding box can then be used to normalize x/y distribution but would suffer even more from the one lone point that could be way out there.

So in essence, I'm looking for a way to find the average position and the bounding box without being affected by the potential flyaway. The quality of those 2 pieces of data would be defined as follows: After cutting the BB into 8 sectors like a pie originating from the center point, if a point is assigned to the NNE sector for example then

the greatest percentage of other points must be towards its south
the second greatest towards its west
the third greatest towards its east
and least amount of points towards its north

Any ideas?


texts: How do I call a system like a grammar, but where a rule has to be applied to all matches at once?

texts:
For example, given rules $\{ a \to x, a \to y \}$ and input $aa$ , I am usually allowed to derive strings $\{ xx, xy, yx, yy \}$. I would like to restrict this to only performing "consistent" rewrites, so that the language would be like $\{ xx, yy \}$. It is evidently possible to synchronize rewrites in distant parts of a sentence within the usual formal grammar setting, but I wonder if this possibility is better explored under a different name or in a different arrangement.

I notice that context-sensitive grammars pose trouble with this "consistency" condition. For example, given a ruleset $\{ aa \to x\}$ and initial string $aaa$, I am not sure if I should allow anything to be derived. Then again, it is entirely possible that only some rules, and specifically some context-free rules, may be enhanced with consistency.

I am rather sure the system I have in mind defines a language, and even that I could with some thinking propose a formal way to rewrite a given grammar so that some select context free rules are made consistent. But I wonder if this is actually widely known under some other name.


texts: Improvement Heuristics for Asymmetric TSP

texts:
i have been solving the Time-Dependent Traveling Salesman Problem using
an Ant Colony Optimization.
Upon reading the ACO papers, there are several reminders which state
that ACO performs best with daemon actions - improvement heuristics.

In the classical TSP, the most common improvement heuristic used is the k-opt exchange,
which works particularly well because one does not need to calculate the whole
solution cost, but only differentials on the updated solution.

When the problem is assymetric (which is the case for the time-dependent variation), this is not the case.

I wonder if there are usefull improvement heuristics which can be used as daemon actions to the Assymetric/time-dependent TSP.

I already did some research on this subject, but found no interesting material.


texts: How to apply a 1-qubit gate to a single qubit from an entangled pair?

texts:
Reading about superdense coding I came upon a calculation I can not understand.

We have an EPR entangled pair of qubits $\frac{1}{\sqrt2}(|00\rangle + |11\rangle)$ and we want to apply a Pauli X gate to the first of the entangled qubits. On wikipedia, there is an example showing that such an operation would lead to the state $\frac{1}{\sqrt2}(|10\rangle + |01\rangle)$. I can't see an intuition behind it. I know that the Pauli X gate operates as a quantum NOT, but at the same time I do not know how to write it algebraically.

How can a single qubit from an entangled pair be represented? Is it $\frac{1}{\sqrt2}(|0\rangle + |1\rangle)$ for the pair above? And if so, why does the Pauli X gate change it at all (if we wrote the operation using matrices, the qubit would be represented as $\left[\frac{1}{\sqrt2} \frac{1}{\sqrt2}\right]$, which multiplied by the Pauli X gate matrix would not change at all...)


texts: Busy-Beaver-like question for WHILE-Programs (Theoretical CS)

texts:
So this is exam-task is called "Busy WHILE-Programs"

In our lecture it was proven that WHILE-Programs are turing-complete. In short a WHILE-Program only allows the following:

Variables             x1,x2,...  (initially all 0 and can only be positive)
Constants c           0,1,2,3,...
Assignment            xi := c
Addition/Subtraction  xi := xj + c, xi := xj - c
while-loops           while(xi != 0) { ... }

In part (a) of the task we should show, that every WHILE-program can be simulated by a WHILE42-program.

A WHILE42-program is a WHILE-program where all constants can only be 42 or lower.

Now the task where I need help (I try to translate from german):

Let WHILE42(n) be the subset of all WHILE42-programs, with no more than n instructions/commands. The function g(n) returns the biggest value, a terminating program from the WHILE42(n)-subset assigns any of it's variables. Prove or disprove the following statement:

The function g(n) is not computable

I have two routes with the second being probably a valid answer:

First: My intuition tells me it is not computable and that I should show (like in the Busy-Beaver-example) that if it would be computable, it would solve the Halting-problem. Which would show, that it can't be computable.

My thought-process so far:

If g(n) is computable, I could take any TM M_1 and transform it in a WHILE42-program W_1 with n_1 commands.
I could then calculate g(n_1).

Then I need to show that from this value g(n_1) I can derive somehow an upper value of how many steps I need to simulate M_1 to decide if it will terminate or run forever.

But I struggle to determine what this upper value is.

Second: Here my intuition tells me, that this is not how it is expected to be solved. So I would prefer a solution to the first one, if there is any

If g(n) is computable, there is a TM M_g that calculates g(n). M_g could be transformed in a WHILE42-program W_g with n_g commands.

Since W_g would for any n at some point assign the highest value for this WHILE42(n)-subset, g(n_g) can not compute a value. For any value k  g(n_g) could return, it would be possible to construct a terminating WHILE42-Programm that adds the value 42 k-times to a variable which would grow larger than k.


texts: what is the Recent Nature Inspired Algorithm for Optimization?

texts: I'm into designing a recommender system for movie database and for effective optimization.I suggested the idea of using particle swamp optimization ,but my professors need recent algorithms,can any one suggest recent nature inspired algorithms for optimization.(After Cuckoo Search Optimization).


texts: Eliminating ambiguity when referring to complexity in cases of multiple parameters and/or multiple results

texts:
When looking through a few questions at StackOverflow¹ that all ask for algorithms to select k distinct random numbers out of N, I've become confused about how to compare the answers in terms of time and space complexity.

each algorithm has two parameters, N and k
and returns k elements

In terms of Big O notation, all the algorithms worth speaking of are O(N) overall.

But there are still major differences between them:

Some require ~k steps while others ~N
Some can return elements one by one while others only return them all at the end.
Most require all the k (or even N) elements to be present in memory at once, but some are able to return each one in sequence and discard it.

Now to unambiguously put these distinctions when describing each algorithm's complexity? More specifically, I'm interested in the standard way it is done in formal papers so as not to reinvent the wheel.

¹https://stackoverflow.com/questions/196017/unique-non-repeating-random-numbers-in-o1/16097246, https://stackoverflow.com/questions/158716/how-do-you-efficiently-generate-a-list-of-k-non-repeating-integers-between-0-and-n, https://stackoverflow.com/questions/2394246/algorithm-to-select-a-single-random-combination-of-values, https://stackoverflow.com/questions/54059/efficiently-selecting-a-set-of-random-elements-from-a-linked-list


texts: Is every subset of a decidable set, also decidable?

texts:
Is it true that if A is a subset of B, and B is decidable, than A is guaranteed to be decidable?

I believe it would be true because all the subsets of B should also be decidable making A decidable. I'm not sure if my thought process is right or if there's a easier more intuitive way to explain this.


texts: Relationship between formal system and formal languages

texts:
In a course of computer science it is common to study the hierarchy of formal languages, grammars, automata and Turing machines. I wonder what is the relationship of these objects with formal systems.

For example, lambda calculus is said to be a formal system.  Would its grammar also be considered a formal system?


texts:
How do we uncurry functions when they are polymorphic? For example, is it possible to uncurry the following types? If so what is the uncurried type?

$\forall X. X \rightarrow int \rightarrow X$ ?
$int \rightarrow \forall X. X \rightarrow X$ ?
$int \rightarrow \forall X. X \rightarrow int \rightarrow X$ ?


texts: Proof that finite automata is closed under intersection

texts:
I'm looking at a proof that says that:
If $M_1=(Q_1, \Sigma , q_1, A_1, \delta)$ and $M_2=(Q_2, \Sigma , q_2, A_2, \delta)$ are two finite automata(FA) then $M=M_1 \cup M_2$ is also an FA. We define $M=(Q, \Sigma , q, A, \delta)$ where $Q=Q_1 \times Q_2$, $q_0=(q_1,q_2)$ and $\delta((p,q),\sigma)=(\delta(p,\sigma),\delta(q,\sigma))$.

I'm just having one problem. We have to prove that $\delta^*((p,q),x)=(\delta^*(p,x),\delta^*(q,x))$. (x is a string in $\Sigma^*$)
We do it by induction. I've already proven the base case, and I'm now trying to prove it holds for $x'=x\sigma$. This is what I've gotten so far:

$\delta^*((p,q),x')=\delta(\delta^*((p,q),x),\sigma)=\delta(\delta^*(p,x),\delta^*(q,x)),\sigma)$

I don't really know how to proceed from here. Can someone help?


texts: Prove that the depth function of a Binary Search Tree is $O(\log n)$ on average

texts:
I am struggling with this question because I am not sure how to see that a depth function is $\mathcal{O}(\log n)$ on average when it clearly traverses through the whole tree which should make it $\mathcal{O}(n)$:

depth(tree):
    if tree is a leaf:
        return 0
    else:
        return 1 + max(depth(tree.left_subtree), depth(tree.right_subtree))

It goes through each and every node. Could someone explain to me how finding the depth of a BST can be done is $\mathcal{O}(\log n)$ on average?


texts: What are staged functions (conceptually)?

texts:
In a recent CACM article [1], the authors present an implementation for staged functions. They use the term as if it was well-known, and none of the references looks like an obvious introduction.

They give a short explanation (emphasis mine and reference number changed; it's 22 in the original)

  In the context of program generation, multistage programming (MSP, staging for short) as established by Taha and Sheard [2] allows programmers to explicitly delay evaluation of a program expression to a later stage (thus, staging an expression). The present stage effectively acts as a code generator that composes (and possibly executes) the program of the next stage.

However, Taha and Sheard write (emphasis mine):

  A multi-stage program is one that involves the generation, compilation, and execution of code, all inside the same process. Multi-stage languages express multi-stage programs. Staging, and consequently multi-stage programming, address the need for general purpose solutions which do not pay run-time interpretive overheads.

They than go on to several references to older work allegedly showing that staging is effective, which suggests that the concept is even older. They don't give a reference for the term itself.

These statements seem to be orthogonal, if not contradictory; maybe what Rompf and Odersky write is an application of what Taha and Sheard propose, but maybe it is another perspective on the same thing. They seem to agree that an important point is that programs (re)write parts of themselves at runtime, but I do not know whether that is a necessary and/or sufficient ability.

So, what is staging respectively are interpretations of staging in this context? Where does the term come from?

Lightweight Modular Staging: A Pragmatic Approach to Runtime Code Generation and Compiled DSLs by T. Rompf and M. Odersky (2012)
MetaML and multi-stageprogramming with explicit annotations by W. Taha and T. Sheard (2000)


texts:
Is the VC dimension of an origin-centered circle 1 or 2?

It seems to me that the VC dimension of an origin centered circle should be 1, because for two points with distances from the origin r1 <= r2, r2 will never be able to be labeled 1 without r1 also being labeled 1, so the r1 = 0, r2 = 1 labeling could never be possible.

However, this and this both say that an origin-centered circle has VC dimension of 2.


texts: Would $\sf RP = NP$ imply $\sf NP = coNP$?

texts:
If $\sf RP = NP$ then the hierarchy collapses to its second level (by the Karp-Lipton theorem). But what about $\sf NP$ and $\sf coNP$?

I tried to prove that $\sf BPP$ is contained in $\sf NP$ (the other direction is trivial if $\sf RP = NP$) but to no avail, and I'm not even sure that it's true.

What do you think?


texts:
$n$ professors go to a conference and have to sit together at a table. See illustration below for $n=8$

Each professor has people they like to sit next to and people they do not want to sit next to. Given a $n\times n$ (non-symmetrical) matrix $M$ where $M_{ij}$ gives the score assigned by professor $i$ if s/he is made to sit next to professor $j$ and $M_{ii}=0$, the goal is to output a symmetrical indicator matrix $I$ where $I_{ij} = 1$ if professor $i$ is sitting next to professor $j$ such that $\sum M.*I$ is maximized (I used Matlab notation here to denote elementwise multiplication of two matrices). How can we find this optimal arrangement? Lets assume we are dealing with even $n$.

From my side I spent some time calculating the total # of possible arrangements for given $n$ and arrived at this formula:
$\frac{C^n_{n/2}}{2}(\frac{(n/2)!}{k})^2$
where $k = 1$ if $n = 2$ and $k = 2$ otherwise.

I wrote the following program to calculate the # of different arrangements for given value of $n$ (assume even $n$) according to above formula.

public static void main(String[] args) {
        for(int i = 2; i <= 10; i += 2)
        {
            System.out.printf("%d\t%s\n", i, foo(i).toString());
        }
    }

    static BigInteger foo(int n)
    {
        BigInteger t1 = binomial(n, n/2).divide(BigInteger.valueOf(2));
        BigInteger t2 = factorial(n / 2);
        BigInteger t3 = n >= 4 ? BigInteger.valueOf(4) : BigInteger.ONE;
        return t1.multiply(t2).multiply(t2).divide(t3);
    }

    // http://stackoverflow.com/a/2929897/147530
    static BigInteger binomial(final int N, final int K) {
        BigInteger ret = BigInteger.ONE;
        for (int k = 0; k < K; k++) {
            ret = ret.multiply(BigInteger.valueOf(N-k))
                    .divide(BigInteger.valueOf(k + 1));
        }
        return ret;
    }

    static BigInteger factorial(int n) {
        BigInteger ret = BigInteger.ONE;
        for (int k = 2; k <= n; k++) {
            ret = ret.multiply(BigInteger.valueOf(k));
        }
        return ret;
    }

Output:

2   1
4   3
6   90
8   5040
10  453600


texts: When an ISAM index is built, how is the number of leaf nodes per index node (the "fan-out") calculated?

texts:
I asked this question on DB.SE but it didn't get any traction, so I'll ask it here...

The following statement is in the Ramakrishnan text (2nd ed. page 252):

(emphasis in bold is mine)

  The non-leaf pages direct a search to the correct leaf page. The number of disk I/Os
  is equal to the number of levels of the tree and is equal to $log_FN$, where $N$ is the
  number of primary leaf pages and the fan-out $F$ is the number of children per index
  page. This number is considerably less than the number of disk I/Os for binary search,
  which is $log_2N$; in fact, it is reduced further by pinning the root page in memory. The
  cost of access via a one-level index is $log_2(N/F)$. If we consider a file with $1,000,000$
  records, $10$ records per leaf page, and $100$ entries per index page, the cost (in page
  I/Os) of a file scan is $100,000$, a binary search of the sorted data file is $17$, a binary
  search of a one-level index is $10$, and the ISAM file (assuming no overflow) is $3$.

Question: How is the value of F calculated when the index is constructed?

From the example given it seems the structure will be:

root node containing 1,000 pointers to index nodes
one level of 1,000 index nodes, each containing a pointer to 100 leaf nodes
100,000 leaf nodes, each containing ten records

Assuming that is the correct understanding of what he describes, what determines the value of $F$ when the index is built? Is it calculated in such a way that the index will have exactly 3 levels and so $F$ is set to ensure we can reach all leaf nodes in 3 steps? This doesn't seem to be the case since he has a diagram elsewhere in the book of an ISAM index with more than 3 levels.

So then what dictates the value of $F$? i.e. what keeps it from being 1K or 100K?


texts:
I have my end of year exams next Thursday. I'm generally doing fine but I am having some major issues with this strand of my course, this has to be the biggest issue I have. So, here is the question in the past paper:

  You have been tasked with determining the validity of a
    manufacturer’s claim that their widget is more reliable than their main
    competitors’ widgets.

  In order to verify this assertion you test a sample of 25 widgets from
    the manufacturer’s range and find a mean pass rate of 992 per 1000
    with a standard deviation of 15 per 1000.

  Previous studies have shown that the mean pass rate of all other
    widgets on the market is 979.4 per1000.

  In order to increase the confidence in the making a decision about
    the null hypothesis you choose a 99.5% confidence level and find the
    corresponding t-table value to be 2.947.

  State the null hypothesis.

I have revision notes in front of me, but I just don't understand what this question is actually asking. Am I just writing down my own hypothesis, or do I need to use this equation?

  H0; μ
    H1; μ

If anyone could go through step by step for what I need to do, then that would be fantastic. My notes are just confusing!


texts:
Given a function E(x) which outputs 0 is x is even and 1 is x is odd, prove that this function is primitive recursive.

My attempt is as follows

$$ E(x) = x \mod 2$$
To show that any function is primitive recursive, it must be obtained by composition and recursion from the initial functions $s(x) = x + 1; n(x) = 0$ and $u_i^n(x_1,x_2 \ldots x_n) = x_i$
We know that
$$ E(0) = 0 $$
$$ E(x+1) = (E(x) + 1) \mod 2 $$
By using induction -
$$ E(n) = n \mod 2$$
Let $n = 0$
$$ E(0) = 0$$
which is easily shown to be primitive recursive since it is an initial function of the $PRC$ class.
Assuming that this is true for $n = k$.
$$E(k) = k \mod 2$$
Taking $ n = k+1 $
$$ E(k+1) = (E(k) + 1)\mod 2 $$

But at this point, I do not know how to proceed.


texts: Interactive example of Dynamic scoping and evaluation order of expressions

texts:
Given the following (arbitrary language, although I think it is close to Algol 60) program:

program main;                               // A main parent level
  var i : integer;                          // A 'global' variable

  (* Note that all parameters are passed by value here *)

  function f1 (j : integer) : integer;      // A Child function
  begin { f1 }
    i := i + 3;
    f1 := 2 * j - i;
  end; { f1 }

  function f2 (k : integer) : integer;      // Another Child function, same level as f1
    var i : integer;                        // Here, there is a variable that is declared
  begin { f2 }                                 // but no value assigned
    i := k / 2;
    f2 := f1(i) + f1(k);
  end; { f2 }

begin { main }                              // Running/Calling/Executing the code
  i := 8;
  i := i + f2(i);
  writeln(i);
end. { main }

How would you trace the values of variables throughout the program when it is interpreted using Dynamic scoping of free variables, when the arguments appearing in expressions  are evaluated left to right, and when they are evaluated right to left, so that the user can watch what happens

I have created a JS plnkr for Static Scoping with Left to Right evaluation
and another for Static Scoping with Right to Left evaluation.
Feel free to adapt these answers (if possible) for Dynamic Scoping, with L->R and R->L evaluation.

I chose plnkrs because I knew I could get the Static/lexical side using JS, but am unsure of how to make it happen dynamically or in another interactive environment (preferably not one I have to install).

I learn a bit slower on some problems like this where the values are asked of the output, but don't show the value states throughout the program, and trying to get a better understanding, especially in an example I can play around with interactively, as the book examples are really bad.  In the code above, it also gets challenging, because it appears that the variable i in line 2 is allocated, but would be undefined.   But that may be my imperative/functional brain making it more complicated than it is...


texts: Terminology for a graph obtained from another by adding edges

texts:
$H$ is a supergraph of $G$ if it can be obtained from $G$ by adding, edges, vertices, or both.

Is there a standard terminology for a graph that can be obtained from $G$ only by adding edges?


texts: Number of induced paths in an interval graph

texts: Let $G$ be an interval graph. For any two vertices $u,v$ in $G$, how many induced paths are between them in $G$? Is it polynomial in terms of the number of vertices in $G$?


texts: Data structure for identifying elements while keeping track of relation

texts:
I'm looking for a data structure representing a finite set $I$ and a $d$-relation $R \subseteq I^d$ such that the following operations can be implemented efficiently:

Add a new element $i$ to $I$.
Identify elements $i, j \in I$, i.e. take the quotient set $I' = I_{/ i \sim j}$ and take for $R'$ the obvious relation on $I'$ induced by $R$, i.e.
\begin{equation}
R'([i_1], \dots, [i_d]) \iff \exists j_1 \sim i_1, \dots, i_n \sim j_n: R(j_1, \dots, j_n)
\end{equation}
where $[-]$ denotes equivalence class under $\sim$.
For example, if $d = 2$ and $k \neq i, j$, then $R'([i], [k]) \iff R(i, k) \lor R(j, k)$.
Check whether elements $i, j \in I$ are equal/represent the same element.
Insert a tuple $(i_1, \dots, i_d)$ into $R$
Check whether a tuple $(i_1, \dots, i_d)$ is in $R$.

If it weren't for the relation $R$, then a union-find data structure would be a perfect solution, supporting 1, 2 (minus the relation part) and 3 in essentially constant time. On the other hand, a hash table would support 4 and 5 in constant time. I don't see a way of combining those data structures without blowing up some step to $O(\mathrm{max}(|R|, |I|))$ though.

Bonus points if the data structure can be adapted to support snapshots, i.e. saving the current $(I, R)$ and reverting back to it later efficiently.


texts: Round-Robin Scheduler - What exactly is the quantum time used for?

texts:
Suppose you have three stages for a job:

Creation stage = the job gets created

Executing stage = the job is executed/served

Finishing stage = the job is "marked" as finished.

Now, say the quantum time for a round-robin scheduler is 100ms. From what I understand, the 100ms is spent on the executing stage. Am I right to assume that the creation and finishing stage is OS stuff, and what really the quantum time is used on, is the executing time?

I'm a bit confused because I'm trying to write a model, and for the scheduler I'm trying to figure out whether "job 1 was created" counts as a "turn" or consumption of quantum time for that given job. So, if "job 1 was created" happens, then it switches to "executing job2".

I might be mixing up OS tasks and CPU execution here.


texts: Is in-place run length encoding possible in O(1) space given that the output is shorter than the input?

texts:
This is inspired by a problem from here. This is the approximate form of the problem:
Given a string like "aaaa777cbb" (10 symbols long), run length encode it in-place to a string like "a473c1b2" (8 symbols long). You are guaranteed that the input will always be longer than the output.
The precise form of the problem is:

You are given an ordered list $L$ of symbols from a set $S$. Any symbol from $S$ may appear in the list.
$S$ contains all the positive integers up to and including $|L|$ (the length of $L$) and also some other symbols.
Rules of manipulating the input in-place

You can replace one symbol in the list with another
You can trim the list to a length of your choice by removing symbols from the end
You cannot insert symbols

You must overwrite the list of symbols with it's run-length-encoding representation and trim it to length so that it includes only the run-length-encoding representation.

The run-length-encoding representation replaces each series of 1 or more of the same symbol in the input with that symbol followed by the symbol representing the number of occurrences of the previous symbol.

For example: $[a, a, a, a, a, a, a, a, a, a, 7]$ becomes $[a, 10, 7, 1]$ meaning "$a$ ten times followed by $7$ one time"
Note that the length of the output list is always even

You are guaranteed that the length of the input list is always larger than the length of the output list

You must do this with $O(1)$ additional working memory

Each "word" of working memory contains $log_2 |S|$ bits (put another way, words may be constructed which store constant amounts of information, the position of any element in the input, or any symbol from the input)

Intuitively I don't think this is possible. The solutions provided on the original site seem to break on strings like "abccccc" (length 7) where the output should be "a1b1c5" (length 6), since they start by overwriting "b" with the "1" from "a1" before they have even checked which symbol is in the 2nd position.
I have thought about trying to start by finding the compressible runs of letters (2 or more of the same letter), but I don't know how to tell which symbols are already processed and which are from the original input without using some sort of memory that which would grow with the size of the input (like a bitmap of processed areas) and therefore put me in violation of the $O(1)$ space requirement.
I consider acceptable answers to be proofs that this problem either is or is not solvable in $O(1)$ space.


texts: offline Bin Packing problem with multiple size bins

texts:
As per my research on stack overflow communities, This is probably known as cutting stock problem / multiple Knapsack problem (a variant of the bin packing problem) which is NP hard.
here are the constraints:

there are two integer arrays one has lengths (already defined), the other has
the bin sizes (already defined),
lengths needs to be packed in any combination of bin of any size, the desired solution would be with least wastage of total bin used
bins but off course but collective wastage of all the used bin must be least
the lengths and bin sizes are fixed and will be provided by another process before computation start

based on First Fit Decreasing (FFD) algorithm i am able to pack bin of a fixed size but the wastage is not minimum. Refer to the results in images achieved so far... One can get optimum results when mix size bins are used. What would be the algorithm in case of multiple bin utilized ?
Data:
Lengths: {2385,2385,2385,2385,2385,2385,1260,1260,1260,1260,1260,1260,337,337,210,210,125,125,108,108}
Bins: {3000,5000}

Results based on FFD algorithm of bin packing
When i use bin length of 3000 only the total wastage is 3434

When i use bin length of 5000 only the total wastage is 1570

When mix length bins (3000 and 5000) are used the total wastage is 570, the problem is what would be an
optimum algorithm to achieve this or even better than this ?


texts: What is the period of N xored identical random number generators, with differing seeds?

texts:
This question is a kinda spin off from Why do we not combine random number generators?

If for example we had N identical type random number generators, with N different seeds, what would the period be if their outputs were xored together?  Would it be period, N x period or period (power N)?

So a numerical example would be:

2 linear feedback shift registers of 10 bits.

1 LFSR's period = 1023.

2 xored LFSRs' period = 1023, 2046 or 1046529?

(I have a sense that it's period but I can't overcome that fact that the state size is so much bigger.)


texts: How often is Prolog/ASP used in non-research areas?

texts:
I've just recently found out about KRR (Knowledge representation and Reasoning) and ASP, not hearing a thing about them before (except a bit about prolog). I've read a bit about them and one of their primary usage seems to be AIs.

My question would be how widely used ASP or other declarative languages are, is there some frequently used program using them (like search engines?) or is it mostly for research purposes? What may be the reason they are not so well known? Is it because AI-development belongs to a more "advanced level" of programming?


texts: Is the Shakespeare Programming Language Turing complete?

texts:
I was reading about tge Turing machine. I also came across with the Shakespeare programming language. After trying to understand the basics of the PL, I thought that it must be non-Turing complete. On some page I found out that I was wrong and Shakespeare is actually "turing complete".

I didn't find how can I create while loops or recursive calls in Shakespeare so I can't understand why it us Turing complete.

Will be glad for some explanation.


texts:
everywhere I've searched it says that the minimal period of an LFSR given by a characteristic polynomial $c(x)$ is the least number $r \in \mathbb{N}$ that: $$c(x)|(x^r-1)$$ but how do I prove it's correctness?
I've tried o prove it like that:
given $c(x)$ the characteristic polynomial and $h(x)$ theinitial state polynomial, I'll denote the minimal period with $\pi$ then:
$$
{h(x) \over c(x)}=G(x)= \sum^\infty_{k=0}a_kx^k=\sum^{\pi -1}_{k=0}a_kx^k(1+x^\pi+x^{2\pi}...)={\sum^{\pi -1}_{k=0}a_kx^k \over 1-x^\pi}
$$
and I'm not sure where to go from here


texts: What should I do if I think I wrote an algorithm that is _generally_ faster than Atkin Sieve?

texts:
I've been having some fun with prime numbers. A few months ago I sat down to see if I could write something that could compete with Atkin Sieve and ended up with an algorithm that, on my local tests on my RAM-restricted computer provide results where my algorithm is either close to Atkin or it can be way faster (depending on the number of prime numbers that are being discovered).

I set up a repo with the "basic" algorithm and then another version that uses BigIntegers with an expanding array so that memory could expand as much as necessary (trying not to go on RAM-hungry implementations using Collections of BigInteger and such).

This is waaaay out of my area of expertise... let's say, I'm just having fun while learning so I think I need people that have more experience on the field of performance testing and also guidance from people with research background to guide my steps if it's worthy.

So.... how about you take a look at the code and run some local tests? Perhaps offer ideas to improve performance? Or how to know if I should turn this into a serious research project?

Branches

Master has a basic implementation that works on boolean arrays.
bigint has basically the same implementation using BigInteger (and Collections)
bigint-selfgrowing: bigint implementation using an enormous boolean array (grows as needed)
bigint-selfgrowing-lessmemory: because of the nature of the data that my algorithm handles, for every 6 numbers, only 2 of them have to be kept so I modified the arrays to not care for the other 4 numbers (which allows for a theoretical 66% memory reduction but with a noticeable performance hit... plus Atkin is still using the original Enormous Boolean Array so it's not comparing oranges to oranges anymore... still, worth a look)

All branches have 3 classes that can be used to easily run tests of the pattern sieve (my sieve) against atkin. They can get 1, 2 or 3 parameters:

Single parameter: run single test with so many numbers
Two parameters: run tests starting from first parameter up to second parameter increasing number of primes by the first parameter each run
Three parameters: Run tests from first parameter up to second parameter increasing primes by the the third parameter each run.

For each test, it will report how many ms/ns/us it took to run (depending on the java class that was called) in csv format (and will also provide a little human-readable output on stderr, just in case).

https://github.com/eantoranz/patternsieve

Thanks in advance.

PS I used an implementation of Atkin that I found on internet (credits provided on commit, code and on stderr when running) so it might not be the best out there... if you know of a better implementation, let me know.


texts: Algorithm for recovering paired lists when elements are broken

texts:
I am trying to solve an algorithmic problem.  I came from http://math.stackexchange.com upon an advise that this forum would be a better place to ask this.

I would like to hear your advice on where to search for hints.  If my problem has got a name, I would like to know what it is called in the field, and what I should learn to solve it.  Any partial suggestion would be welcome.  Also if there is another forum that fits my question better than here, I would be happy to hear that too.

A description of my problem is as follows.  Suppose you have a number of pairs of objects.  Let $X$ be the first list of objects and $Y$ be the second list. Assume $X = Y$ in a sense they share the same list of objects.

Now, objects in both lists are "broken" into pieces; Each element $x \in X$ is decomposed to $x_1, x_2,...$.  The same happens for $Y$.  As a result, what you have is two sets $X', Y'$, which contain the broken pieces of the original objects.
The task is to recover the original objects in $X$ and $Y$ from $X'$ and $Y'$.

Here is an example where objects are strings.
Suppose $X = Y = [apple, banana]$, and the strings are decomposed as:
$X' = [ban, le, ana, app]$ and $Y' = [na, ple, ap, na, ba]$.  I would like to recover $banana$ and $apple$ from information $X'$ and $Y'$.

Does this problem have a name?  Or, what do you think the good things to learn for me to study this type of problem?


texts: Asymptotic bounds on number of 3SAT formulas with unique solutions

texts:
A set is sparse if it contains polynomially bounded number of strings of any given string length $n$ otherwise it is dense. All known NP-complete sets are dense. It was proven that P=NP if and only if there is a sparse NP-complete set (under Karp reduction).

I would like to find the density of uniquely satisfiable 3SAT formulas. Is it super-polynomially dense or exponentially dense? What is known about the asymptotic lower bound on the number of 3SAT formulas with unique solutions?


texts: How append, prepend, and generally insertAt work in RRB-tree

texts: I read the paper about Relaxed Radix Balanced trees (RRB trees) and am trying to implement them. What I can't get is how insertion at an index should be performed step by step. Can anyone proficient in this data structure describe this procedure?


texts: What is the minimal degree $d$ required for a B tree with $44*10^6 $ keys so that it's height is less than or equal to $5$

texts:
What is the minimal degree $d$ required so a B - tree with $44*10^6$ keys will have a height $h$, such that $h\leq 5$

My attempt was to build the tallest tree possible with minimum degree $d$ and $n = 44,000,000$ keys and then solve for $d$. That would mean any other tree with a minimal degree $d'$ such that $d'\geq d$ and $n$ keys will be shorter than the one I built:

at depth 0 , we have the root and that's $1$ node

at depth 1, we got exactly $2$ nodes

at depth 2, since we're going for the tallest tree each node will have a minimal number of keys so $d-1$ keys each, that means $d$ children each so a total of $2d$ nodes.

at depth 3, following the same reasoning , $2d^2$ nodes.
...

at depth $h$, there are $2d^{h-1}$ nodes

total number of keys is :

$n = 1+ (d-1)\sum_{k=0}^{h-1} {2d^k} = 1 + (d-1) \frac{2(d^h-1)}{d-1} = 2d^h-1 = 44*10^6 $

so:

$2d^5-1=44,000,000 $

$d= 29.4 $

$d\geq 30$

is that even correct ?


texts: How likely is it that a computer miscalculates 1+1?

texts:
Of course, normally a fully-functional computer will calculate 1+1=2. However, the physics governing the behavior of a chip is quantum mechanical. So in principle there is a certain probability that something goes wrong and we get the result 1+1=x where x≠2. In my opinion this probability should get bigger the smaller the chips are becoming.

So the question is: How likely is this event? Can one give an order of magnitude?

P.S. I'm not talking about quantum computing, just "standard" computers nowadays everyone has on their desk.


texts: Implementation of Fourier Online Gradient Descend

texts: According to the algorithm, is it true that I have to sample 1,...,D u's from the normal distribution with mean 0 and variance 1 (not sure what sigma square here refers to)? And then I have to construct the z as shown in the algorithm. However, I wonder how this will speed up gradient descend because creating sin and cos in alternatingly in code will probably take a very long time(in python). Does anyone know what is the proper and efficient way to implement this algorithm? Thanks


texts: How to prove that the reversal of the concatenation of two strings is the concatenation of the reversals?

texts:
Given languages $L_1$ and $L_2$, how do we prove that
$$(L_1L_2)^{\mathrm{rev}} = (L_2^{\mathrm{rev}})(L_1^{\mathrm{rev}})\,,$$
where ${}^{\mathrm{rev}}$ denotes reversal?

I think using mathematical induction, it can be shown true for two languages $L_1$ and $L_2$ of length $1$ each and then do induction using one of the lengths and then repeat with the other length.
Is there any other way of proving this in a simpler way without making it too big with induction method?


texts:
I am trying to learn Lambda calculus from here

and while trying to solve some problems, I got stuck. I was trying to solve the following problem (page 14, excercise 2.6 part (i):

Simplify $M \equiv (\lambda xyz.zyx) aa (\lambda pq. q)$.

My evaluation using the beta rule reduces it to $(\lambda z. z)$ as follows:
First I replace occurences of $x$ in $M$ by $aa (\lambda pq. q)$, and then since there are no occurences of $y$ in the resulting $\lambda$ term, the expression simply evaluates to $(\lambda z. z)$.

Is my reasoning correct? (Since there were no solutions to these notes, I want to ensure my understanding is correct. Any corrections, will be much appreciated! Thanks in advance.


texts: Proving grammar only generate strings that is multiple of 3

texts:
Hello I have an exercise for homework and I was hopping to get some hints in order to solve it.

num-> 11 | 10 num' 01 | num 0 | num num
num'-> 00 num' | 1 num' | ε

I need to prove that my grammar produces only strings that is multiply of 3.
What i know is:

11 is 3 so no problem there
adding 0 to the end of the num is irrelevant because it will be still dividable by 3.
same with num num
I know that is something about the 10 num' 01 pattern. (1001 is divided by 3)

I was thinking to try to prove it with sums (this is how i solve a previous exercise). However i am not sure that i can solve it that way.


texts: Prove/disprove the existance of a data structure that has O(log N) inserts/deletes and get k-th largest element in O(1)

texts:
Consider a sorted array. We can get the $k$-th largest element in $O(1)$, but insertions and deletions cost $O(n)$.

Consider an order statistic tree. Insertions and deletions cost $O(\log{N})$, but getting the $k$-th largest element costs $O(\log{N})$.

I can't think of any way to create a data structure with the best of both worlds, that is that we can get the $k$-th largest element in $O(1)$, and insertions and deletions cost only $O(\log{n})$, but I can't prove that it isn't possible.

So far, my idea for a proof basically revolves around it being impossible to have $O(1)$ accesses without an array. We can't have a tree or a linked list without the time complexity becoming dependant on the number of elements. Then, if an array is required, the only way to insert an element in less than $O(\log{n})$ time is to add it to the end or to the front (which is $O(1)$). But if we do this, we can't maintain the sorting of the list. So we need another data-structure which maps a given $k$ to its real index in the array in $O(1)$ and which supports insertions/deletions in $O(\log{n})$. The only difference between this inner data structure and the outer one is that the elements in the inner array will be each number from $0$ to $n$, but I don't think that matters and now I'm just back where I started!

What's the answer?


texts:
I'm trying to backfill missing CS knowledge and going through the MIT 6.006 course.

It asks me to rank functions by asymptotic complexity and I want to understand how they should be reduced rather than just guessing. The question is to reduce this to big-O notation, then rank it:

$$f(n) = n \cdot \sqrt{n}$$

I see in this answer that $\sqrt{n} \gt \log{n}$

I don't understand how to think about the complexity of $\sqrt{n}$.

What is the complexity class of $\sqrt{n}$?

What is the relationship between $\sqrt{n}$ and $\log{n}$?


texts:
Draw recursion trees and use them to find big theta bounds on the solutions to the following recurrences. For each, assume that T(1) = 1 and that n is a power of the appropriate integer. ex) T(n) = 8T(n-2) + n

There are multiple equations that I have to do with the above directions. I am lost on finding big theta bounds. I would prefer examples since I learn easiest that way. Thank you for any help!


texts: How to recognize a STRIPS planning problem has no solution?

texts:
Strips –Stands for STanford Research Institute Problem Solver (1971).

STRIPS Pseudo code -

STRIPS(stateListstart, stateListgoals)
1.Set state = start
2.Set plan = []
3.Set stack = goals
4.while stack is not empty do
     1.STRIPS-Step()
5.Return plan

STRIPS-Step()
switch top of stack t:
1.case this a goal that matches state:
    1.pop stack
2.case this an unsatisfied conjunctive-goal:
    1.select an ordering for the sub-goals
    2.push the sub-goals into stack
3.case this a simple unsatisfied goal
    1.choose an operator op whose add-list matches t
    2.replace the twith op
    3.push preconditions of op to stack
4.case this an operator
    1.pop stack
    2.state = state + t.add-list -t.delete-list
    3.plan = [plan | t]

Some explanations -

state - is a list of predicates.

stack - is a stack which includes both predicates or operations.

[plan | t]  - add the opreration t to list plan.

If the stack gets empty, it means that plan holds the solution plan.

Since the algorithm is running while stack is not empty do, how can I recognize that there is no solution (i.e plan) which led to the goal state ?

Those who are not familiar with this algorithm,  you can see its running example here. Brief introduction: imagine a crane which picks boxes and put them each other , so operation can be put box A on box B and state can be box A is on box B .


texts: How to find the shattered set size for unknown hypothesis target

texts:
My aim is to prove a VC-dimension $d$ for different problems. All the problems I have do not have a target function (or concept) explicitly stated. This unlike most of the examples I came through. For example in the interval problem, the target function $h^*$ is: if point $x\in [a,b]$ then $x=+$ and $-$ otherwise. I do not know where $[a,b]$ resides in $R$ but at least I know its an interval. Therefore, three points of $(+,-,+)$ cannot be shattered by any concept.

I am given an infinite input space $X$ and $H$ is the class of all finite languages over $X$ and asked to prove the VC-dimension for this problem. I have no clue what the target function looks like.

Assume I got two points $x_1,x_2\in X$, there are $2^2$ possibilities $(-,-),(-,+),(+,-),(+,+)$. I am stucking here since I don't know what is shattered (i.e. realisable) and what is not without knowing the target function $h^*$. Should I assume such function exists and then workout based on its behaviour? am I missing something?


texts: Are number of states in a NFA same as Pumping length?

texts:
So i was reading a post on Minimum pumping length of regular language where Yuval Filmus has proved that a pumping lemma might have lesser number of states than a minimal DFA. But What about NFA's? Are NFA's able to give us minimum pumping length?

For example say we have a language L= $(10)^∗$, though for this minimal DFA will have $3$ states but NFA will have only $2$ states, which in fact is the pumping length of the language. So are NFA's able to give us exact pumping length of a language?


texts: I'm taking a computer theory class and my professor told us that a pushdown automaton cannot use data structures other than a stack (like a queue or multiple stacks). Why is that?


texts: What is this operator in "The Temporal Logic of Programs" Pnueli 1977?

texts: In The Temporal Logic of Programs there is an operator first appearing on page 3 (48) under "Partial Correctness" that looks like an elongated super set symbol. What is it?


texts: In ISGCI, unit interval graphs are denoted as ($C_{n+4}$,$S_3$,claw,net)-free. Is this an accurate notation?

texts:
When I search unit interval graphs in ISGCI, it says that the unit interval graphs (UIG) are equivalent to ($C_{n+4}$,$S_3$,claw,net)-free graphs.

I am confused about the definition of an $S_3$ graph.
I am aware that in some resources, $S_n$ means $K_{1,n}$, and in others $S_{n-1}$ means $K_{1,n}$.

However, in both cases, ($C_{n+4}$,$S_3$,claw,net)-free $\equiv$ UIG seems like a wrong notation.

If $S_3$ is $K_{1,3}$, then $S_3$ is also a claw graph. Thus, ($S_3$,claw)-free is a redundant notation.
On the other hand, if $S_3$ is $K_{1,2}$, then it is wrong because a path of length 3 is realizable as a unit interval graph.

If this notation is true, then can I also write UIG $\equiv$ ($C_{n+4}$,$S_3$,$K_{1,2}$,$P_2$,claw,net)-free?
If not, then is it correct to write that UIG $\equiv$ ($C_{n+4}$,claw,net)-free?


texts: Why does existence of predecessor imply adequacy of a numeral system?

texts:
I encountered this result when working with $\lambda$-calculus (so every element I mention here was a $\lambda$-expression there [1]), but I will express everything with, more understandable to broader audience, notions of functions.

Intro

Definition 1
A numeral system is a sequence $d = d_0,d_1,\ldots$ such that there exist functions $S$ (successor) and $isZ$ (test for zero) such that
$$S(d_n) = d_{n+1},$$
$$isZ(d_0) = T,\ \ isZ(d_{n+1}) = F.$$
where $T$ and $F$ are notions of true and false.

Definition 2
A numeric function $\varphi : \mathbb{N}^p \to \mathbb{N}$ is definable with respect to $d$ if there exists $f$ such that
$$\forall (n_1,\ldots,n_p)\in \mathbb{N}^p\ \ f(d_{n_1},\ldots,d_{n_p}) = d_{\varphi(n_1,\ldots,n_p)}.$$

Definition 3
A numeral system $d$ is adequate if and only if all partial recursive functions are definable with respect to $d$.

My question (intro)

Proposition 1 (Proposition 6.4.3 in [1])
Let $d$ be a numeral system. $d$ is adequate if and only if there exists $P$ (predecessor) such that
$$\forall n \in \mathbb{N}\ \ P(d_{n+1}) = d_n.$$

For the $\Rightarrow$ direction, it is sufficient to observe that predecessor is a partial recursive function. Specifically, it is a primitive recursion of zero function and first coordinate projection.

My question
How would one prove a $\Leftarrow$ direction? How is it even possible to have such a powerful result, that existence of one function leads to definability of all partial recursive functions?

[1] Hendrik Pieter Barendregt, The Lambda Calculus, 1984.


texts: Using exponential penalty functions in constrained nonlinear optimization

texts:
Background: penalty functions

Penalty functions convert a constrained optimization problem

\begin{equation}\begin{split}
\text{minimize} \quad & f(x) \\
\text{subject to} \quad & g(x) \leq 0
\end{split}\end{equation}

into an unconstrained optimization problem

\begin{equation}\begin{split}
\text{minimize} \quad & f(x) + p(g(x), t)
\end{split}\end{equation}

where $p: \mathbb{R} \mapsto \mathbb{R}$ is a nondecreasing function and $t > 0$ is a "temperature" that increases as the optimization procedure iterates, causing the penalty function to become "harder", i.e.:

$$
\lim_{t \to \infty} p(g, t) =
\begin{cases}
0 :& g < 0 \\
\infty :& g > 0
\end{cases}
$$

The standard choice of a penalty function [1] is something like

$$
p_q(g, t) =
\begin{cases}
0 :& g \leq 0 \\
t g^2 :& g > 0.
\end{cases}
$$

This quadratic penalty has the property that $p_q(g,t) = 0$ whenever $g < 0$. In contrast, another choice would be an exponential penalty,

$$
p_e(g,t) = \exp(tg).
$$

The exponential penalty has the right behavior in the limit, but $p_e(g,t) > 0$ for $g < 0$ and $t < \infty$. This seems bad: consider the case where $x^*$ is a global optimizer of $f$ but $g(x^*)$ is very close to zero. If there is a solution $x'$ where $f(x') > f(x^*)$ but $g(x') \ll 0$, then the exponential penalty solution may be biased towards $x'$.

Penalty functions with simulated annealing

I am using penalty functions with simulated annealing (SA) optimization for nonconvex problems and, despite their theoretical drawbacks, I have found generally better results using exponential penalties (solutions with lower $f(x)$).

Simluated annealing works as follows. Let $E(x,t) = f(x) + p(g(x), t)$:

Start with an initial guess $x$.
Generate a perturbed value $x'$ by applying some random small change to $x$
If $E(x') < E(x)$, $x \gets x'$
If $E(x') \geq E(x)$, $x \gets x'$ with probability decreasing in $t(E(x') - E(x))$
Increase $t$, go to 2.

Note that SA is usually written with a decreasing temperature, but I have changed it to allow using the same variable as the penalty function temperature.

Is there any reason why exponential penalties might work better in practice? I have seen some applications papers using SA with exponential penalties, but I have not found any published justifications for using exponential instead of quadratic.

One hypothesis: since the exponential penalty distinguishes between feasible solutions that nearly violate a constraint and those that are far from any constraints, it could somehow bias $x$ towards regions where most random perturbations produce an $x'$ that does not violate the constraints, making it "easier" to move between the basins of attraction of different local optima. However, I do not know if this is true, or how to formalize it.

[1] Luenberger and Ye, "Linear and Nonlinear Programming"


texts:
A ﬁle F holds the non-zero elements of two large n×n matrices, A and B.

The matrix entries are stored as triplets (i,j,value),

where value is the (i,j)th element of a matrix.

The ﬁle ﬁrst stores the elements of A and then those of B. The matrix elements are stored in F in an arbitrary order.

In each matrix, only the elements {(i,i) : i = 1,...,n},

{(j,j + 1) : j = 1,...,n−1}, and

{(j + 1,j);j = 1,...,n−1}

are non-zero.

You are to add A and B and store the sum in C and then print A, B and C.

Due to limited memory, for storing all three matrices, you can use space to hold only up to 9n values (NOT triplets).

Is it possible to have an O(n) solution? If no, give reasons. If yes, provide a solution. Clearly explain the data structure and how you are going to store, retrieve, and add the elements.

................................................................................

Here only the elements (i,i) , (j,j+1) , (j+1,j) of the matrices A and B are non - zero.

So, we have to retrieve only the values of (i,i) , (j,j+1) , (j+1,j) of the matrices A and B from the file.

I want to know whether retrieving the values from file takes time or it can be done in constant time.

If it takes time then I think it is not possible to have an O(n) solution to the problem.

Please correct me if I am wrong.

If it takes constant time then please provide a algorithm to solve the problem in O(n) time.


texts: How to prove the well-Definedness of the Operation $.\:$?

texts:
Let $L\subseteq  \Sigma^*$ a Language

$R_L$ is the Myhill-Nerode-Relation of $L$

$\equiv_L$ is the Syntactic Congruence of $L$

$R_L$ and $\equiv_L$ are equivalence relations and are defined as follows :

$x\:R_L\:y \:\Leftrightarrow \: [\forall w\in\Sigma^* : xw\in L\Leftrightarrow yw\in L] $

$u\:\equiv_L\:v \:\Leftrightarrow \: [\forall x,y\in\Sigma^* : xuy\in L\Leftrightarrow xvy\in L] $

How to prove that the operation $"."$ (which i guess is the Concatenation) on the equivalent classes of $R_L$ and $\equiv_L$ is well defined ?

a) $[u_1]_{R_L} . [u_2]_{R_L} = [u_1u_2]_{R_L}$

b) $[u_1]_{\equiv_L} . [u_2]_{\equiv_L} = [u_1u_2]_{\equiv_L}$


texts: Does White never lose in Chess if Chess is solved?

texts: If the machine has enough memory and speed as to compute all states of the Chess game in a reasonable time, can a player with the white pieces - operated by a machine - lose a game?


texts: What can you do with lambda calculus if you aren't allowed parentheses?

texts:
Is there a concise/existing way to denote the expressive power of "lambda calc without using parentheses/tree-of-expressions/application-order-restructuring anywhere"?

Can you do without them/reinvent them? Does it break completely (i.e, even with a naive no-more-parentheses, you're using them implicitly, like when naming things)? Does it become completely trivial/boring?

I haven't tried very hard, but I feel like I couldn't express something like

$\lambda x y z . x y (x z)$

without using parentheses somewhere.


texts: Find perfect matching whose weight is minimal, in polynomial time


texts: What does "edge-connected components of graph" means in paper PUNCH?

texts:
I'm recently trying to study the paper "Graph Partitioning with Natural Cuts": https://www.microsoft.com/en-us/research/wp-content/uploads/2010/12/punchTR.pdf

There is a term edge-connected components in section 3.1 Detecting Tiny Cuts:

  The first pass identifies all edge-connected components of the graph using depth-first search.
  They form a tree T. We make T rooted by choosing as a root the edge-connected component
  with maximum size, which on road networks typically corresponds to most of the graph. We then
  traverse T in a top-down fashion. As soon as we enter a subtree S of total size at most U, we
  contract it into a single vertex...

First, it seems not to mean "connected component" because in section 2 it says:

  To simplify the description of our algorithm, we assume G is connected

And I tried to search this term on Google but only a term k-edge-connected (https://en.wikipedia.org/wiki/K-edge-connected_graph) found and it seems to mean something different.

Could someone tell me what this term means exactly, please? Thank you!


texts: Prove that the upper bound in the Noiseless-coding theorem is strict

texts:
Given a probability distribution $p$ across an alphabet, we define redundancy as:

Expected Length of codewords - entropy of p = $\ E(S) - h(p)$

Prove that for each $\epsilon$ with $0 \le \epsilon \lt 1$ there exists a $p$ such that the optimal encoding has redundancy $ \epsilon$.

Attempts

I have tried constructing a probability distribution like $p_o = \epsilon, p_1 = 1 - \epsilon $ based on a previous answer, but I can't get it to work.

Any help would be much appreciated.

Edit:

The solution I think I have found is mapped below.

redundancy = $E(S) - h(p) = \sum p_is_i + \sum p_ilogp_i$.
We want to show that for a given $\epsilon$, we can find a $p$ that makes redundancy = $\epsilon$.
So $\sum p_is_i + \sum p_ilogp_i = \epsilon ==> \sum p_is_i = -\sum p_ilogp_i + \epsilon$.

We know the optimal value for $s_i$ will be less than $-logp_i + 1$, so we can write all $s_i$ as $s_i = -logp_i+\alpha_i$.

Now, $\sum p_is_i = -\sum p_ilogp_i + \epsilon ==> \sum p_i(-logp_i + \alpha_i) = -\sum p_ilogp_i + \epsilon ==> \sum p_i\alpha_i = \epsilon$.

Intuitively I feel that you can always find a p so that the above is true for $epsilon$, because the $\alpha$ values are governed by how far away from a power of two your $m$ is, but I am not sure how to prove this last step.


texts: Worst-Case Complexity of Quantifiers in Thompson's Construction

texts:
My understanding is that an NFA compiled using Thompson's Construction should have a running time that is linear in the length of the input string, with a space complexity that is linear with the length of the regex pattern.
Consider this pathological example: $a^*a^*ab$, which should match at least one $a$ followed by exactly one $b$. I'm going to refer to the compiled NFA as having three parts, with a "front part" representing the first $a^*$, a "middle part" representing the second $a^*$, and a "back part" representing $ab$.
The front and middle parts would look like this, with a simple $a$ symbol transition for $N(s)$:

The back part would look like two of these symbol transitions, one for $a$ then one for $b$:

Let's try to match $aaab$:

The compiled NFA starts in the start state.
Having two options due to the first Kleene star, it splits execution. It doesn't matter which state goes where, so let's just say state #1 takes the epsilon transition to move on to the middle part, and state #2 stays in the front part.
State #2 would match the first $a$, then split again. Let's say state #2 proceeds along the loop-back epsilon transition and stays in the front part, while a new state #3 moves on to the middle part. Now there are three states.
Meanwhile, state #1 – now in the middle part – also splits due to the second Kleene star, and does basically the same thing as state #2 did in the front part. Let's say state #1 moves on again to the back part, while a new state #4 goes into the Kleene star construction in the middle part, matches the first $a$, and in turn splits again into a state #5 that loops back within the second Kleene star construction, so state #4 can move on to the back part like state #1 did, except that state #4 has already matched the first $a$.

At this point, you can probably see what I'm getting at; the first Kleene star causes execution to split, in the worst case, $O(n)$ times, where $n$ is the length of the input, then the second Kleene star potentially causes each of those $O(n)$ splits to split $O(n)$ times, resulting in $O(n^2)$.
So there must be some way of pruning the possible states and avoiding $O(n^2)$ splits. An obvious pruning strategy would be to prune states if we've already visited the same node before in another state which had already consumed exactly the same amount of the input string. Keeping track of how much input we've consumed at each state is important since we cannot greedily consume either as much or as little as possible in the Kleene star constructions; in the example above, the whole input is only matched if the front and middle parts consume only the first two $a$'s between the two of them, so the back part can get the third $a$ and the $b$. But, this pruning strategy would result in $O(nk)$ space and time complexity, where $k$ is the length of the regex pattern, since there are $O(k)$ nodes in the NFA, and each node can have a unique state depending on how much of the length-$n$ input string it's consumed. I'm ok with $O(nk)$ running time, but I'm concerned about $O(nk)$ space complexity for large inputs in my application.
Is there some more genius pruning strategy that I'm not aware of? I don't have access to ACM, so I'm not able to read the original paper, and none of the articles of read about it go into enough detail to untangle this kind of situation.


texts: Proving that a sentence in first-order logic is not valid

texts:
By the completeness of FOL, one can show that a sentence $S$ in FOL is valid, i.e. that it holds true in every model, by exhibiting a proof of $S$. Such a proof string is a certificate of the validity of $S$.

To show that $S$ is not valid, one can either exhibit a counterexample model in which $S$ doesn't hold, or find a proof that such a model exists, either of which would serve as a certificate.

However, do I understand correctly that while a "certificate of validity" will always exist, that "certificates of invalidity" do not exist in the general case?

In other words, that there can exist $S$ which are not tautologies, and for which a counterexample model exists, but for which one cannot actually construct a counterexample, or a proof of its existence?

This is not a question about the ability of FOL to formalize arithmetic (which Godel proved is impossible), but simply whether or not, in a very foundational sense, it is possible to prove counterexamples exist to FOL sentences in general.


texts:
I like to reduce the number of exceptions raised in my code, and I thought it might help to consider why these exception are raised in the first place, and whether they are a really a fundamental part of code or just an artefact of not really finishing the program.

As a related note I hear OS programming requires avoiding errors where possible, perhaps there are some answers there.


texts: For Example when we consider a DFA that allows the strings having neither sub strings 00 or 11 I can produce the following two DFAs:


texts: Optimizing cheap functions on mixed search space

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

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

with

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

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


texts: Distributing Neural Network Training World-Wide Using Blockchain?

texts:
I just finished reading a white-paper from a recent AI startup. The company, Deep Brain Chain, wants to distribute neural network training over computers worldwide, using blockchain technology. Here is the whitepaper

From my understanding of machine learning and artificial neural networks, the communication bandwidth is the biggest bottleneck. I would assume that anyone needing infrastructure AI services is using some pretty big models. The bigger the training batch, the more likely it is that data transfer speed is a bottleneck.

Now, attempting to paralyze this across multiple nodes "in the cloud" does not seem like it would scale well. Far, far from linear at least.

Utilizing a distributed network of blockchain mining computers seems like an additional step towards imperfect parallelization. The internet connection speed is bound to be 10-100x times slower than speeds achievable in a cloud datacenter.

Plus, none of the computers in a distributed network of blockchain miners are running the same hardware specifications. I'm not sure, but this seems to add lots of difficulty to the parallelization and efficiency issues.

It is my understanding that neural networks are not highly parallelizable to begin with, much less suited for this type of distribution.

However, I've come here to ask these questions: Are there any (known) training algorithms that can avoid the problems I've posted above? Can there be distributed neural network training systems that utilize a massive network of home PCs and data centers alike?


texts: complexity classes defined as limits or "globally"?

texts:
As far as I understand correctly, to say that a decision problem $X$ is in P means that there exists a polynomial $c\cdot n^p$ such that as $n$ goes to $\infty$, the steps required to solve $X$ is bounded by $c\cdot n^p$.

But strictly speaking, this doesn't restrict the complexity for finite $n$ in any way. Strictly speaking if $X$ is in P, it could be that for all $n$ between $0$ and Ackermann function $A(300,300)$, the complexity of $X$ grows according to $e^n$, and then only from $A(300,300)$ onwards it starts being bounded by $c\cdot n^p$.

Am I right that if a problem is in the complexity class P this strictly speaking doesn't say anything about its complexity for finite $n$? Is there a way to talk about complexity for finite $n$?