# Question
Title: The purpose of grey node in graph depth-first search
In many implementations of depth-first search that I saw (for example: here), the code distinguish between a grey vertex (discovered, but not all of its neighbours was visited) and a black vertex (discovered and all its neighbours was visited). What is the purpose of this distinction? It seems that DFS algorithm will never visit a visited vertex regardless of whether it's grey or black.

# Answer
> 35 votes
When doing a DFS, any node is in one of three states - before being visited, during recursively visiting its descendants, and after all its descendants have been visited (returning to its parent, i.e., wrap-up phase). The three colors correspond to each of the three states. One of the reasons for mentioning colors and time of visit and return is to explicitly make these distinctions for better understanding.

Of course, there are actual uses of these colors. Consider a directed graph $G$. Suppose you want to check $G$ for the existence of cycles. In an undirected graph, if the node under consideration has a black or grey neighbor, it indicates a cycle (and the DFS does not visit it as you mention). However, in case of a *directed* graph, a black neighbor does not mean a cycle. For example, consider a graph with 3 vertices - $A, B,$ and $C$, with directed edges as $A \to B$, $B \to C$, $A \to C$. Suppose the DFS starts at $A$, then visits $B$, then $C$. When it has returned to $A$, it then checks that $C$ has already been visited and is black. But there is no cycle in the graph.

In a directed graph, a cycle is present if and only if a node is seen again before all its descendants have been visited. In other words, if a node has a neighbor which is grey, then there is a cycle (and not when the neighbor is black). A grey node means we are currently exploring its descendants - and if one such descendant has an edge to this grey node, then there is a cycle. So, for cycle detection in directed graphs, you need to have 3 colors. There could be other examples too, but you should get the idea.

# Answer
> 2 votes
It is an exercise in CLRS that you can remove the gray or black color and the algorithm works fine with just two colors, in other words it is not really needed. The main goal of marking vertices is to make sure we don't run into an infinite loop by repeatedly visiting already visited vertices.

The reason for using 3 colors in DFS algorithm is mainly pedagogical: it is conceptually clearer, it helps students see what is going on during the execution for each node.

# Answer
> 2 votes
In DFS we classify edges as forward-edge, back-edge , cross-edge and tree-edge.

We use 3 colors to classify the edges. and these colors represents the state of the vertex i.e v. white : the vertex v is not yet discovered.

gray : v has already been discovered , but all the vertices that are reachable from v are not yet discovered. so the vertex v is still in the stack.

black: v is already pop out of stack.discovered and finished.

In doing the DFS if you encounter a gray vertex through edge e then it's a back edge. If you encounter a black vertex through edge e then it's a cross edge/forward edge. if you encounter white vertex then you will call DFS recursively.

# Answer
> 0 votes
Grey vertex states that you have visited that node and moved on to one of its neighbors in some order, but there might be more neighboring vertices to that node. It while be useful while backtracking for exploring unvisited vertices.

Let's say **Vertex A has two neighbors B and C and B has one neighbor D**.

start at vertex A which is white color and **make it grey** and traverse to its neighbor.

Lets say by choosing alphabetical order it **visits vertex B** which is in white color and marks as grey.

Then visits **D of white -\> grey D** -\> no more neighbors. hence marks **D-\>black**.

Now, **backtracks** to B in Grey and no more nieghbors. Hence marks **B-\> black**.

AGain backtracks A in grey and visits c mark to **c-\>Grey** no more neighbors marks C as black

finally, back to A and marks **vertex A as black** as there are no more white vertices and all as black.

# Answer
> 0 votes
Here's a pairwise consistency example. Suppose you're checking a directed graph for pairwise consistency. In other words, you're checking that there are no cases in which, say, A is greater than B is greater than C is greater than A. (Edge direction indicates "is greater than.")

Consider a graph with two paths that rejoin at D:
A -\> B -\> C -\> D
A -\> E -\> F -\> D
Traversing the first path turns D grey when visited, and black when it's determined to have no children. Traversal afterward of the second path discovers D to be black, which would not be an indication of a cycle or of a pairwise inconsistency. (For example, C=5, F=6, D=2.)

Consider a different graph, with the following path:
A -\> B -\> C -\> D -\> B
When A discovers B, it turns B grey. B will thus be grey when D discovers it. Being grey would be interpreted as indication of a cycle and of pairwise inconsistency somewhere along the path.

Takeaway: in a graph in which edges take one and only one direction, discovering grey means a cycle, discovering black does not

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


# Question
Title: Increase-key and decrease-key in a binary min-heap
In many discussions of binary heap, normally only decrease-key is listed as supported operation for a min-heap. For example, CLR chapter 6.1 and this wikipedia page. Why isn't increase key normally listed for min-heap? I imagine it is possible to do that in O(height) by iteratively swapping the increased element (x) with the minimum of its children, until none of its children is bigger than x.

e.g.

```
IncreaseKey(int pos, int newValue)
{
   heap[pos] = newValue;
   while(left(pos) < heap.Length)
   {
      int smallest = left(pos);
      if(heap[right(pos)] < heap[left(pos)])
         smallest = right(pos);
      if(heap[pos] < heap[smallest])
      {
         swap(smallest, pos);
         pos= smallest;
      }
      else return;
   }
}

```

Is the above correct? If not, why? If yes, why isn't increase key listed for min-heap?

# Answer
The reason that your operation is not listed, is that one is not simply interested in all operations that can be easily implemented using a certain data structure, but rather the other way. Given a set of operations, what is the most efficient way (in terms of space and time) to implement these operations. (But I add more to this later)

Binary heaps implement the abstract data structure priority queue, which asks for operations is\_empty, add\_element (a key with its priority), find\_min, and delete\_min. More advanced queues also allow one to decrease the priority of the key (in a min\_heap) or even increase it. In fact, you have given an implementation.

Two remarks. Your operation is used in the heapify function, that efficiently constructs a heap from an array. In heapify your operation is repeated (starting from the last key).

Then, most importantly, your code uses the position of the node. For the pure data structure priority queue that is cheating. That data structure asks to perform a certain operation given a key. So in order to decrease or increase the priority of an element, you will first have to locate it. I think that is the main reason it is not listed.
> 8 votes

# Answer
The algorithm you suggest is simply heapify. And indeed - if you increase the value of an element in a min-heap, and then heapify its subtree, then you will end up with a legal min-heap.
> 7 votes

# Answer
I think that the first thing to consider is what is a supported operation?

Does "inserting a value with a specific, fixed key" (e.g. for keys taken from the integer realm, inserting with key = 3) correspond to a supported operation for the min heap?

No, because that operation can be trivially implemented with more general supported operations. Likewise, inserting 2 elements at once can be done with the exisiting `insert` operation.

On the other hand, the `insert` operation cannot be defined otherwise than by exposing implementation details. It is pretty much the same for the operations listed on the wikipedia page, `heapify` excepted, which could probably be implemented by a sequence of `insert`.

In other words, there are elementary operations provided on the type, which are tightly bound to the implementation details for them to be performing well, and there are other operations, which do not abide to that rule, and thus may be implemented as a combinations of the canonical ones.

With that definition in mind, do you think that increase-key could be implemented with other supported operations exlusively, without a loss of performance? If so, then it is not a supported operation by the above definition, otherwise, you may well be right.

