# Question
Title: How are hash tables O(1) taking into account hashing speed?
Hash tables are said to be amortized $\Theta(1)$ using say simple chaining and doubling at a certain capacity.

However, this assumes the lengths of the elements are constant. Computing the hash of an element requires going through the element, taking $\Theta(l)$ time where $l$ is the length.

But to discriminate between $n$ elements, we need the elements to have length at least $\lg n$ bits; otherwise by pigeonhole principle they won't be distinct. The hash function going through $\lg n$ bits of element is going to take $\Theta(\lg n)$ time.

So can we instead say that the speed of a hash table, taking into account a reasonable hash function which uses all parts of the input, is actually $\Theta(\lg n)$? Why, then, are hash tables in practice efficient for storing variable-length elements, such as strings and large integers?

# Answer
> 4 votes
The tale that hash tables are amortized $\Theta(1)$ is a lie an oversimplification.

This is only true if:
\- The amount of data to hash per item is trivial compared to the number of **K**eys and the speed of hashing a **K**ey is fast - $k$.
\- The number of **C**ollisions is small - $c$.
\- We do **not** take into account time needed to **R**esize the hash table - $r$.

**Large strings to hash**
If the first assumption is false the running time will go up to $\Theta(k)$.
This is definitely true for large strings, but for large strings a simple comparision would also have a running time of $\Theta(k)$. So a hash is not asymptotically slower, although hashing will always be slower than a simple comparision, because comparison has a early opt out ergo $O(1)$, $\Omega(k)$ and hashing always has to hash the full string $O(k)$, $\Omega(k)$.

Note that integers grow very slowly. 8 bytes can store values up to $10^{18}$; 8 bytes is a trivial amount to hash.
If you want to store bigints then just think of them as strings.

**Slow hash algorithm**
If the amount spend hashing is non-trivial compared to the storage of the data then obviously the $\Theta(1)$ assumption becomes untenable.
Unless a cryptographic hash is used this should not be an issue.

What matters is that $n$ $\>\>$ $k$. As long as that holds $\Theta(1)$ is a fair statement.

**Many collisions**
If the hashing function is poor, or the hash table is small, or the size of the hash table is awkward collisions will be frequent and the running time will go to $O(log(n))$.
The hashing function should be chosen so that collisions are rare whilst still being as fast as possible, when in doubt opt for fewer collisions at the expense of slower hashing.
A rule of thumb is that the hashing table should always be less than 75% full.
And the size of the hashing table should not have any correlation with the hashing function.
Often the size of the hashing table is (relatively) prime.

**Resizing the hash table**
Because a nearly full hash table will give too many collisions and a big (empty) hash table is a waste of space, many implementations allow the hash table to grow (and shrink !) as needed.
The growing of a table can involve a full copy of all items (and possibly a reshuffle), because the storage needs to be continuous for performance reasons.
Only in pathological cases will the resizing of the hash table be an issue so the (costly but rare) resizes are amortized across many calls.

**Running time**
So the real running time of a hash table is $\Theta(kcr)$.
Each of $k$, $c$, $r$ on average is assumed to be a (small) constant in the amortized running time and thus we say that $\Theta(1)$ is a fair statement.

**To get back to your questions**
*Please excuse me for paraphrasing, I've tried to extract different sets of meanings, feel free to comment if I've missed some*

You seem to be concerned about the length of the **output** of the hash function. Let's call this $m$ ($n$ is generally taken to be the number of items to be hashed). $m$ will be $log(n)$ because m needs to uniquely identify an entry in the hash table.
This means that m grows very slowly. At 64 bits the number of hash table entries will take up a sizeable portion of worldwide available RAM. At 128 bits it will far exceed the available disk storage on planet earth.
Producing a 128 bit hash is not much harder than a 32 bit hash, so **no**, the time to create a hash is not $O(m)$ (or $O(log(n))$ if you will).

> The hash function going through $log(n)$ bits of element is going to take $Θ(log(n))$ time.

But the hash function does **not** go through $log(n)$ bits of elements.
Per one item (!!) it only goes though $O(k)$ data.
Also the length of the input (k) has no relation with the number of elements. This matters, because some non hashing algorithms have to examine many elements in the collection to find a (non)matching element.
The hash table only does 1 or 2 comparisons per item under consideration on average before reaching a conclusion.

> Why are hash tables efficient for storing variable-length elements?

Because irrespective of the length of the input ($k$) the length of the output ($m$) is always the same, collisions are rare and lookup time is constant.
However when the key length $k$ grows large compared the to number of items in the hash table ($n$) the story changes...

> Why are hash tables efficient for storing large strings?

Hash tables are **not** very efficient for **very** large strings.

If $not$ $n \>\> k$ (i.e. the size of the input is rather large compared to the number of items in the hash table) then we can no longer say that the hash has a constant running time, but must switch to a running time of $\Theta(k)$ especially because there is no early out. You **have** to hash the full key. If you're only storing a limited number of items then you may be much better off using a sorted storage, because when comparing $k1$ $\ne$ $k2$ you can opt out as soon as a difference is seen.

However if you know your data, you can choose not to hash the full key, but only the (known or assumed) volatile part of it, restoring the $\Theta(1)$ property whilst keeping the collisions in check.

**Hidden constants**
As everyone ought to know $\Theta(1)$ simply means that the time per element processed is a constant. This constant is quite a bit larger for hashing than for simple comparison.
For small tables a binary search will be faster than a hash lookup, because e.g. 10 binary comparisons might very well be faster than a single hash.
For small datasets alternatives to hash tables should be considered.
It's on large datasets that hash tables truly shine.

# Answer
> 3 votes
Let's start with a simpler question. Consider what is perhaps the simplest data structure in existence, an *array*. For concreteness, let us imagine an array of integers. How much time does the operation $A\[i\] = A\[j\]$ take? The answer depends on the computation model. Two models are relevant here: the RAM model (which is more common) and the bit model (which is simpler to explain).

In the **bit model**, a basic operation involving $N$ bits costs $N$. So if the integers are $w$ bits wide, the operation $A\[i\] = A\[j\]$ is going to cost about $2w$.

In the **RAM model**, the basic unit of data is not a bit but a *word* (sometimes known as a *machine word*). A word is an integer of width $\log n$, where $n$ is the size of the inputs (in bits). A basic operation involving $N$ words costs $N$. In most cases, if you have an integer array then the integers you need have width $O(\log n)$, and so the operation $A\[i\] = A\[j\]$ costs $O(1)$.

As I said above, we usually analyze algorithms using the RAM model. The only common exception is integer arithmetic, especially integer multiplication, which is often analyzed with respect to the number of bit operations.

Why do we use the RAM model? Since it has more predictive power (vis a vis reality). The assumption that the input size is at most exponential in the size of a machine word is usually justified, especially for modern 64-bit processors, and operations on machine words do take constant time in actual CPUs.

---

Hash tables are more complicated data structures, and they really involve three types: the key type, the hash type, and the value type. From the point of view of the **value type**, a hash table is just a glorified array, so let's ignore that aspect. The **hash type** can always be assumed to consist of a small number of machine words. The **key type** satisfies a special property: it is *hashable*, which means that it has a hash operation which (at minimum) is some deterministic function (a function always returning the same value).

We can now address your question: how long does it take to hash a key? The answer depends on the computation model. This times we have three common models: the two earlier ones, and the oracle model.

In the **oracle model**, we assume that the hash function is given to us by an "oracle" that can compute the hash of an arbitrary key in constant time.

In the **RAM model** and the **bit model**, the hash function is an actual function, and the time complexity of the hash table depends on the time complexity of the hash function. Hash functions used for hash table (rather than for cryptographic purposes) are usually very fast, and take linear time in the input. That means that if the key type has length $N$ bits (in the bit model) or $N$ words (in the RAM model), the hash function takes time $O(N)$. When $N$ is a constant, the hash function takes constant time.

When we analyze the running time of hash table algorithms, we usually implicitly use the oracle model. This is often expressed in a different language: we simply say that we count the number of invocations of the hash function. This makes sense, since usually applications of the hash function is the dominant term in the running time of hash table algorithms, and so to analyze the actual time complexity, all you have to do is to multiply the number of hash invocations by the running time of the hash function.

When analyzing the running time of an algorithm using a hash table as a data structure, we are often interested in the actual running time, usually in the RAM model. One option here is to do what was suggested in the preceding paragraph, namely to multiply the running time of hash table operations (given in terms of number of hash function invocations) by the running time of the hash function.

However, this is not good enough if the keys have varying lengths. For example, imagine we have keys of size $1,2,4,\ldots,2^m$, and we calculate the hash of each of them once. The actual time complexity is $O(2^m)$, but the computation above only gives $O(m2^m)$. If this is the case in some application, we can take it into account on an ad hoc basis, using a refined analysis of the complexity of the underlying hash table.

---
Tags: hash-tables, dictionaries
---


# Question
Title: Comparing asymptotic complexity of functions $\log{n}$, $(\log{n})^c$ and $\sqrt{n}$
I usually follow approach of taking logs and putting arbitrary large powers of $2$ for $n$ and reducing the given function to some constant value for large value of $n$. So in this case I did it as follows:

* $\log{n}$

Putting $n=2^{2^{2^{16}}}$ and taking $\log$

$\log{\log(2^{2^{2^{16}}})}={2^{16}}$

---
* $(\log{n})^c$

Putting $n=2^{2^{2^{16}}}$, $c=2$ and taking $\log$

$\log({(\log{2^{2^{2^{16}}}})^2})=\log({2\times(\log{2^{2^{2^{16}}}})})=\log({2\times(2^{2^{16}})})=\log{2}\times\log{2^{2^{16}}}$

$=1+2^{16}$

---
* $\sqrt{n}$

Putting $n=2^{2^{2^{16}}}$ and taking $\log$

$\log{\sqrt{2^{2^{2^{16}}}}}=\log{2^{2^{2^{{16}^{\frac{1}{2}}}}}}=\log{2^{2^{2^8}}}=2^{2^8}=2^{16}$

So it looks like:

$\log{n}=\sqrt{n}\<(\log {n})^c$

However I checked that $\log{8}\>\sqrt{8}$. But, $\log{(2^{2^{2^{16}}})}=64$, whereas $\sqrt{2^{2^{2^{16}}}}$ is much larger number making equality between the two unlikely.

1. So where I am making mistakes in above calculations?
2. How above three functions compare asymptotically?

# Answer
for any $c\>1,\epsilon\>0$, $$\lim\_{n\to\infty} \frac{(\log n)^c}{n^\epsilon} = 0$$

This means that $\log n=o( (\log n)^c)$ and $(\log n)^c = o(n^\epsilon)$. In particular, for $\epsilon =0.5$, $(\log n)^c = o(\sqrt{n})$.

See Reference answers to frequently asked questions
> 1 votes

---
Tags: asymptotics
---


