# Question
Title: Identification and the definition of data type
A frequently cited definition of data type is that it is a set of values and a set of operations of those values.

I've never read any mention along the lines of a type must be capable of being identified, although the programming languages I've encountered use names to distinguish different types.

* Is the use of identifiers then just a convenience for the programmer? In principle, couldn't you just replace the identifier with the type definition each time it was needed?
* Are there any programming languages that don't use named types?
* And, if so, what implications, if any, are there of this? (One possibility I can think of is that it means there is no nominal typing.)

# Answer
> 3 votes
> Is the use of identifiers then just a convenience for the programmer? In principle, couldn't you just replace the identifier with the type definition each time it was needed?

Yes. You can have a strongly typed language that completely infers types, where the program at no point refers to the types, at all, ever.

For example, you could write programs in Hindley Milner (without the gamut of extensions you see in something like Haskell) without ever referring to a type. You shouldn't, but you could.

Types and values are usually separate in non-dependently typed programs, and if your system allows for full type reconstruction, you don't need to refer to them in your code.

> Are there any programming languages that don't use named types?

Doubtful. When you use an integer but the program expects a boolean, the compiler has to tell you *something*. So it's going to want to give a name to those types.

Without primitive types, you can't do much useful in a programming language, so you're going to want to at least give your primitive types names.

Also, having all sum-types be anonymous would be extremely tedious. You *could* refer to the `List` type as `T . T = Nil + Cons T`, and occasionally you will see something like this on paper, but this is going to get hard to use very fast. As you can see, recursive types are particularly awkward in this scheme, and you usually end up needing the type-level equivalent of the $Y$-combinator.

Now, if you use things like Church encoding, you can get away without having primitive types, where everything is probably going to be higher-rank polymorphic types. For example, you can encode natural numbers as `forall a . (a -> a) -> a -> a`. But again, this is something more useful on paper than in the hands of a programmer.

> And, if so, what implications, if any, are there of this?

None that I can think of, other than the lack of nominal typing, and you could even fake nominal typing by attaching some singleton type to your values.

For example, `((), forall a . (a -> a) -> a -> a)` is isomorphic to `forall a . (a -> a) -> a -> a`, but now you have two isomorphic types the system considers distinct.

---
Tags: typing
---


# Question
Title: What is the complexity of Array[n] and Object.value
I faced a great doubt about the Complexity of two ways of calling a information.

First I have an Array, if I call an array in a program like this:

```
print array[0]

```

This process will be O(1) as I understand.

But what is the complexity of something like this:

```
class Obj:
    value = 1
print Obj.value

```

Is this complexity is the same of callin and array by Index? If we ignore the process to create the object.

# Answer
If you have CPython in mind then yes, the both are $O(1)$.
To get array by index the address is calculated as pointer to first element + index * size of element, and for object, which uses struct it is pointer to struct + offset, where offset is calculated at compilation.

The general runtime of operations depends solely on data structure used internally by given implementation of language (please note that language itself might not indicate what structure must be used and the very same language might have different structures using different vendors). It may be offset table, hash table, balanced tree etc.
> 2 votes

---
Tags: algorithm-analysis, data-structures, programming-languages, runtime-analysis
---


title: Why not space out memory allocations?

text:
# Question
Title: Why not space out memory allocations?
In ext4 file system, the files are spaced out as far apart as reasonably possible to allow for efficient reallocation. Why do we not do this in memory?

Why not allocate one memory as page 20, and the next large allocation as page 100 to allow for excess expansion before and after the current allocation? I feel that makes sense for large frequently changing-in-size buffers. For smaller buffers, doing so would probably be a drain on memory because we have to allocate each page for a small amount of bytes(but perhaps do it within a block too in the malloc impl). This would also provide greater memory corruption prevention, allowing segfaults(or windows equivalent) to happen quicker(specifically for larger buffers).

Why don't we do this? I get it on modern 32-bit systems because of limited address space, but why not on 64-bit?

# Answer
> 2 votes
## Why is memory different from a hard disk?

Because hard disks have different performance characteristics than RAM.

With hard disks, seeking is extremely slow. Sequential reads are much faster than random-access reads. In other words, it's much faster to read data that is stored consecutively than to store data that's scattered all around the disk. Therefore, there are benefits to making sure your files are contiguous, as much as possible.

RAM doesn't have the same property. With RAM, there is no penalty for "seeking". You can pick any page and read from it, and the cost will be the same, no matter where the page is located. For instance, reading page X and then page Y will have the same cost regardless of whether X and Y are adjacent or not.

So, you end up with different algorithms that are optimized for hardware with different performance characteristics.

Why do hard disks have this strange property? Because they are based on a rotating piece of iron. If you read block X on the hard disk, and next want to read block Y, but Y is on the other side of the platter, then you'll have to wait for the platter to finish rotating far enough for Y to be under the read head. That takes time. RAM doesn't have this property.

Interestingly, the differences are becoming less these days. Today, SSD (solid state storage devices, based on Flash storage) are becoming a popular replacement for hard disks. SSD's have their own performance characteristics, but they're more like RAM than like magnetic hard disks. This means that the filesystem optimizations you'd do for a SSD-oriented filesystem are different from the ones you'd do for a hard-drive-oriented filesystem. Many of today's filesystems were designed decades ago when magnetic hard disks were dominant, and optimize for the performance characteristics of magnetic hard disks.

## Why not harden software by deliberately leaving space between buffers?

You are implicitly proposing a scheme for making software more robust against out-of-bounds errors and buffer overruns: leave plenty of unallocated space between each pair of buffers allocated on the heap.

That's not a bad idea. It's been proposed before and studied in considerable depth. It does add some robustness against bugs. It can also make buffer overrun attacks harder, especially if you randomize the location of all heap buffers. It's also relatively easy to deploy in a way that is compatible with legacy software. So it does have some quite attractive advantages.

However, it also has some disadvantages. It imposes some performance overhead -- not a huge amount, but enough to be a bit painful. Why does it impose performance overhead? Largely because it reduces spatial locality. Consider two 16-byte allocations. Current allocators try to pack them together into a single page. In your scheme, we'd have to put each allocation onto its own page. That means we have a lot more pages, which means that we get a lower TLB hit rate.

There are different variants on this scheme, with different performance implications, but they all run up against the challenge: in exchange for the robustness and security benefits, there is some non-zero performance overhead. So that's one reason why people might not adopt it.

The other big reason is: we're using platforms and allocators that were designed decades ago. At the time, security wasn't as critical as it is today, so this sounded like a pretty unattractive proposal: I get to implement something more complicated and fiddly, and it'll make my entire system slower? No thanks.

Today given the magnitude of security problems we're facing, there's gradually increasing interest in these alternatives. But they still face an uphill battle, because of the non-zero performance implications.

To learn more about academic research on this subject, read research papers on the Diehard, Dieharder, and Archipelago systems. They discuss the design in a very accessible way and measure the performance and other costs of such a scheme. If you're still intrigued, you can explore the literature where other researchers have explored other points in the design space to understand their implications.

Bottom line: you're not the first to think of this, and it is a pretty attractive idea, but it also comes with some significant costs.

---
Tags: memory-management, virtual-memory, memory-allocation
---


# Question
Title: Complexity of matrix inverse via Gaussian elimination
I'm trying to determine the exact complexity of finding an $n\times n$ matrix inverse of $A$. If it is known that the complexity of Gaussian elimination is $\frac{2}{3}n^3 + \frac{1}{2}n^2+O(n)$, then is it true that the complexity of finding $A^{-1}$ should be about twice same, since we are effectively doing two sets of Gaussian eliminations in parallel plus some row interchanges and multiplications?

Please correct me if I'm wrong.

# Answer
> 1 votes
No, it's not true. You *can* use Gaussian elimination to invert a matrix in $O(n^3)$ time, but there are other algorithms that are even faster. The complexity of a problem is the running time of the *fastest* algorithm for that problem. Therefore, it is not correct that the complexity of matrix inversion is $\Theta(n^3)$.

See https://en.wikipedia.org/wiki/Gaussian\_elimination#Computational\_efficiency, https://en.wikipedia.org/wiki/Matrix\_multiplication\_algorithm, https://en.wikipedia.org/wiki/Computational\_complexity\_of\_mathematical\_operations#Matrix\_algebra, https://scicomp.stackexchange.com/q/22105/4274, Complexity class of Matrix Inversion.

---
Tags: time-complexity, matrices, linear-algebra
---


# Question
Title: Busy Beaver machines on semi-infinite tape
The Busy Beaver problem is to find the largest number of non-blank characters that are printed by a terminating Turing machine of no more than a given size on the blank input.

The usual Busy Beaver machines run on a blank tape that is infinite in both directions.

