# Question
Title: Which languages are recognized by one-counter machines?
**Counter machines** with two or more counters are typically shown to be equivalent to Turing machines in courses on the theory of computation. However, I have not seen a formal analysis of which languages can be recognized by a one-counter machine. Are these languages equivalent to the context-free languages (perhaps by some clever construction relating them to PDAs), or are they an entirely different class of languages?

# Answer
> 11 votes
A one counter automata is a push down automata with only one symbol allowed on the stack (plus a fixed bottom symbol). Languages recognized by one counter automata form a proper subset of the context free languages.

For example a 1-counter automata can recognize the language $\\{a^nb^n\\}$ which is not regular, but cannot recognize the language $\\{a^nb^ma^mb^n\\}$ which is context free and can be recognized by a 2-counter automata, too.

If k-DCA is a *deterministic* k-counter automata, and k-NCA is a *nondeterministic* k-counter automata, then we have the following proper inclusions:

DFA (regular languages) $\subset$ 1-DCA $\subset$ 2-DCA

1-DCA $\subset$ 1-NCA

If we don't allow $\epsilon$ transitions (switch to *real time*) then k-DCA $\subset$ k'-DCA for k \< k'.

Just for completion: there are languages that are context free but cannot be recgnized by counter automatas (k-DCA with k $\geq$ 2) (for example $\\{ww^R\\}$), and languages recognized by counter automatas that are not context free (for example $\\{a^nb^nc^n\\}$). A counter automata (in particular a two counter automata) can be Turing complete only if its input and output are properly encoded (see Wikipedia entry for details).

# Answer
> 7 votes
Counter automata were much studied in the ancient formal language past, in the context of AFA and AFL theory (abstract families of automata & languages) by US and French teams (Ginsberg, Greibach, ... , Nivat, Berstel, ...)

Counter automata are typically defined as finite state automata equipped with external memory, consisting of a natural number (or several if you have more than one counter). This number can be incremented, decremented, and (usually) tested for zero. A computation starts with zero and is only accepted when the counter is zero at the end, comparable to the pushdown empty stack acceptance.

If such a machine has at least two such counters then it is equivalent to a Turing machine, even in the deterministic case. The proof of this fact is by Minsky and can be found in the wikipedia article you linked. The model is of course related to the register machine mentioned in the same wikipedia page. The coding-problems mentioned in the wikipedia article are not important in this setting here as we consider automata with an input tape (after all we have to read an input string) whereas wikipedia on this page only assume counters.

This counter automaton can be seen as a special type of pda, having only one stack symbol, *and* a bottom-of-stack (that is never moved). This enables the automaton to test whether the counter/stack is zero, and act accordingly.

There are in fact *three types* of counter automata. So combine results wisely or you end up with contradictions (as happened me in the past). All three types are (strictly) included in the context-free languages for one-counter.