# Question
Title: How does a language abstract away from underlying byte machines?
So as the title suggests,

> How does a programing language, such as Java or C, abstract itself away from underlying byte machines?

Im curious, because I know that static/dynamic typing, data abstraction and control abstraction play a role. But I don't understand it so I was wondering if anyone could shed a nice explanation on this question!

Thanks a lot in advance!

**EDIT: I currently have this as an explanation so far..**

> Programming languages tend to abstract away from the underlying byte machines to provide a high-level view for the programmer. This can be for multiple reasons ranging from making code easier to write and debug, to solving platform issues.
>
> One way languages abstract themselves away is through typing. Using java as an example, it uses predefined base types of a certain size, including but not limited to: *int*, *float* and *char*. It also uses object/structured types which have a dynamic size such as *Object* and *String*. Like some others, it provides a garbage-collection and automatic memory management utility. This makes it abstract even further away as you can worry less about allocating memory space to data types, compared to a language like C.

# Answer
I'm assuming you are really asking

> how is it possible that the same source code can be compiled to different architectures?

In order to achieve this feat different systems use different solutions.

**Interpreter**
Some languages use an interpreter. In this case there is no underlying architecture. The source code gets interpreted as written.

**Virtual machine using byte code**
Languages like C# and java compile to intermediary code (called byte code) for a virtual machine.
A runtime then executes this code somewhat like an interpreter would.
Frequently a just-in-time compiler further compiles (critical parts of) the byte-code to actual machine code.
So Java and C# do not care about the actual machine.

**Virtual machine as intermediary target**
Other compilers use the LLVM architecture. LLVM presents a virtual machine to the front end and a compiler using LLVM compiles for this virtual machine.
Specific LLVM backends tuned to a specific CPU architecture further compile this intermediary code to actual machine code.
LLVM differs from Java in that LLVM always compiles all code to machine code and it does not force any specific runtime upon the compiler.

**Direct compilation**
Traditional compilers like gcc (gnu C) compile the code to a specific architecture in a direct manner. Every architecture requires a different compiler which follows the language rules to create assembly code.
Maintaining separate compilers for different CPU architectures whilst ensuring all those abstractions work the same on all targets is accomplished through sheer hard work and coordination between compilers.

Hence the rise of intermediary virtual machines as compilation targets.

> To what extend does a compiler abstract away the underlying CPU?

This differs per language. Older languages like C tend to less abstraction.
The trend in newer languages is towards more abstraction.
Some languages offer both abstract types (always the same irrespective of architecture) as well as implementation dependent types (different for different architectures).
An example of this is a `NativeInt` type that is 32 bits on X86 and 64 bits on X64.

**CPU's do some of the abstraction**
The other element in play is that CPU's are converging towards a single 'constellation'. More and more CPU architectures are using the X64 model of 32 bit integers and 64 bit memory.
Also many CPU's are backwards compatible with their predecessors.
As long as a compiler produces code that runs on a current or previous version of a CPU that CPU will run it.
So in that case it's the CPU that abstracts away (some of) the differences.

> ... **Byte machine**

A byte machine does not exist.
There is `byte code`, which is code for the virtual machine used by e.g. Java.
and there is `machine code`, which is what a CPU consumes.

**Memory management**
You talk about memory management.
This is a subject completely different from abstraction.
Every CPU architecture handles memory in essentially the same way.
All but the most esoteric CPU's have a stack and use pointer logic to address the heap.
The fact that e.g. Java and C# use a garbage collector is not technically abstraction, but relates to resource management.
How resource management gets done depends upon the runtime library in use by that language.

**Dynamic types**
Dynamic types are invented to solve the problem of buffer overflows (arguably the number one security issue facing computing today). If the runtime library handles string and array management then the burden on the programmer decreases.

> How does a languages abstract away managed or dynamic types

By using a runtime library.
All usage of dynamic and managed types gets translated into calls to the runtime library.
E.g. when using a dynamic string, the runtime library handles the reference counting, copy-on-write and growing and shrinking the storage as needed.
None of these actions are visible in the source code.
> 4 votes

---
Tags: programming-languages, typing, research
---


# Question
Title: When would the worst case for Huffman coding occur?
I am doing a project on Huffman coding and wanted to know when it wouldn't be ideal to use or rather when would the Huffman coding produce low compression. Since it mainly revolves around the frequencies of the characters present in the input text, I believe the answer is also going to be related to that.

This is what I got from wiki.

`The worst case for Huffman coding can happen when the probability of a symbol exceeds 2^(−1) = 0.5, making the upper limit of inefficiency unbounded.`

So if a character appears more in our input text, would it ensure good or bad compression? According to wiki, if the probability of symbol exceeds 0.5 (meaning that if a character appears more in our input text), it would be produce bad compression. But from what I understand, in Huffman coding, the more a character appears, the more better it is for us to get compression right?

Well anyway I just want to know in which type of files or text data, our Huffman coding would get bad compression. Maybe I am overthinking, but a little help would be great.

Thanks.

P.S: I don't think this question is subjective, I know that there is a specific answer to it. All I want is a worst case, I don't presume it's subjective?

# Answer
According to NIST:

> The worst case for Huffman coding (or, equivalently, the longest Huffman coding for a set of characters) is when the distribution of frequencies follows the Fibonacci numbers. For this and other relations see Alex Vinokur's note on Fibonacci numbers, Lucas numbers and Huffman codes.

According to Alex Vinokur a sample Huffman encoding of a sample Fibonacci distribution was 2.3846 times longer than the original. See example 3.1.1.
As I understand it the inefficiency gets worse as the alphabet increases which is why wikipedia talks about unbounded inefficiency.

Note that is not the fact that a single character is prevalent that's the issue it is the distribution of the frequencies that's the problem.

A more useful description comes from your wikipedia quote:

> The worst case for Huffman coding can happen when the probability of a symbol exceeds $2^{-1} = 0.5$, making the upper limit of inefficiency unbounded. These situations often respond well to a form of blocking called run-length encoding;

This happens when a few letters in the alphabet are much more prevalent then others; a skewed distribution as described in the NIST quote above.
This is common in uncompressed bitmap files.

The reason for this is that:

> The Huffman algorithm considers the two least frequent elements recursively as the sibling leaves of maximum depth in code tree. The Fibonacci sequence (as frequencies list) is defined to satisfy F(n) + F(n+1) = F(n+2). As a consequence, the resulting tree will be the most unbalanced one, being a full binary tree.

This is why run length coding or other forms of compression are usually applied prior to Huffman coding.
It eliminates many of the worst case scenario's for Huffman coding.
If it turns out the run length encoding is suboptimal it can simple be skipped.

Zip's deflate algorithm uses de-duplication + run length encoding followed by huffman encoding.

**Huffman codes and binary trees**
A Huffman code is closely related to a binary tree, however unlike a binary tree a Huffman code only stores its information in the leaf nodes.
The optimal input for Huffman compression is one where the output tree is fully balanced. I.e. where all letters of the Huffman alphabet are equally likely, but where more bits are used in the encoding than needed.
E.g. a text file where 8 bits per character are used even though only 64 different letters are in use. The distribution of letters in a typical language is much flatter than a Fibonacci sequence and thus well suited to Huffman.

Note that it is not necessary the case that all input letters for Huffman should be same size, they can very well be different sizes.
Usually this is not considered in order to simplify the implementation.

**Strategies for avoid worst case behavior**
Do a frequency analysis on your input data prior to Huffman encoding.
> 4 votes

---
Tags: algorithm-analysis, data-compression, encoding-scheme, huffman-coding
---


# Question
Title: Orderability of Belief States in a POMDP?
Consider a POMDP with integer states $1,2,\ldots,N$, where $N$ is finite. We thus have a complete order over the states.

It seems reasonable to think that belief states for this POMDP may be orderable in some partial order sense.

Does this orderability translate into any structure of the optimal policy? Anyone have any relevant literature?

# Answer
Having recently worked on this topic, I can say that the answer to both of your questions is yes.

The belief states may be partially ordered for example applying the monotone likelihood ratio, or other appropriate stochastic orderings that tell when a probability mass function (pmf) $f$ -- here a belief state -- is "greater than" another pmf $g$.

Roughly speaking, if the POMDP state transition and observation models are such that the partial order is preserved on a belief update operation, structural statements about the optimal policy of the POMDP can be made. Details may be found in a recent journal paper: V. Krishnamurthy, U. Pareek, Myopic Bounds for Optimal Policies of POMDPs: An extension of Lovejoy’s Structural Results, Operations Research, 2014; available at the author's website. The article also provides a literature review on the topic where further references may be found.

Krishnamurthy and collaborators also have a paper where the MLR ordering is applied on a single line in the belief space, on which the MLR order applies to every belief state: V. Krishnamurthy, D. Djonin, Structured Threshold Policies for Dynamic Sensor Scheduling--A POMDP Approach, IEEE Trans Signal Processing, Vol.55, No.10, pp.4938--4957.
> 3 votes

---
Tags: dynamic-programming, markov-chains
---


title: Backward vs Forward Data-flow Analysis

text:
# Question
Title: Backward vs Forward Data-flow Analysis
I understand how both forward and backward data-flow analysis work but in what situations would we use them? Why do we need to be able to do it in both ways? Do compilers of certain types perform one way more efficiently than the other?

# Answer
You can do different analysis with forward and backward flow algorithms:

Forward-analysis can provide information about some code to "future" code -- along the normal path of execution. A good example is *constant propagation* where you provide the value of variables to code further down the line.

Backward-analysis can provide information about some future properties "back in time". A good example is *dead code elimination* where you can remove assignments to variables if they will never be read in the future.

Real compilers like gcc or llvm perform both kind of analysis and there are even optimizations that require both kind of analysis simultaneously:

*Partial redundancy elimination* is one of those forward- and backward-analysis requiring algorithms: It tries to move code to the latest-necesary, earliest-possible place.
> 7 votes

---
Tags: compilers, data-flow-analysis
---


# Question
Title: How to calculate Huffman code length without generating the actual huffman code?
Given a vector of elements, how can I calculate the length of the Huffman codewords without generating the Huffman code itself?

Using Matlab, I was able to compute the Huffman code and and get the length of the codewords but is it possible to get the lengths alone without computing the codewords?

# Answer
You can count the distribution of frequency of the alphabet you want to Huffman encode.
If this distribution is skewed Huffman encoding will perform poorly.
See: When would the worst case for Huffman coding occur?

If this distribution is flat Huffman encoding will perform well.
The more letters in your possible alphabet do not occur in your text the better Huffman performs.

If however you have a flat distribution and most or all of the possible encoding space in your alphabet is used, then Huffman encoding will not be able to compress it.

If you want to generate the lengths of the codes that Huffman would create without actually doing Huffman encoding you will need to create a algorithm so close to Huffman as to not make very much difference, especially not in running time.

