# Question
Title: Why is the throughput (performance) of the Slotted Aloha protocol ≈ 0.36
I've read that the throughput - that is, the amount of good useful messages relative to capacity - of the Slotted ALOHA protocol for communication networks is roughly 0.36%.

But its not clear how we arrived at that number.

Can someone explain it?

# Answer
Unlike in the regular ALOHA protocol, where other nodes can send messages that interfere with ours at any time, in the Slotted ALOHA protocol, the only other time a message can be sent to interfere with ours is if it's sent at the exact time ours is sent (since in Slotted ALOHA messages can only be sent at specific intervals, like every 5 seconds for example)

Therefore, the probability that our message will be the only one, and have no interference is the probability (in a Poisson Process) that only 1 message on the system (ours!) is sent on the mark

$$P\[(N(t + 1) - N(t)) = 1\] = \frac{{e^{ - \lambda\tau } (\lambda\tau) ^ 1 }}{{1!}} = \lambda\tau e^{ - \lambda\tau} = \lambda e^{ - \lambda}$$

This gives us a function of the throughputs for all $\lambda$s.

To find the $\lambda$ with the highest throughput (that is, what expected rate gives us the highest throughput) we take the derivative and set to zero:

$$e^{-\lambda} - \lambda e^{-\lambda} = e^{-\lambda} (1 - \lambda) = 0 $$

$$\therefore \lambda = 1$$

In other words, when $\lambda$ is $1$, our throughput is highest. How high exactly? Just plug it back into the function we came up with, $\lambda e^{ - \lambda}$ and get:

$$ 1 * e^-1 = \frac{1}{e} = 0.36787....$$

Here's nice graph comparing the two ALOHAs, made by Reuven Cohen.
> 4 votes

# Answer
The answer to your question given is quoted directly for the most part from 'Computer Networking: A top down approach' by Kurose and Ross 4th Edition.

" we assume the following: • All frames consist of exactly L bits. • Time is divided into slots of size L/R seconds (that is, a slot equals the time to transmit one frame). • Nodes start to transmit frames only at the beginnings of slots. • The nodes are synchronized so that each node knows when the slots begin. • If two or more frames collide in a slot, then all the nodes detect the collision event before the slot ends.

Let p be a probability, that is, a number between 0 and 1. The operation of slotted ALOHA in each node is simple:

• When the node has a fresh frame to send, it waits until the beginning of the next slot and transmits the entire frame in the slot. • If there isn’t a collision, the node has successfully transmitted its frame and thus need not consider retransmitting the frame. (The node can prepare a new frame for transmission, if it has one.) • If there is a collision, the node detects the collision before the end of the slot. The node retransmits its frame in each subsequent slot with probability p until the frame is transmitted without a collision."

We make the following definition:

"A slot in which exactly one node transmits is said to be a successful slot. The efficiency of a slotted multiple access protocol is defined to be the long-run fraction of successful slots in the case when there are a large number of active nodes, each always having a large number of frames to send."

The derivation of the maximum efficiency - the answer to your question is given.

"To keep this derivation simple, let’s modify the protocol a little and assume that each node attempts to transmit a frame in each slot with probability p (That is, we assume that each node always has a frame to send and that the node transmits with probability p for a fresh frame as well as for a frame that has already suffered a collision.) Suppose there are N nodes. Then the probability that a given slot is a successful slot is the probability that one of the nodes transmits and that the remaining N – 1 nodes do not transmit. The probability that a given node transmits is p; the probability that the remaining nodes do not transmit is (1 – p)^N-1. Therefore the probability a given node has a success is p(1 – p)N-1. Because there are N nodes, the probability that any one of the N nodes has a success is Np(1 – p)^N-1."

To obtain the maximum efficiency we find a p\* that maximizes the expression.

Also, to find maximum efficiency for a large number of nodes, we have to let N tend to infinity in Np\*(1 – p\*)^N-1. After performing the necessary calculation, you will get the maximum efficiency to be 0.37.
> 1 votes

---
Tags: computer-networks, performance, communication-protocols
---


# Question
Title: Syntax and formal grammar of a formal language
For a formal language, I wonder what differences and relations are between its syntax and its formal grammar.

A formal grammar
is a set of formation rules that describe how to generate the strings that belong to the formal language.

Wikipedia says that syntax

> is "the study of the principles and processes by which sentences are constructed in particular languages."
>
> the term syntax is also used to refer directly to the rules and principles that govern the sentence structure of any individual language.

So I wonder if for a formal language, its syntax and its formal grammar the the same concept? Thanks!

# Answer
> 6 votes
Syntax is a very general term that encompasses the description and properties of physical representation of languages, i.e. of sets of sentences intended to convey ideas, concepts, meanings, etc. It is to be contrasted with semantics that is concerned with what is being conveyed.

Syntax is often thought of as structured sets of strings of symbols on a given alphabet (sentences), but that is the simpler form. Many syntaxes have a more complex structure, such as spoken natural language, signed language, graphical languages, musical scores, etc.

Syntax could be thought of as just a way to describe the set of legitimate representations, but it is usually expected to also associate structure with these representations. This structure is the scaffolding that is used to associate meaning (semantics) with a syntactic construct.

Grammars are a specific way to define these sets of sentences. There are other ways, such as automata (e.g. FA, PDA, TM), or string set expressions (regular expressions). Some types of grammars (Context-free in particular, but not the only one) are the preferred medium for expressing syntax as they are complex enough to provide structure allowing to express semantics with enough perspicuity, while remaining simple enough to be intellectually tractable.

Regular grammar, for example, do not provide enough structure and expressive power for general syntactic structure, but are often adequate for the structure of simpler semantics constituants (identifiers, numbers, morphological strcture of natural languages).

On the other hand, while context-sensitive languages can define more complex sets of sentences, the associated structure is usually too complex for deriving semantics from it in a simple enough way.

Context-free grammar are convenient because they associate a tree structure with sentences. This tree structure can be seen as an expression in a formal algebra, from which meaning can be derived by a convenient and well understoof mathematical tool: the homomorphism.

There are other ways of associating a tree structure with a sentence, for example by considering derivation trees with the structure (see mildly context-sensitive formalisms).

One could also define the syntax with automata, but this is much more computational and less perspicuous.

**Denotational vs operational aspects**

The preference for grammars over automata may also be related to the preference for denotational definitions over operational definition. Many grammars may be seen as more denotational as they may be read as equational definitions of syntactic structures. Though it may sometimes be disputed, denotational definitions are perceived as closer to the essence and mathematical properties of the defined entity, as giving a more perspicuous understanding, more appropriate for mathematical analysis, while operational semantics are more encumbered with technical computational or algorithmic details on the use of these entities.

Hence, it is common practice to prefer denotational definitions as reference, including for syntax. Operational tools (such as parsers) are then derived for practical computational work, and have to be proved equivalent.

**Meta-language issues**

Note that, when I say that a grammar "may be read as equational definitions of syntactic structures", I assume that the grammar itself is a sentence in a formal language (the language for writing grammar) and that this language may be assigned one or several semantics by appropriate means. Indeed, there is at least one well known standardized language for writing context-free grammars which is the Backus-Naur Form (BNF).

Actually, different semantics can often be associated with the same syntax, though they will often be in some mathematical relation, possibly isomorphic. This is in particular the topic of what is called "abstract interpretations" and "non standard interpretations" of languages.

**Remark on the question**

When answering the question, I did take the expression "formal language" in a general sense of language formally defined, as often used in mathematical context, with syntax and semantics. But the discussion is very much the same in the case of natural language.

Now it is possible that the question was intended only for the consideration of formal languages as simple sets of strings, as in formal language theory.

I would tend to think that this should not change much the answer, since even formal language theory often sees more in its formal languages than simple set of strings. This is typically the case when it makes a difference between strong and weak equivalence of grammars. Furthermore, a grammar is usually only one possible way to define the language and/or give it structure.

# Answer
> 2 votes
The terms *syntax* and *grammar* are ambiguous, but most commonly, they both refer to the structure of utterances in a language. (These terms are opposed to *semantics*, which refers to what the utterances mean.) Additionally, *a grammar* is a particular description of the structure of sentences of a particular language. This is true both in linguistics and in computer science.

In linguistics, we further have the term *grammaticality*, which is ambiguous, too: with respect to a particular language, a sentence is either said to be *grammatical* if it is valid (it belongs to the language; it may be uttered) or if it conforms to its grammar (it has the right structure). These are not the same things. Chomsky used the example

```
Colorless green ideas sleep furiously

```

of a sentence that is perfect English grammatically, but still would never be uttered, because it doesn't make sense. Most texts would take the second stance and classify such a sentence as grammatical.

In computer science, instead of the term *grammatical*, we use the term *syntactically valid*. The issue remains the same: we can express things that conform to the structure of a language but still don't make sense.

For instance, take this C program:

```
#include <stdio.h>
int main(int argc, char* argv[]) { int i = 4; printf("%d\n", j); }

```

This is a valid C program, except that it uses an undeclared variable, `j`. Most compilers will throw an error and refuse to compile the program.

However, the syntax of programming languages is usually described by means of context-free grammars, which are incapable of requiring all variables in a program to be declared prior to use. Hence, any context-free grammar for C will accept this program.

Is it syntactically valid?

Many practitioners will say: **yes**,

* syntax is defined by a grammar;
* look, here's this grammar for C;
* the program conforms to the grammar, so it is *syntactically* valid;
* the problem of `j` being undefined is not a syntactical problem, but a semantical one.

Other practitioners will say: **no**,

* a grammar is only a first approximation of syntactic validity;
* `j` being undefined clearly makes the program invalid, and we can see that at compile time, without running it;
* hence, it is a syntactical issue, even when a context-free grammar doesn't detect it.

A second example:

```
#include <stdio.h>
int main(int argc, char *argv[]) { int i; printf("%d\n", i); }

```

The meaning of a C program is what it does when executed. In this case, the behavior is undefined, because the value of a variable is printed that is never set. Most would say this is a syntactically valid C program that isn't meaningful. Some may use a compiler that defines its behavior by always initializing undefined variables and say this program is perfectly valid, syntactically and semantically.

Instead of using context-fee grammars, we can describe syntax using more powerful techniques, such as attribute grammars or two-level grammars, which *can* require all variables to be declared, or initialized, prior to use. With respect to such a grammar, these two C programs will be *ungrammatical*. However, writing grammars to capture this correctly is not easy, and checking whether a given program conforms to a given grammar using such a technique is hard or even undecidable. As a result, such techniques aren't popular today.

---
Tags: formal-languages, terminology, formal-grammars
---


# Question
Title: Find longest common substring using a rolling hash
The longest common substring (LCS) of two input strings $s,t$ is a common substring (in both of them) of maximum length. We can relax the constraints to generalize the problem: find a common substring of length $k$. We can then use binary search to find the maximum $k$. This takes time $\cal O(n \lg n)$ provided that solving the relaxed problem takes linear time.

Finding a $k$-common substring can be solved using a rolling hash:

1. Compute hash values of all $k$-length substrings of $s$ and $t$.
2. If a hash of $s$ coincides with a hash of $t$, then we've found a $k$-length common substring.

Step 1 uses a rolling hash to achieve linear time but I can't see how we can perform step 2. in linear time. Any suggestions?

