# Question
Title: if P=NP, and if language A is not NP-hard, A = ∅ or A = Σ*
I don't know how to solve this. Show that if P=NP, and if language A is not NP-hard, A = ∅ or A = Σ\*

# Answer
Suppose that $\mathsf{P}=\mathsf{NP}$. You can show that the contrapositive statement is true: If $A\neq \emptyset$ and $A \neq \Sigma^\*$ then $A$ is $\mathsf{NP}$-hard.

Consider any language in $B \in \mathsf{NP}$. We will provide a poly-time computable function such that $x \in B \iff f(x) \in A$, thus showing $B \le\_p A$. This will immediately imply that $A$ is $\mathsf{NP}$-hard.

Let $y \in A \neq \emptyset$ and $n \in \Sigma^\* \setminus A \neq \emptyset$. Given $x \in \Sigma^\*$, use the fact that $B \in \mathsf{NP} = \mathsf{P}$ to decide, in polynomial time, whether $x \in B$. If that's the case let $f(x) = y$. Otherwise, let $f(x) = n$.
> 1 votes

---
Tags: np-hard, np
---


# Question
Title: How do I find out what SPACE a language has?
I want to know how I can calculate/find out which SPACE a language has, because I don't get it. I have this definition

> Definition: Fix a function $f: \mathbb N → \mathbb N$. We say that a language $A$ is contained in $\text{SPACE}(f(n))$ if there is a Turing Machine (TM) that decides $x\in A$ vs $x\not\in A$ based on a maximum number of const $\times f(|x|)$ non-blank tape symbols. In the following, mark the strongest assertion that is still true.

I have this question and 4 possible assertions (the same assertion can be selected multiple times).

1. Let $A\subseteq\\{0,1\\}^\*$ be a regular language. i.e. a lanugage that can be decided by a finite state automaton. Then $A\in$

The assertions are:
$\quad$(a) $A\in\text{SPACE}(\log(n))$;
$\quad$(b) $A\in\text{SPACE}(n)$;
$\quad$(c) $A\in\text{SPACE}(n^2)$;
$\quad$(d) $A\in\text{SPACE}(2^n).$

# Answer
As stated by Ordoshsen, if $A$ is a regular language, then: $$A \in \mathsf{SPACE}(1)\subset \mathsf{SPACE}(\log n)\subset\mathsf{SPACE}(n)\subset \mathsf{SPACE}(n^2)\subset \mathsf{SPACE}(2^n)$$ so all answers a, b, c and d are true.

To prove that $A \in \mathsf{SPACE}(1)$, consider a DFA $D = (Q, \delta, q\_0, F)$ such that $A = L(D)$. Consider a two-tapes Turing machine $(Q\cup\\{q\_a, q\_r\\}, \Gamma, \\#, q\_0, \Delta, q\_a, q\_r)$ where:

* $\Gamma = \Sigma\cup\\{\\#\\}$;
* $q\_a\in Q$ is the accepting state, $q\_r\in Q$ is the rejecting state;
* $\Delta$ is defined as follow:
    + for $q\in Q\setminus\\{q\_a, q\_r\\}$ and $a \in \Sigma$, $\Delta(q, a) = (\delta(q,a), a, \rightarrow)$;
    + for $q\in Q\setminus\\{q\_a, q\_r\\}$, $\Delta(q, \\#) = \left\\{\begin{array}{rl} (q\_a, \\#, \rightarrow) & \text{ if }q\in F\\ (q\_r, \\#, \rightarrow) & \text{ if }q\notin F\end{array}\right.$

So the Turing machine read the input word and makes transitions the same way as the DFA, and accept if the state is final when reaching the end of the word, reject otherwise.

This Turing machine use constant space in the size of the input: here, the considered space is the second tape of the machine, which is never used. The input (or the first tape) is not considered in the running space of the machine.
> 1 votes

# Answer
The space complexity is defined for TMs.

You have to come up with an algorithm (Turing machine) that uses as little space as possible and calculate its space complexity.
> 0 votes

---
Tags: turing-machines, space-complexity
---


# Question
Title: Finding a minimum spanning tree that shares the minimum number of edges with the given one
Given some undirected weighted graph $\ G(V,E, w) $ and its minimum spanning tree $\ T$, I need to find another spanning tree $\ T' $ with minimal amount of common edges of both trees. If there are no other spanning trees then $\ T' = T $

I was thinking maybe if I can "subtract" the edges of the minimum spanning tree I was given from the original graph edges and then this subset of edges that I've left with is my starting point for running prim algorithm and if I can not find other MST then any $\ T' = T $ does that make any sense at all ?

# Answer
Instead of "subtract", it is easier to "try to avoid".

---

Sort all edges first by their weights, then by whether they belong to $T$. In other words, for any two edge $e\_1$ and $e\_2$, $e\_1$ precedes $e\_2$ if and only if

* $w(e\_1) \lt w(e\_2)$, or
* $w(e\_1) = w(e\_2)$ and $e\_1$ does not belong to $T$ and $e\_2$ belongs to $T$

The above order can also be realized by just increasing all weights of edges in $T$ by a small enough amount, such as $\frac d2$, where $d$ is the minimum positive difference between weights of any two edges.

Run Kruskal's algorithm or Prim's algorithm as usual using the above order of the edges instead of the usual order which sorts the edges by weights only. Since the edges are ordered by their (original) weights still, we will obtain a minimum spanning tree, which is $T'$.

---

On the other hand, you idea to "subtract" works as well.

Let $S$ be the all edges of $T$. For each edge $e\in S$ from the lightest to the heaviest,

1. remove $e$ from $T$. $T$ becomes two disjoint trees
2. check whether there is an edge other than $e$ of the same weight that connects those two disjoint trees.
    * If we are able to find one, add it to $T$.
    * Otherwise there is no such edge. Add $e$ back to $T$.
3. return $T$, which may or may not have been changed, as $T'$.

However, the algorithm above is harder to implement and probably slower as well.
> 1 votes

---
Tags: algorithms, graphs, minimum-spanning-tree
---


# Question
Title: How to evaluate all the binary sequences, generated from $2^{100}$ for finding all the sequeces which contain minimum $10$ zeros?
Suppose I have a set of $2^{n}$ number of binary sequences. And I have to select only those sequences which contain a minimum ${P}$ number of $0$ in it. For example, please consider the below one

Eg. suppose $n=4$, so the total number of the binary sequence is $2^{4}=16$. And the binary sequences are as follows $0000, 0001, 0010, 0011, 0100, 0101,0110, 0111, 1000, 1001, 1010, 1011, 1100, 1101, 1110, 1111$

Furthermore, let us consider $P\geq3$. Therefore we will select the flowing sequences only

$0000, 0001, 1000$.

Here, the problem is with the value of $n$, if it is large enough, such as $ n\geq100$ and $P\geq 10$. Then how to evaluate all the binary sequences, generated from $2^{100}$ for finding $P\geq 10$?

Currently, I am clueless about solving this issue and looking for an opinion or any thoughts or techniques from you. Please help, if possible.

# Answer
> 1 votes
Let f(n, p) be the number of binary sequences with exactly P zeroes. You just calculate them in the right order and store the results:

```
f(n, 0) = 1 for all n.
f(n, p) = 0 for all p > n.
f(n, p) = f(n-1, p-1) + f(n-1, p) for 1 <= p <= n.

```

Then you add the values f(n,p) for p \>= P to get the number of sequences. Enumerating them is obviously impossible even if n is not very large.

---
Tags: time-complexity, computability, search-algorithms, discrete-mathematics, mathematical-foundations
---


# Question
Title: If the distance to a vertex is updated in the n-th relaxation of Bellman Ford, is that vertex on a negative-weight cycle?
Recently I asked a question Here about following topics:

> after finishing bellman ford algorithm, if BF continue to update distances and distance value related to one vertex v being updated,then v is on negative cycle. \[\***\]

from my counterexample I think this is a wrong sentence.

I see in the implementation of the following problem Here That mentioned:

> The key idea is that if after n−1 relaxations, there is an edge that can be relaxed further then that edge must be on a negative weight cycle.

Author says "that edge must be on a negative weight cycle".

I see also in Here that mentioned:

> That is, some nodes not on the negative cycle now have a distance of negative infinity from the source because of one or more nodes on the path from the source to the node that lie in a negative cycle.

and lastly I read in comments here Comments that one user write:

> All vertices that have their distances updated in the n-th phase must be on a negative weight cycle, no?

My challenge is via different statements, \[\***\] is a correct or not correct sentence?

# Answer
> 2 votes
The statement is not correct. You can use your counter-example from before, and add redundant nodes to it.

Since the bellman-ford algorithm runs iterations equal to the number of nodes in the graph - you will see that nodes that are reachable from a negative cycle (but not on the negative cycle) will *also* get updated.

---

## The correct statement

To clear things up, here is the correct statement:

**Theorem:**

If a vertex $v$ is updated in the extra iteration of the Bellman-Ford algorithm, then there exists a negative cycle $C$, such that $v$ can be reached from $C$ (i.e, there is a path from any node in $C$ to $v$).

**Proof:**

It is well-known that a graph $G$ contains a negative cycle $\iff$ there exists some vertex that is updated in the extra Bellman-Ford iteration.

Let $v$ be the updated node. Then, consider the sub-graph $G'$ of $G$, consisting only of the nodes that can reach $v$.

Let $d^G\_{i}\[u\]$ be the value given to $u\in G$ in the $i$'th iteration of the bellman ford algorithm on $G$, and equivalently $d^{G'}\_{i}\[u\]$ on $G'$. Its not hard to see that for any $u\in G'$, $d^{G'}\_i\[u\]=d^{G}\_i\[u\]$ (i.e, the bellman-ford on $G$ and $G'$ is equivalent).

Therefore, $v$ must also be updated in the extra iteration if we run Bellman-Ford on $G'$, and thus $G'$ must contain a cycle $C$. But $G'$ contains only nodes that can reach $v$ \- so it must hold that there is a path between $C$ and $v$ as required to show.

---
Tags: algorithms, graphs, data-structures, trees, shortest-path
---


# Question
Title: Can 3-SAT be recognized in less than exponential time?
Obviously it is an open question if $3$-SAT can be *decided* in a polynomial amount of time. But what results do we know about its recognizabilty? Can $3$-SAT be recognized in a polynomial amount of time?

# Answer
This problem stays an open problem (at least using the intuitive definition of "recognizable in poly time" - either running in poly time or looping forever).

Consider there is such a TM that "recognizes" $3-SAT$ in "poly-time". Then, let $p(n)$ be the polynomial running time of the TM. Then, we can simulate this TM for $p(n)$ steps - if it halts then we return the answer from it, and otherwise (it didn't halt) we can reject.

Since we know that it either has to halt in $p(n)$ steps or loop forever, and it didn't halt in $p(n)$ steps - we can conclude it will loop forever and thus the input is not in the language.

And here we just built a polynomial Turing machine *deciding* $3-SAT$, which is an open question.
> 2 votes

---
Tags: satisfiability, 3-sat, decidability
---


title: D* Lite - can edge costs be asymmetric?

text:
# Question
Title: D* Lite - can edge costs be asymmetric?
I'm trying to modify the original D\* Lite algorithm adding a margin constraint wrt to any nearby obstacle to be satisfied for each selected cell in the path. This causes the edge cost function between nodes to be asymmetric: let **x** and **y** be 2 adjacent nodes, with **x** being distant to an obstacle less than the given margin, while **y** is far enough and is perfectly traversable. The cost from **x** to **y** is then 1, but the cost from **y** to **x** will be infinite due to the closeness of **x** to an obstacle. I noticed that sometimes the algorithm get stuck in calculating the shortest path and I'm wondering if the asymmetry of the edge costs can be the cause. As for the heuristic, I'm using the euclidean distance which is admissible.

# Answer
> 2 votes
Yes, D\*-lite is a directed graph algorithm, so it works fine with asymmetric edge weights by definition.

However, note that the heuristic being admissible is not sufficient. According to the paper, it must be consistent. Based on what you described, I would guess Euclidean distance would be consistent for your graph, but we can't know for sure without seeing the graph.

---
Tags: algorithms, graphs, shortest-path, a-star-search
---


# Question
Title: find 3 points among some given 2D points such that the triangle includes another given point
Ideally, these would be the points that form the smallest (nondegenerate or degenerate) triangle. However, I can admit a large amount of approximation to get it to a lower order of complexity.

I can do some preprocessing on the given set of $N$ points. Up to around $O(N\log N)$ would be acceptable.

I want to repeat the lookup operation up to N times, so each individual operation would have to be around $O(\log N)$.

---

As Preprocessing, we can find the convex hull of the given points. It can be done in $O(N\log N)$. Suppose the convex hull is polygon $C\_0$, $C\_1$, $\cdots$, $C\_{k-1}$, $C\_k=C\_0$. (The polygon could be degenerated.) Use binary search to find the triangle that contains the given point $P$, or the given point is outside of the polygon. This step takes $O(\log k) $ time.

While the approach above technically solves the problem stated in the title, I don't think it will produce good solutions in most cases, due to the fact that the vertices of the triangle will always be in the convex hull. This will produce quite big triangles. However, this could be the start of a solution, if there is a greedy improvement step afterwards.

# Answer
You can use Clarkson's algorithm to find the smallest (non-degenerate) enclosing triangle in $O(d\log^2 n)$ expected time, where $d$ is the dimension of your input. So, for constant dimensions, it takes $O(\log^2 n)$ expected time. The algorithms is applicable, because the smallest triangle problem is an LP-type problem.

Clarkson's algorithm has many desirable properties that are useful in practice. As a Las Vegas algorithm, it always gives some answer, albeit sub-optimal, if it is stopped early. While the running time is stochastic, the answer will always be correct, given enough time. (cf. Monte Carlo algorithms) The incremental nature of the algorithm makes it easy to handle robustness and input imprecision. Additionally, Clarkson's algorithm is easy to distribute over multiple computing agents, see e.g. our paper here.
> 1 votes

---
Tags: algorithms, complexity-theory, computational-geometry
---


title: Iterable hash table

text:
# Question
Title: Iterable hash table
I'm currently working on implementing all the major data structures from C++ to better understand them and I arrived at the unordered\_map, which should be a hash table implementation (it's actually not) and wondered that even if I implement the hash table, how could I make it iterable?

Let's say I'm implementing the hash table with a contiguous array in which I store the elements. When needed I resize the array and copy the elements over.

Since the positions of the elements are determined by the hash function, I cannot guarantee that each position is filled, but also, when iterating over each position in the contiguous array I don't know if it is filled by an actual element or it's just the default value there.

The only solution I thought of is to have a separate contiguous array of boolean values which determine which slots are filled and which are not, but I don't really like this solution.

Do you know of any other solutions of how to solve this issue, while still retaining the O(1) element access?

# Answer
> 2 votes
gnasher729's solution is often a good one, from a pragmatic perspective. It achieves linear time iteration as long as you ensure that the load factor of the hash table is bounded below by a constant.

Another alternative is to maintain a doubly-linked list of all of the hash slots. In other words, each hash slot also has a "next" and "prev" pointer, which for filled slots points to the next and previous filled hash slot. You can update this doubly linked list in $O(1)$ time whenever you insert or delete an entry into the hashtable. Then, this list makes it easy to do linear-time iteration over all elements of the hash table. In practice this is probably less desirable, because it significantly increases the space requirements, but it is another option.

# Answer
> 2 votes
In most implementations slots must be clearly recognisable as either "never used", "previously used but not used anymore" or "used, containing a hash value". So you just iterate over the stored hash values and use those that are neither "never used" nor "not used anymore".

Execution time is linear in the number of slots. If the number of slots is vastly greater than the number of used slots, it may be time to reduce the size of the hash table.

---
Tags: data-structures, hash-tables
---


# Question
Title: Bin-packing with a capacity constraint on pairs of bins
In the classic bin-packing problem, we have to pack some positive integers into bins, such that the sum in each bin is at most some constant $B$, and subjet to this, the number of bins is minimum.

Suppose now that we relax the capacity constraint: we only require that the sum in each *pair* of bins is at most $2 B$. For example: suppose the inputs are 9, 8, 7, 4 and $B=10$. With a constraint on each bin, we need 4 bins. With a constraint on each pair of bins, we need only 3 bins: {7,4}, {9}, {8}. Note that the sum of each pair of bins is at most 20.

What are some polynomial-time approximation algorithms for the relaxed problem?

WHAT I TRIED:

1. I looked at the Karmarkar-Karp bin packing algorithms. They find, in polynomial time, a solution with at most $OPT+\log^2(OPT)$ bins, where $OPT$ is the minimum number of bins. These algorithms crucially rely on *configurations*. A configuration is a multiset of items that can fit into a single bin (that is, a multiset of integers with sum at most $B$). A configuration for a pair of bins would be a multiset of integers with sum at most $2B$. But here, the constraint is on *every* pair (not just adjacent pairs), and it is not clear how to enforce this constraint. The same is true for most other algorithms that use configurations, such as the ones by de-la-Vega and Lueker, Hoberg and Rothvoss.
2. Let $L$ be the largest sum in the optimal bin-packing. We can find an approximate solution to the relaxed bin packing problem by guessing $L$:

* If $L\leq B$, then we run the KK bin-packing algorithm with capacity $B$.
* Otherwise, $B \< L\leq 2 B$. Every other sum in the optimal packing must be at most $2 B - L$. Then, we run the KK bin-packing algorithm with one bin of capacity $L$ and as few bins as possible of capacity $2 B-L$.

The problem is that this algorithm is polynomial in $B$, which is pseudopolynomial in the problem size.

Is there a polynomial-time approximation algorithm, with guarantees similar to KK bin packing, for the relaxed bin-packing problem?

# Answer
> 1 votes
Let $OPT$ denote the optimal number of bins with original constraints.

Let $OPT'$ denote the optimal number of bins with relaxed constraints.

Note that $OPT' \geq OPT-2$.

Therefore, $KK$ bin packing algorithm also gives a solution to your problem of cost at most $OPT'$ \+ $O(\log^2(OPT'))$.