Arguably, the definition of a supported operation I provide is mine, as far as I know. It is not formal, and thus subject to discussion (although it seems pretty clear to me). However, I would be glad if someone could provide a source which clearly and unambiguously define what a supported operation is for datatypes, or at least define it in better terms than mine (is that definition given in CLR? I don't have a copy).

My second point will be on how we define a priority queue (which is the raison d'être of binary heaps). Is the `increase_key` a necessary operation for that datatype, i.e. for its proper use?

As you can see my angle is all about definitions. I do not really provide an answer to your questions, merely some pointers, so enhancements are welcome.
> 0 votes

# Answer
The decrease key is in fact mentioned as an exercise 6.5-4 in CLR. Here is why I think it was not presented in the chapter itself: It can be constructed simply by reusing the `MAX-HEAPIFY(A, i)` i.e. you will only need to compare the element to its children not its parent(since you decreased the key); The comparison to parent is only needed if you increase the key's value and that is a *different* algorithm ,`MAX-HEAP-INCREASE-KEY(A, x, k)`.

So in short they gave you two algorithm to fix the heap; Algo 1 fixes the heap sub tree by looking at children; Algo 2 fixes the heap subtree by looking at the parent. All the other algorithms can be built using those.
> 0 votes

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


title: When to use DFS and when use BFS?

text:
# Question
Title: When to use DFS and when use BFS?
Preparing for an interview.

I see two cases where each one is specially suited

BFS: When you need to find shortest path between vertices (if one exists).

DFS: If you need to find cycles in a directed graph:

Uses-case where both can be used: Finding cycle in undirected graph, Is there a path from one vertex to another

Are there any other specialized or common cases?

In general DFS is considered to be simpler (though if graph is very deep, I am assuming we can have a stack overflow due to excessive recursion). So, if both can be used for a use-case, use DFS?

# Answer
Shortest cycle: BFS has the nice property that, if started from u, the first time the BFS finds u is when the shortest cycle that includes u has been completed.

Email infections: Determining whether a computer is infected from looking at the email metadata, BFS and DFS are about the same, since you don't know if that worker was infected early, late, or not at all. The trick in that problem is to set up the graph right so a search can be done with as few conditionals as possible.
> 0 votes

# Answer
Bfs and Dfs both are good state space search algorithms. If search space is infinite then its good to use Bfs because dfs can be lost in infinite space and will not return any result. Also, Bfs searches result in neighbors and then go neighbor by neighbor on other hand dfs searches for answer branch by branch. If you search key is near starting point then go for bfs
> -2 votes

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


# Question
Title: Modelling a basic sequential circuit as a transition system?
I'm going through Dr Joost-Pieter Katoen's slides and stumbled upon this:

For some reason I can't quite make out how the transition system relates to the sequential circuit. If I had a question for instance that asked me to convert the circuit into a TS, what steps should I take to approach it (using this one as an example).

Grateful for any help.

# Answer
> How does the transition system (denoted by $\texttt{TS}$) relate to the sequential circuit (denoted by $\texttt{SC}$)?

* The states of $\texttt{TS}$ are all possible combinations of values of variable $x$ and register $r$ (*no output variable* $y$) in $\texttt{SC}$.
* The label of each state in $\texttt{TS}$ consists of all the variables (including the register) which are evaluated true given the valuations in $\texttt{SC}$.
For example, $\\{x, r, y \\}$ for state $(x = 1, r = 1)$ means that all variables are true according to $\lambda\_y = \lnot (x \oplus r)$ and $\delta\_r = x \lor r$ given $x = 1, r = 1$.
* The transitions (arcs with arrow) between states in $\texttt{TS}$ result from the functions $\lambda\_y$ and $\delta\_r$.
For example, $(x = 0,r = 1) \to (x = 0,r = 1)$ if the next input bit equals 0.

---

For more details and a general recipe for modeling sequential hardware circuits as transition systems, please refer to the book "Principles of Model Checking" (Section 2.1.2) by Christel Baier and Joost-Pieter Katoen. The MIT Press.
> 5 votes

# Answer
Exercise 2.1. Consider the following two sequential hardware circuits: r1 AND x1 r2 OR x2 OR AND NOT y1 y2 Questions: (a) Give the transition systems of both hardware circuits. (b) Determine the reachable part of the transition system of the synchronous product of these transition systems. Assume that the initial values of the registers are r1=0 and r2=1.
> 0 votes

---
Tags: model-checking, software-verification, transition-systems
---


# Question
Title: Given a language L how can I derive its Boolean formula?
Let: be given by

Compute Boolean formulas for the following:

This is part of my coursework; I have the answers but can't understand them. I want to develop some intuition on how I can solve these or a general framework on how I can approach them.

Some guidance on resources is also appreciated. And sorry I couldn't figure out how to format it in Latex which worked over here.

# Answer
> 2 votes
I'll just consider $\text{MOD}^1\_{0,3}$, the other ones are similar. I'm assuming that you want a boolean formula $\phi$ such that $\text{MOD}^1\_{0,3}(x\_1, \dots, x\_n) = 1 \iff \phi(x\_1, \dots, x\_n) \text{ is true}$.

Note that $\text{MOD}^1\_{0,3}(x)$ is true if and only if the number of variables set to $1$ is a multiple of $3$. A first "natural" approach to find a possible $\phi$ is that of explicitly considering all variable assignments with that property and or-ing them together.

The resulting formula wold be: $$ \bigvee\_{k=0,\dots,\lfloor n/3 \rfloor} \bigvee\_{S \in \binom{\\{1, \dots, n\\}}{3k}} \left(\bigwedge\_{i \in S} x\_i \wedge \bigwedge\_{i \in \\{1, \dots, n\\} \setminus S} \overline{x}\_i \right). $$

While this works, this formula has exponentially many conjunctive clauses, each of which has $n$ literals.

A second idea is that of examining one input variable at a time and keeping track of the remainder of the division between the number of true variables encountered so far and $3$. To this aim we introduce $2$ new variables $y\_i, z\_i$ for each $i = 0,\dots,n$ where if we interpret $y\_i z\_i$ as a binary number, it will be exactly $\left( \sum\_{j=1}^i x\_j \right) \bmod 3$.

The formula will be a conjunction of sub-formulas.

* To ensure that $y\_0=z\_0 = 0$ we can use the sub-formula $\overline{y}\_0 \wedge \overline{z}\_0$.
* To correctly compute $y\_i$ from $x\_i, y\_{i-1}, z\_{i-1}$ (for $i = 1, \dots, n$) we can can write down a truth table to figure out that $y\_i$ should be true if and only if the formula $\mathcal{Y}\_i = (\overline{y}\_{i-1} \wedge z\_{i-1} \wedge x\_i) \vee (y\_{i-1} \wedge \overline{z}\_{i-1} \wedge x\_i)$ is true. Using the equivalence between $a \implies b$ and $(\overline{a} \vee b)$ we obtain the sub-formula $(\overline{\mathcal{Y}}\_i \vee y\_i) \wedge(\mathcal{Y}\_i \vee \overline{y}\_i)$.
* To correctly compute $z\_i$ from $x\_i, y\_{i-1}, z\_{i-1}$ (for $i = 1, \dots, n$) we can use a similar reasoning to obtain the sub-formula $(\overline{\mathcal{Z}}\_i \vee z\_i) \wedge(\mathcal{Z}\_i \vee \overline{z}\_i)$, where $\mathcal{Z}\_i = (\overline{y}\_{i-1} \wedge \overline{z}\_{i-1} \wedge x\_i) \vee (\overline{y}\_{i-1} \wedge z\_{i-1} \wedge \overline{x}\_i)$.
* Finally, we need to check that $y\_n$ and $z\_n$ encode $0$ (i.e., $\sum\_{j=1}^i x\_j$ is a multiple of $3$). We can do so by using the sub-formula: $\overline{y}\_n \wedge \overline{z}\_n$.

Notice that, for each $i=0, \dots, n$, we used a constant number of clauses each with constant-many literals. Overall, $\phi$ has $\Theta(n)$ clauses with $\Theta(1)$ literals each.

---
Tags: complexity-theory, circuits
---


# Question
Title: Is Partition Problem with non-integer input NP-complete?
The Partition Problem supposes that we have a set $S=\\{s\_{i} \in \mathbb{R^{+}}\\}\_{i=1}^{n}$, is there a subset $T$ such that $\sum\_{s \in T} s = \sum\_{s \notin T}s$?

I have read a lot of proofs using the Subset Sum problem: Given an **integer** set $S$ and an **integer** t, does there exist a subset $U$ of $S$ such that $\sum\_{s \in U}s = t$? My problem is that most of them does not consider that the partition problem does not require the inputs to be integers, and a lot of them transform the input $S$ of the Subset Sum problem to $S\cup \\{ \text{some elements} \\}$ in the Partition Problem. If the input to the partition problem is non-integer, or, worse, irrational, I do not think this method works.

I have tried to reduce the partition problem to subset sum problem, by transforming the input $S$(which could be irrational numbers) to $S^{\prime} = \\{ 2\lceil s\_{i} \rceil \\}$ and $t = \sum\_{i} \lceil s\_{i} \rceil$. Besides, I have also tried a few other similar ways including considering the floor function. However, whichever I tried, I could not prove that partition problem has a solution on $S$ if and only if the subset sum problem has a solution on $(S^{\prime},t)$. I do not find any contradiction if the subset sum problem has a solution on $(S^{\prime},t)$ and the partition problem does not have a solution on $S$, and vice versa. It sort of makes sense to me because having the result in integer subset sum problem could hardly have any implications on the non-integer partition problem.

Would anyone have any hints on how to prove the non-integer version of the Partition Problem is NP-complete by reducing it to the Subset Sum Problem?

# Answer
> 1 votes
This paper, On Strong NP-Completeness of Rational Problems, proves that partition problem is strongly NP-complete when all input numbers are rational numbers.

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


# Question
Title: Detecting if an edge is "inside" a polygon?
I have computed a constrained triangulation of a set of points. The constraint happens to be a closed polygon.

The objective is to detect all edges which are inside the polygon, that is, an edge where both endpoints are points in the polygon and for which all interior points are inside the area of the polygon.

A hacky way to do it is to compute the winding number for the midpoint of the edge and test if it is inside the polygon. But this is very brute forcy. I am wondering if there is a better way.

# Answer
To find all the edges inside a polygonal constraint *inside* of a larger constrained triangulation, You can do the following:

1. Find a single triangle inside the polygonal constraint
2. Use flood fill to find all triangles inside the polygonal constraint
3. Put all edges of these triangles into a set
4. Remove the polygonal constraint edges from the set

## Finding the First Triangle

To find the first triangle inside of the polygonal constraint, You could simply take one edge of the polygon $(a,b)$ and find the triangle $(a,b,c)$, provided the polygonal constraint has the same orientation as the triangles.
> 3 votes

# Answer
If you already have a constrained triangulation, to test if it contains the line segment $(a,b)$, You can do the following:

1. Find the triangle $(p,q,r)$ that contains $a$. If it does not exist, return false
2. If $(p,q,r)$ contains b, return $true$
3. Find the edge $(s,t) \in \left\\{(p,q), (q,r), (r,p)\right\\}$ which intersects $(a,b)$
4. If a neighboring triangle $(t,s,u)$ does not exist return $false$
5. Set $(p,q,r) \leftarrow (t,s,u)$ and go to **2.**

Step **4.** basically tests if an edge exits a border.

## Finding The Triangle

In order to find the triangle that contains $a$ You *could* build some BVH with all the triangles and in $\mathcal{O}(n\*\log(n))$ and find a triangle in $\mathcal{O}(\log(n))$. But that may not be as fast in practice as in theory.

Another way is to start at some triangle and then walk along the mesh towards $a$ using the A\* algorithm. If You sort the tested edges according to some space-filling curve order, and You always start with the triangle You've last looked at, You may even find the next triangle in amortized $O(1)$ time in practice.
> 4 votes

---
Tags: graphs, computational-geometry, discrete-mathematics, graphics
---


# Question
Title: What else measures are used to compare algorithm efficiency apart from Time and Space complexities?
While *Time Complexity* is the measure of how an algorithm scales with respect to input size, *Space Complexity* on the other hand measures how much the memory scales as input changes.

I see programmers pre-dominantly using these 2 metrics but are there any other generic measures/metrics for comparing the efficiency of 2 or more algorithms?

# Answer
> 6 votes
When it comes to the numerical methods used in science and engineering, one important measure is numerical accuracy.

---
Tags: algorithms, time-complexity, space-complexity
---


# Question
Title: How to handle coplanarity in convex hull?
I implemented the $O(n^2)$ convex hull algorithm. That is:

* Find a triangle known to be in the hull (by finding the lowest point, a point connected to it in the 2D convex hull, and the point that makes the widest angled triangle relative to all other triangles with thsoe 2 points).
* Add the 3 edges and the triangle normal to q queue.
* While the queue is not empty

+ pop and edge and the normal to its last seen triangle from the queue.
    + for each point, compute the dot between the last seen normal and the normal produced by the 2 edge points, pick the point with the largest dot (smallest angle).
    + for the 2 new edges, if they have not been seen before, push them and the new triangle's normal onto the queue.

This would be a rust implementation:

```
pub fn convex_hull(points: &Vec<Vec3>) -> Vec<usize>
{
    // The lowest point is part of the 3D convex hull.
    let lowest_id = points
        .iter()
        .enumerate()
        .min_by(|(_, p1), (_, p2)| p1.z.partial_cmp(&p2.z).unwrap())
        .map(|(id, _)| id)
        .unwrap();

    // The lowest point is guarateed to be connected to one of the points in the 2D convex
    // hull.
    let mut best_angle = 1.0;
    let mut best_angle_id = 0;
    for (id, p2) in points.iter().enumerate()
    {
        if id == lowest_id
        {
            continue;
        }

        let mut e1 = p2 - points[lowest_id];
        e1.y = 0.0;
        e1 = e1.normalize();

        let dir = Vec3::new(0.0, 0.0, 1.0);
        let dot = e1.dot(&dir);
        if dot < best_angle
        {
            best_angle = dot;
            best_angle_id = id;
        }
    }

    // Pick a candidate to initialize the next part of the algorithm. Should be distinct
    // from the points we already found.
    let mut candidate = 0;
    while candidate == lowest_id || candidate == best_angle_id
    {
        candidate += 1;
    }

    let get_normal = |i, j, k| -> Vec3 {
        return cross(&(points[j] - points[i]), &(points[k] - points[i])).normalize();
    };

    // Find the thrid point by finding a points such that all other points are in one side
    // of it.
    for i in 0..points.len()
    {
        if i == lowest_id || i == best_angle_id
        {
            continue;
        }

        let normal = get_normal(lowest_id, best_angle_id, candidate);
        if normal.dot(&(points[i] - points[lowest_id])) < 0.0
        {
            candidate = i;
        }
    }

    // Add the first triangle to the set.
    let mut face_ids = vec![lowest_id, best_angle_id, candidate];

    // Test and fix dingint order if necessary.
    let normal = get_normal(face_ids[0], face_ids[1], face_ids[2]).normalize();
    let test = normal.dot(&Vec3::new(0.0, 0.0, -1.0));
    if test < 0.0
    {
        face_ids.swap(0, 2);
    }

    let normal = get_normal(face_ids[0], face_ids[1], face_ids[2]).normalize();
    let mut edge_queue = vec![
        (face_ids[1], face_ids[0], normal),
        (face_ids[2], face_ids[1], normal),
        (face_ids[0], face_ids[2], normal),
    ];

    let mut seen_edges = HashSet::new();
    seen_edges.insert((face_ids[1], face_ids[0]));
    seen_edges.insert((face_ids[2], face_ids[1]));
    seen_edges.insert((face_ids[0], face_ids[2]));
    while !edge_queue.is_empty()
    {
        let (p1_id, p2_id, current_normal) = edge_queue.pop().unwrap();

        let mut best_point = 0;
        let mut best_dot = -1.0;
        let mut best_normal = Vec3::zeros();
        // Find the point that produces the most coplanar triangle with the other
        // triangle in the current edge.
        for point_id in 0..points.len()
        {
            let normal = get_normal(p1_id, p2_id, point_id);
            let dot = normal.dot(&current_normal);

            if dot > best_dot
            {
                best_point = point_id;
                best_dot = dot;
                best_normal = normal;
            }
        }

        face_ids.push(p1_id);
        face_ids.push(p2_id);
        face_ids.push(best_point);

        // Insert points in the opposite winding order to maintian orientation.
        let was_seen = !seen_edges.insert((best_point, p2_id));
        if !was_seen
        {
            edge_queue.push((best_point, p2_id, best_normal));
        }

        let was_seen = !seen_edges.insert((p1_id, best_point));
        if !was_seen
        {
            edge_queue.push((p1_id, best_point, best_normal));
        }
    }

    face_ids
}

```

However, although this works in theory, it greatly struggles with co-planarity. Let me show you. On a randomly distributed point cloud I get a fine CH:

But if I try it with a set where lots of points are coplanar I get something horrible:

The general shape of the CH is correct, but the topology I am getting out is just awful. How should I handle coplanarity?

# Answer
If You find a co-planar triangle candidate, it has to be one that does not contain any other points in that plane. I am not familiar with rust so here is a pseudo-code attempt to enhance your code:

```
if dot > best_dot || (
       dot == 0 &&
  best_dot == 0 && // <- should always be true at this point
  (triangle (p1_id, p2_id, best_point) contains point_id)
)
{
  best_point = point_id;
  best_dot = dot;
  best_normal = normal;
}

```

To test if a triangle $(a,b,c)$ contains a point $p$ on a plane with a normal vector $n$. You could think of $(a,b,c)$ as part of a triangular prism that is infinitely long in the direction of $n$. Or in other words check if $p$ is on the right side of the following three planes given by three points each:

* (b,a,b+n)
* (c,b,c+n)
* (a,c,a+n)

## Floating Point Rounding be a Harsh Mistress

While this would theoretically solve Your problem, there is another big headache in practice: Numeric accuracy. For this algorithm to work robustly, all Your dot products and co-planar and in-triangle testing have to be *exact*. You either could:
> 2 votes

# Answer
The geometric solution in case of coplanar points is to form the convex hull of the coplanar points in their plane, giving a convex polygon. The internal sites are discarded.

Unfortunately, I cannot tell you how to update your algorithm.
> 0 votes

---
Tags: algorithms, data-structures, computational-geometry, topology
---


# Question
Title: Consider A Busy Beaver like Turing Machine on a Mobius Strip. Is it equivalent to standard BB number?
I have modified Busy Beaver Turing Machine scenario. Is this new scenario equivalent to the standard one?

Consider a double sided tape twisted it into a mobius strip having P slots in total.

Initially all zeros on the slots.

Consider two adjacent slots.

We define a Mobius Busy Beaver number which is the sum total of right to left and left to right crossings on the adjacent slots by the Turing Machine.

Are these equivalent scenarios?

Question after watching this excellent video.

# Answer
No. A finitely-sized tape means the Turing machine is not Turing-complete, but in fact a (very large) state machine. This makes the busy beaver number computable in your setup, and thus necessarily different than the original busy beaver numbers.
> 2 votes

---
Tags: discrete-mathematics, mathematical-analysis
---


title: Hex Word Search Generator Algorithm

text:
# Question
Title: Hex Word Search Generator Algorithm
I want to create an algorithm to build a hex matrix with given: \- max n rows \- max m collumns \- min t rown \- min q collumns

containing the specific words from a list: "example", "test", "algorithm".

For example. To build a hex matrix with:

```
  - max n = 5 rows
  - max m = 6 collumns
  - min t = 5 rows
  - min t = 4 collumns
  - containg words: "orange", "test"

```

Can anyone point me in the right direction of how to build this type of algorithm? ( C++, C#, Swift, Objective-C)

# Answer
> 0 votes
Represent the Hex as Graph;

* each node has additional property; `has_letter`; $T,F$
* add the first randomly
    + choose starting point on the graph, probably randomly
    + place the letters by DFS or BFS,
    + add the letter into a list $l$.
* adding another word with one connection, from start

+ from the list find the first letter of the new string that in the middle of another.
    + place the remaining words by DFS or BFS in nodes with $F$ flag.
* adding another word with one connection, not necessary from the beginning.

+ from the list find the letters of the new string.
    + One part may be on the upper; as `corner` and `almond`. if the connection is $o$, `alm` on the upper,
    + One part may be on the lower, and `nd` from the previous example.
    + place the upper part with DFS or BFS in nodes with $F$ flag.
    + place the lower part with DFS or BFS in nodes with $F$ flag.

Hope this helps;

# Answer
> 0 votes
A hex graph can be represented as a 2D matrix where every other column is shifted vertically. It is no big deal to enumerate the six neighbors of a given cell.

This said, you can start from an empty grid and write the words, starting from a random cell and moving in random directions, as long as the next cell is empty or already contains the next letter.

As the last condition will rarely happen by accident, you may try to choose a letter in the word to be written and try to write that word both ways from a cell that already contains that letter.

Presumably you will want a compact matrix with many crossings, but I see no better way to try a large number of times until you find a satisfactory solution. (Well, optimization techniques such as simulated annealing could help, but I am not sure that such a sophistication is worth it.)

---
Tags: algorithms, word-combinatorics
---


title: Does this really define a 0L-system?

text:
# Question
Title: Does this really define a 0L-system?
Looking through old exams I found a problem stated as the following:

> Define a 0L-system as a 3-tuple $S = (\Sigma, w, h)$ where $\Sigma$ is an alphabet, $h:\Sigma^\* \to \Sigma^\*$ is a homomorphism and $w \in \Sigma^\*$ is a starting word. Furthermore define $L(S) = \\{w,h(w),h(h(w)),...\\}$ and define $L$ as a 0L-language if there exists a 0L-system $S$ such that $L$ = $L(S)$.
>
> Prove or disprove that every 0L-language is context-free.

My solution looked like this:

Let $S\_C = \\{\\{a\\},a,h\\}$ with $h(a)=aa$. Then $L(S\_C)= \left\\{ a^{2^n} \mid n \in \mathbb{N} \right\\}$. Assume that $L(S\_C)$ is context-free. Consider $z = a^{2^n} \in L(S\_C)$. Since $|z| = 2^n \> n$, by the pumping lemma for CFLs, $z=uvwxy$ such that $|vx| \> 0$ and $|vwx| \leq n$. Consider $uv^2wx^2y = a^{2^n + i}$, where $0 \< i \leq n$. We have $$2^n \< |uv^2wx^2y| = 2^n+i \leq 2^n+n \< 2^{n+1}$$ which holds true for all $n \in \mathbb{N}$. So $uv^2wx^2y \notin L(S\_C)$ and therefore, $L(S\_C)$ is not context-free and as such, not every 0L-language is context-free.

However, looking on the internet I found that all 0L-languages *are*, in fact, context-free, although they were defined a bit differently. I am relatively sure that my proof is correct, so the given definition for 0L-languages (or 0L-systems) above must be wrong, but I simply wanted to ask to make sure I wasn't missing something obvious.

# Answer
I agree with you, the definition is incorrect. You are trying to prove that $\exists l.\text{0L-L(l)}\land\lnot CFL(l)$. This proof amounts at telling what $l$ is, to show (in separate branches) that it satisfies $\text{0L-L}(\cdot)$ and fails to satisfy $CFL(\cdot)$.

You pointed out $L(S\_C)$ satifies $\text{0L-L}$ because $S\_C$ exists and trivially complies to the definition of $L\text{-}System$ you provided.

The second branch instead requires to you disprove $l$ to be a CFL and you planned to do so by the pumping lemma.

I agree about the definition being incorrect because $L\text{-}Systems$ are defined as triples but $0L\text{-}Systems$ are characterized by productions whose LHS contains exactly one non-terminal symbol. The definition of $h:\Sigma^\*\rightarrow\Sigma^\*$ you provided does nothing to prevent the choice of a rewrite system that generates $L=\\{a^nb^nc^n|n\in\mathbb{N}\\}$ that is notoriously not a CFL.
> 0 votes

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


title: Heap's Algorithm for k-permutations?

text:
# Question
Title: Heap's Algorithm for k-permutations?
Heap's Algorithm enumerates the permutations of a set of N objects. It's described as:

* Permute the elements in positions 1 to n−1 by applying this algorithm to those elements.
* Apply the following steps n−1 times. Increment counter i=1 after each iteration.
    + Swap element in position n with one of the other elements in the following way.
        - If n is odd, swap elements in positions 1 and n
        - If n is even, swap elements in position i and n
    + Permute the elements in positions 1 to n−1 by applying this algorithm to those elements.

How can Heap's Algorithm be used to generate the *k-permutations* of N objects? That is, given a set of N objects, enumerate the ordered selection of k items from the N objects. How would the above algorithm be changed?

# Answer
Yes, and the idea behind the modification is fairly straightforward.

Using a C-like notation, this is Heap's algorithm:

```
void
generate(int k)
{
    if (k == 1) {
        output(A[0..N-1]);
        return;
    }

    generate(k-1);
    for (int i = 0; i < k-1; ++i) {
        if (k % 2 == 0) {
            swap(A[i], A[k-1]);
        }
        else {
            swap(A[0], A[k-1]);
        }
        generate(k-1);
    }
}

generate(N);

```

This is the order that Heap's method produces all the permutations for $N=4$, say:

```
0 1 2 3
1 0 2 3
2 0 1 3
0 2 1 3
1 2 0 3
2 1 0 3
3 1 0 2
1 3 0 2
0 3 1 2
3 0 1 2
1 0 3 2
0 1 3 2
0 2 3 1
2 0 3 1
3 0 2 1
0 3 2 1
2 3 0 1
3 2 0 1
3 2 1 0
2 3 1 0
1 3 2 0
3 1 2 0
2 1 3 0
1 2 3 0

```

If you output the *last* $K$ digits for each permutation:

```
output(A[N-K..N-1]);

```

Then the output will be all $K$-permutations, with each permutation repeated exactly $K!$ times. For example, setting $N=4$ and $K=2$:

```
2 3
2 3
1 3
1 3
0 3
0 3
etc

```

To avoid the duplicates, therefore, you just need to skip to the last permutation in the group, which turns out to be a single swap if N-K is odd, but a slightly more complex permutation if N-K is even.

```
/* NOTE: The original version of this code did not get
   the even case correct. */
void
generate(int k)
{
    if (k == N-K) {
        output(A[N-K..N-1]);
        if (N > K + 1) {
            if (N-K is odd or K == 2) {
                swap(A[0],A[N-K-1]);
            }
            else {
                a0 = A[0];
                ank3 = A[N-K-3];
                ank2 = A[N-K-2];
                ank1 = A[N-K-1];
                for (int j = nmk-3; j > 1; --j) {
                    A[j] = A[j-1];
                }
                A[0] = ank3;
                A[1] = ank2;
                A[N-K-2] = ank1;
                A[N-K-1] = a0;
            }
        }
        return;
    }

    /* The code from here on is unchanged. */
    generate(k-1);
    for (int i = 0; i < k-1; ++i) {
        if (k is even) {
            swap(A[i], A[k-1]);
        }
        else {
            swap(A[0], A[k-1]);
        }
        generate(k-1);
    }
}

generate(N);

```
> 1 votes

# Answer
by calling the original heap's algorithm `generate(k,A)`, we expect it to print all permutations of $A\[1:k\]$ and $A$ will be rotated to the right $1$ unit if its size is even, else it'll be unaltered.

I've no idea how to generate k-permutations of N objects by directly changing heap's algo because by changing what we expect `generate(k,A)` to do we're changing the whole recurrence tree, ie. we may need to clearly re-specify each of the divide, conquer and combine step.

but still below is a more straightforward way to generate k-permutations of N objects (specifically the numbers $1,...,n$, it can be easily modified to permute other objects by treating $1,...,n$ as array indices) that make use of heap's algorithm. While it doesn't "directly modify" the heap's algorithm, it may give you some idea on how to do so.

basically, by calling `k_perm_of_n(k,n)` it prints all $k!$ permutations for each of the $\binom{n}{k}$ $k$-combinations of the set $\\{1,...,n\\}$. The only overhead is the rotation/copying of the array modified by heap's algorithm.

```
#include <iostream>
#include <algorithm>
#include <vector>
#include <numeric>

//a is a k-combination of 1,...,n
//generates the next larger k-combination after 'a' according to lexicographic order (by mutating 'a')
//, e.g. {1,3,4} is larger than {1,2,4} compare from left to right entry-wise
//returns false when 'a' is already the largest combination, else returns true (and 'a' will be mutated)
bool next_combination(std::vector<int>& a, int n) {
    int k = (int)a.size();
    for (int i = k - 1; i >= 0; i--) {
        if (a[i] < n - k + i + 1) {
            a[i]++;
            for (int j = i + 1; j < k; j++)
                a[j] = a[j - 1] + 1;
            return true;
        }
    }
    return false;
}

//heap's algorithm
template<typename T>
void generate(int k,std::vector<T>&A){
    if(k==1){
        std::for_each(A.begin(),A.end(),[](const T&t){std::cout<<t<<' ';});
        std::cout<<std::endl;
    }
    else{
        generate(k-1,A);
        for(int i=0;i<k-1;++i){
            if(k%2==0)
                std::swap(A[i],A[k-1]);
            else
                std::swap(A[0],A[k-1]);
            generate(k-1,A);
        }
    }
}

//print all k permutations of 1,...,n
void k_perm_of_n(int k,int n){
    std::vector<int> a(k);
    std::iota(a.begin(),a.end(),1);//fill a with 1,...,k
    do{
        //for simplicity we just copy A to B as generate() may mutate the input array
        //alternatively you may rotate it back if A.size() is even
        std::vector<int>b(a);
        generate(k,b);//prints all permutations of this combination
    }while(next_combination(a,n));//move to next combination
}

int main(){
    k_perm_of_n(2,4);//print all 2-permutations in 1,...,4
}

```

the `next_combination` is from \[1\] and you may want to read \[2\], the heap's algorithm is from \[3\].

\[1\] Algorithms for Competitive Programming

\[2\] Combinatorial number system

\[3\]Heap's algorithm
> 0 votes

---
Tags: permutations
---


# Question
Title: Efficient algorithm for finding the target sum
**Task.** Find such natural numbers a1,. . . , am , that none of them would be included in the list of excluded numbers, a1 + · · · + am = N and max{a1 , . . . , am} would be as small as possible. Numbers cannot be reused.

**Initial data.** The first line contains two natural numbers N and K - desired sum and length of excluded number list. The second line lists the K distinct numbers that are excluded.

**Results.** Output the numbers a1 , . . . , am, whose sum is N and which satisfy the listed conditions. They can be listed in any order. If it's impossible to satisfy the conditions, output "IMPOSSIBLE".

**Constraints.** 1 ≤ N ≤ 1000 000 000, 0 ≤ K ≤ 1000 and all excluded number list members are between 1 and 1,000,000,000 inclusive.

This seems similar to the subset sum problem. I have implemented a tabular Dynamic Programming solution, however, that is not fast and memory-efficient enough. The time-complexity of my algorithm is O(N\*(N-K)) while space-complexity is O(N).

Any ideas?

# Answer
> 1 votes
This *is* an instance of the subset sum problem. The set is the range of naturals up to $N$ from which you remove the excluded numbers.

---
Tags: dynamic-programming, combinatorics, subset-sum
---


# Question
Title: Finding the smallest possible pattern order to recreate a canvas
I made this problem up in my head, and I'm looking for a solution. I realized that it's a very interesting problem, and I'm way too dumb to solve it, so I'm asking for help.

# The problem

Given a 'desired canvas', which is a grid of colors (let's say an 8 by 8, because it's easy to work with). And given a list of unique 'patterns', where a 'pattern' is grid of booleans with the same size as the 'desired canvas'.

We can define an 'instruction' with a pattern and a color. We can use an instruction to "paint" on a new canvas, where we start with a blank canvas, and we paint the pattern on the canvas, but only on the pixels where the pattern is True. We can do this with every instruction. An 'instruction set' is a list of instructions. The order of the instructions matter, because we can paint over pixels, resulting in a different canvas.

**What is the smallest possible instruction set, that reproduces our desired canvas?**

We know that, most likely there are more than one of those, but we only care about one, so it doesn't matter which one we get. It just has to be the smallest possible size.

To be always able to reproduce the 'desired canvas' with our patterns, let's say we always have some default patterns, each of them being just a single pixel for every position (for 8x8 that'd be 64).

**This problem is easily solvable by just trying every possible combination of instructions, but that would be very slow.**

**Also, the algorithm has to be only fast for a single pattern group, what I mean by that is that we can parse the patterns into a structured format, and then we can use that format to solve the problem for multiple 'desired canvases' faster. Although, the parsing process shouldn't take *too* long.**

**It should work well with a large number of patterns, let's say 1000.**

# Things I found

## Checking if the instruction set is correct by only looking at the patterns

We can check if the instruction set is correct by only looking at the patterns, and not the colors. In this code I store the patterns and the colors in a list of bitmaps, where each bitmap is a 64 bit integer, and each bit represents a pixel. The first bit is the top left pixel, and the last bit is the bottom right pixel. Each bitmap in the `color_bitmaps` represents positions of a different color.

```
def is_correct(color_bitmaps: list[int], pattern_order: list[int]):
    occupied = 0

    for pattern in pattern_order[::-1]:
        bitmap = pattern & ~occupied
        found = False
        for color in color_bitmaps:
            if color & bitmap == bitmap:
                found = True
                break
        if not found:
            return False
        occupied |= bitmap
    return occupied == (1 << (64)) - 1

```

Because of this, it's easy to brute force the problem, because we can just try every possible combination of patterns, and check if it's correct. But this has a complexity of `O(n!)` (if not worse), which is very slow.

## Relationships between patterns

I found relationships between the patterns, which could make solving the problem easier.

### Unrelated

Two patterns are unrelated if there are no intersections. This means that in the instruction set it DOES NOT matter whether these two are before or after one another, because they would result in the same canvas.

### Parent-child

A and B patterns are in parent-child relationship if the intersection of A and B equals B. In that case A would be the parent and B would be the child. This means that A should be always before B in the instruction set, because if B is before A then the resulting canvas is the same if B wouldn't be there.

### Overlapping

If two patterns have an intersection, and not in a parent-child relationship, they are in a overlapping relationship. This means that in the instruction set it DOES MATTER whether these two are before or after one another, because they would result in a different canvas.

# What I tried

I tried brute forcing the problem, but that was too slow. I found some ways to make the range of possible solutions smaller, but still. I also tried to travel through the pattern tree, but it's more of a graph than a tree, because of the overlapping relationships.

# End note

I'm looking for a decent algorithm that can solve this problem. Also I thought of machine learning, but I don't know how to apply it to this problem, so if you know how to do that, guidance would be appreciated.

(( i used python for examples just because it's easy to understand, but i'm not limited to python ))

# Answer
> 1 votes
Since each pattern brush potentially overwrites previous pixels, I would suggest you work your way backwards. Basically You start checking for which patterns intersected with the "considered pixels" all pixels have the same color. For each of the patterns call the solver recursively with an image where the pattern pixels are removed from "considered pixels".

This will still give you a lot of combinations though. So instead of going through all combinations, you could do an A\* search where the number of "considered pixels" is the the distance.

Depending on how tricky and/or redundant the pattern are that may still be a lot of combinations that have to be tested.

---
Tags: algorithms, graphs
---


# Question
Title: What are the advantages of using PRNG over TRNG?
True random number generators use an unpredictable physical means to generate numbers, whereas pseudo-random numbers utilize mathematical formulas to produce a certain sequence of numbers that will appear random. I know that for PRNGs the efficiency is very high because they tend to generate a large quantity of random numbers in a short amount of time. Beside reproducibility and efficiency, what are the advantages of using PRNG over TRNG?

# Answer
> 5 votes
It's an apples and oranges comparison.

When you want something to be truly random, you must use a TRNG. Examples include a lottery, or a secret/private key in cryptography.

When you want something repeatable, you must use a PRNG. An example is a large secret keystream for XOR encryption, generated (imperatively: identically) on both the transmit and receive side from a short common shared secret key.

> What are the advantages of using PRNG over TRNG?

PRNGs can be portable to different computers and languages. Their implementations are easy to validate. They have a mathematical security definition, and it's easy to make fast PRNGs that experimentally match it (on the other hand, we don't know how to prove that).

TRNGs are not portable (they are not entirely software anyway), and are much more complex (typically there's a hardware source, tests of that at power-up and while in use, and a conditioning stage). It's hard to convince a neutral party that a TRNG works.

In practice, the best choice is almost always a Cryptographically Secure PRNG, seeded by a public constant when one wants repeatability, or seeded by the output of a TRNG (or a secret constant changed manually as needed, perhaps combined with a counter, or time from a truly strictly increasing reference) otherwise. The CSPRNG will mask any small imperfection of the TRNG there will be, and have a high throughput: modern CSPRNG are extremely fast (in the order of 10 CPU cycles per byte generated for Salsa20, which supports "skip-ahead").

# Answer
> -1 votes
In a word, no.

Even TRNGs carry artifacts from natural processes which must be filtered out by slow entropy polling, random polling, inversion and XOR from the same source but over two different time periods, using many such sources, and combinations of all of the above.

The time between Geiger counter ticks is an example of truly random events, created as they are from a billion billion radioactive atoms. It's literally slow entropy polling taken to the extreme! Although the times are analog, they can be made digital simply by comparing each interval to the preceding one. If it's longer, it's a 0. If it's shorter, it's a 1. By using an even number of multiple independent detectors and timers and XORing the streams, you'll arrive at a string of binary numbers which pass all current and conceivable tests of randomness.

You can achieve the same degree of randomness, however, even if you use fairly deterministic generators, such as those found in Excel, if you "randomize the random."

I've been doing so for several years, and at a rate of over 91 Mbps.

By the way, CSPRNG is not "Cryptographically Strong PRNG." It's "Cryptographically Secure Pseudo-Random Number Generator."

---
Tags: algorithms, randomized-algorithms, cryptography, pseudo-random-generators
---


# Question
Title: Efficient algorithms to generate partial permutations?
I want to efficiently generate partial permutations.

That is, I want to generate the set of ordered arrangements of K distinct elements selected from a set from N items. For example, with the set ABCDE where N=5, if K=2, then the partial permutation set is AB, AC, AD, AE, BA, BC, BD, BE, CA, CB, CD, CE, DA, DB, DC, DE, EA, EB, EC, ED.

The obvious way to do this is to repeatedly concatenate lists, and add/remove items from lists. I'm looking for a more efficient algorithm.

There are multiple algorithms for efficiently generating the full set of permutations of a set of N items, but I have not know of any that generate the set of partial permutations.

# Answer
You can use immutable, singly linked lists to generate partial permutations in $O(n \operatorname{choose} k)$ operations and memory, which is likely optimal. Here's an example in the Scala programming language:

```
class PartialPermutations( n: Int, k: Int ):
  require(n >= k)
  require(0 <= k)

  def foreach( action: List[Int] => Unit ): Unit =

    def recursion( n: Int, k: Int, sample: List[Int] ): Unit =
      if k == 0 then
        action(sample)
      else
        for i <- n to k by -1 do
          recursion(i-1, k-1, i-1 :: sample);
        end for
      end if
    end recursion

    recursion(n, k, List.empty[Int])

  end foreach

end PartialPermutations

for x <- PartialPermutations(8,3) do
  println(x)
end for

```

Note that the samples are returned in **descending reverse lexicographical order**. An ascending standard lexicographical ordering can be achieved with a few modifications.

The basic idea of the algorithm is to:

* If $k = 0$, return an empty list
* Take $\operatorname{partialPermutations}(n-1,k-1)$ and append $n-1$ to each of it
* Take $\operatorname{partialPermutations}(n-2,k-1)$ and append $n-2$ to each of it
* ...
* Take $\operatorname{partialPermutations}(k-1,k-1)$ and append $k-1$ to each of it

While this performance is fancy in theory it will likely not give You any performance benefit in practice, because whatever you do with these partial permutations is very likely an $\mathcal{O}\left(k\cdot\left(n \operatorname{choose} k\right)\right)$ operation anyways. So here is a slightly simpler array-based $\mathcal{O}\left(k\cdot\left(n \operatorname{choose} k\right)\right)$ implementation in JavaScript:

```
function* partialPermutations( n, k )
{
  const sample = new Array(k)

  function* recursion( n, k ) {
    if( k <= 0 )
      yield sample.slice() // <- make a copy
    else for( let i=n; i-- >= k; i ) {
      sample[k-1] = i
      yield* recursion(i, k-1)
    }
  }

  yield* recursion(n,k)
}

for( const x of partialPermutations(8,3) )
  console.log(x)

```
> 1 votes

---
Tags: permutations
---


# Question
Title: How are blind writes recoverable in a transaction schedule?
Consider the following schedule -

```
T1     T2

R(A)
W(A)
       R(A)
       W(A)
       Commit
Commit

```

I understand that this schedule is non-recoverable, because if a failure occurs between the two commits, then we can't rollback the operations performed by T2, as they would already have been committed.

But, if we change this schedule to

```
T1     T2

R(A)
W(A)
       R(A)
       W(A)
Commit
       Commit

```

then this becomes recoverable, as if a failure now occurs immediately before T1's commit, then all the operations performed by T1 and T2 can be rolled back, and if a failure occurs between the two commits, then we can roll back only T2's operations and run only T2 separately again.

Now, everywhere that I've read about recoverable schedules, it is written that a recoverable schedule is one where, for each pair of transactions Ti and Tj such that Tj **reads** a data item previously written by Ti, the commit operation of Ti appears before the commit operation of Tj.

So, if we go by this definition, then the following schedule must be recoverable -

```
T1     T2

R(A)
W(A)
       W(A)
       Commit
Commit

```

But, how is this schedule recoverable? In this case as well, if a failure occurs between the two commits, then we again can't roll back T2's W(A) operation, and if we roll back only T1's operations and run only T1 separately, then the final value that will be reflected in the database will be T1's W(A), when our original intention was to store T2's W(A) in the database.

# Answer
```
T1     T2

R(A)
W(A)
       W(A)
       Commit
Commit

```

is not recoverable, even though it satisfies the condition you mentioned about the commit order of transactions. Let's walk through it:

1. T1 reads and writes A.
2. T2 writes A.
3. T2 commits.
4. T1 commits. If a failure occurs after T2's commit but before T1's commit, the system needs to be rolled back to a consistent state. But, in this case, the final state after rolling back would reflect T1's update to A, and the update from T2 would be lost.

This is a case where the criterion mentioned ("for each pair of transactions Ti and Tj such that Tj reads a data item previously written by Ti, the commit operation of Ti appears before the commit operation of Tj") does not ensure recoverability when taken on its own. Recoverability also requires that the final committed state of the database reflects the actual intentions of the transactions.

Your analysis highlights a limitation in the definition you mentioned. Recoverability requires not only the commit order but also the preservation of the final intended updates. In a recoverable schedule, if a transaction Tj reads a value previously written by Ti, then Tj's commit should appear after Ti's commit to ensure that the intended effects of both transactions are correctly reflected in the committed state, even in the face of failures.
> 1 votes

---
Tags: database-theory, database-concurrency
---


# Question
Title: What is the object translating part of a monadic endofunctor?
A monad is an endofunctor $T:C\rightarrow C$ with natural transformations $\eta:id\_C\rightarrow T$ and $\mu:T^2\rightarrow T$.

Being natural transformations mean that $$T(f)\circ \eta\_A = \eta\_B\circ id\_C(f)$$ should hold and $$T(f)\circ\mu\_A = \mu\_B\circ T^2(f)$$ also. These are the algebraic expressions that the defining diagrams of natural transformations commute.

Translating this to the language of functional programming, $\eta$ is `unit`, and a polymorphic one, so $\eta\_{nat}$ is the monomorphisation of `unit` to the `nat` type. $\mu$ is `join` in the same sense. The functor $T$ consists of two things: it takes object and morphisms. The latter part is called `map` in functional programming. So the above equations translate to

```
map f o unit = unit o f

```

where, if `f` is `A -> B` then this is

```
map f o unit(A) = unit(B) o f

```

but that is usually handled with a polymorphic type system and the second equation is

```
map f o join = join o map (map f)

```

So, `map` is the morphism-translating part of the endofunctor $T$.

But what is the object-translating part of $T$ in functional programming? Is it the type operator `M` when we write `unit: 'a -> 'a M` ?

# Answer
> 0 votes
Objects are isomorphic to identity morphisms. So, the object-translating portion of the endofunctor is a subportion of the morphism-translating portion, also carried by `map`.

---
Tags: functional-programming, category-theory, monad
---


# Question
Title: Does there exist a data compression algorithm that uses a large dataset distributed with the encoder/decoder?
If my goal were to compress say 10,000 images and I could include a dictionary or some sort of common database that the compressed data for each image would reference, could I use a large dictionary shared by the entire catalog and therefore get much smaller file sizes? Could this be expanded to work with images in general, i.e. to replace something like JPEG?

Are there existing compression systems that operate like this, where there is a large common set of bits transmitted and loaded before decompression, that has been built by analyzing many images?

For example, is there an existing computer science/machine learning research effort using sparse autoencoding over a large set of images and this concept of distributing a network derived from that encoding with the decompressor?

---

Note: Coming back to this question and the answers, I see that it was primarily not understood because those that read it did not understand enough about new types of machine learning.

New techniques in machine learning, particularly deep learning or other advanced neural network systems, do have the potential make many existing data compression techniques outdated. Or rather, we should expect that some more extensive research will result in these types of powerful encoders. As of yet this is mainly speculative, and data compression scientists cannot conceive of them without fully understanding the power of the new neural network techniques.

# Answer
you're focused on images so will construct a scenario that fits your question in the affirmative. imagine certain images that are not compressed via lossy compression eg a non jpeg-like algorithm. imagine the images are not compressed and stored in a straight pixel format. next suppose there are images that are composed of sub images in a vertical fashion. eg imagine a stack of images composing a larger image:

```
A
B
C
D

```

in the above crude diagram A,B,C,D are stacked images that compose a larger image, say E. now suppose that one creates a file that is concatenating files/images A,B,C,D,E. on a standard "lossless" dictionary compression algorithm like lempel-ziv, the algorithm will be smart enough to use A,B,C,D as long dictionary strings, and compose E out of those strings. (this depends on specifics like maximal dictionary word size etc, but it could be made to work). so in this admittedly rather contrived scenario, the answer is YES.

however, you are missing something about JPEG, it is typically lossy compression, and also images are generally a 2d format, whereas a lot of compression algorithms take advantage of 1d patterns like long strings. so this lossiness combined with the 2d format will mean that general compression algorithms will *not* really save much over the cost to store the original images (which generally are already compressed anyway).

therefore this is generally a negative answer overall, the overall idea of "compressing" using a "dictionary of images" is not really valid/possible/plausible and you can get a better idea of why by studying the mechanics/dynamics of compression algorithms in a more detailed way. on the other hand there are a wide variety of image compression algorithms that do in fact take advantage of redundancies in images. in JPEG for example the image is broken into squares and it can reuse common squares!
> 1 votes

# Answer
The Brotli compression algorithm is somewhat like that. It is however a text compression algorithm. It uses a dictionary of words common in HTML documents which is packaged with the (de)compression software not the compressed data.
> 0 votes

---
Tags: machine-learning, neural-networks, data-compression, computer-vision
---


# Question
Title: Is { a^nb^na^n} a context-sensitive language?
The language $L\_1 = \\{ a^nb^nc^n \\}$ is often given as an example of a context-sensitive language.

I am wondering if the language $L\_2 = \\{ a^nb^na^n \\}$ belongs also to the same category?

# Answer
> 2 votes
The grammar:

> $S\to aS'Ba\mid aba \mid\varepsilon$
>
> $S'\to aS'Ba\mid aba$ (so that only the start symbol can generate the empty word)
>
> $aB \to Ba$ (to move the inner $a$'s to the right)
>
> $bB \to bb$ (to transform all $B$'s into $b$'s)

is a noncontracting grammar generating the language $\\{a^nb^na^n\mid n\geqslant 0\\}$. That means the language is context-sensitive.

Beware that the previous grammar is not context-sensitive (the problematic rule is $aB\to Ba$).

If you want a context-sensitive grammar, it is a bit more complicated. Something like this should work:

> $S\to aS'BA\mid aba \mid \varepsilon$
>
> $S' \to aS'BA\mid abA$
>
> $AB\to XB$
>
> $XB \to XY$
>
> $XY\to BY$
>
> $BY \to BA$
>
> $bB\to bb$
>
> $A \to a$

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


# Question
Title: a program discovering himself how to solve propositional calculus
it is well-known that propositional logic problems such as

$$ (p\leftrightarrow q) \lor r \quad\overset{?}{\vdash}\quad (((p\lor q)\to(p\land q)) \land \lnot r)\lor r$$

can be simply solved by evaluating the corresponding boolean functions for the $2^n$ possible values of the $n$ boolean variables (here $p,q,r$).

my question is then : instead of hand-writing such a propositional logic solver, couldn't we search for a program capable of generating such a solver ?

what would be then the minimal core / set of concepts and rules needed for a program being capable of ''discovering'' and ''solving'' the propositional calculus ?

is it a unsolvable artificial intelligence problem, or would it have some nice solutions, helpful for solving the more interesting higher order logics ?

# Answer
If there are no quantifiers, testing validity of such formulas is equivalent to testing satisfiability of the complement of the formula. That can be done with a SAT solver. SAT solvers and the satisfiability problem are well-studied. So, the minimal set of concepts needed would be: enough to solve SAT.

Statements with quantifiers are harder (QBF). Higher-order logics are harder still.
> 2 votes

# Answer
I'm not quite sure how you would define success, but here are a couple of references and some context to help you get started.

Have a look at this paper in the AI Journal:

A computational approach to George Boole’s discovery of Mathematical Logic

The underlying approach to be seems to be an old-fashioned production system.

I would be remiss if I didn't mention the now ancient Automated Mathematician program by Lenat. The Wikipedia article gives a good overview of the program as well as its considerable shortcomings. Nice related references there as well.

Finally, here's a recent New York Times article that might be relevant.
> 0 votes

---
Tags: artificial-intelligence, first-order-logic, propositional-logic
---


# Question
Title: What is the definition of security of universal hashing
As a cryptographic primitive, universal hashing should have somewhat a criterion on its security. How is its (computational) security defined? Or, in other words, what "breaks" a universal hashing?

# Answer
There's a variety of formal definitions, let me illustrate by giving the three most common definitions. Let $\Pr\_{h\in \mathcal{H}}\[X\]$ denote the probability of event $X$ if $h$ is chosen independently and uniformly at random from set $\mathcal{H}$. A hash function family $\mathcal{H}$ is $\epsilon$-almost universal ($\epsilon$-AU) if for any $m \neq m'$ we have

$$\Pr\_{h\in\mathcal{H}}\left\[h(m) = h(m ')\right\] \leq \epsilon.$$

A hash function family $\mathcal{H}$ is $\epsilon$-almost delta universal ($\epsilon$-ADU) if for any $m \neq m'$ and any $\delta$ we have

$$\Pr\_{h\in\mathcal{H}}\left\[h(m) \ominus h(m') = \delta\right\] \leq \epsilon,$$ where $\ominus$ is subtraction in some group (e.g. subtraction mod $n$ or XOR).

A hash function family $\mathcal{H}$ is $\epsilon$-almost strongly universal ($\epsilon$-ASU) if for any $m \neq m'$ and any $d, d'$ we have

$$\Pr\_{h\in\mathcal{H}}\left\[h(m) = d \wedge h(m') = d'\right\] \leq \epsilon.$$

If $D$ is the set of hash digests, we find that $\epsilon/|D|$-ASU implies $\epsilon$-ADU which in turn implies $\epsilon$-AU.

> Or, in other words, what "breaks" a universal hashing?

All three of the above three formal definitions area *bound* some probability. You break a universal hash by showing that the respective event $X$ happens more often than the bound claims.
> 3 votes

---
Tags: hash, cryptography, security
---


title: $n \pmod k$ circuit

text:
# Question
Title: $n \pmod k$ circuit
I wondered if, for a fixed integer $k ≥ 3$, how can I construct a circuit for each $n \in \mathbb{N}$, that takes as input an n-bit integer $x$ and outputs whether 3 divides $k$?

Considering an n-bit integer as input: e.g. $\ldots10101110$, where $a\_0$ is the rightmost bit and $a\_N$ the leftmost bit, $\bmod 3$ has a cycle of $2$:

$$(a\_0 \times 2^0 + a\_1 \times 2^1 + a\_2 \times 2^2 + a\_3 \times 2^3 + \ldots) \bmod 3\\ = a\_0 \times 1 + a\_1 \times (-1) + a\_3 \times 1 + a4 \times (-1) \ldots$$

so it has a cycle of two, considering the remainder being either 1 or (-1).

How can I use this knowledge to construct a boolean circuit that checks for an n-bit integer as input the divisibility by 3?

Additionally: Once solved for $k = 3$, how can I generalize this to any fixed k? The idea behind this is to create a circuit whose sizes should be polynomial in n.

Important: Please give hints only so I can figure it out myself!

# Answer
> 0 votes
Sadly, my knowledge of circuits is quite limited, so I will try to answer the question algorithmically. If You go through your bits from most to least significant, You could reconstruct Your number as follows:

```
number = 0

foreach bit in [a[n-1], a[n-2], ..., a[n]] do
  number = 2*number + bit
end foreach

return number

```

This can be done by a simple shift followed by an increment per iteration. But, of course, the number might be huge and we are only interested in the remainder. So instead we can can use modular arithmetic to only build the remainder:

```
remainder = 0

foreach bit in [a[n-1], a[n-2], ..., a[n]] do
  remainder = (2*number + bit) mod k
end foreach

return remainder

```

Since `2*remainder + bit <= 2*(k-1) + 1` we can replace the modulo operator by a comparison, conditonally followed by a subtraction:

```
remainder = 0

foreach bit in [a[n-1], a[n-2], ..., a[n]] do

  remainder = 2*number + bit

  if remainder >= k then
    remainder = remainder - k
  end if

end foreach

return remainder

```

And there You have it. For each bit in $a$ you would need:

* 1 Shift
* 1 Increment (e.g. via chain of "flip-flops")
* 1 Comparison
* 1 Conditional Subtraction (e.g. via Ripple-Carry-Adder using two's complement of $k$)

That should take around $\mathcal{O}\left(\left\lceil\log\_2\left(2k-1\right)\right\rceil\right)$ logic gates per bit in $a$.

In practice there are of course much more efficient solutions than that. For division algorithms, I can recommend the book Modern Computer Arithmetic. Everything You learn there should be applicable to circuits as well, but You will have to think much more parallel in circuit design, I presume.

For reference, here is a Scala implementation of the algorithm:

```
def mod( n: BigInt, k: Int ): Int =

  require(n >= 0)
  require(k >  1)

  var rem = 0L

  var i = n.bitLength
  while i > 0 do
    i -= 1
    rem *= 2
    if n.testBit(i) then rem += 1
    if rem >= k     then rem -= k
  end while

  assert(rem >= 0)
  assert(rem <  k)
  return rem.toInt

end mod

```

# Answer
> 1 votes
Here is some JS code that performs the n mod k operations. To visualize I generate all 8-bit representations and let them run through the function to output a truth table, outputting True if divisible by k and False otherwise. For higher bit-inputs one can adapt the code.

```
function mod(n, k) {
  if (n < 0 || k <= 1) {
    throw new Error("Invalid input: n must be non-negative and k must be greater than 1");
  }

  let rem = 0n; // Use BigInt for arbitrary precision arithmetic

  let i = n.toString(2).length; // Bit length of n
  while (i > 0) {
    i -= 1;
    rem *= 2n;
    if (n & (1n << BigInt(i))) rem += 1n;
    if (rem >= BigInt(k)) rem -= BigInt(k);
  }

  if (rem < 0n || rem >= BigInt(k)) {
    throw new Error("Assertion failed: Invalid remainder value");
  }

  return Number(rem);
}

// Generate all 8-bit combinations
const allCombinations = Array.from({ length: 256 }, (_, i) => BigInt(i));

// Set the value of k
const kValue = 13;

// Iterate over the combinations and check divisibility by k
const divisibilityResults = allCombinations.map(combination => mod(combination, kValue) === 0);

console.log(divisibilityResults);

```

Thanks to @DirkT for the ideas.

# Answer
> 0 votes
Given a 3 bit number, we can find a 2 bit number with the same remainder modulo 3. That means we map 0 to 7 to 0, 1, 2, 0 or 3, 1, 2, 0 or 3, and 1. So we take the number xyz and create a circuit C that outputs y’, z’ as follows: If x=0 then y’ = y, z’ = z. If x = 1 then with 4 modulo 3 = 1 we map 1yz to 01 if y = z and to 1y if y ≠ z.

For n \>= 3 bits, we use this to transform the first 3 bits to two bits and are left with n-1 bits. Then we feed these two bits and the fourth bit into an identical circuit, get n-2 bits, and so on until we are left with just two bits. At that point xy is divisible by 3 if and only if x=y.

If you want to build super fast hardware then the problem is that you have a chain of n of these circuits in sequence, taking O(n) steps. You can reduce this to O(log n). Use this method for n \<= 4. For n \<= 8 transform the upper and lower 4 bits into 2 bits each in parallel, then take the resulting 4 bits and handle them as before. For n = 16, split x into 2 x 8 bits, for n = 32 use 2 x 16 bit, for n = 64 use 2 x 32 bits and so on. This takes O(log n) sequential steps.

How many circuits C do we need? n = 4 -\> 2 circuits C. n = 8 -\> 2x2, plus 2, = 6 circuits. n = 16 -\> 2x6, plus 2, = 14 circuits, n = 32 -\> 30 circuits, n = 64 -\> 62 circuits C. That’s what we need anyway, so the fast circuit for large n doesn’t actually need more hardware.

How to build such a circuit: First build a circuit A which outputs (x = y) for inputs x and y. This is (y AND z) OR (NOT y AND NOT z). Now "01 for y=z, or 1y for y!=z" is done by a circuit which outputs (A AND 0) OR (NOT A AND 1) = NOT A, and another that outputs (A AND 1) OR (NOT A AND y) = A or y, call the circuit with these two outputs B and B'. And finally you have (NOT x AND y) OR (x AND b), and (NOT x AND z) OR (x AND b').

---
Tags: digital-circuits, modular-arithmetic
---


# Question
Title: Schoolclass Optimization Algorithm for finding Stable Matching
I have the task to write a program that puts students in classes and that in the best possible way.

We have given the name, the foreign language a student chooses(french or latin), a profile (Music,bilingual or normal) and 2 friends and enemys for every student in a table. A friend is someone a student should be in a class with(no must) An enemy is someone a student shouldn't be in a class with(no must)

As settings we have the minimum and maximum count of students in a class, the maximum count of classes general, maximum count of classes with latin, music and bilingual each.

In the end we want the students put in a class, with at best both their friends, without their enemys and least mixture between the different foreign languages and profiles.

Do you have any rough idea how I could solve this?

Thanks in advance

# Answer
> 0 votes
You can use the Gale-Shapley algorithm (or deferred acceptance algorithm) and opportunely modify it in order to model your case.

In the original algorithm, you have to pair elements from two sets. Here, you have to pair students and classes, but a class can be paired with more than one student. For doing so, it is sufficient to keep a counter for classes' capacity and decrease a counter by 1 each time a student is assigned to a class.

The one who do the choice is the student, while the class receives the proposal. A class would reject a student if it is full.

You have to define the priorities of a student (language, friends, enemies).

You can assign a student and then assign theyr friends to the same class and enemies to another class (if possible). The algorithm could remove a friend if it is necessary, or reassign an enemy to that class.

This algorithm will find a stable matching (but an optimal solution is not guaranteed).

For more details on the original algorithm: https://en.wikipedia.org/wiki/Gale%E2%80%93Shapley\_algorithm

---
Tags: sorting, bipartite-matching, classification
---


# Question
Title: How is a video file read frame by frame without loading the entire video file in memory?
As I understand that a video file is a binary file, the frames are not really present in a contiguous manner in a video file, so reading the video file by doing a seek and reading it frame by frame wouldn't work until you have loaded the entire file into memory and then go through it frame by frame.

But if you see any video file reading library eg opencv code, you can read each frame one by one by calling read multiple times in a loop.

```
video=cv2.VideoCapture(video_path)
grabbed, frame=video.read()

```

My question is how do they(such libraries) work internally to read the frames one by one without loading the entire video file in memory since frames are not really present in a video file in a contiguous manner so the seek and read x+size data wouldn't work.

# Answer
In most video formats, the frame data is in fact stored in chronological order, for many reasons:

* video recording to file
* video streaming
* avoiding slow file seeking on HDDs
* ...

In most video formats, most frames are stored as a difference to the previous frame (so-called inter frames). Since frames are usually less than 40 miliseconds apart, the difference is very small and can be stored with relatively few bits of (compressed) data most of the time.

That makes your question very important and valid: If each image is stored as a difference to the previous image, how can we jump back an forth? We would have to build each frame one after another, starting at the very beginning.

The solution is simple: Most compressed videos contain a series of key frames which are independently compressed, i.e. they do not rely on any previous frame. Their timestamps and positions are stored in a lookup table, usually at the end of the video file (after encoding has finished). To go to a given time step $t$, You jump to the most recent key-frame before $t$ and walk through the inter-frames to the desired frame.
> 1 votes

---
Tags: video
---


title: Is $n^{1.03} = \Omega(n \log \log n)$?

text:
# Question
Title: Is $n^{1.03} = \Omega(n \log \log n)$?
We had this problem on our Algorithms final. It threw me off because if $\log$ is $\log\_2$ then graphing the function shows this is not true, but if $\log$ is $\log\_{10}$ then it looks like it is. How can this idea be formalised?

# Answer
To compare complexity orders, plots are your false friends. Because you may need to look at astronomical values to detect curve crossings. Nothing replaces analytical study.

For example, on a plot $n^{30}$ (in blue) seems to completely outperform $3^n$, but in reality, the latter grows much faster !

---

You are probably aware that $e^x=\Omega(x)$ \[by Taylor, $e^x\>1+x+\frac{x^2}2$\]. This implies $e^{ax}=\Omega(ax)=\Omega(x)$, for any $a\>0$. Now we can replace $x$ by $\log(n)$ and get

$$n^a=\Omega(\log(n))$$ and $$n^{a+1}=\Omega(n\log(n)).$$

Needless to say, this implies

$$n^{a+1}=\Omega(n\log(\log(n))).$$
> 2 votes

# Answer
Remove a factor n, then the question is whether $n^{0.03} = O(\log \log n)$. The problem is that $n^{0.03}$ grows very fast, but not for small n, not for large n, but for absolutely huge n.

Assume "log" is the base 2 logarithm. Then for $n = 2^{100}$ we have $n^{0.03} = 2^{100 \cdot 0.03} = 2^3 = 8.$ $\log \log n$ on the other hand is $\log \log 2^{100} = \log 100 \approx 6.9$. Almost the same. If you draw a graph up to the huge $n = 2^{100}$ it looks quite plausible that the answer to your question is yes. Take $n = 2^{1000}$ and now you are comparing $2^{30}$ to $\log 1000 \approx 10$. Take $n = 2^{10000}$ and now you are comparing $2^{300}$ to $\log 10000 \approx 13.1$. $n^{0.03}$ grows faster than the logarithm and the logarithm of the logarithm.
> 1 votes

# Answer
Recall what big-omega means.

$f(n)$ is $\Omega(g(n))$ if there exists an $n\_0$ and a constant $c$ such that for all $n \> n\_0$, $f(n) \ge c\cdot g(n)$.

To satisfy this definition, $n\_0$ can be as large as it needs to be, and $c$ can be as small as it needs to be. Part of the challenge is finding a suitable $n\_0$ and $c$.

As a hint, to get you started:

$$\log\_2 x = \frac{1}{\log\_{10} 2}\log\_{10} x$$

That is, $\log\_2 x$ is $\log\_{10} x$ up to a constant factor. This is part of why, in asymptotic analysis, we can often just say $\log n$ without specifying the base.
> 0 votes

---
Tags: asymptotics, big-o-notation, landau-notation
---


# Question
Title: What is an algorithm that maps back and forth from (x,y) coordinates to the index of that point in a space filling curve over a rectangle?
Suppose that I have a space filling curve over a rectangle of width `W` and height `H`. For example, for the rectangle:

```
W = 4
H = 4

```

I have the following curve:

Now, given the following coordinate:

```
X = 1
Y = 2

```

We can say that its position on the space-filling curve is 7, as it takes 7 steps walking over the curve to reach that tile. Using that logic, we can build a mapping `width → height → x → y → index`, such as:

```
spaceFillingIndex(4,4,1,2) = 7

```

As well as its inverse, `width → height → index → (x,y)`.

```
spaceFillingCoordinate(4,4,7) = (1,2)

```

My question is: what is an algorithm that implements `spaceFillingIndex`, and what is an algorithm that implements `spaceFillingCoodinate`?

# Answer
I found the math behind the hilbert curve very interesting (generates the space filling coordinates, with index) http://www.fundza.com/algorithmic/space\_filling/hilbert/basics/index.html

Python package refer, https://github.com/galtay/hilbertcurve

for rectangles , you need pseudo Hilbert curve generation https://stackoverflow.com/questions/38463130/hilbert-peano-curve-to-scan-image-of-arbitrary-size

and refer this https://github.com/jakubcerveny/gilbert
> 1 votes

# Answer
There is a very commonly used index formula to map between 2d and 1d:

```
for x=0; x<width; ++x
 for y=0; y<height; ++y
   i = x + y * width

```

One option, is to just run this, store the indices, then use the index when needed (unless you want to generate the whole index on the fly)

For example:

```
function spaceFillingIndex(width,height,px,py)
  // if using base 1 indexes:
  i = (px-1) + (py-1) * width
  return i

```

```
// gives answers in the range [0-15]
spaceFillingIndex(4,4,1,2) = 4

```

And

```
function spaceFillingCoordinate(width,height,index)
  for x=0; x<width; ++x
    for y=0; y<height; ++y
      i = x + y * width
      if i == index
        return (x, y)

```

```
spaceFillingCoordinate(4,4,4) = (1,2)

```

Beware, the order in which the above formula goes through the positions in the 2d array, is not continous in space (it scans column by column, but always "jumping" from the max height to height 0)

However, the general structure still applies.

Additionally, you can add a "cache" for the mapping: iterate through all x,y values within width, height, calculate the index for each of them, and store that in a hash, using x\_y as the key

For example:

```
width_height_map = []

for x=0; x<width; ++x
 for y=0; y<height; ++y
   i = x + y * width
   index_name = x + '_' + y
   width_height_map[i] = (x, y)

```

Then instead of spaceFillingCoordinate having to iterate over the whole data every time, you can just do:

```
function spaceFillingCoordinate(width,height,index)
  return width_height_map[index]

```
> -2 votes

---
Tags: algorithms, search-algorithms
---


# Question
Title: Why can't we use computation history to detect looping of a Turing machine on a given input?
First of all, obviously there is a flaw in my logic and I just want to know what it is. So here is my idea: Given a TM M and an input string ω, simulate M on ω on another TM S. For every change of state on M record the TM's configuration. On all iterations compare the new configuration to every other recorded configuration. If there was a match, then the TM is surely not going to halt, at which point we stop the computation and accept or reject accordingly.

# Answer
Detecting whether a machine $M$ is *looping* (meaning that it has reached the same configuration (**not only of its internal state but also of the tape**) twice), is indeed as "easy" as recording the configurations as we simulate $M$ and checking whether the current one was already seen.

This method is of course incapable of deciding whether a machine *will eventually loop*, but rather it detects looping only once it happens, which means that such procedure never tells you *the machine won't ever loop*; only that *it hasn't looped yet*. Note that this is same thing that occurs with the halting problem; it's easy to tell that a machine has halted; the hard part is deciding **whether a machine will eventually halt or not**.

It is worth noting as well that even though **looping $\implies$ not halting**, it's not true that **not halting $\implies$ looping**; for instance a Turing Machine listing all prime numbers on its tape will never halt and yet also never loop...
> 6 votes

# Answer
This method will not detect

```
n:= 0;
while true do
  n:= n+1

```

so it is not universal.
> 4 votes

# Answer
There are two problems: One, a Turing machine doesn't necessarily halt. That's because it has unlimited amounts of state. Your PC with 128 GB of RAM = 1 Terabit only has $2^{1024 \cdot 1024 \cdot 1024 \cdot 1024}$ different states, so it has to reach the same state again.

Two, if you simulate the Turing machine and you havent detected the same state after a year or after a trillion years then you don't know if you will eventually find a repeating state or not.
> 0 votes

---
Tags: computability, undecidability
---


# Question
Title: Latent variable model from measure theory perspective
It's common in machine learning papers to see things like $p(x,z|\theta)$ or $p(x|z)$. Where $x$ is usually the data vector, $z$ the latent vector and $\theta$ the model parameter, like network weights.

However is there a way to make sense of these notations from measure theory's perspective? Perhaps $(x,z,\theta)$ is a random vector from some joint measurable space.

# Answer
You don't need measure theory to understand that notation. Measure theory doesn't really add anything.

That said: Yes, you can in the same way that you can understand probabilities via measure theory, regardless of whether they come from machine learning or anything else. See, e.g., https://math.stackexchange.com/q/4748560/14578, https://math.stackexchange.com/q/393712/14578, https://en.wikipedia.org/wiki/Probability\_measure, https://math.stackexchange.com/q/393712/14578.

The interpretation is that $X,Z,\Theta$ are random variables; we have a joint distribution on $(X,Z,\Theta)$; and $p(x|z)$ is shorthand for either

* $\Pr\[X=x|Z=z\]$, for discrete distributions; or
* the probability density analog of that for continuous distributions, e.g., $f\_{X|Z}(x|z)$ where $f$ is the conditional density function for $X$ conditioned on Z.

None of this requires measure theory, or benefits from measure theory, but I suppose you could describe it using measure theory if you wished.
> 0 votes

---
Tags: machine-learning, probability-theory
---


# Question
Title: What can i say about L1 given that L2, L1L2 and L2L1 are regular?
I found this question in one of our past exams, and I'm not to sure about the correct answer.

I have a language L1 (which i don't know anything about) and another language **L2**, which is regular, the question is: given that **L1L2**, **L2L1** are regular can i also say for sure that L1 is regular?

At first my answer was no, since I cannot say anything about the original languages given their regular concatenation; But then I thought : Wouldn't I be able to extract the DFA or regex for the first language since I have both L1L2 and L2L1?

Thank you for your time and help :)

# Answer
I thought about it a bit after posting the question and came up with a counter-example for the second (and wrong) assumption:

L1 = { 0^p | p is a prime number} (Not a regular language), L2 = 0\* (regular); Both the concatenations are regular since they become L1L2 = L2L1 = { 000\* } ;

Thank you all for the help and for correcting my mistakes :)
> 1 votes

# Answer
Your first answer was right I'd say. Consider **L2** could be $\emptyset$. It's regular and both concatenations are equally regular. We won't learn anything about **L1** though.
> 0 votes

---
Tags: regular-languages, finite-automata, closure-properties
---