# Answer
In order to implement step 2, use a hash table. Add all the hashes of the $k$-length substrings of $s$ to the table. For each $k$-length substring of $t$, look it up on the table. This takes expected linear time for a large enough hash table.
> 2 votes

---
Tags: strings, hash, substrings, longest-common-substring, rolling-hash
---


title: Distance k-Dominating Set on a Tree

text:
# Question
Title: Distance k-Dominating Set on a Tree
I don't consider myself very good at math, but nevertheless I enjoy solving optimization problems like the ones often asked in ACM ICPC (a college programming competition). I recently came across an issue while trying to solve one of such problems. I'd appreciate any help to find a linear algorithm (something better than $O(n^2)$ is still OK) for the following problem:

> Given a tree $T = (V,E)$ we want to find the size of the smallest set $V'$ such that $V'$ is a subset of $V$ and for every vertex $u$ in $V$ there's at least one vertex $w$ in $V'$ such that $\text{dist}(u,w)$ is less than or equal to $K$, where $K$ is a given natural number.

Here, note that $\text{dist}(u,w)$ is the length of the shortest path from $u$ to $w$ in the tree (in terms of hops), and tree $T$ is unweighted.

I'm very aware that there is a known greedy algorithm for $K=1$, which is in fact the cardinality of the minimum vertex cover. Solving for a general $K$ is what I'm interested in. I thought about several approaches but none of them seem to convince me. Do any of you know how to approach this?

# Answer
> 5 votes
## Binary, rooted trees

Let's focus first on the case of binary, rooted trees (i.e., every vertex has either 0 or 2 children). This case can be solved in polynomial time using dynamic programming, with subproblems as defined below.

Let me first define some notation that will be helpful. $\newcommand{\dist}{\text{dist}} \newcommand{\dom}{\text{dom}} \newcommand{\gap}{\text{gap}} \newcommand{Ni}{\mathbb{N}\_{-\infty}}$ Let $T\_v$ denote the set of descendants of $v$, including $v$ itself, i.e., the vertices in the subtree rooted at $v$. If $S$ is a set of vertices, let $\dist(v,S)= \min \\{\dist(v,s) : s \in S\\}$. Define $\dom(S) = \\{v\in V : \exists s \in S . \dist(s,v) \le K\\}$; this is the set of vertices dominated by $S$. Finally, let $\gap\_v(S) = \max \\{\dist(v,w) : w \in T\_v \setminus \dom(S)\\}$, i.e., the *gap* of $S$ (with respect to $v$) is the depth of the deepest descendant of $v$ that is not dominated by some node of $S$. Also, define the *depth* of $S$ (with respect to $v$) to be $\dist(v,S)$. Define $\Ni = \mathbb{N} \cup \\{-\infty\\} = \\{-\infty,0,1,2,3,\dots\\}$.

The intuition is that we can build up an optimal dominating set recursively, bottom-up. Let $v\_0$ and $v\_1$ be the two children of the root, and suppose we have a set $S\_0 \subseteq T\_{v\_0}$ for the left subtree and $S\_1 \subseteq T\_{v\_1}$ for the right subtree. Can we combine $S\_0,S\_1$ somehow to get a dominating set for the whole tree? To determine the answer to this question, all we need to know about $S\_0,S\_1$ are their depth and gap (with respect to the root). Therefore, all that matters when searching for a minimum dominating set is their depth, gap, and size. We don't need to enumerate all possibilities for $S\_0,S\_1$; for each possible combination of depth and gap, we just need to know the minimum attainable size for a set with that depth and gap. This enables us to use dynamic programming effectively.

In particular, we will use the following definition of a subproblem:

> INPUT: a vertex $v \in V$, a depth $d \in \Ni$, a gap $g \in \Ni$
> OUTPUT: $n(v,d,g)$, defined to be the size of the smallest set $S \subseteq T\_v$ of depth $d$ and gap $g$, i.e., the size of the smallest set $S \subseteq T\_v$ such that $\dist(v,S)=d$ and $\gap\_v(S)=g$

You can use dynamic programming to solve these subproblems, traversing the tree in a bottom-up fashion. If $v$ is a leaf, $n(v,d,g)$ is easy to compute. Next suppose that $v$ is an internal node, with children $w,x$. Then we can compute $n(v,d,g)$ from $n(w,\cdot,\cdot)$ and $n(x,\cdot,\cdot)$ as follows. If $d\>0$ and $g\ge 0$, we use the recurrences:

$$n(v,0,-\infty) = \min \\{1 + n(w,d',g') + n(x,d'',g'')\\}$$

$$n(v,d,-\infty) = \min \\{n(w,d-1,-\infty) + n(x,d'',g''), \\ n(w,d'',g'') + n(x,d-1,-\infty) : d'' \ge d-1, d+g''+1 \le K\\}.$$

$$n(v,d,g) = \min \\{n(w,d',g') + n(x,d'',g'') : \min(d',d'')=d-1, \max(g',g'')=g+1\\}.$$

We have some easy base cases when $d\le 0$ or $g=-\infty$: $n(v,-\infty,g) = 0$ if $g = \max\\{\dist(v,w) : w \in T\_v\\}$, or $\infty$ otherwise; $n(v,0,g) = \infty$ if $g \ge 0$.