# Answer
> 0 votes
If I understand this correctly: Instead of packing everything into bins of size 10, I can either fit everything into one single bin of size 20, or into ONE bin of size 10+k plus any number of bins of size 10-k.

For a small size like B = 10, this might be quite easy in many cases: I use a simple algorithm, like first fit sorted, and prove that I can fit everything into n bins of size 10. Assume the total size is \> 20. To get a result better than n, I could try to fit everything into one bin of size 11, and n-2 bins of size 9. This is not possible if the total size is greater than (n-2) * 9 + 11 = 9n - 7. But items with a total size of 9n - 7 would have most likely fit into n-1 bins of size 10. So it may be easy to show that the best solution is indeed with all bins having size 10.

This argument won't work well with large B.

---
Tags: approximation, packing
---


# Question
Title: Computable Numbers and Cantor's Diagonal Method
We were given the following problem in our university:

> We will call $x \in (0; 1)$ **computable** iff there exists an algorithm (e.g. a programme in Python) which would compute the $n^{th}$ digit of $x$ (given arbitrary $n$.)
>
> 1. Prove the set of computable numbers is countable
> 2. Let's enumerate all the computable numbers and the algorithms which generate them (let algorithms be $T\_1, T\_2, ...$) Then we implement an algorithm such that $A(n) \neq T\_n(n)$. So, we got a computable number which is not in the list. But we can't state that the set of computable numbers is uncountable due to point **1**. Explain this paradox.

Here's my solution:

1. Number of programmes is countable $\blacksquare$.
2. So, why *could* Cantor's method work? It would work if this weird $A(n)$ algorithm was actually implementable (our algorithm theory hasn't started yet, so I am just thinking of all these *~algorithms~* as Python programmes, as suggested in the statement). But, given point **1**, I suppose we rather have proven that $A(n)$ is not implementable. \[Alternatively, we can, once again, use **1** to prove the existence of bijection from the computable numbers to $\mathbb Q$. Disproving the incorrect application of the diagonal method to $\mathbb Q$ is a calculus problem, not particularly hard, so I do not want to overburden the post with it.\]

Point **2** seems too shaky (probably due to the excessive use of point **1**.)

So, did I get this right? If not, I would appreciate a hint towards the correct solution.

# Answer
> 2 votes
It looks like you are on the right track. However, some of your statements are not clear. For example, I do not see the relevance of "the existence of bijection from the computable numbers to $\Bbb Q$".

Hint 1.

> As you might have suspected, it is not possible to computably enumerate all computable numbers, although the set of computable numbers is countable and it is possible to computably enumerate all Python programs.

Hint 2, which is almost the simple solution.

> In fact, the application of Cantor's diagonal method as explained in the original problem shows that any *computable* enumeration of computable numbers will miss at least one computable number. Hence, it is not possible to computably enumerate all computable numbers.
> The moral here is that a set is countable does not imply it is a computably-enumerable set. There is no paradox here. In fact, almost all subsets of $\Bbb N$ is not computably enumerable although all of them are countable sets. The number of Python programs are countable. Since a computably-enumerable set can be produced by a python program, the number of computably-enumerable sets are countable. However, the number of subsets of $\Bbb N$ is uncountable.

---
Tags: algorithms, computability, number-theory
---


# Question
Title: Term for the total communicated data over a distributed system
I am looking for a publication-friendly term to describe the total quantity of data communicated between nodes of a distributed system, as invoked by some discrete operation. This term would describe the integral of the bandwidth over time.

