# Question
Title: Incorporating newline-as-statement-terminator heuristics into context-free languages
Several block structured languages (Scala, Go, Ruby, Julia, Quorum, ...) use semicolons as statement terminators, but allow newlines instead of semicolons under certain circumstances.

My question is: how can I represent Scala-like optional semicolons in a context free grammar? The specific issue is that some kinds of nesting delimiters "enable newlines" while others "disable newlines," so you need to pay attention to what kind of delimiters you are most immediately inside of.

I'm specifically asking about Scala's heuristic, because Julia and Quorum don't have specs. Ruby has a spec, but handles the problem by scattering "`[no line-terminator here]`" throughout the formal grammar and I've been unable to find a general rule. Go has a well described heuristic but it's lexical only, which makes it obvious how to specify and implement, but its usability is somewhat disappointing. (Go inserts a semicolon even if you haven't closed the most recent `(` token.)

Scala goes well beyond the Go lexical rule with a nesting rule (cf reference, Section 1.2). In addition to lexically ensuring that both the token before *and after* the newline are consistent with the insertion of a statement terminator, newlines-as-statement-terminators are disabled between matching `(` and `)` parenthesis and `[` and `]` brackets, but then re-enabled between matching `{` and `}` braces.

I can figure out how to implement a simple *pre*-processor as a push-down automaton. The automaton starts with `enabled` on the stack. As you process the token stream, when you see a `(` or `[` push `disabled` onto the stack, when you see `{` push `enabled` onto the stack, and when you see `)`, `]` or `}` pop the top of the stack. Then when you see a newline that otherwise satisfies the lexical rules for the insertion of a statement terminator, you insert the terminator if and only if `enabled` is on the top of the stack. So Scala's newline-to-statement-terminator rule is "context free" in some sense, but I haven't been able to figure out how to *incorporate* this push-down automaton in with the rest of the language grammar.

# Answer
I do not know Scala (though I hope it has a good opera-tional semantics). I am answering on the basis of the information you give in the question. I think your problem is using the stack rather than the finite state to remember local behavior. Finite state is for information you are currently using, while the stack is for information that you have to remember for future use, but do not need right now. At least, I see this description as a convenient way of designing pushdown uses - though I am aware of all the equivalence games between various definitions of PDA.

So your automaton should start with nothing on the stack, but with a `terminator` register containing `enabled`. As you process the token stream, when you see a `(` or `[` push the content of the register onto the stack and put `disabled` in the register, when you see `{` push the content of the register onto the stack and put `enabled` in the register, and when you see `)`, `]` or `}` pop the top of the stack and put it in the register. Then when you see a newline that otherwise satisfies the lexical rules for the insertion of a statement terminator, you insert the terminator if and only if `enabled` is in the register.

The register may be seen as a simple finite-state control that can be used for a cross-product with the rest of the finite-state control of the PDA parsing your Scala syntax. I expect that by proceding this way, you get a stack policy for terminator insertion rules that can be smoothly merged with the policy for parsing the rest of the syntax, since various types of parenthesis must match for the rest of the language too. And you parser should sing without dissonance.

Doing finite state control cross-prodduct is another technique for designing PDAs (among other devices, most likely). I think it has been extensively analyzed for FA (I think, but it should be checked that this is related to Krohn–Rhodes theory).
> 2 votes

# Answer
The basic problem we have to solve is how to separate sequences of statements

```
(A)
statement1
statement2

```

from multi-line statements

```
(B)
state
ment

```

