# Question
Title: How do you find out if the polygon lies to the right of a regular vertex?
In section 3.2 of the book *Computational Geometry: Algorithms and Applications* (by Berg et al.), the authors describe a procedure to make a polygon y-monotone. The algorithm distinguishes vertices into $5$ different types: "start", "end", "regular", "split" and "merge" vertices.

A regular vertex is a vertex which has one of its neighboring vertices above it, and the other neighbor below it. A regular vertex can be on the left or right chain of the polygon.

Given a regular vertex $v$, how do I find out if the polygon lies to the right or left of $v$?

The polygon is stored in a doubly-connected edge list. The vertices have coordinates and are stored in a normal DCEL data structure along with the half-edges and polygons. It seems reasonable to expect an elegant solution that uses the DCEL.

# Answer
I'm going to assume that your DCEL is counter-clockwise (ccw) oriented, meaning that if we traverse the list of half-edges incident the polygon's interior in order we make a counter-clockwise walk of the polygon. (This is standard.)

Let $v\_i$ be your vertex, from the DCEL you can easily obtain $v\_{i-1}$ and $v\_{i+1}$, the vertices immediately preceding and following (resp.) $v\_i$ in the ccw walk of the polygon. (The DCEL will have an edge $e\_{i-1}$ with target $v\_i$ and an edge $e\_{i}$ with source $v\_i$ both incident to the polygon $P$, and that $source(e\_{i-1}) = v\_{i-1}$ and $target(e\_i) = v\_{i+1}$.)

If $v\_{i-1}$ is below $v\_i$ (and $v\_{i+1}$ is above $v\_i$) then $P$ is to the left of $v\_i$. Otherwise it is to the right. You can see this by drawing out the two possible cases. The point is that locally as you travel from $v\_{i-1}$ to $v\_{i+1}$ the polygon is on your left, so if you are traveling from a vertex above $v\_i$ to a vertex below it, in your view the polygon is on your left, but in the "global" view, the polygon is on the right. However, if you are traveling from a vertex below $v\_i$ to a vertex above it, then your view and the local view both have the polygon on the left. And by the definition of a regular vertex, those are the only two things we need to check.

Of course since you already know that one of $v\_{i-1}$, $v\_{i+1}$ is above and the other is below you only need to check for one. Something like, if $v\_{i-1,x} \< v\_{i,x}$ then $P$ is left, otherwise right.

Here is a sketch:

I saw the code base you are using in your other posting on DCELs, so here is the code version:

First you will need to augment your vertex data structure to have fields for x and y:

```
struct vertex {
    struct half_edge *rep;  /* rep->tail == this */
    double x, y;
};

bool polygon_isleftof(half_edge *he) {
  return he->next->tail->y > he->tail->y;
}

```

By the way, when dealing with DCELs I have found that for many applications it is best to work with half-edges directly rather than vertices (in other words, if you want to pass a vertex to a function, just pass one of the half-edges for which it is a tail/source). That way you get two pieces of information: 1.) the vertex you are interested in and 2.) the face your are interested in. So in the code above my polygon\_isleftof tells you whether the vertex which is the tail of he is to the right of the face which is incident to he. If I instead passed a vertex and a face the code would be much slower:

```
bool polygon_isleftof_slow(vertex *v, face *f) {
    //first we need to find a half-edge incident both f and v
    half_edge *walk = v->rep;
    //loop over all half-edges with tail equal to v:
    do {
        if (walk->left == f) break; //exit the loop if we find a half-edge incident f
        walk = walk->twin->next;
    } while (walk != v->rep);

    //If we didn't find a half-edge incident f and v, then return false:
    if (walk->left != f) {
        return false;
    } else {
        return walk->next->tail->y > walk->tail->y;
    }
}

```

Notice that in the first case, `polygon_isleftof` is $O(1)$ whereas in the second case `polygon_isleftof_slow` is $O(n)$. And since you are probably traversing the polygon using half-edges anyway, there is no reason not to just operate on half-edges and only access the vertices as needed in functions.
> 2 votes

---
Tags: algorithms, data-structures, computational-geometry, doubly-connected-edge-list
---


# Question
Title: Problem with storing an existing triangulation in a DCEL
I am trying to store an existing 2D triangulation (of which I have all of the vertices and edges) in a DCEL data structure.

Using the algorithm described in this answer, I was able to store a part of the triangulation, but not the "half-edge" representative for each triangle.

The algorithm is reported below