For example, if node `0` sends `1 byte` to node `1`, and node `2` sends `3` bytes to node `3`, then the total comunicated data in this transaction is `4` bytes.

The wikipedia page on Bandwidth (computing) includes

> Digital bandwidth should not be confused with:
>
> **Data transfer**: which is the quantity of data transferred over a given period of time.

but this is hardly a 'term' to me, if used like "*the total data transferred is...*"

The closest term I could create myself is "*aggregate payload*", but this might suggest the exclusion of message overheads, according to the Wikipedia definition of Payload.

Is there any nomenclature recognised in the CS community for this kind of thing, or am I stuck with these verbose phrases?

# Answer
Your description is fine: "total amount of data communicated". That is fine.

See also communication complexity, but that's typically used more in theoretical work.
> 1 votes

---
Tags: distributed-systems
---


# Question
Title: Why Prefer Two Stacks to an Array for Undo/Redo?
It seems to be a popular opinion that "the right way" to implement undo/redo is "using a stack." (particularly in the context of an algorithms and data structures interview.)

Here's a GeeksForGeeks article as one reference on this view.

A common variation on this problem is "suppose we want to be able to do many undo or redo operations in a row." (I would argue this feature could be implied in the original question, but it seems that is not the popular view.)

I asked a group about how to solve this and the overwhelming answer from those with a traditional CS background was "use two stacks."

My question here is: Is there any benefit two using two stacks over using an array with a pointer?

It seems to me two stacks is isomorphic to an array with two pointers, but we really only need one pointer so that would be a more efficient approach.

# Answer
> 1 votes
A stack can be, and usually is, implemented using an array and a top-of-stack pointer. It isn't an alternative to an array, but just another (more abstract) way of talking about the array and the specific access pattern needed for this task.

The reason for using two stacks is probably that the undo and redo information for the same change may have different sizes. The most memory-efficient approach is to store only the one that you need, and store it directly on the stack (in the array) rather than allocating a heap object for each change. That means you may end up pushing more or less data than you popped, so you need two pointers.

---
Tags: data-structures, arrays, stacks
---


# Question
Title: Does multiplying word size numbers take constant time?
Does multiplying word size numbers (using standard grade school algorithm) take constant time? Can you use this to speed up computation and do the fast multiplication algorithms use this?

By constant time I mean under the word ram model or whatever model of computation is standard.

I mean in the purely theoretical model how is run-time defined In the word ram model if you fix word size then everything is constant so I'm assuming that you're always given a computer whose bit/word size is logarithmic in your input size please tell me if thats reasonable and if not what should be assumed instead.

# Answer
> 2 votes
For a fixed word size, multiplying word sized numbers takes a fixed maximum time.

If you were to compare implementations with n bit words for n = 8, 16, 32, 64, 128, 256 etc., the amount of time with a fast hardware implementation takes time proportional to log n, with hardware cost proportional to n^2 (that's using n^2 3/2 adders or 7/3 adders which may be just slightly faster). With current technology, having a chip with dozens of 64 bit multipliers is quite affordable.

Using the methods that you learnt at high school, the time for multiplying two n bit numbers is proportional to n^2, with hardware cost proportional to n.

# Answer
> 1 votes
In the word RAM model, data is stored in machine words, whose length is $\log n$; here $n$ is the length of the input, in bits. In this model, arithmetic operations on machine words have unit cost. These usually include addition, subtraction, multiplication, and division. Sometimes logical operations are also included: bitwise AND, OR, XOR.

In his paper How Fast Can We Multiply Large Integers on an Actual Computer, Fürer argues that the word RAM model (which he calls log-RAM) best reflects the performance of fast integer multiplication algorithms in practice. Indeed, for modern CPUs, arithmetic on machine words are atomic operations.

---
Tags: computation-models
---


title: update distance matrix between n points

text:
# Question
Title: update distance matrix between n points
I am looking for an efficient algorithm to update a $N\*N$ matrix, in which the coefficients represents the distance between $N$ number of points, every time that the coordinates of a point change in a 2D Cartesian plane.

Here an example: There are 3 points in a Cartesian plane:

$a=(1,3)$ $b=(3,3)$ $c=(4,1)$

to calculate the distance between $a$ and $b$ I would simply apply:

$d\_{ab} = \sqrt{(x\_b-x\_a)^2 + (y\_b-y\_a)^2}$

the distance matrix would be a $3\*3$ diagonal matrix where the coefficients represent the distances between each point:

$\begin{bmatrix}0 & d\_{ab} & d\_{ac} \\ d\_{ba} & 0 & d\_{bc} \\ d\_{ca} & d\_{cb} & 0 \end{bmatrix}$

My algorithm is pretty straight forward: I nest 2 `for` loops to calculate the distance between each point that are inside the points `array` every time a coordinate change. Here an example in python, but I am not interested in a language specific solution:

```
import math
def distance(a,b):
    x = pow(b[0]-a[0], 2)
    y = pow(b[1]-a[1], 2)
    return math.sqrt(x+y)

points = [[1,3],[3,3],[4,1]]; # cartesian points
distanceMatr = [];
matrixLen = len(points);
for i in range(matrixLen):
    point = points[i]
    row = []
    for j in range(matrixLen):
        d = distance(point, points[j])
        row.append(d)

    distanceMatr.append(row)

print(distanceMatr)

```

If now $a$ moves to $(2,3)$ `points` becomes `[[2,3],[3,3],[4,1]]` and I apply the same algorithm again.

The main problems that I would like to optimise of this algorithm are:

* if the coordinates of $a$ change the distance between $b$ and $c$ doesn't
* the distance $d\_{ab}$ is equal to $d\_{ba}$
* the distance between $a$ and itself is always $0$

Do you have any advice? thank you very much!

# Answer
If the coordinates of $a$ change, you just need to update one row and one column corresponding to $a$, not the whole matrix. This is done in linear time rather than quadratic time in your algorithm.
> 1 votes

---
Tags: algorithms, optimization
---


title: DFA and a Partition of $\Sigma^*$

text:
# Question
Title: DFA and a Partition of $\Sigma^*$
So I'm learning about Myhill-Nerode relations and as an introduction, the book describes possible partitions for $\Sigma^\*$. As an example, given a language $L$, a partition of $\Sigma^\*$ would be $\\{L, \overline{L}\\}$.

Suppose there is a DFA for $L$, the book continues by creating the following notion: For a $q \in Q$ (where $Q$ are the states in the DFA), the set $reach(q)$ is a subset of $\Sigma^\*$:

$reach(q) = \\{w \in \Sigma^\*$ $ |$ $\delta^\*(q\_s, w) = q\\}$

i.e. The set of strings that bring you from the starting state $q\_s$ to $q$.

Then it is said that $\\{reach(q) $ $|$ $q \in Q\\}$ is a partition of $\Sigma^\*$ if every state $q$ is reachable from $q\_s$ and for every $q \in Q$ and every symbol $a \in \Sigma$, the transition $\delta(q, a)$ is defined.

I don't see how this creates a partition of $\Sigma^\*$ and certainly not how to prove this. Any help is appreciated.

# Answer
> 0 votes
Reminder: a family $S\_1, …, S\_n$ is a partition of $S$ if and only if it verifies three properties:

* for each $i$, $S\_i \neq \emptyset$;
* for $i \neq j$, $S\_i\cap S\_j = \emptyset$;
* $\bigcup\limits\_{i=1}^nS\_i = S$.

I will give you hints for each of those points:

* the first point is proved using the fact that each state $q\in Q$ is reachable from $q\_s$;
* the second point is proved using the fact that the automaton is deterministic;
* the third point is proved using the fact that $\delta(q, a)$ is always defined for all $q\in Q$ and $a\in \Sigma$.

Hope that helps!

---
Tags: formal-languages, finite-automata, sets
---


# Question
Title: Minimum number of intervals to cover all possible colors
Given $n$ points in $\mathbb{R}$ each colored with one of following three colors $$C=\\{c\_1, c\_2, c\_3\\}.$$ In polynomial time, Choose the minimum number of intervals of length $1$ each containing some of $n$ points such that from each color, $c\_i$ ($1 \leq i \leq 3$), there is at least one point in one of chosen intervals.

I assume if the number of colors was a parameter of the problem (like $n$), it could be proved that it is in NP. Then by reducing Set Cover to the above problem, it would actually become an NP-Complete problem too. But I hope by setting a restriction on number of colors (here number of colors is restricted to $3$) the problem can be solved in polynomial time, yet I have not found any polynomial solutions.

# Answer
The trivial solution concluded from the comments is as follows.
Order (~$O(n\log{n})$) the given points as $P=\[p\_1,...,p\_n\]$, such that $$i \< j \iff p\_i \< p\_j$$. By iterating from $p\_1$ to $p\_n$ in $O(n^2)$ find all possible intervals of length 1 store them as a tuple of $(\text{subarray of points they contain}, \\#\text{unique colors they contain})$.
As the minimum number of intervals can be either.

* 1: one interval with $\\#\text{unique colors they contain}=3$,
* 2: two intervals one with $\\#\text{unique colors they contain}=2$ and one with $\\#\text{unique colors they contain}=1$ (with no common color between two intervals),
* 3: three intervals each with $\\#\text{unique colors they contain}=1$ with (no common color).

Check cases 1, 2, and 3 (each in $O(n^2)$) one after another. in worst case the problem can be solved with 3 intervals and in $O(n^2)$.
> 1 votes

---
Tags: algorithms, np-complete, polynomial-time
---


title: Max-Min Weighted Matching

text:
# Question
Title: Max-Min Weighted Matching
The maximum weighted matching problem (https://en.wikipedia.org/wiki/Maximum\_weight\_matching) finds a matching in a weighted graph that has maximum sum of weights. I was wondering if there are any existing approaches to find a matching that maximizes the minimum weight? (Can't seem to find any similar references on this)

# Answer
I believe this is known as the "bottleneck matching" problem. Here is an algorithm for that problem.

There is a straightforward algorithm. Pick a threshold $t$. Delete all edges with weight below $t$ and check whether there is a matching in that graph. Now do binary search on $t$, to find the largest $t$ such that the resulting graph has a matching. This requires $O(\lg n)$ executions of a graph matching algorithm, and thus can be done in polynomial time.

I think there may be dedicated algorithms in the literature that may be even faster, but I'm not knowledgeable abou that.
> 1 votes

---
Tags: graphs, weighted-graphs, matching, bipartite-matching
---


# Question
Title: SLR(1) Table construction, FIRST and FOLLOWS
when constructing the SLR(1) table for some grammar I need to compute the FOLLOW set for all terminals in order to decide where and when to reduce.

Do I compute theme for the augmented grammar or the original one?
Is there even a difference?

# Answer
In SLR(1) parser you need to compute only the follows of non-terminal symbols. When you have to put a reduce in the table, you look at the follows of the head of the production, and then put the production only in columns(correspond to terminals) that are in the follows.
> 1 votes

# Answer
by augmented grammar I am assuming the production rule `S'->S`. The purpose of augmented grammar is just to make the process of computing the go-to graph homogeneous for all nodes, it actually isn't a part of the grammar, so you dont need to compute its follows. Even if you did, it won't matter unless you are taking it as a part of the grammar, which in case changes the grammar itself.
> 0 votes

---
Tags: context-free, parsers
---


# Question
Title: Which particular data structure should I use if I want a persistent balanced search tree?
As title, I'm trying to implement a text editor with the rope data structure, which is backed by binary search tree.

Since I want it to have persistent undos, the underlaying data structure should also be persistent.

I know that there is an candidate like randomized immutable treap, I'd like to know if there are other candidates.

# Answer
> 0 votes
There are many data structures for balanced search trees; pick any one. Then, you can make it persistent using path copying, or Driscoll, Sarnak, Sleator, and Tarjan's technique -- these techniques are generic and can be applied to any tree data structure.

---
Tags: data-structures, balanced-search-trees, binary-search-trees, persistent-data-structure
---


# Question
Title: division expression in tuple relational calculus
Could someone please explain the expression for division in tuple relational calculus in words? I do not understand how the multiple operators (existential and universal quantifiers) are to be interpreted.

My question is almost the same as Division in tuple relational calculus but there is no response to this.

# Answer
> 0 votes
Since you aren't clear on how to interpret the quantifiers lets start with them.

The existential quantifier  means there is *atleast one object in a set(finite/infinite) that satisfies some given condition/property*. For example if we consider the **set of all people alive on earth(PE)** we can say that there exist some **people(P)** such that they are females, which using quantifiers would be written as follows

> ***∃ P ∈ PE | P=female or ∃ P ∈ PE (P=female)***

which literally translates to

> there exist people P(∃ P)
>
> belonging to the set of all people alive on earth (∈ PE)
>
> such that (|)
>
> P is a female (P=female)

Similarly it goes for the **universal quantifier ∀**, in which case the *property has to be followed by all the members of the set*. Even if one member doesnt follow, the statement loses its truth value (universal quantifier doesn't hold true, existential may hold depending on the property). For example the closure property on the set of integers for the addition operation

> ***∀ X,Y ∈ Z (X + Y ∈ Z)***

which means

> For all X,Y belonging to integers, X + Y belongs to integers.

Now coming to tuple relational calculus the division operator is defined as

> ***{t | ∃ p ∈ R ∀ q ∈ S (p\[B\] = q\[B\] ⇒ t\[A\] = p\[A\])}***

Over the relations(tables) R(A,B) and S(B)

which means

> t is a tuple such that there exists p belonging to R and if p\[B\] = q\[B\] then t\[A\] = p\[A\] (assuming you know how to interpret other symbols)

that is if the condition **p\[B\] = q\[B\]** becomes true the tuple p\[A\] gets added to the result set of division operation.

One thing can be known from this. For a division operation R ÷ S to be meaningful the set of attributes of S should be a subset of R (think what would happen if its not a subset).

Now this operation be simply understood as

> ***For all tuples in S, search for such tuples in R which have all tuples of S as a part of them and they have the same value for attributes except those that belong to S i.e same value for R\[attributes(R)-attributes(S)\]. Think of it as a group by in SQL***.

Consider the following tables R and S

| R | R |
| --- | --- |
| A | B |
| 1 | a |
| 1 | b |
| 2 | b |
| 3 | c |
| 4 | d |
| 5 | d |
| 6 | b |
| 6 | c |
| 6 | a |
| 2 | c |

| S |
| --- |
| b |
| c |

| R ÷ S |
| --- |
| A |
| 6 |
| 2 |

now lets see how we got here, S has b,c as its tuples, so you look for such tuples in R which have all the values of S and the same value for R\[(A, B) - (B)\] = R\[A\]. Clearly, 1, 3, 4, 5 don't match this criterion and hence are rejected. 2 matches exactly so it is included in the result set. What about 6? it matches too, it has an extra tuple associated with a but that doesn't break the definition and hence, is a part of the result set. 1 is associated with b but not c and hence, rejected.

---
Tags: tuple-relational-calculus
---


title: Is Python truly OOP?

text:
# Question
Title: Is Python truly OOP?
My understanding is that a programming language is generally paradigm (functional, procedural, OOP) independent: we can code using different paradigms in some language. However, some languages, like Java, seem to require the developer to code only in OOP. And the language C does not even support OOP.

In regards to Python, everything (variable, function, module, list, etc.) seems to be an object, i.e. an instance from a class. But we can certainly code in Python without creating classes, etc...So is Python intrinsically OOP even if we don't necessarily have to code with the OOP approach? Could we say that is OOP but less OOP than Java?

Thanks for any clarification.

# Answer
> 3 votes
Indeed: Python supports OOP, but unlike Java, doesn't enforce it. So that seems the most accurate statement regarding the matter.

Based on this, it makes sense to say that *Python is OOP but less so than Java*, or *Python is not OOP but supports it*; but why would you?

* These statements are vague. They invite confusion. Why not just say what you mean instead of hinting at it?
* These statements suggest that there is some benefit or value in trying to grade languages by OOP-ness. This invites debate, but what's the point? Can you think of a benefit of trying to grade languages by OOP-ness, from a computer science perspective? I do understand its use as a device for attracting eyeballs to an article, but clickbait theory is off-topic here.

# Answer
> -1 votes
There are 2 interpretations of the term OOP.

Consider the scenario where you are developing you own programming language. There are several phases of compiling a program and internal modules to provide support and you have implemented them in an OOP fashion, but the programming language you intend to develop doesn't enforce OOP paradigm while writing programs, so in this case the core features are done in an OOP fashion but the language isn't. Similarly there can be other cases too (it gets complicated diving into cross compiling and bootstrapping). An example of this is python, which has its interpreter implemented in many languages like C (procedural) and java(object oriented) but python itself supports both paradigms and doesnt enforce to use any one.

So in short, OOP can mean 2 things, either the language was implemented in an OOP fashion or the language asks you to program in an OOP fashion, and mostly the latter suits the OOP ideology better.

---
Tags: python
---


# Question
Title: The maximum decimal integer that can be stored in memory of 8-bit word processor computer?
Actually i am preparing for an exam and in the last year exam this que. was been asked. *i.e*

**The maximum decimal integer number that can be stored in memory of 8-bit word processor computer ?**

a) **(128)10**
b) **(127)10**
c) **(129)10**
d) **(255)10**