Dedicated separators such as semicolons are a time-honored way to do this clearly but some people dislike them. An alternative is to require some kind of syntax for triggering (B) (I think I've seen `state \ \nment`) which is likely to be rejected for similar reasons.

So, one way to do this is to ensure that the set of statements is prefix-free, that is no statement of the form (B) can parse as (A) ever. Of course, that is rarely possible as you want to allow (improperly parenthesised) statements like

```
x = 3 - 2 + x

```

and at the same time blocks like

```
x = 3
- 2 + x
[returns 1]

```

Such languages (e.g. Scala) are *inherently ambiguous* on a syntactic level (without dedicated statement separators). On a semantic level, you may be able to resolve the ambiguity, e.g. you might figure out during name analysis that `x` is not initialised in reading (B) or during type analysis that the block should return an integer, which reading it as (B) may not do.

Needless to say that many dynamic languages don't even allow for this because all variables may be implicitly initialised or every statement returns something or what not.

In other words, I think this language "feature" is beyond the capabilities of PDAs if you don't want rigid precedences. You need backtracking, look-ahead,
semantic analysis and even guesswork.
> 3 votes

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


# Question
Title: Quickly locating nearest rectangle from a point
The problem is as follows:

> There are several rectangles in the plane (they are not necessarily axis-aligned), how can we index them in such a way that given a point $p$ we can quickly locate the nearest rectangle from $p$? The distance from a point $p$ to a rectangle $R$ is defined as the Euclidean distance between $p$ and its nearest counterpart $q \in R$. If $p$ is inside the rectangle, then the distance is $0$.

Actually what I want is the distance between $p$ and its nearest rectangle, so if we can directly get this distance, it's even better.

The naive solution is to compute the distance between $p$ and each rectangle, however this is time consuming in my case, so I want to know if there exists such a data structure.

Edit:

These rectangles may intersect, and the total number is very likely less than 20 (typically around 5). It is trivial if we only want to know this minimal distance for a few points, linear scan will do the work. However when the number of such points becomes very large, the overall computation overhead cannot be ignored, that's why I want to quickly find the nearest rectangle.

# Answer
> 2 votes
I expect the best option is to use some kind of spatial index. Here's a first suggestion, but I'm sure there are better solutions.

* Create a quad tree with a maximum bucket capacity of $m$.
* For each new rectangle, traverse the tree, and store a pointer to the rectangle at **each** bucket that intersects the rectangle.

Now to find the nearest rectangle for a point $p$:

* Find the bucket $B$ the point falls in.
* Find the distance $d$ to the nearest rectangle $B$.
* Check all surrounding buckets for rectangles that might be closer than $d$.

The last step might still be expensive if you're unlucky, but you can effectively eliminate all buckets that are itself further from $p$ than $d$.

# Answer
> 1 votes
Here's another approach:

The rectangles basically form a generalized Voronoi diagram where the seeds are rectangles instead of points. Each cell in this diagram forms a polygon. The algorithm for computing these polygons is basically the same as that of the regular Voronoi diagram: compute the boundary cutting the plane in to two half-spaces for each pair of rectangles, and intersect the resulting half-spaces over all pairs to find the correct polygon. The polygons (unfortunately) are not necessarily convex, but you can split each polygon into a set of convex polygons

Once you have this list of convex polygons, partitioning the plane, each mapping to a rectangle, all you have to do for a given point is to find which polygon it's in. This can be done by computing the dot product for each side of the polygon, to find which side of the line it's on.

If you do this straightforwardly, you end up with $O(nm)$ dot product computations for $n$ polygons with $m$ sides each, which is probably not better than computing the distance to the rectangles normally. However, each test for the point against a line segment basically eliminates all polygons on one side of the line. You can use this to find a binary tree where each node represents a choice of line segment in the diagram against which you compute the dot product, and the leaves contain a ginle polygon. This suggests that if you have $n$ convex polygons, you can decide the correct polygon in $\log\_2 n$ computations of a single inproduct. I expect this will be efficient, but you might be unlucky and get lots of non-convex polygons that have to be split into many convex ones.

It's quite a job to work all this out into an actual algorithm, and I'm sure I've overlooked some things, but the literature on generalized Voronoi diagrams seems to be quite extensive, so with a little reading you should be able to work it out (if the speedup is worth the effort).

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


title: Variable Length Encoding of Integers

text:
# Question
Title: Variable Length Encoding of Integers
I was just researching Fibonacci encoding of integers. Numbers are encoded in binary and where no two consecutive bits are equal to 1 - other than to terminate the number.

Now other schemes are possible, for example having three or more 1's terminating the number. These representations are more efficient (shorter) for larger numbers but less so for small numbers.

My question is, is it possible to have an optimal scheme where the number of terminating 1's increase as the size of the number increases? And have no ambiguity.

Some examples to clarify:

a. 0 = '1', 1 = '01', 2 = '001', 3 = '0001', 4 = '00001', 5 = '000001', 6 = '0000001'

b. 0 = '11', 1 = '011', 2 = '0011', 3 = '1011', 4 = '00011', 5 = '10011', 6 = '01011'

c. 0 = '111', 1 = '0111', 2 = '00111', 3 = '10111', 4 = '000111', 5 = '100111', 6 = '010111'

These use 1, 2, and 3 terminating 1's respectively.

# Answer
There is no optimal scheme for encoding integers. To understand what this statement even means, we need a few definitions.

---

A *codeword* $w$ is a word over the alphabet $\\{0,1\\}$.

A sequence of codewords $w\_0,w\_1,w\_2,\ldots$ is a *code*.

A code $w\_0,w\_1,w\_2,\ldots$ is *prefix-free* if no $w\_i$ is a prefix of any $w\_j$ for $i \neq j$.

A code $w\_0,w\_1,w\_2,\ldots$ is *monotone* if $|w\_0| \leq |w\_1| \leq |w\_2| \leq \cdots$.

An *integer encoding scheme* is a monotone prefix-free code.

An integer encoding scheme $x\_0,x\_1,x\_2,\ldots$ is *better* than an integer encoding scheme $y\_0,y\_1,y\_2,\ldots$ if $|x\_i| - |y\_i| \to -\infty$.

---

The codes that you give are examples of integer encoding schemes which get progressively better.

**Theorem.** For any integer encoding scheme $y$ there is a better integer encoding scheme $x$.

In fact, the situation is even worse: there is no optimal *sequence* of codes:

**Theorem.** For any sequence $y\_1,y\_2,\ldots$ of integer encoding schemes there is an integer encoding scheme $x$ better than all of them.

For proofs see, for example, this paper.

Elias came up with a sequence of codes, including the gamma and delta codes, which are progressively better, culminating in the limiting omega code; but even this code isn't optimal.
> 4 votes

---
Tags: algorithms, optimization
---


# Question
Title: Is there a limit on the length of queries for the oracle?
Consider the class $L^A$ which contains all the languages that are decided by a deterministic Turing Machine that uses $O(log(n))$ space and that can make queries to an oracle that decides $A$. My question is what is the length of query that the machine can ask the oracle? Is it $O(log(n))$ or can it be polynomial in $n$ (where $n$ is the length of the input)?

# Answer
It seems that the usual definition, following Ruzzo, Simon and Tompa, is as follows. The oracle tape is write-only but has no space constraints. It is erased after each oracle call. In addition, if the machine model were non-deterministic (which is not your case), then the oracle calling process would have to be deterministic.
> 1 votes

---
Tags: complexity-theory, terminology, oracle-machines
---


# Question
Title: Progressive discrete multifunction optimization
I have a set of functions $F$.

The functions effectively take a set $S$ that is always a subset of a global set of all possible values $G$, where $|G|\>1000$. *(alternatively, they could take a $|G|$tuple of booleans, if that's easier)*. The functions return a real result. I want to minimize over $S$ the average value of these functions if *all* of them are given the same parameter $S$.

$$\min\_{S\\,\subset\\, G}\left(\sum\_{f\\,\in\\,F}f(S)\right)$$

Now here's the catch:

The functions take a fantastic amount of time to run (say, a few hours), and I intend to have a huge collection of such functions (say $|F|\>1000$ to start). Every so often, a new function will be created and be added to the set. There is no bound to the size of $F$.

Obviously, I can't just use closed form optimization (I'll be dead before it'll finish), so I'm interested in an algorithm that can find an approximate solution and progressively refine it over time as new function results and new functions come in (and hopefully converge faster than brute force).

We can have a better-than-brute-force because the functions $F$ behave similarly. Namely, $f(S) \approx f(T)$ when $S\approx T$ and $k\_aF\_a(S) \approx k\_bF\_b(S)$ for all $S$ ($k$ is constant). There are, of course, many exceptions.

---

Now, I am new in the CS field so I have no idea what things are called. AFAIK I haven't learned how to do this in Into to ML, but it has the feel of a Genetic Algorithm problem. If anyone could point me to a technique or a name, I'd be very happy.

# Answer
There are two techniques that I suspect might be worth trying in this context:

1. **Simulated annealing.** Simulated annealing is a heuristic for optimization that works well when the objective function varies smoothly as a function of its parameters, based loosely upon some structure in the parameter space. You can find a good discussion of how to use simulated annealing, in Steven Skiena's The Algorithm Design Manual.

In your context, you'll need some operations that tweak $S$ by a little bit. Basically, you start from a specific choice of $S$ and then make small modifications, seeing which modifications increase the value of $\Phi(S)$, where $\Phi$ is the objective function. When you find a $S'$ that increases the objective function, you keep that one and start modifying it. This is basically hillclimbing. Simulated annealing improves on that by doing random jumps to get out of local optima.

In your context, the objective function is

$$\Phi(S) = \sum\_{f \in F} f(S).$$

There are many candidates for how to tweak $S$. You could try adding a random element of $G$ to $S$ (or adding $k$ randomly chosen elements of $G$ to $S$) as one operation; removing a random element (or removing $k$ elements) as another operation; and so on. Typically you take advantage of your domain knowledge to select a set of operations that might potentially make sense as "sensible" ways to vary $S$ by a little bit. Then, you let the simulated annealing algorithm take over from there.

The useful thing about your context is that when you've found an optimal value of $S$ for functions $f\_1,\dots,f\_n$ (i.e., for objective function $\Psi(S) = f\_1(S) + \dots + f\_n(S)$), and then you later get an additional function $f\_{n+1}$ to add to the set, now $S$ is a reasonable starting point to start the optimization process for $f\_1,\dots,f\_{n+1}$ (i.e., for objective function $\Psi'(S) = f\_1(S) + \dots + f\_{n+1}(S)$). In particular, given your structure, we might expect that the optimum for $\Psi'$ might be "close" or "similar" to an optimum for $\Psi$, so the optimum for $\Psi$ is a good place to start the hill-climbing/simulated annealing for $\Psi'$.

To extend on that idea, you might also try remembering multiple values of $S$ from the previous round: say, sets $S\_1,\dots,S\_m$ that give the $m$ largest values of $\Phi(\cdot)$ that you encountered during your optimization with the objective function $\Psi$. Now, when you add another function in the next round and want to find an optimum for $\Psi'$, you could try starting from each of $S\_1,\dots,S\_m$ as candidate starting values for the hill-climbing / simulated annealing. This might be effective in practice -- you'd have to try it out to see.
2. **Memoization.** Since computing $f(S)$ is very expensive, you might use memoization to ensure you never compute it more than once. In particular, you might keep a hashtable with mappings $(f,S) \mapsto f(S)$, so that you never need to compute $f(S)$ for any particular combination of a function $f$ and a set $S$ more than once. This might help you out.

Also, when starting the optimization process for the objective function $\Psi'$, you might try computing $\Psi'(S)$ for each $S$ such that you computed $\Psi(S)$ in the previous round. Since $\Psi'(S) = \Psi(S) + f\_{n+1}(S)$, the memoization will ensure that (if you computed $\Psi(S)$ previously) $\Psi'(S)$ can be computed relatively efficiently: it only requires evaluating $f\_{n+1}(S)$, since $f\_1(S),\dots,f\_n(S)$ will already be in the memoization table.

Finally, if you know anything more about the structure of the $f$'s, you might try looking into branch-and-bound style techniques.

Again, these are just ideas. You are in the space of heuristics, so there are no guarantees. You'll have to try out these techniques in your particular application domain to see how well they work. In practice often you may need to try out different parameter settings and make some application-specific tweaks to these general techniques, so be prepared to experiment and try out different stuff.
> 3 votes

---
Tags: algorithms, optimization, neural-networks, genetic-algorithms
---


# Question
Title: Is it possible for a graph to have two different minimum spanning tree
I am suppose to create a minimum spanning tree from this graph below

I got this answer

However this is my textbook answer

Based on what i have learnt , I think my answer and the textbook answer would both be acceptable however I would like assurance from the community that both the answers are acceptable and I did not miss anything out

Thanks

# Answer
> 12 votes
It is possible to have different minimum spanning trees for a graph. Consider a simple example: a cycle graph with all weights equal. Removing any edge from the graph produces a minimum spanning tree for the cycle graph.

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


# Question
Title: Is there an undecidable decision problem that computable algorithm for it leads to an algorithm for halting problem?
Suppose, to the contrary, that there exists a computable algorithm for some undecidable decision problem. Would this mean that halting problem would be solved by a computable algorithm? I know that the converse is true for a decision problem in RE complexity class, but not for the other way around.

# Answer
> 4 votes
Let me rephrase your question. Suppose $O$ is undecidable; can Turing machines with an $O$-oracle solve the halting problem? There are some undecidable $O$ for which this is false. Constructing such $O$ is known as *Post's problem*, solved using the *priority method*; Wikipedia has some details.

---
Tags: computability, undecidability, halting-problem
---


# Question
Title: Smarter recursion to compute #tilings of $m \times n$ board with $2 \times 1$ dominoes?
So I was thinking about how to computationally (e.g., with recursion) obtain the number of tilings of an $m \times n$ board with $2 \times 1$ dominoes. If $m \leq n$, then we can use recursion on $n$ by keeping track of the which squares are filled in the $n$th column, which gives $2^m$ cases to keep track of for each value of $n$, with the cases related between $n-1$ and $n$ based on how the empty spaces in the $(n-1)$th column are filled with horizontal and vertical dominoes. I was wondering, are there any significant improvements known for this type of recursion? For example can we take advantage of symmetry somehow and e.g. only keep track of the lengths of the contiguous filled squares and contiguous empty squares? Or other improvements? If improvements are possible, does it change the asymptotics of the number of cases that need to be tracked?

# Answer
> 4 votes
From my answer on math.SE:

If you just used $1\times2$ rectangles, then this is same as finding the number of matchings in the $m \times n$ rectangle graph, and a formula for that has been given by Kastelyn:

$$ \sqrt{\left|\prod\_{j=1}^{m}\prod\_{k=1}^{n} \left(2 \cos \frac{\pi j}{m+1} + 2i\cos \frac{\pi k}{n+1}\right)\right|}$$

This was done, by mapping the number to the square root of the determinant of a weighted adjacency matrix of the graph.

You can find a nice exposition for the $1\times 2$ case in the first chapter of Kenyon's lecture notes.

---
Tags: combinatorics, recursion, tiling
---


# Question
Title: Edit distance (Levenshtein-Distance) algorithm explanation
I want to calculate the edit distance (aka ***Levenshtein-Distance***) between two words: «*solo*» and «*oslo*».

According to this site we'll get the result matrix:

What I don't understand is: In case of comparison the last «*o*» from «*solo*» with the first «*o*» of «*oslo*» will see the submatrix:

*3 2
4* ***3***

As far as I understand, in order to calculate the bottom right value, which is equal in this example to ***3*** of this submatrix, we'll get the `min(3, 2, 4)` \+ (0 if the letters are the same, otherwise 1). So, why in this example the bottom right value is equal to ***3*** and not to ***2***?

# Answer
> -1 votes
If we look deeply at algorithm implementation in C: http://en.m.wikibooks.org/wiki/Algorithm\_Implementation/Strings/Levenshtein\_distance#C

we'll see the main string which fills the matrix:

```
matrix[x][y] = MIN3(matrix[x-1][y] + 1, matrix[x][y-1] + 1,
                    matrix[x-1][y-1] + (s1[y-1] == s2[x-1] ? 0 : 1));

```

as we can see, the value of cells with indexes `matrix[x-1][y]` (upper cell) and `matrix[x][y-1]` (left cell) in automatically increased, the upper-left cell (by diagonal) with index `matrix[x-1][y-1]` is increased by 1 only if the letters are different and only after that we'll take a minimum from these 3 values. In other words:

*3 2
4* ***min(3+0, 2+1, 4+1) = 3***

# Answer
> 2 votes
You got the recursive definition wrong. It's

$\qquad\displaystyle d\_{ij} = \min \begin{cases} d\_{i-1, j} + c\_\mathrm{del}(b\_{i}) \\ d\_{i,j-1} + c\_\mathrm{ins}(a\_{j}) \\ d\_{i-1,j-1} + \[a\_j \neq b\_i\] \cdot c\_\mathrm{sub}(a\_{j}, b\_{i}) \end{cases}$

where the $c\_{\mathrm{op}}$ are fixed costs for the respective operations, all of which are $1$ here. You'll note that for alternatives one and two, insertion and deletion (which correspond to a vertical resp. horizontal step in the matrix), don't care if the current symbol matches any other -- you introduce a gap symbol, anyway!

Following this definition, clearly $2+1$ (insertion of $o$) results in the entry you highlight. Note that the alignment computed (implicitly) up until this point is

$\qquad\begin{array}{cccc} \- & o & - & - \\ s & o & l & o \end{array}$

---
Tags: algorithms, dynamic-programming, strings, string-metrics, edit-distance
---


# Question
Title: What are the minimum memory requirments a microprocessors must have to perform any calculation?
Please excuse my ignorance in low level things. A lot of the written below might be very wrong.

As far as I understand (and I might be very wrong), there are two types of memory locations a microprocessor can have: registers and stacks.

My question is what is the most basic set of memory locatiins a microprocessor must have to perform an arithmetic calculation of unlimited complexity, such as : `12 / (11 / (4 - 7) * 31) + 8`.

For example one register is obviously not enough. What about three registers? Or one stack? Or a stack and a register? Given e.g. one stack and a register, can the CPU perform any calculation?

The CPU should be able to perform any calculation like in the example shown above.

# Answer
unlimited complexity?

That requires unlimited memory, after all - the numbers must be stored somewhere, and the place to store them is always in memory.

So you need 1 memory 'cell' for each number, and another for each operation. You also need a counter to keep track of the next number or operation. Add to that a register to perform the calculation (only 1 is *needed* as you can use it to store the results in-place. In reality you'll use another register to notify you of errors such as overflow or division by zero).

Or to put it another way: you need sufficient RAM, an accumulator and a program counter. You can get away without the counter if the memory are streamed in sequentially on a specialist computing machine (eg on tape as per Euphoric's comment).
> 7 votes

# Answer
There are many types of processing machines. The most "famous" among these is the Turing machine. But for the example at hand, we can use a much simpler model, called a pushdown automaton. Each model has its own trade-off with regards to memory, performance and expressiveness.

---

## Memory Requirement

Our required machine has two possible input types: **numbers** and **operators** `+ - * /`. Note that we are assuming that multiplication and division are "known" operations for the processor. If not, we can always convert them into a sequence of add and subtract operations.

1. **A tape of input symbols:** The size is equal to the length of the input. This is typically external.
2. **A stack with push-pop access:** The size is equal to the level of nested operations i.e. roughly the amount of nested brackets. *More on this in the "notation" section.*
3. **One (or more) register(s):** The size of a single register should be enough to store a single symbol i.e. either a number or an operator.

Note that this computation may require other registers for storing the second operand, overflow and carryover values, exception handling, etc. depending on the actual implementation. But the core requirement is **a stack and a register, fed by an input tape**.

---

## Notation

If we limit ourselves to the basic arithmetic operations (which have two operators and an operand), we can represent your complex operation in postfix notation. So your example:

```
12 / (11 / (4 - 7) * 31) + 8

```

becomes:

```
12 11 4 7 - / 31 * / 8 +

```

This is a canonical form which can be easily consumed by some types of stack-based processing machines. It does not require operator precedence, brackets, etc. because the order of operations is encoded in the order of the symbols.

---

## Operation

You start feeding in the post-fix symbols left to right. As long as the symbols are numbers, the machine keeps adding them to a **stack**. When the first operator symbol `-` is hit, the stack looks like this:

```
12 11 4 7

```

the machine pops the top of the stack `7` into a working **register**. It also pops the next element `4`, computes the result of `4 - 7` and pushes it back to the stack.

So the stack is now:

```
12 11 -3

```

The next symbol `/` is now read, and the process continues.
> 3 votes

# Answer
To answer this question one needs quite some theory. This topic was studied in detail around WWII. You should read and understand the theory of Turing machine, and understand that what you are asking is basically: what resources are needed for a Turing machine.

Note that there are many famous tasks that are not solveable with a Turing machine, so you might want to reconsider and rephrase your question.
> 2 votes

# Answer
To complement some of the other answers, I'll try to give you some "real-world" examples, using microcontrollers way way smaller than you would find running OS's like Windows or Linux..

First of all, there is no practical limit to the complexity of the expressions such as the one you wrote, since the compiler (C, C++, C#, Java, etc.) evaluates the expression and turns into a set of instructions similar to the example in metacubed's answer (calculating the inner expression first, on out to the top level). Typical compilers may have limits on parentheses levels, but they are typically 32 or more. Anyhow, essentially infinite in all practical terms.

So on to your example. If you were to input your expression into a compiler, and then compile the code, it would mostly likely not use hardly any code or data space at all. The reason is that any decent compiler will evaluate constant expressions at compile time as much as possible. In your case, the entire expression is constant, so the line

```
result = 12 / (11 / (4 - 7) * 31) + 8;

```

would be replaced by

```
result = 8;

```

8? Why 8 and not 7.8944? That's what I got on my calculator?

By default, virtually all microprocessors/microcontrollers (I'll use MCU from now on) perform integer arithmetic instead of floating point. (In fact only high end MCUs, for example the Intel chips used in your desktop/laptop, have hardware floating point.)

After calculating the inner part of your expression, you end up with 12 divided by -93, which is 0 in integer arithmetic. Adding that to 8 gives 8. Whereas in the floating point case, you have 12 / -113, which is -0.1056 , added to 8 gives 7.8944.

So to make the example non-trivial, one needs to assign all the constants to variables, and then calculate the expression.. Something like this (I'm using C):

```
char result, a, b, c, d, e, f;
a = 12; b = 11; c = 4; d = 7; e = 31; f = 8;
result = a / (b / (c - d) * e) + f;

```

Now that will compile into real code. How much? Depends on the MCU.

On a 32-bit MCU, like the PIC32 (which uses the RISC instruction set called MIPS), it takes 12 instructions (2 per variable) to put all the variables on the stack (since C, by default, puts all local on the stack). It then takes another 20 instructions to calculate the expression. Since the PIC32 has both hardware multiply and divide, those operations take only one instruction. Running at 80 MHz, each of these instructions takes 12.5 ns to execute, so the entire expression is calculated in 0.25 µS.

Each PIC32 instruction takes four bytes, so the entire "program" takes 128 bytes of code space, and 28 bytes of stack space (since there are seven variables).

How much is that? Well, an MCU like the PIC32 typically has several hundred thousand bytes bytes of program space (the one I'm using has 512K), and anywhere from 4K to 128K of RAM. So this program is fairly trivial. And of course compared to an 80x86 micrprocessor running on your desktop, with several GB's of RAM (used for both program and data storage), this program is microscopic in comparison.

When this version of the program is run, the value of "result" printed out is the 8, due to the integer arithmetic discussed earlier.

If one were to change the "char" to "float" in the first line of the code example, this changes thing a lot. The code for storing the variables and calculating the expression doesn't go up very much -- from 32 to 38 instructions; but the main difference is now this code is calling all sorts of floating point subroutines in the C library to do the "real" work. As far as I can tell from the map file (one of the outputs of the compiler), these library routines take up another 532 bytes of code space.

When this version of the program is run, the value of result printed out is the desired value of 7.8944.

Now let's look at a small 8-bit MCU, particularly the PIC16F946. The code to save off the variables and then calculate the result (which took 32 instructions the PIC32) now takes 82 instructions. But wait, the PIC16F946 only has a 8x8 hardware multiply but no hardware divide, so there are helper routines for each.

So you have to add 39 instructions for the multiply routine, and 90 for the divide routine, for a total of 211 instructions. Each of these instructions takes 14 bits (how weird is that?), so to be able to compare with other architectures this would be 185 bytes. Actually that is not all that much larger than the PIC32's 128 bytes, even with the helper routines added in. The 14-bit length of the PIC16 instructions vs the 32-bit length of the PIC32 makes a difference.

However if I change to "char" to "float" as we did for the PIC32, the code size almost quadruples.

A PIC16F MCU has anywhere from 768 bytes to 28KB of program space, and just 25 bytes to 2K bytes of RAM. So unlike the PIC32, this example code will stretch the limits of the lowest end PIC16Fs, and the floating point version of the code would not even fit.

So these very small PICs like this run very small programs -- perhaps performing only one function. But they can cost less than 25Ȼ. A typical car today has over a hundred microcontrollers -- some tiny, some rather sophisticated.

The PIC16F946 series, as well as all other 8-bit PICs, actually has only one register dedicated to arithmetic and logical (AND, OR, NOT) operations and shifts; it is called WREG. Such registers are typically called accumulators. There are 15 additional registers, but they are just used to hold temporary variables, like the initial parameters and intermediate results of our expression.

So you really can do a lot with just one register performing arithmetic and logical operations, because the compiler has unrolled all the complexities of the expression to make it as easy for the target machine to calculate as possible. Many of the original microprocessors in the 1970s, like the 6800, 6502, and 8080 had just one accumulator often called A. The 6809, a follow-up to the 6800, had two named A and B.
> 0 votes

# Answer
"any" calculation, well that cannot be answered with a finite solution, but so long as the calculation can be resolved combinatorially then you dont need any memory at all. If you cant do it combinatorially then you need some latches memory...But you will NEVER actually need "memory" as in ram to PERFORM math operations. You might like to have some memory in order to feed the math operation and have a place to put the result, but switches and lights/leds work just fine as well...

You have to be very specific about he processor and the set of operations it supports and the choices for source and destination for those operations. That determines quite heavily how much memory, registers, stack, etc are required to perform a specific operation, since there is no possible answer to this question for "any" operation.
> -1 votes

---
Tags: computer-architecture, arithmetic
---


# Question
Title: Non Deterministic PDA accepted language not clear
This is a PDA from the lecture slides I'm using:

They say it accepts all words that contain double a's. While it makes some sense it's not full proof.

What prevents the second a to be read in the left branch not the right? Or even a 3rd..4th a and so on? Is that the case of human Intervention like needed in PDA for oddpalindrome?

Also as far as I understand a PDA needs to read the whole input tape AND have an empty stack by the end which doesnt seem to be the case if the input is more than an a. What am I not understanding?

# Answer
> 2 votes
The PDA you're linking to is *non-deterministic*; indeed, the state you are confused about has two out-edges labeled $a$. For the PDA to accept its string, it's enough for there to be *one* accepting computation – what you refer to inaccurately as "human interference" \[intervention?\]. Regarding the acceptance condition of the PDA, figure out what acceptance condition makes this PDA accept the advertised language, and this is the accepting condition that you should have in mind.

---
Tags: formal-languages, automata, pushdown-automata
---


# Question
Title: Why is the VC dimension different on intervals and half intervals?
As I read this lecture for being familiar with VC dimension we find on p. 8:

> VC(half intervals in $\mathbb{R}$ ) = 1 .... no subset of size 2 can be shattered
>
> VC(intervals in $\mathbb{R}$ ) = 2 .... no subset of size 3

It's not clear to me. I read on Wikipedia about the difference of Half Interval and Interval and why VC dimension are different.

For example can this set be half intervals or intervals?

$$ \\{ (-\infty \le x \le a) \\, \left|\\, a \in \mathbb{R} \right. \\} $$

Any direction or hint on this problem?

# Answer
> 1 votes
I assume a half interval $I\_a$ is always of the form

$$ \\{(-\infty \leq x \leq a) \mid a \in \mathbb{R}\\} $$

This means that all points equal or smaller than $a$ belong to the interval. Now, choose any set $S = \\{y,z\\} \subset \mathbb{R}$ such that $y \< z$. $S$ is not shattered, since it is impossible to find a half interval $I\_a$ such that $S \cap I\_a = \\{z\\}$ (if $z$ is included in the intersection, than $y$ has to be included as well).

When we consider intervals $I\_{a,b} = \\{(a \leq x \leq b \mid a,b \in \mathbb{R}\\}$ in contrast to half intervals, we are able to find an interval $I\_{a,b}$ such that $I\_{a,b} \cap S = \\{z\\}$ (as well as for all other subsets of $S$). This makes the difference in the VC dimension.

---
Tags: machine-learning, learning-theory, vc-dimension
---


# Question
Title: Unable to understand an inequality in an application of the pumping lemma for context-free languages
**The problem**

Prove that the language

$\qquad L = \\{a^n b^j \mid n = j^2\\}$

is not context free using pumping lemma.

**Approach taken by the book**

To prove such statements, the book takes the approach of a game played against an opponent who strives to fail our effort to prove that the language is not context free. The steps involved in the game are as follows:

* The opponent chooses m such that for all w $\in$ L, |w| \>= m
* We choose the string w
* The opponent decomposes w in uvxyz such that |vxy| \<= m and |vy| \>= 1
* We pump v and y i-times to get the string uv$^i$xy$^i$z.

Now, if for **any** i = 0,1,2,...

uv$^i$xy$^i$z $\notin$ L

the language L is not context free.

**The solution to the above problem**

* Opponent chooses m
* We choose w = a$^{m^2}$b$^m$
* The opponent decomposes w in uvxyz as follows:
* Pumping v and y i-times yields string with m$^2$+(i-1)k$\_1$ a's and m+(i-1)k$\_2$ b's.
* If opponent takes k$\_1$ $\ne$ 0 and k$\_2$ $\ne$ 0, we can take i = 0, such that

(m-k$\_2$)$^2 \leq$ (m-1)$^2$ ... since k$\_2\ne$ 0 making minimum value of k$\_2$ is 1

= m$^2$-2m+1

**\< m$^2$ - k$\_1$**

**Q.** ***This last line I did not understand. How is -2m+1 \< -k$\_1$? Especially because I can find the below decomposition uvxyz for which -2m+1 \> -k$\_1$.***

***I must be missing some stupid algebra here.***

The solution further continues saying that the pumped resultant string does not belong to L.

* Similar argument can be done if user select k$\_1$ = 0 and k$\_2$ $\ne$ 0 or k$\_1$ $\ne$ 0 and k$\_2$ = 0

# Answer
> 2 votes
The Pumping Lemma requires $|vxy| \le m$ so that the pumped parts are of bounded length. Thus $k\_1+k\_2\le m$. With this it is easy.

As $k\_2 \neq 0$, we must have $k\_1\<m$. Also $m\>0$ as the pumping constant must be positive (but in fact we can assume it to be as large as we want, of course).

Now $2m-1 \ge m \> k\_1$.

That's all.

# Answer
> 0 votes
$m-k\_2$ is the number of $b$'s in the pumped word, let us call it $w'$. In order for $w'$ to be in the language, the number of $a$'s has to be $(m-k\_2)^2$. Depending on the chosen $k\_2$, this is *at most* $(m-1)^2 = m^2-2m+1$. The actual number of $a$'s, however, is $m^2 - k\_1$ and this is truly greater than $m^2-2m+1$. Hence, the pumped word $w'$ is not part of the language.

# Answer
> 0 votes
It is much easier to use Parikh's theorem to prove that your language is not context-free. Indeed the Parikh image of your language is by construction the subset $ \\{ (j^2, j) \mid j \in \mathbb{N} \\} $ of $\mathbb{N}^2$. It is now easy to see that this set is not semi-linear and therefore your language is not context-free.

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


title: B-Tree and how it is used in practice

text:
# Question
Title: B-Tree and how it is used in practice
I understand what a B-Tree is (I already implemented a B-Tree in Java with insert and delete methods that preserve the invariant).

However I do not understand exactly how it is used for example for file systems or databases.

1. How do you choose the keys in these 2 scenarios? And what is the data?
2. Are data and keys the same?
3. I can't think of a good key that is able to order the data in a way that it is easily accessible. If I want to find an entry containing some string.
4. how useful would be a key that gives information about the size of each entry? or the alphabetical order? I don't exactly understand the concept.

I have to add that I don't understand much of file systems or databases which is probably why I'm confused.

# Answer
> 8 votes
A B-Tree is a type of dictionary, no more and no less. It can be used to implement a set (e.g. see the interface for `java.util.Set` for the sort of operations we're talking about), but is most commonly used to implement a map (ditto for `java.util.Map`). So let's just look at maps for a moment.

If you think about a linguistic dictionary, it's ordered by "word", and associated with each word is a definition. You look up a word, and get a definition.

So the context of a map data structure is that you have keys ("words") and you want to map this to values ("definitions").

B-trees are like other kinds of search tree (e.g. binary search trees) in that keys can be accessed in sorted order. This has an advantage for certain types of query. For example you can do range queries, say if you want to find all entries where the key is between two values (e.g. all words in the dictionary starting with "q").

The main advantage of B-trees over other kinds of search tree is that it is particularly efficient when represented on disk. B-trees are page-structured (meaning they can be implemented on top of fixed-size disk pages; this also avoids fragmentation), and have a wide ply, which minimises the number of disk accesses needed to perform a query.

A typical use in a database server is to implement indexes. An index is, once again, much like the index in a paper book. Some books have multiple indexes (e.g. there might be a general index and an index of names of people). Given a key, the index in a book returns a set of pages on where you can find references to whatever is indexed (be it a concept, name, or whatever).

A database index typically maps a key to a set of database records. In a typical organisation, there is one data structure in which records are stored, and multiple indexes which map keys to record identifiers. To find records, you query the index, which gives you a collection of record identifiers. Then you can use those record identifiers to find the records in the store.

A typical use in a modern filesystem is to implement directories ("folders" if you're more used to GUIs). A directory is, logically, a map from names (file names or directory names) to filesystem objects. A filesystem object may be a file, or another directory, or what have you.

As has been pointed out elsewhere, you might want to do some reading on this. Any "introduction to databases" textbook will probably do.

# Answer
> 0 votes
If you do proper research all you'r doubts will be clear. Let me try

> how it is used for example for file systems or databases.

Take an example of a library books, And you want to search a specific book and you have kept all the books randomly how much time will it. If you use B-trees then you will divide the books in the racks with some order, So when you perform a search how much time will it take.

> How do you choose the keys in these 2 scenarios? And what is the data?

the book name,or place will be the key and book will be the data.

> 2.Are data and keys the same?

No keys and data are different .The indexes will be act like keys and data will be the actual data(in data blocks) pointed by the keys.

* index file: contains all the keys and the tree's topology is represented by the organization of data in this file.
* data file: a file that contains all the objects and information stored by the “tree”. Objects contained here are referenced by block pointer references stored in the index file.

> 3.I can't think of a good key that is able to order the data in a way that it is easily accessible. If I want to find an entry containing some string.

If you keep all you'r specific books in specific Racks then the name of rack will become key and each rack may have different blocks each block will become the child of tree.

> I have to add that I don't understand much of file systems or databases which is probably why I'm confused.

If you google you will find lot of information regarding this.

but in brief . filesystem is language dependent and architecture dependent. Data Base system is not.

Access mechanism is very fast in database system. Database is designed because of the need of large Data and Managing, storing, synchronization, security, etc of these data.

---
Tags: data-structures, search-trees, databases, filesystems
---


# Question
Title: Conceptual question about entropy and information
Shannon's entropy measures the information content by means of probability. Is it the information content or the information that increases or decreases with entropy? Increase in entropy means that we are more uncertain about what will happen next.

1. What I would like to know is if entropy increases, does this mean that information increases?
2. If there are 2 signals, one is the desired and the other is the measurement signal. Let error be the difference between the two. Or error can be the estimation error in the context of weight learning.

What can we infer if the entropy of this error term decreases? Can we conclude that the error is reducing and the system is behaving close to the desired signal's behavior?

Shall be grateful for these clarifications

# Answer
Information = Entropy = Surprise = Uncertainty = How Much You Learn By Making an Observation. They all increase or decrease together. The *entropy* of a random variable $X$ is just another number summarizing some quality of that random variable. Just like the mean of a random variable is the expected value of $X$ or the variance of a random variable is the expected value of $(X - \mu)^2$, the entropy is just the expected value of some function, $f(X)$ of the random variable $X$. You find expectations of functions by using $\mathbb{E}\[f(X)\] = \sum\_{x\in X}p(x)f(x).$ In this case the function of $X$ you care about is the log (base 2) of the probability mass function.

$$ H(X) = \mathbb{E}\[-\log\_2 P(X)\] = -\sum\_{x \in X} p(x) \log\_2 p(x).$$

This particular expectation is useful because it doesn't depend on the actual values that $X$ can take on, just the probabilities of those values. So you can use it to talk about situations where you aren't sending numbers, or where the numbers are just arbitrarily assigned to particular messages or symbols that you need to send.

What you want for your second question is the *conditional entropy* of the measurement random variable $X$ given the random variable $Y$ that represents what was sent. When there is no error the conditional entropy will be 0, when there is error the conditional entropy will be greater than 0.
> 4 votes

---
Tags: terminology, information-theory, entropy
---


# Question
Title: Complexity of the decision version of determining a min-cut
I was wondering what the complexity of the following problem is:

> *Given:* A flow network $N$ with a source $s$, sink $t$ and a number $k$.
> *Question:* Is there an $s$-$t$ cut of capacity at most $k$?

Obviously, the problem is in P by standard methods. When trying to logspace reduce the P-complete LP-optimization problem, I encountered the following problems:

* If the LP problem has no feasible solution, then $t$ should not be reachable from $s$. In this case, checking whether an LP problem has a feasible solution would be quite simple (don't know whether this is true).
* If the LP problem is unbounded, then the min-cut should be unbounded as well. This could possibly be the case if $s$ and $t$ are identical. Again, checking whether an LP has an unbounded solution would be even easier.

For the lower bound, NL-hardness is quite easy: For a given directed graph $G$ with nodes $s$ and $t$, just take $G$ as a flow network and assign capacity 1 to each edge. Then ask if there is an $s$-$t$ cut of capacity at most 0. $t$ is reachable from $s$ if and only if the answer to this question is no. Since coNL=NL, we are done.

Moreover, the problem is NL-complete for outerplanar graphs. For this, $s$ and $t$ are joined by an edge of infinite capacity. This edge creates the two new faces $f\_1$ and $f\_2$. Now, answer the question whether there is a path of length at most $k$ from $f\_1$ to $f\_2$ in the dual graph.

I do not see how to generalize this to general graphs nor how to overcome the problems described when reducing LP optimization.

# Answer
The described problem is problem A.4.4 of the book "Limits to Parallel Computation: P-Completeness Theory" and is P-complete. It is proven via a reduction from *Alternating Monotone Fanin 2, Fanout 2 CVP* (problem A.1.4 of the same book).

The reduction described in this book originates from the 1990 Theoretical Computer Science paper "The Binary Network Flow Problem is Logspace Complete for P" (T. Lengauer, K. Wagner).

The reduction gets an *Alternating Monotone Fanin 2, Fanout 2 CVP* instance (a circuit $C$) and creates a flow network $N$ that allows a max flow of value $D 4^{k-1}$ where D is the number of input gates in $C$, iff $C$ evaluates to 1.

The idea is to construct the network by creating two nodes $(i,x,0)$ and $(i,x,1)$ for each gate $(i,x)$ (gate $x$ on the $i$th layer in $C$, one for each possible value 0 and 1). The input layer is layer 0. The source of $N$ is connected to $(0,x,0)$ ($(0,x,1)$) with capacity $4^k$ iff $(0,x)$ is a constant 0 (1) in $C$. Each edge $((i,x),(i+1,y))$ of $C$ is then replaced by a small subnetwork which sends 3/4 of the flow directly to the sink. The remaining quarter is sent to $(i+1,y,0) ((i+1,y,1))$, if $x$ in $C$ values to 0 (1). (At least the max flow needs to take these routes. Hence these small subnetworks simulate the gates.)

Now, the output gate $(k,x)$ is copied as well, but only the $(k,x,1)$ copy is connected to the edge. That is: Iff $C$ evaluates to 0, then exactly 1 flow unit cannot be sent to the sink. Hence, the flow in $N$ is $D 4^{k-1}-1$. If $C$ evaluates to 1, then the full $D 4^{k-1}$ flow units can reach the sink. This completes the reduction.
> 2 votes

---
Tags: complexity-theory, graphs, time-complexity, polynomial-time, network-flow
---


# Question
Title: Ant colony optimization for continuous functions
I am trying to do optimization of a voice activity detection function, which is a function with continuous parameters. This is easily accomplished with genetic algorithms, simulated annealing, and tabu search, but I'm somewhat confused on how to accomplish this with Ant Colony Optimization (ACO).

From what I've read, ACO is mostly used for solving problems that can be formulated as a graph. I've searched for resources relating to multiple parameter function optimization, but the closest thing I found was this article for a single parameter on a continuous function and this long paper with no pseudocode which is contained in this PHD thesis. Are there any resources (websites or books) for accomplishing multiple parameter continuous function optimization with ACO that involve an implementation example?

Alternatively, is the key here to discretize the continuous inputs? If so, what methods exist to do this in a way that works well with ACO?

# Answer
*No, discretizing solution space is not necessary*

I read page 14 of paper you provided and then went googling.

I found this 2014 paper: A unified ant colony optimization algorithm for continuous optimization that mentioned a bit of history of ACO on continuous function.

Tracing from that, I think the best paper to begin is this 2008 paper Ant colony optimization for continuous domains coauthored by the original creator of ACO, Marco Dorigo, himself.

Quote from page 76 this paper:

> The fundamental idea underlying $ACO\_R$ is the shift from using a discrete probability distribution to using a continuous one...

That is instead of remembering pheromone value in discrete boxes, you remember in a form of probability distribution function (PDF) that is parameterized for updates. The moving of the ants (solution points) is also continuous. The ants move random directions across the dimensions of solution space (as opposed to moving from box to box as in the first paper you gave.)

I hope I have answered some of your question and provide some references for further reading without digging too deep in myself.
> 4 votes

# Answer
As mentioned in the other answer, discretizing the space is certainly not necessary. In this paper, there is a method for optimizing continuous domains in chapter 5. Better yet, there is source code in Appendix E, in Matlab.
> 2 votes

---
Tags: algorithms, reference-request, optimization, heuristics
---


# Question
Title: Why does ε-greedy $Q$-learning not oscillate?
I have a intuitive question on the convergence of $Q$- learning. In $Q$ learning for each step a $Q$- value is learned for the state-action pair where the action is selected according to the $\epsilon$-greedy policy determined by $Q$ values.

Now my question is due to $\epsilon$-greedy policy (i.e. due to exploration) is it not possible that the $Q$ values oscillates and does not converge ? each time I am giving chance to non-greedy action his value is improved and may be higher than the value of greedy action after some steps and this becomes greedy now and the same thing continues. Is choosing a small $\epsilon$ enough to prevent this ?

# Answer
> 4 votes
The assumptions for Q-learning's convergence proof require that:

> \[...\] all state-action pairs be visited infinitely often

So the *convergence* is understood in a mathematical sense - the Q-function converges to its fixed-point as the number of steps approaches infinity.

In practice, even after your Q-function will be good enough to induce an optimal policy, you will observe "unnecessary" updates each time a non-greedy action is chosen. To avoid that, you can set the learning rate to 0 after the acceptable quality of the solution is achieved.

Also, your intuition about modifying the ϵ parameter, in case of ϵ-greedy policy, seems right. Setting ϵ to 0 will have practically the same effect as setting the learning rate to 0 in the situation described above - in case of a non-stochastic environment.

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


# Question
Title: How to represent circles in x-y coordinates
I would like to be able to represent circles in x-y coordinates.

Each circle contains an x and y coordinates and radius in double data type.

My goal is to compare circles with each other whether they are partially or completely overlapping.

I am looking for efficient ideas. Honestly the only idea that comes to my mind is draw a line(let's say l1) from x1,y1 to x2,y2 and the length of this line is larger than addition of r1 and r2 then it does not overlap, if r1+r2 =\< l1 then it overlaps, but I don't know how to find whether it is completely overlapping or partially. Also this wouldn't work for cases where I am combining more than one circle.

# Answer
> 4 votes
This answer considers two cases:

* the overlapping relation between two disks, which is a very simple problem.
* the ovelapping or covering of a disk by a set of other disks, which is somewhat harder in general.

## Case of two disks

It is indeed a good idea to use center and radius to represent your circles. However I think you are not thinking of **circles**, which are closed planar lines formed of all points at a given distance $r$, called radius, of a point $c$ called the center. The planar surface enclosed by a circle, which also includes all points at a lesser distance fron $c$ is called a **disk** (also spelled *disc*).

Regarding the various overlap situations for two disks, you have the following test, assuming the two circles have radius $r\_1$ and $r\_2$ (assuming witout loss of generality that $r\_1\geq r\_2$), with their centers at distance $d$ (computable from the centers coordinates, thanks to Pythagoras):

* $r\_1+r\_2\<d$ : disks are disjoint, no overlap.
* $r\_1+r\_2=d$ : disks are tangent externally, a single point of overlap.
* $r1-r2\<d\<r\_1+r\_2$ : disks are partially overlapping.
* $r\_1-r\_2=d$ : disks are tangent internally, total overlap of disk 2 by disk 1.
* $d\<r\_1-r\_2$ : disk 1 overlap totally disk 2.

There can be exact overlap of each disk by the other only when $r\_1=r\_2 \wedge d=0$

Regarding the case of several disk, it is not clear whether you want to see whether one distinguished disk is overlapped totally, partially or not at all by the others, or whether you want to check that for each disk with everyone of the others, or possibly something else. You should make that more precise.

## Case of several disks

*This is only a rough sketch, hopefully correct. Working out all details is a lot more work than can be included in an answer.*

As suggested in the question, we can represent a disk $D$ by a triple $(x,y,r)$ which gives the coordinates of the center, and the radius.

Now if you have a disk $D\_0=(x\_0,y\_0,r\_0)$ and a set of disks $L=\\{D\_i\mid D\_i=(x\_i,y\_i,r\_i),\\; i\in\[1,n\]\\}$, your question, as made more precise in a comment, is how to check whether the disks of set $L$ together overlap partially, totally or not at all the disk $D\_0$.

First you want to make a list of the disks in $L$ that actually overlap $D\_0$. For that you can simply apply the above test to $D\_0$ and $D\_i$ for every $D\_i$ in $L$. You get a set $I\subseteq\[1,n\]$ of indices such that D overlaps every $D\_i$ for $i\in I$.

If this set $I$ is not empty, you know that $D\_0$ is overlapped by $L$.

The question remains of a total overlap of $D\_0$ by $L$.

For this, you create a new set $J\subseteq I$ by removing indices of disks $D\_i$ that are only externally tangent to $D\_0$, overlapping it on only one point.

If $J$ is empty, you had only tangential overlapping in a finite number of point, but the set $L$ does not cover (fully overlap) the disk $D\_0$.

If $J$ is not empty, then $L$ completely overlap $D\_0$ iff it does it with the disks $D\_i$ such that $i\in J$. Tangential overlapping on a single point cannot contribute usefully to overlapping a surface.

Now, all disks in $M=\\{D\_i\mid i\in J\\}$ overlap $D\_0$ on a fragment of its surface.

If one disk in $M$ completely overlaps $D\_0$, then we have an answer of complete overlap. We can now assume it is not the case.

Then the problem is to find an orderly strategy to check whether the disks in $M$ completely cover $D\_0$. We will now use disks from $M$ one by one, removing them from M, to cover $D\_0$. The strategy is in choosing them.

We chose first a disk in M (which we remove from M), such that it is not internally tangent to $D\_0$, but intersect the edge circle of $D\_0$. There must be at least two such disks, else $D\_0$ cannot be covered, as its perimeter circle will nor be covered except for a finite number of points.

We compute the two points where the two circles intersect. They define two arcs, one on each circle, that delimit a surface yet to be covered by the other circles. With respect to this surface, the arc belonging to $D\_0$ is convex, while the other is concave.

For simplicity and intuition, we call these intersections the angles of the remaining surface. We call sides or edges the arcs between 2 angles that delimit the remaining surface to be covered.

We then chose one of the two angles, and look in M for another circle covering this intersection. This new circle removes at least this angle, and adds usually two new angles. We discuss this further below.

One remark is that the arcs coming from $D\_0$ are always convex, while the others are always concave. This is useful to visualize what can occur.

Then we repeat the same step, until there are no angles left, in which case we have a covering of $D\_0$, which is tested first, or until there are no disk left in M that can cover a chosen angle, in which case the overlap is incomplete.

To understand this we have to look at intermediate steps in more details. During execution of the algorithm, we may have actually created an uncovered curvy polygon with many angles. When we chose a new disk $D\_i$ to cover a chosen angle $A$, we may actually cover several angles of the polygon, and the edges in between, so that we actually reduce the number of edges.

So after choosing the disk $D\_i$, we have to find the first edge on both sides of the angle $A$ (not necessarily adjacent to $A$) that are intersected by the circle bounding $D\_i$. These two intersections, one on each side, define two new angles and a new edge provided $D\_i$, and may replace several edges and angles. Hence the number of sides of the polygon may be reduced rather than increased. It may be also that all sides are covered, in wich case we have covered the whole disk.

There may be cases when the new disk will cut the curvy polygon into two polygons, that will both have to be covered. To check for that, the circle bounding the disk has to be checked for intersection with all edges of the curvy polygon(s).

All this implies of course to keep an up-to-date description of the curvy polygon and the relations between angles, edges and disks. To keep correspondence between the relative positions of angles, if they are listed counter-clockwise on the curvy polygon(s), then they should be counter-clockwise on the circle of the disk $D\_0$ and clockwise on the disks from $M$.

There are quite a few details to be worked out, which I would not try without at least checking an implementation. But I believe this basic idea can be implemented.

From this analysis, I think the **time complexity** is $O(n^2)$, since every steps considers a new disk, and has to look at intersections potentially with all disks that have already been considered.

The extension to spheres is left as an exercise.

---
Tags: algorithms, computational-geometry, modelling
---


title: What is the term for this set

text:
# Question
Title: What is the term for this set
I have a set of related data/objects for which, when undergoing some algorithm, there should be only one valid match. Is there a unique term for this type of set?

A common practical use case would be a list displayed for user selection, or a list of keys that should have a single corresponding entry in a database table.

To illustrate this, here are a few examples:

* `[True, False]` (boolean)
* `[Forward, Neutral, Reverse]` (state machine status)
* `[Rare, Medium, Well]` (user preference)
* `[Credit, Debit]` (reference type)

In each of these cases, only one element in the set will be contextually valid, where the context may be a database record, an instance of an object in memory, or a question on a survey.

Examples of sets that wouldn't meet this criteria:

* `[Garage, Kitchen, Bedroom, Bathroom]` (rooms in a home)
* `[Email, Phone, Text]` (method of communication)
* `[All Countries in Europe]` (places I visited)

In these cases, the set is used as a bucket from which a selection may be made - but the selection is not necessarily expected to be a single item in the set.

# Answer
> 2 votes
None of your examples holds up: each has queries that allow multiple answers, and each has queries that allow only singleton answers.

So you are really after a property of *queries*. On the most abstract level, given a set $S$ the term you are looking for is *function*:

$\qquad f : Q \to S \\ \qquad f(q) = s \text{ s.t. } q(s) = 1$

where $Q$ is the set of queries (predicates), i.e. $Q \subseteq S \to \\{0,1\\}$. Note how $f$ is a (well-defined) function if and only if all $q \in Q$ have a *support* (set of values on which $q$ is $1$) of size $1$.

If queries end up being true for (i.e. returning) multiple values, we call $f$ a *relation*. Or, alternatively, a function that maps queries to (possibly empty) *sequences* of results, i.e.

$\qquad f : Q \to S^\*$.

# Answer
> 1 votes
If I'm understanding you correctly, what you're describing loosely corresponds to *disjoint sums*, which you see a lot in type theory and functional programming.

For example, in Haskell you could do something like:

```
data Room = Garage | Kitchen | Bedroom | Bathroom

```

We call Garage, Kitchen etc. "constructors" for the type Room. Note that constructors can take arguments, for example you could have

```
data Room = Garage | Kitchen | Bedroom | Bathroom | Suite (Int, Int)

```

if you wanted to store the floor and room number for suites.

When you access a value of type Room, you need to pattern match it against its constructors, like this:

```
cleaningInstructions :: Room -> String
cleaningInstructions Garage = "It's messy, leave it alone"
cleaningInstructions Suite (roomNum, floorNum) = "Clean well for our guests"
...

```

and so on.

On the theory side, disjoint sums are the category-theoretic dual to Products (i.e. tuples). A product is where you have a thing of type 1, AND a thing of type 2, etc. They correspond well to the AND operation. Disjoint sums correspond to XOR: you have type 1 or type 2, but never both.

You can find more information about disjoint sums and the theory surrounding them here.

---
Tags: terminology, sets
---


# Question
Title: How can one come up with reasonable IP subnet allocations?
An ISP has following chunk of CIDR-based IP addresses available with it: `245.248.128.0/20`
The ISP wants to give half of this chunk addresses to Organization A, and a quarter to Organization B, while retaining the remaining with itself. Which of the following is a valid allocation of addresses to A and B?

> A) 245.248.136.0/21 and 245.248.128.0/22
> B) 245.248.128.0/21 and 245.248.128.0/22
> C) 245.248.132.0/21 and 245.248.132.0/21
> D) 245.248.136.0/24 and 245.248.132.0/21

It is easy to make out that option 'C' and 'D' are wrong. Option 'B' is not possible due to address overlapping. The answer is 'A' for sure, but I'm unable to understand how. How is 245.248.**136**.0/21 and 245.248.**128**.0/22 calculated? I've been trying to solve this the whole day but found no solution to it, any help on how to solve this problem would be appreciated.

Also, how can I determine the range of addresses that can be allocated to organizations A and B?

# Answer
Hints:

* Try working out the binary representation of 245.248.136.0 (it's 32 bits) and of 245.248.128.0.
* Re-read what the /21 and /22 notation means and how CIDR works.
* What is the range of IP addresses included in 245.248.128.0/22? in 245.248.136.0/21?

I think once you understand the concepts you'll find that this question is straightforward.

---

Advice: Rather than asking a question about this specific exercise, you might do better to ask a question about some concept you don't understand: e.g., what /N notation means, how CIDR works, etc. But make sure to do your research first. There's lots written on CIDR, /N notation, etc. You can probably clear up your confusion on your own by doing proper reading on those concepts.
> 1 votes

---
Tags: computer-networks, protocols, routing
---


# Question
Title: Is Post's Correspondence Problem decidable with fixed word size?
So, it's known that PCP is undecidable even when we fix the number of tiles to $n \geq 7$.

I'm wondering, can anything similar be said for when there is a fixed word length?

To be precise, here's the problem:

> Given fixed $m$ and $n$, with $n \geq 7$, and words $u\_1, \ldots u\_n$ and $v\_1 \ldots v\_n$ such that $|u\_i| \leq m$ and $|v\_i| \leq m$, is there an index sequence $i\_1, \ldots i\_k$ such that $u\_{i\_1} \cdots u\_{i\_k} = v\_{i\_1} \cdots v\_{i\_k}$.

For what values of $m$, if any, is this known to be undecidable?

Note that this is similar to this question, but none of the 8 linked papers seemed by their titles to answer my question, and I haven't fully read all 8 of them yet.

# Answer
> 9 votes
For all $m \geq 3$, the problem is undecidable.

Proof by reduction from the word problem of unrestricted grammars:

1. Take an arbitrary formal grammar. W.l.o.g. all left and right sides of rules have length at most $3$.

This can be seen by translating any grammar into an equivalent TM and then converting back.
2. Map the resulting grammar to PCP instances; no tile is longer than the longest left or right side of a rule.

That is, with step 1, all tiles have length $\geq 3$.

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


# Question
Title: Variable Length Encoding of Integers Using a Modulus Algorithm
Continuing on the theme from my last question Variable Length Encoding of Integers, I have come up with a simple encoding scheme, but for which an efficient algorithm eludes me.

The constraints are simple enough: no (binary representation) number is allowed where it is divisible by 3, or a subset (prefix) of that representation is divisible by 3.

To terminate the number two bits are added so that the number ***is*** divisible by 3.

For example **1101** is allowed since neither 1101, 101, 01 nor 1 are divisible by 3.

However, **1011** is not allowed since 11 is divisible by 3.

The representation 1101 would then have 10 prepended to make it divisible by 3 (101101).

All this allows a stream of bits to be read, at each point testing to see if the number is divisible by three. If not, keep reading the next bit, until it is divisble by three. Hence allowing for a (unique) variable length encoding.

My question is about the mapping of integers on to this encoding scheme. However hard I try I can't seem to create a straightforward algorithm to do the mapping. Is there one?

**Clarification**

The examples above are to be read in the order right to left. So any prefix is on the right. So the stream of bits will be read right to left.

# Answer
> 2 votes
The first step is counting the number of strings of length $n$ in which no non-empty prefix is divisible by $3$. Surprisingly enough, these are given by Fibonacci numbers $F\_n$ for $n \> 0$ (exercise). I will show how to map the natural numbers to strings of these forms, from which your encoding will follow. Divide the natural numbers into parts of lengths $1,F\_1,F\_2,F\_3,\ldots$. Using the formula $F\_1+\cdots+F\_n = F\_{n+2}-1$, we see that numbers $m$ in the range $F\_{n+1} \leq m \< F\_{n+2}$ will be encoded using strings of length $n$; additionally, $0$ will be encoded by the empty string. Given $m$, it should be straightforward to find $n$, for example using the Fibonacci recurrence or the approximate formula $F\_n \approx \frac{1}{\sqrt{5}} \left(\frac{1+\sqrt{5}}{2}\right)^n$.

Suppose $m \> 0$, and let $x = m - F\_{n+1}$, so that $0 \leq x \< F\_n$. It remains to encode $x$ as a string of length $n$ in which no non-empty prefix is divisible by $3$. The idea is to interpret the recurrence $F\_n = F\_{n-1} + F\_{n-2}$ accordingly. There are many ways of doing it, here is one. There are $F\_{n-1}$ legal strings of the form $0s$, and $F\_{n-2}$ legal strings of the form $1\alpha s$, where $\alpha$ is determined so neither $\alpha s$ nor $1\alpha s$ are divisible by $3$. We can encode the first $F\_{n-1}$ values of $x$ using strings of the form $0s$, and the latter $F\_{n-2}$ values of $x$ using strings of the form $1\alpha s$. To determine $s$ itself, we run this procedure recursively. The base case is the unique string of length $1$, namely $1$.

To illustrate the entire procedure, let us show how to encode $m = 7$. First we find that $F\_5 = 5 \leq 7 \< F\_6 = 8$, and so $n = 4$ and $x = 7 - 5 = 2$. We write $F\_4 = F\_3 + F\_2 = 2 + 1$, so that the encoded string is of the form $s\_4 = 1\alpha\_4 s\_2$. The string $s\_2$ itself is the encoding of $x - F\_3 = 0$ of length $2$. Writing $F\_3 = F\_2 + F\_1 = 1 + 1$, we see that $s\_2$ has the form $s\_2 = 0s\_1$. The string $s\_1$ itself is the encoding of $0$ of length $1$, which is $s\_1 = 1$. Therefore $s\_4 = 1\alpha\_4 s\_2 = 1\alpha\_4 0s\_1 = 1\alpha\_4 01$. If $\alpha\_4 = 0$ then $1001$ would be divisible by $3$, so $\alpha\_4 = 1$ and the output is $1101$.

# Answer
> 1 votes
After a bit of head scratching, here's an alternative way of doing it:

Prepare a binary tree to represent all possible strings of binary digits. There is one root node which represents the empty string. At each node in the tree we can make a decision to either go left (0) or right (1). In this way any node is reachable, and represents a unique string of digits.

Now we prune the tree. We mark the remainder after dividing the binary number by three against each node. Discard any nodes which are reached by going right (1) and whose remainder is zero. Also discard all their children as these are unreachable.

This leaves a somewhat more sparse tree. The main property of this tree being, that whichever path is taken through it, the binary number is never divisible by three. Also, every node either has two children or one child.

For the mapping. Start from the root node. If there are two children go left (0) or right (1) as before, output 0 or 1 accordingly and move to the next digit. If there is one child, then there is no choice, take that child and output 0, stay on the same digit. Repeat until you reach the end of the binary number.

In this way, all nodes in the sparse tree are uniquely reachable.

The main thing to note, is that if we input successive binary numbers, the encoded output is not ordered strictly. Here's the output for the first few numbers (read right to left):

```
0 → 0
1 → 1
10 → 10
11 → 101
100 → 100
101 → 10001
110 → 1010
111 → 1101
1000 → 1000
1001 → 1000001
1010 → 100010
1011 → 100101
1100 → 10100
1101 → 110001
1110 → 11010
1111 → 11101

```

---
Tags: algorithms, encoding-scheme
---


# Question
Title: State of variables in dynammic programming
I would like to know what a state variable is in simple words, and I need to give a lecture about it.

I have chosen the Longest Common Subsequence problem I found a similar question but it has no answers. I was told that I need to use the "states of variables" (not sure if variable of a state and state variable are the same) when explaining the pseudocode.

I think it has something to do with Hoare logic and state variables but I'm a very confused.

If you can provide useful links or maybe a clear explanation would be great.

# Answer
> 1 votes
Dynamic programming was invented/discovered by Richard Bellman as an optimization technique. The notion of state comes from Bellman's original presentation of Dynamic Programming (DP) as an optimization technique. This is presented for example in the Bellman equation entry of Wikipedia.

The technique was then extended to a variety of problems.

You might usefully read the Wikipedia presentation, I think. The concepts you are interested in, including that of states and state variables, are described there. It may still be some work to see how it fits the algorithm you have to explain.

---
Tags: algorithms, terminology, dynamic-programming
---


title: Is path induction constructive?

text:
# Question
Title: Is path induction constructive?
I'm reading through the HoTT book and I have a hard time with path induction.

When I look at the type in the section **1.12.1**: $$\text{ind}\_{=\_A}:\prod\_{C:\prod\limits\_{x,y:A}(x=\_Ay)\to \mathcal{U}} \left( \left(\prod\_{x:A}C(x,x,\text{refl}\_x)\right) \to \prod\_{x,y:A}\prod\_{p:x=\_Ay} C(x,y,p) \right),$$ I have no issue understanding what that means (I just have written the type from memory, to check that).

What I have issue with is the next very statement:
$$\text{with the equality}\quad \text{ind}\_{=\_A}(C,c,x,x,\text{refl}\_x):\equiv c(x)$$ my first impression was that this last expression does not **define** the resulting function $$f:\prod\_{x,y:A}\prod\_{p:x=\_Ay} C(x,y,p),$$ but just **states its property**.

That is in contrast to previous examples of the induction principles $\text{ind}\_{A\times B}$,$\text{ind}\_{A+B}$ or $\text{ind}\_\mathbb{N}$ -- there are **defining equations** for those elements -- we actually know how to construct the resulting function, given the premises. Which is in agreement with the "constructiveness" of type theory adverted throughout the chapter.

Going back to $\text{ind}\_{=\_A}$, I was suspicious about the fact that (looks like) it is not defined. Stating that the element $f$ *just exists* seemed out of tune with the rest of the chapter. And indeed, the section **1.12.1** seems to stress that my impression is wrong and we in fact have **defined**

> ... *the* function $f:\prod\_{x,y:A}\prod\_{p:x=\_Ay} C(x,y,p),$ defined by
> path induction from $c:\prod\_{x:A}C(x,x,\text{refl}\_x)$, which moreover
> satisfies $f(x,x,\text{refl}\_x):\equiv c(x)$ ...

That leaves me utterly confused, but I have a feeling that this point is very important for all the further developments. So which of the two readings for $\text{ind}\_{=\_A}$ should I go with? Or, probably, I'm missing some important subtlety and the answer is "neither"?

# Answer
> 16 votes
It is an illusion that the computation rules "define" or "construct" the objects they speak about. You correctly observed that the equation for $\mathrm{ind}\_{=\_A}$ does not "define" it, but failed to observe that the same is true in other cases as well. Let us consider the induction principle for the unit type $1$, which seems particularly obviously "determined". According to Section 1.5 of the HoTT book we have $$\mathrm{ind}\_1 : \prod\_{C : 1 \to \mathtt{Type}} C(\star) \to \prod\_{x : 1} P(x)$$ with the equation $$\mathrm{ind}\_1 (C, c, \star) = c.$$ Does this "define" or "construct" $\mathrm{ind}\_1$ in the sense that it leaves no doubt as to what $\mathrm{ind}\_1$ "does"? For instance, set $C(x) = \mathbb{N}$ and $a = 42$, and consider what we could say about $$\mathrm{ind}\_1(C, 42, e)$$ for a given expression $e$ of type $1$. Your first thought might be that we can reduce this to $42$ because "$\star$ is the only element of $1$". But to be quite precise, the equation for $\mathrm{ind}\_1$ is applicable only if we show $e \equiv \star$, which is impossible when $e$ is a variable, for example. We can try to wiggle out of this and say that we are only interested in computation with closed terms, so $e$ should be closed.

Is it not the case that every closed term $e$ of type $1$ is judgmentally equal to $\star$? That depends on nasty details and complicated proofs of normalization, actually. In the case of HoTT the answer is "no" because $e$ could contain instances of the Univalence Axiom, and it is not clear what do to about that (this is *the* open problem in HoTT).

We can circumvent the trouble with univalance by considering a version of type theory which *does* have good properties so that every closed term of type $1$ is judgmentally equal to $\star$. In that case it is fair to say that we *do* know how to compute with $\mathrm{ind}\_1$, but:

1. The same will hold for the identity type, because every closed term of an identity type will be judgmentally equal to some $\mathrm{refl}(a)$, and so then the equation for $\mathrm{ind}\_{=\_A}$ *will* tell us how to compute.
2. Just because we know how to compute with closed terms of a type, that does not mean we have actually defined anything because there is more to a type than its closed terms, as I tried to explain once.

For example, Martin-Löf type theory (without the identity types) can be interpreted domain-theoretically in such a way that $1$ contains *two* elements $\bot$ and $\top$, where $\top$ corresponds to $\star$ and $\bot$ to non-termination. Alas, since there is no way to write down a non-terminating expression in type theory, $\bot$ cannot be named. Consequently, the equation for $\mathrm{ind}\_1$ does *not* tell us how to compute on $\bot$ (the two obvious choices being "eagerly" and "lazily").

In software engineering terms, I would say we have a confusion between *specification* and *implementation*. The HoTT axioms for the identity types are a *specification*. The equation $\mathrm{ind}\_{=\_C}(C,c,x,x,\mathrm{refl}(x)) \equiv c(x)$ is not telling us how to compute with, or how to construct $\mathrm{ind}\_{=\_C}$, but rather that however $\mathrm{ind}\_{=\_C}$ is "implemented", we require that it satisfy the equation. It is a separate question whether such $\mathrm{ind}\_{=\_C}$ can be obtained in a constructive fashion.

Lastly, I am a bit wary of how you use the word "constructive". It looks as if you think that "constructive" is the same as "defined". Under that interpretation the Halting oracle is constructive, because its behavior is defined by the requirement we impose on it (namely that it output 1 or 0 according to whether the given machine halts). It is prefectly possible to describe objects which only exist in a non-constructive setting. Conversely, it is perfectly possible to speak constructively about properties and other things that cannot actually be computed. Here is one: the relation $H \subseteq \mathbb{N} \times \\{0,1\\}$ defined by $$H(n,d) \iff (d = 1 \Rightarrow \text{$n$-th machine halts}) \land (d = 0 \Rightarrow \text{$n$-th machine diverges})$$ is constructive, i.e., there is nothing wrong with this definition from a constructive point of view. It just so happens that constructively one cannot show that $H$ is a total relation, and its characteristic map $\chi\_H : \mathbb{N} \times \\{0,1\\} \to \mathsf{Prop}$ does not factor through $\mathtt{bool}$, so we cannot "compute" its values.

**Addendum:** The title of your question is "Is path induction constructive?" After having cleared up the difference between "constructive" and "defined", we can answer the question. Yes, path induction is known to be constructive in certain cases:

1. If we restrict to type theory without Univalence so that we can show strong normalization, then path induction and everything else is constructive because there are algorithms that perform the normalization procedure.
2. There are realizability models of type theory, which explain how every closed term in type theory corresponds to a Turing machine. However, these models satisfy Streicher's Axiom K, which rules out Univalence.
3. There is a translation of type theory (again without Univalence) into constructive set theory CZF. Once again, this validates Streicher's axiom K.
4. There is a groupoid model inside realizability models which allows us to interpret type theory *without* Streicher's K. This is preliminary work by Steve Awodey and myself.

We really need to sort out the constructive status of Univalence.

# Answer
> 7 votes
I'm no HoTT person, but I'll throw in my two-cents.

Suppose we are wanting to make a function $$f\_A : \prod\_{x,y : A}\prod\_{p : x =\_A y} C(x,y,p)$$ How would we do this? Well, suppose we're given any $x,y : A$ and a proof of their equality $p : x =\_A y$. Since I know nothing about the arbitrary type $A$, I know nothing about the \`structure' of $x,y$. However, I know something about the specific equality type: it has a single constructor, $$\mathsf{refl}\_a : a =\_A a, \text{ for any } a : A$$ Hence, $p \equiv \mathsf{refl}\_a$ for some $a : A$, but this would force $x=a=y$. Hence, if we had an element of $C(x,x,\mathsf{refl}\_x)$ for any $x : A$; ie if we had a function $$base\_C : \prod\_{x:A}C(x,x,\mathsf{refl}\_x)$$ (for our specific $C$), then our function $f\_A$ can be defined as follows: $$f\_A(x,y,p) := base\_C(x,x,p)$$.

Getting rid of the subscripts leads to the general inductive definition.

Hope that helps!

---

PS. I'm no HoTT guy, so I'm assuming \`Axiom K'. More precisely, I'm assuming that an element $e$ of type $E$ must be the result of repeated applications of constructor of $E$. As far as I know, HoTT, probably chapter 2 onwards, throws away this notion ... and that makes absolutely no sense to me.

# Answer
> 3 votes
I'm an *amateur* HoTT guy, so I'll try to complement Moses' already great answer. Let me take the type $A\times B$ as an example. The basic principle of constructive type theory, as outlined by Martin-Löf, is that \*every element of $A\times B$ is described as being in the image of the constructor: $$ \mathrm{pair}\ :\ A\rightarrow B\rightarrow A\times B$$ This philosophy allows us to define *elimination*: to build a function $f$ *out* of $A\times B$, it suffices to describe its action on the *image of $\mathrm{pair}$*.

But since $\mathrm{pair}$ is a constructor (and so is in particular injective), this means exactly that to build a function $f:A\times B\rightarrow C$, it suffices to describe it's action on a pair of elements in $A$ and $B$, so $$f':A\rightarrow B\rightarrow C $$ is sufficient to describe such an $f$. In conclusion, there is a canonical way to define functions out of $A\times B$, and this can be encapsulated in the type $$(A\rightarrow B\rightarrow C)\rightarrow(A\times B\rightarrow C) $$ but this is exactly the type of $\mathrm{ind}\_{A\times B}$.

But this is only half of the story: what happens if this newly constructed $f$ is applied to a *given* $\mathrm{pair}(a,b)$? Well then $f$ should agree with its defining function $f'$, i.e. $$ f(\mathrm{pair}(a,b))\ :=\ f'\ a\ b$$ i.e. $$\mathrm{ind}\_{A\times B}\ f'\ \mathrm{pair}(a,b)\ :=\ f'\ a\ b $$ and this should hold **definitionally** (or *computationally*), which means the two should be completely interchangeable in all situations (which is much different from the $=$ in HoTT).

So you see that the definition of an eliminator for inductive type with given constructors comes in 2 steps:

1. an *existence principle*, which describes the type of $\mathrm{ind}$.
2. a *coherence principle* which defines the computational behavior of $\mathrm{ind}$. In category theory, this would correspond to *uniqueness* of the eliminator in some sense.

---

Let me argue that this is the same for the $=\_A$ type. We want to build, given $x,y:A$ and $p:x=y$, an element of $C$ (we're forgetting the dependencies for simplification). To do that, we need to *assume* that $p$ was built using a constructor for the type $x=y$, *which can only be* $\mathrm{refl}(z)$ for some $z$. This means that to give a function $$f:\Pi x, y:A, x=y\rightarrow C$$ it suffices to give a function $$f':\Pi z:A, C $$ which is defined for $\mathrm{refl}(z)$ (again, forgetting the dependencies in $C$).

Now what does the coherence principle say? Well simply that if applied to a known constructor, $f$ should behave like $f'$, which means $$f\ z\ z\ \mathrm{refl}(z):= f'\ z $$

But that's exactly what you have above! The same principle that gave us the existence and coherence for the eliminator of $A\times B$ gives us the existence and coherence for the eliminator of $=\_A$.

---
Tags: induction, dependent-types, homotopy-type-theory
---


# Question
Title: Preserving connectivity from a vertex by edges deletion
Given a connected graph $G$ and a vertex $v$, is it polynomially solvable to find a maximal cardinality set of edges incident to $v$, which deletion (still) leaves vertex $v$ to be connected with all the other vertices in $G$?

# Answer
> 1 votes
Construct a DFS traversal tree, starting from $v$.

You can remove all edges of v that are not part of the tree.

The tree construction costs $O(|V|+|E|)$.

The identification of the edges that can be removed is $O(deg(v))$.

---
Tags: algorithms, complexity-theory, time-complexity, graph-algorithms
---


# Question
Title: How to prove that a predicate is prefix closed
Suppose we have the predicate

$\qquad A.p.q ≡ (∀i \mid p≤i≤j\<q : X.i≤X.j)$

which says that $X\[p..q)$ is ascending.

Apparently, the predicate holds for empty segments, is prefix closed and is postfix closed.

I would like to prove that the predicate above is indeed prefix closed, but I am not able to; that is, I am unable to prove that

$\qquad A.p.q \implies (∀s \mid p≤s≤q : A.p.s)$

and I wondered if somebody could help?

# Answer
> 2 votes
Your predicate states that $X\_p \leq X\_{p+1} \leq \cdots \leq X\_{q-1}$. If you take any subinterval of $\[p,q)$, say $\[p',q')$, you will still have $X\_{p'} \leq X\_{p'+1} \leq \cdots \leq X\_{q'}$. In other words, a subinterval of a non-decreasing sequence is also non-decreasing.

Now that you know why what you want to prove is true, it remains to prove it formally. Always remember: the first step is to understand *why* something is true, and only then should you try to prove it. In fact, most of the time in mathematics and computer science we skip the second step, that of proving things formally, since it obscures the situation.

---
Tags: logic, proof-techniques, first-order-logic
---


# Question
Title: How to decode multiple-digit gamma codes and get the gap sequence?
How to decode gamma code ($\gamma$ code):

```
1110001110101011111101101111011

```

and get the gap sequence?

Detailed information about Gamma codes ($\gamma$ codes) with a brief example of decoding can be found here.

But in their example there is only one case when gamma code ($\gamma$ code) consists of one digit only, how to deal with multiple digits binary string?

# Answer
The above sequence it read as a concatination of 5 numbers:

You start from the left side, read the first unary code. It let's you know what is the length of the first number. The 2nd number starts right after the 1st, and you interpet it the same way.

1. First, read the first unary code, it is 1110 - so the first number is "1110:001", which is 9
2. The next unary code is right after this, and is: "110" - so the 2nd number is "110:10" which is 6
3. The next unary code is "10", and the 3rd number is "10:1", which is 3
4. The next unary code is "111110", and the 4th number is "111110:11011", which is 32+16+8+2+1=59
5. Next unary number is "110", which gives you the 5th and last number, which is "110:11", which is 7.

So, the decoding of the given gamma code is actually 9,6,3,59,7
> 5 votes

# Answer
When encoding several numbers in sequence, we simply concatenate the encodings of the individual numbers. The gamma code is an example of a prefix-free code: no codeword is a prefix of another codeword. Due to this property, the encoding of every string has a *unique* prefix which is a codeword; this prefix encodes the first number. After removing it, you continue to find the second number, and so on, until exhausting the string.

As an example, let's decode 000100000100. The only prefix forming a codeword is 0001000, encoding 8. Removing this, we are left with 00100, which encodes 4. So the complete decoded sequence is 8,4.

As an aside, the gamma code is *complete*, which means that almost every infinite string (in fact, every infinite string other than $0^\omega$) is the encoding of some infinite sequence of numbers.
> 2 votes

---
Tags: algorithms, data-compression, coding-theory, information-retrieval
---


# Question
Title: Is my simplified explaination of the XOR swap correct?
The XOR swap is a well-known in-place algorithm to swap two values, by XOR:ing them bitwise. It goes as follows:

```
a = a ^ b
b = a ^ b
a = a ^ b

```

Now, I was thinking to myself if I can find a way to help with my intuition regarding this algorithm. And here's what I thought of:

Bitwise XOR is the same as bitwise addition (1 + 1 = 0, as the carry is lost). Hence, if we write down the operations as addition, we get:

```
a = a + b
b = a + b + b
a = a + b + a + b + b

```

I then cancel any matching pair, i.e. b simply becomes a and a becomes b + b + b, which becomes b.

This is all very simple, so does it hold up to scrutiny?

# Answer
> 3 votes
Your proof is correct in intention, but the style is not adequate.

Of course, there is no perfect style, and most of us could improve their style, myself included.

Still, hoping readers will not be too harsh, here is an attempt at writing it, as an example, following your own proof. It may be too verbose, one of my own failings. (it is also a bit intentional here)

Actually the style usually depends also on the audience you are addressing. If the intended audience is very competent in the field, you can skip a lot of details. Nevertheless, careful notation always helps (like the indexing $a\_0$ below).

---

The XOR swap is a well-known in-place algorithm to swap two values, by XOR:ing them bitwise. It goes as follows for two variables `a` and `b`, using the notation of the C programming language:

```
a = a^b

b = a^b

a = a^b

```

**Correctness proof**

We note the XOR operation $\oplus$ as is common in mathematical uses. This notation is justified by the isomorphism between XOR on the booleans and the addition in $\mathbb{Z}/2$.

The algebraic properties of XOR extend to bitwise operations on bit vectors (i.e., sequences of bits) of equal sizes. In particular it remains associative and commutative, and we have for any sequence $x$ of bits: $x\oplus x=\vec{0}$ where $\vec{0}$ is a bit vector of $0$´s of the same length, and $x\oplus\vec{0}=x$.

Assume the initial values of `a` and `b` are respectively $a\_0$ and $b\_0$.

The 3 assigments above are then equivalent to:

`a =`$a\_0\oplus b\_0$

`b =`$(a\_0\oplus b\_0)\oplus b\_0$ which simplifies algebraically to $a\_0$ as indicated above

`a =`$(a\_0\oplus b\_0)\oplus a\_0$ which simplifies to $b\_0$

The initials values of `a` and `b` have been swapped bitwise. $\\;\Box$

---

Though I may be in some disagreement over this with other users, I do not see the usefulness for this proof of insisting on the relation between XOR and addition (other than for justifying the notation). Of course, the generalized view of Yuval Filmus\] brings wider understanding, but the point for me is to have a simple proof, not to write a treatise.

Note that I have been using distinct notation for syntax (taken fron C) and for the semantics of these operations. This justifies having two notations for the XOR operator, and gives a cleaner presentation of the proof, which may sometimes be important.

Of course, one is not always that careful, but it is better to have these principles in mind, without overdoing it, depending on the purpose and audience of what is being written. I think the most important here was to distinguish `a` and $a\_0$.

Hoping this version will satisfy most readers. Further comments welcome.

*With my thanks to all for all the very useful comments.* *Perfection is not of this world.*

# Answer
> 3 votes
Let me mention a generalization of this algorithm, which works in any Abelian group: $$ \begin{align\*} x\_\text{temp} &= x\_\text{in} + y\_\text{in} \\ y\_\text{out} &= x\_\text{temp} - y\_\text{in} \\ x\_\text{out} &= x\_\text{temp} - y\_\text{out} \end{align\*} $$ The proof is left to the reader. Your case corresponds to the group $\mathbb{Z}\_2^n$, in which both operations $+$ and $-$ correspond to XOR.

---
Tags: algorithms, boolean-algebra, xor
---


# Question
Title: Why does reduction from vertex cover to subset sum use base-4?
Why does reduction from vertex cover to subset sum use base-4?

30.13 Subset Sum (from Vertex Cover)

# Answer
The exact base used is somewhat arbitrary. Since each "digit" could be as big as $2$, then you need to use base $b \geq 3$. Jeff probably chose $b = 4$ since it is the smallest power of $2$ which is at least $3$. Assuming your tape alphabet is binary, it is marginally simpler to handle bases which are powers of $2$. He might have well have chosen any (fixed) base $b \geq 3$, or even allow the base to very mildly with $n$.
> 6 votes

---
Tags: complexity-theory, reductions, proof-techniques
---