> ### Algorithm
>
> 1. For each endpoint, create a *vertex*.
> 2. For each input segment, create two *half-edges*, and assign their tail vertices and twins.
> 3. For each endpoint, sort the *half-edges* whose tail vertex is that endpoint in clockwise order.
> 4. For every pair of *half-edges* `e1, e2` in clockwise order, assign `e1->twin->next = e2` and `e2->prev = e1->twin`.
> 5. Pick one of the half-edges and assign it as the representative for the endpoint. (Degenerate case: if there's only one half-edge `e` in the sorted list, `set e->twin->next = e` and `e->prev = e->twin`). The next pointers are a permutation on half-edges.
> 6. For every cycle, allocate and assign a face structure.

Instruction 5 seems to be easier said than done. How can I ensure that every triangle will have a representative, and that a representative will be assigned only once for each triangle?

Furthermore, in point 6, which cycle is it referring to?

(So far, my implementation is similar to the one provided in the answer.)

# Answer
The point of a half-edge data structure is that each half-edge is incident to exactly one face, and each face is represented by a list of half-edges given in order around the face. This is different from a normal planar map in which edges are incident to two faces. This can make certain coding tasks easier to deal with. So an (undirected) edge $\\{u, v\\}$ gets split into two half-edges $uv$ and $vu$ which are directed and twins of each other.

To list all half-edges (in order) incident to a face just requires following next pointers from each edge. Something like:

```
HalfEdge startEdge = ...some half-edge...
HalfEdge walk = startEdge;
do {
  //... do something here ...
  walk = walk.next;
} while (walk != startEdge);

```

In a DCEL the code above will walk around all edges in ccw order incident to the face startEdge.

Here is a concrete example:

Suppose we want to represent a triangulation with a single triangle $ABC$ where $A$, $B$, and $C$ are given in ccw order. We create six half edges: $AB$, $BC$, $CA$, $BA$, $CB$, and $AC$.

set the twins: $AB.twin$ = $BA$, $BA.twin = AB$. $AC.twin = CA$, $CA.twin = AC$, $BC.twin = CB$ $CB.twin = BC$.

set the next pointers: $AB.next = BC$, $BC.next = CA$, $CA.next = AB$ $AC.next = CB$ $CB.next = BA$, $BA.next = AC$.

and prev pointers $AB.prev = CA$, $BC.prev = AB$, $CA.prev = BC$, $BA.prev = CB$ $AC.prev = BA$ $CB.prev = AC$.

Now we already have implicitly faces: if we start with $AB$ and chase the next pointers around until we get back to $AB$, we get $AB$, $BC$, $CA$ which represents the interior of the triangle. If we start with $BA$ we get a different list: $BA$, $AC$, $CB$. This list represents the so-called "unbounded" face which is the exterior of our triangle. These are the "cycles" you mentioned. The first cycle is the (cyclic) list $AB\leftrightarrow BC\leftrightarrow CA$ and the second is $BA \leftrightarrow AC\leftrightarrow CB$.

For some applications this is all you need, but for others you may want a structure for storing extra information about the face. Keep in mind that the face is already represented by the double linked list $AB\leftrightarrow BC\leftrightarrow CA$. However we can make two data structures $f\_0$ and $f\_1$ for storing extra information for the unbounded face $f\_0$ and the interior of the triangle $f\_1$. We then set pointers again:

$AB.face = f\_1$, $BC.face = f\_1$, $CA.face = f\_1$, $BA.face = f\_0$, $CB.face = f\_0$, $AC.face = f\_0$.

So now each half-edge points to the face incident to it. But we may also want to start with a face structure and then get a list of its incident half-edges. We already have the half-edges stored as lists, so we just need to point to any arbitrary start of the list, something like:

$f\_0.halfEdgeList = BA$

$f\_1.halfEdgeList = AB$

So now given a face $f$, we can loop over all its incident half-edges as before:

```
HalfEdge startEdge = f.halfEdgeList;
HalfEdge walk = startEdge;
do { // ... same as above
  walk = walk.next;
} while (walk != startEdge);

```

Finally, assuming you already have correctly set the previous, next, and twin pointers for your half-edges, then you could do something like this: when you create a half-edge, initialize its face pointer to 0. Then add all half-edges to a queue.

Note I'm writing pseudo-code, not C++ code here:

```
while (!queue.Empty()) {
  HalfEdge startWalk = queue.dequeue();
  if (startWalk.face = 0) {
    //This half-edge doesn't have a face yet
    Face f = create_new_face(); //Some function to create a new face and add it to any appropriate lists

    //Now walk around all edges from startWalk setting the face:
    HalfEdge current = startWalk;
    do {
      current.face = f;
      current = current.next;
    } while (current != startWalk);
  }
}

```

UPDATE: I looked at the link you provided and want to give a bit of terminology. Above I used the terms source and target to refer to the the start and end vertices of the half-edge. In the C++ code you linked to source is called tail, and target is the tail of the twin. So if you have a half edge called halfEdge:

```
vertex *source = halfEdge->tail;
vertex *target = halfEdge->twin->tail;

```
> 0 votes

---
Tags: algorithms, data-structures, computational-geometry, doubly-connected-edge-list
---


# Question
Title: Extension of Time Hierarchy Theorem to LBAs
I am trying to prove:

> Let there be a constructible function $t: ~\mathcal{N} \to \mathcal{N}$. Then there exists a language $L$ where $L$ is decidable by an LBA in $O(t(n))$ time, but not $o\left(\frac{t(n)}{\log t(n)}\right)$ time. You may assume that LBAs have a fixed tape alphabet and have unique symbols marking the start and end of the input.

I've read through Sipser's version of the proof (Theorem 9.10) several times, but am not sure how to apply it to LBAs. Hints only please.

# Answer
It may help you to remember that LBA's are simply non-deterministic TM's with a limited tape (instead of infinite).
> 2 votes

---
Tags: complexity-theory, automata
---


# Question
Title: Dijkstra algorithm vs breadth first search for shortest path in graph
I have asked this question in StackOverflow. I was asked to move in here. so here it is:

I need some clarifications and inputs regarding Dijkstra's algorithm vs breadth first search in directed graphs, if these are correct.

Dijkstra's algorithm finds the shortest path from Node `A` to Node `F` in a weighted graph regardless of if there is a cycle or not (as long as there are no negative weights)

but for that, All paths from `A` to all other Nodes in the graph are calculated and we grab the path from `A` to `F` by reversing the sequences of nodes in `prev`.

BFS: finds the shortest path from node `A` to node `F` in a non-weighted graph, but if fails if a cycle detected.

however, BFS just calculates the path from Node A to Node F and not necessarily all path from Node A. if Node F is reached early, it just returns the path.

# Answer
> 19 votes
1. BFS does not fail if a cycle is detected. http://en.wikipedia.org/wiki/Breadth-first\_search
2. Dijkstra's doesn't calculate all paths from A to F either. It stops when it finds the shortest path from A to F.
3. In an unweighted graph, you can use BFS to search for the shortest path from A to all other nodes in the same run too! (just don't make it stop as soon as it finds F)
4. You can use a BFS type algorithm to find the shortest path if you know all lengths are integers less than a 'small' number k in O(k(v+e)) time by replacing every edge (u,w) of length n with a path of n-1 nodes between u and w, the length of each edge in the path is 1.

Hope this helps.

# Answer
> 6 votes
While Aditya's response is good I would like to clarify a few points.

**Breadth-First Search**

Breadth-First Search (BFS) just uses a queue to push and pop nodes to/from. This means that it visits nodes in the order of their depth.

If it happens that the cost of all operators is the same (so that they are considered to be equal to 1), then it is guaranteed to find an optimal solution.

As a consequence, note the following:

1. It just enumerates paths until the solution is eventually found. It cannot be said that this algorithm computes the shortest path from the source node to the goal node (period!). It just computes the distance to all paths it encounters on its way towards the goal. In other words, whatever is said of the path it finds to the goal node can be equally said of any other path discovered by it.
2. Nothing prevents BFS to be applied to graphs with arbitrary costs. The only point to remember is that the algorithm preserves completeness (so that it is guaranteed to find a solution) though admissibility is lost (i.e., it does not guarantee the solution found to be optimal).
3. Originally, BFS did not consider a CLOSED list to store all the expanded nodes so that you are somehow right when you say that it might fall in a cycle. However, since it explicitly stores all nodes in memory and the more memory demanding layer is always the latest one, BFS is usually extended with a CLOSED list that stores all nodes previously expanded. If a transposition is encountered before expanding a node it can be safely skipped.

**Dijkstra's algorithm**

In fact, if you add a CLOSED list to BFS as suggested in point 3 above and also sort nodes in the stack (the so-called OPEN list) in ascending order of $g(n)$ (i.e., the cost of the path from the start state to $n$) then you have Dijkstra's algorithm (well, there is also another very important difference, while BFS stops when *generating* the goal node, Dijkstra's stops when *expanding* it).

So:

1. Again, this algorithm just enumerates paths until the solution is eventually found. It is not true that it visits all nodes in the state space and indeed, Dijkstra's algorithm is known to be complete (i.e., it guarantees that a solution will be found if any exists) even if the underlying graph is infinite.
2. You can safely apply Dijkstra's algorithm when operations have arbitrary costs. Indeed, that's the reason why you substituted the queue with a heap where nodes are inserted in ascending order of their cost.
3. Edgar Dijkstra originally considered using a CLOSED list (you can check his paper, it is only a few pages long and very easy to read) so that cycles are properly considered.

Hope this helps, maybe a more detailed explanation of these algorithms is needed. If so, do not hesitate to ask for them

Cheers,

---
Tags: algorithms, graphs
---


# Question
Title: Short and slick proof of the strong duality theorem for linear programming
Consider the linear programs

\begin{array}{|ccc|} \hline Primal: & A\vec{x} \leq \vec{b} \hspace{.5cm} & \max \vec{c}^T\vec{x} \\ \hline \end{array} \begin{array}{|ccc|} \hline Dual: & \vec{c} \leq \vec{y}^TA \hspace{.5cm} & \min \vec{y}^T\vec{b} \\ \hline \end{array}

The weak duality theorem states that if $\vec{x}$ and $\vec{y}$ satisfy the constraints then $\vec{c}^T\vec{x} \leq \vec{y}^T\vec{b}$. It has a short and slick proof using linear algebra: $\vec{c}^T\vec{x} \leq \vec{y}^T A \vec{x} \leq \vec{y}^T\vec{b}$.

The strong duality theorem states that if the $\vec{x}$ is an optimal solution for the primal then there is $\vec{y}$ which is a solution for the dual and $\vec{c}^T\vec{x} = \vec{y}^T\vec{b}$.

Is there a similarly short and slick proof for the strong duality theorem?

# Answer
> 3 votes
Probably not. Here is a conceptual argument based on

**Farkas Lemma**: Exactly one of the following alternatives has a solution:

> 1. $Ax \le b$ and $x \ge 0$
> 2. $y^TA\ge 0$ and $y^Tb \< 0$

Now let $\delta$ be the optimal objective value of the primal. Let $\epsilon \> 0$ be arbitrary. Let $A'$ to be $A$ with an additional $-c^T$ as the last row. Let $b'$ to be $b$ with an additional $-\delta - \epsilon$ as the last value.

The system $A'x'\le b'$ has no solution. By Farkas, there is a $y' = (y,\alpha)$ such that:

> $y^TA\ge \alpha c$ and $y^Tb \< \alpha (\delta + \epsilon)$.

Note that if $\epsilon = 0$ we are in the other alternative of Farkas. Therefore $\alpha \> 0$.

Scale $y'$ so that $\alpha = 1$. $y$ is dual feasible. The weak duality implies $\delta \le y^Tb \< \delta + \epsilon$.

---
Tags: algorithms, reference-request, linear-programming, linear-algebra, duality
---


# Question
Title: Number of submatrices with a particular sum
Given a $n\times n$ matrix `A[0...n-1][0....n-1]` where all entries are non-negative integers, and a non-negative integer `K`, I want to find the number of submatrices whose entries sum to `K`.

The best solution I can find has $O(n^4)$ running time. Any ideas how to improve the running time?

# Answer
Here is an O(N3) algorithm (it is valid only for matrices of non-negative values).

1. Compute prefix sums for each column: `B[k][j] = Sum(A[0..k][j])`.
2. For each pair of row indices `(p, q)`:
3. Apply a two-pointers algorithm for implicit array of values `B[q][j]-B[p][j]`.

Where a two-pointers algorithm advances first pointer while sum of values between pointers is less than desired and advances second one when this sum is greater than desired. When the desired sum is found, advance first pointer (`x` times) while sum does not change and advance second pointer (`y` times) while sum does not change (we might need to advance pointers more then once in case of sub-matrix column summing to zero), then add `x*y` to counter of found sub-matrices and continue.
> 4 votes

# Answer
If you are only interested in sub-matrices beginning with \[0\]\[0\], it is not hard to get O(n^2) with dynamic programming - save partial sums and use them to build sums of larger sub-matrices.
> 1 votes

# Answer
It is easy to achieve $O(n^3 \lg n)$ running time by accumulating partial sums, if all entries of $A$ are positive.

Define the $n\times n$ matrix $B$ so that

$$B\[i,j\] = \sum\_{r=0}^i \sum\_{s=0}^j A\[r,s\].$$

The matrix $B$ can be computed in $O(n^2)$ time, by filling it in iteratively using the following recurrence relation:

$$B\[i,j\] = B\[i,j-1\] + \sum\_{r=0}^i A\[r,j\] \qquad \text{(for $j\>0$)}.$$

If you precompute the column sums and row sums in advance, the recurrence relation above can be computed in $O(1)$ time per entry of $B$.

Then, once you have the matrix $B$, you can test whether a given submatrix has sum $K$ in $O(1)$ time. In particular, the elements of the submatrix $A\[i..i'\]\[j..j'\]$ sum to $B\[i',j'\]-B\[i,j'\]-B\[i',j\]+B\[i,j\]$, which can be computed in $O(1)$ time.

How do you enumerate all submatrices that sum to $K$, given this data structure? It is not entirely trivial, as there are $O(n^4)$ possible submatrices, so enumerating them all will take too long. But if all matrix entries are positive, you can do it in $O(n^3 \lg n)$ time using binary search.

In particular, you enumerate all possible values of $i,i',j$ and then do binary search on $j'$ to find whether there exists a $j'$ such that $B\[i',j'\]-B\[i,j'\]-B\[i',j\]+B\[i,j\] = K$, using the fact that $B\[i',j'\]-B\[i,j'\]-B\[i',j\]+B\[i,j\]$ is a monotonically strictly increasing function of $j'$ when $i,i',j$ are held fixed.
> 1 votes

---
Tags: algorithms, arrays, matrices
---


# Question
Title: shortest cost tiling of path to x distance
I have a distance to get to, and square tiles that have a cost and length. EX: a 1 unit block that costs 1 unit to purchase.

So if I was trying to get 10 units away. I would require 10 of the 1 unit blocks at that point for a total cost of 10.

So another example would be a distance of 10 units away except I have two tiles to pick from of \[1,1\], \[5,4\], \[x,y\], x = length, y = cost.

The cheapest cost would be 8, (2 of 5 blocks = 10 distance).

So, at first I thought this would be a shortest path problem, but seeing how I can re-use tiles that didn't work out the best.

I then tried to implement a rod-cutting algorithm, using the length of the rod as distance and the price for the length of cuts. This algorithm though kept trying to maximize the distance, which wasn't what I wanted.

My final method, was to divide the cost by length for each tile to find the most cost efficient tile (shown below). This worked for about 9% of my unit-tests, it was failing most because it couldn't see that it might be more cost effective to use a more expensive tile, etc.

I started with a greedy algorithm using cost / length for most efficient cost tiles, when I couldn't get that to work. I moved towards a dynamic programming algorithm using the cutting rod example.

This required a lot of hacky work, since I didn't really want the maximized value via cutting. I wanted the minimal cost value of that distance, though it also only had about a 2% success rate.

I then went into recursion, with help from another tip. Using a tiny little Tile class to help me pass variables around, this had lots of success with my self test values, but once again only had a 10% success rate.

So after trying DFS, Rod-Cutting, Recursion, and Dynamic Programming. I am lost. Did I overlook one of these algorithms?

# Answer
You're heading a good direction with dynamic programming, but you haven't set up the set of subproblems quite right just yet. Don't give up on it yet. Instead, you should keep exploring some more candidate sets of subproblems.

The art of dynamic programming lies in picking the right set of subproblems, and then identifying a suitable recurrence relation in terms of those subproblems. Sometimes you'll have to try several possible ways of decomposing into subproblems before you find something that works, so don't give up if your first try is not a success!

Here are some hints to help you:

* When one of your inputs is an array, you can try using "the set of prefixes of the array" as your set of subproblems. In other words, if the input is an array `A[0..n-1]`, your subproblems can be all of the prefixes `A[0..j-1]`, where `j=0,1,2,..,n-1` (this gives `n` subproblems).
* When one of your inputs is a non-negative integer, you can try using "the set of non-negative integers no larger than the input" as your set of subproblems. In other words, if the input is a non-negative integer `m`, your subproblems can be all of the integers `i`, where `i=0,1,2,..,m`.
* When you have two inputs, there are some possibilities to choose a set of subproblems. One way is to hold one of the inputs fixed and consider all subproblems for the other input. Another way is to choose all pairs of subproblems (if $S$ is the set of subproblems for the first input, and $T$ is the set of subproblems for the second input, use $S \times T$ as your set of subproblems).

Also, you set up your dynamic programming implementation wrong. Your goal should not be to maximize the number of price, or to maximize anything. You are trying to *minimize* the total cost (so `Math.max` is out of place here). Also you will need to pass in something that describes both the cost and the length of each tile; your code doesn't show anything about that.

Finally, don't write code now. Just figure out the ideas. Write down a recurrence relation, and try to check whether it is correct. Then, write pseudocode and show it is correct. Only then should you write code. Diving straight into code is a mistake and is getting you mixed up in implementation details before you've even worked out the conceptual material. Also, on this site, you should not be showing us code: you should be showing us algorithms and pseudocode. This site is about algorithms, not code (StackOverflow is the place for code).

These hints should be enough to enable you to find a solution via dynamic programming (i.e., an efficient algorithm that always finds the least-cost tiling, with reasonable running time).
> 1 votes

---
Tags: algorithms
---


# Question
Title: If P = NP, how do I prove I can find the maximum clique in polynomial time?
I want to prove that if P = NP, then there is a polynomial time algorithm for finding the largest clique in an undirected graph.

I understand how to use a verifier to find this but my issue is since P = NP it doesn't want me to use a verifier. I'm not sure how to approach this.

# Answer
> 5 votes
Assuming $P=NP$, then $CLIQUE \in P$, so you can test for a clique of size $k$ in polynomial time for all $k$. So you can just test for a clique of each size between $1$ and $n$ where $n$ is the number of nodes.

Now that you have the max clique size, you just need to find it. You can do that by removing an abitrary node, then re-running then seeing if there still exists a clique of max size. You will be left with the max size clique.

---
Tags: graphs, time-complexity
---


# Question
Title: Techniques (tools) to convert temporal logic (CTL,CTL* or LTL) to μ-calculus formulae
Suppose one wants to use a μ-calculus model checker, but specify things in temporal logics, which is easier (more intuitive). Is there a technique (even better, a tool) that automatically translates formulae in any of these logics (CTL,CTL\* or LTL) to the μ-calculus?

Thanks very much in advance!

# Answer
You may find an answer or at least relevant references in the article A linear translation from LTL to the first-order modal $\mu$-calculus.
> 4 votes

---
Tags: logic, simulation, linear-temporal-logic, computation-tree-logic, mu-calculus
---


title: How does taking modulo 1 make sense?

text:
# Question
Title: How does taking modulo 1 make sense?
I need some help understanding the problem statement in CLRS 11.3-4 pg 269. It says:

> Consider a hash table of size $m = 1000$ and a corresponding hash function $ h(k) =\left \lfloor m(kA \bmod 1) \right \rfloor $ for $A = (\sqrt5 - 1)/2$. Compute the locations to which the keys 61, 62, 63, 64, and 65 are mapped.

Is $\mod 1$ a misprint in my copy? Also $A$ is a real number. Is modulus defined for non-integer numbers?

# Answer
Thanks to for clarifying mod 1 concept , for constant $\mathcal{A}$ I got the proper explanation in **CLRS** itself it says : Although this method works with any value of the constant $\mathcal{A}$, it works better with some values than with others. The optimal choice depends on the characteristics of the data being hashed. Knuth suggests that $$ \mathcal{A} \approx (\sqrt(5) - 1)/div 2 = 0.6180339887 ... $$ is likely to work reasonably well. As an example, suppose we have $ \mathcal{k} = 123456, \mathcal{p} = 14, \mathcal{m} = 2^{14} = 16384,$ and $ \mathcal{w} = 32.$ Adapting Knuth’s suggestion, we choose $\mathcal{A}$ to be the fraction of the form $$\mathcal{s}/2^{32}$$ that is closest to $$(\sqrt(5) - 1)/ 2,$$ so that $$ \mathcal{A} = 2654435769/2^{32}.$$ Then $$\mathcal{k} . \mathcal{s} = 327706022297664 =(76300 . 2^{32} )+ 17612864,$$ and so $\mathcal{r\_{1}} = 76300$ and $\mathcal{r\_{0}} = 17612864.$ The 14 most significant bits of $ \mathcal{r\_{0}} $ yield the value $\mathcal{h}(k) = 67$.
> 2 votes

# Answer
That's not a misprint. $kA \bmod 1$ makes sense. For instance, $37.239 \bmod 1 = 0.239$.
> 8 votes

---
Tags: algorithms, terminology, hash
---


# Question
Title: How to generate a connected random network topology for a specific number of nodes?
I'm trying to generate a random but realistic network topology so I can test the performance of some routing algorithms. I came across Waxman's model described in Routing of Multipoint Connections, which seems pretty simple:

1. Distribute $N$ nodes randomly across a plane (uniform in x and y).
2. For each pair of nodes, generate an edge between them with the probability $ P = \beta \exp \frac{-d}{L\alpha}$, where $d$ is the euclidean distance between the nodes, $L$ is the maximum distance between two nodes, and $\alpha$ and $\beta$ are parameters in the range $(0, 1\]$.

I've implemented my current understanding of Waxman's algorithm as a simple web-based demo, which visualizes a generated topology from chosen parameters $\alpha$, $\beta$, and $N$.

However, I want to be able to generate a *connected* network topology for a specific number of nodes. Since Waxman's algorithm generates edges probabilistically, I usually end up with disconnected nodes. How do I connect the rest of the nodes to the topology in a way consistent with Waxman's algorithm, i.e. simulates a real network topology?

There are plenty of ways to "finish" the topology by connecting the disconnected nodes, but I don't know which one is the most compatible with the already-generated edges. Waxman's paper doesn't seem to mention how disconnected nodes are treated.

# Answer
> 1 votes
I played with your demo a little bit and I suppose given a distribution of points, $\beta$ and $\alpha$ can be chosen properly so that the generated graph is connected with a high probability. A brute-force approach can be choosing the parameters using a binary search.

# Answer
> 0 votes
You could compute connected components, find the largest connected component, and keep all the nodes in the largest component (discarding the rest of the nodes). That would give you a connected graph and might yield a reasonable distribution on the resulting graph.

---
Tags: graphs, computer-networks
---


# Question
Title: Prove that all non-recursive languages are infinite
I am wondering this statement above \[the title\] is true or not.

Here is what I've already had : non-recursive means undecidable.

I've read this Are all infinite languages undecidable?

which says:

If a Language is undecidable(non-recursive), there must be some strings make the TM fail to halt.SO IT MUST HAVE INFINITE OF THEM WHICH MAKE THE TM FAILS TO HALT.

How could this prove my statement\[title\]? Can anyone explain it to me a bit more clearly?

Thanks

TM means Turing machine. And too be clear My question is : Does ALL non-recursive languages are Infinite?

# Answer
> 1 votes
First, not every infinite language is undecidable. Some infinite languages are very easy to decide. For example, the language of all words ($\Sigma^\*$).

The converse is true, however: every undecidable language is infinite. In order to show this, we can simply show how to decide every finite language:

Consider a finite language $L=\\{w\_1,...,w\_n\\}$. In order to decide it, you can construct a TM $M$ that encodes in its *states* the words $w\_1,...,w\_n$. This is done as follows: the machine starts in $q\_0$, which intuitively corresponds to the empty word $\epsilon$.

$M$ then reads an input letter. If there is no letter, meaning that the word is $\epsilon$, then $M$ either goes to $q\_{acc}$ or $q\_{rej}$, depending on whether or not $\epsilon\in L$. Now, if there is an input letter $\sigma$ on the tape, $M$ goes to a state that corresponds to $\sigma$. Then, again, it reads the tape. If there are no more letters, it either accepts or rejects, depending on whether $\sigma\in L$. Otherwise, it read the next input $\tau$ and moves to the state $\sigma\tau$, and so on, until the maximal length of a word in $L$ is reached, in which case $M$ rejects immediately.

So essentially, $M$ has a state for each word of length at most $k$, where $k$ is the maximal length of a word in $L$. Thus, $M$ can keep track of the word that was read so far, and decides if it needs to be accepted.

---
Tags: formal-languages, turing-machines
---


title: Complements of Linear Bounded Automata?

text:
# Question
Title: Complements of Linear Bounded Automata?
Would switching the accept and reject states of an LBA A create a new LBA we'll say A' in which the language of A' is the complement of the language of A? I believe the answer is yes just by working out an example...but I'm not sure on a solid proof...nor am I sure if the fact that I am working with an LBA vs a regular turing machine makes a difference in this case.

# Answer
I agree with Hendrick Jan; I don't think the currently accepted answer is correct. Even though $A\_{LBA}$ is decidable, that doesn't mean the LBA itself doesn't loop.

As a counterexample, consider an LBA $A$ over $\Sigma = \\{0, 1\\}$, where $A$ accepts $0$ but loops on $1$. Then $L(A) = \\{ 0 \\}$. The LBA with swapped states, $A'$, would reject $0$ and still loop on $1$, so $L(A') = \\{ \\}$. This should be a sufficient counterexample as $\overline{L(A)} = \\{1\\}$, which is not equal to $L(A')$.
> 2 votes

# Answer
It depends whether the automaton is deterministic or not. If it is deterministic, then the answer should be *yes*, just as in the case of DFAs, and you can mimic the proof for DFAs. If it is non-deterministic, then the answer should be *no*, just as in the case of NFAs; in fact NFAs are a special case of non-deterministic LBAs, and the NFA counterexample can be adapted to the LBA setting.

(The set of languages accepted by non-deterministic LBAs is closed under complementation, but the proof is not quite as straightforward; it is known as the Immerman--Szelepcsényi theorem.)
> 5 votes

---
Tags: formal-languages, turing-machines, linear-bounded-automata
---


# Question
Title: Can Euclidean TSP be exactly solved in time better than (sym)metric TSP?
Symmetric/Metric TSP can be solved via the Held-Karp algorithm in $\mathcal O(n^2 2^n)$.

See A dynamic programming approach to sequencing problems by Michael Held and Richard M. Karp, 1962.

In Exact Algorithms for NP-Hard Problems: A Survey (PDF) Woeginger writes:

> This result was published in 1962, and from nowadays point of view almost looks trivial. Still, it yields the best time complexity that is known today.

Thus, this is the best known upper-bound.

**Question:**

> Are there any better results for Euclidean TSP? Or does that best-known bound apply to Euclidean TSP as well.

How is Euclidean TSP different? Well,

* Euclidean TSP can be encoded into $\mathcal O(n \log m)$ space, where $n$ is the number of cities, and $m$ is the bound on the integer coordinates of the city locations. As opposed to (sym)metric TSP variants, which essentially require a distance matrix of size $\mathcal O(n^2 \log m)$. Thus, it might be easier to solve; for example, perhaps Euclidean TSP can be more easily encoded into k-SAT, because the distance function is implicit.
* Contrary to popular notion, Euclidean TSP's reduction from k-SAT is quite different from (sym)metric TSP. UHC (undirected Hamiltonian cycle), symmetric TSP, and metric TSP are pretty directly related to each-other. But formulations of reductions from (sym)metric TSP to Euclidean TSP are not easy to come by. Paragraph, from interesting article, The Travelling Salesman’s Power by K. W. Regan (bold mine):

> Now the reductions from 3SAT to TSP, especially Euclidean TSP, are less familiar, and we ascribe this to their being far more “expansive.” **Texts usually reduce 3SAT to Hamiltonian Cycle, then present the latter as a special case of TSP, but this does not apply to Euclidean TSP**. The ${\mathsf{NP}}$-completeness of Euclidean TSP took a few years until being shown by Christos Papadimitriou, and a 1981 paper by him with Alon Itai and Jayme Luiz Szwarcfiter advertised a “new, relatively simple, proof.” This proof uses vertex-induced subgraphs of the grid graph in the plane, for which the shortest possible TSP tour and any Hamiltonian cycle have the same length. Despite this simplification, the gadgets involved are large—a diagram of one occupies most of one journal page.

Hunting down k-SAT $\rightarrow$ Euclidean TSP reductions is quite an adventure; so far I've found two of them. One $\rm k\text{-}SAT \rightarrow CircuitSAT \rightarrow PlanarCircuitSAT \rightarrow EuclideanTSP$, and another, even tougher one to find, $\rm k\text{-}SAT \rightarrow DHC \rightarrow UHC \rightarrow PlanarUHC \rightarrow EuclideanTSP$. The latter reduction can perhaps be seen to make Euclidean TSP parallel (sym)metric TSP.

# Answer
One can exploit planar separator structures in a geometric setting and thus solve Euclidean TSP exactly in $O(n^{c \sqrt{n}})$ time, where $c$ is some small constant greater than 1. There's at least three simultaneous results for this; Smith's PhD thesis \[1\], Kann's PhD thesis \[2\], and Hwang et al. \[3\]. Each algorithm has a running time of $O^\*(c^{\sqrt{n} \log n})$. This is much better than $O(n^2 2^n)$. As far as I know, it is still an open question whether the running time can be improved by say getting rid of the logarithmic term.

---

\[1\] W.D. Smith, Studies in computational geometry motivated by mesh generation. Ph.D. Thesis, Princeton University, Princeton.

\[2\] V. Kann, On the approximability of NP-complete optimization problems, Ph.D. Thesis, Kungliga Tekniska Högskolan, Stockholm, 1992.

\[3\] R.Z. Hwang, R.C. Chang, R.C.T. Lee, The searching over separators strategy to solve some NP-hard problems in subexponential time, Algorithmica 9 (1993) 398–423.
> 4 votes

---
Tags: graphs, reference-request, time-complexity, np-hard, traveling-salesman
---


# Question
Title: How do you obtain transition relation of a PDA?
I know how to figure out the start state, accepting state, input alphabet, and all that stuff. But how do you develop the transition relation of a PDA? For an FSM, (q0,a),q1) means if you start at q0 and get an a, you transition to q1. But what does (S,a,e),(S,a) mean? (S is start state and e is epsilon)