> Is there any research (and/or experiments) on Busy Beavers machines that run on a *semi-infinite* tape? (the Turing machine's head is initially positioned on the first cell of the tape)

With a semi-infinite tape we must also consider what happens if the head tries to cross the boundary at the beginning of the tape; the two approaches:

* the computation halts
* the head "bounces" to cell 2

probably lead to different results.

# Answer
> 3 votes
We look to the first approach in this answer.

Let us denote this new function by $\Sigma\_{\mathrm{semi}}(n)$.

Also, call the function of the second approach $\Sigma\_{\mathrm{bounce}}(n)$.

Also, denote the original Busy Beaver function by $\Sigma(n)$.

First note that $\Sigma(n) \geq \Sigma\_{\mathrm{semi}}(n)$ and $\Sigma\_{\mathrm{bounce}}(n) \geq \Sigma\_{\mathrm{semi}}(n)$, since every program that works for semi also works for bounce and the original version.

## Uncomputability of $\Sigma\_{\mathrm{semi}}(n)$

In this part of the answer, I'll prove that $\Sigma\_{\mathrm{semi}}(14n+3)\>\Sigma(n)$, therefore it is uncomputable. (If it were computable, then $\Sigma(n)$ would be upper-bounded by a computable function, contradiction.)

This implies that $\Sigma\_{\mathrm{bounce}}(n)$ is also uncomputable.

### Definitions

Number all cells on the tape, starting with 1 for the first cell.

We call the number of the cell the *index*.

Group every pair of consecutive cells such that the first cell in the pair has an on the tape into one *macro cell*, so the tape looks like

```
(1,2)(3,4)(5,6)(7,8)....

```

### Constructing a new machine

Consider the Busy Beaver with $n$ states that leaves $\Sigma(n)$ ones on the tape with states $B\_1, B\_2, B\_3, \cdots B\_n$. We leave the new symbol and direction intact, but instead of going to a new state $B\_i$, we go to $B\_{i,\mathrm{left}}$ if the direction is left, and to $B\_{i,\mathrm{right}}$ if the direction is right. (Exception: If the new state is $\mathrm{HALT}$, then it remains $\mathrm{HALT}$.) We construct a machine that needs additional states for each state $B\_k$.

The idea of this machine is that all cells with odd index contain exactly two ones: One that is further to the right than any one in a cell with an even index, and one that is at the cell with index 1. If we read the leftmost one, we know that we are on the edge of the tape and then we move the whole tape with even index two indices to the right. Because of the rightmost one we know up to where we should move the tape. So every cell with an even index will be used for executing a normal Turing machine. The cells with odd index will be used to ensure the Turing Machine doesn't run of the tape.

Anyway, here are the states:

* $B\_{k,\mathrm{right}}$ (odd index): This has the following ruleset:

+ If it reads a zero, then we go to the right, keep the symbol a zero and go to state $B\_k$.
    + If it reads a one, then we go to the right, make the symbol a zero and go to state $B\_{k,1}$.
* $B\_{k,1}$ (even index): This has the following ruleset:

+ It doesn't change the symbol it reads and goes to the right and to state $B\_{k,2}$.
* $B\_{k,2}$ (odd index): This has the following ruleset:

+ If it reads a zero, it changes this into an one and goes to the left and to state $B\_{k}$.
    + It is not possible to read a one in this state. When the machine enters this state, it is on a cell with an odd index. However, we removed a one in state $B\_{k,\mathrm{right}}$ two steps before this, so only the leftmost one remains and we are certainly more to the right than that one.
* $B\_{k,\mathrm{left}}$ (odd index): This has the following ruleset:

+ If it reads a zero, then we go to the left, keep the symbol a zero and go to state $B\_k$.
    + If it reads a one, then we go to the right, keep the symbol a one and go to state $B\_{k,3}$.
* $B\_{k,3}$ (even index): This has the following ruleset:

+ If it reads a zero, it writes a zero and goes to the right and to state $B\_{k,4}$
    + If it reads a one, it writes a zero and goes to the right and to state $B\_{k,7}$
* $B\_{k,4}$ (odd index): This has the following ruleset:

+ If it reads a zero, it writes a zero and goes to the right and to state $B\_{k,3}$
    + If it reads a one, it writes a zero and goes to the right and to state $B\_{k,5}$
* $B\_{k,5}$ (even index): This has the following ruleset:

+ If it reads a zero, it writes a zero and goes to the right and to state $B\_{k,9}$
    + It is not possible to read an one, because we read the rightmost one on the odd index before this cell and thus the rightmost one on the tape.
* $B\_{k,6}$ (even index): This has the following ruleset:

+ If it reads a zero, it writes an one and goes to the right and to state $B\_{k,4}$
    + If it reads a one, it writes an one and goes to the right and to state $B\_{k,7}$
* $B\_{k,7}$ (odd index): This has the following ruleset:

+ If it reads a zero, it writes a zero and goes to the right and to state $B\_{k,6}$
    + If it reads a one, it writes a zero and goes to the right and to state $B\_{k,8}$
* $B\_{k,8}$ (even index): This has the following ruleset:

+ If it reads a zero, it writes a one and goes to the right and to state $B\_{k,9}$
    + It is not possible to read an one, because we read the rightmost one on the odd index before this cell and thus the rightmost one on the tape.
* $B\_{k,9}$ (odd index): This has the following ruleset:

+ If it reads a zero, it writes a one and goes to the left and to state $B\_{k,10}$
    + It is not possible to read an one, because we read the rightmost one on the odd index before this cell and thus the rightmost one on the tape.
* $B\_{k,10}$ (even index): This has the following ruleset:

+ It doesn't change the symbol it reads and goes to the left and to state $B\_{k,11}$.
* $B\_{k,11}$ (odd index): This has the following ruleset:
    + If it reads a zero, it leaves a zero, goes to the left and to state $B\_{k,10}$.
    + If it reads a one, than this is the leftmost one. It leaves this one unchanged, moves to the right and to state $B\_k$.

If this helps, here are informal explanations of what the states $B\_{k,\mathrm{something}}$ do:

* $B\_{k,\mathrm{right}}$: Bring the head to the cell with the even index and notice that the rightmost one on the odd index needs to be moved.
* $B\_{k,1}$: Bring the head to the cell with the odd index.
* $B\_{k,2}$: Write the new rightmost one.
* $B\_{k,\mathrm{left}}$: Bring the head to the cell with the even index and notice that the tape needs to be moved.
* $B\_{k,3}$: Write moved zeroes on cells with even index.
* $B\_{k,4}$: Move the head to even index and notice the rightmost one.
* $B\_{k,5}$: Write moved zeroes on cells with even index after the rightmost one was noticed.
* $B\_{k,6}$: Write moved ones on cells with even index.
* $B\_{k,7}$: Move the head to even index and notice the rightmost one.
* $B\_{k,8}$: Write moved one on cells with even index after the rightmost one was noticed.
* $B\_{k,9}$: Write a new rightmost one.
* $B\_{k,10}$: Move to the position the head should be.
* $B\_{k,11}$: Move to the position the head should be and notice the leftmost one. Note that the original position where the head should have gone is one to the left of the end of the tape, so it is not one to the right of the tape.

### Initial setup for the new machine

Before we will run this machine, we will put an 1 in cell 1 and cell 3, and move the head of the machine to cell 2. So the tape looks like

```
(1,_)(1,_)(_,_)(_,_)....

```

This can be done using three states:

* State 1: It reads a zero. It writes an one. It goes to the right. It goes to state 2.
* State 2: It reads a zero. It writes a zero. It goes to the right. It goes to state 3.
* State 3: It reads a zero. It writes an one. It goes to the left. It goes to state $B\_1$, as defined above.

### Conclusion

We created a new machine with 14 states per original state and 3 states for the initial setup that simulates $\Sigma(n)$ on a semi-infinite tape. Therefore $$\Sigma\_{\mathrm{semi}}(14n+3) \> \Sigma(n)$$

Note that I didn't necessarily tried to optimize those constants, since I just wanted to show uncomputability.

---
Tags: reference-request, busy-beaver
---


# Question
Title: Are some real world compression algorithms sometimes producing unexpectedly large files?
Lossless compression is not magic. It just gives the common patterns a short notation, compensating by the less common patterns ending up with a longer notation. By that logic, all lossless compression algorithms must sometimes give you a larger file back. A real world example of that is for instance giving a file containing 'a' and a line feed to gzip (2 bytes), it subsequently returns a 30 byte file. In general, compression tools do not break even for very small files.

My question is: Are some compression utilities bloating out larger files by some significant amount? (While "Give this file to 7z and watch you harddrive fail!" is cool, things like "This 4kb file will grow to 6kb." are also good.)

I can see a reason why such behaviour might not exist. If you for instance always put an extra bit to the output telling if the file is actually compressed, or just the original file in the cases where the compression fails, your output can never be worse than the original file plus 1 bit. I am however not sure if any such protection against unexpected large files is used.

# Answer
> 1 votes
If you take vanilla RLE in bitmap which does not have any consecutive runs it will increase file size two times. It is apparently very rarely used fact that BMP, TIFF and PCX allows compression, (not all applications supporting these formats even implement RLE scheme). This is very pathological case and since it mostly increase file size it is abandoned.

Normal compression algorithms include information of failure, so instead of huge increase you can expect several bytes per chunk increase. In those that do not check there are three methods of checking how far we can increase file: take already compressed file, take encrypted file or find pathological cases from algorithm.

I have generated $256 \text{ bytes}$ file with consecutive numbers.
Compressed as 7z LZMA: $349 \text{ bytes}$, LZMA2:$356 \text{ bytes}$, Deflate or Deflate64: $400 \text{ bytes}$, bz2: $388 \text{ bytes}$, PPMd: $421 \text{ bytes}$ so not that cool.

---
Tags: algorithms, data-compression
---


# Question
Title: Proving complexity of computing product of matrices
If $A$ is a non-singular $n\times n$ matrix, $B$ is an $n\times p$ matrix, and $C$ is a $p\times n$ matrix (where $1\le p \ll n$), how does one prove that the complexity of $$D=A^{-1}(BC)$$ is $\frac{8}{3}N^3+2pn^2+O(n)$ flops?

I have no idea where to start. It is assumed that we do not compute $A^{-1}$ directly, but, instead, we compute the $LU$-factorization of $A$, and use $L$ and $U$ to compute the product $A^{-1}(BC)$ using the method of solving of multiple right-hand sides (whatever this means).

I would appreciate some help with this.

# Answer
> 5 votes
I'm afraid you can't. As I mentioned in my response to your previous question:

> The complexity of a problem is the running time of the *fastest* algorithm for that problem.

There exist algorithms for this problem whose running time is much less than $N^3$. As I described in my previous answer, there are much more efficient algorithms for matrix inversion (and for matrix multiplication). I linked to algorithms for both.

Therefore, you cannot prove that the complexity is $\frac83 N^3 + \dots$ flops -- because that isn't true.

Given your pair of questions, and since you said you're not sure where to start, I would suggest you start by reviewing the following material here on this site:

Then, read some material on fast algorithms for matrix multiplication and other matrix operations. That'll be a starting point, at least.

If what you want is to understand the running time of LU-factorization of a matrix, that's a different question. If that's your question, you should probably research that, and then post a new question, showing what research you've done.

---
Tags: complexity-theory, time-complexity, linear-algebra
---


# Question
Title: Embedding high dimensional vectors into low dimensional space preserving similarity
I have a collection of high dimensional vectors such as $\vec{a}\_{i} \in \mathbb{R}^{n}$ where $n$ is 3000. What I want to do is to embed these vectors into a space such as $\vec{b}\_{i} \in \[0, 255\]^{n}$ where $n$ in this case is now 32. I want to embed it (using any hash trick or something like that) in a way that will preserve similarity. For example, if I have the following two vectors that are very similar to each other:

$\vec{a}\_{1} = (1.2, 0.1, 0.4, 12.8, \ldots)$

$\vec{a}\_{2} = (1.1, 0.1, 0.4, 12.5, \ldots)$

I want these two vectors to end in the same "bucket" of this other space where the vectors belongs to $\[0, 255\]^{32}$. Note that **I don't want to use it for search**, I want similar vectors to be in the same "bucket" in this other low dimensional space. I was trying to use LSH but I wasn't able to figure out a way to solve this.

# Answer
Locality-sensitive hashing is one reasonable approach for this. I suggest reading standard resources on locality-sensitive hashing (LSH). In your case, a locality-sensitive hash is a hash function that maps $h:\mathbb{R}^n \to S$ where if $x,y \in \mathbb{R}^n$ are close enough, then we'll have $h(x)=h(y)$ with high probability.

To get started, tead https://en.wikipedia.org/wiki/Locality-sensitive\_hashing and https://cstheory.stackexchange.com/q/10053/5038.

Do understand that LSH is fundamentally *probabilistic*: if $x,y$ are similar, they will have a high probability of being mapped to the same bucket, but this cannot be guaranteed.

Alternatively, you might be interested in metric space embeddings. An embedding $E:\mathbb{R}^n \to \mathbb{R}^d$ has the property that if $x,y$ are close (i.e., $\\|x-y\\|\_2$ is not too large), then $E(x),E(y)$ will be close (i.e., $\\|E(x)-E(y)\\|\_2$ will be not too large). This could then provide a solution to your scheme, if you are satisfied that similar inputs map to buckets that are "nearby" but not necessarily identical.

For more on metric space embeddings, you can start with https://cs.stackexchange.com/a/27923/755, https://cstheory.stackexchange.com/a/6818/5038, https://cstheory.stackexchange.com/q/21487/5038, https://cstheory.stackexchange.com/questions/tagged/embeddings.
> 4 votes

---
Tags: hash, hashing
---


# Question
Title: AC-3 Algorithms on CSP problem, What is happened when enocunter to an empty domain variable?
Suppose We Applying Arc-Consistency (**AC3**) algorithms on one Constraint Satisfaction Problem, if domain of one variable be empty, what is the next step of this algorithm?

---

According to This Link and to Wikipedia's description of AC3: once one domain is empty, the algorithm stops, indicating there is no solution to the CSP.

This book says: if one domain of the non assigned variables becomes empty then backtracks to....

---

My challenge is about the behavior of this algorithms, i.e, in which phase (when) AC-3 stops, and when it's select Backtrack.

> Update: Anyone could describe the behaviors of AC-3 on empty domain in each phase?

---

**References**: This question asked 5 month ago on SO but I think the answer is wrong, because I add some references that shows other things.

# Answer
> 1 votes
You've misunderstood the book. It's not describing the AC-3 algorithm; it's describing some other algorithm. The book is describing an algorithm that combines both guess-and-backtrack together with arc consistency. The AC-3 algorithm doesn't do any guess-and-backtrack; it uses only arc consistency checks.

Thus, AC-3 *does* terminate if there is some variable whose domain set becomes empty; in this case, AC-3 declares the constraint system unsatisfiable (inconsistent). This is the correct thing to do, in the context of the AC-3 algorithm.

Of course, if you're talking about some totally different algorithm (like the book is), that other algorithm might do something totally different. No great surprise there.

I don't see anything wrong with the answer to the Stack Overflow question you link to.

# Answer
> 0 votes
At the very first phase when you give empty domain it is non-conditional failure - it is the same as saying: "I have a function $f(x) = x^2 + 1$, but $x \in {\emptyset}$, find me feasible solutions, which are none.
In the phase when arcs are getting cut you check if the values are consistent between two variables - here arc is either in solution or is inconsistent.
You have the same function as above and points: $x \in \\{0, 1\\}, y \in \\{1, 5\\}$. This makes one consistent pair, the second is cut, it will not be in the solution. At this point if there were more constraints you would check the consistency of related variables (You might call it backtrack, because another variable that is related takes part, but here you might find that there are no arc, and it is perfectly fine here). But if $x \in \\{23, 45\\}$ then you cannot find any good pair, but now it turns out that domains of $x$ is $\emptyset$, so something was inconsistent - with checked constraints you have no feassible points, so it is failure.

The sildes you have provided show that AC-3 is detecting wrong candidate for solution faster than forward checking. The outer scheme is backtracking solver, which at every step assumes one of possible values, assigns it and continues guessing values until it finds solution or contradiction (in such case it goes back to assumption made and changes it to different possible value). Slides show that propagating constraints is superior to propagating values, because it allow faster checking of error.

AC-3 in this context is used as black-box function to determine failure, but the pure algorithm itself does not backtrack - it operates on one given instance - candidate for solution, and it's output serves as indicator to backtracking.

---
Tags: artificial-intelligence, satisfiability, 3-sat, constraint-programming, constraint-satisfaction
---


# Question
Title: Overflow of integer counter in distributed systems
I've just been introduced to Paxos. There is notion of the of value that is incremented each time a new proposal is send. To provide order for proposals, something like time. What happens when this long or integer value overflows and starts from zero again. The proposed sequence number will become lower than the old one and every proposal will be rejected.

Thank you.

# Answer
> 3 votes
In general:

> Paxos algorithm uses unbounded integers to tag data. In practice, however, every integer handled by the processors is bounded by some constant $2^b$ where $b$ is the integer memory size. Yet, if every integer variable is initialized to a very low value, the **time** needed for any such variable **to reach the maximum value** $2^b$ is actually **way larger than any reasonable system’s timescale**. For instance, counting from $0$ to $2^{64}$ by incrementing every nanosecond takes roughly 500 years to complete. Such a long sequence is said to be practically infinite.

Self-stabilizing systems:

> One particular aspect of self-stabilizing systems is the need to re-examine the assumption concerning the use of (practically) unbounded time-stamps. While in practice it is reasonable for Paxos to assume that a bounded value, represented by 64 bits, is a natural (unbounded) number, for all practical considerations, in the scope of self-stabilization the 64 bits value may be corrupted by a transient fault to its maximal value at once, and still recovery following such a transient fault must be guaranteed.

Source: Self-Stabilizing Paxos

---
Tags: distributed-systems, arithmetic
---


# Question
Title: What is the reason behind a specific ordering of the rows in the generator matrix for Hamming codes?
What order the rows are in a Hamming generator matrix are irrelevant for the Hamming coding to work, given the check matrix is built accoridngly.

In order to limit cognitive overload, it could have been decided that the "official" way of doing it should be either all data rows first then all parity rows after, all in ascending order, or just all rows in ascending order. In that case, in the description of a communications protocol it would be enough to specify the number of bits without providing the generator matrix, and everyone would know how to implement it. Very simple software libraries could be written which implement it.

However, after looking at some implementations, this is not the case. People seem to use arbitrary matrices, such as

$$\begin{pmatrix} 1 & 1 & 0 & 1 \\ 1 & 0 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 1 & 1 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \end{pmatrix}$$

Is there a reason why one such ordering would be superior to other orderings?

# Answer
> 6 votes
If a single-bit error correction is attempted, the ordering presented in the example guarantees that the syndrome vector (the result of the multiplication of the checking matrix and the received data), if interpreted as an integer, will indicate the position of the error. Otherwise, a lookup table would have to be used.

---
Tags: coding-theory, hamming-code
---


# Question
Title: What is a program in self-replicating programs?
I'm trying to understand the workings of artificial life as exemplified by systems like Tierra or Avida. The idea behind these systems is that organisms are modeled as assembly-language programs that replicate themselves in the memory of a computer, possibly a virtual machine. But here there is already something I don't understand (I'm not a programmer by vocation or by nature).

My idea of a computer's memory is that it's basically just a list of instructions. By default control proceeds from a given instruction to the next one in the list, but the instruction itself can send control someplace else. My question is: which sublists of this list of instructions count as programs?

Presumably the memory can be partitioned (in the set-theoretic sense) into a bunch of programs (actually copies of programs, since distinct "organisms" are allowed to have the same "genome"), plus some empty space; how does one do this?

# Answer
> 4 votes
The computer's operating system keeps track of which pieces of memory make up which program. The partition into programs is entirely arbitrary, and the only reason a section of memory counts as program is because there is a specially designated piece of memory that keeps a list of all "programs" and their memory locations.

# Answer
> 2 votes
Adding on Tom van der Zanden's answer, for most existing artificial evolution systems (for sure Tierra) a program is a sequence of instructions subject to strict limitations.

* **limitations to preserve the organism (program) structural integrity** (*cellularity-constraints* in Tierra). E.g.

+ each organism has exclusive write privilege to its own code;
    + an organism can examine and even execute the code of another organism but NOT overwrite it.
* **language level limitations**. E.g. `jmp` instructions, when available, are somewhat restricted. For example Tierra uses a *template* (a sort of biological inspired pattern matching) instead of an absolute / relative address.

Constraints on the instruction set and on the structure of the organism are key elements in systems like Tierra or Avida since they concur to define what an organism is (together with the "list of all programs").

> which sublist of this list of instructions count as programs?

"The entire list count as a program": usually a special machine language with a limited instruction set is used. It's studied to be less fragile to mutation and failures than a standard machine language.

Anyway errors that cause instructions to fail make them have no effect.

---
Tags: simulation, bio-inspired-computing
---


# Question
Title: Getting speed difference between signal comparison using Dynamic Time Warping
I understand that Dynamic Time Warping is an algorithm to find a matching between two signals with different length and speed

But is there a possible way to find the speed difference between the two signals being compared?

To clarify my question. I am working on a project to find similarity between two motions. The data being compared is in the form of Quaternion. By using DTW I was able to find the similarity/ dis-similarity between these motion signals, However I would like to know is there a way to find if one motion signal is slower/faster than the other. Ex: both motions are actually similar, but one of the motion is slower than the other

# Answer
There is no single "speed difference". The way DTW works is that it checks whether you can find a match by slowing up and/or speeding up one of the signals.

For instance, suppose you want to match signal X to signal Y, which last 3 minutes. It's possible that the best match might involve speeding up signal Y for the first minute, slowing it down for the second minute, and leaving its speed unchanged for the third minute. Thus, there's no one speed, no one speed difference, and no simple answer to whether Y is faster than X or not. Rather, the answer is: "faster in parts, slower in others".

Once you find the best match using DTW, you can easily recover in which parts Y was faster than X, and in which parts Y was slower than X. I encourage you to do a bit more reading about how DTW works -- it'll probably all become clear as you understand the gist of the idea.
> 1 votes

# Answer
DTW is designed to handling local changes in timing. Global changes is time are referred to as Uniform Scaling \[a\].

You can create a FOR loop, loop over all possible Uniform Scalings, and record the one that has the lowest distance (under either euclidean distance, or DTW, or both \[b\])

That degree of Uniform Scaling is then your prediction of the speed relative to the oracle.

I have done this for guestures, speech, music etc.

Note that the range of all possible Uniform Scalings, should be limited, maybe something like 70 to 200%.

Eamonn

\[a\] http://www.cs.ucr.edu/~eamonn/vldb04.pdf \[b\] http://www.cs.ucr.edu/~eamonn/vldb05.pdf
> 1 votes

---
Tags: algorithms, machine-learning, dynamic-programming, pattern-recognition, time-series-analysis
---


# Question
Title: Closed form solution for optimization problem
Consider the problem of finding the real-valued matrix $C$ so that

$$\\|S-AC\\|\_F^2\qquad(1)$$

is minimal. ($S$ and $A$ are real valued matrices and $\_F$ denotes the Frobenius norm). This problem has a closed form solution of $C=A^+S$, where $A^+$ is the pseudo-inverse of $A$.

I need to control the magnitude of the elements in $C$, that is an extra regularization term $\varepsilon\\|C\\|\_F^2$ must be added to (1). Is it there a closed form solution for minimizing

$$\\|S-AC\\|\_F^2 + \varepsilon\\|C\\|\_F^2\\,?\qquad(2)$$

# Answer
There is a closed-form solution to your problem, but first it helps to know two facts to derive the minimizer. The first fact is that we can re-write the Frobenius norm squared as a trace operation. Namely, $$\\|C\\|^2\_F = \text{Tr}\left\[CC'\right\],$$ where $C'$ denotes the transpose of $C$. The second fact is the derivative of the Frobenius norm squared, which is given by $$\frac{\partial}{\partial C} \text{Tr}\left\[(S - AC)(S - AC)'\right\] = -2A' (S - AC).$$

Luckily for us the derivative of sums is equal to the sum of the derivatives (i.e., the derivative is a linear function). So we can take the derivative of the objective with respect to $C$ piecemeal. We end up with $$\frac{\partial}{\partial C} \\|S - AC\\|^2\_F + \lambda\\|C\\|^2\_F = -2A' (S - AC) + 2\lambda C.$$ Setting this equal to 0 and solving we have, $$\begin{align\*} -2A' (S - AC) + 2\lambda C &= 0 \Leftrightarrow \\ -2A'S + 2A'AC + 2\lambda C &=0 \Leftrightarrow \\ -2A'S + 2(A'A + \lambda I)C & = 0 \Leftrightarrow \\ C &= (A'A + \lambda I)^{-1}A'S, \end{align\*}$$ where $I$ is the identity matrix.

An eigendecomposition of this result gives more insight into the behavior. Put simply, you add $\lambda$ to the eigenvalues of the $A'A$ matrix which should shrink your final estimates. This is a form of regularization known as ridge regression. Except here we are applying it for multivariate multi regression instead of linear regression.
> 5 votes

---
Tags: optimization, machine-learning, linear-algebra
---


# Question
Title: Why are Python 2 and 3 so incompatible with each other?
Every software should have backward compatibility (at least some sense of it), this ensures old codes can run in the future updated systems without any problems in most situations. But why did the Python team decide to make the v3 a new language? The community has to split up into two and every computer has to install both v2 and v3 in order to run every python code. This is a huge mess. Is there a computer science reason behind this decision?

# Answer
> 5 votes
The saying goes, "In C++11, 11 is the number of legs the stapled onto the dog to make a better octopus".

As with basically everything in Computer Science, this is all about tradeoffs.

If you focus on backwards compatibility, you have potentially conflicting features interacting with each other. You're stuck with the design choices that were initially made, when you didn't have the knowledge and data that years of production use provide.

Breaking changes, conversely, have the disadvantage of breaking old code, though with Python 2, usually files could be converted mechanically.

Now, there are also questions of "what makes a language?"

From a semantics point of view, every time you add a new feature to a language, you have effectively defined a new language with different semantics. There are nice formalisms for dealing with this: for example, some extensions to languages are conservative, meaning you're only expressing features that the start language could express.

Python 2 to 3 was not an extension, let alone a conservative one. So from a theory point of view, they're different languages, that happen to share a name, most syntax, and a real-life community.

Java broke backwards compatability when they decided to be a different language from C++ or SmallTalk or Eiffel. At the end of the day, the lines between languages and dialects and versions can be blurry, and the decision will come down to what is viewed as the most pragmatic for developers.

---
Tags: programming-languages
---


# Question
Title: Hash multiple integers directly using FNV-1a
An alternative version of FNV-1a hash spread on the internet, which operates directly on integers instead of bytes. The offset basis and prime are the same used in the original version, which operates on bytes.

With this version, is the statistical quality of the produced hash similar to the original algorithm?

Alternative version operating on integers:

```
#include <cstdint>

#define OFFSET_BASIS 2166136261ul
#define FNV_PRIME 16777619ul

uint32_t hash(uint32_t i, uint32_t j, uint32_t k)
{
   return ((((((OFFSET_BASIS ^ i) * FNV_PRIME) ^ j) * FNV_PRIME) ^ k) * FNV_PRIME);
}

```

Original version operating on bytes:

```
#include <cstdint>

#define OFFSET_BASIS 2166136261ul
#define FNV_PRIME 16777619ul

uint32_t hash(char* data, size_t bytes)
{
   uint32_t h = OFFSET_BASIS;

   for (size_t i = 0; i < bytes; ++i)
   {
      h = (h ^ data[i]) * FNV_PRIME;
   }

   return h;
}

```

# Answer
> 4 votes
It's not equivalent, and I suspect there will be a loss of statistical randomization/mixing.

The core step that offers mixing of the bits is multiplication by `FNV_PRIME` modulo $2^{32}$. The original version (operating on bytes) does this once for each *byte* of the input. The alternative version (operating on integers) does this once for each integer, i.e., once for each *four bytes*. Thus, the alternative version does only one-fourth as many of these mixing operations.

For these reasons, I anticipate that the alternative version will provide poorer mixing of the bits and might offer poorer statistical properties or weaker collision resistance.

For instance, here is one weakness of the alternative version that isn't present in the original version. Suppose you simultaneously flip the high bit of `i` and `j`. Then it turns out that the output (the hash value) will remain unchanged, with the alternative version. This is a weakness in a hash function. The original version doesn't have this weakness: there's no simple set of bit flips you can do to the input that will have a similar effect. This is a result of the fact that the alternative version only does the multiplication-based mixing one-fourth as much as the original version.

Now, don't take this the wrong way. This doesn't necessarily mean that the alternative version is flawed or useless. The alternative version might still be good enough for applications; that will depend on the distribution of integers that you hash and the needs of the particular application. But you can't make an equivalence argument that it's "just as good" as the original version.

---
Tags: hash, randomness, statistics, hashing, c
---


# Question
Title: Approximability of convex programming (convex optimization)
Convex optimization is defined here: https://cstheory.stackexchange.com/questions/22314/definition-of-convex-optimization-problem-by-stephen-boyd-and-lieven-vandenbergh

The problem is NP-hard: https://mathoverflow.net/questions/92939/is-that-true-all-the-convex-optimization-problems-can-be-solved-in-polynomial-ti

But is anything known about the approximation complexity of the problem? Does it have a PTAS (poly time approximation scheme)? Or is there a proof that a PTAS is impossible unless P=NP? Are there any known results on upper/lower bounds on its approximability?

Any information will be much appreciated.

# Answer
You haven't defined convex optimization in general, and indeed it is not clear how one would encode a general convex optimization problem. However, to answer your question it suffices to consider the special case of copositive programming. It is known that Independent Set can be expressed as a copositive program, and this problem is NP-hard to approximate up to a factor of $n^{1-\epsilon}$ for every $\epsilon \> 0$. In particular, there is no PTAS.
> 2 votes

---
Tags: approximation
---


title: Timely lower bounded Turing machines

text:
# Question
Title: Timely lower bounded Turing machines
Let M be a deterministic Turing machine wich has the properties:

1) $\forall x,y \in \Sigma^\* : t\_M(xy) \ge t\_M(x) + t\_M(y)$

2) $\forall a \in \Sigma: t\_M(a) \ge 1$ (Also 2) should be obvious for every DTM).

Then it follows that for all $x \in \Sigma^\* : t\_M(x) \ge |x| $. The graph $G\_M$ induced by the transition function contains a cycle: To see this choose a word $w$ whose length $|w|$ is $\> |Q|$ where $Q$ is the set of states of $M$. Then we have $t\_M(w) \ge |w| \> |Q|$. Since $M$ is at every time step on exactly one state, $M$ must visit in $t\_M(w) \> |Q|$ time steps one state at least twice, hence the graph $G\_M$ must contain a cycle.

My question is this: Can we construct to every DTM $M'$ an equivalent DTM $M$ with the properties above? In my intuition this is possible: Just construct $M$ such that it reads all the input, writes what it has read, move the pointer to the beginning of the word and then gives control to $M'$. But is it possible to give a more formal proof for this? Or is my intuition wrong?

# Answer
> 0 votes
Use the following recursive procedure to construct $M'$ from $M$:

1. Run $M'$ on all non-trivial prefixes and suffixes of the input (if any), and ignore the results.
2. Run $M$ on the entire input, and output the result.

If $M$ always terminates, so does $M'$. The first step guarantees your first condition. The second condition is virtually automatic.

---
Tags: turing-machines
---


title: Finding an optimal topological ordering

text:
# Question
Title: Finding an optimal topological ordering
I have some jobs, which calculate values. Some of these jobs require the calculated values of other jobs for their own calculation. An execution plan for these jobs can be found with a topological sort on the dependency graph.

However, these calculated values are huge and occupy a large chunk of memory. I want to find a topological order that minimizes memory usage.

To give a simple example, consider the following dependency graph:

There are three possible topological orders: $1\\, 2\\, 3\\, 4$, $1\\, 3\\, 2\\, 4$, and $3\\, 1\\, 2\\, 4$. Let's look at each of them.

In the first case, the values of $1$ and $3$ can be discarded immediately after $2$ and $4$ have finished, respectively, so each of them must be kept in memory for one additional step. The value of $2$ has to be kept for two additional steps until $4$ has finished. So in total we have to keep $4$ results in memory over the whole execution.

In the second case the values of $1$ and $3$ have to be kept for two steps and the value of $2$ for one step. This makes $5$ in total, so this ordering is worse in terms of memory usage.

In the third case the value of $3$ has to be kept for three steps and the values of $1$ and $2$ for one step each. Again we have a total of $5$, so this ordering is also worse than the first one. Thus the first ordering should be chosen.

Is there an efficient algorithm to find an optimal ordering without needing to inspect all possible orderings?

Bonus: is it also possible to give an optimal solution, if the values would need different amounts of memory per job?

# Answer
This problem is called the Minimum Linear Arrangement of a Directed Graph and it is indeed NP-hard.

See the reduction from the MLA to MLAD on page 11 of this (old) technical report: S. Even and Y. Shiloah, *NP-completeness of several arrangement problems*, Technical Report no. 43 of the Department of Computer Science, Israel Institute of Technology (Technion), 1975 (PDF).
> 6 votes

---
Tags: algorithms, graphs
---


title: Minimal hypergraph transversals

text:
# Question
Title: Minimal hypergraph transversals
the exact complexity for hypergraph transversal problem is yet unknown and is an open research problem.

However, I would need a fast way to compute, on paper, the minimal transversal of a hypergraph. A transversal intersects all hyperedges of the graph.

A transversal is minimal if it does not contain any transversal as a proper subset.

Let us look at this example, where `V = {a,b,c,d,e}`

```
Hyperedge 1: de
Hyperedge 2: abce
Hyperedge 3: bd

```

How can I compute, on paper, the minimal transversal of this hypergraph? Computing the minimal transversal with only 2 hyperedges is trivial, but in the 3 hyperedges case, the complexity increases.

Looking forward to your input.

# Answer
> 1 votes
The problem is NP-hard by a reduction from hitting set. Thus, there is no efficient or "easy" algorithm in this sense. Of course, any algorithm you might execute with pen and paper can also be realized on a computer.

With that being said, just try all possibilities by hand. As you observe, it is easy to see if the solution is of size one or two. It can get much more tedious after that, and the reason is NP-hardness.

---
Tags: graphs
---


# Question
Title: A question on the graph induced by the transition function of a deterministic Turing machine
Let $M$ be a deterministic Turing machine with totally defined transition function $\delta$ and working alphabet $\Gamma$. Let $Q$ denote the statespace of $M$'s finite control. Let $G\_M$ be the graph induced by $\delta$ which is defined as $G\_M = (V,E)$ with $V = Q$ and $(q,q') \in E$ iff there exist $a,b \in \Gamma$ and $m \in \\{\pm 1\\}$ such that $\delta(q,a) = (q',b,m)$. Are there any results which translate properties of the machine $M$ to graph theoretic properties of $G\_M$ and vice versa?

# Answer
Not likely: almost every property of a Turing Machine is undecidable, and almost every property of a graph is decidable.

If you ignore tape contents, you don't have Turing machines, you have finite automata. But graphs can't really represent tape content.

You can perform some trivial dead code analysis, but there may be unreachable states which are reachable in your graph.
> 2 votes

---
Tags: graphs, turing-machines
---


title: Find the optimal way

text:
# Question
Title: Find the optimal way
We consider the TSP in Grid-City.

The roads in Grid-City have the form of a grid, so that the intersection points can be described by an integer coordinate system.

The distance of $2$ points $C=(x,y)$ and $D=(x',y')$ is defined as $d(C,D)=|x-x'|+|y-y'|$.

An input for the TSP consists of $23$ points with the following coordinates: $$(i,0), \text{ for } i=0, 1, \dots , 10, \\ (i,2), \text{ for } i=0, 1, \dots , 10, \\ (13, 0)$$

I want to give the optimal TSP-Tour.

We have the following grid, or not?

To find the optimal TSP-Tour (without the approximation-algorithms) from which point do we start? From which point we want?

If we choose one point to start, lets consider the $S=(0,0)$.

The second point will be either $A=(0,2)$ or $B=(1,0)$, right? Since $2=d(S,A)\>d(S,B)=1$, the second point is $B=(1,0)$.

Or can we consider for the second point also the diagonal one, $(1,2)$ ?

Or is this not the correct way to find the optimal TSP-Tour?

When the roads are just the vertical and horizontal lines, we have that the distance of a point $(i,j)$ to an other is either $d\_1=1$ or $d\_2=2$, or not?

If this is true, is the optimal TSP-Tour the following? $$(0,0)\rightarrow (1,0) \rightarrow (2,0) \rightarrow \dots \rightarrow (10,0)\rightarrow (13,0)\rightarrow (10,2) \rightarrow (9,2) \rightarrow \dots \rightarrow (1,2) \rightarrow (0,2) \rightarrow (0,0)$$ But how do we get from the point $(13,0)$ to the point $(10,2)$ ?

$$$$

**EDIT:**

I have to find also the approximation for the TSP-Tour through the NEAREST-NEIGHBOR and then through the NEAREST-INSERTION with starting point $(0,0)$.

Do we get the following result through the NEAREST-NEIGHBOR? $$(0,0)\rightarrow (1,0) \rightarrow (2,0) \rightarrow \dots \rightarrow (10,0)\rightarrow (10,2) \rightarrow (9,2) \rightarrow \dots \rightarrow (1,2) \rightarrow (0,2) \rightarrow (13,0) \rightarrow (0,0)$$

So is the length of this Tour equal to $10+2+10+15+13=50$ ?

The NEAREST-INSERTION algorithm is the following:

```
T <- {1}
while |T|<n do
   j <- vertex with minimal d(T,j), j notin T
   insert j with minimal cost into T
return T

```

So, we have the following:

```
T={(0,0)}
j=(1,0)
T={(0,0), (1,0)}
....
T={(0,0), (1,0), ... , (i,0), ... , (100,0), (100,2), ... , (j,2), ... , (1,2), (0,0)}

```

or not?

So, do we get the same result with both approximations?

# Answer
Your question is not fully clear to me,

however if it boils down to, is the tour that you propose the optimal one, the answer is yes.

You can easily prove it:

Your tour has a total distance of 30. If you would consider the problem of finding the shortest tour where the only points are (0,2) and (13,0) then the answer is trivially (0,2) -\> (13,0) -\> (0,2) which also has a total distance of 30. Since the Manhattan distance respect the triangle inequality, then you know that the tour traversing 23 points including (0,2) and (13,0) has a distance greater or equal to 30. Since your tour has a distance of 30 it is optimal.
> 2 votes

# Answer
You can easily find a path that is a valid path for the problem, and an optimal path for the three locations (0, 0), (13, 0) and (2, 0) which shows immediately that it must be the optimal solution for the problem. (Move from (0, 0) to (13, 0) to (13, 2) to (0, 2) to (0, 0)).
> 1 votes

---
Tags: complexity-theory, optimization, traveling-salesman
---


# Question
Title: Is there a similar categorization to Elementary Cellular Automata?
Elementary cellular automata show different systems and fractals like rule 30, rule 90, and rule 110. I want to know if there is another classification or type which shows similar structures just like in elementary cellular automata (ECA).

For example what other systems can show structures similar to Sierpinski triangle (which is the same as rule 90 in ECA)?

Is there a method to build rule 30 or 60 using other system than ECA?

# Answer
You might take a look at Lindenmayer Systems.

From Wikipedia:

> An L-system consists of an alphabet of symbols that can be used to make strings, a collection of production rules that expand each symbol into some larger string of symbols, an initial "axiom" string from which to begin construction, and a mechanism for translating the generated strings into geometric structures.

L-systems can be used to generate a Sierpinski triangle.
> 2 votes

---
Tags: complexity-theory, computability, cellular-automata
---


# Question
Title: The meaning of "set" in NP-complete problem
Garey and Johnson describe in their book many NP-complete problems which are based on sets, for example Hitting Set, Minimum Test Set, Set Packing, Set Splitting, and many more.

The traditional mathematical definition of a set does not allow duplicates; when multiplicities count, the object is called a multiset.

Are the sets in the NP-complete problems described by Garey and Johnson allowed to contain duplicates?

# Answer
> 6 votes
It doesn't matter. If a certain problem has one version in which the encoding of sets allows for repeated elements (which are ignored semantically), and another in which repeated elements are forbidden, then there is a simple polynomial time reduction from the former to the latter showing that if the first version is NP-complete, so is the second one.

---
Tags: np-complete, sets
---


# Question
Title: Where is pivoting done in the Crout decomposition algorithm?
Consider the following code, found on wikipedia, that implements the Crout decomposition algorithm:

```
    void crout(double const **A, double **L, double **U, int n) {
    int i, j, k;
    double sum = 0;

    for (i = 0; i < n; i++) {
        U[i][i] = 1;
    }

    for (j = 0; j < n; j++) {
        for (i = j; i < n; i++) {
            sum = 0;
            for (k = 0; k < j; k++) {
                sum = sum + L[i][k] * U[k][j];
            }
            L[i][j] = A[i][j] - sum;
        }

        for (i = j; i < n; i++) {
            sum = 0;
            for(k = 0; k < j; k++) {
                sum = sum + L[j][k] * U[k][i];
            }
            if (L[j][j] == 0) {
                printf("det(L) close to 0!\n Can't divide by 0...\n");
                exit(EXIT_FAILURE);
            }
            U[j][i] = (A[j][i] - sum) / L[j][j];
        }
    }
}

```

Which part is responsible for pivoting?

The thing is, I've read that partial pivoting is still a rather non-trivial operation (on the order $O(n^2)$), but the above algorithm seems similar in terms of complexity to the "naive" LU decomposition without any pivoting.

To check, I've run the algorithm on my 28x28 test matrix

```
[ 0 0.291601633 0 -0.062262937 0 0 0 0 0 -0.22949092 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0.291601633 0 -0.062262937 0 0 0 0 0 -0.22949092 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 -0.062262937 0 0.633860174 0 -0.203470344 0 -0.185648901 0 -0.182968732 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ -0.062262937 0 0.633860174 0 -0.203470344 0 -0.185648901 0 -0.182968732 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 0 -0.203470344 0 0.386208493 0 -0.18368887 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 -0.203470344 0 0.386208493 0 -0.18368887 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 0 -0.185648901 0 -0.18368887 0 1.163032501 0 -0.044175498 0 0 0 -0.20912 0 0 0 -0.55618 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 -0.185648901 0 -0.18368887 0 1.163032501 0 -0.044175498 0 0 0 -0.20912 0 0 0 -0.55618 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 -0.22949092 0 -0.182968732 0 0 0 -0.044175498 0 0.702145321 0 -0.25202 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ -0.22949092 0 -0.182968732 0 0 0 -0.044175498 0 0.702145321 0 -0.25202 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 0 0 0 0 0 0 0 -0.25202 0 0.883882188 0 0 0 0 0 0 0 0 0 -0.220414179 0 -0.28380561 0 -0.14610303 0 0 ]
[ 0 0 0 0 0 0 0 0 -0.25202 0 0.883882188 0 0 0 0 0 0 0 0 0 -0.220414179 0 -0.28380561 0 -0.14610303 0 0 0 ]
[ 0 0 0 0 0 0 0 -0.20912 0 0 0 0 0 0.49528 0 -0.17615 0 -0.11001 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 0 0 0 0 -0.20912 0 0 0 0 0 0.49528 0 -0.17615 0 -0.11001 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.17615 0 0.17615 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 0 0 0 0 0 0 0 0 0 0 -0.17615 0 0.17615 0 0 0 0 0 0 0 0 0 0 0 0 0 ]
[ 0 0 0 0 0 0 0 -0.55618 0 0 0 0 0 -0.11001 0 0 0 1.033363204 0 -0.090289125 0 0 0 0 0 0 0 -0.298767964 ]
[ 0 0 0 0 0 0 -0.55618 0 0 0 0 0 -0.11001 0 0 0 1.033363204 0 -0.090289125 0 0 0 0 0 0 0 -0.298767964 0 ]
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.090289125 0 0.299090395 0 -0.208861407 0 0 0 0 0 0 ]
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.090289125 0 0.299090395 0 -0.208861407 0 0 0 0 0 0 0 ]
[ 0 0 0 0 0 0 0 0 0 0 0 -0.220414179 0 0 0 0 0 0 0 -0.208861407 0 0.429181968 0 0 0 0 0 0 ]
[ 0 0 0 0 0 0 0 0 0 0 -0.220414179 0 0 0 0 0 0 0 -0.208861407 0 0.429181968 0 0 0 0 0 0 0 ]
[ 0 0 0 0 0 0 0 0 0 0 0 -0.28380561 0 0 0 0 0 0 0 0 0 0 0 0.570852385 0 -0.29792224 0 0 ]
[ 0 0 0 0 0 0 0 0 0 0 -0.28380561 0 0 0 0 0 0 0 0 0 0 0 0.570852385 0 -0.29792224 0 0 0 ]
[ 0 0 0 0 0 0 0 0 0 0 0 -0.14610303 0 0 0 0 0 0 0 0 0 0 0 -0.29792224 0 0.818338896 0 -0.387730558 ]
[ 0 0 0 0 0 0 0 0 0 0 -0.14610303 0 0 0 0 0 0 0 0 0 0 0 -0.29792224 0 0.818338896 0 -0.387730558 0 ]
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.298767964 0 0 0 0 0 0 0 -0.387730558 0 0.68647389 ]
[ 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 -0.298767964 0 0 0 0 0 0 0 -0.387730558 0 0.68647389 0 ]

```

which is invertible (you can check here), when it returned a number NaNs and Infinities.

# Answer
That algorithm doesn't do any pivoting. It requires non-zero elements on the diagonal of `A` to work, otherwise you divide by zero. Note the check:

```
if (L[j][j] == 0) {
    printf("det(L) close to 0!\n Can't divide by 0...\n");
    exit(EXIT_FAILURE);
}

```
> 1 votes

---
Tags: matrices
---


# Question
Title: Why are regular expressions defined with union, concatenation and star operations?
A *regular expresssion* is defined recursively as

1. $a$ for some $a \in \Sigma$ is a regular expression,
2. $\varepsilon$ is a regular expression,
3. $\emptyset$ is a regular expression,
4. $(R\_1 \cup R\_2)$ where $R\_1$ and $R\_2$ are regular expressions is a regular expression,
5. $(R\_1 \circ R\_2)$ where $R\_1$ and $R\_2$ are regular expressions is a regular expression,
6. $(R\_1)^\*$ where $R\_1$ is a regular expression is a regular expression.

This definition is taken from page 64 of

> Sipser, Michael. Introduction to the Theory of Computation, 3rd edition. Cengage Learning, 2012.

Now, I have the following questions.

* Why do not the definition contain the `intersection`, `complement` or `reverse` operations?
* If we change the 4th item to $R\_1 \cap R\_2$, do we get an equivalent definition, i.e. for each regular language, there is a modified regular expression and vice versa?
* I know that this definition is complete and well-defined, but why is it preferred to other equivalent, well defined and complete definitions?

# Answer
1) If we also allow intersection and complement, then the resulting expressions are sometimes called *extended regular expressions*; as the regular languages are closed under boolean operations nothing is gained by them. It is just syntactic sugar. A similar conclusion holds for the reverse operation. Part of the reason why on first instance all the other operations are not mentioned is the goal of keeping the definition as simple as possible, so that (inductive) proofs do not have to take care of to many cases. Another cause might be that if we allow certain operations, but others not, in some cases very distinct (subregular) language classes result, for example if we consider extended regular expression without the star operator, then we get a proper subclass of the regular ones, the so called star-free or aperiodic languages, see wikipedia:star-free language.