The type above stores an integer (or a natural number, that doesn't matter) and can test its contents beiing zero. *Blind* counter automata store an integer but cannot test for zero. They can expicitly count below zero though. *Partially blind* counter automata cannot test for zero, but store an natural number. If the machine tries to go below zero it halts without accepting. This is a natural storage type to model Petri nets. It also is ralated to the PDA, now with a single stack symbol without the special bottom marker (and hence the problem of testing for zero: we just get stuck when popping the last stack element). Sometimes the names of the families defined by the respactive counter models are OCL, ROCL and 1-BLIND.

All these families have been studied, they all are (but I am rusty in my AFA/AFL theory) principal full trios (=rational cones) which means they are closed under (inverse) morphisms and intersection with regular languages, and can be obtained using these operations starting with a single language. For the largest family OCL (with zero test) you can start with the language $(Dc)^\*$ where $D = \\{ w\in \\{a,b\\}^\* \mid \\#\_a(w) = \\#\_b(w) \\}$ is the "two sided Dyck language on on pair of brackets" (in terminology fitting the subject). There is important intuition related to this language. Symbols $a$ and $b$ reflect popping and pushing, $c$ is the zero test.

As an example of relevant research, Latteux etal have a nontrivial paper "The Family of One-Counter Languages is Closed Under Quotient" (which is actually about ROCL).

---
Tags: computability, automata
---


title: What are handles in parsing?

text:
# Question
Title: What are handles in parsing?
I have read a few algorithms for $LR(k)$ parser, in which there is a frequent mention of selecting a handle from the grammar given. For example, one document said - *"the essence of LR parsing is identifying the handle on top of stack"*

Please help me understand, what are handles in parsing?

# Answer
> 6 votes
Let's consider the following grammar:

> 1: $S \to A b$
> 2: $S \to B b$
> 3: $A \to a a$
> 4: $B \to a a a$

Obviously, this language is totally uninteresting: the only words in it are $aab$ and $aaab$. However, the grammar is not $LL(1)$ or $LL(2)$ (not sure if you know what that is, if you don't, then that's not a problem).

Let's try parsing the input $aaab$ by going through it one character at a time, while pretending we know absolutely nothing about the rest of the string, except the next token (essentially, we use 1 token of lookahead). We are allowed to use our knowledge of everything we've seen so far though.

Initially, we only know that the string starts with an $a$. This tells us absolutely nothing about whether we are in 'case 1' (production 1) or 'case 2' (production 2) of our grammar. Luckily, we don't really care at this point.

Let's skip over the $a$ and go to the next point. We remember the $a$ and look at the next token. This is another $a$. Note that by now, we've seen $aa$, which means that we might be in case 1: it might be the case that these first two $a$s constitute an instance of $A$! We'll just leave it at this for the moment, and first 'read' the $a$ officially.

We now look at our third token and find it is again an $a$. We now want to decide whether those two $a$s we saw earlier really constitute an $A$ ($LR(k)$ algorithms never delay this decision). As an $A$ is always followed by a $b$, we decide this is not the case: our next token is an $a$.

Reading the $a$, we know we're definitely in case 1 (assuming our input is correct). Our lookahead becomes a $b$, which is precisely what we expect. We therefore decide that the three $a$s we've seen so far are in fact a $B$. Note that at this point, we no longer need to 'remember' that we've seen three $a$s: all we need to know is that we've seen a $B$. This is effectively the same situation we'd be in if we would have had $Bb$ as input, and we'd have read $B$, and as this makes everything easier to remember, we'll do precisely that (this corresponds to a reduce action of an $LR(k)$ parser).

Finishing up, we read the $b$, find that we are at the end of the input, decide that the left part must be an $S$ and decide that the input was correct.

The $LR(k)$ algorithm works pretty much as described above. It remembers what it has seen so far and decides based on this information and the next token whether the last bit of what it has seen so far is 'actually' a nonterminal. It then replaces this by the nonterminal, shuffles some information around and continues as if the replacement had taken place in the input.

The crucial bit is finding out when what we've seen so far, or to be more precise the last bit of what we've seen so far, is actually an instance of a nonterminal, so an expansion of a production. In our example, if we had transformed the two $a$s at the start into an $A$, then everything would have went wrong. We say that $aa$ is not a handle at this point. However, $aaa$ was a handle, as we correctly replaced it by a $B$. A grammar is $LR(k)$ if we can always make correct decisions about what is a handle using $k$ tokens of lookahead and everything we've seen so far.

---
Tags: compilers, parsers
---


# Question
Title: Prove that $\text{EXACT-TRIPLE}$ is not in NP
I received the following assignment:

$\text{EXACT-TRIPLE} = \\{ \phi \mid \phi \text{ is a boolean formula that has exactly 3 satisfying assignments} \\}$.

I need to decide whether this problem belongs to NP or not. I assume it does not. How do I prove that?

# Answer
The problem is coNP-hard, and so not likely to be in NP. Indeed, given a formula $\phi$, you can construct a formula $\phi'$ such that if $\phi$ has $x$ satisfying assignments then $\phi'$ has $x+3$. This gives a reduction from the coNP-complete problem UN-SAT to EXACT-TRIPLE.
> 9 votes

---
Tags: complexity-theory, np-complete, satisfiability, np
---


# Question
Title: Algorithm for getting the outer boundary of a large graph
I am trying to create an isochrone based on the OpenStreetMap data set. Everything works fine, I extracted data, processed it into a DAG, ran a Dijkstra algorithm over it. The result is a subset of the complete graph. This is an impression of the covered parts of the subset displayed over Google Maps:

However, when the area gets larger, the number of reached vertices gets very large and displaying like this gets slow. What I would like to do is convert the set of edges and vertices into a polygon. Basically, this should be posible by removing all of the inner edges, leaving just the edges around the boundary of the area and the edges pointing out from it. I know coordinates for all vertices and approximating each edge as a line would be fine. Larger inner areas should become holes inside the polygon.

My first attempt was to use an geospatial library (in my case the SqlServer spatial extensions), create a multiline from all of the edges and doing an ST\_Buffer on it. Turns out to be very slow and memory consuming for large numbers of edges (\> 1000)

I was thinking along the lines of finding small polygons in the set (turning left at every turn?) and removing every edge that is part of 2 of these polygons.

Extra image to use in comment below:

# Answer
I think you can do this with marching squares, which is both fast and easy to implement.

To use marching squares you need to construct a scalar grid over your domain. Impose a regular grid over your region of interest. For each point in the grid, compute the distance (or time, etc.) between the grid point and your point of interest using a shortest path algorithm. Store this value at that point to serve as the scalar values of your grid. Then apply the marching squares algorithm to generate an isocontour for some isovalue $d$; all points on this contour will be distance $d$ away from your point of interest. More on the details of this algorithm on Wikipedia.

Additionally you can speed up the shortest path computation since your graph is a DAG. First topologically sort your DAG and then relax each edge, like you would in Bellman-Ford, in the order given by the sorting. The correctness follows from relaxing each edge along every path from the source node to every other node. Thus the single source shortest path can be computed for a DAG in $O(V+E)$.
> 5 votes

# Answer
For each vertex $i$, note its $(x\_i,y\_i)$ location and the distance $d\_i$ from the source. Building the Voronoi diagram or the Delaunay triangulation of the pointset can be useful (this would not use $d\_i$ data).

If you want something simpler and self-contained, then for each point find its closest neighbors (this info can also be read from the Delaunay triangulation) and compare their $d\_i$ values. In particular, if the current point $i$ has no neighbors $j$ with $d\_j\>d\_i$, then $i$ is on the boundary. Otherwise, consider each closest neighbor $j$ with $d\_j \> d\_i$ and make decisions based on the straight-line (or street) distance $d\_{ij}$. For example, $i$ would still be on the boundary if for all neighbors $j$ you find $d\_i + d\_{ij} \> d\_j$.

Depending on the exact desired output, you may want to add some additional neighboring vertices to the boundary identified by the above condition.
> 4 votes

# Answer
I would suggest the following. The data you extracted from OSM is not enough. A DAG only represents the combinatorial data, but not the topological data. What you should do is to sort for every vertex of the DAG the emanating edges in cyclic order, say ccw. Also I would forget about the directions of the edges. With this information you can start at any boundary edge and then you simply walk along the outer face until you reach your starting position.

Since your graph is planar, the sorting takes just $O(n \log n)$.

It also seems that yo have vertices of degree 1 on the boundary. You should get rid of them, for example by doubling the incident edges.
> 3 votes

---
Tags: algorithms, computational-geometry, graph-traversal
---


title: Shortest paths graph

text:
# Question
Title: Shortest paths graph
Given a directed graph $G$, edge weights for each edge, source vertex $s$ and $d\[v\]$ for each vertex in the graph (the distance from $s$ to $v$), I need to find an algorithm that builds the shortest paths graph.

I was thinking of going on edges by BFS, but then how can I know which edge should be in the tree and how to check that the $d\[v\]$ for each vertex is true?

# Answer
> 2 votes
Thre are multiple algorithms already developed like Dijkstra's algorithm, Bellman-Ford algorithm or A\* search algorithm.

The problem you face is also well described on Wikipedia.

Maybe there is something specific about your assignment like memory or time complexity?

# Answer
> 2 votes
As has been pointed out, there are well known shortest path algorithms. But your problem already has most of the information. Specifically, you already know the shortest path distances $d\[v\]$ from $s$ for each node $v$. In such a case, you can use a much better algorithm.

By a "shortest paths graph", I think you mean a collection of shortest paths from $s$ to every other vertex $v$. In such a case, you can use a Depth First Search (DFS) as follows:

* Start the DFS from the source vertex $s$.
* Mark a node visited as soon as you reach it for the first time.
* For every node $u$ visited, do a DFS on all children $v$ of $u$ only if $d\[v\] = d\[u\] + w(u, v)$, where $w(u, v)$ is the weight of the edge from $u$ to $v$.
* If a child $v$ of $u$, which obeys the previous condition of distances, has already been visited, it simply means that there are multiple shortest paths from $s$ to $v$, and that you have already selected some other such path which does not go through $u$. In such a case, do *not* include this edge $(u, v)$ in your shortest paths tree/graph. This is because by doing a DFS, you have already selected *all* shortest paths that go through $v$.

Note that this algorithm relies on the following property of a shortest path algorithm: edge $(u, v)$ is on some shortest path to $v$ from $s$ if and only if $d\[v\] = d\[u\] + w(u, v)$. Therefore, only the shortest paths are taken by the algorithm. Since we ignore a shortest path from $s$ to $v$ through $u$ if and only if $v$ has already been visited, we ensure that all shortest paths are included.

Note that this algorithm is linear in the size of the graph. I mention DFS, since it is much easier to program for such a scenario, and recursion holds the stack implicitly.

However, you can use BFS too for this purpose. Use the same property in the BFS as above, that is:

* Enqueue (and mark visited) only those neighbors $v$ of $u$ which obey the following property: $d\[v\] = d\[u\] + w(e, v)$.

Note that if there are multiple shortest paths to some vertex $v$ from $s$, using a DFS or a BFS may give different shortest path trees (though both will be correct). DFS will give a random tree, whereas BFS will give a tree where the shortest path selected would be such that it will also have the minimum number of edges among all shortest paths from $s$ to $v$. Unless you desire such a property, I think a DFS would be much simpler. See this Udacity nugget for more information about how to compare these algorithms and a more in depth explanation.

# Answer
> 0 votes
The best algorithm depends on whether $d\[v\]$ is reliable or not. If it is reliable then you can find the shortest paths graph like this:

```
for each edge e in G:
    if weight[e] + d[origin of e] == d[end of e]:
        include e in the output graph

```

If $d\[v\]$ is not reliable then Dijkstra's algorithm and the Bellman-Ford algorithm are best, and will also produce the correct values of $d\[v\]$ as a side effect.

**EDIT**

The graph produced by the above algorithm is not guaranteed to be a tree because of the possibility of equal cost paths. If you need it to be a tree, then you will need to use Edmonds's algorithm.

---
Tags: algorithms
---


title: Label Assignment Problem

text:
# Question
Title: Label Assignment Problem
I try to solve an exercise in **Distributed Algorithm** described as follow.

Let's define a *label assignment problem* as follow. There is a anonymous network (vertices don't have unique ID's , nodes don't have any clue about $n$ - number of vertices nor about network topology ). The labels assigned to vertices must be distinct and there is no limitation on the length of the label. *The initiator is given.* Show the algorithm for solving the problem in asynchronous model with time complexity $\text{O}(D)$ and using $\text{O}(m)$ messages (where $D$ is the diameter of graph and $m$ number of edges), prove that the labels are indeed distinct. Show the changes in complexities if the algorithm is executed on the synchronous network.

Let's say that the initiator is the node A, wlog assign it $A\_{id} = 1$, broadcast $A\_{id} = 1$ to all children of $A$ by flooding algorithm, any node $B$ by receiving message from it's parent for the first time will assign $B\_{id} = PARENT\_{id}+1$ and send $B\_{id}$ to it's children, if $B\_{id}$ is already defined, drop the message. $T=\text{O}(D)$ - time complexity, $M=\text{O}(m)$ - message complexity for broadcast.

It seems like on synchronous network the complexities will be the same, just becasue **broadcast** and **convergecast** on synchronous and asynchronous network run in $T=\text{O(D)}$ and $M=\text{O}(m)$.

If there are any change in complexities on the synchronous network? Does the above algorithm look good?

# Answer
I dont know the solution of your problem: especially as we dont have a limit on the ID's. My "guessing" is that you cannot solve this problem with complexities you listed.

I will only answer your following question:

Does the usage of randomized leader election is eligible in the case of graph as described above?

I dont suggest using leader election. Its lower bound does not meet your requirement (it is still an open problem to solve the election problem with $O(D)$ time and $O(m + n \log n)$ message, Peleg 199\*). The known randomized election algorithms so far do not work on arbitrary graphs. There is a new algorithm that runs in arbitrary graphs (but requires knowledge of $n$). This algorithm is not yet officially published (due to Peleg et al. 2012).

I will list the references later.
> 1 votes

---
Tags: algorithms, time-complexity, distributed-systems
---


# Question
Title: What can be said about Θ-classes in m and n if we know that m < n?
A function in $\Theta(m + n^2)$ and $0 \< m \< n^2$, is in $\Theta(n^2)$. Does a function in $\Theta(m\log n)$ and $0 \< m \< n^2$, imply that it is $\Theta(n^2\log n)$?

# Answer
If $m=\Theta(n^2)$, then indeed $\Theta(m\log n)=\Theta(n^2\log n)$.

However, you are only given that $0\<m\<n^2$, that is, $m=O(n^2)$ and you can only infer that the algorithm has complexity $O(n^2 \log n)$, but not $\Theta$ of the same quantity. For instance, assume $m$ is a constant, or assume $m=\sqrt{n}$, and you could see why it cannot be $\Theta(n^2\log n)$.
> 6 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: Does Quicksort always have quadratic runtime if you choose a maximum element as pivot?
If you have a quick-sort algorithm, and you always select the smallest (or largest) element as your pivot; am I right in assuming that if you provide an already sorted data set, you will always get worst-case performance regardless of whether your 'already sorted' list is in ascending or descending order?

My thinking is that, if you always choose the smallest element for your pivot, then whether your 'already-sorted' input is sorted by ascending or descending doesn't matter because the subset chosen to be sorted relative to your pivot will always be the same size?

# Answer
> 16 votes
The worst case complexity for quicksort is $\Theta(n^2)$. This is achieved by picking pivots that divide the set such that one group has only a single member. With a bad pivot picking algorithm, this can easily be achieved by picking one end of a sorted set. Your assumption is correct.

# Answer
> 5 votes
Yes! You're thinking is absolutely right! And as correctly mentioned by Yuval Filmus, the running time will be $\Theta(n^2)$

# Answer
> 3 votes
One subarray will have $0$ or $1$ element while the other will have $(n-1)$ elements; hence it is $O(n^2)$: $$t(n)=t(n-1)+t(0)+O(n)= O(n^2)$$

---
Tags: algorithms, time-complexity, algorithm-analysis, runtime-analysis, sorting
---


# Question
Title: alphabet of a single tape turing machine that simulates a multitape TM
First of all sorry, if this question already exists, in that case, pointing to the right direction will be appreciated.

Secondly, sorry, if the question is below the expected level of Niveau, but all help appreciated.

In the textbook by J. Hromkovic, named "Theoretical Computer Science, Introduction to Automata, Computability, Complexity, Algorithmics", in Page 110, in the 2003 edition, i note that the alphabet of a single tape TM which simulates a multitape TM is given by

$$ \Gamma\_{single\ tape} = (\Sigma\_{multi\ tape} \cup \\{¢,␣ , $ \\})\times \\{\uparrow , ␣ \\} \times (\Gamma\_{multi\ tape}\cup\\{ ␣,\uparrow\\})^{k} \cup \Sigma\_{multi\ tape} \cup \\{¢\\} $$

should that not be, instead:

$$ (\Gamma\_{multi\ tape} \cup \\{¢,␣ , $ \\})\times \\{\uparrow , ␣ \\} \times (\Gamma\_{multi\ tape}\cup\\{ ␣,\uparrow\\})^{k} \cup \\{¢\\} ? $$

according to the book, the single tape TM splits its tape in "tracks" , see image i scanned from the book: https://i.stack.imgur.com/rG9kk.jpg

because, the last $¢$ is the primary left end marker, the first two terms of the Cartesian product series is responsible for the top two track, the rest $k$ tracks are constructed by the term which has k in exponent.

all help is appreciated. sorry for the dummy question. i am a meteorologist, who takes his past time in computer programming.

ps, i can neither embed (is that the correct term?) the ¢ character by \cent nor the ␣ by \textvisiblespace in a post like this. does stackexchange use a different command for those? thank you

# Answer
(I successfully downloaded the image).

It is not clear in the picture what is the difference between $\Sigma$ and $\Sigma\_A$, however looking at the definition of Exercise 4.12 I think that the author simply distinguishes the input alphabet $\Sigma\_A$ from the working alphabet $\Gamma\_A$ (*tape alphabet*); so in order to simulate:

the input tape of A (with symbols from $\Sigma\_A$) plus the $k$ tapes of A (with symbols from $\Gamma\_A$)

it uses $\Sigma\_A$ in the first term of the Cartesian product.

Be careful that you didn't copy exactly the $\Gamma\_B$ of the book (you wrongly put a $\cup$ where the book puts a $\times$):

$\Gamma\_{B} = (\Sigma\_{A} \cup \\{¢,␣ , \\$ \\})\times \\{\uparrow, ␣ \\} \times (\Gamma\_{A}\times \\{\uparrow, ␣\\})^{k} \cup \Sigma\_{A} \cup \\{¢\\}$

The final $\Sigma\_A$ is probably used to represent the initial input of the multitape machine A "as-is" (and satisfies the requirement that the input alphabet must be a subset of the working alphabet); but I think it is a little bit confusing (and perhaps the $ symbol should also be included with the final ¢)

The first steps of the simulation of B should be: copy the input to the "hypotethetical" track 0 of B, initializing the head pointers of the "hypothetical" tracks 1,..,k of B.
> 1 votes

---
Tags: turing-machines
---


title: Derive some strings

text:
# Question
Title: Derive some strings
G=({S,A,B},{0,1},P,S)

Where P:

* S→A1B
* A→0A|ε
* B→0B|1B|ε

I have to list the first 25 strings from L(G). So far I've made the tree, but I'm not sure that it's correct.

# Answer
> 1 votes
"the first 25 strings" in what order? Let's assume lexicographic order. Then, go by length of the produced strings.

Length 0: only $\varepsilon$ is of length $0$. Can $\varepsilon$ be generated by the grammar? (No).

Length 1: what strings of length 1 can be generated by $G$? only the string "1" (why?)

now, proceed to length 2,3,4... until you get 25 strings. But, doing this, can you see any rules here? Can you define the language generated by $G$ and then easily infer what are then strings (of length $n$) that $G$ generates?

HINT:

> The regular expression is $0^\*1(0+1)^\*$.

Finally, for each string construct a derivation tree, like you did. It seems that the grammar is un-ambiguous, so there's only one tree anyways. The way to write it as left-side derivation is listing the sentinel phrase and replace the leftmost variable with the right-had-side of its production. For the tree you give, an equivalent derivation is: $$S\to \mathbf{A1B} \to \mathbf{0A}1B \to 0\mathbf{\varepsilon} 1B \to 01\mathbf{0B} \to 010\mathbf{1B} \to 0101\mathbf{\varepsilon} = 0101 $$

---
Tags: context-free
---


# Question
Title: k-armed bandit - index policies vs. Q-learning
I am interested in the stateless k-armed bandit problem, where an agent repeatedly chooses one of k independent arms, each with a different distribution of rewards, and tries to maximize its total reward.

I read many papers about this subject, but I am still confused, as there are two types of solutions:

A. It has been proven that the optimal solution to this problem is an index policy: For each arm, calculate a quality index, based on the rewards received from that arm so far. The index roughly estimates an upper confidence bound on the expected reward from that arm. Now choose the arm with the highest index.

B. On the other hand, this problem can also be presented as a Markov decision process, which can be solved by Q-learning. The general formula for Q-learning is:

$Q\_{t+1}(s,a) := (1-z\_t) Q\_t(s,a) + z\_t (R\_t + g * max\_{a'}(Q\_t(s',a'))$

Where: t is the time, s is the state we were at, a is the action we did, s' is the state we got into, $z\_t$ is the rate of learning at time t, R\_t is the reward we received at time t, and g is a constant discount rate.

In this case, there is only a single non-terminal state. Each arm-pull is an episode: it starts with the initial state, and always goes to the final state. Therefore, the Q value of the final state is always 0, and we only need to calculate Q values for actions of the single initial state:

$Q\_{t+1}(a) := (1-z\_t) Q\_t(a) + z\_t R\_t$

It is guaranteed that the process will converge to an optimal policy, if each action is selected eventually, and if the learning rate $z\_t$ decreases in an appropriate rate (speficically, $\sum\_{t=1}^\infty z\_t^2 \< \infty$ and $\sum\_{t=1}^\infty z\_t = \infty$).

Now, my question is: what is the relation between two methods for solving the k-armed bandit problem?

1. Is it possible to prove, that the Q values converge to one of the indices given in the literature?
2. Why use an index method, if it is possible to use the much simpler Q-learning method?

# Answer
The difference between your formula and the index methods is that your formula gives more weight to recent data. If there's a lever that has large but infrequent rewards then your formula won't converge.

On the other hand, your formula will perform better than index methods if the reward distribution for some of the levers changes across time.

The next state is actually not the terminal state unless there are no more trials, so simplifying out $g * max\_{a'}Q\_{t}(s',a')$ is only valid if $g = 0$. But in this case $g = 0$ should work quite well.
> 1 votes

---
Tags: machine-learning
---


# Question
Title: Maximizing a convex function with a linear constraint
$$\text{maximize } f(\mathbf{x}) \quad\text{subject to } \mathbf{Ax} = \mathbf{b}$$

where

$$f(\mathbf{x}) = \sum\_{i=1}^N\sqrt{1+\frac{x\_i^4}{\left(\sum\_{i=1}^{N}x\_i^2\right)^2}},$$

$\mathbf{x} = \[x\_1,x\_2,...,x\_N\]^T \in \mathbb{R}^{N\times 1}$ and $\mathbf{A} \in \mathbb{R}^{M\times N}$.

We can see that $f$ is convex and of the form $\sqrt{1+y^2}$. It can be also shown that $f$ is bounded in $\[\sqrt{2}, 2\]$. I know that a convex maximization problem is NP-hard, in general.

However, using the specific nature of the problem, is it possible to solve it using any standard convex optimization software/package?

# Answer
Yes, Convex Optimization with equality constraint is NP-Hard in general. However, there exist mature techniques that find very nice approximate solutions to convex optimization problems, like Coordinate Descent.

Suppose you use coordinate descent and the matrix A has rank $k$. You can fix n-k-1 coordinates of your feasible solution $x = (x\_1, x\_2, x\_3, ..., x\_n)$ and then the solution vectors in the solution space are uniquely determined by one coordinate, for example $x\_i$. In that case, you can just take the derivative of $f(\cdot)$ with respect to $x\_i$ to find the maximum in this iteration.

Then we iteratively fix n-k-1 coordinate and improve the solution until a approximately optimal one is found.
> 5 votes

---
Tags: optimization
---


title: LU decomposition with pivoting

text:
# Question
Title: LU decomposition with pivoting
I have to solve system of linear algebraic equations $AX=B$, where $A$ is a two-dimensional matrix with all elements of main diagonal equal to zero.

How to solve this problem? Iterational methods are not applied in this case.

One way is LU Decomposition method with reordering rows of $A$ to get entries in the main diagonal that are not zero, using permutation matrix. How can we quickly reorder the rows of the matrix or find the permutation matrix?

Note that the matrix dimensions are large and I have to write a program to solve SLAE in C# language, so I do not need any Matlab or Mathematica functions. Thanks!

# Answer
This is a bipartite matching problem, which has several known algorithms. As a bonus, you get a combinatorial criterion for when it is even possible (namely, Hall's theorem).

Construct a bipartite graph with $n$ vertices on each side $x\_i,y\_j$. Connect $x\_i$ to $y\_j$ if $A\_{ij} \neq 0$. A maximum matching in this graph, if it involves all the vertices, gives you a permutation $\pi$ such that $A\_{i\pi(i)} \neq 0$ for all $i$.
> 4 votes

---
Tags: matrices, linear-algebra
---


# Question
Title: Data structures and algorithms for bridge game play?
In a bridge game, a deck of 52 cards (13 spades , 13 clubs, 13 diamonds, 13 spades) are dealt to 4 players (13 cards each) then game starts.Game session ends after 13 tricks each having 4 cards.There are 28561 possible non repeated 4 card groups.

What is the best method of generating and storing all possible trick combinations (played according to the bridge rules just for one session) to be further processed by a computer program (i.e., data structures such as game trees, and any open source algorithms written for any computer language if any).

All resources to read to get the theory behind or any references are welcome. Thank you.

# Answer
If the data is really a tree graph, then maybe a Prüfer code?
> -1 votes

---
Tags: algorithms, data-structures, combinatorics, board-games
---


title: Computing the clustering coefficient

text:
# Question
Title: Computing the clustering coefficient
I saw in this video that computing clustering coefficient of central node of a star graph using the following algorithm is $\Theta(n^2)$ and for a clique it is $\Theta(n^3)$. is that correct?

```
def clustering_coefficient(G,v):
    neighbors = G[v].keys()
    if len(neighbors) == 1: return 0.0
    links = 0.0
    for w in neighbors:
        for u in neighbors:
            if u in G[w]: links += 0.5
    return 2.0*links/(len(neighbors)*(len(neighbors)-1))

```

# Answer
**Edit:** My answer was based on assuming the code given as a pseudo-code, rather than a concrete Python example. For Python, the data structure is a dictionary (hash map) and so finding neighbors (the `in`) operation will in fact be $O(1)$ on average, giving $\Theta(n^2)$ overall complexity on *average* for both graphs. Rare worst cases in hash maps can depend on implementation. In general for pseudo-codes, see my original answer below.

The complexity also depends on the data structure being used for storing the graph $G$. If an adjacency list is used, where for every vertex $v$ in the graph, its neighbors are stored in an array/linked list, then the above complexities are valid. Here's how:

For the central node of the star graph, there are $n-1$ neighboring vertices. Then, the pair of neighbors of this central node - the $w$ and $u$ vertices - can be selected in $\Theta(n^2)$ ways. For each such $w$, checking if $u$ is a neighbor of $w$ can be done in $\Theta(1)$ time, since each such $w$ only has $1$ neighbor - the central node $v$. This gives overall complexity of $\Theta(n^2)$.

For a clique of size $n$, every node has $\Theta(n)$ neighbors. Then, the pair of neighbors $w$ and $u$ for any node $v$ can be chosen in $\Theta(n^2)$ ways - this is the complexity of the two outer `for` loops. For every such $w$, checking if $u$ is its neighbor requires going through the list of $\Theta(n)$ neighbors of $w$, and so the `if` statement has $\Theta(n)$ complexity. This takes the overall complexity of the two nested `for` loops and the `if` loop to $\Theta(n^3)$.

However, there are other representations of the graph data structure, which give different (generally better) complexities for the same algorithm. For example, having an adjacency matrix to represent the graph means that the check for $u$ is a neighbor of $w$ can be done in $\Theta(1)$ time, even for a clique. Similarly, using a hash set instead of list/array to store neighbors would mean checking for neighbors can be done in $\Theta(1)$ on *average*. These are the more common representation. You could also choose an arbitrary representation where neighbors are sorted (just to demonstrate how the underlying data structure can affect algorithm complexity). In such a case, checking for neighbors will take $\Theta(\log n)$, giving overall $\Theta(n^2 \log n)$. Each has its pros and cons, and the appropriate data structure must be chosen according to your situation.
> 1 votes

---
Tags: graphs, algorithm-analysis, runtime-analysis
---


# Question
Title: SSTF disk scheduling algorithm? What if lowest seek times are equal in either direction?
Using the Shortest-Seek-Time-First (SSTF) disk scheduling algorithm (where we select a request with a minimum seek time from the current head position), what happens if the requests in both directions from the current head position are equal?

For example, if the head position is at 25, and the nearest positions are 5 and 45, how do we determine which one to select?

Thanks

# Answer
Short answer: Depends on implementation.

Long answer: Ties could be broken randomly, or some fixed direction might be preferred. A popular strategy is to select that position first which does not require the head to change direction (since changing direction could take more time). So suppose that the head has moved from 20 to 25, it might prefer 45 next instead of 5 (since it was going towards the higher side). It could also depend on what the further instructions are going to be. Basically, the answer depends on what tie-breaking policy is selected in the implementation, and how complicated the implementation can be.
> 9 votes

---
Tags: algorithms, operating-systems, storage
---


title: Bellman-Ford: shortest path

text:
# Question
Title: Bellman-Ford: shortest path
my assumption:
\- we have an undirected graph with only positive edges
\- the edges are sorted alphabetically:
e.g A-B, A-C, B-D
and e.g not C-A, D-B, A-B

I do not understand, why we need the first loop (line 1) here. I executed the algorithm on paper on 3-4 different undirected graphs. And everytime the first iteration of line1 ends, the algorithms finishes to find the shortest path and the remaining iterations are doing just garbage check.

Can anyone give a concrete graph example where we need the first loop? Does the first loop to do something with the negative edges or edge direction perhaps ?

```
1 for i=1 to vertices.length-1
2    foreach e in edges
3        if e.v2.cost > e.v1.cost + e.weight
4            e.v2.cost := e.v1.cost + e.weight
5            e.v2.pre := e.v1

```

# Answer
> 4 votes
You're correct that there is always an ordering of the vertices for which this algorithm will converge in one iteration, namely the topological ordering given by the shortest-path spanning tree. However, in general the vertices won't be given to us in that order.

Consider for example a path $(C,A),(A,B)$, where $C$ is the source. The algorithm will go through the edges in the order $(A,B),(C,A)$, and will need two iterations to converge.

Here is another example, in which the source it the first vertex: a path $(A,C),(C,B),(B,D)$, where $A$ is the source. The algorithm will go through the edges in the order $(A,C),(B,D),(C,B)$, and will need two iterations to converge.

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


title: Random graph model

text:
# Question
Title: Random graph model
When we say that in random graph we add an edge with a certain fixed probability, what do we actually mean?

For example if probability is 0.5, does that mean that we can just add two edges in a graph because 0.5+0.5=1.

# Answer
> 10 votes
Suppose you wish to compute the random graph $G(n,p)$ that is the graph with $n$ vertices where each edge is added with probability $p.$

Suppose you have a coin that gives tails with probability $p$ and heads with probability $1-p.$

Then what you do you take $\\{1,...,n\\}$ to be the vertex set of your graph and for each pair $(i,j) \in { \\{1,\ldots,n\\} \choose 2}$ you flip your coin. If it comes tails you add the edge $(i,j)$ to your graph otherwise you don't.

# Answer
> 4 votes
In the random $G(n,p)$ model, each of the $\binom{n}{2}$ edges is added to the graph with probability $p$ *independently*. That means that if you consider any two edges, then both are in the graph with probability $p^2$, not $2p$.

# Answer
> 0 votes
In addition to what is said, which is correct, you can build a random graph $G(n,p)$ for $0 \leq p \leq 1$ as follows:

Assume you have a set of vertices $V$ and empty edges $E$. For each $v$ in $V$: For each $u$ in $V$ (where $u \> v$ with respect to some total order among the nodes of $V$): generate a uniform random number $r$ where $r \in \[0,1\]$. If ($r \leq p$) then include the edge $(v,u)$ and $(u,v)$ to $E$.

This generates a random graph $G = (V,E)$ denoted $G(n,p)$ where $|V| = n$. This however is a directed graph. If you want to make it a directed graph, which as that case does not follow the definition, then add only the graph $(v,u)$.

---
Tags: graphs, probability-theory
---


# Question
Title: Is it possible to use plants as a medium to store data? By what data structure?
my question is simple. Is it possible to use plants as a medium to store data?

My opinion is: Possible, but we need to solve, how to distinguish 2 states. Duplication and CRC of stored DATA is quiet simple. Growing new plants is easiest possibility, but we need to create unit, which will take care about raid and duplicating informations between all plants.

Could there be a different data-structure? What is a potential of storing data into plants? What about security? How would you write data into plants without losing that information?

No, this is not a joke. Think about it. It grows everywhere, it is protected against water, cold, wet, dry, magnetic field, shaking and so on.

Try to remember, you can use your own garden as a datastore for your music, films and data. Or just use public garden to share media, photographs, messages or opinions by connecting remotely to plants.

# Answer
> 3 votes
What you propose sounds like it would be quite error laden, as plants are not necessarily independent, and those grown in the same area of the same species might share a common root system, so what you might consider redundancy is not a guarantee that your data will be preserved. I would also venture to say that it's rare for a plant to be hardy against cold weather, and especially against something like an herbicide.

What you might consider is the concept of biocomputing and, more specifically, DNA computing, which uses the ordering of the base pairs to store and manipulate information. The field is still in its infancy, but Turing machine-like behavior has been achieved, and in some cases basic algorithms can be implemented (e.g., the Hamiltonian path problem as cited in the Wikipedia article).

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


# Question
Title: Finding maximum and minimum of consecutive XOR values
Given an integer array (maximum size 50000), I have to find the minimum and maximum $X$ such that $X = a\_p \oplus a\_{p+1} \oplus \dots \oplus a\_q$ for some $p$, $q$ with $p \leq q$.

I have tried this process: $\text{sum}\_i = a\_0 \oplus a\_1 \oplus \dots \oplus a\_i$ for all $i$. I pre-calculated it in $O(n)$ and then the value of $X$ for some $p$, $q$ such that $(p\leq q)$ is: $X = \text{sum}\_q \oplus \text{sum}\_{p-1}$. Thus:

$$ \mathrm{MinAns} = \min\_{(p,q) \text{ s.t. } p\le q}{\text{sum}\_q \oplus \text{sum}\_{p-1}} \\ \mathrm{MaxAns} = \max\_{(p,q) \text{ s.t. } p\le q}{\text{sum}\_q \oplus \text{sum}\_{p-1}} \\ $$

But this process is of $O(n^2)$. How can I do that more efficiently?

# Answer
If $k$ is the bitsize of the integers, then you can compute the Max in $O(n k)$ time.

Basically, the problem is, given $n$, $k$-bit integers $S\_i$, find $i,j$ such that $S\_i \oplus S\_j$ is maximum.

You treat each $S\_i$ as a binary string (looking at the binary representation), and create a trie out of those strings. This takes $O(nk)$ time.

Now for each $S\_j$, you trying walking the complement of $S\_j$ in the trie you created (taking the best branch at each step basically), finding a $j'$ such that $S\_j \oplus S\_{j'}$ is maximum.

Do this for each $j$, and you find the answer in $O(n k)$ time.

Since your integers are bounded, this algorithm for max is basically linear, and so is the algorithm for min got by sorting (as sorting can be done in linear time).

Incidentally, if there were no bounds, then you can reduce element distinctness to the min version.
> 7 votes

# Answer
Sorting helps with $\max$ too. A little bit, at least. Clearly, maximum would be reached by $x \oplus \neg x$. So for each $x = \text{sum}\_i$ do a binary search for $\neg x$. That's $O(n \log n)$ time, same as sorting, so that remains to be the complexity of the whole procedure.
> 5 votes

# Answer
Here is why Strilanc's suggestion works for $\min$. Consider your array $\mathrm{sum}$, and suppose the minimum is achieved by $a\_p,a\_q$, where $p\<q$. Either $a\_p = a\_q$ (in which case $a\_p = a\_{p+1}$), or $a\_p = x0y$, $a\_q = x1z$ for some $x,y,z$. Suppose $q \> p+1$, and let $a\_{p+1} = xbw$. If $b = 0$ then $a\_p \oplus a\_{p+1} \< a\_p \oplus a\_q$, while if $b = 1$ then $a\_{p+1} \oplus a\_q \< a\_p \oplus a\_q$. Therefore $q = p+1$.
> 4 votes

---
Tags: algorithms, algorithm-analysis, performance, binary-arithmetic, arithmetic
---


# Question
Title: RDT2.1 - does the Sender listener to "ack" even though state=ready?
> Computer Networking: A Top Down Approach Featuring the Internet, Jim Kurose, Keith Ross Addison-Wesley 4nd edition , page -223.

Also here slide 60 .

RDT2.1 (Reliable data transfer) -

```
Sender(s):
state=ready; i=0;
On rdt_send(d,m):
    if state=ready
    then
    { p=<s,d,m,i,
    EDC(s||d||m||i)>;
    udt_send(p);
    state=busy; }
On udt_deliver(a)
     If a=<“ack”,EDC(“ack”)>
    then
    { i++;
    state=ready; }
    else udt_send(p);

```

When the `Sender` side is in `state=ready` , does he still listener to "ack" recived from the `Reciver` ?

I need to know this , cause if so it seems that the `Sender` can get duplicate "ack"'s from the `reciver` and inc the `i` without sending any packet mainwhile .

# Answer
> 0 votes
From the code above, Yes.

Regarding your second note. A sender will go to the busy state if it sends a message and there it will wait for an ACK. I can imagine that the reciver would send multiple ACK's only if there is some fault. Usually, such faults are not considered in the basic protocol description, but are considered in the actual implementation.

---
Tags: computer-networks
---


# Question
Title: Determine whether the $k^{th}$ smallest element in max-heap is greater than a given number
A set of numbers is stored in a **max-heap**. We want to find an algorithm with $O(k)$ time complexity to check if $k^{th}$ **smallest** element is greater than an arbitrary given number.

# Answer
Here is an attempt at disproof:

Suppose we have a max-heap of $n$ elements such that $k\<\log n$ and I inform you that the $k^{th}$ smallest element is at the greatest depth of the tree. Without this detail, it could be elsewhere in the tree, but if we cannot solve this special case in time $O(k)$, the more general case will take at least as much time - otherwise, we could use the algorithm for the general case to solve this specific case.

Note that in a max-heap, no node will give a bound on how *small* its children will be (but rather only how large). Thus, if we know the $k^{th}$ smallest is at the greatest depth, no node except those at the greatest depth will provide any information as to the location of the $k^{th}$ smallest element. There are $\log n$ children at the greatest depth and no particular ordering among them (which is one of the key characteristics which differentiates a heap from a sorted binary tree). Thus, you'll need to check all $\log n$ elements before you can determine whether the $k^{th}$ smallest is greater than an arbitrary number.

Hence, no comparison based algorithm with time complexity less than $O(\log n)$ exists to determine for a given max-heap whether the $k^{th}$ smallest element is greater than an arbitrary number.
> 1 votes

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


# Question
Title: What Properties Matter For the Bound on Generalization Error of Hypothesis Set?
As I know, there are several upper bounds on the generalization error of hypothesis set with respect to sample complexity. For hypothesis space $V$, if the learning algorithm output the set of hypotheses that are consistent with the training data, i.e., $\sum\limits\_{1 \leq i \leq n}{\frac{I\[h(x\_i) \not= y\_i\]}{n}} = 0$, the VC theory gives the bound on generalization error. If we consider the "margin" or confidence of classification, PAC Bayes theory gives tighter bounds on generalization error with margin incorporated.

My question is: what other properties or structure of the set of all possible hypotheses output by the learning algorithm matter for the bound on generalization errors? Name a few.

# Answer
> 2 votes
Rademacher complexity is also a tool used to bound generalization error.

---
Tags: machine-learning, artificial-intelligence
---


# Question
Title: Finding the grammar type of the programming language
How can someone find what type of grammar for a given programming language?

Formerly I'm looking for a grammar type for most popular programming languages: C, C++, C#, Java, List, OCaml, Haskell etc.

# Answer
> 6 votes
Programming languages are typically defined in several stages. A language in formal language theory is a set of strings, but that isn't a very useful concept to explain programming languages. The meaning of a source program is defined by several stages of translation; here are typical stages in the compilation of a translation unit:

1. Lexical analysis, i.e. splitting the program into tokens. Token recognition is often performed by finite automata, but not always (e.g. languages with nested comments need a stack at this stage).
2. Parsing. This stage is usually described by a context-free grammar. Although lexical analysis could be described by that same context-free grammar, this would typically result in an extremely complex and slow-to-parse grammar, which is why the two stages are separate.
3. Variable binding, i.e. associating the different uses of the same name to mean the same variable. In particular, in most languages, variables need to be declared before use. This cannot be described by a context-free grammar.
4. Typechecking, if the language has a static type system. There is a lot of variability here.
5. After that point, subsequent compilation stages tend not to have failure cases. There are exceptions, for example some languages regulate recursive definitions at a late stage.

There's no grammar type that describes valid programs in typical programming languages (unless you go for a formalism that can describe all decidable languages or more, such as unrestricted grammars). Many languages can be described by a context-free grammar up to stage 2, but there are exceptions (for example, C has feedback from variable binding to parsing because something like `f(); foo * bar;` is valid in C89 if `foo` is a variable but not if `foo` is a type defined by `typedef`). When you reach the binding stage, there has been work on general models for binding, but I'm not aware of any name for the kind of languages and transducers that correspond to context-free-grammars-plus-bindings. For typechecking, the sky's the limit: there are languages with Turing-complete type systems, and even the ones that aren't are typically very ad hoc and don't particularly fit any interesting category other than decidable.

# Answer
> 3 votes
Since the development of ALGOL60 one realised that a systematic approach to define the language was necessary. Backus-Naur-form was developed, meaning that most programming languages are basically context-free.

I say basically, because some parts of the language cannot be defined in that way. As an example, the declaration of a variable before it is used. On the nonexistence of a phrase structure grammar for ALGOL 60, Robert W. Floyd, Communications of The ACM - CACM , vol. 5, no. 9, pp. 483-484, 1962

---
Tags: formal-grammars, programming-languages
---


# Question
Title: terminology for grouping words in a string?
We commonly create sub-groups of strings in one particular algorithm implementation. I just want to know in CS literature is there any standard name for such kind of grouping. For e.g.

```
Hello World! This is May from the dairy farm.

```

Strings with sub-groups of two:

```
Hello World!
World! This
This is
is May
...

```

# Answer
You are probably looking for the term n-grams, with $n = 2$ in your case. This is very useful in natural language processing and speech recognition.
> 3 votes

---
Tags: terminology, strings, substrings
---


# Question
Title: Dijkstra's algorithm for undirected graphs with negative edges
INPUT: "an undirected, weighted graph (negative weights allowed)"

Could someone give an example for an undirected graph with negative edges where Dijkstra's algorithm doesn't work? As far as i understood it only fails by directed graphs in case of negative edges.
Am i right ?

# Answer
> 3 votes
It has been a long time, honestly. But I am following the pseudocode given in wikipedia.

It is basically the same standard proof that depends on *directed graph* argument and a triangle graph, but simply consider longer paths. (Actually, after reading this solution below, you will realize that even a triangle graph will generate wrong results if it contains a negative edge).

Consider an *undirected* ring graph $G = (V,E)$ where:

* $V = \\{a,b,c,d,e,f,g\\}$ and,
* $E = \\{(a,b),(b,d),(d,e),(e,f),(f,g),(g,c),(c,a)\\}$.

Let's every edge have weight 1 except $(e,f)$ has weight -100. This means that you to get from $a$ to $b$ you should take the other side of the ring. We want to find the distance from $a$ to every other node. This is denoted $dist(v)$ for each $v \in V$.

At the last two iterations of the algorithm, we have $e$ and $f$ left in the queue, and $dist(e)$ and $dist(f)$ both equals to 3. Let's pick the minimum of them (i.e. $e$) and remove it from the queue. Here you will update $dist(f)$ to 3 - 100 = -97. Then you will do the same with $f$ (the queue of vertices is empty now). You will update $dist(g)$ to 2 - 100 = -98 and $dist(e)$ to -97 - 100 = -197. The algorithm terminates since the queue of vertices is empty. And it is just mess !

# Answer
> 6 votes
It's not just Dijkstra's algorithm that doesn't work. Other standard shortest-path algorithms like Bellman-Ford don't work on undirected graphs with negative edges either.

The problem is that these algorithms compute a shortest path tree rooted at the source vertex $s$. Specifically, both algorithms assign a predecessor (or parent) to each vertex $v$, which is the second-to-last vertex on the shortest path from $s$ to $v$. This works for undirected graphs with positive edges and arbitrary directed graphs, because in those graphs, any prefix of a shortest path is another shortest path.

But shortest paths in undirected graphs with negative edges don't necessarily define trees. Consider the following simple example:

The shortest path from $s$ to $x$ passes through $y$ and has length zero. Symmetrically, the shortest path from $s$ to $y$ passes through $x$ and has length zero. Both of these shortest paths use the edge $xy$, but in opposite directions. The edges $sx$ and $sy$ are prefixes of shortest paths, but they are not themselves shortest paths.

Shortest paths can still be computed in polynomial time in these graphs (provided they have no negative cycles), but the algorithms are much more complicated.

# Answer
> 5 votes
Think about a "triangle"(3-clique): an undirected graph $G(V,E)$ with three vertices $a,b,c$ and edges $(a,b),(b,c),(c,a)$. Assign cost $w\_{a,b} = 1$, $w\_{b,c} = -100$, $w\_{c,a} = 100$. If we want to find the shortest path from $a$ to $b$, Dijikstra greedily chooses $b$ via edge $(a,b)$, which has cost one. However, the shortest path from $a$ to $b$ is $(a,c),(c,b)$, which has cost only 0.

In fact, the proof of the correctness of Dijikstra algorithm relies on the fact that all edges have non-negative weights such that the greedy algorithm always stays ahead.

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


title: Names of Softwares used for modeling

text:
# Question
Title: Names of Softwares used for modeling
Which tools or softwares are mostly used for the purpose of modeling a computer network?

# Answer
> 2 votes
I suppose you mean simulating computer networks? because modelling is different (you can model your network as a graph for instance). If this is the case have a look at these simulators:

* *NS2*: built with C++, a discrete-event simulator, open source, and perhaps the most useful. You would need to use Tcl to write the script of the simulation experiments. New open source libraries are always added. I suggest it, however, i know many consider it a bet complex. Good knowledge in C++ is required if you want to maximally exploit it (at least to print your statistics and analyze them). The newer version is *NS3* (i have nt used it yet), but from what I read, you can write your simulation experiments using python or c++.
* *Opnet*: I am not a fan, and it is not open-source. I think there is a student-version.
* *simjava*: if you are a java person, then use this. (I haven't used it, but i saw it being cited in many research papers).

but be careful before starting working with any "network simulator" because in many cases you don't need complex simulators. A simple C++, Java or Python code would be sufficient. (Actually, it is always a good programming exercise to create your own discrete-event simulator for a network).

If you are interested in distributed processors simulation (from a theoretical point of view), then I would suggest *erlang (a programming language)*. It is functional language very similar to Haskell (created by Eriksson). it is very easy to create processes with identities. But even more, you can let the processors exchange messages by sending/receiving messages in a very simple way.

---
Tags: computer-networks
---


# Question
Title: Formal Languages - Expressive power of Formalisms
I need help with the following question:

Order the following formalisms according to their expressive power: placing A before B means that any language definable by A is definable by B. Also state which, if any, of them are equivalent.

```
• Turing Machines (TM)
• Regular expressions (reg.exp.)
• Turing Machines with multiple tapes (TM+)
• Pushdown Automata (PDA)
• Nondeterministic Finite Automata with ǫ-transitions (NFAǫ)
• Nondeterministic Finite Automata (NFA)
• LR(1) grammars
• Nondeterministic Turing Machines (NTM)
• Deterministic Pushdown Automata (DPDA)
• Deterministic Finite Automata (DFA)
• Context-free Grammars (CFG)

```

Is this the correct answer ? I have a exam next week and need to know If my answer is correct.

```
NFAe=NFA=DFA=Reg.exp, LR(1)-Grammar=DPDA, CFG=PDA, TM=NTM=TM+

```

Thanks in advance

# Answer
> NFAe=NFA=DFA=Reg.exp, LR(1)-Grammar=DPDA, CFG=PDA, TM=NTM=TM+

Seems OK to me.
> 3 votes

---
Tags: formal-languages, regular-languages, context-free, regular-expressions, pushdown-automata
---


# Question
Title: Standard notation for the language of the universal Turing machine?
The universal Turing machine $U\_{TM}$ is a TM that takes in as input an encoding of a TM and a string, then runs the TM on the string and does whatever the simulated TM does. The language of the universal TM is the set of all encodings of a TM/string pair as a string for which the TM accepts the string.

I have seen several different names for the language of the universal Turing machine. Michael Sipser refers to it as $A\_{TM}$ (the acceptance language for Turing machines), while Hopcroft, Ullman, and Motwani call it $L\_u$ (the universal language).

Is the a standardized term for the language of the universal Turing machine? I would understand if there might be many "universal Turing machines" that vary in their encoding schemes, so if the answer is "no, there is no general term for this" that would be good to know. I'm mostly asking because I'm teaching an introductory course in the theory of computation and have been using the term $A\_{TM}$ for this without knowing if there is a better term to use.

Thanks!

# Answer
> 6 votes
No, there is no general term for this.

---
Tags: computability, terminology, turing-machines
---


# Question
Title: Why we do isomorphism, automorphism and homomorphism?
What are the key differences between these three terms isomorphism, automorphism and homomorphism in simple layman language and why we do isomorphism, automorphism and homomorphism ?

# Answer
Isomorphism formalizes the notion of **equal** graphs. For example on this figure you see three isomorphic graphs

More formally, an isomorphism of graphs $G\_1$ and $G\_2$ is a bijection $f:V(G\_1) \mapsto V(G\_2)$ that preserves adjacency. That is to say:

$$u \sim\_{G\_1} v \iff f(u) \sim\_{G\_2} f(v)$$

It is not hard to find such a bijection for every pair of graphs on the picture.

Now if $G\_1 = G\_2$ then the obtained mapping becomes an automorphism - a isomorphism from the graph to itself.

You might ask what is the intuitive notion of graph automorphism and the answer is that it gives you some kind of information of which vertices are "equivalent" in a graph. In other words if there is an automorphism of $f$ of graph $G$ such that the vertex $v$ is mapped to vertex $u$ then in a way the neighbourhood of $u$ and $v$ "looks" the same.

This in turn leads to the notion of **graph symmetries**. A graph $G$ is said to be *vertex-transitive* if for every pair of vertices $u,v \in V(G)$ there is an automorphism $f:V(G) \mapsto V(G)$ such that $f(u) = v.$ An example of a vertex-transitive graph is the Petersen graph

and as you can see the graphs "looks" pretty symmetric. That is precisely because it has "many" automorphisms of the described type.

Graph homomorphisms are usually not studied by layman and are more or less of theoretical purposes. For example they are closely related to the notion of **vertex-colourings.** See also Hadwiger Conjecture
> 19 votes

# Answer
In the context of graph theory, a homomorphism $h:G\rightarrow G'$ is a mapping between two graphs that maps adjacent vertices in $G=(V,E)$ to adjacent vertices in $G'=(V',E')$. In other words, for every edge $e=(u,v) \in E$, the edge $(h(u),h(v))\in E'$. Graph homomorphism imply many properties, including results in graph colouring.

Now a graph isomorphism is a bijective homomorphism, meaning it's inverse is also a homomorphism. If two graphs are isomorphic, then they're essentially the same graph, just with a relabelling of the vertices. The problem of determining if two graphs are isomorphic to one-another is an important problem in complexity theory.

Finally an automorphism is isomorphism from a graph to itself.
> 8 votes

---
Tags: graphs
---


# Question
Title: What is the number of expressions containing n pairs of matching brackets with nesting limit?
I know the answer *without* nesting limit is the Catalan number. My question is, specifically, is there a recurrence relation that gives the number of expression containing $n$ pairs of matching brackets such that no more than $l$ open brackets are not closed at any given point?

For instance, for $n=3$ and $l=2$ the answer is $4$. All possible combinations are $(())()$, $()(())$, $()()()$, $(()())$. We cannot have $((()))$ since there are three open brackets that are not closed at the middle.

# Answer
Okay. I think I may have figured it out myself. I invite everyone to check my answer to see if it makes sense. So the first bracket must be a left bracket and there must be some right bracket later on that corresponds to this first bracket. Inside these two brackets there is a valid bracket expression $A$ with depth at most $l-1$ and outside these two brackets there is another valid expression $B$ with depth at most $l$ (since it is not already contained in a pair of brackets like $A$). Also, just like the definition of Catalan numbers, if $n=0$ then the number of valid expressions is $1$. If $n\neq 0$ and $l=0$ then the number of valid expressions is $0$ (since if $n\neq 0$ then we must have at least one pair of brackets, but $l=0$ means that we cannot have more than $0$ open bracket at any time, meaning that there is no way we can construct any valid bracket expressions). So the recurrence relation I got is: \begin{align} C(i, j)= \begin{cases} 1 & i=0 \\ 0 & i\neq 0, j=0 \\ \sum\limits\_{k=0}^{i-1} C(k, j-1)\cdot C(i-k-1, j) & \text{otherwise.} \end{cases} \end{align}
> 5 votes

# Answer
Turns out this is not an easy problem, but it has been solved. A similar case is treated in Bounded discrete walks by Banderier and Nicodème (2010) and they refer to the exact result you need in Combinatoire analytique des chemins et des cartes¹ by Banderier (2001).

---

1. This is a preliminary version. You can obtain a copy of the final version by contacting the author.
> 2 votes

# Answer
A comment and a suggestion.

For *fixed* $\ell$ the language of words with nesting limit $\ell$ is regular, with a very simple automaton, basically a line of states, each representing the current level. Form that automaton a recurrence formula can be obtained (in terms of the number of bracket pairs $n$, again for fixed $\ell$).

Your own formula reminds of the classical formula for Catalan numbers, using *convolution* $C\_{n+1} = \sum\_{i=0}^n C\_iC\_{n-i}$. Convolution is a nice operation when the sequence is presented as generating function, a formal infinite "polynomial"; for Catalan numbers $C(x) = \sum\_{n\ge0} C\_nx^n$. From the given recurrence one obtains $\frac {C(x)-1}x = C(x)^2$ from which experts can solve $C\_n$.

In your formula you have an expression for $C\_{\ell+1}(x)$ and $C\_{\ell}(x)$, the generating functions for $\ell+1$ and $\ell$ bounded expressions. To me it seems \[I might have errors here\] that your formula is $\frac {C\_{\ell+1}(x)-1}x = C\_{\ell+1}(x)C\_{\ell}(x)$. That is a recurrence relation for $C\_\ell(x). Not in the numbers themselves, but in their generating functions.
> 1 votes

# Answer
The question comes down to: how many ways are there to distribute $n$ nodes into subtrees? This is related to integer partitions; in fact, this recurrence describes the desired quantity:

$\qquad \displaystyle \begin{align} a(1,1) &= 1 \\ a(n,1) &= 0 \qquad\qquad\qquad\qquad\qquad\qquad, n\>1 \\ a(n,l) &= \sum\_{P \in \operatorname{Part}(n)} \prod\_{i \in P} a(i,l-1) \qquad, n,l \> 1 \end{align}$

with $\operatorname{Part}(n)$ the set of all partitions (as multi-sets) of $n$. Well, that does not seem to be too approachable.

A more promising avenue might be via grammars and their generating function. For fixed $l \in \mathbb{N}\_+$, the (unambiguous) grammar $G\_l = (\\{S\_i \mid 0 \leq i \leq l \\},\\{(,)\\},\delta\_l, S\_l)$ with $\delta\_l$ given by

$\qquad \displaystyle \begin{align} S\_0 &\to \varepsilon \\ S\_i &\to (S\_{i-1})S\_i \mid \varepsilon \qquad, 0\<i\leq l \end{align}$

generates the Dyck-language restricted to nesting depth $l$. This translates to the equation system

$\qquad \displaystyle \begin{align} S\_0(z) &= 1 \\ S\_i(z) &= z^2S\_{i-1}(z)S\_i(z) + 1 \qquad, 0\<i\leq l \end{align}$

and $\[z^n\]S\_l(z)$, that is the $n$-th coefficient of the series expansion of $S\_l$ (around $z=0$), is the number of such words of length $n$. See here and here for other examples of this technique with references.

For every fixed $l$, solving this system is easily done by computer algebra. I will have to ask around whether there are techniques to solve it in $l$; I know that similar cases have been solved before.
> 0 votes

---
Tags: formal-languages, combinatorics, recurrence-relation, word-combinatorics
---


title: Simplify complexity of n multichoose k

text:
# Question
Title: Simplify complexity of n multichoose k
I have a recursive algorithm with time complexity equivalent to choosing k elements from n with repetition, and I was wondering whether I could get a more simplified big-O expression. In my case, $k$ may be greater than $n$ and they grow independently.

Specifically, I'd expect some explicit exponential expression. The best I could find so far is that based on Stirling's approximation $O(n!) \approx O((n/2)^n)$, so I can use that, but I wondered if I could get anything nicer.

$$O\left({{n+k-1}\choose{k}}\right) = O(?)$$

# Answer
> 7 votes
**Edit:** This answer is for $k\<n$. Without bounding $k$ in terms of $n$ the expression is unbounded.

If $k=n-1$ then your expression becomes $O\left ({{2(n-1)}\choose{n-1}}\right)$. Notice that by Stirling's formula for any $0\<\alpha\<1$ $${m \choose {\alpha m}}= \Theta(m^{-{1/2}} 2^{H(\alpha)m}),$$ where $H(q)=-q \log q - (1-q) \log (1-q)$ is the binary entropy. In particular $H(1/2)=1$. Therefore we have for $k=n-1$ $$O\left ({{2(n-1)}\choose{n-1}}\right)=\Theta((2n-2)^{-{1/2}} 2^{2n-2})=\Theta\left(\frac{ 4^{n}}{\sqrt{n}}\right).$$

Since the upper bound $k=n-1$ is the worst case ( I leave it as an exercise to show this), your expression is $O\left(\frac{ 4^{n}}{\sqrt{n}}\right)$.

# Answer
> 2 votes
Wolfram says Sondow (2005)\[1\] and Sondow and Zudilin (2006)\[2\] noted the inequality: $$\frac{1}{4rm}\left\[\frac{(r+1)^{r+1}}{r^r}\right\]^m \< {(r+1)m \choose m} \< \left\[\frac{(r+1)^{r+1}}{r^r}\right\]^m$$ for $m$ a positive integer and $r\ge 1$ a real number.

We can then use $${n+k-1\choose k} \< {n+k\choose k} = {(r + 1)m \choose m}$$ with $r = \frac{n}{k}$ and $m = k$.

Then we have $${n+k-1\choose k} \< \left\[\frac{(r+1)^{r+1}}{r^r}\right\]^m = \left(\frac{n+k}{k}\right)^{n+k}$$

Now, the binomial expression has the highest value at the middle of the Pascal's triangle. So, in our case, $n+k = 2k$ or at $k = n$.

Substituting that in the above inequality, we get: $${n+k-1\choose k} \< 2^{2n} = 4^n$$.

Therefore, a tighter bound is $${n+k-1\choose k} = O(4^n)$$.

You can also see that the lower bound for the maximum value is $${n+k-1\choose k} = \Omega\left(\frac{4^n}{n}\right)$$

References:
\[1\] Sondow, J. "Problem 11132." Amer. Math. Monthly 112, 180, 2005.
\[2\] Sondow, J. and Zudilin, W. "Euler’s constant, q-logarithms, and formulas of Ramanujan and Gosper" Ramanujan J. 12, 225-244, 2006.

---
Tags: asymptotics, combinatorics, runtime-analysis
---


# Question
Title: An online parallel algorithm for finding top K elements
Suppose we have a function on GPU which calculates elements of array from which we need to select top K elements. The number of elements can be quite big so we can't store them in memory and our algorithm should be online. Another requirement for algorithm is its good parallelization so it could be effectively run on GPU.

Is there any classic approach for the problem? I've thought only of building heap/balanced tree with $k$ elements and inserting new elements into it if new elements is better than existing and popping smaller element. It gives O($n$ log$k$) but it fails with parallelisation because requires synchronization between GPU threads on modifying tree.

# Answer
Here is one naive solution:
Let the number of parallel processes be $m$. Then, keep a separate buffer/heap/balanced tree for each of the $m$ processes. Divide the range of input into $m$ sections. Whenever you read a number, insert it into the appropriate process' heap. This way, each process only works on its own heap/tree. When you are done with the input, and want to output the top $k$ elements, do a partial mergesort to find the overall top-k.

This will require $O(km)$ space and $O(n\log k + km\log k)$ time.
> 3 votes

---
Tags: algorithms, parallel-computing
---


# Question
Title: "Applicative order" and "Normal order" in lambda-calculus
> **Applicative order:** Always fully evaluate the arguments of a function before evaluating the function itself , like -
>
> $(\lambda x. x^2(\lambda x.(x+1) \ \ 2))) \rightarrow (\lambda x. x^2(2+1))\rightarrow \ (\lambda x. x^2(3)) \rightarrow \ 3^2 \ \rightarrow \ 9$
>
> **Normal order:** The expression would be reduced from the outside in , like -
>
> $(\lambda x.x^2 (\lambda x.(x+1) \ 2)) \rightarrow \ (\lambda x.(x+1) \ \ \ 2)^ 2 \rightarrow\ (2+1)^2 \ \rightarrow 3^2 \ \rightarrow \ 9 $

Let $M = (\lambda x.y \ (\lambda x.(x \ \ x) \ \lambda x.(x \ \ x)))$

Why is it that under applicative order, $M \rightarrow$ infinite loop,
but under normal order, $M \rightarrow y$?

# Answer
> 9 votes
$(\lambda x.y \ (\lambda x.(x \ \ x) \ \lambda x.(x \ \ x)))$ is an infinite loop because $$\lambda x.(x \ \ x) \ \lambda x.(x \ \ x) \to \lambda x.(x \ \ x) \ \lambda x.(x \ \ x)$$ Notice that $\lambda x.(x \ \ x)$ just writes it's argument twice.

# Answer
> 17 votes
The term you are reducing is $(K\_y \Omega)$ where $K\_y$ is the constant function $\lambda x. y$ (it always returns $y$, ignoring its argument) and $\Omega = (\lambda x. (x \\, x) \\: \lambda x. (x \\, x))$ is a non-terminating term. In some sense $\Omega$ is the ultimate non-terminating term: it beta-reduces to itself, i.e. $\Omega \to \Omega$. (Make sure to work it out on paper at least once in your life.)

Applicative order reduction must reduce the argument of the function to a normal form, before it can evaluate the top-level redex. Since the argument $\Omega$ has no normal form, applicative order reduction loops infinitely. More generally, for any term $M$, $M \Omega \to M \Omega$, and this is the reduction chosen by the applicative order strategy.

Normal order reduction starts by reducing the top-level redex (because the function $K\_y$ is already in normal form). Since $K\_y$ ignores its argument, $(K\_y \Omega) \to y$ in one step. More generally, $K\_y N \to y$ for any term $N$, and this is the reduction chosen by the normal order strategy.

This case illustrates a more general phenomenon: applicative order reduction only ever finds a normal form if the term is strongly normalizing, whereas normal order reduction always finds the normal form if there is one. This happens because applicative order always evaluates fully arguments first, and so misses the opportunity for an argument to turn out to be unused; whereas normal order evaluates arguments as late as possible, and so always wins if the argument turns out to be unused.

(The flip side is that applicative order tends to be faster in practice, because it's relatively rare for an argument to be unused; whereas it's common for an argument to be used multiple times, and under applicative order the argument is only evaluated once. Normal order evaluates the argument as often as it's used, be it 0, 1 or many times.)

---
Tags: logic, lambda-calculus, normal-forms
---


# Question
Title: Finding containing sets in a set of sets
Suppose I have a set of sets of integers $A$, is there an efficient algorithm/data structure that will allow me to query for all sets of integers that include a given input set? That is, given input $I\subset \mathbb Z$, find $C$, the sets in $A$ that include all of $I$, that is $C=\left\\{ B \in A \mid I\subseteq B\right\\}$.

Looking for the best of a few solutions.

# Answer
The right approach will generally tend to depend on your data -- size of sets, number of sets, range of elements, size of input, number of queries etc. Here are a couple of approaches:

**Approach 1:** You could use a Bloom filter for each of the sets in $A$, and for the input set $I$. Assuming the same number of bits for each set, and the same $k$ hash functions for each bloom filter, you could do a bitwise AND of two filters to do a probabilistic test for subsets. This will give no false negatives, but may give false positives. For example, let $F\_I$ and $F\_{A\_i}$ be the bit-arrays of the Bloom Filters for the input set $I$ and some set $A\_i$ in $A$. Then, if $F\_{A\_i} \cdot F\_I = F\_I$, then there is a possibility that $I \subseteq A\_i$. If they are not equal, then $A\_i$ definitely does not contain $I$. Using 64 bit integers, you can quickly perform bitwise AND, and comparison operations on a large number of bits, and so can quickly eliminate sets which do *not* contain $I$. If they turn out to be equal, then for confirmation, you might then have to check each element of $I$ for presence in $A\_i$, where $A\_i$ might be a hash set.

One downside of Bloom filters is that addition of elements to the set increases the probability of false positives, and deletion of elements is not possible (in simple implementations) since they introduce false negatives. So for deletion of some integer from a set in $A$, the corresponding Bloom filter will have to be recreated. Also, this method will generally give best results when the size of sets is large enough that querying from hash sets starts becoming slow.

**Approach 2:** If the number of sets is fairly large, but the data distribution is such that there are relatively few unique integers (what is relatively few will depend on your implementation and requirements), you could store the unique integers instead of the sets. You could have a hash-map where each integer is the key, and the value contains a bit-vector (or list) of the sets to which the integer belongs to. Then, you check each integer of $I$ for presence in the hash-map. If it is not found in the hash-map ($O(1)$), then no set of $A$ contains $I$. Otherwise, keep taking the intersection of the sets associated with the integer being checked, with the sets so far found that contain all elements checked thus far. Thus, the problem boils down to efficient set intersection. If the list of sets in the hash map is a bit vector, you need to perform bitwise AND. If they are a list (say, sorted), you can use an adaptation of merge-sort.
> 2 votes

---
Tags: algorithms, sets
---


# Question
Title: Notation Conventions for Tree Data Structures
I'm currently working on a paper describing a new algorithm in computational science. If all goes well, this algorithm will be around for a while (within the specific community). As such, I want to set notation conventions that will *not* drive other people insane. The primary difference is that this algorithm makes use (logically) of tree data structures while the traditional algorithms in the field have used linear arrays.

The old algorithms therefore could denote specific data as $data\_i$ (that is, using LaTex subscripts. Similarly, one could refer to $data\_{i-1}$, and it would be clear that that is the "parent" data to $data\_i$. Unfortunately, trees do not support this sort of indexing.

Are there any notation conventions for trees that allow clear, concise descriptions of that sort? I want to be able to give talk about an arbitrary bit of data (i.e. $data\_i$) and readily discuss parent and child data. The community is mathematician heavy and as such mathematical notation of the sub/superscript y operator sort is favored over the class.property CS style. Note also that these are arbitrary trees; they need not be binary or any other such structure.

Does anyone know of a notation convention that would fit the bill? Alternatively, is there a better place to ask this? Thanks for the help.

# Answer
You can use functions.

Let $node$ be an arbitrary node of the tree.

Then $data(node)$ is data associated with $node$, $children(node)$ is set of child nodes of $node$ and $parent(node)$ is parent of $node$.

For data associated with $i^{th}$ child of $node$ you can use $data(children(node)\_i)$ etc.
> 2 votes

---
Tags: algorithms, trees
---


# Question
Title: Turing machine and coming up with an idea
I read many things about the Turing machine and understand how it works but what I can't get the grasp of (and what none of the books seem to try to teach) is how should I approach a problem I am given to solve? I mean: checking if a word is a palindrome, for example, consists of 11 states in the book I'm learning from. For my current state of knowledge, just sitting over an empty sheet of paper and coming up with all these states seems next to impossible, to say the least. When I try to do something like this, I get stuck immediately since I don't know what should I do to make these states work somehow "together". I don't have such problems when programming in some prog languages but here, I just can't figure out how I should approach something consisting of some n-teen states. Could you please point me some direction to learn about it?

# Answer
> 7 votes
Just to expand the comments above, you should try to find a high level algorithm, and then refine its steps in smaller pieces.

For example, if you want to recognize palindrome words, a high level agorithm can be:

```
1. check if the leftmost symbol is equal to the rightmost symbol
2. if they are not equal reject, otherwise delete them
3. if there are other symbols then goto 1, otherwise accept

```

That can be refined in the following way:

```
1.1 move the head on the leftmost symbol
1.2 "store" its value
1.3 if it is the only symbol left then accept (w has an odd length)
1.4 otherwise move the head to the rightmost symbol
2.1 compare it to the "stored" one
2.2 if they are not equal halt and reject, otherwise
2.3 delete the rightmost symbol
2.4 move the head to the leftmost symbol
3.1 delete it
3.2 if the tape is empty halt and accept, otherwise
3.3 goto 1.1

```

The steps are "implemented" using the internal states of the Turing machine. While designing the Turing machine you can name the states with *labels* instead of "q0, q1, q2" to make the design process easier.

If you have a single tape Turing machine, the step *\[1.2 "store" its value\]* means that you must use the internal states to "remember" the symbol read while the head moves to the rightmost one.

Suppose you have two input symbols $a,b$ and $-$ is the blank symbol, then you can use a set of states La,L'a,CMPa and Lb,L'b,CMPb to represent (store) the leftmost symbol read; so steps 1.1, 1.2, 1.3, 1.4, 2.1, can be implemented in this way:

```
     |  a      |   b     |   -
START| a,R,La  | b,R,Lb  | -,R,START << move right until you find a symbol
La   | a,R,L'a | b,R,L'a | ACCEPT    << step 1.3
Lb   | a,R,L'b | b,R,L'b | ACCEPT    << step 1.3
L'a  | a,R,L'a | b,R,L'a | -,L,CMPa  << step 1.4
L'b  | a,R,L'b | b,R,L'b | -,L,CMPb  << step 1.4
CMPa | -,L,MVL | REJECT  |           << compare to a
CMPb | REJECT  | -,L,MVL |           << compare to b
MVL  | .......                       << move left

```

As you can see after reading the leftmost symbol the states are doubled:

```
Lx we are on the first symbol after the leftmost one (which is symbol x)
L'x we are moving rightward from the leftmost symbol x
CMPx we are comparing the rightmost symbol with the leftmost symbol x

```

# Answer
> 3 votes
Try using visual designers like this or turingkara-en, which also contains exercises.

Keep in mind that the TM is meant to be a theoretical, minimalistic model to simplify proofs. Programming on the other hand will get nasty fast. So don't think it's a shame to have problems with programs requiring more than half a dozen states.

# Answer
> 2 votes
Suppose you're given some string over a three-character alphabet $\\{0,1,\\,\\\_ \\}$, where the latter is the blank character. You'd like to know if the input consists of a single "word" over $\\{0,1\\}$, ending with one or more blank characters, which is a palindrome. (There could be multiple words later on the tape, but you're not paid to care.) How could you figure this out?

A word $W = a W' b$ is a palindrome if and only if $a = b$, and $W'$ is also a palindrome. To find the end of the word, you'll need to look for the last character preceding a blank; and whether or not $W$ (or $W'$) is a palindrome, you don't really need to hang onto that first input character $a$ for very long. So you can probably proceed by blanking out the first character (while "storing" what value it is in one of two branches in the program code, using some of the states as a limited memory), and basically shuttle back and forth between the left- and right-hand sides of the string, checking whether the two ends of the word are the same. This is basically the same as working it out for a two-hundred long string of characters over the alphabet where you might scratch out letters on either end (rather than blanking, but it's basically the same) until you found a mismatch, or made your way to the middle.

Generally when designing a Turing machine to solve some problem, you have to find some way to break up the problem into little pieces that can be easily solved by either making local changes to the input, or by recording some piece of information in some long branches or decision-tree-like structures in the state transitions while the machine head searches back and forth for the information that it needs to solve the problem. The challenge in solving problems on a Turing machine is to find a way that involves little to no local memory at the machine head, because it has no stored memory of its own aside from what state it is in; and so it's a sort of a challenging parsing problem. But in the end it's doing basically the same thing — in an extremely primitive way — that you do when you solve a problem involving a long input: it simply reads and rereads the input as it needs to, going back and forth. For simple problems such as this, if you think very carefully about how *you personally* would go about solving such a problem (perhaps while sleep deprived and therefore not having the sharpest memory), you can start to figure out how to write the state transitions for the problem.

Now, if you're told to do it in a specific number of states, that can be difficult, but certainly you can start by trying to find a straightforward way of doing it first, and then thinking (if you've used too many states) if there are any simplifications or optimizations that you can apply, by taking advantage of the structure of the problem somehow. There isn't any sort of general procedure that you can apply to do this, so it's basically down to whether or not you can find the essential structure of the problem (and whether or not your exercise is free from typos).

---
Tags: turing-machines
---


# Question
Title: What factors must one consider choosing an NN structure?
Suppose we have a classification problem and we wish to solve the problem by Neural Network. What factors must one consider choosing an NN structure? e.g Feed Forward, Recurrent and other available structures.

# Answer
Here is a list of parameters you should take into consideration (to name some):

1. The learning algorithm (gradient descent is the most explained of them)
2. The number of layers (3,4 layers is usually enough - input, 1 or 2 hidden, output). The output layer depends on your output (e.g., if you want to classify yes/no then your output layer consists of two nodes). The same applies for input layer. However, you may consider the case of using only a subset of the input for the learning. For instance, you may think that your problem is affected by $k$ variable. However, if you take $k'$ of them then you may get better results.
3. Number of nodes in the hidden layers (you select that by trial and error)
4. Number of training iterations (not too much to avoid over-fitting)
5. Size of training/testing data (there are some known rules like the 80:20 for example)
6. The type of the function used at the nodes (neurons) (e.g. $f(x) = 1/(1+e^x)$ or $f(x) = tanh(x)$), usually the first is sufficient.
7. An important issue is the pre-processing and post-processing of data (this is common in all pattern recognition techniques). You may for instance convert your data by applying a certain function $f$ and then run your experiments.

**Note**: given the many parameters you need to deal with, it is a good approach to use a search algorithm to select the best parameters for you. It is better be a heuristic search algorithm (e.g. genetic algorithm) if you had very large number of parameters set you will deal with (which is usually the case).

**Note**: use the Matlab NN library or Weka (open source). They would have all these parameters for you. In fact, Weka has many other learning algorithms.

**Note**: Perhaps, you may want to use other algorithms then. If this is case, try support vector machines. There was a historical battle between these two algorithms (in the 1990's). SVM won it ! (I am not being very scientific here).
> 4 votes

---
Tags: artificial-intelligence, neural-networks, neural-computing
---


# Question
Title: What does big O mean as a term of an approximation ratio?
I'm trying to understand the approximation ratio for the Kenyon-Remila algorithm for the 2D cutting stock problem.

The ratio in question is $(1 + \varepsilon) \text{Opt}(L) + O(1/\varepsilon^2)$.

The first term is clear, but the second doesn't mean anything to me and I can't seem to figure it out.

# Answer
> 14 votes
The expression "$A(L) \le (1 + \varepsilon) \text{Opt}(L) + O(1/\varepsilon^2)$" is, as usual, shorthand for the following:

> There exist constants $c\>0$ and $\varepsilon\_0\>0$ such that for all $\varepsilon$ with $0\<\varepsilon\<\varepsilon\_0$, the inequality $A(L) \le (1 + \varepsilon) \text{Opt}(L) + c/\varepsilon^2$ holds.

# Answer
> 2 votes
This seems a looser variant of polynomial time approximation scheme ($PTAS$). If $\epsilon$ is not small, you can achieve approximation with ratio very close to $1+\epsilon$ because $\mathcal O(\epsilon^{-2}) \le c \epsilon^{-2}$ is small. ($c$ is a fixed positive real number independent of any other variable.) If $\epsilon$ is small, the 2nd term gets larger.

However, $OPT(L)$ is usually much larger than a constant. No matter how large $\mathcal O(\epsilon^{-2})$ becomes, it is still a constant (since $\epsilon$ is a given target real number for the approximation ratio). So Kenyon-Remila theorem means: "Constructed $\le (1+\epsilon) OPT +\mathcal O(1)$ for any given app ratio $1+\epsilon$, where the $\mathcal O(1)$ term is a constant depending on $\epsilon$. It is actually $\mathcal O(\epsilon^{-2})$."

# Answer
> 0 votes
In fact, the algorithm in question is a so-called "asymptotic polynomial time approximation scheme" (APTAS), which means that the approximation ratio is measured asymptotically in terms of the optimum; the approximation ratio of $(1+\epsilon)$ is approached as the optimal value gets larger since the additive term $O(\epsilon^{-2})$ is indepentent from both $n$ (the number of items in the instance $L$) and $Opt(L)$, the optimal value of the instance $L$.

# Answer
> -1 votes
are you looking for explanation on Big O? if Yes, this link might help you http://en.wikipedia.org/wiki/Big\_O\_notation

# Answer
> -1 votes
If I remember correctly, this usage you feel confused predated (and actually inspired) the usage of $O$ for asymptotic functions. For example, you can have a short look at http://en.wikipedia.org/wiki/Prime\_number\_theorem.

---
Tags: algorithms, asymptotics, approximation
---


# Question
Title: Demonstrating that for every monotonic grammar there is an equivalent context-sensitive grammar
I'm trying to understand the equivalence in expressive power of formal grammars whose rules take the form:

$$ \alpha \rightarrow \beta $$ where $ |\alpha| \leq |\beta| $ (called a *monotonic* grammar), and grammars whose rules take the form:

$$ \alpha B \gamma \rightarrow \alpha C \gamma $$

where $\alpha $ and $\gamma$ are strings of terminals & non-terminals or possibly empty, and $B$ and $C$ are single non-terminals. I understand that grammars of the second kind are already, by definition, grammars of the first kind, but I'd like to understand how to derive a grammar of the second kind, given one of the first kind (a monotonic grammar). Can anyone suggest a good reference for this? Many thanks in advance.

# Answer
First replace every terminal $a$ with a non-terminal $X\_a$ and add a production $X\_a \to a$, because context sensitive grammars only work on non-terminals. Then, for every production $A\_1\dots A\_n \to B\_1\dots B\_n$ create a new non-terminal $D$ and replace the production with a sequence of productions

$$\begin{align} A\_1A\_2\dots A\_n &\to DA\_2\dots A\_n \\ DA\_2A\_3\dots A\_n &\to DB\_2 A\_3 \dots A\_n \\DB\_2A\_3A\_4\dots A\_n &\to DB\_2 B\_3A\_4 \dots A\_n \\ &\vdots \\ DB\_2\dots B\_{n-1}A\_n &\to DB\_2\dots B\_{n-1}B\_n \\ DB\_2 \dots B\_n &\to B\_1B\_2 \dots B\_n \end{align}$$

which are all context sensitive. Also, replace every production $A\_1 \dots A\_n \to B\_1 \dots B\_m$ where $n \< m$ with

$$\begin{align} A\_1\dots A\_n &\to B\_1\dots B\_{n-1}C \\ C &\to B\_nB\_{n+1} \dots B\_m\end{align}$$

where the first production can be made context sensitive as previously shown and the second one is context free. Of course, this construction may introduce problems (if $B\_1A\_2 \to \dots$ is already in the grammar, for instance). This is easily solved by adding new non-terminals.
> 5 votes

---
Tags: formal-grammars, context-sensitive
---


# Question
Title: Pumping lemma for Context-Free Languages
I have a question about a specific pumping lemma problem for Context-Free Languages.

Suppose we have the following Language:

> $L = \\{a^{i}b^{j}c^{k}d^{l} \mid 0 \< i \< k \wedge j \> l \> 0 \\}$

Here is my attemp to prove that the language is not context-free:

Assume $L$ is context-free. Let $n\>0$ be the pumping length given by the lemma.

Let $z = a^{n}b^{n+1}c^{n+1}d^{n}$, then $z \in L$.

Than according to the lemma, $z$ can be written as $z = uvwxy$ where the following properties hold:

1. $|vx| \geq 1$
2. $|vwx| \leq n$
3. for every $i \geq 0$, $uv^{i}wx^{i}y \in L$.

We have 6 different possibilities for $vwx$:

1. $vwx = a^{i}$ where $i \leq n$
2. $vwx = a^{i}{b^j}$ where $i+j \leq n$
3. $vwx = b^i$ and $i \leq n$
4. $vwx = b^{i}c^{j}$ and $i+j \leq n$
5. $vwx = c^{i}$ with $i \leq n$
6. $vwx = c^{i}d^{j}$ and $i+j \leq n$

Is this right so far? The thing that I'm unsure of is if my different cases for $vwx$ are right.

How do I choose the pumping length for case 2? If I choose $i$ = 2, what if $i$ is zero ? Then I don't have any contradiction.

Thanks in advance

# Answer
Let me rephrase property 3 of the pumping lemma: for every $l \geq 0$, $uv^lwx^ly \in L$. Now let's consider the seven different cases:

Case 1: $vx = a^i$ where $i \> 0$. Choose $l = 2$ to get $a^{n+i} b^{n+1} c^{n+1} d^n \notin L$.

Case 2: $vx = a^ib^j$ where $i,j \> 0$. Like case 1 or case 3.

Case 3: $vx = b^i$ where $i \> 0$. Choose $l = 0$ to get $a^n b^{n+1-i} c^{n+1} d^n \notin L$.

Case 4: $vx = b^ic^j$ where $i,j \> 0$. Like case 3 or case 5.

Case 5: $vx = c^i$ where $i \> 0$. Choose $l = 0$ to get $a^n b^{n+1} c^{n+1-i} d^n \notin L$.

Case 6: $vx = c^id^j$ where $i,j \> 0$. Like case 5 or case 7.

Case 7: $vx = d^i$ where $i \> 0$. Choose $l = 2$ to get $a^n b^{n+1} c^{n+1} d^{n+i} \notin L$.
> 6 votes

---
Tags: formal-languages, formal-grammars, context-free, pumping-lemma
---