Answer of this que. as given in the answer key is **b) 127**. And I have no idea how they arrived at this result.

Acc. to my understanding, we have 8-bits, which is **28 = 256** so **255** should be the maximum integer which we can store.

**EDIT** \- An another very similar que. asked in same exam was

**The maximum permissible integer in a computer with n-bit word processor and one word per integer is equal to**

a) **2 n - 1 \- 1**
b) **2 n \- 1**
c) **2 n - 1 \+ 1**
d) **2 n \+ 1**

Its ans. is **a) 2 n - 1 \- 1** (acc. to official ans. key).

By putting n = 8 from above que. we got the answer 127. But again i am clueless how did they derived this answer too.

# Answer
> 0 votes
The following is the reasonable verdict, I believe, given no more context, as said by Steven's comment and harold's comment.

The maximum (decimal) integer that can be stored in memory of 8-bit word processor computer depends on the context, that is, whether we are talking about unsigned integers or signed integers.

According to this Wikipedia page on 8-bit computing,

> There are $2^8$ (256) different possible values for 8 bits. When unsigned, it has possible values ranging from 0 to 255; when signed, it has -128 to 127.

The natural answer, without no more context, should be $2^8-1=255$. We have not seen any computer processor that interprets an 8-bit sequence (in a basic level, just to be safer) as an integer that is more than 255. On the other hand, almost all computer processor today can interpret an 8-bit sequence as an (unsigned) integer as large as 255 . In fact, as said in this nice answer of Kristian H,

> Unsigned numbers are one interpretation of a sequence of bits. It is also the simplest, and most used interpretation internally to the CPU because addresses, and op codes are simply bits. Memory / Stack addressing and arithmetic are the foundations of microprocessor, well, processing. Moving up the abstraction pyramid, another frequent interpretation of bits is as a character (ASCII, Unicode, EBCDIC).

---

Having said the above, let me come to defend the choice of the author of that exam, even though I would NOT phrase the question and answer suite as presented in the question.

The question in the exam was designed to test a student's basic understanding of the representation of numbers in our binary computer processors.

If a student chooses, presumably for some good reason, "b) **(127)10**", we can be confident that student knows the very basic about the representation of a signed integer by two's complement. One bit out of that 8 bits must be used to represent the sign. Somehow, the range of positive integers is one less than the range of negative integers. So, the maximum signed integer in 8 bits is $2^{8-1}-1$. We can be confident that student would know the maximum unsigned integer can be represented in 8 bits could be $2^8-1=255$.

However, if a student chooses "d) **(255)10**", it might be hard to justify that student knows what happens with signed integers. So, if the exam is aimed at checking how much students have learned, choice b) could be appropriate.

So, in the context of an exam, a student would have a better chance to be considered more knowledgeable if choice b) is selected instead of choice d). Or a better chance to gain a better grade.

---

Once again, let me emphasize harold's verdict, "that is not a reasonable question". Ideally, for the intended choice of b), the question should be "the maximum signed integer that can be stored in memory of 8-bit word processor computer?"

---

For a detailed explanation of two's complement, please check this Wikipedia page.

# Answer
> 1 votes
I got the same question in my technical informatics exam. The right answer was also 127, my professor explained signed integer is the default format, therefore the range would go from -128 to 127. You can display 256 distinct value, but the maximum would still be 127.

# Answer
> 1 votes
With a single 8-bit word, you can represent 256 different, distinct values. However, there is nothing in the first question that restricts you to use only one word, you can use however many words you like. With two words, you can already represent 65536 values, with 42 words, we could already represent every particle in the universe. Therefore, the maximum integer that can be represented is *arbitrarily large*, or put another way *there is no maximum integer*.

The second question restricts you to use a single word, but there is still a problem: we now know, we can only represent 256 distinct values, but the question doesn't tell us anything about how those values are encoded. For example, the ISO8859-1 encoding of characters can represent the international generic currency sign (`¤`) as one of the 256 values, but it cannot represent the Euro sign (). ISO8859-15 on the other hand, can represent the Euro sign but not the generic currency sign, and neither can represent the Bitcoin currency sign .