Here's a picture if that helps. I want to understand the circled part. I will be extremely appreciative of any help.

# Answer
As you can see, $\Delta$ is a set of pairs that represent a transition function. First element of the pair is a triple $(q, a, X)$, where $q$ is a state, $a$ is an input symbol (possibly empty string), and $X$ is the top stack symbol.

The other element of the pair describes the action of PDA when its configuration fits the above triple. This other element is again a pair $(p, \gamma)$, where $p$ is a new state and $\gamma$ is a sequence of symbols replacing $X$. If $\gamma = \epsilon$, then $X$ is just popped.

It might help to view $((q, a, X), (p, \gamma))$ as

$$(q, a, X) \rightarrow (p, \gamma)$$
> 1 votes

---
Tags: pushdown-automata
---


# Question
Title: Using pumping lemma to prove a language is not context free
When using the pumping lemma for a context free language, if I write any $w \in L$ as $uvxyz$, is my goal to show that a string will not pump for ANY arrangement of $uvxyz$ that I choose, or is my goal to show that THERE EXISTS some arrangement of $uvxyz$ over $w$ that will pump?

# Answer
> 5 votes
The pumping lemma claims that if the language is context-free, then there exists a configuration such that you can pump the string. Therefore, to prove that the language isn't context-free, you must show that pumping fails for *every possible* arrangement.

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