2) If we keep items 1. - 6. but just alter item 4. in using intersection instead of union, we get a proper subclass of the regular languages. For example we could no longer describe the language $L = \\{a,b\\}$ as it would involve the union of $\\{a\\}$ and $\\{b\\}$ (see proof below). If we allow complementation, things change as we have union back by DeMorgan's laws.

3) This was partly answered by me in 1), but what you mean when you say that this definition is preferred? I know definitions where 2. is omitted (as we have by 6. that $L(\emptyset^{\ast}) = \\{\varepsilon\\}$), or 3. is omitted (as we have $\emptyset = L(\overline{ X^{\ast} }$)), or both are omitted; so this one is not the minimal possible definition (it gives us also some syntactic sugar as we have extra symbols to describe $\\{\varepsilon\\}$ and $\emptyset$).

*EDIT*: My first mentioned comment in 2) was wrong, languages in the inductive closure under $\circ$, $^{\ast}$ and $\cap$ do not neccessarily are subsets of $x^{\ast}$ for some $x \in X$, for example consider $L(a\circ b) = \\{ab\\}$. Nevertheless we have that $L = \\{a,b\\}$ could not be describes by such an expression. I will give a proof, namely I proof that if $L = L(R)$ for some expression with the modified 4th item, then if $X = \\{a,b\\}$ (and hence $a\ne b$) $$ \\{a,b\\} \subseteq L \Rightarrow ab \in L. $$ The proof goes by induction on the expression $R$. For the base case it holds vacuously, now suppose it holds for $L(R\_1), L(R\_2)$. If $L = L(R\_1 \cap R\_2) = L(R\_1) \cap L(R\_2)$ and $\\{a,b\\} \subseteq L$, then $\\{a,b\\} \subseteq L(R\_i), i = 1,2$ hence by induction hypothesis we have $ab \in L(R\_1) \cap L(R\_2)$. If $\\{a,b\\} \subseteq L(R\_1\circ R\_2) = L(R\_1)L(R\_2)$ then as $a = a\cdot \varepsilon = \varepsilon\cdot a$ we must have $a\in L(R\_1)$ and $\varepsilon \in L(R\_2)$ or vice versa. Suppose the first case. If $b \in L(R\_1)$, then $ab \in L(R\_1)$ by induction hypothesis, hence $ab = ab\cdot \varepsilon \in L(R\_1)L(R\_2)$. Now suppose $b \in L(R\_2)$, then we have $a\cdot b \in L(R\_2)L(R\_2)$ by definition of $L(R\_1)L(R\_2)$. Lastly if $a,b \in L(R\_1^{\ast})$, then $a \in L(R\_1)^n$ and $b \in L(R\_2)^m$ for some $n,m \> 0$. If $n = m = 1$ we find $ab \in L(R\_1)$ by induction hypothesis, so suppose $n \> 1$, but this gives $a \in L(R\_1)$, similar either $m = 1$ or $m \> 1$ gives $b \in L(R\_1)$ and the induction hypothesis gives $ab \in L(R\_1) \subseteq L(R\_1^{\ast})$. $\square$