Note that the bulk of the running time of Huffman encoding is taken up by frequency counting.
For a text of length $n$ with an alphabet of $a$ characters the running time of Huffman is $O(n+a)$ and because $a$ is almost always insignificant (as well as being a constant) in comparison to $n$. The running time is $O(n)$.

You can skip the counting step if you want by making assumptions about your input.
For instance if you know your input is English text or C-source code, than you can simply use the average frequencies for typical English texts (or C-source code) to generate your Huffman code.
If so you will already know the lengths of your codes, because you are simply loading a precomputed table of Huffman codes.

Needless to say this risks suboptimal compression.
> 1 votes

---
Tags: algorithms, image-processing, data-compression
---


title: Path finding well know problems

text:
# Question
Title: Path finding well know problems
Is there any pathfinding trivial problems like the TSP?
I know that is possible to solve TSP using A\*, Best-first and using spanning tree and other things as heuristic but, is there any problem well know by the AI community?

# Answer
> 1 votes
A different kind of pathfinding problem could be the solving of a sliding puzzle. Which can be implemented using a\*. You can pass in a board configuration like:

```
ed_o
nmac
jibf
hglk

```

and find a path to an inputted solution:

```
abcd
efgh
ijkl
mno_

```

An admissible heuristic for this could be city-block distance.

---
Tags: heuristics
---


title: How do I calculate MDS codes?

text:
# Question
Title: How do I calculate MDS codes?
We are given $n, m$ with $n - m \> 1$. Let $S$ be the set of all $n$-bit words. Form $2^{n-m}$ disjoint subsets of $S$ of size $2^m$, denote a typical one of them by $A$, and let $B = S \setminus A$. With $H(a,b)$ denoting the Hamming distance of elements $a \in A$ and $b \in B$, let $G(a) = \max\_{b \in B} H(a,b)$ and $F(A) = \min\_{a \in A} G(a)$. How could one construct the $A$s such that the $F(A)$ values are as small as possible?

# Answer
> 3 votes
It seems you are looking after (linear) MDS codes. A linear $\[n,k,d\]$-MDS code "partitions" the space into $2^k$ balls of size $2^n/2^k$ elements each, so that the minimal distance between any two codewords is at least $d=n-k+1$. This is the maximal possible distance by the singleton bound.

Now, Let $C$ be such a code, and consider its cosets, that is, given any word $w\in \\{0,1\\}^n$ look at the affine subspace $w+C = \\{ w+u \mid u\in C\\}$. It is not difficult to see that any such coset is also an MDS code (namely, it partitions the entire space into balls of the same size, with the same distance guarantees; however it are no longer a linear space, but an affine one).

To answer your question, given any $\alpha\in \\{0,1\\}^n$ and any coset $\beta = w+C$, $\alpha$ is within distance $\lceil d/2\rceil$ from one word in $w+C$ (the center of the appropriate ball where $\alpha$ lies). Due to the singleton bound, such a distance is optimal.

---
Tags: coding-theory
---


# Question
Title: How do I calculate values in K-means (clustering)?
I'm learning some Data Retrieval concepts, one of them being K-means clustering. I understand that it's meant to help understand data, but that's where I begin having issues. I'm working on this problem

and I'm not sure how to approach it. This isn't a "just give me the answer" kind of thing either, I would actually like to know what the variables represent and how I would figure out the answer(s). If someone could explain it in a simple, understandable way, that would be greatly appreciated.

# Answer
First you need to find out which points are assigned to which cluster. It looks like you understand that part. Then you take the mean for each cluster. The mean is taken component-wise. So, for these 2-dimensional vectors (x, y) you need to take the means of all the x's and then separately the means of all the y's.
> 0 votes

---
Tags: information-retrieval
---


# Question
Title: Is there an implementation of higher kinded types in typed lambda calculus?
I can see that we can do higher kinded types `( * -> *) -> *` in Scala and Haskell and other languages. I'm looking for a simpler vanilla implementation of just the basic static type checking system - perhaps in Prolog or MiniKanren.

My question is: **Is there an implementation of higher kinded types in typed lambda calculus?**

# Answer
> 3 votes
I doubt you find mainstream languages with HKTs simpler than Scala and Haskell. And even those don't implement HKTs fully. Tim Sheard's Ωmega and some interactive proof assistants have HKTs too.

Chapters 29 and 30 of Types and Programming Languages show exactly how HKTs are added to a typing-system and how to do type-checking with HKTs. Why not do it yourself, it's instructive!

---
Tags: lambda-calculus, abstract-data-types, prolog
---


# Question
Title: Whether assigning of single precision IEEE754 float to double is reversible?
Using the IEEE754 standard, let's assign single precision variable **s** to double precision variable **d** and then assign **d** to single precision variable **s'**.

Is this operation is reversible (lossless) for any value that can be represented in IEEE754, including NaN, infinity, etc.? In other words, is it guaranteed that **s** = **s'** for all possible **s**?

---

On my processor NaN is not reversible (01 00 80 7f != 01 00 c0 7f). Brute force shows that NaN is not reversible, but this might be implementation dependent, so please answer within the scope of IEEE754 standard.

# Answer
The value of a number does not change when converting a single to a double.
This includes converting single +/-inf to double +/-inf.

However the printed representation of that number may change, this is the way that number would be printed on screen or converted to a string. Let me give you an example.

```
single s;
single s1;
s = 125.32f;
println("value of s = " + s);  --> displays 125.32
double d = s;
println("value of d = " + d);  --> displays 125.31999969482422

```

Does that mean that s ≠ d?
**No:** s does equal d, and when d is assigned to s1, s and s1 will be exactly equal.
The difference in the displayed value is because more digits are needed to uniquely distinguish the argument value from adjacent values of the same type.
This is a quote from the Java docs, but of course this issue extends to all languages that use IEEE754 floats.

Full disclosure: I copied most of this answer from: https://stackoverflow.com/questions/17504833/why-converting-from-float-to-double-changes-the-value

See here if you want to hear it from Jon Skeet himself: https://stackoverflow.com/questions/17504833/why-converting-from-float-to-double-changes-the-value

**Update**
I just tested the assertion using the following code and I can indeed confirm that casting a single to a double and back again does not yield any data loss whatsoever. This was tested in Delphi, but I have no reason to suspect the results would be different in any other IEEE754 compliant environment.

```
var
  a: cardinal;
  s: single absolute a;     //a and s occupy the same memory slot.
  s2: single;
  b: cardinal absolute s2;  //b and s2 occupy the same memory slot.
  d: double;

begin
  for a:= 0 to $FFFFFFFF do begin
    if not(IsNaN(s)) then begin  //must exclude NaN to avoid exceptions.
      d:= s;
      s2:= d;
      assert(a = b);
    end;
  end;
end.

```

The test took 2 minutes of CPU time.

Just to satisfy the OP's curiosity there is no 'algorithm' happening here, the line `d:= s` is compiled as:

```
Project82.dpr.20: d:= s;
00419526 D905CC0E4200     fld dword ptr [$00420ecc]
0041952C DD1DD80E4200     fstp qword ptr [$00420ed8]

```

That means the CPU itself performs the cast. And I do believe we can trust the CPU to be IEEE754 compliant.
> 1 votes

# Answer
Maybe this will help. This is not full answer - just information to think.

> 5.3 Floating-Point Format Conversions It shall be possible to convert floating-point numbers between all supported formats. If the conversion is to a narrower precision, the result shall be rounded as specified in Section 4. Conversion to a wider precision is exact.

IEEE Std 754-1985
> 1 votes

# Answer
Quite funny, I wasn't able to find the IEEE 754 document that describes the standard. I guess that such conversions are not part of the "formal" standard, and they are left to the implementation (I may be wrong here).

Information-wise, there is no reason to lose information by the conversion 32bit-\>64bit-\>32bit. If performed correctly, the conversion should return exactly the original value.