title: What is "memory coalescing"?

text:
# Question
Title: What is "memory coalescing"?
I came to know that the graphic processing unit have something called memory coalescing. On reading on it I was not clear on the topic. Is this any way related to Memory Level Parallelism.

I have searched in Google but was not able to obtain a satisfactory answer.

It would be helpful if someone gives a more comprehensive, easy-to-understand explanation.

# Answer
"Coalescing" can also refer to **coalescing memory access patterns**. In this usage, coalescing is used to mean making sure that threads run simultaneously, try to access memory that is nearby. This is usually because:

* Memory is usually retrieved in large blocks from RAM.
* Some processing units will try to predict future memory accesses and cache ahead, while yet processing older parts of memory.
* Memory is cached in a hierarchy of successively larger-but-slower caches.

Therefore, making programs that can use predictable memory patterns is important. It is even more important with a threaded program, so that the memory requests do not jump all over; otherwise the processing unit will be waiting for memory requests to be fulfilled.

Diagrams inspired by **Introduction to Parallel Programming: *Lesson 2 GPU Hardware and Parallel Communication Patterns***:

Below: Four threads, with uniform memory access. The black dashed rectangle represents a single 4-word memory request.

The memory accesses are close, and can be retrieved in one go/block (or the least number of requests).

However, if we increase the "*stride*" of the access between the threads, it will require many more memory accesses. Below: four more threads, with a stride of two.

Here you can see that these 4 threads require 2 memory block requests. The smaller the stride the better. The wider the stride, the more requests are potentially required.

Of course, worse than a large memory stride is a random memory access pattern. These will be nearly impossible to pipeline, cache or predict.

### TikZ sources:
> 14 votes

# Answer
I think I see two uses of the word "coalescing" around the net, both having to do with memory. One is **coalescing freed memory allocations**, which is what is referred to in the wikipedia page linked in the question.

---

### Coalescing freed memory allocations

When allocating memory, sometimes the memory manager can have a situation where there are two adjacent memory blocks that are freed. Combining these would make them a single freed memory block - this is called "coalescing". Example:

Starting with 4 allocated blocks:

Later, one of them is freed:

And later another is freed:

Now, why have two adjacent free blocks? Coalescing them:

Coalescing can occur as soon as it is possible, or, for example, in a garbage collector, when the collector runs.

### TikZ sources:
> 4 votes

---
Tags: terminology, reference-request, computer-architecture, memory-management
---


# Question
Title: Scheduling optimization problem in theta(n)
I've been told it is possible to find a solution to this optimization problem in $\Theta(n)$ but I still don't know how I could do it. I did find easily a solution in $n\lg (n)$ though. I only need to have a VALID solution, not the optimal.

This is the problem :

Let say you have n tasks that have a start time and a max time. Each task takes 1 unit of time to complete.

So for example :

```
T1 = 2,3
T2 = 1,4
T3 = 4,5
T4 = 1,5
T5 = 3,4

```

This means that T1 CAN be started at time 2 and must be done by time 3. So a correct solution could be :

> T2, T1, T5, T3, T4

Any idea on how I could create an algorithm in $\Theta(n)$? For now I thought of using a sorting algorithm that does not use comparison but it only works with integer so I can't really get a reference to an object or something.

# Answer
> 1 votes
Since there are no dependencies between tasks, you might try a greedy algorithm: at each step, take the task that has the smallest start time (of all remaining tasks), then move on to the next time step. This does end up requiring you to sort.

If the start and end times are all bounded above by some constant times $n$, you might want to read up on non-comparison based sorting routines, such as counting sort. These sorting algorithms can achieve $O(n)$ time (under those conditions), yielding a $O(n)$ time solution to your problem (under the condition that the start and end times are all bounded above by some constant times $n$).

If you have no guarantees on the range of possible start and end times, then as David Richerby explains in his comment, there is no hope of achieving $O(n)$ time: there is a reduction from sorting, as he explains, so $O(n \lg n)$ is about the best you can hope for if we have no guarantees about the start and end times. That still might be plenty efficient in practice; for realistic values of $n$, $\lg n$ will be quite small, and standard sorting algorithms are extremely efficient.

---
Tags: optimization, scheduling
---


# Question
Title: Priority queue for partially ordered priorities with infima
I have a some objects with priority that is compound type and is only partially ordered. I need to select the objects in order of this priority (i.e. yield *minimal* item each time). But rather than arbitrarily completing the order, I would prefer if the queue was stable in a sense that if there is more than one minimal element, it should return the oldest first.

Is there any heap data structure that would work with partial ordering? Or a modification of regular priority queue to work with it? Common choice for the algorithm I need is simple binary or 4-ary heap, but that does not work with partial ordering.

The priority values support:

1. Partial ordering using operation $\preccurlyeq$. It's partial ordering, so it's possible that $a \preccurlyeq b$ is false and $b \preccurlyeq a$ is also false. I write $a \not\lesseqgtr b$ in that case.
2. Finding infima (glb) and suprema (lub). $\inf(x\_i)$ is the maximal $y$ such that $y \preccurlyeq x\_i$. Calculating the infimum of $n$ values takes $O(n)$ time. **Infimum** (and supremum) **of every set exists.**
3. A linear extension for the partial ordering could be defined. Using it for the priority queue is the easy way out as the algorithm does work that way. But the order affects performance and the order of insertion looks like it should be best in avoiding worst cases.

Additionally the algorithm that I want to use this in needs to know infimum of all priorities in the queue.

The priorities have some real-world meaning, but are subject to change, so it does not seem viable to rely on other properties they could have.

---

Note: Binary heaps don't work with partial ordering. Assume a binary heap with $a$, $b$ and $c$, where $a \preccurlyeq c$ and $a \not\lesseqgtr b$ and $a \not\lesseqgtr c$. They are positioned in that order, so

```
     a (0)
   /   \
 b (1)   c (2)

```

now *d* is inserted. Next free position is 3, the left child of $b$, so we get

```
        a (0)
      /   \
    b (1)   c (2)
  /
d (3)

```

If $d \preccurlyeq a$ (which implies $d \preccurlyeq c$ from transitivity, but does not say anything about $d$ and $b$) and $d \not\lesseqgtr b$, then $d$ does not get swapped with $b$, because it's not less. But it actually is less than $a$, but it's not compared with it, so now the main heap invariant does not hold; top is not minimal.