Remark: One commonly used conclusion: If $a = uw$, then $u = a$ or $w = a$. This follows as $1 = |a| = |uw| = |u| + |w|$, hence $|u| = 0$ and $|w| = 1$ or $|u| = 1$ and $|w| = 0$. In the first case we have $u = \varepsilon$ and hence $a = w$.
> 16 votes

# Answer
The technical report that introduced regular languages, regular expressions, and finite automata asks your question on page 70:

> The question may occur to the reader, why did we select the particular three operations $E\vee F$, $EF$, and $E\*F$?

(Soon afterwards, it was noted that $E^\*$ is a more convenient operator than $E\*F$ and equivalent in power. So these days, we use $E^\*$ instead.)

The answer occupies several pages. First, it is remarked that the answer must be sought in whether the resulting languages form an interesting class and how they compare with languages described by other means. On page 72, it is remarked that negation and conjunction are redundant: they do not add any expressive power. On page 80 and further, it is proved that the regular languages are exactly the languages recognized by finite state machines.

In other words: Stefan's answer can safely be considered conclusive, as it was already given in the report that first introduced these concepts.
> 11 votes

# Answer
From this selection of operators (union, concatenation, and star) one can construct an NFA with a size linear to the size of the expression. On the other hand, if you add intersection and complementation, the size of the equivalent automaton may explode non-elementarily, which is usually not desirable.
> 4 votes