Checking a few edge cases (using the calculators of http://babbage.cs.qc.cuny.edu/IEEE-754.old/64bit.html) show this is indeed the case. It shouldn't be too difficult to write a program that goes over all the 32bit values and verifies they convert back correctly. Ignoring the NaNs, this shouldn't even take that long.
> -1 votes

---
Tags: floating-point
---


title: How to construct a running kd-tree?

text:
# Question
Title: How to construct a running kd-tree?
I have a stream of 3-tuples of type `(x,y,t)` where `x` and `y` are in the range `0-127` and `t` is time, therefore monotonic increasing.

I want to be able to quickly search for points around a query point and think that constructing a kd-tree from the data is a good way to achieve that.

Now I can hardly construct a kd-tree by inserting each new point as, due to the monotonic increasing `t`, it will inadvertently become unbalanced.

Is there a way to create a "running" kd-tree, that is inserting elements on the one t-side, while dropping elements on the other t-side without the tree becoming unbalanced?

# Answer
How about a bitwise trie? For 3D, you would interleave the bits of your three values into a single bitstrings, which could be used as a binary key. The maximum depth is determined by the number of bits. If x, y and t each have 32 bits, the depth is limited to 3\*32=96 bits. Usually the depth is much less, because depth is solely determined by the type of data, not by the insertion order. Insertion and deletion time does also not change over time, only with the size of the tree.

The bit-interleaving imposes a z-order on the tree which helps with window queries by *roughly* translating spatial proximity into neighbourness in the tree.

A Java example, with support for kD-window queries, can be found here (my own code). THis also contains code to do the bit-interleaving, also for floating-point values.

If you do bit-interleaving, it may be worthwhile to transform the coordinates to a similar value range. For example if x and y range from 0 to 10000, then it may be useful to multiply and/or add a constant to t, such that it also ranges from 0-10000 (you can also transform x,y instead). This is not essential. You may also want to use t as the first dimension, because it sounds like you perform a lot of window queries over t to remove old values. Having t as first dimension should improve such queries.

If you are looking for something more sophisticated, especially with more dimensions or large datasets, there is the PH-Tree. It is similar to a bitwise trie, but uses larger nodes like a quadtree, so the maximum depth is more limited. The linked website also links sourcecode and a description, including a performance comparison of kDtree, bitwise tries (critbit tree) and PH-Tree.

Disclaimer: The last part is basically self-advertising, but to the best of my knowledge, the PH-tree may be the best solution in your case, at least if you have large datasets.
> 3 votes

---
Tags: data-structures, trees, linear-algebra
---


# Question
Title: Is it possible to build DFA for odd-length words with 1 in the middle?
$L := \\{w \in \\{0,1\\}^\* | $the length of $w$ is odd $ \wedge $ 1 is in the middle of $w\\}$

So the alphabet is $\\{0,1\\}^\*$. My problem is that I can't keep track of the equality of chars before and after $1$. A limited DFA for the length less than 6:

How can I expand it so that it would accept any length words? Is it possible?

I tried putting cycles in it, but as I already said, then I just cant keep track of the number of chars after $1$ to be equal to that before. In other words 1 to be always in the middle.

# Answer
No, you can not. Proof by Pumping Lemma: Assume $L$ is regular and $n$ be the pumping length consider the word $w=0^n10^n$. Thus there are $x,y,z \in \\{0,1\\}^\*$ with $|xy|\<n$ and $|y| \> 0$ such $xyz=w$. Then $\forall i\in \mathbb{N}\_0: xy^iz \in L$.

**But** due to its length constraint $x$ and $y$ consist of $0$ only and all are before the $1$. Thus $xy^2z = 0^{n+|y|}10^n \notin L$.

Thus, $L$ is not regular and can not be expressed by any DFA.
> 13 votes

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


# Question
Title: How are artificial intelligence and Natural intelligence compared?
I can remember reading that computer intelligence is heading (or maybe the most powerful ones already have) towards the Natural intelligence of a four-year-old child. But how are the two kinds of intelligence compared?

# Answer
You are probably referring to ConceptNet (created by the Massachusetts Institute of Technology under its Artificial Intelligence program).

It's a software system / semantic network containing lots of things computers should know about the world, especially when understanding text written by people.

Researchers from the University of Illinois (research team led by Stellan Ohlsson) did a study on the ConceptNet 4 version of the AI and they *discovered that its IQ level is the same as that of a 4-year-old child* (somewhat... see below).

The chosen IQ test is known as the Wechsler Preschool and Primary Scale of Intelligence (third edition, WPPSI-III). It's commonly used in schools across the United States and is designed to measure the level of intelligence in five key categories and consists of 14 subtests (picture memory, similarities, object assembly, picture naming...).

> The test questions (e.g. "Why do we shake hands?") were translated into ConceptNet 4 inputs using a combination of the simple natural language processing tools that come with ConceptNet together with short Python programs that we wrote. The question answering used a version of ConceptNet based on spectral methods.
>
> The ConceptNet system scored a WPPSI-III VIQ that is average for a four-year-old child, but below average for 5 to 7 year-olds
>
> \[CUT\]
>
> **The large variations among subtests and ordinary common sense strongly suggest that the WPPSI-III VIQ results do not show that "ConceptNet has the verbal abilities a four-year-old."**
>
> **Rather, children's IQ tests offer one objective metric for the evaluation and comparison of AI systems**

(From Measuring an Artificial Intelligence System's Performance on a Verbal IQ Te st For Young Children \- Stellan Ohlsson, Robert H. Sloan, György Turán, Aaron Urasky)
> 5 votes

---
Tags: artificial-intelligence
---


title: Computing the Maximum in an MxM Matrix

text:
# Question
Title: Computing the Maximum in an MxM Matrix
I have an MxN matrix where each element contains a positive numeric value.

I need to find those elements in the matrix that add up to the "maximum value". The caveat is that each row and column can be used *at most once* in calculating the total.

I have a brute force algorithm for doing this bit it's ugly. I was wondering if there is a well-known algorithm for accomplishing this.

# Answer
> 7 votes
Your problem is known as maximum weighted bipartite matching or the assignment problem, and has efficient algorithms such as the Hungarian algorithm.

---
Tags: algorithms
---


# Question
Title: Genetic Algorithms - Why wouldn't we use the principle of Elitism?
In Genetic Algorithms, the idea of elitism is that we keep our best solution from the generation in our population regardless of what happens throughout the iteration. However, elitism seems to be discussed as an optional thing; so what situations is using elitism actually a negative aspect of a genetic algorithm?

# Answer
It increases the convergence speed of the GA, which is a double-edged sword. You want the algorithm to find good solutions quickly, but not so quickly that is has not been able to sample sufficiently large areas of the space that it's not just doing a very local search around the initial population.

Another option that can work well is to be elitist, but try to intelligently figure out when you've converged and should introduce some diversity.
> 7 votes

---
Tags: genetic-algorithms
---


# Question
Title: Determining if my artificial neural network needs additional layers
I have implemented a neural network for load forecasting in Microsoft Excel. My structure is very simplistic and involves only 1 hidden layer and 4 neurons. (See picture)

I trained my network with a very large set of data and the predictions are as decent as could be expected. However, when I go to try and predict the "future" using recent data, the network is only in the ball-park, not very close at all. Here is a plot of the actual numbers versus the forecast ones.

From looking at this chart, can it be determined if I need another layer or more neurons??

# Answer
> 0 votes
There isn't any hard and fast rule to determine that how much hidden layers would work. In your case, extra layer won't help that much, but extra features can (I'm pretty much sure). Weather forecasting, as far as I know, isn't something which can be determined using only 4 features (considering your input neurons). You can always come up with more and more features, which effectively help in predicting the weather. So, I'd suggest to look for more features (about 10 to 15 useful features), and come up with the following configuration of the network:
1.) Input: Number of neurons in he input layer should be equal to the number of features you calculate for each data entry.
2.) Output: If you can categorize the weather in, say, 5 different categories (sunny, rainy, foggy, stormy, meteor shower), then there can be 5 output neurons.
3.) Hidden: Number of neurons in the hidden layer is normally the mean value of the number of input, and output neurons. You can also have same number of neurons in the input, and hidden layer.

---
Tags: neural-networks, neural-computing, gradient-descent
---


# Question
Title: Using a combination of spatial and non-spatial inputs for convolutional neural networks
I'm working on training a game AI using deep reinforcement learning to achieve specific examples based on pixel input and some additional state information.

Naturally, I'm using a convolutional neural network to deal with the pixel information, which has been working well so far. However, I still have additional information available, such as numeric values associated with current health and ammo.

I know it must be possible to create a network architecture to take advantage of both the spatial information provided by the screen buffer as well as non-spatial information such as the game states I mentioned earlier. Is there any way to create a neural net architecture that can handle both spatial and non-spatial state?

# Answer
> 1 votes
Yes. One way is to start with several convolutional layers, and then end with one or two fully connected layers. You can add the other features as inputs to the first of those fully connected layers. This is basically serial composition of convolutional layers then fully connected layers.

There are other options for network architectures, but that'd be a reasonable one to try first. The choice of architecture is an art and depends partly on how you think one might learn from the features, and how the value of one feature might affect the kinds of things you'd like for in other features. The architecture I suggest above would be good if we pretty much want to look for the same kinds of information about the pixel input, regardless of the value of health, ammo, etc. If you think the health, ammo, etc. would dramatically influence what kinds of information we'd want the network to extract from the pixel input, one might consider other network architectures.

---
Tags: machine-learning, neural-networks, reinforcement-learning
---


# Question
Title: Context free grammar for nested arrays separated by commas
I have to define a context free grammar for the following rules:

(i) A pair of square bracket tokens \[\] surrounding zero or more values separated by commas. (ii) A value can be another array or a number.

A number is represented by the token `NUMBER`. So for example, `[NUMBER, [NUMBER, NUMBER], NUMBER]`. is valid.

I am stuck as how to approach this.

My intuition is always to look at the question and see that `S->LSQ VALUE RSQ, VALUE->VALUE COMMA VALUE | VALUE | ARRAY | e | NUMBER, ARRAY -> LSQ NUMBER RSQ, NUMBER ->NUMBER`. But I know this slips up.

What steps can I take to ensure I am always thinking in the right way?

# Answer
your current implementation doesn't enforce the first condition "A pair of square bracket tokens \[\] surrounding zero or more values separated by commas" as an empty string or a NUMBER on its own would be accepted by the grammar.

You could use the following CFG to maintain the integrity of the constraints

array ::= \[ \] | \[ element \]

element ::= value | value , element

value ::= array | NUMBER

To derive \[NUMBER, \[NUMBER, NUMBER\], NUMBER\]

Start with array -\> \[element\]

1. \[ element \]
2. \[ value, element \]
3. \[value, array \]
4. \[value, value, element \]
5. \[value, array, value\]
6. \[value, \[element\], value\]
7. \[value, \[value, element\], value\]
8. \[value, \[value, value\], value\]
9. \[NUMBER, \[NUMBER, NUMBER\], NUMBER\]

The grammar rules provided for JSON here might also be a useful reference: http://json.org/
> 1 votes

# Answer
I believe I have a solution but @wvxvw's comment is very helpful.

```
ARRAY -> LSQ ARRAY RSQ | ARRAY COMMA  ARRAY | e | NUMBER
NUMBER -> NUMBER
LSQ -> [
RSQ-> ]
COMMA-> ,

```
> 0 votes

---
Tags: context-free, formal-grammars
---


# Question
Title: Solving $T(n)= 3T(n/4)+ n\log n$ without the master method
How can one solve $$T(n)= 3T\left(\frac{n}{4}\right) + n\cdot \log n$$ without using the master method?

I know it has a solution using the master theorem from this link.

# Answer
Hint:

The master theorem is the result of observing the tree associated to the recursive relation $T(n)$. So, one possible way can be considering draw by yourself this tree, begin with the root, in this case, $n\log n$ and descending with three nodes, each one $T(n/4)$, and so on. When you see the pattern, look at each level of the tree, then sum up all nodes, and sum all levels, the total should give you an answer.
> 3 votes

---
Tags: recurrence-relation
---


# Question
Title: What does $\cdot$ mean as a notation with complexity classes?
In the wikipedia page for Toda's Theorem, the notation $A\cdot B$ is used where $A$ and $B$ are two complexity classes, but without explanation as to its meaning.

SO given two classes $A$ and $B$ what does $\cdot$ mean in $A\cdot B$?

Using an example for the cited page, what would $BP \cdot \oplus P$ mean?

Is it correct to say $A\cdot A=A$, and when is it true that $A\cdot B=B$ or $A$?

# Answer
Reading Toda's original paper, it's not clear that a general application of $\cdot$ has meaning, however it may have been extended later.

Toda introduces three operators: $\oplus\cdot$, $\mathsf{BP}\cdot$ and $\mathsf{C}\cdot$, so the $\cdot$ is, in this context, not an independent piece of notation. Toda is extending the $\mathsf{BP}\cdot$ operator introduced by Schöning (but with uglier notation - $BP\mathscr{C}$ for the operator applied to class $\mathscr{C}$).

The three operators give (intuitively) the closures of classes under three different types of reductions. I'll reproduce the definition (and intuitive explanation) for $\mathsf{BP}\cdot$ for Toda's paper (p. 867):