In the exposition above, $d,g$ are implicitly subject to the constraints that $d \in \\{-\infty,0,1,\dots,2K\\}$, $g \in \\{-\infty,0,1,\dots,K-1\\}$, $d \ge 0 \land g \ge 0 \implies d+g \> K$, $g \ge 0 \implies d \le g+K+1$, $g=-\infty \implies d \le K$ (since other combinations aren't possible). $d',g'$ and $d'',g''$ are implicitly constrained in the same way.

Finally, the size of the smallest distance-$K$ dominating set for the entire tree is given by $\max \\{n(r,d,-\infty)\\}$ where $r$ is the root of the tree.

Running time analysis: There are $O(|V| \cdot K^2)$ subproblems. Each recurrence can be computed in $O(K^2)$ time, by organizing the $\min$ computation suitably. Therefore, the total running time is $O(|V| \cdot K^4)$.

## Unrooted trees

It is easy to deal with unrooted trees: simply pick an arbitrary vertex to be the root, and now a depth-first search will turn it into a rooted tree. Then you can apply the above algorithm.

## Trees of arbitrary branching factor

The above algorithm can be easily generalized to trees whose branching factor at each vertex is $\le 2$ (i.e., each vertex has either 0, 1, or 2 children).

I haven't thought through what happens if the tree might have arbitrary branching factor (i.e., not restricted to $\le 2$). I expect that similar recurrences and subproblems will be applicable. If you organize the $\min$ computations cleverly, you might be able to achieve a low-order-polynomial running time, e.g., $O(|V| \cdot K^c)$ for some small constant $c$ (e.g., $c=4$). However, I haven't worked through the details; I'll leave that to you.

---
Tags: algorithms, graphs, optimization
---


# Question
Title: How to prove that a language is context-free?
There are many techniques to prove that a language is *not* context-free, but how do I prove that a language *is* context-free?

What techniques are there to prove this? Obviously, one way is to exhibit a context-free grammar for the language. Are there any systematic techniques to find a context-free grammar for a given language?

For regular languages, there *are* systematic ways to derive a regular grammar / finite-state automaton: for instance, the Myhill-Nerode theorem provides one way. Is there any corresponding technique for context-free languages?

---

My motivation here is to (hopefully) build up a reference question that contains a list of techniques that are often helpful, when trying to prove that a given language is context-free. Since we have many questions here that are special cases of this, it would be nice if we could document the general approach or general techniques that one can use when facing this sort of problem.

# Answer
A practical approach that in many examples works \[but not always, I know\] is trying to find the **nesting structure** of the strings in the language. "Nested dependencies" have to be generated at the same time in different parts of the string.

Also we have the **basic toolbox**, the regular operations $\cdot, \cup, {}^\*$ can be used within a context-free grammar:

1. concatenation: $S\to S\_1S\_2$ if you can split the language in two consecutive parts use this production ($S$ is the new axiom, variables $S\_1,S\_2$ generate the parts)
2. union: $S\to S\_1 \mid S\_2$ split into disjoint parts
3. iteration: $S\to S\_1S \mid \varepsilon$ (again $S$ is the new axiom, the language generated from $S\_1$ is repeated)

### Example 1

Unequal numbers can be handled using a simple trick, splitting in "less" and "more".

$L= \\{ a^mb^n \mid m\neq n \\}$

Now clearly $L= \\{ a^mb^n \mid m\< n \\} \cup \\{ a^mb^n \mid m\> n \\}$.

Consider first half: $L\_1 = \\{ a^mb^n \mid m\< n \\}$. If there must be more $b$'s we can generate an equal numbers of $a$'s and $b$'s on the one and *and* add at least one extra $b$: $L\_1 = \\{ a^mb^m b^i \mid m\ge 0, i\>0 \\} = \\{ a^mb^m \mid m\ge 0 \\}\cdot \\{ b^i \mid i\>0\\}$. This we can handle with concatenation from the basic toolbox.

Now the complete language also deals with the case we have more $a$'s. This we handle by using union.

$S \to S\_1 \mid S\_2$ (choose which part)

$S\_1 \to XB$ (extra $b$ part)

$X\to aXb\mid \varepsilon$ (equal number of $a$ and $b$)

$B \to Bb \mid b$ (one or more $b$'s)

$S\_2 \to AX$ (extra $a$ part)

$A \to Aa \mid a$ (one or more $a$'s)

This construction is also used to build more complicated languages, like $\\{a^ib^jc^k \mid i,j,k\ge 0 \text{ and }i≠j\text{ or }i≠k\\}$ as done in detail by Rick and babou here.

### Example 2

$K =\\{ a^kb^lc^m \mid l=m+k\\}$

A first "obvious" rewrite.

$K =\\{ a^kb^{m+k}c^m \mid m,k\ge 0\\} = \\{ a^kb^mb^kc^m \mid m,k\ge 0\\}$

In linguistice this is called "cross-serial dependency": the interleaving $k,m,k,m$ (usually) strongly indicates non-contextfreeness. Of course $m+k=k+m$ and we are saved.

$K =\\{ a^kb^{k+m}c^m \mid m,k\ge 0\\} = \\{ a^kb^kb^mc^m \mid m,k\ge 0\\}$

with productions $S\to XY$, $X\to aXb\mid \varepsilon$, $Y\to bYc\mid \varepsilon$

Similarly $K'= \\{ a^kb^lc^m \mid m=k+l\\} = \\{ a^kb^lc^lc^k \mid k,l\ge 0\\}$

with productions $S\to aSc \mid X$, $X\to bXc\mid \varepsilon$

Compare the difference in nesting of the variables involved in these languages: $k,k,m,m$ is like $(\_k)\_k(\_m)\_m$, where $k,l,l,k$ is like $(\_k(\_l)\_l)\_m$.

### Example 3

Using the same technique we can solve the language of strings in $1^\* 0^\* 1^\* 0^\*$ with equal numbers of $0$ and $1$, or

$K = \\{ 1^n 0^m 1^k 0^p \mid n+k=m+p \\} $

See elsewhere on our cs.exchange.

### Example 4

Here a more complicated example for the nesting (thank you Raphael).

$L=\\{b^ka^l(bc)^ma^nb^o \mid k,l,m,n,o\in {\Bbb N},k\neq o,2l=n,m\ge 2 \\}$

Replace $n$ by $2l$. We can now drop $n$ in conditions.

Replace $k \neq o$ by $k \> o \text{ or } k \< o$ (confused? $o$ is 'oh' not 'zero'). Apply tools for union. We work with $k \> o$ here. Also $k\>o$ iff $k=s+o$ and $s\>0$ where $s$ is a new variable. Replace $k$ by $s+o$.

$L\_1 =\\{b^{s+o}a^l(bc)^ma^{2l}b^o \mid l,m,o,s\in {\Bbb N},s\>0,m\ge 2 \\}$

Some simple rewrites.

$L\_1 =\\{bb^sb^o a^l bcbc(bc)^m (aa)^{l}b^o \mid l,m,o,s\in {\Bbb N} \\}$

Now we see the nesting structure, and start building a grammar.

$S\_1 \to TV$, $T\to bU$, $U\to bU \mid \varepsilon$ (see: concatenation and iteration here)

$V \to bVb \mid W$ (we generate $o$ $b$'s on both sides)

$W \to aWaa\mid X$

$X\to YZ$, $Y\to bcbc$, $Z\to bcZ\mid \varepsilon$

---

Final comment: these techniques help you come up with a candidate context-free grammar that will hopefully recognize your language. A correctness proof may still be needed, to ensure that the grammar really works to recognize your language (nothing more, and nothing less).
> 16 votes

# Answer
There is one characterisation of CFL that can be of use, the Chomsky-Schützenberger theorem.

### Dyck language

> Let $T$ an alphabet. We define the *Dyck*-language $D\_T \subseteq (T \cup \hat{T})^\*$ of $T$ by the context-free grammar $G = (\\{S\\}, T \cup \hat{T}, \delta, S)$ with $\delta$ given by
>
> $\qquad\displaystyle S \to aS\hat{a}S \mid \varepsilon, \quad a \in T$.

### Chomsky-Schützenberger theorem

> $L \subseteq \Sigma^\*$ is context-free if and only if there are
>
> * an alphabet $T$,
> * a regular language $R \subseteq (T \cup \hat{T})^\*$ and
> * homomorphism $\psi : (T \cup \hat{T}) \to \Sigma^\*$
>
> so that
>
> $\qquad \displaystyle L = \psi(D\_T \cap R)$.

Note that the homomorphism is extended to words (symbol by symbol) and then to languages (word by word).

## Example

Consider $L = \\{ a^n b^n c^m \mid n,m \in \mathbb{N}$. With

* $T = \\{ \[, \langle\\}$ (and, canonically, $\hat{T} = \\{ \], \rangle\\}$),
* $R = \mathcal{L}(\[^\* \]^\*\langle^\* \rangle^\*)$ and
* $\psi(x) = \begin{cases} a, &x = \[ \\ b, &x =\ \] \\ \varepsilon, &x = \langle \\ c, &x =\ \rangle \end{cases}$

the theorem implies that $L$ is context-free, in particular since

$\qquad\displaystyle D\_T \cap R = \\{\[^n \]^n \langle^m \rangle^m \mid n,m \in \mathbb{N}\\}$.

## Example 2

Show that $L = \\{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \mathbb{N}, k \neq o, 2l = n, m \geq 2 \\}$ is context-free.

Here, we need one type of parentheses for $a$, one for $bc$, one for $b$, and another used to model the $b$ that cause $k \neq o$. We use

* $T = \\{ \[, \langle, \vdash, \< \\}$,
* $R = \mathcal{L}(\<^+\>^+\vdash^\* \[^\* \langle\langle^+ \rangle^+\rangle \]^\* \dashv^\*) \cup \mathcal{L}(\vdash^\* \[^\* \langle\langle^+ \rangle^+\rangle \]^\* \dashv^\*\<^+\>^+)$ and
* $\psi(x) = \begin{cases} b, &x \in \\{\vdash, \dashv, \<\\} \\ a, &x = \[ \\ aa, &x =\ \] \\ bc, &x = \langle \\ \varepsilon, &\text{else} \end{cases}$

and apply the theorem. In order to see that $L = \psi(D\_T \cap R)$, we don't need more than the fact that matching symbols (e.g. $\[$ and $\]$) have to occur equally often in any $w \in D\_T$. Adding this contraint to the regular expressions we defined $R$ by, we get

$\qquad \begin{align\*} D\_T \cap R = &\\{\<^p\>^p \vdash^o \[^l \langle^m \rangle^m \]^l \dashv^o \mid p \geq 1, o \geq 0, l \geq 0, m \geq 2\\} \\ &\cup\ \\{\dots\\} \end{align\*}$

and therewith

$\qquad\begin{align\*} \psi(D\_T \cap R) &= \\{ b^{p+o} a^l (bc)^m a^{2l} b^o \mid p \geq 1, o \geq 0, l \geq 0, m \geq 2 \\} \\ &\quad \cup\ \\{ \dots \\} \\ &= \\{ b^k a^l (bc)^m a^n b^o \mid k,l,m,n,o \in \mathbb{N}, k \> o, 2l = n, m \geq 2 \\} \\\&\quad \cup\ \\{ \dots \\} \\ &= L \\;. \end{align\*}$

## To grammars and automata

If we want to have an automaton or grammar in the end, we have some more work ahead of us.

* Towards an automaton, construct the NPDA for $D\_T$ and an NFA for $R$. The former is standard and we have algorithms for the latter, provided the language is given in a suitable representation (see also here). Intersection both is another standard construction and $\psi$ can be applied to every transition individually.
* Towards a grammar, build one for $R$ (again, should be standard), take the one for $D\_T$ and intersect them. Then apply $\psi$ to the rule set (symbol for symbol).

Arguably, this is easy since algorithmic; the complexity lies in finding suitable $T$, $R$ and $\psi$. I don't know if this approach is (often) simpler than constructing PDA/grammars directly but it may allow to focus on the important features of the language at hand. Try for yourself!
> 11 votes

---
Tags: formal-languages, context-free, formal-grammars, proof-techniques, reference-question
---


title: Formal language inverse

text:
# Question
Title: Formal language inverse
How can you specify the "inverse" of a word, so: let's say a word consists of a's and b's the language is: $ww^{-1}$ the second word is the same as the first but every a is replaced by b and every b by a

# Answer
What you're calling $w^{-1}$ is a special case of what's known as a *homomorphism*, where, informally speaking, we define a map $h$, from an alphabet $\Sigma$ to strings over an alphabet $\Gamma$ and then extend this in a natural way to maps of words. In your case, the map is particularly simple: $h(a)=b$ and $h(b)=a$. There's quite a bit known about such maps; for instance both regular and context-free languages are closed under homomorphisms.

(For what it's worth, your $ww^{-1}$ language isn't regular.)
> 2 votes

---
Tags: formal-languages, terminology
---


# Question
Title: Gödels (first) incompleteness Theorem and the Halting Problem - How limiting is it?
When I first heard of these things I was very fascinated as I thought it sets really a limit to mathematics and science in general. But how practically relevant are these things?

For the Halting Problem: Are there more than some artificially constructed cases, where one can't decide whether the algorithm will terminate or not?

For the Incompleteness Theorem: Are there more than some artificially constructed cases, where one can't prove/disprove statement?

I'm asking this because it seems that in most areas of science it doesn't really matter that there are such fundamental limitations. Are they even there? I'd like to know where this really sets a limit and where it is really relevant.

# Answer
The halting problem being undecidable has lots of practical relevance, here is a quick example:

Writing anti-virus software is hard: We can't decide whether a given piece of code is malicious because if we could we could decide the halting problem.

To see this take a piece of code which takes as input a Turing machine $M$ and an input word $w$ and does something malicious if and only if $M$ halts on input $w$. If we could decide whether a given piece of code were malicious then we could decide whether this piece of code was malicious but then we would be able to decide the halting problem, which we know we cannot do.

What this is saying is that there is no perfect anti-virus software, it can't be done. That doesn't mean we shouldn't try to write anti-virus sotware, just that we will never be able to write a perfect one. In fact any statement about deciding what programs do is undecidable (see Rice's theorem).

With respect to Godel's theorem, Goodstein's theorem is an example of a statement which is unprovable using the Peano axioms.
> 9 votes

# Answer
> For the Halting Problem: Are there more than some artificially constructed cases, where one can't decide whether the algorithm will terminate or not?

there are quite a few "roughly practical/applied" contexts with active research where the halting problem plays a role:

* automated theorem proving. proving theorems by computers runs into the same undecidability limits of the halting problem.
* proving program termination for real programs is an area of research and shows up in eg compiler logic and program analysis.
* Kolmogorov complexity attempts to study the theoretical limits of data compression algorithms. finding an optimal compression (in a certain sense, ie finding the smallest TM compressing a string) is undecidable.
* undecidability shows up in some physical problems. eg dynamical systems.
* a basic problem studied called "the busy beaver" problem. still theoretical but less abstract than the halting problem and studied in particular for its connection. researchers have attempted to resolve this for decades for "small" TMs with few states/symbols.

here is an related/interesting quote from a recent paper studying the busy beaver problem "problems in number theory from busy beaver competition" by Michel (p.3):

> Actually, the halting problem for Turing machines launched on a blank tape is m-complete, and this implies that this problem is as hard as the problem of the provability of a mathematical statement in a logical theory such as ZFC (Zermelo Fraenkel set theory with axiom of choice). So, when Turing machines with more and more states and symbols are studied, potentially all theorems of mathematics will be met. When more and more non-halting Turing machines are studied to be proved non-halting, one has to expect to face hard open problems in mathematics, that is problems that current mathematical knowledge can’t settle.

in other words the halting problem actually encodes/encapsulates the challenge of attempting to prove new mathematical theorems in math/CS and therefore can be regarded as extremely deep/practical/applied in this sense. (however while some consider this observation obvious or trivial, this is also generally not a commonly held/voiced opinion.)
> 6 votes

# Answer
I am answering one of your two questions, regarding the halting problem.

First, the undecidability of the halting problem does not state that you cannot decide whether a given TM does not halt. It states that there is no general algorithm that can decide that for all TM.

This is a statement about our models of what constitute computation. But, according to Turing-Church thesis, that is all we have to express compuation.

Regarding the relevance, it is based on artificially constructed Turing Machines. But then, all TM are pretty artificial and constructed only to assert some facts about computation. Whether some TM are more relevant than others in practice is pretty much as important a question as the sex of angels, or the number of them that can stand on a needle head.

The undecidability of the halting problem tells us that there are general questions that cannot be solved by a general technique applicable to all cases. What I mean by general question is a question depending on some parameters, where the answer is to be found for some values of the parameters.

Recall that the purpose of much of our mathematics is to find general techniques to solve a family of problems. A typical example is the resolution of equations. The undecidability of the halting problem tells us that this is not always possible.

For example, it can be used to show that there is no general technique to decide whether a context-free grammar is ambiguous.

However, you question is a valid one. It may be that a problem is undecidable because you just made it a bit too general. Possibly, by restricting it a bit, you can make it decidable for useful and still large enough subfamily.

I do not have a spectacular example in mind, but I am sure there must be some.

I recall one true case of a program analysis problem that was proved NP-complete (unless it was undecidable, I do not remember well). Against all advice, a PhD student decided to tackle it anyway. He was actually able to show that some restrictions on the problem, that did not matter much in practice, turned it into a very tractable problem, thus enabling the use of various program analysis and optimization tools.
> 5 votes

---
Tags: computability, logic, halting-problem, applied-theory
---


# Question
Title: Expected number of maximal cliques in $G(n,p)$
The $G(n,p)$ random graph model creates graphs with $n$ vertices and each possible edge exists independently with probability $p\in (0,1)$.

Much is known about the (expected) size of a largest clique in these graphs, and it has been shown that the expected number of maximal cliques of size $d$ is

$${n\choose d} p^{d \choose 2} (1-p^d)^{n-d}.$$

To find the expected number of maximal cliques, just sum over all values of $d$ to get

$$\mu (G(n,p)) := \sum\_{d=1}^n {n\choose d} p^{d \choose 2} (1-p^d)^{n-d}.$$

I'm interested in the asymptotic growth of $\mu (G(n,p))$ as a function $n$. For example, if $p$ is fixed, does $\mu$ grow polynomially in $n$?

A quasi-polynomial bound is not hard to show. Since the expected maximum clique size is roughly $\omega(G(n,p))\approx\frac{2 \log n}{\log(1/p)}$, the number of cliques (not necessarily maximal) is $O( {n \choose \omega(G(n,p))+1}) = O(n^{\omega(G(n,p))+1})=O(n^{\frac{2 \log n}{\log(1/p)}+1})$.

# Answer
> 3 votes
Since $\mu$ is the sum of $n$ terms, we can estimate it up to a factor of $n$ by the maximal term: $$ \max\_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \leq \sum\_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \leq n\max\_{d=1}^n \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d}. $$ In order to find out which term is the largest, we can use the estimate $$ \log\_2 \binom{n}{d} p^{\binom{d}{2}} (1-p^d)^{n-d} \approx nh(d/n) + \binom{d}{2} \log\_2 p - (n-d)p^d, $$ which is true up to polynomial factors for $d = \omega(1)$. We can estimate the magnitude of the largest term by differentiating this quantity with respect to $d$. If you follow this path, you should obtain an estimate for $\mu$ which is tight up to polynomial factors in $n$.

---
Tags: graphs, probability-theory, random-graphs, clique
---


# Question
Title: Lower-bounding the Membership Problem in the Bitprobe Model
I am working through the following paper "Data Structures for Storing Small Sets in the Bitprobe Model" by Radhakrishnan et al. and am confused regarding one of their arguments about a lower bound.

In particular, they are trying to show that $s\_A(2, m, 2) \in \Omega(m^{4/7})$. That is, the goal is to store a set $S$ of $2$ elements from a universe $U$ of size $m$ such that a query of the form "is $x \in S$" can be answered using only $2$ bit probes. The $s\_A(2, m, 2)$ indicates the minimum number of bits required to answer such queries, and in particular, the scheme is allowed to be adaptive (the second probe can depend on the first one).

They begin by saying that such a scheme can be defined by three functions $a, b, c\colon \[m\] \to \[s\]$, where the query "is $x \in S$" is answered by first probing location $a(x)$ then probing locations $b(x)$ or $c(x)$ depending on the outcome of the first probe. They then go on to explain that this can be viewed as a bipartite multigraph where $G = (B = \[s\], C = \[s\], E = \\{\langle b(x), c(x)\rangle : x \in \[m\]\\})$. Lastly, they state that $E$ is naturally partitioned into sets $E\_1, E\_2, \ldots E\_s$, where $$E\_i = \\{\langle b(x), c(x)\rangle : x \in \[m\], a(x) = i \\}$$.

Now, my questions are as follows. First they make the assumption that "Each $E\_i$ is a matching $\ldots$ Details Omitted". Why can this assumption be made? I can't for the life of me figure out why this needs to be the case.

My second (and more important question) is this. They provide the following example: They state that edges with the same type of label (i.e $x$ and $x'$) belong to the same matching. In their caption, they state that if such a scheme were to exist, then there are some pairs that cannot be stored (such as $x$ and $y$ on the left). This is what I don't understand. They do not provide an explanation beyond the "If it were to exist in our graph, then the underlying scheme cannot store all sets of size two. In particular, it is easy to verify that if this configuration exists, there is no way to store the set $\\{x, y\\}$".

I am just getting myself familiar in this area, so some of the "obvious" things may not be so obvious to me right away.

# Answer
> 2 votes
First, the reason why the authors had to omit so many details is that the paper was published in a conference (SOCG) with a strict page limit. When you publish your paper, please provide a full version on your website with all the proofs. In my area usually the full details are in an appendix which is not available from the conference website since back in the day, the proceedings were printed and so a strict page limit had to be enforced. Nowadays many proceedings are online only and then there is no page limit, but it seems that your paper dates from before that period.

I'll only address your main question. Consider the structure for storing $\\{x,y\\}$. When you query $x$, you get either "left" or "right" at the first probe. Say you got "right". Then the right endpoint of the edge $x$ must be 1 (we use the convention that the output is the last bit read, see the paper). When querying $x'$, we read the same first bit, and so the right endpoint of the edge $x'$ must be 0. This means that the left endpoint of $y$ must be 1. This means that when querying $w'$, the first bit read must be "right". But then when we query $w$, we read the right endpoint of the edge $w$ which is 1.

Suppose now that you got "left" in the first probe of $x$. Then the left endpoint must be 1, and so the first probe of $y'$ must be "right". Therefore the right endpoint of $y$ must be 1, and so the first probe of $z'$ must be "left". But then when we query $z$, we answer the left endpoint of $z$ which is 1. In both cases we have reached a contradiction.

---
Tags: data-structures, sets, lower-bounds
---


# Question
Title: In Paxos, what prevents multiple values from being chosen?
Say we have two proposers (P1, P2), one acceptor (A), and two learners (L1, L2).

What would prevent this sequence of events from occurring?

1. P1 initiates a round numbered 1. A agrees to participate, and reports that is has not voted on any proposals.
2. P2 initiates a round numbered 2. A agrees to participate, and reports that is has not voted on any proposals.
3. P1 asks A to vote for some value `v1` in round 1.
4. A accepts `v1` and tries to notify learners. L1 receives the message and declares that `v1` is chosen.
5. P2 asks A to vote for some value `v2` in round 2.
6. A accepts `v2` and tries to notify learners. L2 receives the message and declares that `v2` is chosen.

# Answer
I'll assume this is Basic Paxos. Step (4) cannot occur - the acceptor A maintains in nonvolatile memory the largest promise it has made (the highest round it has agreed to vote on). At step (2), the max promise becomes 2. When A recieves P1's accept request in step (3) it will reject it because the accept request is from round 1 (this information is communicated in the accept request).
> 2 votes

---
Tags: algorithms, distributed-systems
---


# Question
Title: How do we make sure in Paxos that we don't propose a different value if a majority has formed?
Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

and I was confused about one specific part. How does or why does property $P2^b$ satisfy property $P2^c$?

These are the properties:

$P2^b = $ If a proposal with value $v$ is chosen, then every higher-numbered (i.e. approx. later in time) proposal issue by any proposer has value $v$.

$P2^c$ = For any $v$ and $n$, if a proposal with value $v$ and number $n$ is issued, then there is a set $S$ (some majority) of acceptors such that either:

(a)no acceptor in $S$ has accepted any proposal numbered less than $n$, or

(b)$v$ is the value of the highest-numbered proposal among all proposals numbered less than $n$ accepted by the acceptors in $S$ (some majority).

The paper uses $S$ to denote some majority and $C$ to denote some majority that has actually *chosen* a value.

The thing that I am confused about is, for me $P2^b$ is saying, ok once a value has been chosen, say at sequence number $n$ (i.e. roughly time $n$), then after that time, we want to make sure that any proposer is only able to propose the value of the majority (chosen value). If we have that, then, we do not risk the already formed majority from reverting weirdly. i.e. once we have formed a majority, we want it to stick and stay like that. However, it was not 100% clear to me why property $P2^c$ satisfied that requirement. I kind of see why (a) is a nice property to have, since, having (a) means that its safe to issue a new proposal $(n, v)$ since we contacted some majority $S$ and none of them had accepted anything in a time earlier than now $n$. So, if a majority had formed we would have seen at least one value and we did not see anything accepted, its safe to propose something since a majority has not formed.

---

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research

# Answer
> 2 votes
$P2^c\implies P2^b$ since $P2^c\iff (a)\lor (b)$ and the logical statement $(a)\lor(b) \implies P2^b$ is equivalent to $(a)\implies P2^b\land (b)\implies P2^b$.

Let's consider $(a)$. If no acceptor in $S$ has accepted anything below $n$, then $P2^b$ is trivially satisfied (the implication predicate is false).

Otherwise, assume $(b)$. Then there exists a highest-numbered accepted value $(v, n)$ for some acceptor within $S$, which the proposer will decide to send as an accept request. Thus $v$ must have been chosen already, since an acceptor had it.

---
Tags: algorithms, algorithm-analysis, distributed-systems
---


# Question
Title: Unrolling multi-variable mu (μ) expressions in type theory
Unrolling an iso-recursive μ-type expression such as, say, one isomorphic to natural numbers:

```
μα.1+α

```

using

```
unroll : μα.T → T[μα.T / α]

```

by three steps, for example, gives:

```
μα.1+α
μα.1+(1+α)
μα.1+(1+(1+α))
...

```

If I instead have a polymorphic list, such as:

```
λα.μβ.1+αβ

```

is there a necessary relative order to the expansion of λ and μ? Say I instantiate α to T:

```
μβ.1+Tβ
μβ.1+T(1+Tβ)
μβ.1+T(1+T(1+Tβ))
...

```

Can we instead unroll μ before applying the λ at an arbitrary step?

```
λα.μβ.1+αβ
λα.μβ.1+α(1+αβ)
λα.μβ.1+α(1+α(1+αβ))
...

```

It looks in this case like we could. What I'd really like to know though is how to expand an expression having *more than one μ variable*; say:

```
μα.μβ.1+αβ

```

I could start with a few unrolls with β:

```
μα.μβ.1+αβ
μα.μβ.1+α(1+αβ)
μα.μβ.1+α(1+α(1+αβ))
...

```

...starting with α instead looks more complicated:

```
μα.μβ.1+αβ
μα.μβ.1+(μβ.1+αβ)β
μα.μβ.1+(μβ.1+(μβ.1+αβ)β)β
...

```

...or maybe α-β alternation could work, say starting with β:

```
μα.μβ.1+αβ
μα.μβ.1+α(1+αβ)
μα.μβ.1+(μβ.1+αβ)(1+(μβ.1+αβ)β)
...

```

...or starting with α:

```
μα.μβ.1+αβ
μα.μβ.1+(μβ.1+αβ)β
μα.μβ.1+(μ(1+αβ).1+α(1+αβ))(1+αβ)
...

```

Where does it all end? I can't imagine they end up equivalent. Is there a standard approach?

# Answer
> 5 votes
> I can't image they end up equivalent.

That's where you're wrong! In fact, starting with two different unfoldings of some expression you can always keep unfolding them in such a way that they "meet" again.

This property is formally called confluence.

More formally: define

$$ T \rightarrow\_\tau T'$$

If $T'$ is the result of a repeated number of unfoldings of $T$. We have the following **Theorem**:

Suppose $$ T\_1\ {}\_\tau\\!\leftarrow T\rightarrow\_\tau T\_2$$

There exists $T\_3$ such that $$ T\_1\rightarrow\_\tau T\_3\ {}\_\tau\\!\leftarrow T\_2$$

The proof is a bit subtle. I'll just try and convince you using your own example: $$T = \mu\alpha\beta. 1 + \alpha\times\beta$$

The reductions you outlined contain a slight mistake, the correct "$\alpha$-reduction" is:

$$T\rightarrow\_\tau \mu\beta.1 + T\times \beta\qquad (1)$$

and not $T\rightarrow\_\tau \mu\alpha\beta.1 + (\mu\beta.1+\alpha\times\beta)\times\beta$ As you suggest.

The $\beta$-unfolding is:

$$T\rightarrow\_\tau \mu\alpha.1+\alpha\times(\mu\beta.1+\alpha\times\beta)\qquad (2)$$

Let's show both of these lead to the same term. Take $U(\alpha)=\mu\beta.1+\alpha\times\beta$. We have $$ T\rightarrow\_\tau \mu\alpha.1+\alpha\times U(\alpha)$$ By the above reduction. Set $T\_1=\mu\alpha.1 +\alpha\times U(\alpha)$. On the other hand $$T\rightarrow\_\tau 1+ T\times U(T)\qquad (3)$$

by composing (1) with a $\beta$-unfolding. Composing the second reduction with an $\alpha$-reduction gives $$ 1 + T\_1\times U(T\_1)$$

But since $T\rightarrow\_\tau T\_1$, we can replace $T$ by $T\_1$ in (3) to get identical terms.

---
Tags: type-theory, recursion, inductive-datatypes
---


# Question
Title: directed graph data structure with fast in/out neighbor query
If I store a directed graph $G$ in adjacency list format, one can find all the out-neighbors $j$ of a given vertex $i$ in $\mathcal O(d)$ time, where $d$ is the max degree of the graph. These are all the vertices $j$ such that $(i,j)$ is an edge of $G$. On the other hand, if I want to find all the in-neighbors of $i$, i.e. the set of all vertices $j$: $(j,i)$ is an edge, then this takes $\mathcal O(n)$.

If I want to answer both in- and out-neighbor queries fast, I could just store the graph $G'$ obtained from $G$ by reversing all the edges, but that doubles memory usage. **Is there a graph storage scheme for which both in- and out-neighbor queries take $\mathcal O(d)$ time, but doesn't require double the memory?**

# Answer
If you care about constant factors, then big-Oh notation is not a useful tool to help you compare or measure possible data structures. If you want to minimize storage as much as possible, you need to think about the layout of the bits -- and then it would help to know concrete parameters and information, like roughly how big $n$ is, a rough estimate of the average degree (averaged over all vertices), a rough estimate of the largest degree and the distribution of degrees, etc.

For instance, one scheme is to represent the list of out-neighbors using something more efficient than a plain linked list (e.g., a linked list of buckets, where each bucket contains $c$ elements, and where you choose an optimal value of $c$ to minimize expected space usage). Or, you can pack these lists of out-neighbors and in-neighbors into a single big array, with each vertex having a pointer to the first index in that array where the sequence of out-neighbors or in-neighbors exist. You can also arrange that each entry needs only $\lceil \lg n \rceil$ bits, where $n$ is the number of vertices.

Another scheme is to use a multi-linked list as Patrick suggests, but with a slight twist. Instead of storing a pair of vertices $(a,b)$ in each linked-list node, store $a \oplus b$ (the xor of the identifier for vertex $a$ and the identifier for vertex $b$). This will be present in two linked lists: the out-neighbors of $a$, and the in-neighbors of $b$. Each linked-list node will have two next pointers. Notice that, when traversing the list of out-neighbors of $a$, all of the nodes will have $a$ as one of the two vertices, so if the value $x$ is stored in the node, we know it represents an edge to $a \oplus x$ (since $a \oplus (a \oplus b) = b$). Similarly, when traversing the list of in-neighbors of $b$, the value $x$ in a node represents an edge from the vertex $x \oplus b$. This doesn't reduce the number of pointers compared to a naive scheme, but it halves the amount of space for storing the data (the vertex identifiers) in each linked-list.

There are many more such bit-packing tricks and considerations that can be tried when you care about constant factors.
> 2 votes

# Answer
I believe the best you can do without completely recreating the graph is a multi-linked list:

Assuming adjacency lists are the only structure that'll get you neighbors in $\mathcal{O}(d)$ time, you'll need one each for out- and in-neighbors. The same elements can be used by each list, so $(a,b)$ is both in the list of out-neighbors of $a$ and in-neighbors of $b$, but there will still be twice as many *pointers* as there are edges in the original graph.

Memory being a linear function of the number of edges, it's going to be of use mostly in sparse graphs.

EDIT: As D.W. shows below, this doesn't actually save any space.
> 0 votes

---
Tags: graphs, data-structures, efficiency
---


# Question
Title: Can we use domains other than the naturals in computability theory?
I wonder why people assume the domain of a computable function is $\mathbb N$? For example, in Wikipedia.

Can its domain be any countable set rather than $\mathbb N$?

Can its domain be an uncountably infinite set?

# Answer
> 6 votes
The domain is finite strings of symbols from some alphabet – i.e., initial contents of Turing machine tapes. The natural numbers can be easily coded as finite strings: either in unary using length or in some higher base using symbols from the tape alphabet as digits. Other countable sets (e.g., integers and rationals) can be coded if, and only if, there is a computable bijection between that set and the naturals. However, you can't let your domain be *any* countable set: for example, if you want your domain to be the set of Turing machines that halt on every input, you couldn't even tell which Turing machine a given finite string codes.

There's no way to use an uncountable domain because the initial contents of the tape must be finite and there are only countably many finite strings over any finite alphabet.

# Answer
> 5 votes
Models of computation based on "continuous domains" were initially developed by Dana Scott in the '60s (see Domain Theory).

Working from the reals, the domain is a partial order on certain subsets (compact intervals) of the reals, each of which can be identified with a real, but with a topology distinct from the usual. Computable functions, like continuous functions, preserve "limits" of computationally enumerable elements of the domain. For a good overview, see: Formalisation of Computability of Operators and Real-Valued Functionals via Domain Theory

# Answer
> 4 votes
its worth mentioning here theres a significant body of theory about theoretical computational models over the reals, "real computation". the model is in some ways more powerful than Turing machines and is also subject to some academic debate about its relative role in CS. see eg:

# Answer
> 1 votes
During the Hellenistic period in Greece, constructions by circle and ruler were an important computational tool. As an example, try to look at deferent and epicycle from the Ptolemaic system of astronomy not as an explanatory model, but as a practical algorithm for computing approximate positions of stars by circle and ruler. Also note that civil engineering needs computational tools for determining the static of buildings, and that circle and ruler are not too bad for that purpose. There are limitations to this computational method, when very small and very huge magnitudes occur together in the same computation. This is one of the rare occasions where greeks used techniques vaguely related to our modern positional number systems.

Papyrus was cheap enough to make this a practical method of computation, at least when you were not from Pergamon. Pliny the Elder claims that Pergamon tried to compete with Alexandria, and as a consequence papyrus was temporarily withheld from them. They invented parchment as a reaction, or at least significantly improved the production methods and the quality of parchment. But parchment was probably still too precious to consume it for something as auxiliary as computations.

---

This answer is "freely based" on information from The Forgotten Revolution: How Science Was Born in 300 BC and Why It Had to Be Reborn. I googled a bit to ensure that what I write is not too far off from "current consensus", but I'm lazy and this answer should be considered as "quite inaccurate".

# Answer
> -2 votes
Forgive me if get this wrong because I am here to try and learn as much as possible.

But it seems to me that, regardless of the base used there cannot be an infinte number of characters. As each character is used once (not sure about this) the computer or maybe its to do with chaos theory or the laws of probability or physics or something, but as each character is used once it can not be used again on its own, so each character has to be combined with another to form a string. So if you have 1 million characters and you now using strings of 2 characters you have 2 million possible strings to use, than once they are all used you need to use strings of 3 characters, so you have 3 million possible strings to use (I think but I'm not sure; my basic maths is rubbish) and so on till you have 1 000 000 000 000 possible strings. It would not take a computer a day to go through all possible combinations if it were set up to do just that. But if it is just going through the string combinations as normal it probably uses the same string multiple times so it would probably take years.

Please correct me if I am wrong, I am not great with maths (please see profile) please explain in a conceptual mannor.

This whole concept of a domain for a computable function is intriguing to me, What is the Function of N?

---
Tags: computability, computation-models
---


# Question
Title: Analysis of a recursive algorithm, where running time strongly depends on input
I want to find the worst-case running time of an algorithm, which follows the following recurrence equation: The worst-case running time is $\Theta(n^2) + T(n, 2, n)$, where

$T(x, i, y) = \begin{cases} 1 & \textrm{if $(x=0)$ or $(y=0)$ or $(i \> n)$} \\ x+y+ T(x-a,\quad i+1, \qquad b)\\ \ \qquad+ T(x-a,\quad i+1,\ y-b)\\ \ \qquad+ T(\quad\ \ \ a,\quad i+1,\ y-b) & \textrm{otherwise} \end{cases}$

where $a \in \\{0, ..., x\\}, b \in \\{0, ..., y\\}$, and $a,b$ can be different in each recursion step, dependent on the input.

(Note: $x$ and $y$ represent the sizes of two lists $|L\_1|=x, |L\_2|=y$, and in each recursion step, each list is split into two, i.e. into lists of size $a$ and $x-a$ (for $L\_1$), and $b$ and $y-b$ respectively (for $L\_2$).)

How can I analyze such a recurrence equation, i.e. determine $f$ s.t. $T(n, 2, n)\in O(f)$? In particular, I do not know how to deal with $a, b$, especially since they are completely dependent on the input of the algorithm.

(I can solve the recurrence equation for special cases of $a,b$, e.g. $a=\frac{x}{2}, b=\frac{y}{2}$ for all recursion steps, or $a=x, b=0$ for all recursion steps etc., but not in general.)

# Answer
In order to determine an upper bound on $T(x,i,y)$, consider instead the recurrence $$ T'(x,i,y) = \begin{cases} 1 & \text{if $x = 0$ or $y = 0$ or $i \> n$} \\ x + y + \max\_{\substack{0 \leq a \leq x\\ 0 \leq b \leq y}} S'(x,i,y,a,b) & \text{otherwise,} \end{cases} $$ where $S'$ is given by $$ S'(x,i,y,a,b) = T'(x-a,i+1,b) + T'(x-a,i+1,y-b) + T'(a,i+1,y-b). $$ If you have more constraints on $a,b$, you should adjust the bounds in the definition of $T'$ accordingly.
> 2 votes

---
Tags: time-complexity, asymptotics, recurrence-relation, recursion
---


# Question
Title: What algorithms exist for solving natural number linear systems?
I'm looking at the following problem:

Given $n$-dimensional vectors of natural numbers $v\_1, \ldots, v\_m$ and some input vector $u$, is $u$ a linear combination of the $v\_i$'s with natural number coefficients?

i.e. are there some $t\_1, \ldots, t\_m \in \mathbb{N}$ where $u = t\_1 v\_1 + \dots + t\_m v\_m$?

Obviously the real-number version of this problem can be solved using Gaussian elimination. I'm wondering, has the integer version of this problem been studied? What algorithms exist to solve it?

Note that this is using natural numbers, but not modular arithmetic, so this is somewhat separate from the Chinese Remainder Theorem and systems like that. Also, it seems related to Diophantine equations, but I'm wondering what has been done in the case where only non-negative integers are considered? This is also reminiscent of a multi-dimensional subset-sum problem, generalized to allow us to take an arbitrary number of copies of each vector. It also seems related to testing whether $u$ is an element of the lattice generated by $v\_1,\dots,v\_m$, except that here we only allow linear combinations with non-negative coefficients.

For anyone interested, this is motivated by looking at whether a Parikh vector is in a linear set, as in Parikh's Theorem.

In particular, I'm interested in an algorithm that could solve the problem using only natural number operations, avoiding going into the reals/floating point numbers.

# Answer
Your problem is NP-complete, by reduction from Subset Sum (it is in NP since the fact that everything is non-negative bounds the coefficients of the solution sufficiently well). Given an instance $S = \\{s\_1,\ldots,s\_n\\}, T$ of Subset Sum (is there a subset of $S$ summing to $T$?), we construct an instance $v\_1,\ldots,v\_{2n},u$ of your problem as follows. For each $1 \leq i \leq n$, we put $v\_i$ to be the vector with two non-zero entries: $v\_{i,i} = 1$ and $v\_{i,n+1} = s\_i$, and $v\_{n+i}$ to be the vector with a unique non-zero entry $v\_{n+i,i} = 1$. The target vector is $u=1,\ldots,1,T$. Each natural combination of $v\_1,\ldots,v\_{2n}$ equal to $1,\ldots,1,\ast$ must select exactly one of each of $v\_i,v\_{n+i}$, and so encodes a subset of $S$ whose sum is the value of the last component.
> 9 votes

---
Tags: algorithms, reference-request, linear-algebra, integers, knapsack-problems
---


# Question
Title: Rational of why Paxos only issues new values if its value is the largest one in the majority that he can see?
I was studying Paxos from:

http://research.microsoft.com/en-us/um/people/lamport/pubs/paxos-simple.pdf

Recall that Paxos is a distributed system algorithm with the goal that the processes participating in its protocol will reach consensus on one of the valid values.

I was reading page 4 of the paper where it says condition $P2^c$:

"For any v and n, if a proposal with value v and number n is issued, then there is a set S consisting of a majority of acceptors such that

* (a) no acceptor in S has accepted any proposal numbered less than n, or
* (b) v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S."

(Where S = any set consisting of a majority of acceptors. C = the set of acceptors that have accepted some value c, the letter C stands for the majority that has Chosen a value).

I was trying to understand better the conditions for issuing a proposal, specifically (b) is the one causing troubles for me.

For me (a), makes sense because we don't want to issue a new proposal with a higher sequence number if there has been any proposal that has been chosen from the majority we are able to see (i.e. S). Since anything that has been chosen is accepted and since something chosen is part of the majority C, if we issue a new proposal, we could risk confusing the current paxos instance when its already chosen a value.

However, (b) is less clear to me why we want it to hold. Recall (b) is:

(b) = "v is the value of the highest-numbered proposal among all proposals numbered less than n accepted by the acceptors in S".

Why are we interested in having that condition? Which safety properties does that condition help us maintain?

---

Author: Leslie Lamport

Title: Paxos made simple

Institution: Microsoft Research

# Answer
The paper already gives a detailed explanation to motivate that condition and explain why it is useful to prove that a protocol meets that condition. Read the development in Section 2 of the paper; it lays the chain of reasoning out very nicely.

To summarize: P2c helps us prove P2b; P2b helps us prove P1 and P2; P1 and P2 help us ensure that we meet the safety requirements outlined at the start of Section 2.1.

So, to answer your question "Which safety properties does that condition help us maintain?": that condition helps us maintain the three safety properties specified at the start of Section 2.1 of the paper (as the paper already explains).
> 2 votes

---
Tags: algorithms, algorithm-analysis, distributed-systems
---


title: floating point normalised value of -1

text:
# Question
Title: floating point normalised value of -1
I have, lets say, 8 bits mantissa and 4 bit exponent. Then,

`-1=1111 1111` there are no 0s so how can I normalise -1 in 2's complement form?

# Answer
> 0 votes
Sorry, I found out the answer myself. It is `1000 000` manitssa and `0000` exponent. for mantissa, `1.000 0000 = -128 *power(2,-7)`.

for exponent, `0000 = 0`. So, result= -128 * power(2,-7)

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


# Question
Title: Differences between substitution and rewriting?
I am continuing with my self-study of formal languages.

Given two alphabets $\Sigma$ and $\Delta$, a string substitution is a mapping from $\Sigma$ to $\mathcal P(\Delta^\*)$, which induces a mapping from $\Sigma^\*$ to $\mathcal P(\Delta^\*)$.

In case that a string substitution is a string homomorphism, it is a mapping from $\Sigma$ to $\Delta^\*$, which induces a mapping from $\Sigma^\*$ to $ \Delta^\*$.

A rewriting system, however, seems to be a relation on $\Sigma^\* \times \Delta^\*$.

So I wonder if the main difference between rewriting and substitution is that rewriting is a relation, which might not be a mapping, while substitution is a mapping? Thanks.

# Answer
There are three differences between substitutions and rewriting systems:

1. Substitutions happen one symbol at a time, while a rewrite rule can rewrite an entire substring at once.
2. Substitution is a single-valued function while in a rewriting system, several rewriting rules can apply to any given substring.
3. A substitution must specify what value is substituted for each symbol. Rewriting systems need not apply in all situations.

I would say that the first two are the major differences. You can define substitutions so that they are partial functions, and then the third difference doesn't apply.
> 3 votes

---
Tags: formal-languages
---


# Question
Title: Definition of the cyclic shift of a formal language?
Wikipedia says, the context-free languages are closed under

> the cyclic shift of $L$ (the language $\\{vu : uv \in L \\}$)

So I am looking for the definition of the cyclic shift operation on formal languages.

From the quote, what are required on $u$ and $v$? Are they in $L$, or in $alphabet(L)^\*$? Thanks.

# Answer
> 5 votes
The cyclic shift of a language $L$ consists of all cyclic shifts of the words in $L$. Instead of defining the cyclic shift formally, let me give an example. The following are all cyclic shifts of the word `monkey`:

`monkey` `onkeym` `nkeymo` `keymon` `eymonk` `ymonke`

To see the connection with the definition, consider `nkeymo`. If we write `monkey` as `mo` concatenated with `nkey` and then switch both parts, we get `nkeymo`. This corresponds to setting `u=mo` and `v=nkey` in the definition above.

To answer your concrete question, $u,v \in \Sigma^\*$. (The alphabet is usually denoted by $\Sigma$.)

---
Tags: formal-languages
---


# Question
Title: Paths between tuples, MSV, decision trees
I'm reading about Multiset Size Verification Problem and in the following paper - http://www.skynet.ie/~sos/mapviewer/docs/Voronoi\_Diagram\_Notes\_2.pdf \- I got stuck just on the first lemma. However, since my concrete problem is rather specific, I'll describe it as self-contained, so that no background in terms of what MSV really is will be needed (but I encourage you to check it :)).

Fix natural $k, n$ such that $k \le n$. Let $$ Y = \\{ (z\_1, z\_2, \ldots, z\_n) \in \mathbb{R}^n : |\\{ z\_1, z\_2, \ldots, z\_n \\}| = k \\} $$ Next, let $$ T = \\{ (z\_1, z\_2, \ldots, z\_n) \in \mathbb{R}^n : \\{z\_1, z\_2, \ldots, z\_k \\} = \\{1, 2, \ldots, k \\} \ \text{and} \ z\_i \in \\{1, 2, \ldots, k \\} \ for \ i \in \\{ k+1, \ldots, n \\} \\} $$ In the paper that I linked to, they claim that for any distinct $a, b \in T$, on any continuous path from $a$ to $b$ we must encounter a point $p$ that is outside $Y$, i.e. $p \in \mathbb{R}^n - Y$. Apparently, it is not hard to see that, but I have a big difficulty proving it formally.

I wasn't sure whether to ask this question on Math community, or here, since the problem itself is purely mathematical. It's closely related to CS, though.

# Answer
Consider any path from $a \in T$ to $b \in T$ inside $Y$. Let $t$ be the first time in which the first $k$ coordinates are not distinct. Prior to time $t$, for each $1 \leq i \leq k$, all coordinates in $j \in \\{k+1,\ldots,n\\}$ such that $a\_j = a\_i$ must keep satisfying this relation along the path, since otherwise there will be more than $k$ distinct values. Therefore at the point $t$, there will be fewer than $k$ distinct values. We conclude that the first $k$ coordinates always remain distinct, and that they determine the rest of the vector. In particular, the values in the first $k$ coordinates can't cross each other: if $a\_i \< b\_i$ and $a\_j \> b\_j$ then the intermediate value theorem shows that at some point $x$ along the path, $x\_i = x\_j$. We conclude that $a\_1,\ldots,a\_k = b\_1,\ldots,b\_k$. Since the first $k$ coordinates determine the rest, in fact $a = b$.
> 0 votes

---
Tags: decision-problem
---


# Question
Title: Describe a TM through denotation of the transition function
I'm trying to describe a TM through denotation of the transition function. Given is a TM that recognizes the language

$$ L ={\\{w\\#w} \mid w \in {\\{0,1}\\}^\*\\} $$ over the input alphabet: $$ \displaystyle\sum = {\\{}0,1,\\#\\} $$

My guess is first to place a word $$ w \in {\sum}^\* $$

on the tape, and in every cell a symbol one after the other:

and the rest would be denoted with squares. Something like this $$ ...w|\\#|w|\square... $$ the head would be on the first Symbol from $w$

So I guess now I know that
$$ \Gamma = \\{w,\\#,\square\\} $$

I could probably try to make a table using what I have now:

for $w$:

$q\_0 = (q\_0,w,\\#,R)$ R would be the direction the head is going

$q\_1 = (q\_{yes},w,\\#,N)$ N means the head doesn't move and $q\_{yes}$ means that the TM accepts w

Im not sure if what I'm doing is correct. I would appreciate if someone could tell me if I'm on the right track.

# Answer
> 3 votes
You are making way too many guesses, and seem to be confused on the difference between words (elements of $\Sigma^\*$, or $\Gamma^\*$) and letters (elements of $\Sigma$ or $\Gamma$). This is basic stuff and need to be understood before even pretending to think about transition functions.

Indeed, the Turing machine gets a string on its input tape (with letters from $\Sigma$) flanked by $\Box$'s. To be precise $w$ is *not* an element of the tape alphabet, but a string over the input alphabet $\Sigma$. The tape alphabet equals $\Gamma = \\{ 0,1,\\#,\Box \\}$ *plus* all the additional symbols that you need for the task you have to perform.

The task is: check whether the input is in fact a string of the form $w\\#w$, i.e., two copies of the same string separated with $\\#$. The Turing machine may write on the tape and use a little bit of memory, but cannot read stings $w$ in one go (which is what your question suggests). It makes steps on single letters like $(p,0,p\_0,\bar 0,R)$: "in state $p$ I read letter $0$, switch to state $p\_0$ \[to remember $0$\] write $\bar 0$ on the tape \[replacing $0$ to indicate I have seen it\] and move to the position on the right". (Now you have to add $\bar 0$ to $\Gamma$.)

So check your lecture notes on the technical details again, and start thinking how to do the comparison letter-by-letter. It is not that hard: just pretend you are the machine and analyse your steps on a simple example input.

---
Tags: terminology, turing-machines, automata
---


title: Efficient search with removal

text:
# Question
Title: Efficient search with removal
I want to search from a given set of elements. Along with that I also want to remove that searched element. The problem is that the number of these queries is $q=O(n)$, where $n$ is the number of total elements. Which data structure should I use. Also, I want to avoid hashing.

# Answer
Without any additional information about your setting or requirements, an obvious first choice is some self-balancing binary search tree, such as a red-black tree. It allows you to insert and remove elements in $O(\log n)$ time, where $n$ is the number of elements.

Following a standard engineering approach, try it out first. If it doesn't meet your requirements, analyze your situation more carefully, and try something else.
> 2 votes

---
Tags: algorithms, data-structures
---


title: Binomial heap multiplying nodes

text:
# Question
Title: Binomial heap multiplying nodes
**Input:** A max binomial heap $H$, and a pointer to a node $V$.
**Output:** A max binomial heap, where all the children of $V$ are multiplied by 2.

I have tried solving this by taking out the node $V$ together with it's sub-tree, multiplying all the children of V by $2$, rearranging the heap to close the hole, and adding V's children to the heap.

It sums up to $O(k\log n )$, where $k$ is the number on nodes in the tree containing $V.$
Can I do better than this? I'm sure I can but I don't know how.

# Answer
I think in this scenario you can just *bubble-up* one of the updated element to restore the max-heap property.

Notice that by the multiplication you have increased the keys in $V$ children. So the trees rooted at the children still have the max-heap property, but maybe $V$ does not anymore. You can repair this, by swapping the largest key of the children with the key of $V$. This restores the max-heap property for the subtree rooted at $V$. You continue by comparing the key of $V$ with the key of the father of $V$ and swap the key is necessary. You do this, until nothing was swapped, or you reach the root - its the typical **heapify** routine.

Since binomial heaps have depth at most $\log n$ and the degree is also bounded by $\log n$ the whole procedure needs $O(\log n)$.
> 1 votes

---
Tags: algorithms, data-structures, heaps
---


title: Definition of prefixes of a string

text:
# Question
Title: Definition of prefixes of a string
From Wikipedia:

> The prefixes of a string is the set of all prefixes to a string, with respect to a given language: $$ \operatorname{Pref}\_L(s) = \\{t \mid s=tu \mbox { for } t,u\in \operatorname{Alph}(L)^\*\\} $$ here $s\in L$.

So is it equivalent to $$ \operatorname{Pref}\_L(s) = \\{t \mid t \mbox { is the first $n$ part of $s$}, \forall n \in \\{1, \dots, \mbox { length}(s)\\} \\}? $$

# Answer
> 1 votes
No. As you have defined it, $t$ is only in the language if it is every prefix, except $\varepsilon$, of $s$. That definition describes $\emptyset$ if $|s|$ is not 1, or $\\{s\\}$ if $s$ is a single symbol. If you change ∀n∈{1,…, length(s)}, to $\text{s.t.}$ $1 \leq n \leq |s|$, then it would be almost equivalent. However the first language includes the empty string.

Also "first n part of" is not a very good way to describe a prefix of length n. It could be ambiguous. And you should define what $t$ is, i.e. $t \in \Sigma^\*$.

---
Tags: formal-languages
---


# Question
Title: Need an algorithm to find the input factors that are most affecting the output
I apologize if this question is already answered and appreciate any pointers to existing answers. I'm not familiar with statistical or data mining terms so my search was limited to basic words used in the title of this question. I did look at some algorithms but could not decide if they serve the purpose.

I'm looking for an algorithm that can give me % probability or % confidence that out of given set of input factors which inputs are affecting the output most. Let us take an example below and assume that input and output will be recorded 4 times a day for a month.

Output:

* Phone's battery drainage
* Phone heating up (temperature).

Input:

* Ambient temperature
* Which apps were used most when the output was measured (multiple input points)
* Number of calls received and call length
* Screen brightness
* GPS connectivity enabled?
* Bluetooth enabled?
* Cellular signal strengh

If we measure this data for month, we will find that *Cellular Signal Strength* and *screen brightness* probably will be linked to *Battery Drainage* most. On the other hand *3D resource intensive games* will be linked to *Phones heating up* the most. Can I deduce such relationship using any existing algorithm(s)?

# Answer
> 2 votes
## Fundamental limitations on what you can achieve

The principled answer is: No, you can't reliably deduce such causal connections. When you have only observations of the data, you can use statistical analysis to look for correlations, but you can't deduce causation. Correlation does not imply causation. You are looking for causality, but you cannot infer causality from field data (from external, uncontrolled observations of a system). To test causality you need a controlled experiment.

This is a problem not just in principle, but often in practice as well. In practice, we might have correlations among your "independent variables" or confounding factors you haven't accounted for, which causes correlations that aren't an indication of causality.

For instance, you might find that ambient temperature is correlated to display brightness (because at night it is cooler and darker, so phones turn down display brightness, whereas at day it is warmer and brighter, so phones turn up display brightness to compensate for the daytime light). Now we'd expect that when the display brightness is higher, the battery will be drained faster. Can you deduce this causal connection from statistical inference applied to some observations? Well, you might observe a correlation between display brightness and battery drain rate, which sounds good. But if display brightness is correlated to ambient temperature, then when you do a statistical analysis, you might also discover a correlation between ambient temperature and display brightness -- and that's a spurious correlation that doesn't indicate any causal connection.

## Pragmatic, engineering answer

That said, the pragmatic answer is to use statistical analysis of your data to look for correlations, and then hope that at least some of the correlations will represent something real. You have to go into it with eyes open knowing that some of the correlations will be spurious, for the reasons explained above, but maybe that's OK. Maybe statistical analysis can still be useful to you.

So, how should you do the statistical analysis? There are many possible ways. It's best to say what is the best; that probably depends upon what relationships between the input and output you think are plausible.

But a very simple approach that I suspect will work well for you is to use linear regression. Try to find a linear model that expresses an output variable (e.g., the battery drain rate) as a weighted linear combination of the input variables. Linear regression can find the best weights for you that minimizes the prediction error.

Then, the size of those weights tells you exactly what you want to know. Suppose you are predicting the battery drain rate, and in your linear model the weight for the screen brightness input variable is 0.7. This means that if you increase the screen brightness by adding $\Delta$, then the battery drain rate is predicted to increase by adding $0.7 \Delta$.

## Tricky details

There are a few things about your specific problem that might be a bit tricky.

One tricky aspect is the business about apps, and how to code that into a linear regression framework. One way is to pick a few categories of apps, and then have a separate indicator input variable for each category (0 if that app is not present, 1 if it is present). However, you don't want to have too many input variables, because that will require a lot more data to reliably form a linear model. A few dozen app categories might be fine, but thousands of input variables for the thousands of different possible apps probably would not be.

Another tricky aspect arises if you expect there to be non-linear dependencies, and you want to find them. For instance, you mention in a comment the possibility that low cellphone signal strength combined with running a 3D game might increase battery drain rate in a way that neither alone would. If you expect those kinds of non-linearities, one standard way to deal with them is to introduce new input variables for "interaction effects": e.g., you introduce a new input variable which is the product of the signal strength times the indicator variable that indicates whether a 3D game is running. (These new input variables are derived from the other input variables, but in a non-linear way.) You can introduce one new "interaction" input variable for each pair of original input variables that you think might exhibit a combined effect of this sort (where the effect of their combination is greater than the sum of their individual effects). This is a standard technique that you can find described in good tutorials on linear regression.

Ultimately, there's lots more to say on statistical data analysis, linear regression, and applying it to practice -- more than I can write in a single answer. I recommend you read a good tutorial or two on linear regression and maybe the relevant chapters of some statistical textbooks. If you still have more questions after all of that, it's also worth knowing about Cross Validated, a Stack Exchange site on statistics.

# Answer
> 1 votes
Well, you are asking for derivatives! You want to measure how the change of an input affects the output. That's exaclty a derivative.

Call "Cellular signal strengh" x and "Phone's battery drainage" f(x).

Let's say that you fix the cellular cellular signal strengh to a level of 3 ($x\_0=3$). You measure a corresponding phone's battery drainage of 10% / hour ($f(x\_0) = f(3) = $ 10% /hour).

Then you change the signal strengh to a level of 4($x\_1=4$). The phone's battery drainage dropped to 7% / hour ($f(x\_1) = f(4) =$ 7% / hour).

This way you estimate a corresponding change of the output with respect of the input (aka derivative) of $\frac{f(x\_1) - f(x\_0)}{x\_1 - x\_0} = \frac{7 - 10}{4-3} $ % /hour = - 3 % / hour = $f'(\xi)$ with $\xi \in \[x\_0, x\_1\]$.

You estimate that a change of signal level of 1 gives you a battery drainage 3% less than before. Note that the information it gives you information is just "local": that value is calculate in the proximity of level 3, so close to level 1 you could get a very different change.

How is that useful? Let's say that you repeat the same measurement, but this time regarding temperature. You might find out that a temperature change of 1 degree raises your battery drainage of 0.1% / hour.

Now you can compare the different effects: a small change in the signal level gives you a big change in the battery drainage, while a small change in temperature gives you a very small change. Is it what you were asking for?

A final remark: here it is very important how you gather data, how fine (=resolution) the data is and how often you get it.

If you want to gather data from a mobile phone that is under actual use and is not being tested in controlled environment, you have to make sure that the polling rate is high enough: ambient temperature might change slowly (minutes), but signal strength might change pretty fast (seconds). Thus you have to make sure that you can resolve these fast changes.

---

Let's formalize a little bit.

We say that the output is a vector $\vec{x} = (x\_1, x\_2, x\_3, x\_4, ...)$, $x \in S$ where S is the set of the possible values of the input. Then the output is $f = f(x)$, a function that takes the touple $\vec{x} = (x\_1, x\_2, x\_3, x\_4, ...)$ and gives you the corresponding output.

What you are computing here are the partial derivatives of $f(\vec{x})$:

$\frac{\partial f(\vec{x})}{\partial x\_1}|\_{\vec{x} = (x\_1, x\_2, x\_3, x\_4, ...)}$,

$\frac{\partial f(\vec{x})}{\partial x\_2}|\_{\vec{x} = (x\_1, x\_2, x\_3, x\_4, ...)}$, etc.

The partial derivatives are computed at particular values of the input. Look at the partial derivatives as the corresponding change of the output caused by a little variation of the input. The bigger the partial derivative, the bigger the effect. Note that the partial derivatives are calculated at a particular combination of the input. That is: at a particular screen brightness, at a particular battery level, at a particular temperature, you estimate the effect of changing the phone level by a little.

If you are lucky you will see that to some extent some variables are influential to the partial derivative: for example the partial derivative might not change with gps connectivity enabled or not (as probably will).

---
Tags: algorithms, machine-learning, data-mining, statistics
---


# Question
Title: Mathematics Courses for Computer Scientists
I am looking for standard math courses (Calculus 1, Calculus 2, Linear Algebra, etc.) that were developed specifically for computer scientists, and use computer-science examples for motivation. For example, the pagerank algorithm can be used to motivate eigenvectors and eigenvalues.

# Answer
The Matrix in Computer Science (Brown) http://cs.brown.edu/courses/cs053/current/lectures.htm

Coding the Matrix (Coursera) https://www.coursera.org/course/matrix

Both are by Philip Klein http://cs.brown.edu/~pnk/
> 3 votes

# Answer
David Forsyth in my department (UIUC) developed a course and notes on probability for CS majors. It ties the teaching of probability/stats to applications coming from data analysis. Also has matlab programming etc. See link below.

http://luthuli.cs.uiuc.edu/~daf/courses/Probcourse/Probcourse-2013/498-home.html

Mehran Sahami has a course on probability for CS majors. See info at the link below.

http://www.stanford.edu/class/cs109/index.html
> 1 votes

---
Tags: education, mathematical-analysis
---


# Question
Title: Algorithm to match timestamped events from two sources
does a good known algorithm exists for this problem?

On input I have two series of timestamps "when the event was observed". Theoretically the recorded timestamps should be very well aligned.

Visualized ideal situation on two time lines "s" and "r" as recorded from the two devices:

but more likely they will not be so nicely aligned and there might be missing events from timeline s or r:

I am looking for algorithm to match events from "s" and "r" like this:

So that the result will be something like: (s1,r1); (s2,r2); (s3,null); (s4,r3);(null,r4)... Or something similar. Maybe with some "confidence" rating.

It feels like there should be some well known algorithm for this problem, but I am a bit out of my element here.

Thanks.

# Answer
> 2 votes
Here is a pragmatic approach:

1. Look for matching pairs. Consider a pair $(s,r)$ (where $s$ is from the first device and $r$ from the second device) to be a match if their timestamps are very close, i.e., $|s-r| \le \epsilon$ for some small fixed value of $\epsilon$ that you choose in advance. $\epsilon$ is a tolerance. To find matching pairs, for each $s$, you look for a value $r$ in the range $\[s-\epsilon,s+\epsilon\]$.

You can quickly find all matching pairs by first sorting $s$ and $r$ individually, then doing a linear scan across them.
2. Count how many values don't have a match. Use the number of values that don't have a match to derive a confidence score. The more mismatches, the less confident you are.

There are a number of elaborations possible:

1. For instance, if you've found $n$ matching pairs $(s\_1,r\_1),\dots,(s\_n,r\_n)$, you can use $|s\_1-r\_1|+\dots+|s\_n-r\_n|$ as an additional confidence measure: the higher this is, the worse a match it is. You could compute a weighted sum of $|s\_1-r\_1|+\dots+|s\_n-r\_n|$ and the number of mismatched pairs.
2. If you frequently find that many points can be matched to multiple other possible points (one $s$ has multiple $r\_i$'s it could match to), you could try framing this as a bipartite graph matching problem. Basically, you have a vertex for each sample point, and an edge between $s$ and $r$ if $|s-r|\le \epsilon$; now find a maximum matching in this bipartite graph, and that will give you a way to find the maximum number of matched pairs. Then you can use the number of unmatched values as a confidence score. You can also use some kind of search over a range of $\epsilon$ values, if it's not clear how to choose $\epsilon$ a priori.

However, this is probably overkill and unnecessary, if events are well-aligned (if the typical distance between two events from a same device is much larger than the typical alignment error in the timestamp for an event at one device vs the timestamp at the other device). If events are well-aligned, simply choosing a suitable threshold $\epsilon$ and applying the simple approach at the top of my answer will probably suffice.
3. If you expect systematic clock skew, where one device's clock is a bit ahead of the other device's clock (by a constant), you could correct for this in a number of ways:

* One simple pragmatic way is to look for a set of matching pairs $(s\_1,r\_1),\dots,(s\_n,r\_n)$ in a first pass (this first pass doesn't have to be perfect, so you could use a larger value of $\epsilon$). Then, use the median of $s\_1-r\_1, \dots, s\_n-r\_n$ as your estimate of the clock skew; say the median is $\Delta$. Now replace each $s\_i$ with $s'\_i=s\_i-\Delta$. Finally, do a second pass where you match the (corrected) $s'\_i$'s to the $r\_j$'s, maybe with a smaller value of $\epsilon$. In practice this might work very well.
    * Alternatively, you could use RANSAC to fit a line $s=r+c$ to the data, where the constant $c$ is unknown. Normally RANSAC is described as a way to fit a line $y=ax+c$ (in this setting, $s=ar+c$), but in your application, we can fix $a=1$ (assuming both clocks run at the same rate and we care only about clock skew) and then apply RANSAC methods to find the best fit line, i.e., to find the constant $c$ that provides the best fit.

# Answer
> 0 votes
Your drawing looks like you'll be traversing parallel arrays.

You come to s1, c.compare(s1,r1) and have your comparator (c) check against some tolerance value (you'll have to define the compare and tolerance obviously). If they are within the tolerance store them both in some key/value pairing object (which can then be added to something like an ArrayList for later review), and move onto the next elements. Make this K/V object in such a manner that one value can be null.

http://docs.oracle.com/javase/7/docs/api/java/util/Comparator.html

Your comparator can return any value you want to check against

```
return (Math.abs(s1 - r1) > TOLERANCE);

```

---
Tags: algorithms, matching
---


title: Random algorithm termination

text:
# Question
Title: Random algorithm termination
Suppose I have an algorithm that works as follows when invoked: it calls itself recursively with probability $0 \< p \< 1$ and terminates with probability $1-p$. Does this algorithm terminate? On the one hand you can show that $\lim\_{n \to \infty}p^n = 0$, so it must terminate at some point before infinity. On the other hand it also seems reasonable to say that it is possible for the algorithm to call itself repeatedly indefinitely. What is the correct interpretation?

# Answer
> 7 votes
The question "Does it terminate?" isn't well-formed. You need to define more precisely what you mean by that question before it can be answered.

* Is it guaranteed to terminate on all possible execution traces? No. There exists an execution trace where it never terminates.
* Does it terminate with probability one? Yes. If you flip a coin until you first get heads, the probability of getting a never-ending sequences of tails is zero.
* Is the expected number of repetitions until termination finite? Yes. If you flip a coin until you first get heads, the expected number of flips is finite (it is the expected value of a geometric distribution).

So, the answer to the question depends upon precisely which of those questions you meant to ask. Normally, that's about all we can say.

Usually, if it matters, we try to define what we mean by "terminate" more precisely. For instance, in the definition of the Halting Problem, "terminates" is specified to mean "guaranteed to terminate on all possible inputs and all possible execution traces", and the formalization of the Halting Problem implicitly restricts us to deterministic algorithms (more precisely, to Turing machines, which are necessarily deterministic; they don't have access to randomness). Anyway, in general, if the differences matter, it's your job to specify exactly which meaning you have in mind.

---
Tags: algorithms, terminology, randomized-algorithms
---


# Question
Title: Can heuristic methods and machine learning approaches be considered alternate methods to solve NP-Complete problems?
I was watching the videos from Skiena's Computational Biology Lectures, which is also available at youtube. In those videos, the professor made a statement that, most of the problems posed to computer scientists by biologists were proved to be NP-Complete. My questions are the following ones: ( Please forgive me, if I make blunders here in asking questions. I am not from CS background.)

1. **Do NP-Completeness imply no algorithm exist for that particular problem?**
2. The professor was talking about heuristic approaches where normal approaches fails. **Do there exist 'heuristic' approaches in computer science to solve problems?** If so , Can some one give examples. (I have heard of heuristic approaches in analog circuit design in electronics. But I am not sure. Music composition is heuristic , right?)
3. **Is Machine learning a solution to solve some computational problems, where traditional algorithmic solutions doesn't exist?**

# Answer
I haven't seen these lectures, but here's what I think about he questions you pose.

1. No. NP-completeness is unrelated to the existence of algorithms. For example, we have plenty of problems that we can prove only have an exponential solution. We typically talk about "is there a solution" as *decidability*. There are problems that have no solution and we call these *undecidable*. The Halting Problem is a popular example.
2. Absolutely. When we can't find an efficient solution for all inputs, we find something that works for "most cases". In some cases, we can can prove the solution generated is not worse than K times the true optimal solution. In other cases, we cannot.
3. Yes. Machine learning works well for certain classes of problems, but is really hard to apply to others. It's not a "silver bullet" or alternate solution to computational complexity.

Regards.
> 2 votes

---
Tags: machine-learning, heuristics
---


title: Order of steps in Kosaraju-Sharir

text:
# Question
Title: Order of steps in Kosaraju-Sharir
The Wikipedia summary of the Kosaraju-Sharir algorithm is as follows:

> Let G be a directed graph and S be an empty stack.
>
> * While S does not contain all vertices.
>     + Choose an arbitrary vertex v not in S.
>     + Perform a depth-first search starting at v. Each time that depth-first search finishes expanding a vertex u, push u onto S.
> * Reverse the directions of all arcs to obtain the transpose graph.
> * While S is nonempty:
>     + Pop the top vertex v from S.
>     + Perform a depth-first search starting at v in the transpose graph.
>     + The set of visited vertices will give the strongly connected component containing v; record this and remove all these vertices from the graph G and the stack S. Equivalently, breadth-first search (BFS) can be used instead of depth-first search.

But in my textbook - Sedgewick's Algorithms (fourth edition) \- it describes the steps of the algorithm as follows:

> * Given a digraph G, compute the reverse post-order of its reverse digraph. GR
> * Run a standard DFS on G, but consider the unmarked vertices in the order just computed instead of the standard numerial order
> * The set of all vertices...

The conclusion drawn in the third step is identical, as are the operations performed in the first two steps, but it seems that those two steps are given in opposite orders: Wikipedia tells me to start by doing a DFS on G and *then* transposing it, doing the second DFS on GR, whereas my textbook suggests that I begin by transposing G, do the first DFS on GR and the second on G.

**My primary question** is: Am I understanding this correctly, or am I misinterpreting what one or the other is saying?

**Secondly:** Intuitively, it seems as though these operations are transitive and therefore that these two "different methods" are in fact equivalent, and will always yield the same final result. I've tested this intuition on a couple of digraphs and it seems to hold true - but is it?

**Thirdly:** Assuming it is, is there any objective reason to prefer one over the other, or is it simply a matter of preference?

> **NOTE:** As of now, this question is cross-posted on StackOverflow. I'm an established user there, so I know that cross-posting is generally frowned upon, but I've just joined this SE and am curious to gauge the response I get here relative to what I get there. I will delete one or the other after doing so. If you'd like me to do so immediately, please comment.

# Answer
> 2 votes
1. Yes, you are understanding this correctly.
2. The set of SCCs of a graph is uniquely determined. So if the algorithms were returning different sets, this would imply that one of them is incorrect. For the Wikipedia version a correctness proof is linked at the bottom of the article. If Sedgewick also gives a correctness proof of his algorithm, these two proofs together imply the property.
3. Reversing a graph twice will give you the original graph. Thus, if one algorithm performs especially well/bad on a certain graph, the other one will show that performance on the reversal of the graph in question. So neither algorithm will perform better in the general case.

The comment on SO that the WP version does use $O(n)$ extra space for the stack is not entirely correct: Sedgewick also has to store the order of traversal in some way, which wll also take $O(n)$ space (though possibly with a smaller hidden constant). Additionally, you can replace the stack with a different way of storing the order in the WP algorithm as well.

---
Tags: algorithms, graphs, data-structures
---