I suspect a forest of heaps somewhat in style of binomial heap could be made to work. Basically it's important to always compare new values with root and only link together comparable elements. It would make the trees in the forest randomly sized and thus make the complexity dependent on number of mutually incomparable sets in the heap. I somewhat suspect the complexity can't be fixed (we have to keep comparing until we hit a comparable element) I might have missed something, so I am leaving this open.

---

Note: The ordering is *partial* and while there are ways to define a linear extensions for it, adding a timestamp and using it as secondary criterion is *not* one of them. Suppose we assigned the timestamp $t(a)$ for each $a$ and defined the ordering $\preccurlyeq'$ as $a \preccurlyeq' b$ iff $a \preccurlyeq b$ or ($b \not\preccurlyeq a$ and $t(a) \le t(b)$. Then suppose we have distinct $a$, $b$, $c$, such that $t(a) \le t(b) \le t(c)$ and $c \le a$. Then $a \preccurlyeq' b$ and $b \preccurlyeq' c$, but $c \preccurlyeq' a$, so the relation is not transitive and therefore is not an ordering at all. This kind of extending only works for weak orderings, but not partial ones.

---

**Edit:** I realized that not only is infimum of any set defined, but I actually need to be able to get infimum of elements currently in the queue efficiently. So I am now contemplating whether adding special nodes containing infima of subtrees to some common heap structure would help.

# Answer
Although the exact problem posed in the original question does seem to be difficult (and I would be interested in a solution to that problem, especially the infima finding part). I just wanted to note that if the partially ordered set indeed consists of vectors using a product order, and if it is sufficient to just have the guarantee that the priority queue returns the values in an order that is "compatible" with the partial order (that is, smaller elements are always returned before larger elements), then there is a fairly easy way to do it.

The idea is essentially to find a topological ordering of the partially ordered set. That is, a total order '$\le\_T$' such that $\mathbf{a}\le\mathbf{b}\implies \mathbf{a}\le\_T\mathbf{b}$. For vectors using a product order, this is fairly easy: just use a lexicographical order '$\le\_S$', where the first "component" is the sum of all the components used for the product order (the rest of the components are essentially arbitrary, so you could also stick to a weak order). We can then see that $$\mathbf{a}\<\mathbf{b}\implies \forall\_i(a\_i\le b\_i)\text{ and }\exists\_i(a\_i\<b\_i)\implies(\sum\_i a\_i)\<(\sum\_i b\_i)\implies\mathbf{a}\le\_S\mathbf{b}$$ and $$\mathbf{a}=\mathbf{b}\implies \forall\_i(a\_i=b\_i)\implies(\sum\_i a\_i)=(\sum\_i b\_i)\implies\mathbf{a}\le\_S\mathbf{b},$$ and thus that $\mathbf{a}\le\mathbf{b}\implies\mathbf{a}\le\_S\mathbf{b}$. We can thus use this order with a priority queue and be sure that smaller elements (in the product order) will always be extracted before larger elements.
> 3 votes

# Answer
What's wrong with making your partial ordering complete?

> But rather than arbitrarily completing the order, I would prefer if the queue was stable in a sense that if there is more than one minimal element, it should return the oldest first.

If you prefer 'oldest first', then your order is effectively complete; 'incomparable' items are comparable by age.

Add a timestamp (or any other monotonously growing integer) to each item and use it if 'real' comparison is impossible.
> 2 votes

# Answer
EDIT: this seems to be an interesting problem, and I had a little research about it. I suggest you read the following:

1. Darell Raymond. Partial order databases, PhD Thesis, University of Waterloo.

I suggest you read this paper: Daskalakis, Constantinos, et al. "Sorting and selection in posets." SIAM Journal on Computing 40.3 (2011): 597-622.

The authors presents here a data structure called ChainMerge that accepts a poset and a chain decomposition of the poset into $q$ chains. The size of the data structure is $O(n q)$. The authors presents an algorithm for finding the minimas that runs in $O(w n)$ where $w$ is an upper bound on the width of the poset. .. I thought maybe this is interesting.

Note: I deleted a previous naive answer. Please click on edit to see it.
> 1 votes

# Answer
My use of terminology may be incorrect. Please edit my answer directly to fix any problems you find.

---

First, mutually incomparable sets need to be detected from the inputs.

For example, there may be 5 objects, `a, b, c, d, e`, but their partial ordering form two disconnected graphs:

* `a ≤ b ≤ c`
* `d ≤ e`
* but any of `{a, b, c}` is incomparable with any of `{d, e}`.

These mutually incomparable sets need to be detected first, before the objects can be stored into an appropriate data structure. This can be done with a Union find algorithm

---

For efficiency, the insertion of a new object needs to have an efficient way of finding "the list of existing objects which are comparable with this new object".

---

Now, within each subset (respectively `{a, b, c}` and `{d, e}`), the minima should be well-defined. (For each subset there can be *one or more* minima, due to partial ordering.)

I see this as a directed acyclic graph. Trying to fit it into a heap seems disastrous.

---

To extract the minima from this composite data structure, the next step is to get the list of all minima from all subsets, pick the one with the earliest timestamp, and remove and return this object.
> 0 votes

# Answer
A project I'm working on involves a similar problem (incidentally I'm also using the partial order of vectors). We already had a quadratic time algorithm for sorting a randomly ordered list, and I developed an insertion algorithm by observing its behaviour when only one object was out of order. We don't know whether or not this is the fastest possible implementation.

Here is some pseudocode.

```
class PartialOrderPriorityQueue
   q <- empty list
   method insert (n):
     for i <- 0 to (q.length - 1):
       if q[i] <= n:
         t <- q[i]
         q[i] <- n
         n <- t
     q.append(n)

   method pop():
     return q.remove(0)

```
> 0 votes

---
Tags: data-structures, priority-queues
---


# Question
Title: Maxima of diagonals in a column wise and row wise sorted matrix
Let $\\{a\_i\\}$ and $\\{b\_i\\}$ be non-decreasing sequences of non-negative integers.

How fast can one find $$c\_j=\max\_{0 \leq i\< j}\\{a\_i+b\_{j-i-1}\\}$$ for all $0\leq j\leq n-1$?

Naively, it takes $O(n^2)$ time, but I'm hoping monotonicity can help here.

It's easy to observe $\\{c\_i\\}$ is also non-decreasing. If we consider the matrix $M$ where $M\_{i,j} = a\_i+b\_j$, then it is a matrix sorted in both row and column direction, and we are searching for the maximum element in every diagonal.

However, if it's an arbitrary column wise and row wise sorted matrix, this problem require $\Omega(n^2)$ time.

Proof: Let all the numbers below the main diagonal be $\infty$. The elements in the $k$th diagonal are randomly numbers from $(k,k+1)$. Reading any entry provides no information for any other entry.

Edit: This problem is much harder than I anticipated. We can model this problem as a convolution problem over the semiring $(\min,+)$ (take the dual, search for min instead of max), and it can be solved in $O(\frac{n^2}{\log n})$ time according to a Ryan Williams's answer on mathoverflow. It doesn't use the information that the sequence is non-decreasing though.

# Answer
~~Great question! "Distance Transforms of Sampled Functions", by Felzenszwalb and Huttenlocher shows how to compute this in $O(n \lg n)$ time.~~

"Necklaces, Convolutions, and X+Y", By Bremner et al. shows a $O\left(\frac{n^2}{\frac{\lg^2 n}{(\lg \lg n)^3}}\right)$ algorithm for this problem on the real RAM and a $O(n \sqrt{n})$ algorithm in the nonuniform linear decision tree model.
> 5 votes

---
Tags: algorithms
---


title: LZW decoding process

text:
# Question
Title: LZW decoding process
I'm trying to understand how LZW decodes a string.

For example suppose that we have a dictionary where:

* a=0
* b=1

and we have to encode the string "**aabbabaabb**", so the output of the encoding process (if I have not made mistakes) produces the string "**0011324**" and the dictionary became(using a tree representation):

<sub>(source: f.cl.ly)</sub>

The decoder will just know "0011324" and the starting dictionary where there are just a=0 and b=1.

> How does it work the decoding process with just these 2 informations?

# Answer
Short answer: the decoding algorithm follows the same steps as the coder: it actually builds the tree. E.g., in your example the first two 0's mean two a's have been read, This then implies the code for aa was added to the tree as number 2. This continues, but necessarily the decoder always is one step behind the coder. In most cases all information is present to make decisions in the next move. Unfortunately there is the possibility that the decoder needs the code that has been just inserted in the tree (and is not available for the decoder since it lags behind). That case is so specific that it can be reconstructed from the other information (then the unknown letter must be the first letter of the last code).

That is the global view. Wikipedia has a larger example.
> 2 votes

---
Tags: information-theory, lempel-ziv
---


title: Precise definition of term: *schema*

text:
# Question
Title: Precise definition of term: *schema*
Does the term *schema*, in the context of describing a structure, refer to the actual structure of the data, or the *description* of this structure? I.e. can I talk about the schema of an entity without a *schema language*?

For example, suppose I am writing documentation for some JSON API, that always returns a particular structure, say:

```
{
   "name" : "jeroen",
   "age" :  28
}

```

Can I say that the *schema* for the payload returned by this API includes required values for "name" and "age"? Or does the term exclusively refer to another document that formally describes this structure using a schema language of some sort? In that case, what is another appropriate term to refer to the recurring pattern in the structure?

The Github API, has a section titled schema: http://developer.github.com/v3/#schema. However, the word schema is not mentioned in the text itself, nor do they use any schema language. This would suggest that schema is just a general term for the structure/attributes of the output. Unless they consider english as a schema language, in which case the entire page is a schema. Hmmm.

# Answer
> 3 votes
In order to write the documentation of the structure of the JSON objects returned from your API you can follow two approaches:

1. describe the common attributes and of the objects returned by every function of your API; and then for each API function describe the specific attributes (their type, meaning, and example);
Many APIs that use JSON to exchange data are documented using this approach: e.g. Google APIs for various services, Facebook Graph API, Twitter API, ...
In this case I think it is not correct to use the term "schema".
2. or you can give a formal description of the output using a schema definition language like JSON-schema (designed by the IETF) and that plays the same role of the XML schema definition language for XML. But I don't know if JSON-schema is an established standard (there is an active Google group, but I didn't find any "notable" example, ... ).
In this case you should provide a valid (json-)schema for the output of each function.
If you choose this approach, then you should say that *name and age are two required properties of the (json-)schemas of the (json-)objects returned by the functions of your APIs* (but obviously you should provide the full-schemas, too)

---
Tags: terminology, encoding-scheme
---


# Question
Title: Is membership of x in an infinite set decidable?
In order to prove a certain function to be partially computable, I need to show an $\mathbb S$-program that computes it. I could really use the predicate $X \in B$ in my program to draw my conclusion. To give you the idea of what I am dealing with here it is one of my problems:

> Give an infinite set $B$ such that $\Phi(x,x)\uparrow$ for all $b \in B$ and such that $$H(x) = \begin{cases}1 \text{ if } \Phi(x,x)\downarrow \\ 0 \text{ if } x \in B \\ \uparrow \text{ otherwise}\end{cases}$$ show that $H(x)$ is partially computable.

I am wondering if membership for infinite set is decidable and therefore can be used to write $\text{IF } X \in B$ such program. Am I allowed?

**Edit:** the notation $\Phi(x,x)\uparrow$ means the function is undefined.

# Answer
No, this is not allowed, in general, if we know nothing about the set $B$.

As Andrej Bauer explains in the comments: if the set $B$ is arbitrary and there are no guarantees about the set $B$ (as you state in the comments), then no, you cannot write "IF $X \in B$" in a program, as the predicate $X \in B$ might not be computable (depending upon the set $B$).

Re-reading your question, I see that you are allowed to choose a set $B$ of your choice (subject to some conditions). If you're able to choose $B$ in a way that makes $B$ recursively enumerable, then $B$ is no longer completely arbitrary and you now have an additional condition on $B$ which makes this a straightforward homework (as Andrej Bauer also explains in the comments).
> 1 votes

---
Tags: computability, decision-problem
---


# Question
Title: What is the lower bound of the following computation
I came across this question was I was browsing online

An operation OP has the following characteristics

```
    OP Latency = 7 clocks
    OP cycles/issue =2

```

Derive the minimum number of cycles required for the following computation:

```
 X[0] OP X[1] OP X[2] OP ....... OP X[N-1]

```

The answer was written as 7 + 2(n-2). But I was not able to achieve the result. Can someone help me to solve this.

**My try:** As suggested by D.W. to check the value for n=3,4,5 For n=3, I am getting lower bound as 7+2(2)

For n=4, I am getting lower bound as 7+3(2)

For n=5, I am getting lower bound as 2(7)+4(2)

For n=6, I am getting lower bound as 2(7)+5(2)

Am I going correct. But it deviates from the answer given

# Answer
Your edit changes the question. $7+2(n-2)$ *is* a lower bound on the number of cycles to get the answer, but it is not the minimum number of cycles. For some values of $n$, the minimum number of cycles is strictly larger than $7+2(n-2)$.

---

Example: if $n=3$, your goal is to compute $X\[0\] OP X\[1\] OP X\[2\]$.

The optimal sequence is $Y := X\[0\] OP X\[1\]; Z := Y OP X\[2\]$. This takes 14 cycles.

It's not 9 cycles as you wrote: the value of $Y$ is not ready until 7 cycles have finished, and the computation of $Y OP X\[2\]$ cannot start until the value of $Y$ is ready; once you start the computation of $Y OP X\[2\]$, it will take another 7 cycles to get the final answer.

Due to the dependencies, there is no way to do it in less than 14 cycles. So, 14 cycles in the minimum number of cycles possible.

What about the lower bound $7+2(n-2)$? For $n=3$, we have $7+2(n-2)=7+2\times 1=9$. So, the lower bound says 9. That *is* a correct bound: the minimum *is* indeed $\ge 9$. To say that something is a lower bound means that the true total time is always at least as large as the lower bound.

So, $7+2(n-2)=9$ *is* a correct lower bound on the time taken for $n=3$. It just isn't the best possible lower bound, but it is *a* lower bound.

---

For general $n$, something similar happens. $7+2(n-2)$ is *a* lower bound. It's not a very good lower bound, and the actual time taken will usually be larger than $7+2(n-2)$. But, it certainly won't be less -- and that's all that we mean when we say that $7+2(n-2)$ is a lower bound.

How do we know that $7+2(n-2)$ is a lower bound? Well, obviously, we have to perform at least $n-1$ OP operations. After issuing each one, we have to wait 2 cycles before issuing the next one. Also, there is a latency of 7 cycles to wait for the result from the last one. Thus, we need at least $7+2(n-2)$ cycles in total, as explained in David Richerby's answer.

That's why $7+2(n-2)$ *is* a valid lower bound, even though it isn't the minimum number of cycles.
> 0 votes

# Answer
The attempt in the edited question is almost there. When you issue the instruction `OP`, you get the answer back seven cycles later. When you issue an `OP` instruction, you must wait two more cycles before issuing another. You need to issue $N-1$ `OP` instructions, so they're issued at times $0, 2, 4, \dots, 2(N-2)$, and the last one completes seven cycles after it's issued, so we get the required answer.

---

Having said that, the example in the question seems bad. Since `OP` is an instruction taking two arguments, it's unclear what `X[0] OP X[1] OP X[2]` even means. If it's supposed to mean `S := X[0] OP X[1]; S := S OP X[2];` then there are dependencies between the instructions. The second `OP` needs to know the value returned by the first, so it can't be issued until the first one has finished. If the instruction sequence is supposed to mean `X[0] OP X[1]; X[1] OP X[2]`, then it should just be written that way, or even just `OP; OP`, since the arguments are irrelevant.
> 1 votes

---
Tags: computer-architecture
---


# Question
Title: What classes of data structures can be made persistent?
**Persistent data structures** are immutable data structures. Operations on them return a new "copy" of the data structure, but altered by the operation; the old data structure remains unchanged though. Efficiency is generally accomplished by sharing some of the underlying data, and avoiding full copying of the data structure.

**Questions:**

> * Are there results about classes of data structures that can be made to be persistent (while keeping the same or very similar complexities)?
> * Can *all* data structures be made persistent (while keeping the same or very similar complexities)?
> * Are any data structures known to be unable to be made persistent (while keeping the same or very similar complexities)?

# Answer
> 26 votes
**Positive result: persistence does not cost too much.** One can show that every data structure can be made fully persistent with at most a $O(\lg n)$ slowdown.

Proof: You can take an array and make it persistent using standard data structures (e.g., a balanced binary tree; see the end of this answer for a bit more detail). This incurs a $O(\lg n)$ slowdown: each array access takes $O(\lg n)$ time with the persistent data structure, instead of $O(1)$ time for the non-persistent array. Now take any imperative algorithm whose running time in the RAM model is $O(f(n))$, where $n$ denotes the amount of memory used. Represent all of memory as one big array (with $n$ elements), and make it persistent using a persistent map. Each step of the imperative algorithm incurs at most a $O(\lg n)$ slowdown, so the total running time is $O(f(n) \lg n)$.

Apparently it is possible to do a bit better: apparently one can reduce the slowdown factor to $O(\lg \lg n)$ (expected, amortized time), using the techniques in the Demaine paper cited below -- but I am not familiar with the details of that work, so I cannot vouch for this myself. Thanks to jbapple for this observation.

---

**Negative result: you cannot avoid some slowdown, for some data structures.** To answer your third question, there exist data structures where it is known that making them persistence introduces some slowdown.

In particular, consider an array of $n$ elements. Without persistence, each array access takes $O(1)$ time (in the RAM model). With persistence, it has apparently been shown that there is no way to build a persistent array with $O(1)$ worst-case complexity for accessing a random element. In particular, there is apparently a lower bound showing that fully persistent arrays must have $\Omega(\lg \lg n)$ access time. This lower bound is asserted on p.3 of the following paper:

The lower bound is attributed to Mihai Patrascu, but there is no citation to a source that gives the details of the proof of this asserted lower bound.

---

**A rich area of research.** If we take an arbitrary data structure or algorithm, it's a bit of a delicate question whether you can make it persistent with at most $O(1)$ slowdown or not. I don't know of any general classification theorem. However, there is a lot of research into ways to make specific data structures persistent, in an efficient way.

There is also a strong connection with functional programming languages. In particular, every data structure that can be implemented in a purely functional way (with no mutations) is already a persistent data structure. (The converse is not necessarily the case, alas.) If you want to squint your eyes, you could take this as some weak sort of partial classification theorem: if it is implementable in a purely functional programming language with the same time bounds as in an imperative language, then there is a persistent data structure with the same time bounds as the non-persistent one. I realize this probably isn't what you were looking for -- it is mostly just a trivial re-phrasing of the situation.

---

**How to make a persistent array.** I won't try to describe the construction for how to build a fully persistent array with $O(\lg n)$ worst-case access time. However, the basic ideas are not too complicated, so I'll summarize the essence of the ideas.

The basic idea is that we can take any binary tree data structure, and make it persistent using a technique called *path copying*. Let's say we have a binary tree, and we want to modify the value in some leaf $\ell$. However, for persistence, we don't dare modify the value in that leaf in place. Instead, we make a copy of that leaf, and modify the value in the copy. Then, we make a copy of its parent, and change the appropriate child pointer in the copy to point to the new leaf. Continue in this way, cloning each node on the path from the root to the leaf. If we want to modify a leaf at depth $d$, this requires copying $d$ nodes.

If we have a balanced binary tree has $n$ nodes, then all leaves have depth $O(\lg n)$, so this operation on the binary tree takes $O(\lg n)$ time. There are some details I'm skipping -- to achieve $O(\lg n)$ worst-case time, we may need to rebalance the tree to ensure it remains balanced -- but this gives the gist of it.

You can find more explanations, with pretty pictures, at the following resources:

That will give you the main idea. There are extra details to take care of, but the details are out of scope for this question. Fortunately, this is all standard stuff, and there is lots of information available in the literature on how to build such data structures. Feel free to ask a separate question if the above resources aren't enough and you want more information about the details of building a persistent array data structure.

---
Tags: reference-request, data-structures, functional-programming, persistent-data-structure
---


# Question
Title: Determining interests from Twitter text using Latent Dirichlet Allocation
I would like to **determine interests or hobbies that people have given their Twitter timeline data**. Their timeline is their historical collection of tweets.

The result I am trying to achieve is to automatically label a user with a collection of interests such as:

* Finance
* Photography
* Android Development

**I have tried using a topic model, LDA, using an individuals tweets as the corpus but I am not so sure about the applicability of the results**. LDA gives a collection of terms associated with the topics it found. This requires some manual interpretation to distinguish what the interest is.

For example you might get some results from LDA like the following:

* \[Twitter, Java, time, work, day\]
* \[code, IPhone, mobile, look, job\]
* \[football, fantasy, team, pick, score\]

I can generally pick out the topics people are interested in here but its just the key word or topic identifier I am interested in not the other contextual terms like team, pick or score in the last example. Ideally I would like to transform these term-based results into something like the following interests:

* \[Twitter, Java\]
* \[IPhone, Mobile Development\]
* \[Fantasy Football\]

**I have considered how to do this using a supervised approach**. Given your categories of interest and using a bag-of-words model with a naive Bayes classifier the task would be to determine which category the topic terms belong to.

This requires labelled data for each category of interest which could be quite time consuming to create. **Is there a possible unsupervised learning approach that could work?**

I may have gone down the wrong path using topic models, if so, what existing textual research areas could help.

**Not looking for a complete solution to the problem, just any suggestions, references or links would be appreciated**.