The same goes for numbers: with 8 bits and an unsigned unary encoding, I can represent the numbers from 0 to 8. With a signed unary encoding, I can represent the numbers from -3 to +3, including both -0 and +0. With an unsigned unary encoding offset by 42, I can represent the numbers 42 to 50.

Regardless of whether I use a signed or unsigned, unary, binary, decimal, or some other encoding, I can always represent arbitrarily large numbers by introducing an offset in my encoding.

So, again, also for the second question, it is impossible to give the answer.

To answer the second question, we would need to know the encoding, to answer the first question, we would need to know the encoding and the memory size.

# Answer
> 0 votes
In 8 bits the total number of integers that we can store are 256 i.e -128 - 127 including zero in positive.

For representation of positive numbers the MSB(Most Significant bit) is always zero 01111111 and for negative numbers the MSB remains 1.

---
Tags: computer-architecture, cpu, memory-hardware, memory-access, memory-allocation
---


# Question
Title: What would be a pseudocode of try-catch pattern, common in generally all programming languages?
What would be a pseudocode of try-catch pattern, common in generally all programming languages?

**Perhaps the following?**

```
Try X,
If you catch Y (success) than continue,
If you didn't catch Y (bug),
Either,
Do nothing || throw an exception (error)

```

# Answer
Just copy what you found in *some* language. As long as it is reasonable clear it’s fine. For example

```
Do
    Statement 1
    Try statement 2
    Try statement 3
    Statement 4
    Throw some exception
Catch exception type 1
    Actions
Catch exception type 2
    Actions
Catch
    Re-throw exception
End do

```

So you have one block covered by catch blocks, containing statements that can or can’t throw exceptions, handling for different classes of exceptions, “throw” to throw an exception and “rethrow” for throwing an exception that was just caught instead of handling it.

This is modelled on Swift which doesn’t allow surprising exceptions.
> 1 votes

---
Tags: pseudocode
---


title: Subtraction on Big Theta notation

text:
# Question
Title: Subtraction on Big Theta notation
This is a question I got for an assignment, and I have been stuck on it for the past few days.

Prove that $\Theta(n)+\Theta(n-1) = \Theta(n)$

Does it follow that $\Theta(n) = \Theta(n)-\Theta(n-1)$

I was able to prove the first part but I am getting stuck in the second part. If someone could help me out with this I would be very grateful.

# Answer
> 1 votes
First, let us explain what the sentence $$ \Theta(n) + \Theta(n-1) = \Theta(n) $$ means. It means the following:

> If $f(n) = \Theta(n)$ and $g(n) = \Theta(n-1)$ then $f(n) + g(n) = \Theta(n)$.

(If you're more pedantic, you should replace $=\Theta(\cdot)$ with $\in \Theta(\cdot)$. The notation isn't symmetric. Similarly, the original sentence could have $\subseteq$ in place of $=$.)

You can prove this directly using the definition of $\Theta(\cdot)$:

> $\phi(n) = \Theta(\psi(n))$ if there exist $c,C,N\>0$ such that for all $n \geq N$: $c\psi(n) \leq \phi(n) \leq C\psi(n)$.

(We tacitly assume that $\psi(n)$ is eventually positive, and $N$ is implicitly assumed to be chosen so that $\psi(n) \> 0$ whenever $n \geq N$.)

---

Now, let us consider your second sentence: $$ \Theta(n) = \Theta(n) - \Theta(n-1). $$ This sentence means that if $f(n) = \Theta(n)$ then there are $g(n) = \Theta(n)$ and $h(n) = \Theta(n-1)$ such that $f(n) = g(n) - h(n)$. This also holds: you can take $g(n) = 2f(n)$ and $h(n) = f(n)$.

However, the right-hand side $\Theta(n) - \Theta(n-1)$ is not so useful, since we cannot say too much about its rate of growth. For one, it is not necessarily eventually positive; but even if we consider its magnitude, all we can conclude is that it is $O(n)$. Due to these reasons, you are unlikely to see a difference of two asymptotic notations, unless the subtrahend is asymptotically smaller than the minuend (and even then, you ought to be very careful).

---

Here is the general case: if $X$ is an expression involving asymptotic notations $\Upsilon(F\_i)$ (where $\Upsilon \in \\{O,\Omega,\Theta,o,\omega\\}$ could depend on $i$) and $Y$ is an expressions involving asymptotic notations $\Upsilon(G\_j)$, then $X=Y$ has the following meaning:

> If $f\_i = \Upsilon(F\_i)$ for all $i$ then there exist $g\_j = \Upsilon(G\_j)$ for all $j$ such that $$X\[\Upsilon(F\_i)/f\_i\] = Y\[\Upsilon(G\_j)/g\_j\].$$

Here $Z\[s/t\]$ denotes the substitution of $t$ for $s$ in $Z$.

---

One more bit, just to confuse you even further: sometimes asymptotic notation refers to *magnitudes* of expression. For example, $-n = \Theta(n)$ under this convention. In that setting subtraction makes a bit more sense — but just a little bit.

---
Tags: algorithm-analysis, asymptotics, proof-techniques, big-o-notation
---


title: How to simulate an NTM using a DTM?

text:
# Question
Title: How to simulate an NTM using a DTM?
I've seen questions about how an NTM could simulate a DTM and this seems pretty straightforward to me. However, my text book says you can also simulate an NTM using a DTM.

How would this work? I'm especially curious on how to define the transitions, since in the DTM, each transition would have to be deterministic.

# Answer
> 1 votes
You use dovetailing to simulate all possible execution paths of the NTM.

---
Tags: turing-machines, nondeterminism
---


# Question
Title: Define a directed edge in a DAG using partial ordering
I am trying to describe a novel type of DAG's construction algorithm. The directed edges of the graph corresponds to a partial ordering: i.e. any directed edge $e$ spanning from $f$ to $t$ also observes: $f \preceq t$.

Q: How can I precisely define the main task of edge construction: that is finding the node $f$ for a given $t$?

It is something like this:

find all $f\_a \in \\{ f\_i \\}$ s.t. $f\_a \preceq t$ $\land \nexists f\_j$ s.t. $f\_i \preceq f\_j$

but I'm not sure if this is sufficient or even understandable?

### Some Background

Without getting too specific: the DAG itself is that of an executed program, and is used for dynamic runtime analysis. Each node represents the execution of some event, while an edge $e = f \rightarrow t$ means that $f$ triggered $t$.

# Answer
If you represent the DAG as an adjacency list, where each node links to all of its predecessors, you can find all predecessors by iterating over that list.

If you represent the DAG as an adjacency list, where each node links to all of its successors, you can easily construct a list of predecessors in a linear-time (iterate over all nodes and all successor lists, and create the predecessor lists). Then see above.
> 0 votes

---
Tags: graphs, runtime-analysis, partial-order
---


# Question
Title: Are turing machines & equivalents with infinite sized random programs still turing machines?
Are turing machines with an infinite program tape that is completely random, or another example is a Game of Life simulation on an infinite randomly initialized grid, still turing machines, so to speak?

edit: if this is the wrong place to ask this(?) remove it

# Answer
> 1 votes
They are still turing complete. Here is some intuition for why:

You can manually "clear", say, the first $100$ positions by replacing them with a blank. Then, we can "split" the tape into two parts by writing a special character $\\#$, for which the first half are all of the tape contents before the first occurrence of $\\#$ and the rest of the tape is everything else.

We can now consider the first part of the tape to be a "cleaned out" tape, like a usual TM would have. When we run out of space, we move $\\#$ a few cells forward (any constant number you really want) and set the memory it the area it was before to $\sqcup$ (effectively allocating a constant extra memory and then clearing the contents out).

---
Tags: turing-machines, computability, randomized-algorithms, randomness, probabilistic-algorithms
---


# Question
Title: If the Pushdown-Automaton for a language is deterministic, is the language non-ambiguous?
For a given context-free grammar (CFG) you can always construct a pushdown automaton PDA (and vice-versa). This pushdown automaton is possibly non-deterministic, since for a non-terminal $X$ in the CFG, there might be multiple rules of the form $X \rightarrow \gamma$.

The book I am using says that this looks like it could lead to ambiguity in the language, but that this isn't the case. My first question is why this is. To me at least, it seems like this should imply ambiguity.

Following this the book states the question "If there is a deterministic PDA that determines a language $L$, is $L$ non-ambiguous?". I can't see how you could argue this to be true (or false) or how to construct a proof for it. With ambiguity being the existence of multiple left/rightmost derivations for a given input string.

# Answer
Basically, the statement is true: when we have a deterministic PDA for a language $L$, we can construct a non-ambiguous grammar for $L$.

The notions of determinism and non-ambiguity are related, but we should be cautious. Determinism for PDA is a kind of 'local' property: In each configuration (state, input symbol, top of stack) the PDA has only a single possible continuation. Non-ambiguity is more 'global': for each word in the language the grammar has only a single derivation tree (or equivalently, a single leftmost derivation).

The two notions are not equivalent: the language of palindromes over a two-letter alphabet does not have a deterministic PDA (it cannot determine when to switch from pushing to popping) but it has a very simple non-ambiguous CFG.

In fact the 'standard' construction from PDA to CFG translates a deterministic PDA into a non-ambiguous grammar. By the construction each leftmost derivation will correspond to a PDA computation. As the deterministic PDA has only a single computation, there will be only a single leftmost derivation.

The above is the basic observation, but unfortunately it is not true if we do not take some technical precautions. First, the standard construction works if we start from a PDA that accepts by empty stack, and not the usual accaptance by final state. This is a restriction, languages accepted by empty stack are necessarily prefix-free (if a string is in the language, none of its prefixes are). Second, the observation that a deterministic PDA has only a single accepting computation, is not completely true: after accepting the automaton may keep computing with $\epsilon$-moves, and accept the same input again.

Both these problems can be avoided by considering the language $L{\\\\$}$ instead of $L$. Here ${\\\\$}$ is a special end-marker. Using the end-marker the PDA can be instructed to clear its stack, and we have empty stack acceptance. Then we obtain a non-ambiguous CFG from the deterministic PDA. Finally we may drop $\\\\$$ from the grammar, without really changing the derivations, so without causing ambiguity.
> 3 votes

---
Tags: automata, context-free, pushdown-automata
---


# Question
Title: Is there an OS with capability to freeze/unfreeze any app?
I'm looking for an operating system (commercial opensorce or any) which can **freeze** any currently running application (video/audio playback, a game etc.).

While the app is frozen the OS must be able to show some windows (maybe some information to the user) or play some sound etc. In other words the apps are frozen and you can't do anything with them but the OS itself is functional and able to interact with the user.

Ofcourse the consequent **unfreezing** must be without any loss of app's state if it is possible (the game is not an online multiplayer game where you buddies are long time gone from the place you were at the moment of freezing).

P.S. The questiong is a bit vauge since I don't know the language of OS devs. Maybe this runtime freezing has a special name?