> $L \in \mathsf{BP}\cdot\mathbf{K}$ if there exist a set $A \in \mathbf{K}$, a polynomial $p$, and a constant $\alpha \> 0$ such that, for all $x\in \Sigma^{\ast}$, $$ \text{Prob}(\\{w\in\\{0,1\\}^{p(|x|)}:x\\#w\in A \leftrightarrow x \in L\\}) \geqq \frac{1}{2}\alpha $$

The intuitive definition is (p. 865):

> Intuitively speaking, a set is in $\mathrm{BP}\cdot\oplus \mathbf{P}$ if and only if it is reducible to a set in $\oplus\mathbf{P}$ under a polynomial-time randomized reduction with two-sided bounded error probability.
> 3 votes

# Answer
There is no such notation. The piece of notation you are citing is $\mathsf{BP} \cdot \mathsf{X}$, which is the bounded probabilistic version of $\mathsf{X}$, that is, $\mathsf{BP}\cdot\mathsf{X}$ has the same relation to $\mathsf{X}$ as $\mathsf{BPP}$ has to $\mathsf{P}$.
> 1 votes

---
Tags: complexity-theory, complexity-classes, notation
---


title: Please check my Huffman tree

text:
# Question
Title: Please check my Huffman tree
My professor gave an example of Huffman tree.

Given inputs

```
a 80
b 10
c 20
d 50
e 100
f 35
g 60

```

… then the tree will be:

But when i tried to solve it at home, I get this answer:

Which is correct, and why?

# Answer
> 2 votes
The average codeword length of your professor's code is $2.577$.

The average codeword length of your code is $2.662$.

Huffman's algorithm produces a code minimizing the average codeword length.

You draw the conclusions.

---
Tags: algorithms, greedy-algorithms, data-compression, huffman-coding
---


# Question
Title: What is the Best and easiest way to create a Classifer for Sentiment Analysis
Sentiment analysis using Machine Learning is a hot topic. In the present situation when a person doesn't have a problem in having the training data set then which way should we create the classifier possibly the NaiveBayes classifier?

# Answer
This isn't the best way but it's simple and fast:

* preprocess the input with the Porter Stemmming algorithm (it's a process for removing the commoner morphological and inflexional endings from words in English) or similar (take a look at Snowball)
* preprocess the input flagging words before and after every negation ("never", "not", "no", "n't"):

```
the movie was not great => the movie ¬was not ¬great

```
* Use Bernoulli Naïve Bayes (duplicate words are removed from the document and given a class, positive or negative, you assume that the words are conditionally independent of each other): $$P(C\_j | D) = \frac{\prod\_i P(x\_i | C\_j) P(C\_j)}{P(D)}$$

$$P(x\_i | C\_j) = \frac{count\ of\ x\_i\ in\ documents\ of\ class\ C\_j}{total\ number\ of\ words\ in\ documents\ of\ class\ C\_j}$$ ($x\_i$ are the individual words of the document $D$)

You can also use Laplacian smoothing to avoid problems if the classifier encounters a word that hasn't been seen in the training set:

$$P(x\_i | C\_j) = \frac{1 + count\ of\ x\_i\ in\ documents\ of\ class\ C\_j}{2 (total\ number\ of\ words\ in\ documents\ of\ class\ C\_j)}$$

This works quite well.

Further steps are *feature selection* (removing redundant features, while retaining those features that have high disambiguation capabilities) and *the use of ngrams* (e.g. Fast and accurate sentiment classification using an enhanced Naive Bayes model by Vivek Narayanan, Ishan Arora, Arjun Bhatia).
> 3 votes

---
Tags: machine-learning, natural-language-processing, classification
---


# Question
Title: Let G be k-reguler bipartite graph of degree at least 2. show that K(G) not equal 1?
Let G be k-reguler bipartite graph of degree at least 2, for all v belong to V(G) prove that k(G-v) is connected?

# Answer
> 1 votes
The statement is false. Here is a counterexample. Let $E$ be the even numbers and $O$ be the odd numbers, and Let $N=\\{(n,n+1)|n\in\mathbb{N}\\}$. Then $G=(E\cup O, N)$ is a $2$-regular, bipartite graphs, every vertex of which is a cut-vertex.

I won't do your homework for you until you can show where you get stuck, but I'll give you a hint: the conjecture is true for *finite* graphs, and the proof hinges on this fact. You say, *well the resulting components have some number of vertices, and these vertices of one component are distributed between the partitions, so I can count the number of edge ends on either side of the partitions* and then you double check if it comes out to the same. It also hinges on the fact that the two partitions are equally big: for a $k$-regular graph $G=(U\cup V, E)$, $|U|=|V|$, a fact which you will have to prove first. The proof for that hinges on the fact that the graph is regular.

---
Tags: graphs
---


title: Boolean search explained

text:
# Question
Title: Boolean search explained
My mother is taking some online course in order to be a librarian of sorts, in this course they cover boolean searches, so they can search databases efficiently, however, she got a question sounding something like this:

*The search "x OR y" will result in 105 000 hits, while a search for only x will result in 80 000 hits, and a search for only y will get 35 000 hits. Why does the search "x OR y" give 105 000 hits, when the combined individual searches gives 115 000 hits?*

For me this sounded strange, so I tested this myself, using the words *bacon* and *sandwich*.

* Only *bacon* yielded *179 000 000* results
* Only *sandwich* yielded *312 000 000* results
* *bacon **OR** sandwich* gave *491 000 000* results

But for me it adds up: 179 000 000 (bacon) + 312 000 000 (sandwich) = 491 000 000 (bacon OR sandwich)

Why could an OR query result in fewer hits than both individual queries combined?

# Answer
Hint: The search x AND y will result in 10 000 hits.
> 63 votes

# Answer
The counting principle that applies here is inclusion-exclusion.

$$ \left|X \cup Y\right| = \left|X\right| + \left|Y\right| - \left|X \cap Y \right|$$

To make the numbers work out, $\left|X \cap Y \right|$ must be 10000.

A Venn diagram may be more convincing to someone who may be intimidated by the notation.
> 95 votes

# Answer
Document 1: The cat is on the table
Document 2: My cat is black
Document 3: The dog is under the table
Document 4: What's the name of your cat?
Document 5: This is a black and white photo

Search for **cat**: returned documents are 1,2,4 (3 documents returned)
Search for **black**: returned documents are ...
Search for **cat OR black**: returned documents are ...

:-D :-D
> 13 votes

# Answer
In simple words:

Search for X gives you n answers.
Search for Y gives you m answers.
Search for X AND Y gives you p answers.
In searching for X OR Y, the search breaks off as soon as it finds either X or Y. So if there's an X before a Y, that Y will not be counted in searching for X OR Y. Therefore your search for X OR Y will give you n + m - p answers.
It's important to note that the results will be the same, whether you do 2 searches, or just one. It's just that in summing the two searches, some documents are counted twice.
> 3 votes

# Answer
Imagine you have only one document. This is Document#1 with this:

```
X Y

```

Now imagine you have a search function that can give you all the documents based on one keyword:

```
search("X") => 1
search("Y") => 1

```

Notice that the number of documents in both cases is 1. Now if you have a search function that gives you the number of documents that matched one or more of the keywords supplied:

```
search("X", "Y") => 1

```

When you add the number of documents containing `X` to the number of documents containing `Y`, this causes you to count the same document twice. In your case, this happened `10000` times as pointed out above :)
> 3 votes

---
Tags: sets, counting
---


# Question
Title: Is running AES NI in parallel possible (one encryption per core/thread)?
AES NI seems to perform AES operations much faster than doing in software. However, if I have a machine with a large number of cores (say 32 cores), can I perform 32 AES encryptions using AES NI instruction i.e. one per core? Or can I just run one AES instruction?

# Answer
> 4 votes
It depends mostly on the memory bandwidth. Each core contains the dedicated AES hardware, but the CPUs need to obtain the data to encrypt or decrypt somehow. Even with a single core you have to be careful about how you dispatch instructions to get maximal performance, see Intel's white paper, page 48 bottom.

If you already have the machine, you can always try it out and let us know how it went.

# Answer
> 0 votes
Often the AES algorithm cannot be parallelised, because it is inherently serial.
Every round uses the result of the previous round as input.
Furthermore AES is usually run in CBC mode where again the previously encrypted block is used as input for the next block.
EBC mode is inherently insecure and should never be used.

Some modes of AES can be run in parallel, the Intel docs state:

> The AES instructions provide a substantial performance speedup to bulk data encryption and decryption. When using parallelizable modes of operation, such as CBC decryption, CTR, and CTR-derived modes (GCM), XTS. The per formance speedup could exceed an order of magnitude over software-only, lookup tables based AES implementations. In scenarios where pipelined operation is impossible, for example in CBC encryption, the performance speedup would still be significant, around 2 to 3 times over (unprotected) software implementation.

You can however use those 32 cores to encrypt 32 different files at the same time...
Just don't try and speed up encryption by encrypting small snippets, because then you're recreating ECB mode with all its associated disadvantages.

The AES NI hardware relies heavily on lookup tables hardcoded in the chip.
(That's why it's so fast, it replaces lookup in memory with lookup on chip and it replaces bit manipulations in code with bit manipulations in silicon).
None of these operations require global state or set a global mode inside the chip, so you can run AES instructions on each of your cores at the same time.

Because single threaded hardware AES is so blazingly fast you will however run into bandwidth problems getting your data in and out of those 32 cores.
You'll quickly overload the memory bus.

From page 48 onwards the Intel documents explain how to optimize parallel operations with AES-NI.
https://software.intel.com/sites/default/files/article/165683/aes-wp-2012-09-22-v01.pdf

---
Tags: computer-architecture, parallel-computing, encryption
---


title: Jobs in algorithm design

text:
# Question
Title: Jobs in algorithm design
I just wanted to know if there are actually jobs only devoted to creating and optimising algorithms after finishing a Bachelors degree. Or is it only restricted to PhD's?

I solve problems on SPOJ and CodeForces, but I'm not sure if I'd get a job doing something like that.

# Answer
> 2 votes
I think it would be unusual to find an organisation advertising specifically for someone to design algorithms. Generally speaking a company will have a product or a number of products which go through an improvement and release cycle. Part of this will involve optimising algorithms/code. However to specialise so greatly I would have thought would mean such an employee would spend much of their time twiddling their thumbs! Any organisation nowadays generally wants someone to be multi-skilled (eg able to code as well)

Having said that, large organisations which engage in a lot of research (the likes of NASA, Google, Facebook, Bell Labs, Xerox of old) may have posts such as that. Bear in mind that those guys will be looking for real genius-level staff as well. (You may well be a genius.. :) )

I would try to broaden my horizons a little beyond just algos though, as after all, an algorithm is no good unless it can be implemented! And that will always bring its own set of challenges given available resources and the specific nature of the problem domain.

I know this isn't an "answer" just my thoughts. As a first port of call try typing "algorithm designer" into monster.com or similar job site! Good luck!

---
Tags: algorithms
---


# Question
Title: Is there any count-preserving cellular automata which tends do "10101010..."?
Suppose that I have a bit string of finite length. Is there any bit rewriting rule `rewrire :: (Bit,Bit,Bit) -> (Bit,Bit,Bit)`, that doesn't change the total count of `1`s on the bit string, and that when applied to arbitrary triplets in any order will converge to a bit string that will begin with an arbitrarily long sequence of `10`, followed by either all `0`s or all `1`s.

# Answer
Seems like the rule:

```
000 => 000
001 => 100
010 => 010
100 => 100
011 => 011
101 => 101
110 => 101
111 => 111

```

Does what I want. Testing this rule by applying it to an arbitrary bit string, this is how it evolves:

```
0   11110110010010000010100000000001000
1   11110111001000001000100000000001000
2   11101111100000100000100000000100000
3   11101111100010000010000000010000000
4   11011111011000001000000001000000000
5   11011111011000100000000100000000000
6   10111110110110000000010000000000000
7   10111110110110000001000000000000000
8   10111101101101000100000000000000000
9   10111101101101010000000000000000000
10  10111011011011010000000000000000000
11  10111011011011010000000000000000000
12  10110110110110110000000000000000000
13  10110110110110110000000000000000000
14  10101101101101101000000000000000000
15  10101101101101101000000000000000000
16  10101011011011011000000000000000000
17  10101011011011011000000000000000000
18  10101010110110110100000000000000000
19  10101010110110110100000000000000000
20  10101010101101101100000000000000000
21  10101010101101101100000000000000000
22  10101010101011011010000000000000000
23  10101010101011011010000000000000000
24  10101010101010110110000000000000000
25  10101010101010110110000000000000000
26  10101010101010101101000000000000000
27  10101010101010101101000000000000000
28  10101010101010101011000000000000000
29  10101010101010101011000000000000000
30  10101010101010101010100000000000000
31  10101010101010101010100000000000000
32  10101010101010101010100000000000000
33  10101010101010101010100000000000000
34  10101010101010101010100000000000000
35  10101010101010101010100000000000000
36  10101010101010101010100000000000000
37  10101010101010101010100000000000000
38  10101010101010101010100000000000000
39  10101010101010101010100000000000000
40  10101010101010101010100000000000000
41  10101010101010101010100000000000000
42  10101010101010101010100000000000000
43  10101010101010101010100000000000000
44  10101010101010101010100000000000000
45  10101010101010101010100000000000000
46  10101010101010101010100000000000000
47  10101010101010101010100000000000000
48  10101010101010101010100000000000000
49  10101010101010101010100000000000000
50  10101010101010101010100000000000000
51  10101010101010101010100000000000000
52  10101010101010101010100000000000000
53  10101010101010101010100000000000000
54  10101010101010101010100000000000000
55  10101010101010101010100000000000000
56  10101010101010101010100000000000000
57  10101010101010101010100000000000000
58  10101010101010101010100000000000000
59  10101010101010101010100000000000000
60  10101010101010101010100000000000000
61  10101010101010101010100000000000000
62  10101010101010101010100000000000000
63  10101010101010101010100000000000000
64  10101010101010101010100000000000000
65  10101010101010101010100000000000000
66  10101010101010101010100000000000000
67  10101010101010101010100000000000000
68  10101010101010101010100000000000000
69  10101010101010101010100000000000000
70  10101010101010101010100000000000000
71  10101010101010101010100000000000000
72  10101010101010101010100000000000000
73  10101010101010101010100000000000000
74  10101010101010101010100000000000000
75  10101010101010101010100000000000000
76  10101010101010101010100000000000000
77  10101010101010101010100000000000000
78  10101010101010101010100000000000000
79  10101010101010101010100000000000000
80  10101010101010101010100000000000000
81  10101010101010101010100000000000000
82  10101010101010101010100000000000000
83  10101010101010101010100000000000000
84  10101010101010101010100000000000000
85  10101010101010101010100000000000000
86  10101010101010101010100000000000000
87  10101010101010101010100000000000000
88  10101010101010101010100000000000000
89  10101010101010101010100000000000000
90  10101010101010101010100000000000000
91  10101010101010101010100000000000000
92  10101010101010101010100000000000000
93  10101010101010101010100000000000000
94  10101010101010101010100000000000000
95  10101010101010101010100000000000000
96  10101010101010101010100000000000000
97  10101010101010101010100000000000000
98  10101010101010101010100000000000000
99  10101010101010101010100000000000000
100 10101010101010101010100000000000000
101 10101010101010101010100000000000000
102 10101010101010101010100000000000000
103 10101010101010101010100000000000000
104 10101010101010101010100000000000000
105 10101010101010101010100000000000000
106 10101010101010101010100000000000000
107 10101010101010101010100000000000000
108 10101010101010101010100000000000000
109 10101010101010101010100000000000000
110 10101010101010101010100000000000000
111 10101010101010101010100000000000000
112 10101010101010101010100000000000000
113 10101010101010101010100000000000000
114 10101010101010101010100000000000000
115 10101010101010101010100000000000000
116 10101010101010101010100000000000000
117 10101010101010101010100000000000000
118 10101010101010101010100000000000000
119 10101010101010101010100000000000000
120 10101010101010101010100000000000000
121 10101010101010101010100000000000000
122 10101010101010101010100000000000000
123 10101010101010101010100000000000000
124 10101010101010101010100000000000000
125 10101010101010101010100000000000000
126 10101010101010101010100000000000000
127 10101010101010101010100000000000000

```

This was found by testing every possible automata, writing the results to a file and then manually inspecting to look for the desired outcome. This is the resulting file and this is the script I used to generate it:

```
// count-preserving rules
var C0 = [[0,0,0]];
var C1 = [[0,0,1], [0,1,0], [1,0,0]];
var C2 = [[0,1,1], [1,0,1], [1,1,0]];
var C3 = [[1,1,1]];

function rewrite(bits, i, rules){
    var A = rules[0], B = rules[1], C = rules[2], D = rules[3], E = rules[4], F = rules[5];
    switch ((bits[i]<<2) + (bits[i+1]<<1) + bits[i+2]) {
        case 0b000: bits[i] = 0; bits[i+1] = 0; bits[i+2] = 0; break; // 000
        case 0b001: bits[i] = C1[A][0]; bits[i+1] = C1[A][1]; bits[i+2] = C1[A][2]; break;
        case 0b010: bits[i] = C1[B][0]; bits[i+1] = C1[B][1]; bits[i+2] = C1[B][2]; break;
        case 0b100: bits[i] = C1[C][0]; bits[i+1] = C1[C][1]; bits[i+2] = C1[C][2]; break;
        case 0b011: bits[i] = C2[D][0]; bits[i+1] = C2[D][1]; bits[i+2] = C2[D][2]; break;
        case 0b101: bits[i] = C2[E][0]; bits[i+1] = C2[E][1]; bits[i+2] = C2[E][2]; break;
        case 0b110: bits[i] = C2[F][0]; bits[i+1] = C2[F][1]; bits[i+2] = C2[F][2]; break;
        case 0b111: bits[i] = 1; bits[i+1] = 1; bits[i+2] = 1; break; // 111
    };
};

function show(bits){
    return bits.map((n)=>n?"1":"0").join("");
};

function test(times, rules, bits){
    show_rule = (r) => ""+r[0]+""+r[1]+""+r[2];
    var str
        = JSON.stringify(rules)+"!\n"
        + "001=>"+show_rule(C1[rules[0]])+", "
        + "010=>"+show_rule(C1[rules[1]])+", "
        + "100=>"+show_rule(C1[rules[2]])+", "
        + "011=>"+show_rule(C2[rules[3]])+", "
        + "101=>"+show_rule(C2[rules[4]])+", "
        + "110=>"+show_rule(C2[rules[5]])+"\n";
    for (var t=0; t<times; ++t){
        for (var i=0; i<bits.length-(t%3); i+=3)
            rewrite(bits, i+(t%3), rules);
            //rewrite(bits, ~~(Math.random()*(bits.length-2)), rules);
        str += t + "\t" + show(bits) + "\n";
    };
    return str;
};

var str = "";
for(var A=0;A<3;++A)for(var B=0;B<3;++B)for(var C=0;C<3;++C)for(var D=0;D<3;++D)for(var E=0;E<3;++E)for(var F=0;F<3;++F){
    var block = test(128, [A,B,C,D,E,F], [1,1,1,1,1,0,0,0,1,0,0,1,1,0,0,0,0,0,1,1,0,0,0,0,0,0,0,0,0,0,0,1,0,0,0]);
    str += block + "\n";
};
require("fs").writeFileSync("count_preserving_binary_cellular_automatas.txt", str);
//document.getElementById("automata_result").value = str;

```
> 3 votes

---
Tags: computation-models, cellular-automata, term-rewriting
---


# Question
Title: How to identify strongly confluent cellular automatas?
Lets represent a class of cellular automata as a finite, unidimensional bit array `state : [Bit]`, plus a rewrite rule `rule : (Bit,Bit,Bit) -> (Bit,Bit,Bit)`. Given any state of the system, a posterior state can be computed by taking any consecutive triple of bits `(a,b,c)` and replacing it by the result of `rule(a,b,c)`.

Since `rule` is a map from 3 bits to 3 bits, there are `(2^3) ^ (2^3) == 16777216` possible rules. Is it possible to identify if a specific rule is confluent?

# Answer
> 1 votes
Suppose we fix $n$ and want to ask about confluence of the system on $n$-bit states. Then one approach you could try would be to use BDDs.

Build a BDD for the transition relation $\to$, where for two $n$-bit states $s,t$ we say $s \to t$ if you can get from $s$ to $t$ in a single step. Now, build a BDD for the reflexive, transitive closure $\to^\*$. (This can be built in a fixpoint computation, by looking for the least fixpoint of the equation $\to^\* = \to^\* \circ \to \lor \\; \text{id}$; i.e., set $R$ to be the identity relation, and then iteratively replace $R$ with $R \circ \to \lor \\; \text{id}$, where the latter relation $R'$ is defined such that $sR'u$ holds iff $s=u$ or there exists $t$ such that $sRt$ and $t\to u$. Iterate until convergence.) If you're lucky, the BDD for $\to^\*$ won't be too large.

Now, once you have a BDD for $\to^\*$, you can use standard BDD operations to check directly whether the convergence criteria applies. In other words, you check the validity of the formula

$$\forall a,b,c . (a\to^\* b \land a\to^\* c \implies \exists d . (b \to^\* d \land c \to^\* d)).$$

This only gives you the answer for fixed $n$. If you want to know if it is confluent for all $n$, I don't know how to check that. Also, this procedure might take exponential time in the worst case. So, you might be able to systematically check small values of $n$, and then heuristically guess that if there is a counterexample to confluence, then hopefully it'll show up for some small $n$... but this isn't guaranteed to be sound in general.

---
Tags: computability, turing-machines, cellular-automata, term-rewriting
---


# Question
Title: How to find a minimum set of axioms within a set of propositions?
I have a set of propositions, for example $\\{a\_1,a\_2,\dots,a\_n\\}$. Some propositions depend on others (for example, $a\_1,a\_2\Rightarrow a\_3$, means if $a\_1,a\_2$ are true, then $a\_3$ is true). I want to find a subset of the propositions to be defined as axioms, in the sense that, these propositions being true imply that all the others are true. The number of axioms should be as small as possible. I want to know whether there are some methods?

# Answer
> 5 votes
Determining whether a proposition follows from a set of axioms is an **NP**-Complete problem. Finding a minimal set of axioms from a set of propositions naturally invokes this problem many times *as a subroutine*.

For example, consider the following set of propositions:

$$P = \\{v\_1, v\_3 \vee v\_2, v\_1 \wedge v\_3\\} $$

A minimum set of axioms from this set is $\\{v\_1 \wedge v\_3\\}$. But to find it, you have to prove $v\_1$ and $v\_3\vee v\_2$, and those proofs are in general hard to find. The problem *is there a set of axioms $A$ for a set of propositions $P$ with at most $k$ axioms?* is in $\Sigma\_{3}^{p}$, which means it's in the third level of the polynomial hierarchy, which means that it's two levels higher than **NP** in the way that **NP** is one level higher than **P**, to give you an idea of its complexity. I do not know if it is also in a lower level. Browsing through this survey (link) \[1\] of problems that are complete for various levels of the polynomial hierarchy, I do not see this problem among them, so it's possible that it's not $\Sigma\_{3}^{p}$-Complete, but it wouldn't surprise me.

Before you go out to look for a set of axioms, you may want to know whether the set of propositions is sound and any subset is complete (untrue propositions cannot be proved, all true propositions can be proved). These problems have similar **NP**-scary complexity. First, *Is this set of propositions complete?* is a problem in $\Pi\_{2}^{p}$ of the polynomial hierarchy, because it asks, for all $p\in P$, can $p$ be proved from propositions $P\setminus \\{p\\}$? Completeness of your system is in **co-NP** as it asks, *Forall all $p\in P$, can $p$ not be proved from $P \setminus \\{p\\}$?* So it seems that checking for soundness and completeness is easier than finding a minimal axiom set, but not by much. (I'm less sure about this paragraph. Is it true that a logical system of propositions $P$ is sound iff for all $p\in P\colon \neg p$ cannot be proved from $P\setminus \\{p\\}$?)

The comments to your question pertain to the context of database entries, but they are purely syntactic and only establish redundancy in the database, whereas if your question is about propositions, as I understand it, then the contents of the database must be inspected semantically, and this leads you to this complexity nightmare.

\[1\] M. Schaefer, C. Umans, *Completenss in the Polynomial Hierarchy, A Compendium*, 2008.

---
Tags: algorithms, sets, propositional-logic
---


title: Minimizing the overall cost over groups

text:
# Question
Title: Minimizing the overall cost over groups
I am trying to solve the problem of minimizing the overall cost over several groups. The schema of the data goes something like this:

```
User (U) | Group (G) | Price (P)
================================
U1       | G1        | P11
U2       | G1        | P12
--------------------------------
U1       | G2        | P21
U2       | G2        | P22
--------------------------------
U3       | G3        | P33
U4       | G3        | P34
--------------------------------
U5       | G4        | P45

```

A user (U) can apply to be an admin of more than one Groups (G). There is a salary (P) that must be given to U if U is selected as the admin of G (U can demand any arbitrary number as salary for a group G).

The goal is to satisfy these conditions

* Every group should have exactly 1 admin.
* A User should not be the admin of more than 1 group.
* Find admins for as many groups as possible.
* The sum of salaries should be minimum.

Examples/Notes

* If there are only two applications and are by the same user U (say for groups G1 and G2, expected salaries P1 and P2), only either of G1 and G2 will get an admin. If P1 \> P2, U should be adjudged the admin of G1 (and not G2).

I'm not very sure which category of Assignment problem does this fall into. My approach was greedy and doesn't look optimal.

* Group-wise sort (ascending) the expected salary.
* Arbitrarily allocate a user to a group where there is only 1 admin-ship request. Remove this user from other group-admin requests.
* Among the first request across groups, find the maximum and allocate the user to the group. Remove this user from other group admin-ship requests.
* Repeat

**Question**: What is an optimal solution to this problem?

# Answer
> 3 votes
You are probably looking for a solution to the following optimization problem.

**Weighted maximum biparite matching**. Given a weighted bipartite graph $G=(U\cup V, E)$ with weights $w\colon U\times V \rightarrow \mathbb{N}$, find a set of edges $A\subseteq U\times V$ such that all edges in $A$ are disjoint (that is, no two edges are adjacent, that is, no group has two admins and no admin has two groups) and the sum $\sum\_{a\in A}w(a)$ is minimized, and it is not possible to add another pair $(u,v)\in U\times V$ to $A$ without violating the non-adjacency constraint.

The sets $U$ and $V$ are the users and the groups, respectively. The set of edges $E$ is the set of applications (user-group pairs) and the set of weights is the salary of a given assignment. The Blossom algorithm (link) is a optimization algorithm that finds a maximum matching, and it can be adapted to solve the weighted case.

A final note: you seem to be optimizing two objectives at once: both the minimum salary, and the maximum number of covered groups. Obviously these objectives conflict: covering less groups gives a lower salary. Fortunately, the Bloom algorithm will find a *maximum* matching, so it will cover as many groups as is possible, and within the set of matchings that cover the maximum number of groups, it finds the one with the lowest sum salary.

# Answer
> 1 votes
## Checking whether there's a valid assignment

You can check in polynomial time whether or not there exists any assignment such that every admin is assigned to only one group, and every group has exactly one admin. Simply using maximum matching algorithms.

## Finding the assignment of least cost, if one exists

If the answer to the above query was "yes, at least one such assignment exists", you can find the assignment of lowest cost using weighted maximum matching: you assign a weight to each edge that is equal to the negative of the salary, and then look for a maximum-weight matching algorithm.

In other words, this is exactly an instance of the assignment problem. There are standard polynomial-time algorithms for the assignment problem, so this problem can be solved, too.

## Handling the case where no such assignment exists

What if there doesn't exist any assignment where every admin is assigned to exactly one group and every group has exactly one admin? Well, it's not clear from the question what you want to happen in this case, so it's hard to suggest a specific algorithm. Your first step is to identify (1) a set of hard requirements that absolutely must be met in this situation, no matter what, and (2) an objective function that you want to maximize. Once you've identified those, then one can look for an algorithm that solves the associated optimization problem. But until you can articulate that, the problem is not well-defined. The core problem is that you can't simultaneously optimize for two quantities at once (maximize number of groups covered, minimize total salary), because in general there will be a tradeoff between the two, and you need how you want to trade off between them before you can ask for an algorithm to find the optimal tradeoff.

In this case there is a technique you can use to enumerate all Pareto-optimal tradeoff points:

1. First, check for the optimal assignment that covers all groups (if one exists), using the techniques above.
2. Next, check for the lowest-cost assignment that covers $n-1$ of the $n$ groups (i.e., where all but one of the groups has an admin). You can do this by adding a fake admin whose salary is \\$0 and who can administer any group, then solving the assignment problem. Any solution to this modified problem that covers all $n$ groups will correspond to a solution to the original problem that covers $n-1$ groups, at the lowest possible cost.
3. Next, check for the lowest-cost assignment that covers $n-2$ of the $n$ groups, by adding two fake admins. Repeat: for each $k$, find the lowest-cost assignment that covers $k$ of the groups.

This gives you $n$ candidate solutions with different tradeoffs between "number of groups covered" and "lowest total salary". You can then decide which of those you want as your final solution, depending on how you want to trade off those two quantities.

## Greedy algorithm

No, the greedy algorithm does not provide an optimal solution, in general. It's not hard to construct counterexamples.

---
Tags: algorithms, optimization, greedy-algorithms, bipartite-matching, assignment-problem
---


title: Find Correlations in Vectors of symbols

text:
# Question
Title: Find Correlations in Vectors of symbols
Given a set of vectors, lets say that each coordinate is populated from an alphabet (meaning set of symbols, numbers, etc) (particular or shared alphabets are indistinct).

Is there any standard procedure for performing the following task ?

Look for sets of positions that "make the same choice" in several vectors.

That means: a subset of indices where, when we project to just those indices, there's some value that's taken on by many of the vectors.

An example:

```
Input
[0,-,0]
[0,+,+]
[+,+,+]
[0,0,0]
[-,+,+]

Output

2 coordinates involved ( 2 and 3), appearing in 3 vectors: x2=+ and x3=+
1 coordinate involved (1), appearing in 2 vectors:  x1=0

```

# Answer
> 1 votes
A possible solution would be generating (in Apriori terms) a "transaction" that contains indexed symbols and mine that for frequent itemsets.

---
Tags: algorithms, reference-request, machine-learning
---


title: Letter Combinations of a Phone Number

text:
# Question
Title: Letter Combinations of a Phone Number
I came across this problem in the “Elements of Programming Interviews” interview preparation book, and also on the site, leetcode.com (link to problem).

Problem statement – Letter Combinations of a Phone Number

"Given a digit string, e.g., “23”, return all possible letter combinations that the number could represent. The mapping of digits to numbers is the same as on a telephone number pad. So for “23”, the combinations are, \["ad", "ae", "af", "bd", "be", "bf", "cd", "ce", "cf"\]."

There are plenty of solutions online and in books. However, I’m curious to know about the fundamentals of this problem.

Is this problem essential asking for the Cartesian product of multiple sets? If so, what are some efficient algorithms to compute this? Some solutions reference DFS and BFS. How are DFS and BFS related to this problem (are they possibly referring to the type of recursion being used to solve the problem) ?

Thanks

# Answer
> 1 votes
> There are plenty of solutions online and in books. However, I’m curious to know about the fundamentals of this problem.

Basically, this problem is trying to reveal your ability to solve problems using recursive algorithms/divide&conquer for generating all possible permutations (brute-force). There are some filtering techniques that can be used in practice, but the worst-case running time is exponential.

> Is this problem essential asking for the Cartesian product of multiple sets? If so, what are some efficient algorithms to compute this?

Yes, one way to look at the problem is 'Cartesian product of multiple sets'. Given a string `S`, you can consider two sets `a[i]` and `b[i]`, where `a[i]` is the set of character strings that can be made by substring `S[1:i]`, and `b[i]` is the set of character strings that can be made by substring `S[i+1,end]`; then output the Cartesian product of `a[i]` and `b[i]` for every possible `i`. However, this algorithm is not the best one.

> Some solutions reference DFS and BFS. How are DFS and BFS related to this problem (are they possibly referring to the type of recursion being used to solve the problem) ?

These algorithms use `DFS` for its recursive nature. Probably, it uses `BFS` to avoid stackoverflow.

---
Tags: algorithms, combinatorics, sets
---


title: Is NEXP = co-NEXP?

text:
# Question
Title: Is NEXP = co-NEXP?
It is known that $\mathsf{NL}=\mathsf{Co{-}NL}$ and unknown if $\mathsf{NP}=\mathsf{Co{-}NP}$. But what about $$\mathsf{NEXP}=\mathsf{Co{-}NEXP}?$$ Is it known whether these two classes are equal?

# Answer
It is known that $\mathsf{NP} = \mathsf{coNP}$ implies $\mathsf{NEXP} = \mathsf{coNEXP}$, using a padding argument. However, both are considered unlikely.

The difference between classes like $\mathsf{NP}$ and $\mathsf{NEXP}$ and the class $\mathsf{NL}$ is that the former are defined by time constraints while the latter is defined by space constraints. The Immerman–Szelepcsényi argument used to prove $\mathsf{NL}=\mathsf{coNL}$ only works for space-constrained classes.
> 8 votes

---
Tags: complexity-theory, closure-properties, complexity-classes
---


title: Church-Turing and physical PDEs

text:
# Question
Title: Church-Turing and physical PDEs
When I read about the Church-Turing thesis it seems to be a common claim that "physical reality is Turing-computable." What is the basis for this claim? Are there any theoretical results along these lines?

For context, I am a researcher who works on physical simulations, so of course I'm aware that many partial differential equations (PDEs) that would arise in nature (e.g. the heat equation, wave equation, etc) can be approximated by numerical methods like finite elements, and that for many PDEs a solution can be estimated to arbitrary accuracy given enough computation (by decreasing the space and time step sizes).

However, I also know that proving convergence of finite element methods is *notoriously* difficult for PDEs of any appreciable complexity, even "easy" PDEs like the mean curvature flow that describes the shape of a soap film. I also know that many "Zeno-type" situations arise in practice in physical systems, such as Euler's disk or inelastic collapse. Is there reason to believe that the solutions to *all* PDEs, or at least all PDEs that would arise in nature, are Turing-computable?

# Answer
The branch of mathematics and computer science that studies these questions is computable mathematics. The general answer is that things tend to be computable. I would add to that the observation that it often takes some work to establish computability. For instance, you mention finite element methods and the problems with their convergence. This proves absolutely nothing about computability of PDEs because there are, or might be, other methods for solving PDEs.

Some references that migth interest you, in order of relevance:
> 4 votes

---
Tags: computability, simulation, church-turing-thesis, hypercomputation
---


# Question
Title: Queue that can sort by multiple priorities?
I have a high interest in priority-queues (E.g., see my answers on: Does there exist a priority queue with $O(1)$ extracts?), and was wondering if there is a priority-queue or similar data-structure where you can sort by multiple values?

For example, if I wanted to sort by `numval` and sort by `strval`, and be able to get the highest (Gödel numbering for str) in $\mathcal{O}(1)$.

```
struct Node {
    int numval;
    std::string strval;
};

```

Easily I can think to just maintain two priority-queues, but this would require twice the memory.

Is there a better way?

# Answer
> 3 votes
**Simple solution: use two queues**
If you want to keep track of multiple priorities that are unrelated then you'll have to use 2 priority queues.
You don't have to duplicate all the data, because you can just put a reference (pointer) to the data in your queue.
That way you only have 1 location where your object resides and two pointers to it in the two priority-queues.

So the memory load would be $O(nk+2n)$ where $k$ is the length of your object and $n$ is the number of objects.
As long as $k$ is significantly long the $2n$ factor will be insignificant.

**Complex solution: intertwine the queues and use COW semantics**
If the priorities are related, then you can lessen the memory load by implementing the priority queue as a linked structure where shared items link to the same node.
You'll have to use copy-on-write semantics on the shared nodes for this to work.

**For an example see B(+)Trees in databases**
Something very similar happens in databases, where the tables are represented as B-trees.
When a change is made a reference to the tree is copied and copy-on-write is applied to all nodes that are changed.
When the change is committed the pointers for the changed tree and the original tree are exchanged.
While the transaction is in progress the old tree and the new tree are intertwined.

**Beware the running time of COW**
You can do the same to your priority queue, but this only makes sense if most of the data will be the same for the queues or writes are rare, otherwise the copy-on-write semantics will kill your running time.

---
Tags: data-structures, asymptotics, efficiency, priority-queues, memory-management
---


title: Hash table collision probability

text:
# Question
Title: Hash table collision probability
For an open-addressing hash table, what is the average time complexity to find an item with a given key:

1. if the hash table uses linear probing for collision resolution?
2. if the hash table uses double probing for collision resolution?

From my understanding my answer to the first question would be $O(n)$ but I'm not sure about the double probing question.

# Answer
> 6 votes
What are the odds of a collision given a fixed hash table size?

**Size of hashtable**
When hashing $k$ items into a hash table with $n$ slots, the expected number of collisions is

$n - k + k(1-{\frac{1}{k}})^n$

The main statistic for a hash table is the `load factor:` $\alpha = \frac{n}{k}$
For a perfect hash the load factor also happens to be the probability that a collision will occur.

**Open addressing**
Back to the question:

> average time complexity to find an item with a given key if the hash table uses linear probing for collision resolution?

The length of probe sequence is proportional to $\frac{\alpha}{(1 - \alpha)}$. As the load factor $\alpha$ approaches 1, probe times goes to infinite.

The following graph shows the benefits and drawbacks of open addressing quite clearly.

Because of locality of reference open addressing is fast up to 70% load factor, after that running time deteriorates quickly.
*Note that the graph only shows cache locality issues. Its for this reason that the chaining times do not go up much. In reality the chaining time goes up exponentially as well when the hash table fills up, albeit slower than the linear probing time.*

Let $\alpha$ be the load factor

Double hashing has a time complexity of $O(2 * \frac{1}{2}(\dfrac{\alpha}{(1-\alpha)}))$

Linear probing has a time complexity of $O(1 * (\dfrac{\alpha}{(1-\alpha)}))$

So the time complexities are the same, but the constants are different.
Double hashing takes more time, but linear probing goes into pathological running time sooner as the fill factor goes up.

---
Tags: time-complexity, hash-tables
---


title: What is Pointer Jumping ?

text:
# Question
Title: What is Pointer Jumping ?
Studying parallel algorithms for CLRS, old edition Chapter 30. Can some one explain with a simple example what is pointer jumping and how exactly it works ?

# Answer
> 1 votes
I really can't explain it better than Wikipedia does:

Suppose you want to traverse a tree. You can traverse it in a serial manner by walking the tree (either recursively or otherwise), or you can traverse it parallel by starting at $N$ leaf nodes and following the shortest path to the root.

In the serial case your running time will be $O(n\log(n))$.
$n$ is because you need to visit all $n$ nodes and $\log(n)$ because of extra time spend going up and down the tree because you can only reach sibling nodes via their parent.

In the parallel case your best running time will be $O(\log(n))$ or more accurate $O(\frac{n}{m}\log(n))$ where $m$ is the number of threads used.
You do this by assigning a leaf node to a thread and finding the shortest path to the root.
If you have more leaf nodes than threads you'll assign more than one leaf node to a thread.

Because the height of a tree is $\log(n)$ the running time per thread is obviously $O(\log(n))$.
This is not as efficient as can be, because the closer you get to the root the more nodes will get visited more than once.
You can solve this issue by having the first thread to arrive at a parent to leave a breadcrumb after which subsequent threads drop out.
If you elect to let duplicate threads drop out of the traverse, you also solve the problem of thread synchronization issues when altering data in the tree.

---
Tags: algorithms, terminology, parallel-computing
---


# Question
Title: When is an ATM network connection superior to an IP connection?
Currently learning about Networks in Computer Science, and I don't understand why you would ever use an ATM (asynchronous transfer mode) network instead of IP, as IP doesn't have to be as reliable and can be set up much more quickly, and is what the entire Internet basically uses.

# Answer
ATM gives you a defined, guaranteed bandwidth once a connection is setup. Therefore it is great when you wish to **replace “end to end” leased lines**, with a network that can be configured without having to physically change cable connections. (ATM is still used a lot inside of BT (UK) telephone exchanges to allow line cards to be connected to different “providers” without having to reconnect the phone wires.)

*For example you need to read data values from a remote sensor at 32 kbs, and you can’t cope with a single value being lost or delayed. Another example is CCTV when you want wish to have any dropped frames.*

**However it is cheaper these days to have a IP network that is ten times faster than you need, compared to a ATM network at the speed you need……** **IP got the mass market** and the computer network vendors sold their kit for a lot less then the telecom equipment vendors.

This was partly due to the telecom service providers demanding lots of “bells and whistles”, then deciding once the telecom equipment vendors had designed what was asked for, that “of the shelf” Ethernet switches where good enough. So the customer was wrong, resulting in most large telecom equipment vendors closing down.

Therefore an ATM connection is superior to a IP connect when you need a continues fixed bandwidth and someone will sell you a ATM connect for a not much greater price then a IP connection!
> 2 votes

# Answer
AFAIR ATM was specifically designed to also transfer real time data like voice. This requires guaranteed properties like bandwidth and latency.

IP can't give those guarantees as it looses packets and reorders packets.

Also ATM is connection oriented, whereas IP needs the complexity of TCP to get that.
> 3 votes

---
Tags: computer-networks
---


# Question
Title: Are QR codes Turing-complete under the rules of Conway's Game of Life?
This is a bit of a weird question, but I was wondering earlier if QR codes are Turing-complete when interpreted as initial states for Conway's Game of Life.

My intuition is "yes", as there are infinitely many QR codes (they just get bigger as you add more information), and the Game of Life itself is Turing-complete. However, it's not inconceivable that the restrictions imposed by the QR code format mean that *no* QR codes are Turing-complete.

Another way to phrase the question would be **"can all Turing machines be encoded as a string which, when converted into a QR code and used as the initial state for Conway's Game of Life, produces equivalent output to the original Turing machine"**

# Answer
QR codes are limited to a maximum size 172x172, which is not nearly large enough to built a Turing complete state machine in.
A current implementation of a Turing machine in GoL takes 1714 by 1647 cells. It is undoubtedly sub optimal, but compressing it to 172x172 seems a stretch.

However let's assume the QR code is a little larger than 1714 square.
All of the elements in the listed Turing machine are constructable using gliders and besides much larger universal Turing machines have been constructed that are fully replicable. Given a large enough QR code most of the key space is arbitrary.
There are some fixed elements that would have to be destroyed.
There are no known patterns that cannot be destroyed by a well timed glider salvo and certainly the fixed patterns in the QR codes have been explored.

Given the amount of redundant parent patterns that reduce to the same child pattern it is quite likely it is possible.
Furthermore the error correction only has a local effect, so changing a pattern in the top corner does not affect data at the bottom.

If you change the question to:

> If I stamp my GoL grid with many QR codes, can I built a turing machine?

Then the answer is yes, because its trivial to collapse a QR code to a glider and a Turing machine can be constructed using gliders and only gliders.
> 8 votes

---
Tags: computability, computation-models, turing-completeness
---