# Answer
> 1 votes
Thanks for your comments, reformulating the question lead me to a different way of thinking about the problem.

Getting an interest category list is actually reasonably straightforward for broad level hobbies it is just the labelled training data that may be hard to produce.

I found this paper on unsupervised text classification and this is probably a better fit than topic models in this scenario. It uses a small number of keywords (average 3) per category and segmented sentences to produce training data for a naive Bayes classifier.

I think I will use this with some Twitter specific text pre-processing and some sentiment classification to see if the categories are spoken of in a positive light.

---
Tags: natural-language-processing
---


# Question
Title: Maximum number of states in minimized DFA from NFA with $n$ states
If an NFA with $n$ states is converted to an equivalent minimized DFA then what will be the maximum number of states in the DFA? Will it be $2^n$ or $2n$?

# Answer
> 3 votes
The maximum number of states is $2^n$. Conversion from NFA to DFA is done by subset construction and the number of states of the resulting DFA is in the worst case $2^n$. Minimization of the resulting DFA in the worst case might not reduce the number of states.

An example of this is automaton that accepts strings over $\Sigma = \\{0, 1\\}$ which have $1$ as the $n$th symbol from the end. Of course, $n$ is a concrete number. A NFA has states $q\_0...q\_n$ and the following transition function:

$$(q\_0, 0) \rightarrow \\{q\_0\\} \\;\\;\\;\\; (q\_0, 1) \rightarrow \\{q\_0, q\_1 \\}$$ $$(q\_i, 0) \rightarrow \\{q\_{i+1}\\} \\;\\;\\;\\; (q\_i, 1) \rightarrow \\{q\_{i+1}\\} \\;\\;\\; 1 \leq i \leq n-1$$

Intuitively, the corresponding DFA needs to remember last $n$ symbols since it does not know has it seen the end, which means there are $2^{n}$ states. For more details, I suggest looking into this book. It has a more detailed proof and generally covers these topics in thorough.

---
Tags: automata, finite-automata, nondeterminism
---


# Question
Title: Do Kernel-Mode Windows Services Considered Part of Kernel?
I learned that there are two types of services in Windows , one called -service- which is in user-mode , other is called -driver service / device driver\- which is in kernel-mode.

What I wonder is , do kernel-level services considered as a part of the kernel? If so , does writing kernel-mode services mean extending Operating System?

My lecturer accepts the definition of OS as , it is solely the Kernel. So I wonder if kernel-level services are included in his OS definition.

# Answer
> 2 votes
> Are kernel-level services considered as a part of the kernel?

That can be debated, but for me the answer is yes.

You might run into a purist who considers only the code from the manufacturer in the kernel to be part of the kernel and extensions as an add on the kernel. I would ask you instructor for his answer, you are the customer, right?

> If so , does writing kernel-mode services mean extending Operating System?

For me it surely does.

The easiest way to think of this is adding a device that requires installing a kernel mode device driver. Once the kernel mode device driver is installed all the code has access to the device driver in the same way all the code has access to the kernel. That is simplified but you should get the analogy.

---
Tags: operating-systems
---


# Question
Title: Difference between Computing Architecture and Platform in Computer Science
I was looking for an appropriate term to call my proposal. I knew it is either platform or architecture. But could not simply and clearly distinguish them in an academic manner. So, I searched the web and the literature and found few definitions on architecture and platform as follows that sound logical.

* Software Architecture: A set of system elements and relations associated with them \[reference: documenting software architecture: views and beyond\]
* Platform: A set of subsystems and technologies providing a coherent set of functionalities through interfaces and specified usage pattern that any subsystem that depends on the platform can use without concern of the detail of how the functionality provided by the platform is implemented.

However, still is it not clear what are the differences. I guess researchers often use these two terms interchangeably with marginal consideration on their differentiations. Looking at the definitions, I figured out that architecture likely specifies structural properties of systems and usually tries to describe the structure of a system and its consisting components and their relationship. Using architecture, developers cannot produce a system that works according to that architecture. However, platform is trying to specify structural and behavioural attribute of a system by describing its subsystems and their relationship. Platform also provides an abstract by which developers can create new software systems that rely upon the platform.

Is this interpretation accurate enough? One may argue that platform is prepared on top of an architecture and without architecture one may not be able to propose platform.

In your idea, what else are the differences and distinguishing lines between these two terms?

# Answer
> 7 votes
Architecture generally refers to a design-level structure or organization for an entire system.

Platform generally refers to something (an operating system, a library, a programming language, a programming environment) which you can build other things on.

# Answer
> 2 votes
Disclaimer: The folowing answer is just my opinion. It's not necceseraly 100% true. Sorry for bad english.

When we say "architecture", we primarily mean computer architecture with address bits, memory, we define commands of processor.

Examples of macro definitions of windows architecture:

```
_M_IA64 Intel Itanium platform
_M_IX86 x86 platform
_M_X64  x64 platform

```

(Yes, "platform" and "architecture" marginally are used interchangeably)

When we say "platform" we mean computer platfrom which deals with system software (eg. operating systems). Examples of macro definitions of windows platforms:

```
_WIN64  A 64-bit platform.
_WIN32  A 32-bit platform. This value is also defined by the 64-bit compiler for backward compatibility.
_WIN16  A 16-bit platform

```

So architecture is lower level concept than platform. On top of that architecture we implement platform (eg. Win32 or POSIX). And on top of platform, you build an applications.

---
Tags: terminology, software-engineering
---


# Question
Title: Are all the NP-complete problems have strong reductions?
Are all the NP-complete problems have strong reductions? If I find a polynomial solution to one **NP-complete** problem, can I state that `P = NP`?

# Answer
You don't seem to have a correct grasp of the concept of NP-completeness. Every NP complete problem has a reduction to every other NP complete problem. That is, there is a poly-time reduction *from* SAT *to* HAMPATH.

Thus, if you have a polynomial solution for HAMPATH, you can solve any case of SAT in polynomial time, so P=NP.
> 10 votes

---
Tags: p-vs-np
---


# Question
Title: Valid-invalid bit in a process page table
**Valid-invalid** bit is used to indicate whether a page in a process’s page table is valid or not. Why is it needed?

Does that mean that each page table has a certain minimum size, i.e. it can accommodate minimum of n references to pages and if the number of pages being referenced by the process is less than n, then this bit is required to tell that only few entries are valid in the page table?

If the page table is built and populated dynamically, then the page table will only have as many entries as needed by process and there will no need for this bit, as all entries will be valid.

Other tags are **page-table**, **valid-invalid bit**

# Answer
> 2 votes
Typically the page table is a tree of fixed size pages. So each node of the page table contains a fixed number of entries. Here's the picture of a 32-bit x86 multi-level page table from Wikipedia:

Each page on x86 is $2^{12}=4096$ bytes. Each page table entry is 4 bytes = 32 bits, and contains a pointer to the beginning of another page. Each page table page contains exactly $2^{10}=1024$ page table entries. Since the pages are aligned we know that the bottom 12 bits of the pointer would all be zeros, so we use those bits for status bits (including the invalid bit). The invalid bit is necessary if you want to make the table sparse in any way.

---
Tags: operating-systems, memory-access
---


# Question
Title: Does this pushdown automaton describe the language {$a^n b^n c^i \in \{a,b,c\}^*\ |\ n \ge 0,i\ge 0$}?
I've just been learning about pushdown automata and I'm trying to create one that describe the following language:

{$a^n b^n c^i \in \\{a,b,c\\}^\*\ |\ n \ge 0,i\ge 0$}

What I have is the following:

(state, symbol, top of stack), (next state, what goes to stack).

$(s,$e$,$e$),(f,$e$)$

$(s,a,$e$),(s,d)$

$(f,b,d),(f,$e$)$

$(f,c,$e$),(f,$e$)$

Where $s$ is the starting state, $f$ is the final state and e is the empty word.

Do I have the right idea? My worry is sending the automata to the final state while there are still entries in the stack - is that allowed?

# Answer
> 1 votes
As I am (not) yet certain of the PDA model you are using, I will not comment on correctness of your construction, but I have a general remark on PDA.

There happen to be two generic ways of defining languages for PDA: by final state and by empty stack. Let a configuration be a description of the PDA, its (yet unprocessed) tape, state, stack.

Using *final state acceptance* means that we accept any word that leads from the initial configuration of the automaton to a configuration that is in a final state (no matter what is the contents of the stack) after reading the complete input. Similarly, *empty stack acceptance* means that we accept any word that leads from the initial configuration of the automaton to a configuration in which the stack is empty (no matter what is the state) after reading the complete input.

By standard constructions one is able to change a PDA into an equivalent one using the other acceptance type. so for practical reasons the two notions are interchangeable. When dealing with technicalities (in case of deterministic automata for instance) the acceptance type *does* matter.

In conclusion: if you are using final state acceptance, then do not worry about remaining stack symbols.

---
Tags: pushdown-automata
---


# Question
Title: How does BIRCH (Balanced Iterative Reduction Using hierarchical) CF Tree insertion algorithm work?
I am studying Cluster Analysis and I came across BIRCH (Balanced Iterative Reduction Using hierarchical) http://en.wikipedia.org/wiki/BIRCH\_(data\_clustering) CF Tree insertion algorithm. I am confused what does branching factor(B), threshold for diameter of cluster in a leaf(T) means and in general how the algorithm works. It will be of immense help if someone can please explain it using an example. Thanks in advance.

# Answer
Since you mentioned you haven't read it yet, I suggest you start by reading the original paper (which was linked to from the Wikipedia page). For research-level contributions, that's often a helpful place to start, if you're having trouble finding a place to learn more.

Wikipedia also links to some slides on BIRCH. That might be worth reading first to get an overview for what they're trying to achieve, before reading the original paper -- but you'll still need to read the original paper. The slides are not a substitute for the paper, especially if you want to know the specifics of the algorithm.

You should not expect a textbook or slides to give this level of details. They might try to give you the general idea or the overall intuition, but if you want to know the full details, it's likely that you'll need to read the original paper. It's not unusual to find that you need to go to the primary sources, for recent research like this.
> 1 votes

---
Tags: data-mining
---


title: Recursive Universal Turing Machines

text:
# Question
Title: Recursive Universal Turing Machines
Let $U$ be a universal Turing machine that on input $\<M,w\>$ simulates a Turing machine $M$ on input $w$. I have a question about what would happen if $U$ "operated" on itself.

That is, what happens when we consider the input $\<U, \<M,w\>\>$?

Or what about the input $\<U, \<U, \<M,w\>\>\>$?

# Answer
If we give the input $\<U, \<M,w\>\>$ to the Turing machine U, it will simulate the Turing machine U on input $\<M,w\>$. The behavior of the simulated machine U on input $\<M,w\>$ is to simulate the Turing machine $M$ on input $w$. So it seems like the behavior would still be a Turing machine that simulates $M$ on input $w$. At least two questions need further clarification:

* How is the input $w$ encoded? If we have a requirement that only input where "$\<$" and "$\>$" are "perfectly matched" is allowed, then we can just copy the input "w" unmodified between $\<M,$ and $\>$. This is the strategy used by Tcl, which can be surprising if you are not used to it. Otherwise, you have to encode the input "$w$" suitably, which can mean that you have to escape "$\<$" and "$\>$", as well as the escape character itself. In this case, the "$w$" in $\<U,\<U,\<M,w\>\>\>$ is quite different from "$w$" itself, because it has been encoded multiple times. For example the escape character "\\" might have turned into "\\\\\\\\\".
* What exactly do we mean by "simulate"? The most important aspects of a simulation of a Turing machine is whether it halts or not. If the Turing machine M halts, it is (or can be) also important which output it leaves on its tape. If the machine M doesn't halt, we need to be careful how to define the output of the machine. For simplicity, let's assume that either the machine has a dedicated output tape, or that we don't care for the output in case the machine never halts. The output should never be encoded like the input, but directly match the original output.

What about the efficiency of the simulation? A good simulation would have only a constant offset in memory consumption and a logarithmic factor (logarithmic in the input to $U$) in runtime (-\>multi-tape Turing machine is assumed here). Both properties seem to be conserved by applying $U$ to itself, so you still have an efficient simulation of $M$ on input $w$ if you apply $U$ (repeatedly) to itself.
> 3 votes

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


# Question
Title: Context-free Language: deciding z string
Let $L = \\{ x \in \\{a,b\\}\* | \ |x|\_a \leq |x|\_b^2\\}$

I know this is a NOT context free language. How can i choose the correct $z=uvwxy$ and try to apply the Pumping Lemma?

I think that $z=(a^n b)^n$ it's wrong, cause it's part of the language only if $n=0,1$

$z=(ab^n)^n$

should be fine.

Then the relatives substring $vwx$ should be:

$vwx = ab$

$vwx = b^k$

$vwx = ab^k$

Where am I going wrong? How can I proceed?

# Answer
jmite explained where you are going wrong. You have misunderstood what the pumping lemma says. The pumping lemma says that if $L$ is a CFL, then every sufficiently long string can be pumped. However you said that $L$ is **not** a CFL. As a result, the pumping lemma promises nothing. If you pick any particular string, it might be pumpable, or it might not.

In other words, you are making a converse error. "If P then Q" does not mean "If not(P) then not(Q)". The pumping lemma says "if P then Q" (if $L$ is a CFL, then long strings are pumpable). You have observed "not(P)" ($L$ is not a CFL). You cannot infer "not(Q)" from this information (you cannot deduce that long strings are not pumpable; in reality, they might be, or they might not be).
> 1 votes

---
Tags: context-free, pumping-lemma
---


title: How does a TLB and data cache work?

text:
# Question
Title: How does a TLB and data cache work?
I'm trying to study for an exam and I realized I'm confused about how the TLB and data cache work.

I understand that the TLB is essentially a cache of most recently used physical addresses. However, I was looking at a diagram in my textbook (shown below), and I don't understand what's going on in it. It suddenly splits up the physical address and uses it to index the cache, I guess. But why is it showing the cache and data separately? and why is the byte offset just left floating? I'm pretty sure the cache is supposed to store data as well. I don't think its sole purpose is to determine whether or not there's a hit or miss inside of it.

I apologize for my ignorance in advance, but the book barely covers TLB's (it's like a little more than a page) and it doesn't do a very good job at explaining the relationship between a TLB and cache.

# Answer
I think I see your confusion. The TLB and the data cache are two separate mechanisms. They are both caches of a sort, but they cache different things:

* The TLB is a cache for the virtual address to physical address lookup. The page tables provide a way to map virtualaddress $\mapsto$ physicaladdress, by looking up the virtual address in the page tables. However, doing the lookup in the page tables is slow (it involves 2-3 memory loads). If the processor had to do this lookup every time any instruction accessed memory, this would cause a substantial slowdown.

Therefore, the TLB acts as a dedicated cache for this lookup. The TLB has a few TLB entries, where each TLB entry contains both a virtual address and its corresponding physical address.

The TLB lets the processor very quickly convert virtual addresses to physical addresses. If an instruction asks the processor to do some memory operation on a (virtual) address, the processor first checks to see whether the TLB contains an entry for that virtual address. If it does, then that's called a "cache hit" for the TLB lookup, and since the TLB entry also contains the translated physical address, the processor immediately knows what physical address to use. If it doesn't, that's a cache miss for the TLB lookup, and the processor has to laboriously do the virtual-to-physical conversion by walking the page table. (Once it finishes doing that conversion, it adds an entry to the TLB so that future conversions of that virtual address will happen much more quickly.)
* The data cache is a cache for the contents of memory. Main memory lets you specify a physical address and read the value at that physical address. However, main memory is slow. If we had to go to main memory every time we wanted to do any memory operation, our processor would be very slow.

Therefore, the data cache acts as a dedicated cache for memory reads. The data cache has some cache entries, where each cache entry contains a physical address and the value of memory at that address.

The data cache lets the processor very quickly read from memory. When the processor wants to read memory at some (physical) address, it first checks the data cache to see whether it contains a cache entry for that address. If it does, this is known as a "cache hit" (in the data cache), and the processor can immediately use the data value stored in that cache entry, without needing to contact main memory. If it doesn't, then this is a "cache miss" (for the data cache), and the processor needs to go to main memory. (After the processor receives the value at that address from main memory, it adds a cache entry to the data cache so that attempts to read that same address will hit in the data cache.)

They are both caches, but they serve a different purpose. The processor uses both for each memory operation: it first uses the TLB to convert from virtual address to physical address, then it checks the data cache to speed up the process of reading the value stored in memory at that address.

For more details, you can read the Wikipedia article on TLBs. If you do a search, there is a lot of other information available on TLBs and data caches. I suggest searching for "TLB" and for "L1 cache" or "L2 cache" (the latter 2 are kinds of data caches).

(For future reference: we expect you to do some research on your question before asking here, and to check standard Internet sources. If the answer can be found in Wikipedia, you haven't done enough research on your own. You might have had better luck if you'd checked Internet sources for information on how TLBs before asking here. See also How much research effort is expected of Stack Overflow users?. So, take the opportunity to use this as a lesson for how you can improve your own research skills -- something that will be valuable to you throughout your career.)
> 23 votes

---
Tags: computer-architecture, cpu-cache, virtual-memory
---


# Question
Title: Showing that graph of spanning trees are connected
Suppose we have a graph $H$, where each vertex represents a spanning tree of another graph $G$.

We create an edge between 2 vertices in $H$ if $ST\_1$ (spanning tree) contains exactly one edge not in $ST\_2$ (and vice versa).

How do we show that $H$ is connected?

# Answer
Use induction on the number of edges and vertices in $G$. Fix some edge $e$ of $G$. If $S$ and $T$ are two different spanning trees that do not use $e$, apply the induction hypothesis on the graph $G\setminus e$. If both use $e$, apply the inductive hypothesis to the contracted graph $G/e$. If only one does, w.l.o.g., $S$, replace $T$ by $T'$, obtained by adding $e$ to $T$ and removing any edge in the (unique) cycle in $T+e$. Either $T'$ is $S$, or we are back in a previous case.
> 1 votes

# Answer
So two vertices in $H$ are connected by an edge if their corresponding spanning trees $ST\_1$ and $ST\_2$ differ in exactly two edges $e \in ST\_1$ and $e' \in ST\_2$, or equivalently, if by removing $e$ from $ST\_1$ and adding $e'$ to it, we get $ST\_2$.

Therefore, a path in $H$ corresponds to a sequence of these remove and add operations. You need to show that for any two spanning trees $ST\_i$ and $ST\_j$, with any number of different edges you can obtain $ST\_j$ by applying these operations iteratively to $ST\_i$. More specifically, you need to prove that for any edge that is present only in $ST\_i$, if we remove that edge, there is another edge only present in $ST\_j$ that we can add to $ST\_i$ such that it remains a tree.
> 0 votes

---
Tags: graphs, spanning-trees
---


# Question
Title: Chernoff bounds and Monte Carlo algorithms
One of Wikipedia examples of use of Chernoff bounds is the one where an algorithm $A$ computes the correct value of function $f$ with probability $p \> 1/2$. Basically, Chernoff bounds are used to bound the error probability of $A$ using repeated calls to $A$ and majority agreement.

I don't understand how, to be frank. It would be nice if somebody could break it down piece by piece. Moreover, does it matter whether $A$ is a decision algorithm or can return more values? How are Chernoff bounds in general used for Monte Carlo algorithms?

# Answer
> 7 votes
Let's suppose that we have a polynomial time randomized algorithm $A$ for a decision problem $\Pi$ with the property that $$ \mathrm{Pr}\[A \text{ is right}\] \> 1/2 $$ for all inputs. (In particular, independent of the input length $n$.)

We can use Chernoff bounds to show something stronger, namely that for any fixed $c$, there is a polynomial time, randomized algorithm for $\Pi$ that is correct with probability at least $1-n^{-c}$.

The algorithm is very simple: On an input of length $n$, we run $A$ a polynomial number of times $N$ (to be determined below) and then report the majority answer. Call this algorithm $A'$.

What we need is a bound on $$ \mathrm{Pr}\[A' \text{ is wrong}\] $$ in terms of the number of repetitions $N$. The hypothesis about $A$ implies that there is an $\epsilon \> 0$ such that $$ \mathrm{Pr}\[A \text{ is right}\] \ge 1/2 + \epsilon $$ Since the $N$ runs of $A$ are independent, for any $k\in \[N\]$ we have $$ \mathrm{Pr}\[k \text{ of } N \text{ runs of } A \text{ are right}\]\ge Pr\[X = k\] $$ where $X$ is a binomial random variable with parameters $N$ and $1/2+\epsilon$. Since the algorithm $A'$ is wrong exactly when at most $N/2$ of the runs of $A$ are right, we obtain an upper bound on the failure probability by a "tail estimate" bounding $$ \mathrm{Pr}\[X \le N/2\] $$ This is a prototypical time to use a Chernoff bound, since a binomial r.v. is the sum of $N$ independent random variables. One instance of the Chernoff bound says that if $Y$ is the sum of $N$ independent r.v.'s with support in $\[0,1\]$ and $t \> 0$, then $$ \mathrm{Pr}\[Y \< E\[Y\] - t\] \le e^{-2t^2/N} $$ Thus, since $E\[X\] = N/2 + N\epsilon$, we take $t = N\epsilon$ to obtain $$ \mathrm{Pr}\[A' \text{ is wrong}\]\le e^{-2\epsilon^2 N} $$ So we can take $N = (1/2)\epsilon^{-2}c\log n$, and we get the claimed error probability for $A'$.

---
Tags: randomized-algorithms, randomness, chernoff-bounds
---