# Answer
> 1 votes
Every pre-emptive multitasking OS has this capability: to freeze a process, once the process finishes its current time slice, simply don't reschedule it again until it is unfrozen.

See also https://en.wikipedia.org/wiki/Computer\_multitasking and SIGSTOP on Unix.

---
Tags: operating-systems
---


# Question
Title: What happens if we change $\mathcal{BQP}$ to allow quantum bits, but not quantum gates?
In the definition of the class $\mathcal{BQP}$ found in textbooks we (as the circuit builders) have access to an unlimited number of deterministic zero-initialized qubits and to a finite set of quantum gets (it turns out that some sets of gates are universal). I'm struggling to make the definition of $\mathcal{BQP}$ intuitive for me and to figure out which parts are essential. What would happen if we were to only allow the Toffoli gate (which is universal for classical computation) and an unlimited number of qubits, each with a state chosen from a finite set? The question arises, are some sets of qubits universal, that is no other set induces a bigger complexity class? If so, what is this maximal complexity class?

When going from deterministic to randomized computation it is enough to have random bits and no random gates, and $\mathcal{NP}$ could I think also be defined in terms of "nondeterministic" bits, so that makes me wonder if the same can be done for quantum computation (and if, as I expect, not, then why not).

# Answer
> 1 votes
This is universal for BQP, unless you put strong restrictions on the allowed measurements.

To start with, if you apply the Toffoli to a target qubit in the $\lvert-\rangle$ state, you get a Controlled-Z (CZ) gate.

Using the CZ gate and initial $\lvert+\rangle$ states, you can create the cluster state (in fact, on any lattice of your liking).