---
Tags: formal-languages, regular-languages, regular-expressions
---


# Question
Title: Approximate Nearest Neighbour Problem in Spherical Setting
There has been significant literature in solving the (Approximate) Nearest Neighbour Problem in the spherical setting in the $\mathbb{R}^n$ using Angular and Spherical LSH and other lattice sieving techniques. A proper definition of the problem is found in the image below.  (The problem definition is borrowed from Faster sieving for shortest lattice vectors using spherical locality-sensitive hashing by Laarhoven and Weger 2015. Here is the IACR page for the paper. )

(Refer to Sieving for shortest vectors in lattices using angular locality-sensitive hashing by Laarhoven 2015. The link is in the comments.)

I was curious if there is a way to have a similar spherical setting for the approximate NN problem for the finite field $\mathbb{Z}\_2^n$. Particularly, I was wondering if there was a sphere definition relevant to $\mathbb{Z}\_2^n$ that could be analogical or atleast very similar to the one in Definition 4. The one in definition 4 allows entire lattices to be embedded on the sphere i.e. $P$ is a lattice. The proposed distance measure could either be the $l\_2$ norm or the hamming distance. It does not seem that it can be simply translated into finite fields.

I apologize if this is a naive question or does not make sense because I am a first time undergraduate researcher who is not very familiar with this forum and the level of questions asked here.

