# Question
Title: Restricting capabilities of admin role in database schema
Suppose I have to design database for learning management system. Which will going to have user having roles such as admin, teacher, tutor, student etc. In a system student can submit solution for an assignment in a course and teacher or tutor can provide the grade for it.

Now while implementing is it good idea to not allow admin of a database to not to change the grade of students for an assignment? I got this suggestion that as admin is superuser (user with all capabilities) he should be able to change the grade. So what should I do? and why?

# Answer
Generally, you cannot prevent administrators from making any change they want to the database. Many administrator actions require privileges that give them a lot of control over the database. For instance, if they can restore from backups (something that administrators often need to do), they can overwrite everything in the database.

Designing systems that will remain secure even when the system administrator is not trusted is very challenging, and for a learning management system, is probably more expensive than is worth it.

Therefore, there's probably no point in trying to restrict admin. Don't forbid what you can't prevent.
> 2 votes

# Answer
Audit trails can provide a mean to accomplish that kind of security-related objective (individual accountability / reconstruction of event).

Users (not only administrator) are less likely to attempt to circumvent security policy if they know that their actions will be recorded in an audit log.

There are several aspects you should consider:

* native database audit capabilities do not provide sufficient controls. Native audit trails must be extracted on a regular basis and transferred to a (secure) system where the database administrators do not have access;
* it can be expensive, in terms of both performance and storage (an audit trail may record "before" and "after" versions of records);
* periodical reviews must be carried out (probably with the help of some tools for audit trail analysis).
> 2 votes

---
Tags: database-theory, databases
---


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

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

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

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

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

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

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

# Answer
> 4 votes
The way I understand it, the answer is your item #2.

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

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

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

---
Tags: finite-automata, np-complete, cellular-automata
---


# Question
Title: What are positive and negative circles in weighted digraph?
I am going through Warshall and Floyd algorithms and I read that Floyd's algorithm does not hold if a graph has negative circle. I have not been able to fully figure out what negative circle means. Therefore, I would like to know more about positive and negative circles.

# Answer
> 3 votes
A *circle* is a path in the graph ($v\to u\_1 \to u\_2 \to \cdots \to v$) starting from some node $v$, that goes back to node $v$, thus "closing a circle".

The "value" of a circle, is the sum of the weights of the edges in the circle. If they sum to a negative value -- the circle is "negative"; otherwise, it is "positive".

---
Tags: graphs
---


# Question
Title: Convert C language code to problem specification by computing the invariant of a program
Suppose that you need to give a problem specification of some problem *P* and you have an implementation of *P*, in C.

I have 2 questions:

1. Can you obtain the formal specification of the problem if you compute the invariant of the external for cycle?
2. What is the relation between the specification and the C code invariant?

# Answer
> 3 votes
You can not reconstruct the specification from just the code.

For one thing, you don't know whether the code is correct or not. For another, there are multiple possible specifications that are all compatible with the code.

For instance, consider the following function:

```
unsigned int f(unsigned int x) {
    return x+1;
}

```

Was the intended specification that `retval == x+1`? Or that `retval > x`? Or that `retval > 0`? We can't tell. There just isn't enough information to know. (Ignore integer overflow for the moment.)

---
Tags: formal-languages, software-verification
---


title: Big O Running Time Analysis

text:
# Question
Title: Big O Running Time Analysis
What is the big O running time for following `method()` by counting the approximate number operation it performs. How can I identify the running time of each line? I mean when is 1, n or n^2..?

```
static int do(int n) {
    int count = 0;
    int j = 0;
    for (int i = 0; i < (n-1); i++) {
        j == i;
        while (j != 0) {
            if ( (j%2) == 0)
               count++;
            j = j/2;
        }
    }
    return count;
}

static int method(int n) {
    int sum = 0;
    for (int i = 0; i < n; i++) {
        sum = sum + do(i);
    }
    return 1;
}

```

# Answer
> 0 votes
`O(1)` when you are accessing or assigning a single variable

```
int number = array[index];

```

`O(n)` when you iterate over `n` elements

```
for (int i = 0; i < n; i++)
{
   //code
}

```

`O(n^2)` when you iterate `n` times over `n` elements (nested loop)

```
for (int i = 0; i < n; i++)
{
   for (int j = 0; j < n; j++)
   {
      //code
   }
}

```

---
Tags: asymptotics
---


# Question
Title: Is there an alternative to full factorization for testing the Polya conjecture?
The Polya conjecture is a disproved conjecture that states over half the numbers less than any number has an odd number of prime factors. It first fails at $n = 906,150,257$, thus being a good example that testing very many cases is not always enough.

I have been giving "disproving the Polya conjecture" as an exercise a few times, as the counter example is well within computational capabilities.

The simple algorithm for it is to have an incrementing $n$, factorize it, count the factors, and increment either the counter for odd numbers, or even numbers. Continue until you reach the counter example.

Factorization is however an operation to try to avoid, as even the most effective algorithms for that have a nasty computational complexity.

The amount of unnecessary information created by factorizing every number got me wondering if there are better ways. Because:

* We do not have to know what the factors of a number are, just how many.
* Even the number of prime factors is not needed, as we only need the parity.
* We do not have to know the parity of the number of prime factors of each number in a range, it is sufficient to know how many are odd, and how many are even.

Factorization here yields a lot more information than actually needed. Is it really necessary?

# Answer
> 2 votes
You can use a sieve to significantly improve the running time. Decide on a number $N$, say $N = 2^{30}$. Initialize an array of length $N \times 2$ bits: one to keep track of the parity of the number of prime factors, and the second to mark which numbers have been visited. Now run an algorithm similar to the sieve of Eratosthenes. The running time equals the total number of prime factors of all numbers up to $N$, which is roughly $N\log\log N$.

With this information in hand, it is easy to check for violations of the conjecture.

---
Tags: algorithms, time-complexity, factoring
---


# Question
Title: How often can a linear speed sort succeed?
Let's say you have sorting function. It is allowed to exit with failure (but if it does not it must return a correctly sorted sequence). It is also $\mathcal O (n)$.

What kind of bounds can we place on the success rate of such an algorithm? It obviously can't succeed 100% of the time, since then it would just be an ordinary list sorting function and it would have to be $\Omega(n \log n)$. The answer isn't 0% success, since you can check if it sorted in $\mathcal O (n)$, and so you can sometimes succeed.

Of course, the success rate depends on how we are choosing the list. The uniform case would be best, but any kind of bounds would be helpful.

# Answer
David Eppstein gave away the answer: an $O(n)$ comparison-based algorithm will succeed on a negligible fraction of permutations. One way to see that is that an $O(n)$ algorithm can only take care of $2^{O(n)}$ different input permutations, compared to the $n! = 2^{\Omega(n\log n)}$ possible ones.
> 2 votes

---
Tags: complexity-theory, time-complexity, lower-bounds, sorting
---


# Question
Title: Computing MOD_4 function using MOD_2, OR, AND, NOT gates
Define the $\newcommand{\MOD}{\text{MOD}}\MOD\_q$ function from $\\{0,1\\}^n \rightarrow \\{0,1\\}$ as follows:

Let $x\_1,\cdots,x\_n$ be the input. Then $\MOD\_q(x\_1,\cdots,x\_n)=0$ if the number of 1's in $x\_1,\dots,x\_n$ is divisible by $q$; $\MOD\_q(x\_1,\cdots,x\_n)=1$ otherwise.

I want to compute $\MOD\_4$ using a constant depth circuit using only the following gates: $\MOD\_2$ gates and the usual AND, OR, NOT gates. Gate fan-in is unbounded. Technically I want to show that $\MOD\_4 \in \text{ACC}\_0\[2\]$, where $\text{ACC}\_0\[2\]$ means alternating circuit of constant depth with parity gates ($\MOD\_2$ counters). Or more generally, I want to show that $\MOD\_{p^k} \in \text{ACC}\_0\[p\]$.

Can this be done? Is there a way to compute $\MOD\_4$ using $\MOD\_2$, AND, OR, and NOT gates?

My attempt: If I pass the input through a $\MOD\_2$ gate, then if it outputs 1 (i.e., odd) then $\MOD\_4$ is also $= 1$. But $\MOD\_2$ will output $0$ for the integers of the form $4k+2$ whereas $\MOD\_4$ should be $1$ for those cases. I tried using OR, AND gates also but failed. I guess it will use some number theoretic property.

# Answer
Suppose for simplicity that the number of ones in the input is even, and we want to know whether it is divisible by 4 or not. Intuitively, what we would like to do is to somehow "halve" the number of ones in the input; then divisible by 4 would correspond to even, and not divisible by 4 would correspond to odd. Since we have parity gates in our disposal, we would be able to solve our problem.

How do we "halve" the number of ones? The idea is to consider the running sums $$ y\_i = x\_1 \oplus \cdots \oplus x\_i. $$ Each time $x\_i = 1$, we have $y\_{i+1} \neq y\_i$. Half the time, $y\_i$ switches from 0 to 1, and half the time it switches from 1 to 0. By concentrating on one-sided switches, we are able to effectively halve the number of ones, and so solve your problems. Details left to you.
> 3 votes

---
Tags: complexity-theory, modular-arithmetic
---


title: Symmetry in Pattern Databases

text:
# Question
Title: Symmetry in Pattern Databases
I am trying to understand the use of symmetry in pattern databases (Heuristics, single agent search). This is too specialized of a topic to find common videos or explanations in general. I read the paper *Pattern Databases* by Joseph C. Culberson and Jonathan Schaeffer (University of Alberta) in Computational Intelligence, Volume 14, Number 3, 1998.

In the paper, they explain the different kinds of symmetries we can use on the 15-Sliding Tile Puzzle such as Horizontal, Vertical and Mirror. But what I do not understand is how exactly are we going to use those symmetrical configurations of a puzzle to find a good lower bound on the estimated cost of a state from the goal.

I would really appreciate if anybody can explain the process of using symmetry in pattern databases or can point toward a good explanation.

# Answer
> 2 votes
From your question I assume you understand how symmetries are computed. As an exercise, make sure to understand the example given in Figure 4 which refers to the easiest of all symmetries, the Mirror (also known as Diagonal) denoted as $D$. In the following I will refer to this symmetry only unless otherwise noted.

Next, hope you also understand that symmetries create isomorphic puzzles so that the number of moves necessary to optimally solve the *reflected state* is precisely the same number of moves (but different) necessary to optimally solve the original state ---see Figure 3 in the paper for a good example of a *path reflection* which results from applying $D$.

Hence, when computing the heuristic estimate of any state $p$, compute its symmetrical state $p'$ (in time linear in the size of the puzzle), and look up the Pattern Database for both states $p$ and $p'$. Since Pattern Databases are indeed *homomorphisms* let $\rho$ denote such mapping ---i.e., what tiles are mapped to themselves and what tiles are replaced by the *don't care* symbol. Thus, you can safely take the maximum of both values returned from the PDB:

$h(p)=\max\\{V(\rho(p)), V(\rho(p'))\\}$

where $V(n)$ denotes the value stored in the PDB for the *abstracted state* $n$ which consists of tiles and *don't care* symbols. The two values within brackets are indeed those mentioned at the beginning of Section 4.3.

Note the importance of the blank tile: The other symmetries H, V and D' do not preserve its location and therefore Section 4.2 proposes to use some corrections (3, 3, and 6 respectively) to both the lower and upper bounds.

Of all these symmetries, the most widely used are $D$ and $D'$. Other works (among many others) exploiting them are given below:

Richard E. Korf, Ariel Felner. Disjoint Pattern Database Heuristics. Artificial Intelligence, 134, pp. 9--22, 2002

Ariel Felner, Richard Korf, S. Hannan. Additive Pattern Database Heuristics. Journal of Artificial Intelligence Research, 22, pp. 279--318, 2004.

Uzi Zahavi, Ariel Felner, Robert C. Holte, Jonathan Schaeffer, Duality in Permutation State Spaces and the Dual Search Algorithm, Artificial Intelligence, 172 (4--5), pp. 514--540, 2008

To finish, let me reproduce here a paragraph from the last paper:

> Because all valid, alternative PDB lookups provide lower bounds on the distance from state $S$ to $G$, their maximum can be taken as the value for $h(S)$. Of course, there is a tradeoff for doing this ---each PDB lookup increases the time it takes to compute $h(S)$. Because additional lookups provide diminishing returns in terms of the reduction in the number of nodes generated, it is not always best to use all possible PDB lookups.

Hope this helps,

# Answer
> 0 votes
From the article you mentioned: "states near to the goal can be precalculated", the obvious consequence is that you can go further if the branching factor (ir in this case search space) is lower.
So symmetrical reduction is not tool to do estimation but reduction for the search space and the end game (states near to goal) to make computations less computationaly expensive.

Another reduction described is to store partial solutions (sometimes called roadmap)(good states that makes the goal easier achievable) and reduces the space covered $1038-fold$.

The heuristic from A\* and given roadmap has to estimate the best move from available data, so it is lower bound possible for this approach.

---
Tags: search-algorithms, artificial-intelligence, heuristics, search-problem
---


# Question
Title: How to work out if an IEEE 754 floating point number is normalized?
How do I tell whether a particular IEEE 754 floating point number is a normalized floating point number? Is there some way to recognize an IEEE 754 normalized floating point number?

# Answer
For single-precision floating-point numbers you need to check if the following condition holds for the exponent $e$: $0 \< e \< 255$. The exponent occupies bits $30 .. 23$ (including both ends) of a floating-point number.

For double-precision floating-point numbers you need to check if $0 \< e \< 2047$. The exponent occupies bits $62 .. 52$ in this case.

Essentially, for IEEE 754 floating-point numbers one has to check that the bits of the exponent are not all 1's and not all 0's. All zero bits correspond either to subnormal numbers or to signed zero. And when all bits of the exponent are ones it corresponds to $+\infty, -\infty$ or NaN (not a number).
> 2 votes

---
Tags: floating-point, number-formats
---


title: Design the grammar for the following

text:
# Question
Title: Design the grammar for the following
Design the grammar for the following: L = (a^n)*w*(w^r)*(b^n) where n\>=0 and w={a,b}*

# Answer
> 0 votes
The answer goes something like this

S-\>ε/ aSb

S-\>A

A-\>ε/ aAa / bAb

here is a sample string for the above with proof

aabaabbb

S=\>aSb

S=\>aaSbb

S=\>aaAbb

S=\>aabAbbb

S=\>aabaAabbb

S=\>aabaεabbb

S=\>aabaabbb

here above symbol ε is epsilon

---
Tags: finite-automata
---


# Question
Title: What does it mean to have a continuous action space w.r.t. to reinforcement learning?
Last time I posted this question I got criticised for not being specific enough, hence this is my second attempt at trying to understand what it means to have a continuous action space.

Please refer to this paper, page 5 (*A Survey on Policy Search for Robotics* by Marc Peter Deisenroth, Gerhard Neumann and Jan Peters. Foundations and Trends in Robotics. 2013).

The authors say:

> The RL algorithm has to manage (i) high-dimensional continuous state and action spaces, (ii) strong real- time requirements, and (iii) the high costs of robot interactions with its environment.

I do not understand how an action can be continuous, in the same way that a state-vector is continuous by virtue of having elements that are simply $x\_k \in \mathbb{R}^D$ for a state vector $\mathbf{x} := \[x\_1,\ldots,x\_K\]^T$. But how can an action be quantified in the same way? It obviously can I simply do not understand how.

# Answer
When you're driving of your car and you turn the wheel, is that a discrete or a continuous action? It's continuous, because you can control how much you turn the wheel. How much do you press the gas pedal? That's a continuous input. This leads to a continuous action space: e.g., for each positive real number $x$ in some range, "turn the wheel $x$ degrees to the right" is a possible action.
> 5 votes

---
Tags: machine-learning, reinforcement-learning
---


# Question
Title: Difference between algorithm and procedure
I came to know that the important difference between algorithm and procedure is that the algorithm halts and procedure doesn't halts(stops). But i am not able to understand the concept. Please can any one explain with the example?

# Answer
Let me cite the classic -- D.E. Knuth's "The Art of Computer Programming", 3ed (1997).

Some terminology first.

> The modern meaning for algorithm is quite similar to that of *recipe*, *process*, *method*, *technique*, **procedure**, *routine*, *rigmarole*, except that the word "algorithm" connotes something just a little different.

Note: the bold face is mine. Then Knuth goes on:

> A procedure that has all of the characteristics of an algorithm except that it possibly lacks finiteness may be called a *computational method*.

It turns out that one of the earliest examples of a computational method belongs to Euclid:

> Euclid originally presented not only algorithm for the greatest common divisor of numbers, but also a very similar geometrical construction for the "greatest common measure" of the lengths of two line segments; this is a computational method that does not terminate if the given lengths are incommensurable. Another example of a nonterminating computational method is a *reactive process*, which continually interacts with its environment.

It seems that by the second case Knuth meant operating systems, web-servers and so on, i.e. the programs that are supposed to run "forever", but do something useful along the way.
> 11 votes

# Answer
What most people say is that a procedure is something which may go on and on or may stop/halt but an algorithm is some thing that is well defined and will stop and give output. Moreover, an algorithm is something much deep and theoretically proven. People do write new algorithms but they provide mathematical proofs for it. Anyone can write a procedure to do a task but it may or may not be a well defined and proven algorithm. Lastly, I personally believe, the logic that does the work most efficiently is what's needed.
> 4 votes

---
Tags: algorithms
---


# Question
Title: Depth of a pipeline in a CPU's architecture
I follow a course on CPU architectures and I'm making exercises at the moment. Now I encountered the word "depth of a pipeline" in one of the exercises, but I don't know what's meant by the depth of a pipeline. Is it the number of stages of the pipeline or something else? I can't find it anywhere in the syllabus.

# Answer
I think that depth is a measure of the overlapping of instructions while number of stages is a hardware constant. When you increase the number of stages, you usually make the CPU faster but it is with dimishing margin. See Almdahl's law about this and the book "Computer Organization and Design" by Pattersson and Hennesay.

The more stages, the larger the depth but it is stated that there can be optimal number of stages or optimal depth:

According to (M.S. Hrishikeshi et. al. the 29th International Symposium on Computer Architecture)

> The difference between pipeline depth and pipeline stages; is the Optimal Logic Depth Per Pipeline Stage which about is 6 to 8 FO4 Inverter Delays. In that, by decreasing the amount of logic per pipeline stage increases pipeline depth, which in turn reduces IPC due to increased branch misprediction penalties and functional unit latencies. In addition, reducing the amount of logic per pipeline stage reduces the amount of useful work per cycle while not affecting overheads associated with latches, clock skew and jitter. Therefore, shorter pipeline stages cause the overhead to become a greater fraction of the clock period, which reduces the effective frequency gains.
> 2 votes

---
Tags: computer-architecture, cpu-pipelines, cpu
---


title: removing ε production

text:
# Question
Title: removing ε production
It's not that i dont know how to remove εproduction but when complex problem arises i get confused for example

S--\>Aa/aaB

A--\>a/ε

B--\>bbA/ε

CFG without ε production for the above question is

S--\>Aa/aaB/a/aa

A--\>a

B--\>bbA/bb

here i replaced A,B with ε in all productions to obtain the result

But for questions like this one

S--\>ABCa/bD

A--\>Bc/b

B--\>b/ε

C--\>c/ε

D--\>d

how many possabilities will occur in S production

# Answer
> 1 votes
I understood your confusion

firstly here C,B,A,S all approach ε at one point

so solving in the method you solved previous example put ε one by one in S then consider all combinations like this

S--\>ABCa/bD/BCa/ACa/ABa/Aa/Ba/Ca/a

A--\>Bc/b/c

B--\>b

C--\>c

D--\>d firstly in S for (ABCa) put ε in A then B then C later BC,CA,AB,ABC so if you follow this fashion you get the answer

---
Tags: context-free
---


# Question
Title: show that special case of NP-complete problem is also NP-complete?
I want to show that a problem is NP-hard by reducing a known NP-complete problem to it. However, I will have to use a special case of the NP-complete problem for the reduction to work. I'm pretty sure that the special case version is also NP-complete but I have no idea how to prove that. Are there any general guidelines for how to do this?

For example, consider this version of the SUBSET SUM problem without repetition:

*Given an integer **I** and a multiset **S** of **integers in the range 1,2,...,10**, is there a non-empty subset of **S** whose sum is **I**?*

I could be wrong, but don't think the restriction of possible values in *S* to {1, ..., 10} affects the NP-completeness of the problem. How would one go about showing this?

**EDIT:** Apparently that version of the problem is actually in **P**. I might restate my question later.

# Answer
"Are there any general guidelines for how to do this?"

Frequently, one does that by reducing from the general case to the special case.
Otherwise, being a special case of a known NP-complete problem isn't really helpful for that.
How would one go about showing this?

Due to dynamic programming, one would prove  P = NP .
> 1 votes

---
Tags: np-complete, reductions, decision-problem
---


# Question
Title: Can we say that Zookeeper updates are ACD (ACID without the I)?
Zookeeper is based on the Zab (which is slightly different to Paxos) system.

We can do Atomic locks on top of a Zookeeper cluster.

Zookeeper provides eventual consistency.

Zookeeper provides durability.

(I'm aware that Zookeeper sacrifices Availability for Consistency and Partition Tolerance - making it CP - but I'm not asking that question here. )

My question is: **Can we say that Zookeeper updates are ACD (ACID without the I)?**

# Answer
Atomicity is not about being able to implement "atomic locks" or not. Consistency as used in the CAP theorem (i.e. the C in CAP) is not the same thing as Consistency in ACID, and Consistency in CAP is way stronger than eventual consistency. ZooKeeper is an ACID system and a CP system, albeit the ACID "C" is not doing much work here.

Atomicity means a "transaction" either completes entirely or not at all. It's mostly orthogonal to concurrency. If you had a system that was Atomic but not Isolated, transactions could see the intermediate results of other in-progress transactions regardless of whether those other transactions got rolled back or not. Meanwhile, a non-Atomic but Isolated system would not see any intermediate results of *in-progress* transactions, but failed transactions need not rollback their work, so the detritus of failed transactions would be visible to all. Atomicity alone would not allow you to implement atomic locks; Isolation is really the more important property for that though technically Atomicity is also required.

Consistency in ACID means maintaining integrity constraints. ZooKeeper provides few such constraints, so this is accomplished more or less trivially. Consistency in CAP refers to linearizability which is different than but related to Isolation. Isolation refers to serializability. Traditionally, (one-copy) serializability was effectively strict one-copy serializability which is the combination of serializability and linearizability, but serializability and linearizability are actually distinct (though similar looking) notions, neither implying the other. ZooKeeper provides strict one-copy serializability (if you sync before every read), and thus it is both Isolated and Consistent in the CAP sense.
> 3 votes

---
Tags: distributed-systems
---


title: Are these languages are regular?

text:
# Question
Title: Are these languages are regular?
> Consider the languages $L\_1, L\_2 \subseteq \sum^\*$, where $\sum=\\{a,b,c\\}$. Define
>
> $$L\_1/L\_2 = \\{x : \exists y \in L\_2\ such\ that\ xy \in L\_1 \\}$$
>
> Let $L\_1 = \\{a^nb^nc^{2n}: n \ge 0\\}$ and $L\_2 = \\{b^nc^{2n}: n \ge 0\\}$.
>
> Justify whether $L\_1$ and $L\_1/L\_2$ are regular.

$L\_1$ will not be CFL also as it needs more than one stack to count. $L\_1/L\_2$ gives concatenation and the result will be $a^{n} b^{2n} c^{4n}$ which is again non regular. Am I right? I am little bit confused for $L\_1/L\_2$ case as for some $y$, $xy$ belongs to $L\_1$.

# Answer
> 0 votes
Since this looks like an exercise, I'll just hint at the solution for now; some of this has already been nudged at in comments.

What we have:

* $L\_1 = \\{a^nb^nc^{2n}\ |\ n\ge 0\\}$
* $L\_2 = \\{b^nc^{2n}\ |\ n\ge 0\\}$
* $L\_1/L\_2 = \\{x\ |\ xy\in L\_1 \mbox{ for some } y\in L\_2\\}$.

Plugging in the actual $L\_1 $ and $L\_2$, we get

$\begin{array}{ll} L\_1/L\_2 &= \\{x\ |\ xb^nc^{2n}\in L\_1 \mbox{ for some }n\ge 0\\}\\ &= \\{x\ |\ xb^nc^{2n}=a^mb^mc^{2m} \mbox{ for some }m,n\ge 0\\} \end{array}$

Then it is straightforward to show that $m,n$ must actually be equal, and the rest is easy.

---
Tags: automata
---


# Question
Title: Adaptive Radix Tree - Question regarding child indexing
i have to write an exam in a course given by one of the contributing professors of this paper: http://www-db.in.tum.de/~leis/papers/ART.pdf

Of course this could also be a possible topic in the exam. Now i understand the basic advantages and structure of this tree, but i just cannot fathom some details. Maybe someone here can help me with that:

* So Node4 store up to 4 partial keys (of 1 byte each) and up to 4 child pointers. The child pointer used is determined by the position of the partial key, right?
* Starting at Node48 the child pointer is indexed by using the partial key itself as index into the "key"-array and using that value as index into the child-pointer array, right? But why do we have a 256-element array for the key-bytes although there are only 48 child pointers?
* Node256 is just an 256-element array indexed through the key byte.

And at last what are those red numbers depicted in this image?

Thanks a lot!

# Answer
> 2 votes
The red values in the image shows key values associated with a location.

Node4 works by performing a linear search for the key byte in the 4-element key array. If we were looking for key value 255 in the image you posted, we'd find at array index 3. We then find the corresponding child by looking at index 3 in the child pointer array.

Node256 is just an 256-element array of child pointers indexed by key byte, yes.

The problem with Node256 is that it wastes a lot of space if most of the array is empty. Node48 uses much less space by exploiting the fact that a pointer is much larger than a byte (typically 8 bytes). We have an 256-element array of bytes (the child index array), one for each key value. When we index into this array, we get a byte that is an index into the 48-element child pointer array. So the lookup is something like this (the actual implementation is slightly different):

```
Node *find(Node *node, byte key) {
    idx = node->child_indexes[key];
    // Index == 255 is element missing
    if idx == 255 { return null; }
    return node->children[idx];
}

```

Since the child index array has 256 elements we can just index it with the key byte, no need to search like in Node4 and Node16. But as you say, we only have 48 child pointers, so at most 48 positions in the child index array will be in use at any one time. The elements are small though, so it is not much of a waste.

---
Tags: data-structures, search-trees
---


# Question
Title: Facts about internal and external path lengths of binary tree
While learning binary tree's properties, I came across internal path length and external path length, number of comparisons required for successful and unsuccessful search.

My book specifies some facts about these as follows:

1. $S\_n=1+\frac{U\_0+U\_1+...+U\_{n-1}}{n}$
2. For large $n$, $S\_n=2 \log\_en$
3. Internal path length $I\_n$ of binary tree with $n$ internal nodes is at least $n \times \lg(n/4)$ and at most $\frac{n(n-1)}{2}$

Where

* $n \rightarrow$ number of (internal) nodes in binary search tree
* $S\_n \rightarrow$ average number of comparisons required for successful search in a random binary search tree with $n$ internal nodes
* $U\_n \rightarrow$ average number of comparisons required for unsuccessful search in a random binary search tree with $n$ internal nodes
* $I\_n \rightarrow$ Internal path length of binary tree with $n$ internal nodes
* $E\_n \rightarrow$ External path length of binary tree with $n$ internal nodes (not used above)

Out of these I can complete reason out only the maximum internal path length statded in point 3 as follows: It occurs in degenerate binary tree (point 3.6 on this page). In this case, internal path length is $0+1+2+...+(n-1)=\frac{n(n-1)}{2}$.

About the minimum internal path length, the book says following:

> The minimum internal path length occurs in case of the best case binary tree i.e. almost complete binary tree (maximum possible number of nodes having both children). Such tree has $(n+1)$ external nodes at height no more than $\lg {n}$. Multiplying these and applying the below property: $$E\_n=I\_n+2n$$ we get the bound: $$(n+1)\lg n-2n\<n \lg (N/4)$$

**Q1.** However I am still not clear how the above bound is obtained

**Q2.** Also I did not understood how first two facts out of above 3 are derived and especially what the first fact is meant to imply.

# Answer
> 3 votes
I'm assuming the following model for a binary search tree of size $n$. Consider the following infinite process. At step 0, we have the empty tree. At step 1, we have the tree having some arbitrary value at the root. At step $m\>1$, if the current (ordered) contents of the tree at the previous step are $x\_1\<\ldots\<x\_{m-1}$, we choose an interval uniformly at random among the $m$ intervals $$(-\infty,x\_1),(x\_1,x\_2),\ldots,(x\_{m-2},x\_{m-1}),(x\_{m-1},\infty),$$ choose an arbitrary element from the interval, and insert it to the binary tree. A *random binary search tree* of size $n$ is obtained by stopping this process at step $n$, and erasing the values at the vertices.

You can show that the arbitrary choices do not affect the distribution. Also, the relative order of the elements of the tree at step $n$ (in order of insertion) is a random permutation on $n$ elements.

You haven't explained what you mean by $S\_n$ and $U\_n$ exactly, so I assume you are using the following definitions:

* Let $T\_n$ be a random binary search tree of size $n$ *before erasing the values*. Choose one of the $n$ elements at random, and run binary search on $T\_n$ and this element. The average number of comparisons in this process is $S\_n$.
* Let $T\_n$ be a random binary search tree of size $n$ *before erasing the values*, and let $x$ be the random element inserted by the process at the following step. Run binary search on $T\_n$ and $x$. The average number of comparisons in this process is $U\_n$.

**First fact**

Given these definitions, the first fact is easy to prove. Suppose that the element we search for was inserted at step $i$. Note that the distribution of $i$ is uniform over $\\{1,\ldots,n\\}$. Inserting $i$ at step $i$ requires $U\_i$ comparisons in expectation. It takes us the same number of steps to reach this element at the current experiment, and one more comparison to verify that we have indeed found the element. The formula follows.

**Second fact**

Here we need a non-trivial argument, outlined in the Wikipedia article. Let the sorted elements in the tree be $x\_1\<\cdots\<x\_n$. Suppose that the element we look for is $x\_i$. The search goes through an element $x\_j$ if $x\_j$ is an ancestor of $x\_i$. Thus, given $i$, the average number of comparisons is $$\sum\_{j=1}^n \Pr\[\text{$x\_j$ is an ancestor of $x\_i$}\].$$ Now $x\_j$ is an ancestor of $x\_i$ if among all elements in $\\{x\_i,\ldots,x\_j\\}$ (or $\\{x\_j,\ldots,x\_i\\}$), $x\_j$ was the first inserted. Since the true order of insertion is a random permutation of $x\_1,\ldots,x\_n$, we conclude that $$\Pr\[\text{$x\_j$ is an ancestor of $x\_i$}\] = \frac{1}{|i-j|+1}.$$ Choosing a random $i$, this shows that $$ \begin{align\*} S\_n &= \frac{1}{n} \sum\_{i=1}^n \sum\_{j=1}^n \frac{1}{|i-j|+1} \\ &= \frac{1}{n} \sum\_{i=1}^n \frac{1}{|i-i|+1} + \frac{2}{n}\sum\_{i=1}^n\sum\_{j=1}^{i-1} \frac{1}{i-j+1} \\ &= 1 + \frac{2}{n}\sum\_{i=1}^n \sum\_{j=2}^i \frac{1}{j} \\ &= 1 + \frac{2}{n}\sum\_{i=1}^n (H\_i - 1) \\ &= \frac{2}{n} \sum\_{i=1}^n H\_i - 1 \\ &= \frac{2(n+1)}{n} (H\_{n+1} - 1) - 1. \end{align\*} $$ Here $H\_i$ is the $i$th harmonic number, and we used the identity $\sum\_{i=1}^n H\_i = (n+1)(H\_{n+1}-1)$. It is well-known that $H\_i = \ln i + \gamma + O(1/i)$ and that $\ln (n+1) = \ln n + O(1/n)$, and so $$ \begin{align\*} S\_n &= 2\left(1+\frac{1}{n}\right) (\ln n + \gamma - 1 + O(1/n)) - 1 \\ &= 2\ln n + 2\gamma - 3 + \frac{2\ln n}{n} + O\left(\frac{1}{n}\right). \end{align\*} $$

**Third fact**

The upper bound is given by a path, in which case $I\_n = 0 + 1 + \cdots + (n-1) = n(n-1)/2$. For the lower bound, it is easier to consider first the special case $n = 2^m-1$. In that case, the lower bound is given by a balanced binary tree. Such a tree has $2^k$ nodes at depth $k$, and so $$ I\_n = \sum\_{d=0}^{m-1} 2^k k = 2^m (m-2) + 2 = (n+1)\log\_2 \tfrac{n+1}{4} + 2. $$ More generally, if $n = 2^m-1+x$ for $x \< 2^m$, it is best to put the $x$ extra nodes at depth $m$, and so $$ \begin{align\*} I\_n &= 2^m(m-2) + 2 + mx \\ &= (m-2)(2^m+x) + 2(x+1) \\ &= (m-2)n + m-2 + 2(x+1). \end{align\*} $$ Notice that $m \leq \log\_2 (n+1) \< m+1$, that is, $m = \lfloor \log\_2 (n+1) \rfloor$. Therefore $$ I\_n = n\lfloor \log\_2 (n+1) \rfloor + O(n) = n \log\_2 n + O(n). $$ To get an actual lower bound, notice that $$ I\_n \geq (m-2)n + m \> n \log\_2 \frac{n+1}{4} \geq n\log\_2 \frac{n}{4}. $$

---
Tags: graphs, trees, binary-trees, binary-search-trees
---


title: clarification about first for cfg

text:
# Question
Title: clarification about first for cfg
S--\>ABCDE

A--\>a/ε

B--\>b/ε

C--\>c

D--\>d/ε

E--\>e/ε

i have solved first for above question but a little clarification is required

first(S)=

first(A)=a/ε

first(B)=b/ε

first(C)=c

first(D)=d/ε

first(s)=e/ε

the first for C is c (why is it not c/ε like the rest did i miss something) and i am not able to get proper first value for S can i get some help with explanation

# Answer
> 1 votes
first for your cfg will be as follows

first(S)=a,b,c

first(A)=a,ε

first(B)=b,ε

first(C)=c

first(D)=d,ε

first(E)=e,ε

here as you see in the S production we have ABCDE and we see first terminal for first of any production but in A ,B we also have ε as a result of which we consider C production ,but C has only terminal so we stop there itself hence first of S is a,b,c and (as only terminal is there for C first(C)=c)

---
Tags: context-free
---


# Question
Title: Let a > 0 be a constant. Find a simplified, asymptotically tight bound for the recurrence T(n) = aT(n-2) + C
So I have read the posts on this site involving recurrence relations, however this problem is a little different, because of the constant a involved with the recursive portion. I'm trying to solve this recurrence relation by expanding it out and here is what I have so far:

I'm not sure where to go from here and how to find the asmpytotic bounds.

# Answer
The first four lines of your argument were correct; all you missed was the proper generalization. In general, we see that $$ T(n) = c+c\alpha+c\alpha^2+\dotsb+c\alpha^{j-1}+\alpha^j T(n-2j) $$ Now we want to drive $T(n-2j)$ down to a value we know, namely $T(1)=c$. To do this we'll need $n-2j=1$ and so we set $j=(n-1)/2$, giving us $$\begin{align} T(n) &= c+c\alpha+c\alpha^2+\dotsb+c\alpha^{j-1}+\alpha^j T(n-2j)\\ &= c+c\alpha+c\alpha^2+\dotsb+c\alpha^{(n-1)/2-1}+\alpha^{(n-1)/2} c\\ &= c(1+\alpha+\alpha^2+\dotsb+\alpha^{(n-1)/2}) \end{align}$$ and this is just a geometric series, so I'll leave the last steps to you.
> 2 votes

# Answer
The trick here is to solve a modified recurrence in which there is no constant. Let $S(n) = T(n) - C/(1-\alpha)$. Then $$ S(n) = T(n) - C/(1-\alpha) = C + \alpha T(n-2) - C/(1-\alpha) = \\ C + \alpha (S(n-2) + C/(1-\alpha)) - C/(1-\alpha) = \alpha S(n-2). $$ (I found the constant $C/(1-\alpha)$ by solving linear equations.)

The solution to $S(n)$ with initial conditions $S(0),S(1)$ is easily found to be $$ S(2n) = \alpha^n S(0), \qquad S(2n+1) = \alpha^n S(1). $$ It follows that $$ T(2n) = \alpha^n (T(0) - C/(1-\alpha)) + C/(1-\alpha), \\ T(2n+1) = \alpha^n (T(1) - C/(1-\alpha)) + C/(1-\alpha). $$
> 1 votes

---
Tags: algorithm-analysis, asymptotics, recurrence-relation
---


# Question
Title: User recognition through keystroke pattern
Hello thank you for taking time looking at this question. Is it possible to determine the keystroke patterns for a certain user?

My idea is that, when the user enters their username & password it must contain a specific keystroke pattern that when analyzed it could probably predict the actual user and able to differentiate other user that might know the exact username and password from hacking or entering the account.

# Answer
Keystroke dynamics is indeed a form of biometric recognition that has been studied for a long time. It was already known in the telegraph era: skilled operators could recognize each other's “fist”, similar to recognizing someone's handwriting.

As far as I know, this is not precise enough to authenticate someone. A 2005 study by Araújo et al. results in a 96.34% success rate (3.66% false acceptance) in a controlled experiment, for an imposter, for typing the same user-chosen string 10 times (see §IV.B). The false acceptance rate for a hard-to-type password is likely to be worse. It can be used as a second authentication factor, but as an authentication factor, it's pretty weak.

These days, a lot of authentication is performed remotely, with the typing device under control of the unauthenticated user, who may be the attacker. This means that keystroke dynamics is not reliable in this setting.

Keystroke dynamic is sometimes used, not as a primary authentication factor, but to raise alerts when an account might have been compromised. On its own, it has poor signal, since a user with unusual typing patterns may be wounded, tired, using an unfamiliar keyboard, etc. It can be useful in combination with other factors however.
> 2 votes

---
Tags: security, user-interface, authentication
---


# Question
Title: How to find the element of the Digit Sum sequence efficiently?
Just out of interest I tried to solve a problem from "Recent" category of Project Euler ( Digit Sum sequence ). But I am unable to think of a way to solve the problem efficiently. The problem is as follows ( in the original question sequence has two ones in beginning , but it does not change the sequence ) :

> The Digit Sum sequence is 1,2,4,8,16,23,28,38,49.... where the $n^{th}$ term of sequence is sum of *digits* preceding it in the sequence. Find the $10^{15}th$ term of the sequence.

The naive solution can't be implemented because it takes a lot of time. I tried to reduce the problem to a case of matrix exponentiation ( that would takes $O(log ( 10^{15}))$ amount of time ) but could not come up with such a recurrence fitting the linear criteria as recurrence for this sequence is quite peculiar. It can be seen that the sequence is governed by the recurrence :

$$ a\_n = a\_{n-1} + d( a\_{n-1} ) ..... (1 )$$

where $a\_n$ is $n^{th}$ term of the sequence and $d$ is a function which when given a natural number as input returns sum of digits of the number ( eg. $\\;d(786)=21$ ). My second approach was to try to find some pattern in the sequence. It can be seen that the first few terms of the sequence can be written as

```
   a_1 = 1
   a_2 = 1 + d( 1 )
   a_3 = 1 + d( 1 ) + d( 1 + d( 1 ) )
   a_4 = 1 + d( 1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) )
   a_5 = 1 + d( 1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) ) + d( 1 +  d(
   1 ) + d( 1 + d( 1 ) ) + d( 1 + d( 1 ) + d( 1 + d( 1 ) ) ) )

```

From the pattern above it becomes that $n^{th}$ term of the sequence can be generated by the following method :

1. Write $2^{n-1}$ $1$'s with addition symbol between them.
2. Leaving the first $1$, then apply the function $d$ on the next $2^{0}$ terms then on next $2^{1}$ terms, then on next $2^{2}$ terms and so on.
3. Then apply the above method recursively on arguments of each $d$ function applied.

for example if n=3 we perform the following manipulations:

```
    1 + 1 + 1 + 1 + 1 + 1 + 1 + 1
    1 + d( 1 ) + d( 1 + 1 ) + d( 1 + 1 + 1 + 1 )
    1 + d( 1 ) + d( 1 + d(1) ) + d( 1 + d( 1 ) + d( 1 +d( 1 ) ) )

```

By dynamic programming I can generate the $n^{th}$ term using the above method in time $O(log ( 2^{10^{15}} ) )$, which again is no better than the naive solution.

**EDIT 1**
Another thing that can be observed is that $d(a\_n) = d(2^{n-1})$. For example $d(a\_6)=d(23)=d(32)=5$. But I am unable to make use of this point. I again tried to find a linear recurrence relation ( for matrix exponentiation ) , but I am unable to find it.

**EDIT 2**

Following is the graph when the sequence is plotted for smaller range ( first $10^6$ terms of the sequence are plotted ).

PS: I know it is not advisable to ask solutions from Project Euler. But I just want a new direction or a hint, as I have been moving in circles for past few days. If that is also unacceptable I can remove the question if suggested.

# Answer
> 4 votes
Your sequence is described in oeis.org/A004207 as digits sum. There are some good points like sequence mod 9 has repeating pattern $(1, 2, 4, 8, 7, 5)^\infty$, it shares digital roots with oeis.org/A065075 and oeis.org/A001370. If those properties are useful is open problem (because there is no closed form equation for $n-th$ number).

There are some properties of this sequence worth mentioning:
When you calculate $n-th$ number, you need to store only counter (to know which numer it was) and the number itself. To restart there is nothing more needed, as the next number is current number + sum of it's digits.

Taking some steps to ensure speed at first it is good to put numbers into array, avoiding naive mod and div calculations, which are expensive. This gives speedup by constant, but looking at times it does matter.

From starting point you can calculate next one, and next, and it works upto some point, this very point is number of digits change.
What is more important, patterns are changing with increase of numbers.
Digit sums are small in compare to numbers itself, so only the part of number will change on the most operations.
So what really can we cache?

We know that with two numbers with the same sum of digits the addition to get the next number will be the same. What about the next one?

# sasha

## Spoiler alert, below is quite explicit cache pattern

It depends on additional conditions, like the numbers that does not change in the *run*, I will call it *shift*, starting amount as *start*.

Taking some arbitrary *run*, like $100$, and taking *start* from $0$ to $9$ we can cache every pattern from starting point up to $100$, count number of elements (to know how to deal with counter, which is needed to give some $n-th$ number), and memorize it.

Ok. Until now any *start* is covered, what changes beyond $100$?
Unfortunately this patterns stop working, because if you try from $100$ making *start* equal $1$, the next number is calculated perfectly, but second one breaks.

Here we have to cover *shift* set to $1$ and *start* set to $0$. It also means calculating tables for different *shifts*.

*Do we really need to calculate all of them*? Not really, no.
Part of tables is just another one starting item further.
For example starting from $1, 2, 4, 8$ gives the same sequence shifted.
So do we need to calculate longer cache?
No, we calculate it up to *shift* change to pick up another *run*, so it will save a lot of memory.

Now when table is covered, we start from initial setting, pick sum from table, add counter and see that: from $1$ we get to $101$, update variables and jump to $218$, repeating the steps $305$ -\> $406$ -\> $517$ -\> $607$ -\> $719$ -\> $805$ -\> $904$ -\> $1003$.
Ok. What now?

We can continue until *shift* is higher than calculated.
Going further we might build more *runs* on fly, precalculate bigger runs, or observe another patterns (like we can partialy reuse tables already calculated).
Take a look at different *shifts* like $100, 1000, 10000, 100000, 1000000...$ they all give the same *run* being the same environment for digit sums, hence we can use the very same tables.
Making bigger tables than $100$ elements speeds up process further, making bigger jumps at once.

# Answer
> 4 votes
Since you asked for " a new direction or a hint " and I don't know the answer, I'll leave this here, I hope it's helpful. some ideas:

It makes sense there would be a pattern mod 9, since

$\forall k \> 1,k \in \mathbb{Z}\quad10^k \equiv 1 \mod 9$

Which you can prove by induction.

This means that all numbers are congruent to the sum of their digits mod 9.

Further, $a\_n = d(a\_n) \mod 9 \implies $ $$a\_{n} = a\_{n-1} + d(a\_{n-1}) = 2d(a\_{n-1}) \mod 9$$

If we keep expanding this recurrence we get

$a\_{n} = 2^n \mod 9$

Which explains the pattern mod 9.

It also gets us $a\_n = 9k + 2^n$. Every iteration we get a gap that is divisible by 9. How wide are those gaps?

Here's some less than general code:

```
import matplotlib.pyplot as plt
import numpy as np

#sum digits of n
def sum_digits(n):
    s = 0
    while n:
        s += n % 10
        n //= 10
    return s

#get the sequence to n digits
def calculate(n):
    retval = [1]
    for i in range(n):
        retval.append(retval[-1] + sum_digits(retval[-1]))
    return retval;

#empirically confirm that a_n = 2^n mod 9
def confirmPow2(a):
    count = 0
    for i in a[:10000]:
        if((i%9) != (2**count % 9)):
            print "false"
        count = count + 1

#find gaps divisible by 9 in a subset of a
def find9Gaps(a):
    count = 0
    S = []
    for i in a[:10000]:
         S.append(((2**count ) - i)/9)
         count = count + 1
    return S

#repeatedly sum the digits until they're less than 9...
#gives some interesting patterns
def repeatedDigitSum():
    for i in range(1000, 1100):
         print "=========for ",i
         while i > 9:
                 i = sum_digits(i)
                 print i

a = calculate(10**6)
b = find9Gaps(a)
plt.plot(range(len(b[:100])), b[:100])
plt.show()

```

The plot (for the first 100) looks exponential, but I don't think it's perfect.

Here's the output of

```
>>> plt.plot(range(len(b[5:60])), np.log2(np.array(b[5:60])))
>>> plt.show()

```

The last thing I have is that it seems if you sum the digits of a number, and then sum the digits of the resulting number, and repeat this, you eventually get that number mod 9.

Makes sense given the above fact about powers of 10 mod 9.

$$n \equiv d(n) \equiv d(d(n)) \equiv \cdots \mod 9$$

It gives an interesting sequence of numbers though.

Edit: Apparently this is called a "digital root".

---
Tags: time-complexity, number-theory
---


# Question
Title: Whatever that can be done using algorithm can be done using Turing machine
In 1937 how was Alan Turing so sure that all that can be done using algorithms can be implemented using a Turing machine? Since that period many new algorithms were implemented. What was his hypothesis behind this theory ?

# Answer
> 3 votes
The hypotesis is the following:

"Since an algorithm is a well-defined sequence of steps we can always execute an algorithm in a piece of paper(sometimes we may need a really big paper) using a pencil."

Then he created the Turing Machine who can simulate a hand using a pencil with an infinite paper.

---
Tags: computability, turing-machines, church-turing-thesis
---


# Question
Title: What is this approximation/error-reduction method called?
I'm wondering if anyone could help me find my footing in an approach I am taking with a student in my audio programming class for creating more accurate pitch detection algorithms. But the approach is not limited to pitch detection and in fact seems seems similar to Newton's Method, Euler's Method, Horner's Method, and so on. It is a very simple and general idea, and must have some background in numerical methods. I am looking for pointers to the literature.

Here is the idea. We have a function f which takes a signal and returns the fundamental frequency (such algorithms are close cousins to the Discrete Fourier Transform). In order to test its accuracy, I created simple sine wave signals of precise frequencies and tested the algorithm, and graphed the errors over a particular range; basically a perfect f would be the identity function, so we just had to record the deviation from the identity. The errors are basically sinusoidal. So I stored the errors in an array, and use cubic interpolation to create a continuous error function, and built that into the last stage of the algorithm. Of course, there is a problem, because the errors showed the deviation from a perfect f, and the original f is not perfect, so there would be errors in the errors, so to speak. So I iterated the process, correcting successively for errors in the errors, and the algorithm gets better each time. I have not yet figured out whether it will converge to some minimal error. I also have not tested it in musical settings. But it is very promising, and seems like a generally useful technique.

Separate from a programming trick, I would like to understand some of its properties such as convergence and so on. Anyone have any pointer, keywords, etc. for me to pursue this? I'm guessing it is a standard technique in numerical methods.

# Answer
> 1 votes
There is a high risk that you are "overfitting": you are fitting to noise, not to signal. If that's indeed what is happening, your method won't actually be useful.

The way to find out whether your method is actually making any real improvements (or whether you're just fooling yourself) is to have a holdout set: a separate set of signals, that you haven't used during the error correction. In other words, you have a training set (one set of signals) and a test set (a separate list of signals, with no overlap with the training set). You do all of the correction, corrections to the corrections, etc., on the training set. Then, once you've done that, you measure how effective your resulting corrected algorithm is on the test set. This will give you a sense of how effective your approach is.

# Answer
> 0 votes
You may look for the technique called **Linear Regression** to fit your function onto the plotted values. The errors can be minimized in Linear Regression through the **Gradient Descent** algorithm. As far as the interpolations are concerned, you seem to pretty much aware of those techniques, such as Newton's forward/backward interpolation methods, Newton's divided difference method etc.

---
Tags: terminology, approximation, numerical-algorithms
---


title: Turing tests and humans

text:
# Question
Title: Turing tests and humans
How are the questions framed in Turing tests? I mean what factors would one consider before framing questionnaire for the Turing Test.How the questions should be framed to make the test unbiased for a machine and humans?

# Answer
The basic objective of a Turing test is to come up with such an intelligent machine, which actually mimics the human way of communicating.

For that purpose, we'll carefully need to think about what normal humans would like to talk about, in a casual manner. Starting the talks with a friendly, informal manner may be a good thing. After that, you might want to know about the interests of the person you're talking to; you might start with...say, football, or cricket, economical crisis, united nations; there are literally a lot of topics.

Look up for the common trends in the humans...these can include some recent famous political scandals (I don't want to mention Panama Leaks here). Questions can be about the current good movies (hits and flops). You may even come up with a religious, or a philosophical discussion if that helps.

Incomplete questions, and then stating "you know the rest" after a half phrase can also be a good practice, because of the common sense the humans have to infer the essence, and background meaning of the question.

Last, but not the least, if you're going to ask the question from a chat-bot, then it is a real good thing that you place intentional grammatical mistakes, typos, and unclear phrases, that only a real human would be able to understand, because it's a natural thing for the humans to commit a mistake. Questions about past memories are also a good thing, especially when they are slightly offensive; discussing relationships, frustration, failures, fears etc. Emotion-based questions have more tendency to crack up the game.
> 5 votes

---
Tags: turing-machines, machine-learning, artificial-intelligence, turing-test
---


# Question
Title: Need help removing ambiguity from grammar
$E \rightarrow UV \bracevert EBE \bracevert V \bracevert \[E\]$

$V \rightarrow a \bracevert b$

$U \rightarrow \< \bracevert \> $

$B \rightarrow ? \bracevert ! \bracevert @ $

Order of precedence: $?$ \< $!$ \< $@$, with unary operators ($\<, \>$) being the highest

$?$, $!$, $@$ are right associative.

My attempt:

$E \rightarrow UV \bracevert EBT \bracevert V \bracevert \[E\] $

$T \rightarrow E$

$V \rightarrow a \bracevert b$

$U \rightarrow \< \bracevert \> $

$ B \rightarrow ? \bracevert B\_1 $

$ B\_1 \rightarrow ! \bracevert B\_2 $

$ B\_2 \rightarrow @ $

I'm not sure if I left out some corner cases during my conversion. Appreciate if you guys can point some mistakes out and offer some hints.

# Answer
In your attempt put $T\rightarrow UV \ \bracevert\ V\ \bracevert\ \[E\]$ instead of $T\rightarrow E$.

The idea is not to just replace symbols arbitrarily, but replace in such a way that it's derivations are a subset of possible derivations (which should be unambiguous).

And you can also use the procedure prescribed in textbooks or in Jonathan's answer in https://stackoverflow.com/questions/3106195/converting-ambiguous-grammar-to-unambiguous to remove ambiguity (unless the language in inherently ambiguous). I like Jonathan Leffler's answers because he gives lot of detail as well as intuition behind answers.
> 1 votes

---
Tags: context-free, compilers
---


# Question
Title: How to understand pushdown automata intuitively?
What is an intuitive way of understanding what a push down automaton is capable of computing?

# Answer
> 4 votes
Intuitively, a pushdown automaton uses a stack and using a stack we can do a depth first traversal of a parse tree. It means that we can accept strings which are in context free languages by using stack of a pushdown automaton (left-most derivation). This is not a rigorous proof that languages of pushdown automata are context free. For proofs you must see various textbooks on the subject.

# Answer
> 3 votes
Let's start with a finite automaton. Such a device can be viewed as a machine that has a fixed, finite number of boolean variables, like $s = $ "we've seen an even number of $0$'s in the input so far", or $s\_i = $ "the input so far, when interpreted as a binary number, is congruent to $i\pmod 3$". Using such a machine, we can count, but only up to a fixed, finite value.

A PDA can be viewed as a FA with one other variable, a stack. With such a machine, we can count up to an arbitrary number. This means that while the language $$ L=\\{a^nb^n\mid n\ge 0\\} $$ can't be accepted by any FA, it can be recognized by a PDA: for each $a$ we see in the input, we push a marker on the stack and for each $b$ we pop a marker off the stack. When we've seen all the input we stop and accept if the stack is empty and reject if it's not.

In a similar way, we can use the stack to store patterns in our input, which is why the palindrome language $$ P=\\{wcw^R\mid w\in \\{a,b\\}^\*\\} $$ can similarly be recognized by a PDA: we push the characters seen on the stack until we see a $c$ and then match the rest of the inputs against the contents of the stack. Since the stack will contain the characters in $w$, we can match the reverse, $w^R$ part of the input against the contents of the stack.

---
Tags: pushdown-automata
---


title: Transitivity of concat comparison

text:
# Question
Title: Transitivity of concat comparison
I am trying to solve the problem of finding the permutation, amongst all possible ones, of an array of strings, where the concatenation of them compares smallest lexicographically. I solve it with an sort with the following comparison

```
def concat_cmp(x, y):
    return cmp(x + y, y + x)

```

`+` is the string concat operator.

The solution passed all the test cases, but I cannot prove its correctness. Specifically, I cannot prove that this binary relation is *transitive*. Any help?

# Answer
> 2 votes
We denote the concatenation of $x$ and $y$ by $xy$. Your relation is $x \prec y$ iff $xy \< yx$ (where $\<$ is the lexicographic order). You want to show that $x \prec y \prec z$ implies $x \prec z$. Suppose therefore that $xy \< yx$ and $yz \< zy$. Our goal is to show that $xz \< zx$.

Say that two strings $s,t$ are *incompatible* if neither is a prefix of the other. If $s \prec t$ and $s,t$ are incompatible then there is an index on which they differ, and the first such index $i$ satisfies $s\_i \< t\_i$. Conversely, if there exists an index on which $s,t$ differ and the first such index $i$ satisfies $s\_i \< t\_i$ then $s,t$ are incompatible and $s \prec t$.

The proof is by induction on $|x|+|y|+|z|$. We consider several cases.

**Case 1.** $x,y$ are incompatible, and $y,z$ are incompatible. Let $i$ be the first index on which $x,y$ differ, and let $j$ be the first index on which $y,z$ differ. Then $k = \min(i,j)$ is the minimal index on which $x,z$ differ and $x\_k \< z\_k$, implying $x \prec z$.

**Case 2.** $x = yw$. In this case $xy \< yx$ implies $ywy \< yyw$, and so $w \prec y$. Induction shows that $w \prec z$, and so $xz = ywz \< yzw \< zyw = zx$.

**Case 3.** $z = yw$. In this case $yz \< zy$ implies $yyw \< ywy$, and so $y \prec w$. Induction shows that $x \prec w$, and so $xz = xyw \< yxw \< ywx = zx$.

**Case 4.** $x = zw$. In this case $xy \< yx$ implies $zwy \< yzw \< zyw$, and so $w \prec y$. Induction shows that $w \prec z$, and so $xz = zwz \< zzw = zx$.

**Case 5.** $z = xw$. In this case $yz \< zy$ implies $xyw \< yxw \< xwy$, and so $y \prec w$. Induction shows that $x \prec w$, and so $xz = xxw \< xwx = zx$.

**Case 6.** $y = xw$ and $x,z$ are incompatible. In this case $xy \< yx$ implies $xxw \< xwx$, and so $x \prec w$. Moreover, $yz \< zy$ implies $xwz \< zxw \< zwx$. Since $x,z$ are incompatible, there exists an index on which they differ, and the minimal such index $i$ must satisfy $x\_i \< z\_i$. It follows that $x \prec z$.

**Case 7.** $y = zw$ and $x,z$ are incompatible. In this case $yz \< zy$ implies $zwz \< zzw$, and so $w \prec z$. Moreover, $xy \< yx$ implies $xwz \< xzw \< zwx$. Since $x,z$ are incompatible, there exists an index on which they differ, and the minimal such index $i$ must satisfy $x\_i \< z\_i$. It follows that $x \prec z$.

---
Tags: sorting, strings, permutations
---


# Question
Title: Hash function which is invariant under small changes
I am looking for a hash function which is invariant under small changes.

E.g., if I have two strings `MyString` and `MySttring` which slightly differ, their hash values should only differ slightly as well.

Actually, this is the opposite of the normal concept of a hash functions (Avalanche effect) where even slight changes in the input lead to big changes in the output.

Does any one know of such a concept or a hash function? (It should not be the identity function ;))

*Background:* I want to store personal data (name, surname, date of birth). Due to data privacy laws, it is not allow to store the data in clear text. So, I need to hash it. There might be typing errors or OCR errors when storing the data. So, two hash values of the same person might differ. But they should only differ a little, so I know that the input data must have been very similar.

# Answer
> 0 votes
Use locality-sensitive hashing. Make sure you're not breaking the law.

---
Tags: algorithms, cryptography, hash, hashing
---


# Question
Title: JIT, AOT, Interpretation: What are differences between them?
I'm a beginner in Compilation. My understanding is that Interpretation means Interpreter takes source program as input and produce the result of this program.(source -\> Interpreter -\> run on the machine) Compilation means Compiler take source program as input and the front-end translate them into intermediate representation and then the back-end treats intermediate representation as input and produce machine code as output.(source -\> front-end -\> IR -\> back-end -\> machine code -\> run on the machine) However, I'm confused when I learn Java and JVM. JIT seems more complicate than compilation what I understand. And I'm find some new terminologies like AOT. What differences between these terms?

# Answer
> 4 votes
The key distinction between interpreters and compilers (AOT or JIT) is this:

* **Interpreter**: takes a source program $P$, and runs $P$, that means affecting the world through running $P$.
* **Compiler**: takes a source program $P$, produces a new program $P\_{asm}$. When we run $P\_{asm}$, it has the same (hopefully) effect on the world as $P$.

In a picture:

The advantage of compilers is that generated code is faster, because a lot of work has to be done only once (e.g. lexing, parsing, type-checking, optimisation), at compile-time, so is out of the way at runtime. And the results of this work are shared in every execution. The interpreter has to redo this work every time.

A problem of AOT compilers is that they often don't have enough information to perform **aggressive** optimisation. This information is only available at run-time.

A JIT compiler seeks to do better, more aggressive optimisation by executing only at run-time. However, a full compilation cycle is expensive (time-consuming), so shouldn't be carried out at run-time. How can we deal with this conundrum?

The key insight is that program execution time tends to follow the Pareto Principle: the great majority of a program’s execution time is (usually) spent running in a tiny fragment of the code. Such code is referred to as **hot**. Pareto’s principle tells us that (typically) a program contains some hot code. Think: innermost loops. With the information available at run-time, we can aggressively optimise such hot code, and get a massive speed-up. The rest is interpreted. Sluggishness of interpretation doesn’t matter, because it’s only a fraction of program execution time.

There is just one problem ... how do we find hot code? Remember, at compile time, the optimiser couldn’t work it out (reliably). How can we do better at run-time? Answer: Let’s use **counters**! We instrument the interpreter with counters, that increment every time a method is called, or every time we go round a loop. Whenever these counters reach a threshold, we assume that the associated code is hot. We compile that hot code, optimise it aggressively using information available at runtime. The jump to the compiled code, and execute it to completion. When the compiled code terminates, we go back to interpretation. In a picture:

Note that the description above is a simplification, the details are more complicated.

Note also that there is no need for the first part of a JIT compiler to be interpreted. In principle, and AOT can emit code that is effectively a JIT-compiler, and the job of the interpreter (evaluation and profiling) is carried out by ahead-of-time compiled machine code.

---
Tags: compilers
---


# Question
Title: Algorithm for grouping identical neighbors in a list
I have a list that I want to reduce to a smaller list by grouping identical neighbors. This list has many many redundant entries.

Example list:

```
1,1,1,1,1,2,2,2,3,3,1,1,1,2,2,2,2,2,2,2,2,2,4,4,4,4,1,1,1,1,1,1

```

After 'compression'

```
1,2,3,1,2,4,1

```

Is there an algorithm for doing this that is faster than O(n)? In other words, faster than just looking at the next neighbor?

```
while (1)
    n = 0, m = 1
    if (list[n] == list[m])
        remove list[m]
    else
        n = m
        m = m + 1
    if (m > list.size)
        break

```

If not, what about this problem makes it O(n)?

# Answer
You can use an adversary argument (exercise) to show that any algorithm which outputs the correct "compression" must examine all entries in the input, in *every* case. Such an algorithm cannot run in $o(n)$ on *any* input.

To answer your question, the reason that this problem requires a running time of $\Omega(n)$ is that the output depends on all entries of the input, in the sense that for every input and every entry there is a way to change the entry that affects the output. (Note, however, that not every change to the input results in a change to the output: for example $1,1,2$ and $1,2,2$ have the same output, but $1,3,2$ does not.)
> 2 votes

---
Tags: algorithms, time-complexity, data-compression, lists
---


# Question
Title: If O(log n) vs O(n) is exponential what is O(1) vs O(n)?
If one refers to using an `O(log n)` instead of an `O(n)` algorithm as an exponential speedup, how would one refer the speedup gained by using an `O(1)` algorithm vs an `O(n)`?

# Answer
There's no name for that, but the closest would be "infinite" speedup. $O(\log n)$ is considered an exponential speedup over $O(n)$, because $n$ *is exponential in* $\log n$: if we take the exponential function $f(n)=2^n$, we get $f(\log n)=2^{\log n}=n$.

However, $n$ *isn't anything in* $1$: there's no way to recover $n$ from $1$, no matter how quickly the function $f$ that we take grows, $f(1)$ will always be a constant (and never equal $n$). As $n\to \infty$, $1$ becomes infinitely smaller than $n$.
> 4 votes

# Answer
Your confusion seems to be related to the technical meaning of the word "exponential".
As the definition is given in http://www.learnersdictionary.com, it is defined as:

> Exponential growth is literally growth that becomes faster and faster as it continues. In ordinary use, however, exponential is understood to mean simply “very fast” when it is used with words like growth and increase.

Now, let's consider an example, where n = 256 (a power of 2 for the sake of simplicity). If n = 256, then \log\_2 n = 8. This is an "exponential" speedup, because of the log function.
As far as O(1) is concerned, you need to realize that \log\_n n = 1 in general. With that being said, O(1) will also be an ideal "exponential" speedup.
Hope this makes things clear.
> -1 votes

---
Tags: complexity-theory, terminology
---


# Question
Title: Finding pairs of points that have a given offset
Problem: Given a set of points $S = \\{x\_1, x\_2, x\_3, ..., x\_n\\}$ from $\mathbb{R}^m$ and an offset vector $v \in \mathbb{R}^m$, find a set $Z \subseteq S \times S$ containing $k$ pairs of points $(x\_i, x\_j)$ such that the quantity $|x\_i-x\_j-v|$ (Euclidean norm) is smaller for any pair $(x\_i,x\_j) \in Z$ than that of any pair not in $Z$.

One obvious approach would be to maintain a max-heap of size $k$ and run through all pairs of points $(x\_i, x\_j) \in S^2$, inserting pairs into the heap if $|x\_i-x\_j-v|$ is smaller than the current maximum. This algorithm has $O(mn^2 \log k)$ running time.

Is there a faster algorithm? Is there a lower bound on the complexity of this problem?

This problem is motivated by an application where $50 \leq m \leq 1000$, $10^5 \leq n \leq 10^6$, and $5 \leq k \leq 100$, and the running time should be in seconds, not minutes or hours (which is I the naive approach above is not applicable).

# Answer
One optimization I would propose is over the brute force search:

$$ \begin{align\*} d(\mathbf{x}\_i, \mathbf{x}\_j) &= \lVert (\mathbf{x}\_i-\mathbf{x}\_j) - \mathbf{v} \rVert^2\\ &= \sum\limits\_{k=1}^N (x\_i^k - x\_j^k-v^k)^2\\ &= \sum\limits\_{k=1}^N ((x\_i^k-x\_j^k)^2+(v^k)^2-2v^k(x\_i^k-x\_j^k))\\ &= \sum\limits\_{k=1}^N ((x\_i^k)^2+(x\_j^k)^2-2x\_i^kx\_j^k+(v^k)^2-2v^k(x\_i^k-x\_j^k))\\ \end{align\*} $$ as $(v^k)^2$ is the same for all pairs, we could simply drop it - doesn't effect minimization.

\begin{align\*} d(\mathbf{x}\_i, \mathbf{x}\_j) &= \sum\limits\_{k=1}^N ((x\_i^k)^2+(x\_j^k)^2-2x\_i^kx\_j^k-2v^kx\_i^k+2v^kx\_j^k)\\ &= \sum\limits\_{k=1}^N (x\_i^k)^2 + \sum\limits\_{k=1}^N(x\_j^k)^2 - 2\sum\limits\_{k=1}^N x\_i^kx\_j^k - 2\sum\limits\_{k=1}^N v^kx\_i^k + 2\sum\limits\_{k=1}^N v^kx\_j^k\\ \end{align\*}

Let's go back to matrix notation:

\begin{align\*} d(\mathbf{x}\_i, \mathbf{x}\_j) &= \lVert \mathbf{x}\_i \rVert+\lVert \mathbf{x}\_j \rVert - 2(\mathbf{x}\_i \cdot \mathbf{x}\_j)- 2(\mathbf{x}\_i \cdot \mathbf{v}) + 2(\mathbf{x}\_j \cdot \mathbf{v})\\ \end{align\*}

Note that all the terms, except the middle one is free of the pairwise computations and can be computed in $O(N)$ time and stored. To compute $(\mathbf{x}\_i \cdot \mathbf{x}\_j)$, one can assemble matrix $X$, which contains $\mathbf{x}\_i^T$ at each row and compute $D=XX^T$. Each element in this huge symmetric matrix, would then give you the dot product per pair: $D(i,j)=(\mathbf{x}\_i \cdot \mathbf{x}\_j)$. If memory is of concern, you can simply revert to iterative computation and not store the intermediate dot products. All in all, this would save a lot of time in pairwise comptutations, speeding up the entire search. I assume that you could couple this easy to implement approach with any other optimization to further boost the performance. In all the calculations I omitted $sqrt$ because it doesn't influence the relative comparison of distances.

If the assumption is that $\mathbf{v}=\mathbf{0}$ ($\mathbf{v}$ is null), the entire procedure boils down to a fast computation of distance matrix - this view might benefit certain applications.
> 4 votes

---
Tags: algorithms, computational-geometry, nearest-neighbour
---


# Question
Title: How exactly does on describe the formal semantics of the Applied $\pi$-Calculus?
In *"Mobile Values, New Names, and Secure Communication"*, Abadí and Fournet describe thet Applied-$\pi$-Calculus. Although I understood a great part of the description of the Applied $\pi$-Calculus, I'm still a bit confused as to what exactly its formal semantics consists of.

The authors define (on page 2):

> A *signature* $\Sigma$ consists of a finite set of function symbols, such as `f`, `encrypt`, and `pair`m each with an arity.

On page 3, they say that

> Given a signature $\Sigma$, we equip it with an equational theory, that is, with an equivalence relation on terms that is closed under substitution of terms for variables.

Then they proceed, still on page 3, to define *Structural equivalence*, which also *is* an equivalence relation, but defined on extended processes and not terms.

So after reading the paper a number of times and consulting some other resources on the Internet, I have concluded that the semantics of the $\pi$-Calculus depends on a given signature (and hence is "parametrized" in a sense); and that it is composed of:

* the signature and its equational theory, which is provided by us, depending on the application context (I may include symmetric cryptography functions and some equations modeling their behavior, and no asymmetric constructions at all, for example);
* the structural equivalence relation for processes;
* the internal reduction relation (structural semantics used for plain processes);
* the reduction relation including interaction with the environment.

Is this correct, or did I miss anything?

# Answer
You are roughly correct. From an operational point-of-view, applied-$\pi$ is 'just' a $\pi$-calculus where interesting values (rather than just pure names) can be communicated.

Note that in process theory we usually care about coarser notions of equality, such as observational equivalence. This is defined in Section 4.1. Alas observational equivalence is hard to work with in practise due to the universal quantification over all contexts, so we define a second relation which is easier to deal with, in this case labelled bisimilarity. In order to do this, we need labelled transitions rather than reductions. We must show that these two forms of computation coincide.

To make matters even more complicated, Theorem 1 which claims that observational equivalence coincides with labelled bisimilarity is wrong.
> 3 votes

---
Tags: semantics, pi-calculus
---


# Question
Title: Efficient algorithm for finding weakly connected components
We recently studied Tarjan's algorithm at school, which finds all strongly connected components of a given graph. I was curious however how one would find all *weakly* connected components (I had to search a bit to actually find the term).

The most obvious solution would be to do a BFS or DFS on all unvisited nodes and the number of connected components would be the number of searches needed. This is actually what Wikipedia suggests for weakly connected components, too.

My question is if there is a known algorithm that can find these components faster? Or is the BFS/DFS version fast enough (not sure exactly what for)?

# Answer
> 5 votes
Replace every directed edge $u \to v$ with an undirected edge $(u,v)$. Now use any standard algorithm for finding connected components in the resulting undirected graph.

One standard approach for finding connected components is to use DFS. This runs in linear time, i.e., $O(|V|+|E|)$ time.

You can't hope for any algorithm that will perform asymptotically faster: any correct algorithm will have to examine every vertex and every edge at least once, so will have to take at least $\Theta(|V|+|E|)$ time.

---
Tags: algorithms, graphs, efficiency, graph-traversal
---


# Question
Title: What are logical addresses and where do they actually reside?
While studying about *memory management*, *paging* and *segmentation* there is a lot of usage of phrases like `CPU generates logical addresses` and `logical addresses are converted to physical addresses` etc. I know that the term physical address refers to actual RAM, but I do not have clear idea about what logical address is and where does it reside.

So my questions are:

* What is meant by `CPU generates logical address`?
* Where do logical addresses reside (in RAM or somewhere else)?

Can anyone please explain these things.

# Answer
> 5 votes
Well, this is the entire point of "virtual memory".

When your program runs, the OS makes it believe it has all the memory just for itself. That is, addresses 1 to 10,000 (say), are all empty and ready for this program to use. If you run two programs, each one of them gets its own space - each one can access address 1 to 10,000 without any interference between the programs.

Obviously, for this to work, the OS must perform some clever bookkeeping, mapping the programs' "virtual memory" into places in the real memory (or hard disk). That is, when the first program access cell 200, the information **needs not be** in cell number 200 in the real memory. It may be somewhere else, but the OS is responsible of converting the (virtual/logical address) "200" of the first program to some (real) address X, as well as the virtual "200" address of the second program, to some other (real) address Y.

---
Tags: operating-systems, memory-management, virtual-memory, paging
---


# Question
Title: Prove whether this problem is decidable or undecidable
So I am reviewing my notes for this problem, and I cant seem to understand how this problem works. Say we have M, and M accepts an input that makes it visit every non-halting state.

I convinced myself that this problem is decidable, but I am having trouble proving so. A rough outline of my answer would be : Assume we have a TM T that has only one halting state, and if it wants to go through all the states it needs to pass through this halt state and we somehow need to show how they cycle through all the states as such.

Any help would be beneficial, thanks!

# Answer
I believe that you ask whether the following language is decidable:

$$L\_{\text{visit all}} = \\{ \langle M,w\rangle \mid \text{ $M$ run on $w$ visits all its non-halting states}\\}$$

I believe this language is undecidable. The reason is similar to the reason why the following language is undecidable: $$L =\\{ \langle M,w\rangle \mid \text{$M$ visit the state $q\_1$ when running $w$}\\}$$ Very iformally: You can see it by "designating" one state to be special, so if we reach it, it means acceptance. Then reaching all states is equivalent to halting problem.
> 0 votes

---
Tags: computability, turing-machines, undecidability, rice-theorem
---


# Question
Title: Would $\sf RP = NP$ imply $\sf NP = coNP$?
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?

# Answer
> 3 votes
If we will able prove that RP is closed under complement then we can say that If RP = NP then it imply NP = Co-NP.

But we don't know whether RP=Co-RP or not. BPP = P can be proved under some reasonable assumptions but RP $ \subseteq $ BPP.

If we show that RP = BPP then your statement will be correct.

*References:*

1. RP in Wikipedia
2. Notes on Randomized Algorithms (pdf)
3. RP in the Complexity Zoo

# Answer
> 1 votes
Use $\mathsf{RP=NP\implies NP\subseteq P/poly}$ in Cook and Krajicek, *Consequences of the provability of* **NP$\\,\subseteq\\,$P/poly** (Journal of Symbolic Logic, 72(4):1353–71, 2007; PS).

---
Tags: complexity-theory, complexity-classes, probabilistic-algorithms
---


# Question
Title: Algorithm to find a path connecting given nodes in a graph
Suppose I have $n$ nodes in a graph and I identify $x$ nodes in the graph (where $x \< n$). I would like to find a path to connect all those $x$ nodes I have identified. Is there any algorithm for such a scenario?

# Answer
> 1 votes
Your problem is known as the Steiner tree problem. While this problem is NP-complete, it has efficient constant-factor approximation algorithms.

---
Tags: algorithms, graphs, shortest-path
---


# Question
Title: Can the decision version of an optimization problem in NP, be in P?
It is well known that a optimization problem can be turned into a decision problem with an extra parameter: e.g. in TSP we are looking for the lowest cost for a tour, the decision version therefore could check whether a a tour exists which costs at most $K$.

Lets assume we are talking about an optimization problem which is either NP or NP-hard. Can the corresponding decision problem ever be in P?

NB: What I am trying to ask is: if a optimization problem cannot be solved in polynomial time, can the corresponding decision problem be solve in polynomial time?

# Answer
Optimization problems cannot belong to NP or be NP-hard any more than apples. NP is a class of *decision problems*, and NP-hardness is a property of *decision problems*. When we say that an optimization problem is in NP or is NP-hard, what we really mean is that the *corresponding decision problem* is in NP or is NP-hard.
> 4 votes

---
Tags: complexity-theory, optimization, decision-problem
---


title: What is an addressable cell size?

text:
# Question
Title: What is an addressable cell size?
This question started with a quiz question from my university: Consider a big-endian computer system with an addressable cell size of one byte. The values in memory cells 372 to 375 are shown in the table below. What 16-bit two's complement value (expressed as a decimal number) is stored at address 374?

```
Address    Value
372        0xC5
372        0x5E
374        0x7F
375        0x23

```

One thing I'm not clear about is what exactly does "addressable cell size of one byte" mean?

# Answer
Addressable cell size of one byte, in this context, means that every cell in memory contains one byte. Variables which take up more than one byte are spread across several contiguous cells.
> 2 votes

---
Tags: memory-access
---


title: Can a cross-compiler be self-hosting?

text:
# Question
Title: Can a cross-compiler be self-hosting?
My understanding is that a self-hosting compiler will take as input the language it is written in and a cross-compiler will output a language which runs on a platform which is different to what it runs on.

Can we combine these two compiler types into one?

# Answer
> 4 votes
This is certainly possible, and there are two possibilities:

1. There are two compilers for a language. For example, Haskell has GHC, and GHCJS, which is a JavaScript cross-compiler. GHC is written in Haskell, and GHCJS is written in Haskell (and normally compiled with GHC), so GHCJS is a self-hosted cross-compiler.
2. You run your self-hosted cross-compiler in a target language. So, if you had a Foo to Python cross-compiler, and it's the only compiler for Foo, and it's written in Foo, it can be self hosting, but you would have to cross-compile it, then run the result in a Python interpreter.

Basically, be careful that you don't confuse a language with a compiler. A language can have many compilers.

---
Tags: compilers
---


title: Lambda Calculus Argument Delimiter

text:
# Question
Title: Lambda Calculus Argument Delimiter
So I've been looking into lambda calculus on and off for months simply trying to understand the numerical system and the successor function. I understand that it's basically just argument evaluation, but the syntax confused me for the longest time. Finally, I found this:

S0 = (λ abc.b(abc)) (λ sz.z) = λ bc.b((λ sz.z) bc) = λ bc.b((λ z.z) c) = λ bc.b(c)

from this URL: http://palmstroem.blogspot.com/2012/05/lambda-calculus-for-absolute-dummies.html

and realized that I didn't understand how this worked because **there seems to be no delimiter indicating the start of argument space**. My question is: Is there an acceptable delimiter for this in lambda calculus, and, if not, how can I verbalize this when writing or viewing it?

*EDIT*: Some people seem to have misunderstood this, so let me explain better. How do I indicate that a function is being called on a specific set of arguments? For example, in most programming languages the indicator is just parenthesis

```
function(arg0,arg1,arg3...)

```

Is there an equivalent to this in untyped lambda calculus?

*ANOTHER EDIT*: Okay, it's still misunderstood as to what I mean. Let's talk about the successor function again. The wikipedia pages shows something like the following:

```
Succ=La.Lb.Lc.b (a b c)
               ^

```

The marked whitespace is annoying since It's not clear that the part in parenthesis is still part of the function itself, and instead looks like an argument is being passed to the function. Is there a delimiting character that separates the body of the function from the arguments on which it is to be called? Example:

```
Succ=((La.(Lb.(Lc.(b,((a,b),c))))),),,

```

The problem that I think I'm having is that since functions can be returned as primary values, the syntax doesn't express that very clearly. However, in the example that I gave, we can see that there are three commas without trailing inputs, indicating that the function takes 3 values (the function to find the successor of and the successor's potential arguments). Is there a good convention to express the point where a function's body ends and the values that it needs to be evaluated begin?

\*A VERY IMPORTANT EDIT: * **This is not about currying.**

# Answer
So, I think part of the problem is that the resource you're using is not using standard lambda calculus notation.

In most texts, there is a space between arguments. I would write $\lambda x\ y\ z\ldotp z$ in place of $\lambda x y z\ldotp z$. But, if you assume a convention that variables are always single letters, you can omit the space without ambiguity.

But I can't imagine one would ever write whole programs this way. Rather, this is more likely to show up in examples, code snippets, and small proofs, where there aren't many variables and the names don't matter.

Basically it boils down to this:

* A minimal lambda calculus only allows one argument per function, so there's no need for a delimiter. The dot denotes the function body.
* There is common syntactic sugar for multiple arguments, which abbreviates $\lambda x \ldotp (\lambda y \ldotp (\lambda z\ldotp z))$ as $\lambda x\ y\ z\ldotp z$.
* In a situation where variable names are assumed to be single letters, one could use $\lambda x y z\ldotp z$ in place of $\lambda x\ y\ z\ldotp z$.

There is no delimiter, other than the space, that I know of for arguments. Commas would be frowned upon, since they indicate tuples, rather than curried arguments.

**EDIT**: to respond to the OPs edit:

There is no such thing as multiple arguments in an untyped lambda calculus, at least not in standard ones. There are two ways to simulate multiple-argument functions.

1. Tuples: you can use a Church encoding to pass a single argument, which can be decomposed into multiple values. So you would write $f (\<x,y\>)$, where $\<x,y\>$ is some special syntax for making a pair, and then decompose it as $HD\ t$ and $TL\ t$ inside your function to get at each argument.
2. Currying: When, in an imperative language, you would write `f(x,y,z)`, you write $(f\ x\ y\ z)$, which is syntactic sugar for $(((f\ x)\ y)\ z)$. A function accepting multiple arguments is just a function which returns another function.

It turns out that these two are basically isomorphic, so which you do doesn't much matter.

Some languages, like Scheme, have built in syntax for multiple-argument functions, but I haven't seen anything like that in a formal lambda calculus. Usually they're intended to be minimal, and so when you don't need multiple-argument functions, you don't put them in.
> 5 votes

# Answer
People who do $\lambda$-calculus use a number of convenient abbreviations that make it a bit harder for the beginner to figure out what is going on. I will use no such abbreviations.

Since you are asking a very basic question it is difficult to guess where exactly your confusion lies. I will answer more broadly than is probably necessary, just to make sure you get your answer, and also for the benefit of others.

### Expressions are trees

It is a historic accident that we write text from left to right in a straight line. We are so used to this that we devised ways of representing data that is not naturally linear in such a linear fashion. For example, an arithmetic expressions is most naturally viewed as a tree, e.g.,

is an arithmetical expression. We have a way of writing it down in a line:

```
(3 + 8) * 7

```

Here is another way of writing the same expressions:

```
(   3+   8)*7

```

That is, spaces are not important. The font is not important.

The process of converting a string of symbols into the corresponding tree is known as *parsing*.

In $\lambda$-calculus it is exactly the same. Expressions are really trees and it would be much better to draw them as trees, but that is impractical. So we write them in a straight line.

### $\lambda$-calculus syntax

The syntax of $\lambda$-calculus (at least the basic version of it) is very simple. It is simpler than arithmetical expressions, and even simper than any programming language that people use in practice.

Spaces do not matter in $\lambda$-calculus.

There are precisely three ways in which you can create an expressions:

1. It can be a variable, say $x$, $y$, $z$, $x\_1$, $y\_{42}$ and similar. The letter $\lambda$ is not a variable because it is used for another purpose.
2. If we have two expressions, say $A$ and $B$ then we can juxtapose them and place parentheses around them to get $(A \\, B)$. It does not matter how much space there is between $A$ and $B$. This is called *application*.
3. If we have an expression $A$ and a variable $x$ then we can write $(\lambda x \\,.\\, A)$ to get an expression. It does not matter how much space there is between $\lambda$ and $x$. The period between $x$ and $A$ is irrelevant, it is just a visual embellishment. This is called *$\lambda$-abstraction*.

It may help to see an example. The expressions that you wrote as

```
 (λ abc.b(abc)) (λ sz.z)

```

is written without any abbreviations (such as omitted parentheses) as

```
 ((λa.(λb.(λc.(b((ab)c)))))(λs.(λz.z)))

```

I hope I got that right. As a tree it is

You should understand this picture before proceeding.

### How do we apply three arguments to a function?

We do no such thing. We can apply expression $A$ to expression $B$ by forming an application $(A \\, B)$. This is the only way to apply anything. We always apply exactly one thing to exactly one argument.

Nevertheless, we *can* nest applications to get the desired effect of applying several things. For instance

```
((f x) y)

```

is the application of `(f x)` to `y`. It has the effect of applying `f` to two arguments. To see how this works, suppose we wanted a function which takes two arguments and it returns the first argument. This would be

```
(λu.(λv.u))

```

To apply this function to `a` and `(c b)` we do a double application:

```
(((λu.(λv.u)) a) (c b))

```

The way to think of this is that `(λu.(λv.u))` first gets the argument `a`. It computes the result `(λv.a)`. Then `(λv.a)` is applied to the second argument `(c b)`, and it computes the result `a`.

If we want to apply `f` to three things `a`, `b` and `c` then we write

```
(((f a) b) c)

```

Without parenthesis and using standard conventions for abbreviations this is written as

```
f a b c

```

or equivalently as

```
f         a b      c

```

Keep in mind that we did *not* apply `f` to three things! Instead, we applied `f` only to `a`. Then we applied `(f a)` to `b`. Then we applied `((f a) b)` to `c`. This gave the desired effect of passing three things to `f`.

If we wrote

```
(f (a (b c)))

```

then that would be `f` applied to one thing, namely `(a (b c))`. This is different from `(((f a) b) c)`. If we wrote

```
((f a) (b c))

```

then that would be `(f a)` applied to `(b c)`, so in effect this is like applying `f` to two arguments `a` and `(b c)`.

I did not tell the whole story. I left out the concept of bound variables and I did not explain how substitution works. But I hope this clears up some misunderstanding.
> 3 votes

---
Tags: lambda-calculus
---


# Question
Title: similar language by two DFA then why wrong answer
I attempted a mock paper for finite automata .so i was asked to create a DFA which accepts a language in which inputs are a,b and number of b's should be divisible by 3.The first image is my answer for which i was not given marks .but when i checked the answer of the paper they gave the second image as the correct answer.Both the DFA give the accept the language(number of b divisible by 3),so can any one tell how the second DFA in the second is better than the first one,or where did i go wrong.

# Answer
First DFA does not accept $\epsilon$ which has 0 number of $b$'s which is divisible by 3 (0 is said to be divisible by 3). So first answer is incorrect, where as second is correct.
> 4 votes

# Answer
There is no problem with your DFA but the reason why the second image is more appropriate is because the DFA is having less number of states in other words it is an (optimized/minimized) DFA .May be you have not gone through further topics in finite automata like minimization of DFA .After covering that topic even you will end up with DFA which is minimized like the second DFA in the image. Its better if you cover all topics in finite automata before attempting mock tests.
> -1 votes

---
Tags: finite-automata
---


# Question
Title: How do search engines efficiently retrieve documents in a sorted (e.g. page rank) order from an already sorted (by document id) inverted index?
The standard way a search engine retrieves documents is by using an inverse index from words in the query to document ids. Since the ids are sorted, a query like "word1 AND word2" would fetch the lists of document ids two for word1 and word2, and find the intersection in linear time (similar to merge in merge sort).

But how would the search engine efficiently retrieve documents in some specified order , like page rank for example? Since the inverse indices for each word are already sorted by document id (to enable the merging described above), there seems to be no way to sort them also by page rank. (For instance, for "word1" the index might have ids : 5, 11, 19 where these documents have page ranks 3, 1, 2 respectively).

Retrieving the documents by document id first and then sorting by page rank at query time can be impractical if the number of documents to sort is large (say, millions), and especially if the user just wants the top page or two.

# Answer
> 1 votes
I don't know what search engines actually do, but one approach would be sort by decreasing pagerank, resolving ties using the document ID. (In other words, the primary sorting key is the page rank, and the secondary sorting key is the document ID.)

This still allows the merge operation. It also ensures that results are generated in decreasing pagerank order, i.e., the top-ranked results are generated first. Note that if two documents have the same document ID, then they'll definitely have the same pagerank, too, which is why this approach works.

# Answer
> 1 votes
One solution is to store a quantization of the pagerank in a direct access (by docid) memory mapped array together with the other scoring values like the page length. The term relevance score is immediately combined with the query-independent document score (pagerank,page length,...) and the new score inserted into the results priority queue (heap).

---
Tags: algorithms, time-complexity, search-algorithms, database-theory, information-retrieval
---