Once you have the cluster state, you can carry out universal quantum computations in you allow for measurements in a discrete set of directions in the XY-plane. (You don't need Z measurements if you create the cluster state on the right graph right away.)

Finally, I suspect that you could even further restrict the required measurements - I would strongly suspect down to only an X measurement. The idea would be to create the cluster state "on the fly" as you measure, and then start from a suitably rotated state in the XY plane rather than the $\lvert+\rangle$ state; this should effectively give you the ability to measure in any direction in the XY plane you want. (There's a subtlety that you have to make this choice before you measure the preceding site, but I don't think this matters.)

On the other hand, measuring in the Z basis only is indeed efficiently simulatable classically, since the Z measurement can be "pushed" through the Toffolis, to give another Z measurement on the initial product state with some classical relabeling of measurement outcomes.

---
Tags: complexity-theory, quantum-computing
---


title: Disjoint Set deletion

text:
# Question
Title: Disjoint Set deletion
The wikipedia entry for disjoint set data structure includes the statement (in the "Applications" section)

> Note that the implementation as disjoint-set forests does not allow the deletion of edges, even without path compression or the rank heuristic.

Is the article trying to say that a deletion is not possible with a similar time complexity as the optimized find/union (Inverse Ackermann function as the amortized running time)? Because a blanket statement that deletion is not possible seems like a stretch. There's nothing inherent in the data structure that prevents a deletion operation as long as it restructures the forest. It would be expensive when operating on a non-flattened set, but that isn't the same as not being possible.

Or am I overlooking something that (for instance) would make edge deletion an NP operation?

# Answer
The tree structure of a Disjoint Set doesn't have enough data to perform a deletion.

There are many different graphs that produce the same Disjoint Set representation. E.g. if the graph contains 3 nodes `a`, `b` and `c`, and the Disjoint Set looks like `a -> b -> c` (`a` parent of `b` and `b` parent of `c`), then we could have a path graph with just two edges `a - b` and `b - c`, or a cycle graph with the edges `a - b`, `b - c` and `c - a`. And if you remove the edge `a - b` you either split the graph up into two components in case of the path graph, or keep it in one component in case of the cycle graph.

If you add more information to the Disjoint Set, then you could delete nodes. E.g. if you remember all added edges, then you can of course recompute the data structure after every deletion. But that of course ruins your runtime, in the case you delete a lot of edges. And it's definitely more than just a Disjoint Set.

There are of course more clever solutions. E.g. a fun one is described here: https://cp-algorithms.com/data\_structures/deleting\_in\_log\_n.html If you know all operations (additions, deletions, check-if-same-set queries) beforehand (so processing the operations **offline**), you can perform every add/delete operation in $O(\alpha(n) \log(n))$, by changing *adding* and *deletion* operations into just *adding for a certain timespan* operations, and then building a Segment tree over time. But again, it's now more than just a Disjoint Set, it's a more complicated data structure with more information.
> 1 votes

# Answer
That's a confusing statement indeed. I think the following is likely the intended interpretation:

Suppose we are building up an undirected graph by adding edges one at a time, and we want to keep track of the connected components of the graph. You can think of this as supporting one operation: AddEdge. Then a reasonable algorithm is to use union-find to keep track of the components, and this will be very efficient.

What if we want to delete edges too? You can think of this as supporting two operations: AddEdge and DeleteEdge. Then there is no longer a direct, efficient way to handle this (to track the component components) in this scenario. One crude approach might be to track connected components using union-find, update the union-find data structure whenever an edge is added; and if an edge is deleted, discard the entire union-find data structure and build it up from scratch again. Obviously, this would be slow and inefficient. It also requires keeping track of all of the edges that were previously added. Moreover, if you separately haven't kept a record of all edges that were previously added, then it is impossible, as the union-find data structure alone does not have enough information to determine what are the remaining edges.

So, "does not allow" could be interpreted as "does not allow, with similar efficiency, even with modifications to the algorithm", or it could be interpreted as "does not allow at any time efficiency, without modifications to the algorithm, because without modifications there is not enough information retained".
> 1 votes

---
Tags: trees, disjoint-sets
---


# Question
Title: What does "lambda terms modulo convertibility" mean?
In "The Lambda Calculus - Its Syntax and Semantics" by H.P. Barendregt (WorldCat) is this statement, the first sentence of chapter 2 after the introduction chapter, so in a way this sets the tone of the book and is useful to understand.

> The principal object of study in the λ-calculus is the set of lambda terms modulo convertibility. (p. 22)

Then a few paragraphs later is found *convertibility*. (p. 23)

> The basic equivalence relation of λ-terms is that of *convertibility*. This relation will be generated by axioms. In order to formulate these axioms, a substitution operator is needed. **M\[*x* := N\]** denotes that the result of substituting **N** for ***x*** in **M**. ...

Then for 2.1.4 Definition ...

> Provability in λ of an equation is denoted by **λ ⊢** ***M = N*** or often just by ***M = N***. If **λ ⊢** ***M = N***, then ***M*** and ***N*** are called *convertible*.

What does "lambda terms modulo convertibility" mean?

Based on a comment for this question it seems a different synonym for *modulo* would clear things up.

---

In reading TAPL (Types and Programming Languages) by Benjamin C. Pierce (WorldCat) one can get an understanding of axiom with regards to λ-calculus so no need to explain that.

# Answer
Saying that you consider ⟨*objects*⟩ modulo ⟨*equivalence*⟩ means that you treat equivalent objects as equal. This implies that the only properties of the objects that you're interested in are the ones that are invariant under this equivalence, the only functions you're interested in are the ones that turn equivalent objects into equivalent ones, etc.

Formally speaking, this means that you're actually studying equivalence classes for the given equivalence relation. In this case, the equivalence relation is the existence of a chain of alpha-conversions (variable renamings) and beta-conversions (replacing a function call by the result of applying the function) between terms. So whenever Barendregt writes e.g. $\lambda x.(\lambda y.y)x$, what it really means is “the set of lambda terms that are $\beta$-equivalent to $\lambda x.(\lambda y.y)x$”, i.e. the infinite set $\\{\lambda x.x, \lambda y.x, (\lambda x.x)(\lambda y.y), \lambda x.(\lambda y.y)x, \lambda u.((\lambda x.x)((\lambda y.y)u)), \ldots \\}$. And when $M$ and $N$ are two lambda terms, $M = N$ means that $M$ and $N$ are members of the same equivalence class.
> 4 votes

# Answer
"lambda terms modulo convertibility" is an informal phrase that means "lambda terms, but we don't make any distinction between any two lambda terms that are convertible".
> 2 votes

---
Tags: terminology, lambda-calculus, types-and-programming-languages
---


# Question
Title: Skyline problem with triangular buildings
This question is based off of the usual Skyline problem, which is discussed in GeeksForGeeks and also several other websites.

The following are two variations from the usual Skyline problem:

1. Report all points in the skyline, and not just the upper left points.
2. Use arbitrary triangles and report all points in the shape formed by overlapping the triangles, where all triangles have positive height and have a base lying on the $x$-axis. I will call this variant **Skyline-TRI**. (Can one generalize the case where all the triangles are isosceles or right-angled to the case where the triangles are arbitrary?)

---

How can I solve Skyline-TRI?

For simplicity, assume all triangles are sorted by their leftmost coordinates on the $x$-axis. Each triangle is specified by a quadruple $(x\_1,x\_2,x\_3,h)$, which represents three vertices $(x\_1,0), (x\_2,0), (x\_3,h)$.

I know how to write an algorithm using the Divide and Conquer approach that addresses variation 1, but it only works when all the buildings are rectangles. For the rectangle case of the Skyline problem, the rough idea is to keep track of the leftmost coordinate and to find the correct endpoint of each vertical segment in the skyline. For the triangular case, I think it might be useful to consider two triangles specified by coordinates $(x\_{11}, 0), (x\_{12},0),(x\_{13},h\_1)$ and $(x\_{21}, 0), (x\_{22},0),(x\_{23},h\_2)$. The leftmost point on the $x$-axis will be on the Skyline of the two triangles and one can use the equations of the lines of the sides of the triangles not on the $x$-axis to compute intersection points, but I'm not really sure how to put the details together to come up with a linear time algorithm. For example, given the two triangles specified by the values $(1,3,-1,5)$ and $(0,2,2,5)$, the resulting Skyline should contain the points $(0,0), (1/2,5/4),(-1,5), (1,5/2), (2,5), (2,5/4), (3,0)$ in that order.

Splitting the problem of finding the skyline of $n$ triangles into two halves on which to recurse is simple, as is the base case where the three points of the triangle are reported/returned.

I'm not sure how to show that the Skyline of $n$ triangles will contain at most $O(n \log n)$ points.

> **Edit:** To clarify, I want to solve this problem using the divide and conquer approach, and **not** the sweep line technique mentioned in the comments section of this question.

---

One very general solution that doesn't use divide and conquer involves computing all intersections between all sides of the triangles and then finding the convex hull of these points as well as the $O(n)$ points representing vertices of the triangles. This takes $O(n^2 \log n)$ time, which is obviously too slow.

# Answer
> 1 votes
If holes are ignored (only the outline is computed), this is an instance of computing a single face of arrangement of half-lines (rays).

With half-lines, the maximum number of vertices in a single face is $\Theta(n)$. Therefore, this problem can be solved in $\Theta(n \log n)$ expected time using the randomized divide-and-conquer approach. See \[1\] chap.6.2 for details.

If holes are allowed, the number of vertices is $\Theta(n^2)$ in the worst case. Consider the $n \times n$ grid rotated by 45 degrees. Then, replace each line segment with a very acute triangle.

---
Tags: algorithms, computational-geometry, recurrence-relation, recursion, divide-and-conquer
---


# Question
Title: Calculate post dominator with non exiting control flow
Using the basic algorithm to calculate post dominators I run into trouble when working with a CFG containing an infinite loop (i.e., not terminating).

The algorithm:

```
// post dominator of the start node is the start itself
 PDom(n0) = {n0}
 // for all other nodes, set all nodes as the post dominators
 for each n in N - {n0}
     Dom(n) = N;
 // iteratively eliminate nodes that are not post dominators
 while changes in any PDom(n)
     for each n in N - {n0}:
         PDom(n) = {n} union with intersection over PDom(p) for all p in post(n)

```

I have the following function:

```
function x:
  while true:
     doNothing

```

Which has the following CFG graph:

```
                              -CFG->
[METHOD_START] -CFG-> [WHILE]        [DO_NOTHING]  [METHOD_END]
                              <-CFG-

```

When calculating the post dominator tree (starting from `METHOD_END`) this runs in the obvious problem, that there is no elimination of any nodes in `PDom`

The start and final `PDom` will be:

```
METHOD_RETURN : { METHOD_RETURN }
METHOD_START  : { METHOD_RETURN, DO_NOTHING, WHILE, METHOD_START }
WHILE         : { METHOD_RETURN, DO_NOTHING, WHILE, METHOD_START }
DO_NOTHING    : { METHOD_RETURN, DO_NOTHING, WHILE, METHOD_START }

```

This would imply, that `WHILE` is post dominated by `METHOD_START` which is obviously false.

**How do I have to account for infinite loops in post dominator calculations?**

Using the definition of (post) domination of "a node d (post) dominates a node n if every path from the start node to n must go through d" I would assume that the domination tree would have to be empty.

# Answer
The problem is that I was trying to apply the domination algorithm on a forest, i.e., the method has multiple different graphs. However, the algorithm is only defined on a graph. Consequently, before applying the algorithm to the method graph I need to calculate the CFG slice from the start point. I..e, in the given example this would be only `{ METHOD_RETURN }`.
> 0 votes

---
Tags: graphs, compilers, static-analysis
---


# Question
Title: What is the use or how can we implement zero-knowledge proof system in Elections?
I recently heard about the concept of zero-knowledge proof. However, I still do not get how it is possible to make it a solution to some real-world problems. One thing I heard is that zero-knowledge proof can be utilized in Elections. But my question is what is the use, or how can we implement zero-knowledge proof system in elections?

# Answer
> 0 votes
This is far too broad a subject to cover in one answer, so I will give you a recommendation for where you can learn more.
I highly recommend this talk from Ben Adida: https://www.youtube.com/watch?v=ZDnShu5V99s. He discusses cryptography in elections, including zero-knowledge proofs and other cryptographic primitives, at a holistic level. Zero-knowledge proofs are used to verify the correctness of decryption and that the mixnet worked correctly, and he shows an example zero knowledge proof for the latter. You might also be interested to take a look at https://crypto.stackexchange.com/q/6647/351 and https://crypto.stackexchange.com/search?q=%5Bvoting%5D+zero+knowledge, where you can find some pointers into the research literature.

---
Tags: cryptography, zero-knowledge-proofs
---


# Question
Title: Are there any implementations of the spineless tagless G-machine other than in GHC?
From Simon Peyton Jones (recent Royal Society member) we read the paper: Implementing lazy functional languages on stock hardware: the Spineless Tagless G-Machine.

Now this paper is part of how they made Haskell a lazy language when they were implementing it, and solved some problems they had at the time.

The only comparable paper seems to be: Compiling Lazy Functional Programs Based on the Spineless Tagless G-machine for the Java Virtual Machine but there doesn't appear to be an implementation available.

One tangentially related is: Compiling Haskell to Java. However in this approach they leave the implementation of the Spineless Tagless G-Machine in GHC and just read the output.

My question is: **Are there any implementations of the spineless tagless G-machine other than in GHC?**

# Answer
> 3 votes
I used this Google search:

```
"spineless tagless g-machine" site:github.com

```

and found 2 repos that (try?) to implement the STG in non-Haskell languages:

PHP: lechimp-p/php-stg

RPython ("restricted" subset of Python developed for Pypy): cgswords/laurens

# Answer
> 1 votes
Here is a good one with nice visualisations: https://github.com/quchen/stgi

# Answer
> 0 votes
There is an online hosted visual demonstration here with an explanation here.

Typelead was a briefly funded startup that attempted to fork GHC to the JVM (before they ran out of money). Etalang was the result and it contains a STG. You can read the code of the STG here.

---
Tags: reference-request, compilers
---


# Question
Title: Type theory for imperative programming languages?
The type theory that I have seen is all developed over lambda calculus, which is an inherently functional language.

Nevertheless, in practice imperative languages have type systems. Are there differences in the type **theory** for imperative vs functional languages?

# Answer
Sure there are type systems for all sorts of programming languages, including the imperative ones. It's probably best to look at something simple first that exposes the gist of the matter. A classic is John Reynold's The essence of algol, which was quite influential historically, and develops many important ideas.
> 5 votes

# Answer
You might want to look at chapters 13 and 19 of Types and Programing Languages that handle types for constructs with side-effects, and a more general imperative language (Java) respectively.

As Andrej says, the type system community is aware of imperative languages (indeed, I know of very few completely pure systems!), and theory has developed accordingly.
> 2 votes

# Answer
I don't know much, but I am pretty sure Linear Type Theory is used to model imperative programs. For example, Adoption and focus: practical linear types for imperative programming or On linear types and imperative update. Rust, for example, is built on something related to linear types (I forget what exactly though).

It appears the more general category of type systems is Substructural type systems. Here is some more good info on that.
> 0 votes

---
Tags: programming-languages, type-theory
---


title: n! and 2^(n^2); which one grows faster

text:
# Question
Title: n! and 2^(n^2); which one grows faster
I can't figure this out; is $2^{n^2}=O(n!)$ or is it the other way around? Any help is appreciated!

# Answer
$$n! = 1\times 2\times … \times n \leqslant n \times n\times… \times n = n^n \leqslant (2^n)^n = 2^{n^2}$$
> 5 votes

# Answer
You can compare with their logarithm, since O(log(n!)) = O(nlogn) and O(log(2^(n^2)) = O(n^2) and nlogn \< n^2. So the later one grows faster.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: How do we enumerate every algorithm in the circuit model?
Consider the family of circuits $\\{C\_n\\}\_{n\in \mathbb{N}}$ that are big enough to compute every Boolean function for $n$ variables. We can label the nodes in order starting at the inputs and working down the layers, so that $2^{2^n}$ refers to the last, deepest node in the circuit.

A decidable problem corresponds to a path through the output nodes of these $C\_n$, where each output node gives the answer to the problem for an input of length $n$. I believe this is the case because we say that a family of circuits can decide a problem if there is some Turing machine that generates the correct circuit for a given length. So a Turing machine should be able to generate $C\_n$ up to the node that we select as output since we have an algorithm to pick what that output is. There should be countably infinite paths that refer to decidable problems (we can choose the path in finite time), so my question is, how do we enumerate them?

First I tried something simple. To select the node for the $n$th circuit, we could try $$f\_n(k) = k\bmod M$$

The naive choice is $M = 2^{2^n}$, but this would not cover every path; each circuit would loop in sync, and so nodes from lower $n$ would only match with specific nodes from higher $n$. So we choose $M$ as the first prime larger than $2^{2^n}$. Just fill in the extra with repeats of some of the output functions.

But looking closer, this only selects circuits with polynomial size. For any $k$, you can always make $n$ large enough such that $n^c \> f\_n(k)$. The exponential circuits are "infinitely far away."

So I tried to be a little more clever. It's possible to enumerate every binary fraction in $(0,1)$ as the ratio of the sequences A006257/A062383 (see comment there) in an even way, dividing the interval into finer and finer divisions. The sequence goes like $\frac{1}{2},\frac{1}{4},\frac{3}{4},\frac{1}{8},\frac{3}{8},\frac{5}{8},...$ OEIS gives functions for each sequence so let's put them together,

$$ \begin{align} g\_n(k) &= (2^{2^n})\frac{2(m-2^{\lfloor\log m\rfloor})+1}{2^{\lceil\log(m+1)\rceil}}\\ \text{where}\quad m &= k\bmod M \end{align} $$

Except now, $g\_n(k)$ only gives exponential-sized circuits! To see this, there's a result from Shannon that shows the fraction of Boolean functions computable with circuits of size less than $2^n/n$ is vanishingly small as $n$ increases. So for any $k$, there will always be an $n$ large enough that the $2^n/n$ bound is *lower* than the fraction computed within $g\_n(k)$. So now the polynomial-sized circuits are infinitely far away.

In order to cover both sets, I suppose I could weave these two functions together by giving one to the even numbers and one to the odd numbers, but I don't even know if that yet guarantees we cover all the paths. Is there a nicer way to do this enumeration?

# Answer
> 0 votes
One way to describe a circuit is as follows. Suppose that the inputs are $x\_1,\ldots,x\_n$. The remaining gates of the input compute functions $x\_{n+1},\ldots,x\_m$, where each $x\_i$ is one of the following:

* $x\_i = \lnot x\_j$ for some $j \< i$.
* $x\_i = x\_j \lor x\_k$ for some $j,k \< i$.
* $x\_i = x\_j \land x\_k$ for some $j,k \< i$.

This is known as a *straight-line program*, and you can express it textually in many ways. Now you can go over all straight-line programs of the appropriate size.

---
Tags: circuits
---


# Question
Title: How to think about typing inference rules when thinking about typechecking?
I am trying to build an imperative programming language with a type system that will allow for proofs. I just found kind lang, which implements all the ideas that I have been meaning to use (plus more), but it is a functional language. An older rendition of the project was Formality in JavaScript, or probably earlier, the Calculus of Constructions in JavaScript. Also I take inspiration from Rust.

The key function I am trying to understand is how typechecking works (also, how type inference works / is implemented). From Formality, it is like this basically (from the link):

```
const Var = (name,indx)                => ({ctor:"Var",name,indx});
const Ref = (name)                     => ({ctor:"Ref",name});
const Typ = ()                         => ({ctor:"Typ"});
const All = (eras,self,name,bind,body) => ({ctor:"All",eras,self,name,bind,body});
const Lam = (name,body)                => ({ctor:"Lam",name,body});
const App = (func,argm)                => ({ctor:"App",func,argm});
const Let = (name,expr,body)           => ({ctor:"Let",name,expr,body});
const Def = (name,expr,body)           => ({ctor:"Def",name,expr,body});
const Ann = (done,expr,type)           => ({ctor:"Ann",done,expr,type});
const Nat = (natx)                     => ({ctor:"Nat",natx});
const Chr = (chrx)                     => ({ctor:"Chr",chrx});
const Str = (strx)                     => ({ctor:"Str",strx});

// ...

function typecheck(term, type, defs, ctx = Nil()) {
  var typv = reduce(type, defs);
  switch (term.ctor) {
    case "Lam":
      if (typv.ctor === "All") {
        var self_var = Ann(true, term, type);
        var name_var = Ann(true, Var(term.name, ctx.size+1), typv.bind);
        var body_typ = typv.body(self_var, name_var);
        var body_ctx = Ext({name:term.name,type:name_var.type}, ctx);
        typecheck(term.body(name_var), body_typ, defs, body_ctx);
      } else {
        error(term, ctx, "Lambda has a non-function type.");
      }
      break;
    case "Let":
      var expr_typ = typeinfer(term.expr, defs, ctx);
      var expr_var = Ann(true, Var(term.name, ctx.size+1), expr_typ);
      var body_ctx = Ext({name:term.name,type:expr_var.type}, ctx);
      typecheck(term.body(expr_var), type, defs, body_ctx);
      break;
    default:
      var infr = typeinfer(term, defs, ctx);
      var eq = equal(type, infr, defs, ctx.size);
      if (!eq) {
        var type0_str = show(normalize(type, {}), ctx);
        var infr0_str = show(normalize(infr, {}), ctx);
        error(term, ctx,
          "Found type: \x1b[2m"+infr0_str+"\x1b[0m\n" +
          "Instead of: \x1b[2m"+type0_str+"\x1b[0m");
      }
      break;
  };
  return {term,type};
};

```

So there's that, and then there are things like this ("typing rules"):

How am I to read these typing rules, and yet think about a type checking algorithm? I would like to (in my head at least) convert the typing rules to useful code. Basically, what is a type rule for in the end? How does it get used in a type checking algorithm? How do I read the typing rule so that it makes sense in the context of a type checking algorithm pretty much? What is the relation between type inference rules and type checking? I don't see how to combine the two clearly and practically.

# Answer
> 3 votes
The rules of a type system may be given in one of several ways.

We often begin by defining a relation "term $t$ has type $A$" using rules of inference *without* giving any particular way of turning the rules into an algorithm. This is sometimes called the "declarative style". The declarative style is usually the easiest to understand and most amenable to mathematical treatment, such as semantics. If you're designing a new type system you'd probably start here in order to not get tangled up in various algorithmic details.

We then want an equivalent formulation that indicates how we are supposed to carry out type checking. This is sometimes called "algorithmic style".

One particular kind of algorithmic style are the "syntax directed rules" – by which we mean that we can tell which rule to use by analyzing the syntax of the term $t$ that we are trying to typecheck. This is good because it tells you how to implement typechecking. Most of the time most declarative rules are already syntax-directed – but in interesting cases there are always a couple that are not.

It takes experience to know how to design an algorithmic style that correspond to a given declarative style. In fact, figuring out a good type-checking algorithm for a new type system may be quite challenging and publication-worthy.

A popular way to formulate type systems in algorithmic style is to split the relation "$t$ has type $A$" into two:

* *check* that $t$ has the given type $A$, and
* *infer* (synthesize, compute) the type of $t$

This is known as a *bidirectional* type system. The checking and inferring relations (also called phases) are often mutually recursive, and they are also syntax directed – so they give an algorithm. (In case it is not clear, the algorithm is simply to look at the syntactic structure of $t$ to find out which rule should be used, more or less.)

There are many other kinds of algorithms that perform type checking and type inference. For instance, they may collect a set of equational constraints that needs to be solved. Or they may track some other information. It is traditional for such algorithms to be displayed using inference rules (rather than pseudocode that looks like Algol 68). The accompanying text will tell you which bits are to be thought of as inputs and which as outputs, and the rules will be syntax-directed so that in each situation at most one will apply. (And if none apply, you've got a type error.)

To answer your question specifically: there are a number of techniques that turn inference rules into algorithms. What is appropriate in your case depends on what your type system look like. Have you written it down? In declarative style?

---
Tags: type-theory, type-checking, type-inference
---


# Question
Title: Automaton for telling whether a binary number is a multiple of 3
I am designing an automaton which determines whether a binary number is divisible by 3:

$$ \\{x \in \\{0, 1\\}^\* \mid \text{$x$ represents a multiple of three in binary} \\} $$

|  | 0 | 1 |
| --- | --- | --- |
| 0F | 0 | 1 |
| 1 | 2 | 0 |
| 2 | 1 | 2 |

This is the transition state diagram of the automaton, whose states are $0,1,2$; the states are drawn from left to right.

But here the automaton reads the input from left to right. So at first I didn't think about the order (left to right or right to left); I tried to design an automaton which reads the binary from right to left but after much time I couldn't design any automaton which reads the binary right to left and tells whether it is divisible by 3.

Can someone help me out to design such an automaton, or is it possible to design an automaton which reads from right to left and can tell whether its input is divisible by 3?

# Answer
> 7 votes
When you read a number $b\_0 \ldots b\_{n-1}$ from the LSB to the MSB, its remainder modulo 3 is \begin{align} &b\_0 + 2b\_1 + 4b\_2 + 8b\_3 + 16b\_4 + 32b\_5 + \cdots \bmod 3 \\ = \\, &b\_0 - b\_1 + b\_2 - b\_3 + b\_4 - b\_5 + \cdots \end{align} In other words, when reading bits with even indices, the remainder modulo 3 increases by the bit read; and when reading bits with odd indices, the remainder modulo 3 decreases by the bit read.

To implement this using a DFA, you need to keep track both of the remainder modulo 3 and of the parity of the index of the current bit. In total, you will need 6 states, 2 of which will be accepting.

---

As Hendrik Jan mentions in the comments, in order to know whether the number is divisible by 3, we don't actually have to maintain the remainder modulo 3. Instead, we could compute the remainder of $(-1)^{|x|-1}x$, where $x$ is the input, since this remainder is zero iff the remainder of $x$ is zero. The advantage is that the new remainder is $$ (-1)^{n-1} (b\_0 - b\_1 + \cdots + (-1)^{n-1} b\_{n-1}) \bmod 3 = b\_{n-1} - b\_{n-2} + \cdots + (-1)^{n-1} b\_0 \bmod 3, $$ which is just the remainder of the *reverse* of the input. So the DFA actually works whichever way you read the input — LSB to MSB or MSB to LSB.

---

More generally, the regular languages are closed under reversal. One way to see it is that if you have a DFA for your language, you can convert it to an NFA for the reversed language by changing the direction of the arrows and switching initial and final states; you can then determinize it to produce a DFA, if you so wish.

# Answer
> 1 votes
00 is starting position.

(evenx) \[even represents parity of number of bits so far the automaton read and x is remainder of present state\]

oddx \[odd represents parity of number of bits so far the automaton read and x is remainder of present state\]

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


# Question
Title: Show that $ Y \subseteq A^*$ is decidable
Let A be a nonempty alphabet, $X ⊆ A^\*$ a decidable set, and $Y ⊆ A^\*$ be a semi-decidable set. We assume that $Y ⊆ X$ and that $X \setminus Y ⊆ A^\*$ is semi-decidable. Show that then the set Y ⊆ A∗ is decidable.

I am looking for some ideas where to start this problem. I think we need 2 TM's which check each input simultaneously. But some further ideas where to start would be great!

# Answer
Let $x \in A^\*$ be your input string. We can check that $x \in X$ and, if that is not the case, reject immediately (since we know that $x \not\in X \supseteq Y$).

Now, we know that exists a Turing machine $T\_1$ that accepts $Y$. Moreover, there exists a Turing machine $T\_2$ that accepts $X \setminus Y$. Interleave the execution of $T\_1(x)$ and $T\_2(x)$. Eventually, one of $T\_1(x)$ and $T\_2(x)$ must halt and accept. If $T\_1(x)$ accepts, then accept. If $T\_2(x)$ accepts, then reject.
> 1 votes

---
Tags: decidability
---


title: crossings of edges of a geometric graph

text:
# Question
Title: crossings of edges of a geometric graph
I am considering geometric graphs $G=(V,E)$ where $V$ is a set of points in $\mathbb{R}^2$ and the edges are straight line segments between vertices. See the image:  Now I want to calculate all pairs of edges that cross, i.e. intersect in their interior. I want to do this as efficient as possible. I could brute-force it in time $O(m^2)$ or I could use Bentley–Ottmanns algorithm, for a runtime of $O((m+k)\log m)$ where $m$ denotes the number of edges and $k$ the number of crossings.

Both of these algorithms do not use the graph structure at all. Can I get a more efficient algorithm by using the graph-structure? My literature-search with respect to geometric graphs, did not yield any interesting algorithms regarding my problem.

# Answer
> 1 votes
I think the incremental construction method would be useful here. Start with an empty graph, and add your edges one by one. For each new edge, you want to query the intersections with the current subgraph. This can be done via a binary search over the existing line segments (use e.g. the inner product with the normal vector of the new line segment as a key for the binary search). So, merely counting will take $O(m\log m)$, while reporting all edges will take $O(m\log m + x)$, where $x\in O(m^2)$ is the total number of intersecting pairs of edges.

Note that this algorithm does not really use the structure of the graph, and only treats them as line-segments. I think this is to be expected, as there is no difference between the intersections of this graph and the intersections of the line segments of the graph.

---
Tags: graphs, computational-geometry, planar-graphs
---


# Question
Title: How do COVID-19 Vaccination ID verifications work? How do they ensure that the ID is not faked?
How do COVID-19 Vaccination ID verifications work? How do they automatically verify that the COVID-19 Vaccination ID is not faked?

# Answer
> 0 votes
It's difficult, and it's more suitable for a security website.

Usually you get a QR code. A QR code can be cryptographically signed, and if it is signed, it cannot practically be forged. So you can't create a QR code that shows you are vaccinated.

But I can make a copy of your QR code. That QR code would then prove that someone with your name, possibly your face, and possibly your passport number, is vaccinated. If I tried to get on a flight with that QR code, someone would check and see that the QR code proves *you* are vaccinated, but it doesn't prove that *I* am vaccinated, because my photo and passport number don't match.

This is all based on some data in some government computer, and that data can be forged. There are currently three people in the UK in court for entering non-existing vaccinations into the system for money.

---
Tags: algorithms
---