# Answer
> 0 votes
There is a reasonable distance metric on $\mathbb{Z}\_2^n$ that allows one to define something that can be viewed as the analog of a sphere. In particular, use the Hamming distance. Then given any vector $c \in \mathbb{Z}\_2^n$ and any positive integer $k$, the set $\\{x \in \mathbb{Z}\_2^n : d(x,c) \le k\\}$ can be a ball centered at $c$ with radius $k$. You could even call it a Hamming ball.

You can also define a version of nearest-neighbor search, using the Hamming distance on $\mathbb{Z}\_2^n$ instead of the ordinary Euclidean distance on $\mathbb{R}^n$. Everything carries over. The algorithms/solutions may need to be different, though. For approaches to this problem, you could look at metric trees and locality sensitive hashing.

---
Tags: optimization, lattices, nearest-neighbour
---


# Question
Title: Given an amount of sets with numbers, find a set of numbers not including any of the given
Given an amount of sets with numbers (0-20 e.g) , we are asked to find the maximum set of numbers from 0-20 that doesn't include any of the given sets(it can include numbers from a set,but not the whole set) For example :Setting the max number 8 and given the sets

{1,2} {2,3} {7} {3,4} {5,6,4}, one maximum solution is the set {1, 3, 5, 6, 8}. I was thinking of representing it as a graph and then inducting it to the Max Independent Set problem, but that seems to work only if the sets were consisted only from pairs,which doesn't stand.Any idea?Thanks in advance.

# Answer
> 2 votes
> I was thinking of representing it as a graph and then inducting it to the Max Independent Set problem

I think that´s a good start. The problem you are looking for is independent set but in hypergraphs instead of regular graphs.

The opposite of the independent set problem in hypergraphs is the vertex cover problem as it is in regular graphs. Well, that problem is equal to the hitting set problem: https://en.wikipedia.org/wiki/Vertex\_cover#Vertex\_cover\_in\_hypergraphs.

Something that i will do is:

* Sepparate from the universe set all elements that doesn´t appear in a given set and insert those elements inside the solution set: In your example the number 8. So the universe will be $\\{1, 2, 3, 4, 5, 6, 7\\}$ and the solution set will be $\\{8\\}$
* Transform the hitting set instance into set cover. We will have the following subsets in your example: $\\{1\\}$ , $\\{1, 2\\}$ , $\\{2, 4\\}$, $\\{4,5\\}$, $\\{5\\}$, $\\{5\\}$, $\\{3\\}$.
* We find the minimum hitting set and we pick the complement of the minimum hitting set, we add those elements to the solution set and we are done. In your example the minimum hitting set will be: $\\{2, 4, 7\\}$. The complement will be $\\{1, 3 ,5 ,6\\}$. By adding the elements of the complement set to the solution set we have the solution to the problem.

# Answer
> 0 votes
You would get the solution by finding the union of all the sets, then picking one element of each set and removing it from the solution set. Problem is which element to pick :-( By picking the same value in several sets, you reduce the number of values that are actually removed from the superset.

If a set has no element that is a member of another set, then we pick any element, and it makes no difference. If there are elements that are members of other sets, then there is always an optimal solution where we picked an element that was a member of another set. In the example, that's enough to solve the problem: The union of the numbers is { 1, 2, 3, 4, 5, 6, 7 }. We remove the 7 since { 7 } has this element, but no other set does. From the remaining sets we have to remove according to the rules above the numbers 2, 2 or 3, 3 or 4, and 4. We remove 2 and 4 because we have to which solves the problem.

---
Tags: algorithms, sets
---


# Question
Title: Similarity between Min-Conflicts and Coordinate Descent in CSPs?
I'm currently writing a library that solves a specific type of problem that involves mainly constraint satisfaction.

I have came across the Min-Conflicts Algorithm which proved to be rather efficient in the context of the problem.

However, I have recently chanced upon the Coordinate Descent Algorithm and how strikingly it resembles the Min-Conflicts Algorithm.

Probably the only difference is that in Min-Conflicts, a random variable is selected to be modified at each step whereas Coordinate Descent cycles through the variables.

Am I right to say that apart from this difference, min-conflicts and coordinate descent are essentially equivalent? If so why are classified differently?

# Answer
> Am I right to say that apart from this difference, min-conflicts and coordinate descent are essentially equivalent?

In the same sense that A\* and BFS are essentially equivalent except for the choice of which node to visit next, yes.

> If so why are classified differently?

There are some problems for which Min-Conflicts performs asymptotically faster (in the expected-time sense) than Coordinate Descent, and vice versa. Ditto, there are some problems where one (generally) converges and the other (generally) doesn't.
> 0 votes

---
Tags: optimization, constraint-satisfaction
---


# Question
Title: Slicing clusters of non-black pixels from an image into separate images
## The backstory

I have spectrograms of certain repeating sounds. The background of the spectrograms are black and could easily be made transparent if that would help. The sounds are easily distinct from the background. As shown below, each sound is a series of connected pixels of various colors.

## What I want to do

I would like to separate each of the sounds into separate images or slices. That is, from the above example I would like to isolate the sounds into something like the following example.

If you are familiar with Unity 3D, they do something similar with their "Sprite Slicer" that creates a rectangle around objects on a transparent image.
<sub>(source: unity3d.com)</sub>

## My attempt of an algorithm

```
Select non-black pixel
For each neighboring pixel
  If pixel is black
    Try each non-visited neighboring pixel again, traveling a maximum of three pixels away ( a sort of threshold )
  If pixel is non-black
    Add to a list of significant pixels and travel to neighboring pixels
Mark selected pixels as visited and select a new non-black pixel

```

This would result in a list of lists containing pixels where each list is the extracted sound or cluster of pixels that could be compiled into images.

## My concerns

I *know* this has been done before and is called something, but for the life of me I cannot find the words to describe it (hence the poor title).

My algorithm feels non-standard and potentially slow and poorly written. It should work, but it's not *it*.

## Questions

What is this called, how can I find more about it?

How do I succeed in extracting the sub-images as shown by the example?

# Answer
> 4 votes
It seems that you're just trying to find the connected components of a graph. In this case, the vertices are the non-black pixels and there's an edge between two pixels if they're at distance at most $d$, for some appropriate choice of $d$ and some appropriate metric (Euclidean distance, Manhattan distance, whatever works best).

(Note that, in terms of implementation, you don't need to construct an explicit data structure for the graph; you can calculate whether there's an edge between any two vertices whenever you need to.)

# Answer
> 3 votes
You are probably looking for something like image segmentation.

# Answer
> 2 votes
This is otherwise known as connected component labeling.

Or rather, kind of. You can extend CC labeling into image segmentation easily enough by keeping track of the bounding rectangle of each label and then afterwards copying any correctly labeled pixel to the corresponding pixel on the rectangle.

---
Tags: algorithms, image-processing
---


# Question
Title: Can a Turing Machine (TM) decide whether the halting problem applies to all TMs?
On this site there are many variants on the question whether TMs can decide the halting problem, whether for all other TMs or certain subsets. This question is somewhat different.

It asks whether the fact the halting problem applies to all TMs can be decided by a TM. I believe the answer is no, and wish to check my reasoning.

1. Define the meta-halting language $L\_{MH}$ as the language composed of TMs that decide whether a TM halts.

$$L\_{MH} = \\{ M : \forall\_{M',w} M(M', w) \text{ accepts if $M'(w)$ halts, rejects otherwise}\\}$$

2. $L\_{MH}= \emptyset$ due to the halting problem.

Thus, the title question more precisely stated: is it decidable whether $L\_{MH} = \emptyset$?

3. Per Rice's theorem, it is undecidable whether an r.e. language is empty.
In both cases, if $L\_{MH}$ is or is not r.e., it is undecidable whether $L\_{MH} = \emptyset$.
4. Therefore, it is undecidable whether $L\_{MH} = \emptyset$.

This proves a TM cannot decide whether the halting problem applies to all TMs.

Is my understanding correct?

UPDATE: I am trying to show that a TM cannot "prove the halting problem" for some definition of "prove" that seems intuitively correct. Below is an illustration of why I think this is correct.

We can create a TM $M\_{MH}$ that generates $L\_{MH}$ in the following way. The TM takes a tuple $(M\_i,M\_j,w\_k,steps)$. It simulates $M\_i(M\_j, w\_k)$ for $steps$ iterations. If $M\_i$ accepts all $(M\_j, w\_k)$ pairs that halt, and rejects all others then $M\_{MH}$ accepts $M\_i$. Otherwise, it rejects $M\_i$ if $M\_i$ decides incorrectly or fails to halt.

$M\_{MH}$ does not halt, because it must evaluate an infinite number of pairs for each $M\_i$. Additionally, all the $M\_i$s will fail to halt. $M\_{MH}$ will be unable to accept or reject any $M\_i$ as it will not know from the simulation that all $M\_i$s will fail to halt. Thus, the language it defines is not r.e. and not decidable.

$M\_{MH}$ captures my intuition of what I think it means for a TM to prove the halting problem. Other suggestions, such as $M\_{MH}$ rejecting all $M\_i$ or outputting a known proof give $M\_{MH}$ prior knowledge that the halting problem applies to all $M\_i$. This cannot count as $M\_{MH}$ proving something since the $M\_{MH}$'s premise is the conclusion it is proving, and thus is circular.

# Answer
> 5 votes
Another viewpoint: let $\varphi$ be a formalization of the statement "$L\_{MH} = \emptyset$" in ZFC; (trivially) we have:

* the set $P = \\{ x \mid x \mbox{ is a valid proof of } \varphi \mbox{ in ZFC}\\}$ is decidable;
* you can also build a TM $M$ that enumerates the proofs in ZFC and halts if it founds a proof of $\varphi$ or a proof of $\neg \varphi$; clearly $M$ halts;
* the set $\\{ M \mid M \mbox{ decides } P \\}$ is undecidable

# Answer
> 19 votes
The language of Turing machines deciding the halting problem is decidable. A Turing machine that decides it simply always outputs NO.

In other words, $\emptyset$ is decidable.

You might be confused with the fact that the language of Turing machines whose language is empty is undecidable. That is, there is no Turing machine that, on input $T$, decides whether $L(T) = \emptyset$.

# Answer
> 2 votes
You misunderstand Rice's theorem.

Rice's theorem, in this context, says that you can't decide the problem "Does T decide the empty language?".

Your problem is not about deciding whether an arbitrary Turing machine decides the empty language. Your problem is whether or not there exists an M that decides the empty language.

And such M do exist. You can do even better than that: you can actually *construct* such an M and *provide a proof* that it decides the empty language.

The general problem not being decidable does not mean you cannot solve specific instances. In fact, by the usual device of enumerating all proofs, there exists a turing machine that:

* Accepts every turing machine for which a proof exists that it decides the empty language
* Rejects every turing machine for which a proof exists that it does not decide the empty language
* Does not halt if it cannot be proven either way.

# Answer
> 1 votes
The definition about decidability from Wikipedia:

> A recursive language is a formal language for which there exists a Turing machine that, when **presented with any finite input string**, halts and accept if the string is in the language, and halts and rejects otherwise. The Turing machine always halts: it is known as a decider and is said to decide the recursive language.

In other words, it is decidable iff there is a Turing machine that decides all input strings. It is undecidable iff for each Turing machine, it doesn't decide all input strings, which means it could decide none or some strings, but there is at least one (but practically at least infinite of them) it cannot decide.

In your case, the trivial Turing machine doesn't decide for every input $L$, whether $L = \emptyset$, but it happens to know specifically whether $L\_{MH} = \emptyset$.

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


# Question
Title: Simple elementary cellular automata with high period?
I'm looking for a simple rewrite system which displays high period.

In order to do that, I've ran a brute-force search on every elementary cellular automata, for a few fixed memory lengths `L`. The result is that, when `L=7`, there are rules with the max possible period (128). Yet, for `L=8`, no matter which rule is used, I couldn't get a period \> 180. For `L=9`, the maximum period of 133.

I've, then, tried a few variations of the core idea. For example, I tried using 3 symbols instead of just `2` and do a similar brute-force search, but the results are similar.

Thus, I ask: is there any similar system with a rewrite rule which displays high period?

# Answer
> 3 votes
Used symbols will be $0, 1$, table $T$ with $18$ elements ($L=18$), and one element for register $B$.
Initialize table with any configuration with at least one element set to $1$.

At generation step do:
`B = T[0] Xor T[7]`
`T[i] = T[i - 1]`
`T[0] = B`

The array bounds act like wall, if you read from outside you get $0$. This is simple rewrite system, with minimal number of operations without any fancy operations, only *rewrite by one* calculate *xor of two cells* (hey, Rule 90 takes three), and has period $262143$ giving all $18 bit$ numbers excluding $0$.

How to get such system? This is Linear feedback shift register which fits your description of PRNG, has the highest possible period ($2^L-1$) for given number of bits (cells?) minus 1, the best one would have $2^L$.

---
Tags: automata, cellular-automata
---


# Question
Title: How can one find an element in a Merkle tree?
How can one find an element in a Merkle tree, as effectively as possible?

Each internal node has a hash value. So I think, first, hash the value to find, and if an internal node has the same value exactly, get its leaf node. But this is correct in 2-depth, not all cases. Because each internal node has a hashed what is concatenation of their child nodes, by the avalanche effect, the concatenated hash value is unexpected.

So I cannot find the value to do hash and compare.

# Answer
Merkle trees are not designed to support efficient lookup. The best you can do is search the entire tree (all the leaves) and check each node for a match. This is $O(n)$ time.

If you want to be able to efficiently look up an item in a Merkle tree, construct a separate "index": i.e., a separate hashtable (or binary search tree) storing the mapping from hash value to position in the tree.
> 3 votes

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


# Question
Title: Should a pure function take all of the functions it calls as arguments?
After Wikipedia, if a function is pure, then:

> \[it\] always evaluates the same result value given the same argument value(s).

So: if a function, let's call it `f`, calls another function, `g`, then it's behavior clearly depends on the structure of the function `g`. Should `f` take `g` as an argument in order to be pure?

# Answer
> 2 votes
No, `f` doesn't have to take `g` as an argument. Wikipedia's definition is a bit informal. Also informally, the behavior of a pure function is also allowed to depend on the code of the program. Or, to put it another way, the code of the program is considered fixed, not something we vary, so we don't try to track dependences on it.

So, something like `f(x) = 2*g(x)` is fine: if `g` is pure, `f` will be too.

# Answer
> 1 votes
No. For an algebraic structure over a set you fix the set of function symbols and the set of variables from the start. Then you can think of functions as constants. (Technically constants are functions with zero argument but anyway.) Therefore calling (pure) functions does not disrupt the purity.

# Answer
> 1 votes
The fact that `f` calls `g` doesn't influence the purity. All that's required is that for a given input to `f`, `f` always returns the same output. That means `g` must be pure. It also means if someone changes `g` so it's impure, then `f` becomes impure, too. But at that point it's a different function.

---
Tags: functional-programming
---


# Question
Title: Given a set of numbers (negative or positive), and a maximum weight w, find a subset that is maximal whose sum is less than w
The aim of this problem is to find a subset (need not be consecutive) of a given set such that the sum is maximal and less than some given number $w$. (Note, we are trying to find a subset that is less than or equal to $w$ and not closest to $w$).

For example, given a set $\\{1, 3, 5, 9, 10\\}$ and maximum weight 17, the maximal subset is $\\{3, 5, 9\\}$ since its sum is exactly 17.

Another example: given a set $\\{1, 3, 4, 9\\}$ and maximum weight 15, the maximal subset is $\\{1, 4, 9\\}$ since its sum is 14, and there are no other subsets whose sum is 15.

Example with both positive and negative numbers: given a set $\\{-3, 2, 4\\}$ and maximum weight 3, the subset is the set itself since -3 + 2 + 4 = 3.

I know how to solve it with only positive numbers, but I am struggling to find an algorithm to solve this problem for the general case with both positive and negative numbers. Obviously, my goal is not to use the brute force approach and check every possible subset since the complexity would be $O(n2^n)$.

I stumbled upon an idea on another post that suggested adding a sufficiently large number to every elements in the set and subsequently changing the maximum weight. That is given a set $R = \\{ a\_1, a\_2, ... , a\_n \\}$, we add some number $X$ (we can pick some number greater than equal to the absolute value of the smallest negative number) to get a set that looks like $\\{ a\_1 + X, a\_2 + X, ... , a\_n + X \\}$ and change the maximum weight to $nX + w$ where $w$ was the original weight. Now, we have reduced the problem to only non-negative numbers. However, I could not see a way to actually find the subset that was closest to the original weight, but only whether any elements add up exactly the original weight (ie, there is no way to actually find the subset, but only to determine that some subset exists).

Is there any other clever trick like this one to solve the problem for both positive and negative numbers? Any help would be thoroughly appreciated.

# Answer
> 1 votes
This problem can be solved by a rather simple dynamic programming:

Given a set of numbers $\\{a\_1,\dots,a\_n\\}$, let $best(i, w)$ be the best solution using only a subset of the elements $a\_i,\dots,a\_n$ with a maximum value $w$, then $$best(i,w) = max(a\_i + best(i+1,w-a\_i), best(i+1,w))$$ With boundaries conditions $best(n + 1,w) = -\infty$ for any $w \< 0$, and $best(n + 1,w) = 0$ otherwise.

Note that this problem is NP-hard because it solves the partition problem, in particular the running complexity of the above program depends on the given numbers, and can be exponential in the size of the input in the worse case.

# Answer
> 1 votes
As Gilad pointed out the problem is NP-hard.

You can note that it is a special case of the Knapsack Problem where the value and weight of the items are equal. It might therefore be interesting for you to explore a bit the solution methods for this generalization of your problem...

---
Tags: dynamic-programming
---


# Question
Title: Does word addressable memory have more bytes than byte addressable memory?
Well, my question - if word addressable memory has more bytes than byte addressable memory - is derived from the fact that in word addressable memory each address addresses a word and in byte addressable memory each address addresses a byte. In the case of word addressable memory - If the word size is 4 bytes 32 bit architecture, for example, do i have 4\*2^32 bytes in my memory? And in the case of byte addressable memory -will i have 2^32 bytes in my memory?

How is it possible that the same ram, i.e given the ram size is 4 GB, would contain different number of bytes depending on byte/ word addressable memory?

1GB RAM has 1\*1024\*1024\*1024 bytes in it. Say our architecture is 32 bit. So in the case of byte addressable memory there will be 4\*1024\*1024\*1024 virtual addresses per program but in reality there are 1\*1024\*1024\*1024 physical addresses, each points to a byte. In the case of word addressable memory there will be 4\*1024\*1024\*1024 virtual addresses per program - each address points to a word? So in this case there will be theoretically 4\*4\*1024\*1024\*1024 bytes available for each program ? There will be 1\*1024\*1024\*1024 physical addresses, each address points to a word. So there are actually 4\*1\*1024\*1024\*1024 bytes in the memory in this case?

As you can see I am super confused.

# Answer
> 4 votes
If you had a byte addressable architecture where pointers have a fixed size, and every or almost every bit pattern is a valid pointer to a distinct byte address, and a word addressable architecture where pointers have the same fixed size, and every or almost every bit pattern is a valid pointer to a distinct word address, then the second architecture could address more memory. Which means you could buy more RAM for more money and put it into a computer and use it.

That second architecture would be in big trouble with lots of data structures that require byte pointers, like typical implementations of strings, compressed data, etc. Writing an mp3 player with word addressable memory wouldn't be my kind of fun.

In practice, even mobile phones are using 64 bit processors with pointers taking up 64 bits of memory, and the addressable amount of memory right now so much exceeds what anyone could reasonably pay, that it just doesn't matter. 4 GB of memory cost around 20 dollars, multiply by 4 billion, that's 80 billion dollars, and that's what you can address with byte addressability and 64 bit pointers.

(An analogy: You have an order form that allows you to order boxes of eggs. There are only six digits space, so you can order at most 999,999 boxes. If you order boxes of 18 eggs instead of boxes of 6 eggs, you can order three times as many eggs. You also pay three times as much money. Now you look at your form and it has space for 20 digits. That's more than the whole worlds egg production, whether you order them in boxes of 6 or 18. )

# Answer
> 3 votes
> How is it possible that tha same ram, i.e given the ram size is 4 GB, would contain different number of bytes depending on byte/ word addressable memory?

It isn't. a 4GB amount of ram would either contain $2^{31.9}$ byte-addressable memory locations, or $2^{29.9}$ 32-bit-word addressable memory locations. 4GB is 4GB, regardless of what unit you divide it into.

# Answer
> 1 votes
It really depends on how you define word adressable :

* Before the triumph of the 8bits byte, there were all sorts of architectures with different grain sizes.
* Some DSPs have no direct byte accesses (for example Analog Devices SHARC : 32 for integers, 40 for floats and 48 bits for intructions).
* Some CPUs have no byte access instructions, but still use byte addresses. For example early DEC Alphas.
* Due to EDC constraints (error detection and correction), it may be impossible to change a single byte, so write byte accesses are effectively 32, 64 or 128 bits reads, mask, insert the byte, then write back 32, 64 or 128 bits.

Just like changing sector or cluster sizes can change the theorical maximum capacity of hard disks on some OSes, addressing memory by 32bits words instead of 8bits bytes effectively allows to multiply by 4 the amount of addressable data.

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


title: Working Optimization Algorithm

text:
# Question
Title: Working Optimization Algorithm
This is my basic setup: I have five time slots (A, B, C, D, E; each day has these five time slots) over 60 days that all need to be filled with n people each (n must remain a variable). However, each person has a different availability (ex. ABDE, BCDE, AE, BCD, etc.). I want this to be distributed equally so all workers get the same number of shifts, but some workers should be able to input in a number of shifts that they want to do.

I recognize that this is a subproblem of the nurse scheduling problem, and I have spend a few hours trying to grind through some academic papers on it. However, it gets very convoluted very quickly and I get lost somewhere in the mix, as I do not have a knowledge of these kinds of algorithms. This seems to be a simpler version with fewer constraints, so I was wondering what a simple yet effective algorithm would be to solve this problem and if you could provide details on it.

I have come up with a two crude algorithm ideas, and I don't know which of these (if any at all) would be the most effective:

* First distribute work to the person with (1) the least number of shifts assigned so far and then (2) with the least number of availabilities.
* Distribute all work days to those with the least number of availabilities, but fill a person's entire schedule before progressing on to the next person. Shifts get assigned by determining which time slot (A/B/C/D/E) has the least number of people working it.

The thing that I don't like about each of these algorithms is that it seems very easy to get stuck at any given point, and from there I really wouldn't know what to do.

Thanks.

# Answer
The simplest solution (in terms of saving you the time of understanding the literature) is probably going to be to use integer linear programming (ILP / MILP). You can formulate it as an ILP instance, then apply an off-the-shelf ILP solver.

Introduce zero-or-one variables $x\_{i,j}$, with the goal that $x\_{i,j}=1$ means that the $i$th person is assigned to $j$th time slot, and $x\_{i,j}=0$ means that they're not assigned to that time slot. Now you can write down some linear inequalities/equations constraining these, e.g.,

$\sum\_{i} x\_{i,j} = n$ for each $i$ (each time slot needs to be filled with $n$ people)

$\sum\_j x\_{i,j} = c\_i$ for each $i$, where $c\_i = $ the number of shifts the $i$th worker should be assigned

Also if the $i$th worker isn't available for the $j$th slot, then add a constraint that $x\_{i,j}=0$.

Also, $0 \le x\_{i,j} \le 1$ (to force each $x\_{i,j}$ to be zero or one).

The combination of all of these constraints gives you an integer linear program. Ask the ILP solver to find a feasible solution, and boom, you're done. This might not be the most efficient possible algorithm, but it will be simple to implement and play around with, and I expect that it'll give high-quality solutions and be fast enough for the size of problem you're likely to encounter in practice.
> 4 votes

# Answer
Given my understanding of your problem, you should be able to model it as a Maximum Flow Problem for which some polynomial algorithm exists.

Each of your workers would be represented by a node and each of your (60\*5) time slot would be represented by a node. An edge of capacity 1 would exist between a worker and a time slot if that worker has the possibility of working that time slot.

You would then introduce an edge of capacity n between each of your time slot nodes and your sink node.

You would introduce edges between the source nodes and the worker nodes having a capacity of number of slots that the worker wants to work (if this is specified) otherwise it would be the ceiled value of (60\*5\*n - number of shifts that all workers specified that they wanted to work)/(number of worked having not specified a number of shifts to work).

If your total flow has a value of 60\*5\*n you have a feasible solution to your problem.
> 1 votes

---
Tags: algorithms, assignment-problem
---