# Question
Title: Solving an ordered knapsack problem exactly with a non linear (blackbox) evaluation function
Thanks in advance for the help.

I have the following problem which, for lack of a better description, I'm referring to as the problem I've listed in the title.

Specifically I have a knapsack problem where I must exactly fill the knapsack. Additionally, the order in which I place the elements into the knapsack affects the strength of the solution (but not the volume of the individual elements). The function that is used to evaluate the strength, or goodness, of the packing is non linear and very complex. Because of this, I have a model that I will use to repeatedly simulate my evaluation function to get an idea of the strength of each solution rather than directly evaluating my evaluation function (sort of like a surrogate function).

For example, suppose I have a knapsack of size ten. The following would be possible solutions assuming integers are the elements that I can place into the knapsack (for all intents in purposes my actual problem can be visualized in this manner): \[5,5\], \[3,3,4\], \[4,3,3\], etc.

What I'm interested in is two-fold. First, does this problem reduce to any well studied problems from which I could read up more on how they are solved? I'm currently thinking about using some kind of heuristic search to solve this problem, such as a Genetic Algorithm (I don't have to have the optimal solution, though I would like the best that I can get). Second and somewhat related to the first, what work if any has been done on problems that fit the description that I have given above? The knapsack problem is a very well studied problem and I would find it hard to believe if there hasn't been any work done on problems that fit my current one. Unfortunately though, while I've found work somewhat related to my problem, I haven't been able to find anything that directly reduces to my problem.

# Answer
If your function (or your surrogate function) has no structure, then there's nothing to say: you can't do any better than exhaustive search. In particular, you must examine every possible combination of the items that has the right weight. If your function has no structure, then you must evaluate it on each possible combination of items whose total weight matches the desired value: you can't rule out any of the possible combinations. There are exponentially such combinations, so your problem requires evaluating the function (or surrogate function) on exponentially many possible inputs.

Also, if your function has no structure, there are no heuristics or approximation algorithms that will do better than brute force (try some randomly chosen set of combinations and see which does best).

No, this case probably hasn't been studied, because it isn't interesting: there's nothing interesting or useful you can say about it, beyond what I've listed above.
> 1 votes

---
Tags: terminology, optimization, reference-request, heuristics, knapsack-problems
---


# Question
Title: Can random suitless $52$ playing card data be compressed to approach, match, or even beat entropy encoding storage? If so, how?
I have real data I am using for a simulated card game. I am only interested in the ranks of the cards, not the suits. However it is a standard $52$ card deck so there are only $4$ of each rank possible in the deck. The deck is shuffled well for each hand, and then I output the entire deck to a file. So there are only $13$ possible symbols in the output file which are $2,3,4,5,6,7,8,9,T,J,Q,K,A$. ($T$ = ten rank). So of course we can bitpack these using $4$ bits per symbol, but then we are wasting $3$ of the $16$ possible encodings. We can do better if we group $4$ symbols at a time, and then compress them, because $13^4$ = $28,561$ and that can fit rather "snugly" into $15$ bits instead of $16$. The theoretical bitpacking limit is log($13$) / log($2$) = $3.70044$ for data with $13$ random symbols for each possible card. However we cannot have $52$ kings for example in this deck. We MUST have only $4$ of each rank in each deck so the entropy encoding drops by about half a bit per symbol to about $3.2$.

Ok, so here is what I am thinking. This data is not totally random. We know there are $4$ of each rank so in each block of $52$ cards (call it a shuffled deck), so we can make several assumptions and optimizations. One of those being we do not have to encode the very last card, because we will know what it should be. Another savings would be if we end on a single rank; for example, if the last $3$ cards in the deck are $777$, we wouldn't have to encode those because the decoder would be counting cards up to that point and see that all the other ranks have been filled, and will assume the $3$ "missing" cards are all $7$s.

So my question to this site is, what other optimizations are possible to get an even smaller output file on this type of data, and if we use them, can we ever beat the theoretical (simple) bitpacking entropy of $3.70044$ bits per symbol, or even approach the ultimate entropy limit of about $3.2$ bits per symbol on average? If so, how?

When I use a ZIP type program (WinZip for example), I only see about a $2:1$ compression, which tells me it is just doing a "lazy" bitpack to $4$ bits. If I "pre-compress" the data using my own bitpacking, it seems to like that better, because then when I run that through a zip program, I am getting a little over $2:1$ compression. What I am thinking is, why not do all the compression myself (because I have more knowledge of the data than the Zip program does). I am wondering if I can beat the entropy "limit" of log($13$)/log($2$) = $3.70044$. I suspect I can with the few "tricks" I mentioned and a few more I can probably find out. The output file of course does not have to be "human readable". As long as the encoding is lossless it is valid.

Here is a link to $3$ million human readable shuffled decks ($1$ per line). Anyone can "practice" on a small subset of these lines and then let it rip on the entire file. I will keep updating my best (smallest) filesize based on this data.

https://drive.google.com/file/d/0BweDAVsuCEM1amhsNmFITnEwd2s/view

By the way, in case you are interested in what type of card game this data is used for, here is the link to my active question (with $300$ point bounty). I am being told it is a hard problem to solve (exactly) since it would require a huge amount of data storage space. Several simulations agree with the approximate probabilities though. No purely mathematical solutions have been provided (yet). It's too hard, I guess.

https://math.stackexchange.com/questions/1882705/probability-2-player-card-game-with-multiple-patterns-to-win-who-has-the-advant

I have a good algorithm that is showing $168$ bits to encode the first deck in my sample data. This data was generated randomly using the Fisher-Yates shuffle algorithm. It is real random data, so my newly created algorithm seems to be working VERY well, which makes me happy.

Regarding the compression "challenge", I am currently at about 160 bits per deck. I think I can go down to maybe 158. Yes I tried and I got 158.43 bits per deck. I think I am getting close to the limit of my algorithm so I succeeded to drop below 166 bits per deck but I failed to get 156 bits which would be 3 bits per card but it was a fun exercise. Perhaps in the future I will think of something to reduce each deck on average by 2.43 bits or more.

# Answer
> 3 votes
Another thing to consider: if you only care about compressing a full set of several million decks and you also don't care about what order they are in, you can gain additional encoding flexibility by discarding the information about the ordering of the set of decks. This would be the case, for instance, if you need to load the set to enumerate all the decks and process them, but don't care what order they are processed in.

You start by encoding each deck individually, as other answers have described how to do. Then, sort those encoded values. Store a series of differences between the sorted encoded values (where the first difference starts from encoded deck '0'). Given a large number of decks, the differences will tend to be smaller than the full encoding range, so you can use some form of varint encoding to handle occasional large differences while still storing the smaller differences efficiently. The appropriate varint scheme would depend on how many decks you have in the set (thus determining the average difference size.)

I unfortunately don't know the mathematics of how much this would help your compression, but thought this idea might be useful to consider.

# Answer
> 33 votes
Here is a complete algorithm which reaches the theoretical limit.

**Prologue: Encoding integer sequences**

A 13-integer sequence "integer with upper limit $a-1$, integer with upper limit $b-1$, "integer with upper limit $c-1$, integer with upper limit $d-1$,... integer with upper limit $m-1$" can always be coded with perfect efficiency.

1. Take the first integer, multiply it by $b$, add the second, multiply the result by $c$, add the third, multiply the result by $d$,… multiply the result by $m$, add the thirteenth – and that will produce a unique number between $0$ and $abcdefghijklm-1$.
2. Write down that number in binary.

The reverse is easy as well. Divide by $m$ and the remainder is the thirteenth integer. Divide the result by $l$ and the remainder is the twelfth integer. Carry on until you have divided by $b$: the remainder is the second integer and the quotient is the first integer.

So to code your cards in the best possible way, all we have to do is find a perfect correspondence between 13-integer sequences (with given upper limits) and arrangements of your shuffled cards.

Here is how to do it.

**Correspondence between shufflings and integer sequences**

Start with a sequence of 0 cards on the table in front of you.

**Step 1**

Take the four 2s in your pack and place them on the table.

What choices do you have? A card or cards may be placed either at the beginning of the sequence already on the table, or after any one of the cards in that sequence. In that case, this means that there are $1+0=1$ possible places to put cards.

The total number of ways of placing 4 cards in 1 places is $1$. Encode each of those ways as a number between $0$ and $1-1$. There is 1 such number.

*I got 1 by considering the ways of writing 0 as the sum of 5 integers: it is $\frac{4\times 3\times 2 \times 1}{4!}$.*

**Step 2**

Take the four 3s in your pack and place them on the table.

What choices do you have? A card or cards may be placed either at the beginning of the sequence already on the table, or after any one of the cards in that sequence. In that case, this means that there are $1+4=5$ possible places to put cards.

The total number of ways of placing 4 cards in 5 places is $70$. Encode each of those ways as a number between $0$ and $70-1$. There are 70 such numbers.

*I got 70 by considering the ways of writing 4 as the sum of 5 integers: it is $\frac{8\times 7\times 6 \times 5}{4!}$.*

**Step 3**

Take the four 4s in your pack and place them on the table.

What choices do you have? A card or cards may be placed either at the beginning of the sequence already on the table, or after any one of the cards in that sequence. In that case, this means that there are $1+8=9$ possible places to put cards.

The total number of ways of placing 4 cards in 9 places is $495$. Encode each of those ways as a number between $0$ and $495-1$. There are 495 such numbers.

*I got 495 by considering the ways of writing 8 as the sum of 5 integers: it is $\frac{12\times 11\times 10 \times 9}{4!}$.*

*And so on, until...*

**Step 13**

Take the four aces in your pack and place them on the table.

What choices do you have? A card or cards may be placed either at the beginning of the sequence already on the table, or after any one of the cards in that sequence. In that case, this means that there are $1+48=49$ possible places to put cards.

The total number of ways of placing 4 cards in 49 places is $270725$. Encode each of those ways as a number between $0$ and $270725-1$. There are 270725 such numbers.

*I got 270725 by considering the ways of writing 48 as the sum of 5 integers: it is $\frac{52\times 51\times 50 \times 49}{4!}$.*

---

This procedure yields a 1-to-1 correspondence between (a) shufflings of cards where you don't care about the suit and (b) sequences of integers where the first is between $0$ and $1-1$, the second is between $0$ and $70-1$, the third is between $0$ and $495-1$, and so on until the thirteenth, which is between $0$ and $270725-1$.

Referring to "Encoding integer sequences", you can see that such a sequence of integers is in 1-1 correspondence with the numbers between $0$ and $(1\times 70\times 495\times … \times 270725)-1$. If you look at the "product divided by a factorial" expression of each of the integers (*as described in italics at the end of each step*) then you will see that this means the numbers between $0$ and $$\frac{52!}{(4!)^{13}}-1\text,$$ which my previous answer showed was the best possible.

**So we have a perfect method for compressing your shuffled cards.**

---

**The algorithm**

**Precompute** a list of all the ways of writing 0 as the sum of 5 integers, of writing 4 as the sum of 5 integers, of writing 8 as the sum of 5 integers,… of writing 48 as the sum of 5 integers. The longest list has 270725 elements, so it is not particularly big. *(Precomputation isn't strictly necessary because you can easily synthesize each list as and when you need it: trying with Microsoft QuickBasic, even going through the 270725-element list was faster than the eye could see)*

To get from a shuffling to a sequence of integers:

The 2s contribute nothing, so let's ignore them. Write down a number between 0 and 1-1.

**The 3s:** How many 2s are there before the first 3? How many before the second? the third? the 4th? after the 4th? The answer is 5 integers which obviously add up to 4. So look up that sequence of 5 integers up in your "writing 4 as the sum of 5 integers" list, and note its position in that list. That will be a number between 0 and 70-1. Write it down.

**The 4s:** How many 2s or 3s are there before the first 4? How many before the second? the third? the 4th? after the 4th? The answer is 5 integers which obviously add up to 8. So look up that sequence of 5 integers up in your "writing 8 as the sum of 5 integers" list, and note its position in that list. That will be a number between 0 and 495-1. Write it down.

And so on, until…

**The aces:** How many non-ace cards are there before the first ace? How many before the second? the third? the 4th? after the 4th? The answer is 5 integers which obviously add up to 48. So look up that sequence of 5 integers up in your "writing 48 as the sum of 5 integers" list, and note its position in that list. That will be a number between 0 and 270725-1. Write it down.

You have now written down 13 integers. Encode them (as previously described) into a single number between $0$ and $\frac{52!}{(4!)^{13}}$. Write that number out in binary. It will take just under 166 bits.

This is the best possible compression, because it reaches the information-theoretical limit.

Decompression is straightforward: go from the big number to the sequence of 13 integers, and then use them to build up the sequence of cards as already described.

# Answer
> 23 votes
Rather than trying to encode each card separately into 3 or 4 bits, I suggest you encode the state of the entire deck into 166 bits. As Martin Kochanski explains, there are fewer than $2^{166}$ possible arrangements of the cards ignoring suits, so that means the state of the entire deck can be stored in 166 bits.

How do you do this compression and decompression algorithmically, in an efficient way? I suggest using lexicographic ordering and binary search. This will allow you to do compression and decompression efficiently (in both space and time), without requiring a large lookup table or other unrealistic assumptions.

In more detail: Let's order decks by using the lexicographic ordering on the uncompressed representation of the deck, i.e., a deck is represented in uncompressed form as a string like 22223333444455556666777788889999TTTTJJJJQQQQKKKKAAAA; you can order them according to lexicographic order. Now, suppose you have a procedure that given a deck $D$, counts the number of decks that come before it (in lexicographic order). Then you can use this procedure to compress a deck: given a deck $D$, you compress is to a 166-bit number by counting the number of decks that come before it and then outputting that number. That number is the compressed representation of the deck.

To decompress, use binary search. Given a number $n$, you want to find the $n$th deck in the lexicographic ordering of all decks. You can do this using a procedure along the lines of binary search: pick a deck $D\_0$, count the number of decks before $D\_0$, and compare that to $n$. That will tell you whether to adjust $D\_0$ to come earlier or later. I suggest you try to iteratively get the symbol right: if you want to recover a string like 22223333444455556666777788889999TTTTJJJJQQQQKKKKAAAA, first search to find what to use as the first symbol in the string (just try all 12 possibilities, or use binary search over the 12 possibilities), then when you've found the right value for the first symbol, search to find the second symbol, and so on.

All that remains is to come up with an efficient procedure to count the number of decks that come lexicographically before $D$. This looks like a straightforward but tedious combinatorial exercise. In particular, I suggest you build a subroutine for the following problem: given a prefix (like 222234), count the number of decks that start with that prefix. The answer to this problem looks like a pretty easy exercise in binomial coefficients and factorials. Then, you can invoke this subroutine a small number of times to count the number of decks that come before $D$.

# Answer
> 8 votes
The number of possible arrangements of the cards **ignoring suits** is $$\frac{52!}{(4!)^{13}}\text,$$ whose logarithm base 2 is 165.976, or 3.1919 bits per card, which is better than the limit you gave.

Any fixed "bits per card" encoding will not make sense because, as you note, the last card can always be encoded in $0$ bits and in many cases the last *few* cards can be as well. That means that for quite a way towards the "tail" of the pack the number of bits needed for each card will be quite a lot less than you think.

By far the best way of compressing the data would be to find 59 bits of other data that you want to pack with your card data anyway (59.6 bits, actually) and, writing those 59 bits as a 13-digit number modulo 24 (=$4!$), assign a suit to each card (one digit chooses between the $4!$ ways of assigning suits to the aces, another does the same for the kings, and so on). Then you have a pack of 52 wholly distinct cards. $52!$ possibilities can be encoded in 225.58 bits very easily indeed.

But doing it without taking the opportunity of encoding those extra bits is also possible to some extent, and I will think about it as I am sure everyone else is. Thank you for a really interesting problem!

# Answer
> 3 votes
This is a long solved problem.

When you deal a deck of 52 cards, every card you deal has one of up to 13 ranks with known probabilities. The probabilities change with every card dealt. That is handled optimally using an ancient technique called adaptive arithmetic coding, an improvement to Huffman coding. Usually this is used for known, unchanging probabilities, but it can just as well be used for changing probabilities. Read the wikipedia article about arithmetic coding:

https://en.wikipedia.org/wiki/Arithmetic\_coding

# Answer
> 3 votes
Both D.W. and Martin Kochanski have already described algorithms for constructing a bijection between deals and integers in the range $\[0, {52!\over(4!)^{13}})$, but it seems like neither of them have reduced the problem to its simplest form. (Note 1)

Suppose we have a (partial) deck described by the ordered list $a$, where $a\_i$ is the number of cards of type $i$. In the OP, the initial deck is described by a list of 13 elements, each of them with value 4. The number of distinct shuffles of such a deck is

$$c(a) = {(\sum a\_i)! \over \prod a\_i!}$$

which is a simple generalization of binomial coefficients, and indeed could be proven by simply arranging the objects one type at a time, as suggested by Martin Kochanski. (See below, note 2)

Now, for any such (partial) deck, we can select a shuffle one card at a time, using any $i$ for which $a\_i\>0$. The number of unique shuffles starting with $i$ is

$$\begin{cases}0 & \text{if } a\_i = 0 \\ c(\langle a\_1,...,a\_{i-1},a\_i-1,a\_{i+1},...,a\_n \rangle) & \text{if } a\_i \> 0. \end{cases}$$

and by the above formula, we have

$$c(\langle a\_1,...,a\_{i-1},a\_i-1,a\_{i+1},...,a\_n \rangle) = {a\_ic(a)\over\sum a\_i}$$

We can then recurse (or iterate) through the deck until the shuffle is complete by observing that the number of shuffles corresponding to a prefix lexicographically smaller than the prefix up to $i$ is

$$ {c(a)\sum\limits\_{j=1}^i a\_j}\over\sum\limits\_{j=1}^n a\_j$$

I wrote this in Python to illustrate the algorithm; Python is as reasonable a pseudocode as any. Note that most of the arithmetic involves extended precision; the values $k$ (representing the ordinal of the shuffle) and $n$ (the total number of possible shuffles for the remaining partial deck) are both 166-bit bignums. To translate the code to another language, it will be necessary to use some sort of bignum library.

Also, I just use list of integers rather than card names, and -- unlike the above maths -- the integers are 0-based.

To encode a shuffle, we walk through the shuffle, accumulating at each point the number of shuffles which start with a smaller card using the above formula:

```
from math import factorial
T = factorial(52) // factorial(4) ** 13

def encode(vec):
    a = [4] * 13
    cards = sum(a)
    n = T
    k = 0
    for idx in vec:
        k += sum(a[:idx]) * n // cards
        n = a[idx] * n // cards
        a[idx] -= 1
        cards -= 1
    return k

```

Decoding a 166-bit number is the simple inverse. At each step, we have the description of a partial deck and an ordinal; we need to skip over the shuffles starting with smaller cards than the one which corresponds to the ordinal, and then we compute output the selected card, remove it from the remaining deck, and adjust the number of possible shuffles with the selected prefix:

```
def decode(k):
    vec = []
    a = [4] * 13
    cards = sum(a)
    n = T
    while cards > 0:
        i = cards * k // n
        accum = 0
        for idx in range(len(a)):
            if i < accum + a[idx]:
                k -= accum * n // cards
                n = a[idx] * n // cards
                a[idx] -= 1
                vec.append(idx)
                break
            accum += a[idx]
        cards -= 1
    return vec

```

I made no real attempt to optimize the above code. I ran it against the entire 3mil.TXT file, checking that `encode(decode(line))` resulted in the original encoding; it took just under 300 seconds. (Seven of the lines can be seen in the on-line test on ideone.) Rewriting in a lower-level language and optimizing the division (which is possible) would probably reduce that time to something manageable.

Since the encoded value is simply an integer, it can be output in 166 bits. There is no value in deleting the leading zeros, since there would then be no way to know where an encoding terminated, so it is really a 166-bit encoding.

However, it's worth noting that in a practical application, it is probably never necessary to encode a shuffle; a random shuffle can be generated by generating a random 166-bit number and decoding it. And it is not really necessary that all 166 bits be random; it would be possible to, for example, start with a 32-bit random integer and then fill in the 166 bits using any standard RNG seeded with the 32-bit number. So if the goal is simply to be able to reproducibly store a large number of random shuffles, you can reduce the per-deal storage requirement more or less arbitrarily.

If you want to encode a large number $N$ of actual deals (generated in some other fashion) but don't care about the order of the deals, you can delta-encode the sorted list of numbers, saving approximately $\log\_2 N$ bits for each number. (The savings results from the fact that a sorted sequence has less entropy than an unsorted sequence. It does not reduce the entropy of a single value in the sequence.)

Assuming that we need to encode a sorted list of $N$ $k$-bit numbers, we can proceed as follows:

1. Choose $p$ as an integer close to $\log\_2 N$ (either the floor or the ceiling will work; I usually go for the ceiling).
2. We implicitly divide the range of numbers into $2^p$ intervals by binary prefix. Each $k$-bit number is divided into a $p$-bit prefix and an $k-p$-bit suffix; we write out only the suffixes (in order). This requires $N\*(k-p)$ bits.
3. Additionally, we create a bit-sequence: For each of the $2^p$ prefixes (except prefix $0$) we write out a $0$ for each number with that prefix (if any) followed by a $1$. This sequence obviously has $2^p+N$ bits: $2^p$ $1$s and $N$ $0$s.

To decode the numbers we start a prefix counter at 0, and proceed to work through the bit sequence. When we see a $0$, we output the current prefix and the next suffix from the suffix list; when we see a $1$, we increment the current prefix.

The total length of the encoding is $N\*(k-p) + N + 2^p$ which is very close to $N\*(k-p) + N + N$, or $N\*(k-p+2)$, for an average of $k-p+2$ bits per value.

### Notes

1. $52!\over(4!)^{13}$ is $92024242230271040357108320801872044844750000000000$, and $\log\_2 {52!\over(4!)^{13}}$ is approximately $165.9765$. In the text, I occasionally pretend that the base-2 logarithm is really $166$; in the case of generating random ordinals within the range, a rejection algorithm could be used which would only very rarely reject a generated random number.
2. For convenience, I write $S\_k$ for $\sum\limits\_{i=k}^n a\_i$; then the $a\_1$ objects of type $1$ can be placed in $S\_1 \choose a\_1$ ways, and then the objects of type $2$ can be placed in $S\_2 \choose a\_2$ ways, and so on. Since ${S\_i \choose a\_i}={S\_i! \over a\_i!(S\_i - a\_i)!}={S\_i!\over {a\_i!S\_{i+1}!}}$, that leads to the total count

$$\prod\limits\_{i=1}^n S\_i! \over \prod\limits\_{i=1}^n a\_i! S\_{i+1}!$$

which simplifies to the formula above.

# Answer
> 2 votes
As an alternate solution to this problem, my algorithm uses compound fractional (non integer) bits per card for groups of cards in the deck based on how many unfilled ranks there are remaining. It is a rather elegant algorithm. I checked my encode algorithm by hand and it is looking good. The encoder is outputting what appear to be correct bitstrings (in byte form for simplicity).

The overview of my algorithm is that it uses a combination of groups of cards and compound fractional bit encoding. For example, in my shared test file of $3$ million shuffled decks, the first one has the first $7$ cards of $54A236J$. The reason I chose a $7$ card block size when $13$ ranks of cards are possible is because $13^7$ "shoehorns" (fits snugly) into $26$ bits (since $13^7$ = $62,748,517$ and $2^{26}$ = $67,108,864$). Ideally we want those $2$ numbers to be as close as possible (but with the power of 2 number slightly higher) so we don't waste more than a very small fraction of a bit in the bit packing process. Note I could have also chosen groupsize $4$ when encoding $13$ ranks since $13^4$ = $28,561$ and $2^{15}$ = $32,768$. It is not as tight a fit since $15/4 = 3.75$ but $26/7 = 3.714$. So the number of bits per card is slightly lower per card if we use the $26/7$ packing method.

So looking at $54A236J$, we simply look up the ordinal position of those ranks in our master "$23456789TJQKA$" list of sorted ranks. For example, the first actual card rank of $5$ has a lookup position in the rank lookup string of $4$. We just treat these $7$ rank positions as a base $13$ number starting with 0 (so the position 4 we previously got will actually be a 3). Converted back to base $10$ (for checking purposes), we get $15,565,975$. In $26$ bits of binary we get $00111011011000010010010111$.

The decoder works in a very similar way. It takes (for example) that string of $26$ bits and converts it back to decimal (base 10) to get $15,565,975$, then converts it to base $13$ to get the offsets into the rank lookup string, then it reconstructs the ranks one at a time and gets the original $54A236J$ first $7$ cards. Note that the blocksize of bits wont always be 26 but will always start out at 26 in each deck. The encoder and decoder both have some important information about the deck data even before they operate. That is one exceptionally nice thing about this algorithm.

Each # of ranks remaining (such as $13, 12, 11 ..., 2, 1)$ has its own groupsize and cost (# of bits per card). These were found experimentally just playing around with powers of $13,12,11...$ and powers of $2$. I already explained how I got the groupsize for when we can see $13$ ranks, so how about when we drop to $12$ unfilled ranks? Same method. Look at the powers of $12$ and stop when one of them comes very close to a power of $2$ but just slightly under it. $12^5$ = $248,832$ and $2^{18}$ = $262,144$. That is a pretty tight fit. The number of bits encoding this group is $18/5$ = $3.6$. In the $13$ rank group it was $26/7$ = $3.714$ so as you can see, as the number of unfilled ranks decreases (ranks are filling up such as $5555$, $3333$), the number of bits to encode the cards decreases.

Here is my complete list of costs (# of bits per card) for all possible # of ranks to be seen:

$13~~~~26/7 = 3.714 = 3~~5/7$
$12~~~~18/5 = 3.600 = 3~~3/5$
$11~~~~~~7/2 = 3.500 = 3~~1/2$
$10~~~~10/3 = 3.333 = 3~~1/3$
$~~9~~~~16/5 = 3.200 = 3~~1/5$
$~~8~~~~~~3/1 = 3.000 = 3$
$~~7~~~~17/6 = 2.833 = 2~~5/6$
$~~6~~~~13/5 = 2.600 = 2~~3/5$
$~~5~~~~~~7/3 = 2.333 = 2~~1/3$
$~~4~~~~~~2/1 = 2.000 = 2$
$~~3~~~~~~5/3 = 1.667 = 1~~2/3$
$~~2~~~~~~1/1 = 1.000 = 1$
$~~1~~~~~~0/1..4 = 0.0 = 0$

So as you can clearly see, as the number of unfilled ranks decreases (which it will do every deck), the number of bits needed to encode each card also decreases. You might be wondering what happens if we fill a rank but we are not yet done a group. For example, if the first $7$ cards in the deck were $5,6,7,7,7,7,K$, what should we do? Easy, The $K$ would normally drop the encoder from $13$ rank encoding mode to $12$ rank encoding mode. However, since we haven't yet filled the first block of $7$ cards in $13$ rank encoding mode, we include the $K$ in that block to complete it. There is very little waste this way. There are also cases while we are trying to fill a block, the # of filled ranks bumps up by $2$ or even more. That is also no problem as we just fill the block in the current encoding mode, then we pick up in the new encoding mode which may be $1,2,3...$ less or even stay in the same mode (as was the case in the first deck in the datafile as there are $3$ full blocks in the $13$ rank encoding mode). This is why it is important to make the blocksizes reasonable such as between size $1$ and $7$. If we made it size $20$ for example, we would have to fill that block at a higher bitrate than if we let the encoder transition into a more efficient encoding mode (encoding less ranks).

When I ran this algorithm (by hand) on the first deck of cards in the data file (which was created using Fisher-Yates unbiased shuffle), I got an impressive $168$ bits to encode which is almost identical to optimal binary encoding but requires no knowledge of ordinal positions of all possible decks, no very large numbers, and no binary searches. It does however require binary manipulations and also radix manipulations (powers of $13, 12, 11$...).

Notice also that when the number of unfilled ranks = $1$, the overhead is $0$ bits per card. Best case (for encoding) is we want the deck to end on a run of the same cards (such as $7777$) cuz those get encoded for "free" (no bits required for those). My encode program will suppress any output when the remaining cards are all the same rank. This is cuz the decoder will be counting cards for each deck and know if after seeing card $48$, if some rank (like $7$) has not yet been seen, all $4$ remaining cards MUST be $7$s. If the deck ends on a pair (such as 77), triple/set (such as 777) or a quad ( such as 7777), we get additional savings for that deck using my algorithm.

Another "pretty" thing about this algorithm is that it never needs to use any numbers larger than $32$ bit so it wont cause problems in some languages that "don't like" large numbers. Actually the largest numbers need to be on the order of $2^{26}$ which are used in the $13$ rank encoding mode. From there they just get smaller. In fact, if I really wanted to, I could make the program so that it doesn't use anything larger than $16$ bit numbers but this is not necessary as most computer languages can easily handle $32$ bits well. Also this is beneficial to me since one of the bit functions I am using maxes out at $32$ bit. It is a function to test if a bit is set or not.

In the first deck in the datafile, the encoding of cards is as follows (diagram to come later). Format is (groupsize, bits, rank encode mode):

($7,26,13$) First $7$ cards take $26$ bits to encode in $13$ rank mode.
($7,26,13$)
($7,26,13$)
($5,18,12$)
($5,18,12$)
($3,10,10$)
($3,~~9,~~8$)
($6,17,~~7$)
($5,13,~~6$)
($3,~~5,~~3$)
($1,~~0,~~1$)

This is a total of $52$ cards and $168$ bits for an average of about $3.23$ bits per card. There is no ambiguity in either the encoder or the decoder. Both count cards and know which encode mode to use/expect.

Also notice that $18$ cards, (more than $1/3$rd of the deck), are encoded BELOW the $3.2$ bits per card "limit". Unfortunately those are not enough cards to bring the overall average below about $3.2$ bits per card. I imagine in the best case or near best case (where many ranks fill up early such as $54545454722772277...$), the encoding for that particular deck might be under $3$ bits per card, but of course it is the average case that counts. I think best case might be if all the quads are dealt in order which might never happen if given all the time in the universe and the fastest supercomputer. Something like $22223333444455556666777788889999TTTTJJJJQQQQKKKKAAAA$. Here the rank encode mode would drop fast and the last $4$ cards would have $0$ bits of overhead. This special case takes only 135 bits to encode.

Also one possible optimization I am considering is to take all the ranks that have only $1$ card remaining and treating those all as a special "rank" by placing them in a single "bucket". The reason here is if we do that, the encoder can drop into a more efficient packing mode quicker. For example, if we are in $10$ rank encoding mode but we only have one more each of ranks $3,7$, and $K$, those cards have much less chance of appearing than the other cards so it doesn't make much sense to treat them the same. If instead I dropped to $8$ rank encoding mode which is more efficient that $10$ rank mode, perhaps I could use fewer bits for that deck. When I see one of the cards in that special "grouped" bucket of several cards, I would just output that special "rank" (not a real rank but just an indicator we just saw something in that special bucket) and then a few more bits to tell the decoder which card in the bucket I saw, then I would remove that card from the group (since it just filled up). I will trace this by hand to see if any bit savings is possible using it. Note there should be no ambiguity using this special bucket because both the encoder and decoder will be counting cards and will know which ranks have only $1$ card remaining. This is important because it makes the encoding process more efficient when the decoder can make correct assumptions without the encoder having to pass extra messages to it.

Here is the first full deck in the $3$ million deck data file and a trace of my algorithm on it showing both the block groupings and the transitions to a lower rank encoding mode (like when transitioning from $13$ to $12$ unfilled ranks) as well as how many bits needed to encode each block. x and y are used for $11$ and $10$ respectively because unfortunately they happened on neighboring cards and don't display well juxtaposed.

$~~~~~~~~~26~~~~~~~~~~~~~26~~~~~~~~~~~~~26~~~~~~~~~~~~18~~~~~~~~~18~~~~~~~10~~~~~~9~~~~~~~~~~17~~~~~~~~~~~13~~~~~~~~5~~~~~0$
$~~~~54A236J~~87726Q3~~3969AAA~~QJK7T~~9292Q~~36K~~J57~~~T8TKJ4~~48Q8T~~55K~~4$
$13~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~12~~~~~~~~~~~~~~~~~~~~xy~~~~~98~~~~~~~~~7~~~~~~~~~~~~~~6~~~~~~~~543~~~~~2~1~~0$

Note that there is some inefficiency when the encode mode wants to transition early in a block (when the block is not yet completed). We are "stuck" encoding that block at a slightly higher bit level. This is a tradeoff. Because of this and because I am not using every possible combination of the bit patterns for each block (except when it is an integer power of $2$), this algorithm cannot be optimal but can approach $166$ bits per deck. The average on my datafile is around $175$. The particular deck was "well behaved" and only required $168$ bits. Note that we only got a single 4 at the end of the deck but if instead we got all four 4s there, that is a better case and we would have needed only 161 bits to encode that deck, a case where the packing actually beats the entropy of a straight binary encode of the ordinal position of it.

I now have the code implemented to calculate the bit requirements and it is showing me on average, about 175 bits per deck with a low of 155 and a high of 183 for the 3 million deck test file. So my algorithm seems to use 9 extra bits per deck vs. the straight binary encode of the ordinal position method. Not too bad at only 5.5% additional storage space required. 176 bits is exactly 22 bytes so that is quite a bit better than 52 bytes per deck. Best case deck (didn't show up in 3 million deck test file) packs to 136 bits and worst case deck (did show up in testfile 8206 times), is 183 bits. Analysis shows worst case is when we don't get the first quad until close to (or at) card 40. Then as the encode mode wants to drop quickly, we are "stuck" filling blocks (as large as 7 cards) in a higher bit encoding mode. One might think that not getting any quads until card 40 would be quite rare using a well shuffled deck, but my program is telling me it happened 321 times in the testfile of 3 million decks so that it about 1 out of every 9346 decks. That is more often that I would have expected. I could check for this case and handle it with less bits but it is so rare that it wouldn't affect the average bits enough.

Also here is something else very interesting. If I sort the deck on the raw deck data, the length of prefixes that repeat a significant # of times is only about length 6 (such as 222244). However with the packed data, that length increases to about 16. That means if I sort the packed data, I should be able to get a significant savings by just indicating to the decoder a 16 bit prefix and then just output the remainder of the decks (minus the repeating prefix) that have that same prefix, then go onto the next prefix and repeat. Assuming I save even just 10 bits per deck this way, I should beat the 166 bits per deck. With the enumeration technique stated by others, I am not sure if the prefix would be as long as with my algorithm. Also the packing and unpacking speed using my algorithm is surprisingly good. I could make it even faster too by storing powers of 13,12,11... in an array and using those instead of expression like 13^5.

Regarding the 2nd level of compression where I sort the output bitstrings of my algorithm then use "difference" encoding: A very simple method would be to encode the 61,278 unique 16 bit prefixes that show up at least twice in the output data (and a maximum of 89 times reported) simply as a leading bit of 0 in the output to indicate to the 2nd level decompressor that we are encoding a prefix (such as 0000111100001111) and then any packed decks with that same prefix will follow with a 1 leading bit to indicate the non prefix part of the packed deck. The average # of packed decks with the same prefix is about 49 for each prefix, not including the few that are unique (only 1 deck has that particular prefix). It appears I can save about 15 bits per deck using this simple strategy (storing the common prefixes once). So assuming I really do get 15 bit saving per deck and I am already at about 175 bits per deck on the first level packing/compression, that should be a net of about 160 bits per deck, thus beating the 166 bits of the enumeration method.

After the 2nd level of compression using difference (prefix) encoding of the sorted bitstring output of the first encoder, I am now getting about 160 bits per deck. I use length 18 prefix and just store it intact. Since almost all (245013 out of 262144 = 93.5%) of those possible 18 bit prefixes show up, it would be even better to encode the prefixes. Perhaps I can use 2 bits to encode what type of data I have. 00 = regular length 18 prefix stored, 01= "1 up prefix" (same as previous prefix except 1 added), 11 = straight encoding from 1st level packing (approx 175 bits on average). 10=future expansion when I think of something else to encode that will save bits.

Did anyone else beat 160 bits per deck yet? I think I can get mine a little lower with some experimenting and using the 2 bit descriptors I mentioned above. Perhaps it will bottom out at 158ish. My goal is to get it to 156 bits (or better) because that would be 3 bits per card or less. Very impressive. Lots of experimenting to get it down to that level because if I change the first level encoding then I have to retest which is the best 2nd level encoding and there are many combinations to try. Some changes I make may be good for other similar random data but some may be biased towards this dataset. Not really sure but if I get the urge I can try another 3 million deck dataset to see what happens like if I get similar results on it.

One interesting thing (of many) about compression is you are never quite sure when you have hit the limit or are even approaching it. The entropy limit tells us how many bits we need if ALL possible occurrences of those bits occur about equally, but as we know, in reality, that rarely happens with a large number of bits and a (relatively) small # of trials (such as 3 million random decks vs almost $10^{50}$ bit combinations of 166 bits.

Does anyone have any ideas on how to make my algorithm better like what other cases I should encode that would reduce bits of storage for each deck on average? Anyone?

2 more things: 1) I am somewhat disappointed that more people didn't upvote my solution which although not optimal on space, is still decent and fairly easy to implement (I got mine working fine). 2) I did analysis on my 3 million deck datafile and noticed that the most frequently occurring card where the 1st rank fills (such as 4444) is at card 26. This happens about 6.711% of the time (for 201322 of the 3 million decks). I was hoping to use this info to compress more such as start out in 12 symbol encode mode since we know on average we wont see every rank until about middeck but this method failed to compress any as the overhead of it exceeded the savings. I am looking for some tweaks to my algorithm that can actually save bits.

So does anyone have any ideas what I should try next to save a few bits per deck using my algorithm? I am looking for a pattern that happens frequently enough so that I can reduce the bits per deck even after the extra overhead of telling the decoder what pattern to expect. I was thinking something with the expected probabilities of the remaining unseen cards and lumping all the single card remaining ones into a single bucket. This will allow me to drop into a lower encode mode quicker and maybe save some bits but I doubt it.

Also, F.Y.I., I generated 10 million random shuffles and stored them in a database for easy analysis. Only 488 of them end in a quad (such as 5555). If I pack just those using my algorithm, I get 165.71712 bits on average with a low of 157 bits and a high of 173 bits. Just slightly below the 166 bits using the other encoding method. I am somewhat surprised at how infrequent this case is (about 1 out of every 20,492 shuffles on average).

---
Tags: data-compression
---


# Question
Title: How to prove that the reversal of the concatenation of two strings is the concatenation of the reversals?
Given languages $L\_1$ and $L\_2$, how do we prove that $$(L\_1L\_2)^{\mathrm{rev}} = (L\_2^{\mathrm{rev}})(L\_1^{\mathrm{rev}})\\,,$$ where ${}^{\mathrm{rev}}$ denotes reversal?

I think using mathematical induction, it can be shown true for two languages $L\_1$ and $L\_2$ of length $1$ each and then do induction using one of the lengths and then repeat with the other length. Is there any other way of proving this in a simpler way without making it too big with induction method?

# Answer
> 5 votes
Well, consider the following "proof" (I'll explain afterwords why the quotation marks):

Let $w=a\_1\cdots a\_n$ be a word, then we have that

$w\in (L\_1L\_2)^{\mathrm{rev}}$ iff

$a\_n\cdots a\_1\in L\_1L\_2$, iff

there exists $0\le k\le n$ such that $a\_n\cdots a\_k\in L\_1$ and $a\_{k-1}\cdots a\_1\in L\_2$, iff

there exists $0\le k\le n$ such that $a\_k\cdots a\_n\in L\_1^{\mathrm{rev}}$ and $a\_{1}\cdots a\_ {k-1}\in L\_2^{\mathrm{rev}}$, iff

$a\_1\cdots a\_n\in L\_2^{\mathrm{rev}}L\_1^{\mathrm{rev}}$ iff

$w\in L\_2^{\mathrm{rev}}L\_1^{\mathrm{rev}}$

In my opinion, this proof is correct, formal, and would be accepted as a proof of the claim.

However, each "iff" along the way (apart from the last one) actually hides an inductive proof. The point is that each of these inductions is extremely trivial. In fact, even writing $w=a\_1\cdots a\_n$ actually hides some induction. So you need to ask yourself how "deep" do you want to go into the technicalities.

If you want to prove this claim from basic principles, i.e. from the axioms of set theory, then you need to formalize everything. This would be very painful, but such things are actually useful when we use computer-assisted proofs.

# Answer
> 2 votes
I know that we already have an solution to this problem, but the above solution's comments inspired me to write this presentation.

The sequences over a type `X` are *defined* to be the free monoid over `X`. In particular, this means we have a monoid `List X` with a binary operation denoted `_++_`, unit denoted `[]`, and singelton embedding `x ↦ [x]`. ─this is the common notation in the functional programming community.

Since every element of this monoid ─ie every sequence─ is either empty, a singelton, or a catenation, we can define the reverse inductively by

```
_ʳᵉᵛ : List X → List X
[]ʳᵉᵛ = []
[x]ʳᵉᵛ = [x]
(u ++ v)ʳᵉᵛ = v ʳᵉᵛ ++ u ʳᵉᵛ

```

Then we can calculate the desideratum as follows:

```
   (L₁ · L₂)ʳᵉᵛ
=⟨ direct image definition ⟩
   { (u ++ v)ʳᵉᵛ ❙ u ∈ L₁ ∧ v ∈ L₂}
=⟨ definition of _ʳᵉᵛ ⟩
   { v ʳᵉᵛ ++ u ʳᵉᵛ ❙ u ∈ L₁ ∧ v ∈ L₂}
=⟨ dummy renaming ⟩
   { v ʳᵉᵛ ʳᵉᵛ ++ u ʳᵉᵛ ʳᵉᵛ ❙ u ʳᵉᵛ ∈ L₁ ∧ v ʳᵉᵛ ∈ L₂ }
=⟨ ʳᵉᵛ is an involution as can be easily checked ⟩
   { v ++ u ❙ u ʳᵉᵛ ∈ L₁ ∧ v ʳᵉᵛ ∈ L₂ }
=⟨ direct image definition ⟩
   { v ++ u ❙ u ∈ L₁ ʳᵉᵛ ∧ v ∈ L₂ ʳᵉᵛ }
=⟨ symmetry of conjunction ⟩
   { v ++ u ❙ v ∈ L₂ ʳᵉᵛ ∧ u ∈ L₁ ʳᵉᵛ }
=⟨ definition of language catenation ⟩
   L₂ ʳᵉᵛ · L₁ ʳᵉᵛ

```

I just wanted to mention this alternative view of sequences :-)

---
Tags: formal-languages, proof-techniques, induction
---


# Question
Title: How to prevent overflow and underflow in the Euclidean distance and Mahalanobis distance
I was working in my project when I was struck by the question of whether it would be necessary, or at least cautious, prevent overflow and underflow in the calculation of these two distances.

I remembered that there is an implementation of the calculation of the hypotenuse to prevent this. Most languages implementers, and is known for Hypot

The calculation of the Euclidean distance remains the same "pattern" and I thought that if `Hypot()` controls the overflow and underflow should also beware of the Euclidean distance. I've disappointed to note that the language we use, and others, do not control the overflow and underflow for calculating distance. Will not worth spend this "additional effort"?

I did a searchs and came to a question in Math.StackExchange

There is no definitive answer to this issue and is somewhat old. The first thing I wondered is: Will okay? I think that yes, seeing that is a generalization of the same procedure that performs `Hypot()`.

I decided to extrapolate this concept to the Mahalanobis distance. The original is as follows:

$$D\_M(X,Y,L) = \sqrt{\sum\_{i=1}^{n}\left(\frac{X\_i-Y\_i}{L\_i}\right)^2}$$

Since $L$ is the vector of eigenvalues.

And my proposal is this:

$$D\_M(X,Y,L) = C\sqrt{\sum\_{i=1}^{n}\left(\frac{X\_i-Y\_i}{L\_i }\frac{1}{C}\right)^2}$$

That is the same to:

$$D\_M(X,Y,L) = C\sqrt{\sum\_{i=1}^{n}\left(\frac{X\_i-Y\_i}{L\_i C}\right)^2}$$

And $C$ is the max value from the $|(X\_i-Y\_i)/L\_i|$:

$$C = \max\_{i}\left(|\frac{X\_i-Y\_i}{L\_i}|\right)$$

Is it okay?

# Answer
That is a long solved problem. First, if you are using double precision floating point numbers in IEEE754 format (which is most common), that's what extended precision was invented for. Even in the extreme case, $X\_i$ and $Y\_i$ huge, $L\_i$ tiny, the numbers involved are less than $10^{1300}$ and extended precision goes up to about $10^{4000}$.

Without extended precision available, or if your numbers are already in extended precision, you just calculate the result and check whether you had an overflow or if the result is tiny. Tiny results are critical as well: If you use double precision floating point numbers, and your numbers are around $10^-200$, then squaring them gives you zero. There will be a lower bound c where you can prove "if the result is greater than c, then any underflow in the calculation didn't change the final result".

If overflow happens, or underflow happens, then you scale the numbers by a suitable power of two. Do NOT divide by the maximum value, because that introduces rounding errors, and there are cases with n = 2, $L\_i = 1$, where $|X\_1 - Y\_1| ≤ |x\_1 - y\_1|$, $|X\_2 - Y\_2| ≤ |x\_2 - y\_2|$, yet the calculated distance of X, Y is greater than the calculated distance of x, y, due to rounding errors. Scaling by a power of two avoids the problem because it doesn't create any rounding errors.

And you want to make sure that the order of numbers doesn't make a difference. For n = 2 you must make sure that no fused multiply/add operations are used. For n ≥ 3 you probably want to sort the numbers so the ones with smallest absolute difference come first. Otherwise you can get into situations where the distance between $(X\_1, X\_2)$ and $(Y\_1, Y\_2)$ is not the same as the distance between $(X\_2, X\_1)$ and $(Y\_2, Y\_1)$.
> 2 votes

# Answer
I don't know whether your approach is correct, but to answer the title, one way to avoid overflow is using approximations, for example (copied from here):

$$\frac{1007}{1024}\max(|x|,|y|) + \frac{441}{1204}\min(|x|,|y|)$$

Note that this should work fine to avoid overflow from large values. However, I think the approximation will be quite bad for high-dimensional cases (10 dimensions or more), which is another cause of overflows.
> 0 votes

---
Tags: arithmetic, floating-point, numerical-algorithms, euclidean-distance
---


# Question
Title: Why can you push multiple symbols on a PDA stack at once?
I'm really new to learning about PDA's and stuff, i understand that on a edge between 2 nodes you'll have something like this a,b-\>c. This means:

if a is in the beginning of your string and b is on top of your stack you can

* remove a from your string (the one you run through the PDA),
* remove b from your stack
* place c on your stack

and take the edge...

My book also tells me that you can place more then one symbols on your stack. For instance a,b-\>cd.

I think this is because you can also have this edge ε, ε -\> c wich just puts c on the top of the stack,

so a,b-\>cd between Node 1 and 2 can by replaced by Node1 - a,b-\>c - New node - ε, ε-\>d -\> Node2. Can someone please confirm if this is correct?

the pda is defined as (Q,E,T,d,s,F) with

* Q an finite collection of states
* E a finite inputalfabet
* T a finite stackalfabet
* d a transitionfunction Q x E (including ε) x T (including ε) -\> V collection of(Q x T (including ε))
* s the startstate
* F a collection of eindstates (subcollection of Q)

# Answer
You always have to take out a symbol. So if we could only write a single symbol, we could never really build up stack content.

Writing more than two symbols is just syntactic sugar; we could easily simulate it with PDAs restricted to writing zero, one, or two symbols.
> 5 votes

---
Tags: automata, pushdown-automata
---


# Question
Title: Compression of a text that contains only the 5 first letters of the alphabet?
So the question is: "Imagine the compression of a text written only with the first 5 characters of the alphabet (a, b, c, d, e). Knowing that their apparition's frequency is 1)e, 2)a, 3)c, 4)d, 5)b, code the letters on the minimum bits possible."

so here's how I did start:

We have 5 characters, so 3bits will be enough for the characters (2^3 =8). We can put: e=001, a=010, c=100, d=011, b=110 But I don't see how to use their frequency (we don't have the value of it, they just gave a "scale" of their frequency)

# Answer
> 0 votes
Just so you get an idea: You could encode f letters by assigning 00 = a, 01 = b, 10 = c, 110 = d, 111 = e. If their frequencies are a ≥ b ≥ c ≥ d ≥ e, then this will be the optimal fixed-width encoding unless a is very common. If a was very common then you would assign 0 = a and find a good way to encode b, c, d and e. Anyway, this would save one bit every time a letter a, b or c is used.

If you decided to encode 0 = a, 100 = b, 101 = c, 110 = d, 111 = e, that would save one bit compared to the first encoding every time you encode an a, and lose one bit every time you encode b or c. So this is a better encoding if the freq (a) \> freq (b) + freq (c). One more possibility is 0 = a, 10 = b, 110 = c, 1110 = d, 1111 = e; you'd have to calculate the average number of bits for this case as well.

(And google for Huffman to find this method fully worked out).

Yes, Huffman coding would take the two codes with the lowest frequences and combine them into one. For example, d and e are combined into one code de, and you follow for "de" by 0 to get a d, and you follow the code for "de" by 1 to get an e. And then you pick again the two codes with the lowest frequencies. Which would be either b and c, or c and "de". And so on.

# Answer
> 2 votes
If you look at the algorithm for creating Huffman trees/codes, you will see that while it uses frequencies, any weight works. You can always rescale (by dividing by the sum of all weights), if you wish.

If your problem does not contain any weights but only a relative order, you can not build a Huffman tree; you don't know where in the order the inner nodes you create go. Ask your teacher.

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


# Question
Title: Thompson's Construction Algorithm produces a different NFA
My teacher asked me to convert the regular expression $(a | b)^\*$ to an NFA using Thompson's algorithm – well, I'm well aware of how this algorithm works, but since I'm not good at memorising details, I produced a slightly different NFA, and the teacher said it was wrong. Yeah, I know that it's not what the algorithm produces, but I guess it's not wrong either – what do you guys think?

This is the NFA that I produced:

Thompson's algorithm produces an empty transition from state 7 to 2 instead of that from 8 to 1. Is there anything wrong with my construction? If so, could you please show me?

N.B.: The accepting state (8) is not marked because of a difficulty with the drawing tool.

# Answer
> 4 votes
Your construction is correct, in that your FA accepts $(a\mid b)^\*$. In fact, the construction is exactly the one that is used in a popular (and very good) text by Peter Linz. However, your instructor might have objected to the fact that it wasn't the one used in the Thompson paper, which of course it wasn't, as you noted. The upshot is that there are different, equivalent, ways of going from a regular expression to an NFA. As the sage said, "There are many roads to the top of the mountain, grasshopper".

(For instance, one might also propose the 1-state FA for this language, which also would be correct.)

# Answer
> 0 votes
As mentioned earlier, your NFA does accept $(a | b)^\*$ but this does not correspond to the raw output Thompson's algorithm could produce.

Here is what I get:

---
Tags: automata, finite-automata, regular-expressions, simulation
---


# Question
Title: Is there any good way to judge whether the rectangle is inside the point cloud?
How to judge whether a rectangle in the figure is inside the given point cloud? For example, in this figure, the red rectangle is outside the point cloud and the green rectangle is outside the point cloud.

# Answer
The point cloud can define a polygon. After you define a polygon you can use the point inside polygon test on the four corners of the rectangle and see if all the points are inside the polygon.

The point in polygon test.
> 0 votes

---
Tags: algorithms, image-processing, heuristics, graphics
---


# Question
Title: Is Turing Reduction always in context to decidable languages?
According to Wikipedia's article on Turing Reduction

> It can be understood as an algorithm that could be used to solve A if it had available to it a subroutine for solving B.

Does solving mean always halting (accept/reject)? Should B assumed to be decidable language for the sake of proofs ?

# Answer
Absolutely not. In fact, these are most useful when $B$ is undecidable.

Diagonalization was used to show the Halting problem undecidable, but most other problems were shown to be undecidable through a reduction:

1. Suppose we have a subroutine solving $B$
2. Show that we can use that subroutine to solve $A$.
3. If $A$ is undecidable, then we have a contradiction, so we know $B$ must also be undecidable.

That said, the a proper Turing reduction should always halt. It's cheating if you say "I can use $B$ to make a program that either solves $A$ or runs forever". That's not useful in general.

(Although if you used $B$ to find a recognizer for $A$ where $A$ is not recursively-enumerable, you could show that $B$ is not decidable/recursively-enumerable, depending on your initial assumption about $B$.)

If $B$ is decidable, and you reduce $A$ to $B$, all you've done is create an algorithm deciding $A$. Which is useful, but you don't need a formal notion of reduction to do that.
> 3 votes

# Answer
The first point to make is that "solving" here is not a formal term, so it doesn't have a fixed definition. It means – and please forgive the circularity, here – solving the problem in whatever sense we're talking about at the moment. That could be deciding it, semi-deciding it or something else.

With that out of the way, the answer to your main question is "no". It is not necessary for $B$ to be decidable if we want to reduce a language to it. All that we're saying is *if* we could solve $B$, then we could use that to solve $A$.
> 2 votes

# Answer
Yes, $A$ is Turing reducible to $B$ if there is an algorithm that, having a subroutine for solving $B$, halts on any input.

In computability theory we like to think about such algorithms as Oracle Turing Machines. Using a Gödel numbering we can view strings of languages as natural numbers. Therefore we view languages $A, B$ as sets of natural numbers, where $x \in A$ if the string having Gödel number x is in the language. An oracle Turing machine is then a Turing machine with an additional tape, and an additional command that tests whether a number $x$ is on the oracle tape.

A set $A$ is then Turing reducible to $B$, $A\leq\_T B$, if there is an oracle Turing machine $\phi$ such that $$\phi^B= \chi\_A$$ ($\phi^B$ is $\phi$ initialized with $B$ on the oracle tape) where $\chi\_A$ is the characteristic function of $A$, i.e., $\chi\_A(x)=1$ if $x\in A$ and $\chi\_A(x)=0$ otherwise. As $\chi\_A$ is total, $\phi^B$ must halt on every input.
> 2 votes

---
Tags: computability, reductions
---


# Question
Title: Path in directed, weighted, cyclic graph with total distance closest to D?
**Input**: Directed, weighted, cyclic graph *G*. Two distinct vertices in that graph, *A* and *B*, where there exists a path from *A* to *B*. A distance *d*.

**Output**: A path between *A* and *B* with distance closest to *d*. The path need not be a simple path - it can contain repeated edges and vertices.

Which algorithms exist to solve this problem? I'm looking for an optimal solution, but I'm also interested to see if there are any approximation algorithms as well. Efficiency is not a huge concern - I just want to get an idea of the algorithms available.

---

**Bonus question**: are there any algorithms to compute a path from *A* to *B* that visits *every node at least once*, while finding the distance closest to *d*?

# Answer
> 2 votes
As far as I can tell, the first bibliographical reference I'm aware of within the context of *heuristic search* is Lukas Kuhn, Tim Schmidt, Bob Price, Johan de Kleer, Rong Zhou, and Minh Do. *Heuristic search for target-value path problem*. In The First International Symposium on Search Techniques in Artificial Intelligence and Robotics, 2008. Since then, this problem is known as *Target-Value Search*, or TVS for short.

Similar ideas were then continued in another paper published the next year at SoCS (the Symposium on Combinatorial Search) but employing a depth-first search instead: Tim Schmidt, Lukas Kuhn, Bob Price, Johan de Kleer, and Rong Zhou. A depth-first approach to target-value search. In Symposium on Combinatorial Search (SOCS-09), 2009.

Interestingly, the algorithms described in these works solve the problem for graphs with arbitrary edge costs. However, they only perform experiments with tiny graphs (e.g., a few tens of nodes). Another team of researchers proposed a different algorithm for the case of unitary edge costs (ie., where all edge costs are restricted to be the same): Carlos Linares López, Roni Stern, Ariel Felner: Target-Value Search Revisited. IJCAI 2013: 601-607. They performed experiments with much larger graphs (ie., hundreds of thousands of nodes).

In this paper, the authors identified three different variants of the TVS. They originally addressed the case where vertices can be repeated but edges cannot be traversed twice.

That's not the case you are interested in! The specific case of *simple paths* was addressed in a short communication published in SoCS in 2014: Carlos Linares López, Roni Stern, Ariel Felner: Solving the Target-Value Search Problem. SOCS 2014. You will find in this paper the same reduction mentioned by D.W. from the SUBSET SUM PROBLEM to prove NP-hardness.

As mentioned above, however, the last two works are specific to the case where all edge costs are equal to one. All the algorithms mentioned in this response compute optimal solutions and I'm not aware of any approximation algorithms for solving this problem.

Hope this helps,

# Answer
> 2 votes
The problem is NP-hard, by reduction from subset sum (given weights $w\_1,\dots,w\_n$, take a graph with $n$ vertices and two edges from vertex $i$ to vertex $i+1$, one of weight zero and one of weight $w\_i$).

One algorithm is to simply enumerate all paths up to a certain length (say, up to length $2d$, if all edge weights are non-negative). This can be done by enumerating all paths of length $i$; then enumerating all paths of length $i$ by concatenating any path of length $i$ followed by any edge out of the final vertex of that path; and so on, for $i=1,2,3,\dots$ Of course, the algorithm takes exponential time, but it is an algorithm.

# Answer
> -2 votes
I could be wrong but this looks like a classic Dijkstra's algorithm problem. If you aren't familiar with the algorithm you can read more about it at Wikipedia, or you can read about the original variant of the algorithm from this paper written by Dijkstra himself here.

---
Tags: graphs, optimization, weighted-graphs, hamiltonian-path
---


# Question
Title: Checking for $3$-colorability by searching for $K_4$ as a minor
Determining if a graph is $3$-colorable is NP-complete. But this is equivalent, by a resolved case of Hadwiger's Conjecture, to checking if the graph has $K\_4$ as a minor.

Per https://en.wikipedia.org/wiki/Graph\_minor#Algorithms, this can be done in $O(n^3)$ time, where $n$ is the number of vertices, as $K\_4$ has a constant number of vertices. This would seem to be a contradiction (unless $P=NP$)

# Answer
Hadwiger's conjecture states that if a graph is not $(k-1)$-colorable then it has a $K\_k$ minor. Hadwiger himself proved it for $k \leq 4$. Thus, any graph which is not $3$-colorable has a $K\_4$ minor. However, the converse doesn't hold: some graphs having a $K\_4$ minor are $3$-colorable. For example, take $K\_4$ and split each edge into a path of length $2$ edges. The result is bipartite, and so $2$-colorable.
> 5 votes

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


# Question
Title: If you have a Cook reduction in both directions, do you also have a Karp reduction?
If there exists a Cook reduction of a decision problem $\mathcal{P}\_1$ into another decision problem $\mathcal{P}\_2$ and also a Cook reduction of $\mathcal{P}\_2$ into $\mathcal{P}\_1$, then is there also a Karp reduction (a polynomial transformation) between $\mathcal{P}\_1$ and $\mathcal{P}\_2$ (in both directions)?

These are the definitions I use:

> *Cook reduction*
> $\mathcal{P}\_1$ polynomially reduces to $\mathcal{P}\_2$ if there is a polynomial-time oracle algorithm for $\mathcal{P}\_1$ using an oracle for $\mathcal{P}\_2$.
>
> *Karp reduction*
> $\mathcal{P}\_1=(X\_1,Y\_1)$ polynomially transforms to $\mathcal{P}\_2=(X\_2,Y\_2)$ if there is a function $f:X\_1\rightarrow X\_2$ computable in polynomial time such that for all $x\in X\_1$, $x\in Y\_1$ if and only if $f(x)\in X\_2$.

# Answer
> 5 votes
The answer depends on whether you require both of $\mathcal{P}\_1,\mathcal{P}\_2$ to be in NP or not.

## If the problems need not be in NP

Then the answer to your question is "No". There exist problems $\mathcal{P}\_1,\mathcal{P}\_2$ that are Cook-reducible (in both directions) but not Karp-reducible (in either direction)

In particular, consider $\mathcal{P}\_1 = $ HALT (the Halting problem) and $\mathcal{P}\_2 = \overline{\mathcal{P}\_1}$ (its complement). They are Cook-reducible (you just invoke the oracle and complement its answer), but not Karp-reducible.

(Similarly, if $\textsf{NP} \ne \textsf{coNP}$, then the answer is No: take $\mathcal{P}\_1 = $ SAT and $\mathcal{P}\_2 = $ TAUTOLOGY, so that $\mathcal{P}\_1$ is NP-complete and $\mathcal{P}\_2$ is coNP-complete. They're Cook-reducible, but a Karp reduction would prove that $\textsf{NP} = \textsf{coNP}$ via a standard argument.)

## If the question is restricted to require both problems to be in NP

Then it's an open question; no one knows whether the answer is "Yes" or "No". See https://en.wikipedia.org/wiki/NP-completeness#Completeness\_under\_different\_types\_of\_reduction and

---
Tags: complexity-theory, reductions
---


# Question
Title: Algorithm for listing all binary trees of a given height
I've been trying to find an algorithm to list all binary trees of a given height $h$.

Note that I'm not trying to count them: the number of such trees is given in the OEIS (A001699).

All the algorithms that I have been able to see list all binary trees for a given number of nodes. A very inefficient way of solving the problem would proceed by checking all the trees with a number of nodes between $h+1$ and $2^{h+1}-1$, but this is not great at all.

Any pointers or references would be much appreciated.

# Answer
> 2 votes
As hinted at in comments, just follow the recursive structure of binary trees.

We create a function `listbt(h)` that lists all binary trees of exactly height `h`.

```
type BTree = Leaf | Node(BTree, BTree)

def listbt 0 = { [Leaf] }
|   listbt h = {
  result = []
  for T in (listbt h-1) {
    for k in (0..h-1) {
      for t in (listbt k) {
         result += Node(T, t)
         result += Node(t, T) if k < h-1 || t != T
      }
    }
  }
  return result
}

```

Correctness follows with an elementary inductive proof over `h`.

If you memoize the results of `listbt` this is going to be as efficient as it gets; the sheer number of trees and thereby the number of checks `t != T` dominate.

Note that if you employ term sharing (i.e. only link `t` and `T` in `Node(t, T)` but do not copy them) you can reduce the size of the output significantly. That only makes sense if your `BTree` implementation is immutable, though.

# Answer
> -1 votes
My first thought was that this only involves trees built from paths of length h, which are isomorphic to h-bit integers, but those are only a subset of what's needed. However starting with those all that's needed is to fill in each non-full intermediate node with trees that don't reach all the way to the leaf level.

That is: Enumerate the $2^{2^h}-1$ nonempty sets of h-bit integers and convert them into trees. Then for each tree T, for each non-full non-leaf node N (ie having one child only, since it's by definition already on a path to at least one leaf), attach all possible subtrees that don't reach the leaf level (height \< height(N)-1, including the empty tree). Then output the cartesian product across all of the N's in T.

My assertion is that this generates all trees and doesn't generate any twice, since the not-reaching-leaf-level condition makes it impossible to start with one T and convert it into another T' with a different leaf of depth h.

---
Tags: algorithms, binary-trees, enumeration
---


# Question
Title: Confusion regarding the Definition of 2 Way Finite State Automata?
Here is a description I read from one of the sources about 2WNFA:

"Unlike ordinary finite automata, a 2DFA needs only a single accept state and a single reject state. We can think of it as halting immediately when it enters one of these two states, although formally it keeps running but remains in the accept or reject state. The machine need not read the entire input before accepting or rejecting. Indeed, it need not ever accept or reject at all, but may loop infinitely without ever entering its accept or reject state."

I am unclear what it means by: "..The machine need not read the entire input before accepting."

For example in the automata M = ({qo, ql, q2, q3, q4, q5}, {1}, δ, qo, {q5}) (δ is transition function, L=Left, R=Right) and the transitions being:

δ(q0, 1) = (q1, R);
δ(q1, 1) = (q2, R); δ(q2, 1) = (q3, L); δ(q3, 1) = (q4, L); δ(q4, 1) = (q5);

Does the above 2WNFA, accept any string (example: "1") as the first 4 transitions can be ignored as they bring the machine back to the 1st character in the input string, thus for the last transition to the final accepting state a single 1 is enough? On other hand I think the language it accepts is empty?

Terribly confused because of the bidirection along with above explanation.

# Answer
> Unlike ordinary finite automata, a 2DFA needs only a single accept state and a single reject state.

Finite automata do not *need* more accepting states. Well, non-deterministic FA don't; just add two final states and appropriate $\varepsilon$-transitions. Deterministic FA, though, *need* multiple final states; above construction doesn't work, and Myhill-Nerode tells us that we indeed get multiple final states for some languages.

> Unlike ordinary finite automata, a 2DFA needs only a single accept state and a single reject state.

If you add rejecting states to finite automata (an easy enough exercise), neither do finite automata. Consider, for instance,

$\qquad L\_0 = \\{ w \mid w\_1 = 0 \\} \cap L$

for any regular $L$. Then, a finite automaton for $L\_0$ can reject immediately if the first symbol is not a $0$.

In summary, I think the authors try to read meaning into arbitrary syntactical differences.

That said, note how 2DFA *need* a rejection state for the stated reason: there is no natural "end of computation".
> 2 votes

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


# Question
Title: How hard is recovering a binary matrix from its check sums?
I am interested in combinatorial (worst-case) one-way functions. I came across this problem which may be related to coding theory problems (I am not an expert in coding theory).

**INPUT**: Two vectors $R\_{n\*1}$ and $C\_{1\*n}$.

**QUESTION**: Is there a binary matrix $A\_{n\*n}$ such that vector $R$ contains the parity check of each row in $A$ and vector $C$ contains the parity check of each column in $A$.

The parity check of a row (or column) is the sum of all bits Mod 2 (XOR operation).

> What is the time complexity of this problem? Is it NP-complete? Is it efficiently solvable? Is this a known problem in coding theory?

Also, it is interesting to know the time-complexity of a variant in which vectors $R$ and $C$ contains the integer sum of the one's in each row and column in $A$.

**EDIT**: It is interesting to note that the Sum problem becomes $NP$-complete if the directed graph is required to be acyclic (see the link in Yuval's answer).

# Answer
## Parity problem

It is clear that $\sum\_i R\_i \equiv \sum\_j C\_j \pmod{2}$ must hold if any solution exists. On the other hand, if this holds then some solution exists. Let $R$ contain $a$ ones, and let $C$ contain $b$ ones. We can assume without loss of generality that $a \geq b$. Arrange the rows and the columns so that $$ \begin{align\*} &(R\_1,C\_1) = \cdots = (R\_{n-a},C\_{n-a}) = (0,0) \\ &(R\_{n-a+1},C\_{n-a+1}) = \cdots = (R\_{n-b},C\_{n-b}) = (1,0) \\ &(R\_{n-b+1},C\_{n-b+1}) = \cdots = (R\_n,C\_n) = (1,1) \end{align\*} $$ Note that there is an even number of occurrences of the second type. We now construct a block diagonal matrix with the following blocks: $$ \begin{pmatrix} 0 \end{pmatrix} \times (n-a), \quad \begin{pmatrix} 1 & 0 \\ 1 & 0 \end{pmatrix} \times (a-b), \quad \begin{pmatrix} 1 \end{pmatrix} \times b $$

# Sum problem

When the actual sums are given, we have the digraph realization problem, which can be solved efficiently.
> 5 votes

---
Tags: complexity-theory, time-complexity
---


# Question
Title: Derandomization of an approximation algorithm for solving a linear system
I was given a HW assignment that asks me the following:

Given a system of $m$ linear equations in variables $x\_1,x\_2,...,x\_n$ over $\mathbb{F\_p}$, find a randomized algorithm that find an assignment for all the $x\_i$ such that the expected number of equations solved are $m/p$. Then do a derandomization that gives an efficient deterministic algorithm that solves at least $m/p$ of the equations.

A randomized algorithm is easy - assign each variable a value uniformly from $\mathbb{F\_p}$, by the principle of deferred decisions each equation is satisfied with a probability at least $1/p$, since there are $m$ equations and by the linearity of the expectation we get the desired result.

I am having difficulty with the second part, I wish to use the method of conditional expectation: choosing an assignment for the first variables then choosing an assignment to the next variable etc', and the expectation at each point is at least $m/p$ so that after $n$ iterations we have assigned all variables and the expected number of satisfied equations **is** the number of satisfied equations. I have seen this method used for derandomization of MAX-CUT.

My problems making adjustments:

1. Unlike MAX-CUT - I can only bound the expected number of solved equations by $m/p$ and not calculate the exact expectancy, this gives me problems when trying to figure out the next best assignment since I can't choose one that maximizes the conditional expectancy
2. Unlike MAX-CUT - Choosing an assignment for some of the variables can determine the value of another variable (e.g choosing $x\_1,x\_2$ when we have $x\_1+x\_2+x\_3=1$)

I have a suggestion, but I can't manage to prove it works: At iteration $k$ choose an assignment for $x\_k$ s.t the number of equations that are false is minimal (that is equations with one free variable that is not assigned a value contradicting the equality such as $x\_j=t$ when we assigned $x\_j$ a different value)

I would appreciate help analyzing my suggested algorithm or a point in the right direction

# Answer
In your case the method of conditional expectations devolves to a greedy algorithm. At each stage, you choose the value for the variable under consideration that satisfies the most equations (if any; otherwise choose an arbitrary value), and substitute this value.

Why does this work? Suppose that at the beginning of stage $i$, you have $N\_i$ remaining equations (i.e., ones in which there is at least one remaining variable with non-zero coefficient). The greedy choice satisfies at least $(N\_i-N\_{i+1})/p$ equations. In total, the number of equations you satisfy is at least $$ \sum\_{i=1}^n \frac{N\_i-N\_{i+1}}{p} = \frac{N\_1 - N\_{n+1}}{p} = \frac{N}{p}, $$ where $N$ is the total number of equations, and $N\_{n+1} = 0$ is the number of remaining equations at the end of the algorithm.
> 2 votes

---
Tags: algorithms, randomized-algorithms, linear-algebra
---


# Question
Title: Why are these features missing in modern day general purpose computer languages?
I often wondered why languages like c do not have simple syntactical allowances that would help readability. For example, large numbers such as 1073741823 can be hard to read so my opinion is modern day languages should allow delimiters such as , (comma) so you can write a statement such as x = 1,073,741,823. That is MUCH more readable. Perhaps you can do this in some languages using #DEFINE but it seems like such a simple thing should be native to the language.

Another feature I would like to see in general purpose languages are huge ints. That is, integers that are not limited to 16 or 32 or even 64 bits but some very large number of bits, perhaps 256. This would help with simulation of certain games with very large state spaces. Why burden the programmer with such tasks? I, as a user of a programming language, would expect some complexity to be hidden from me and handled by the compiler itself. Just like when we drive our cars, many people don't understand the inner workings of it but they don't need to.

It would also be nice if the math library had basic combinatorial functions such as choose(52,5) and the language also had direct syntax for factorial such as x = 52!/47!. That is "syntactical sugar" compared to Factorial(52)/Factorial(47).

Also when I was in college I proposed a computer language that would optionally use indenting to limit the scope of statement like IF, CASE, LOOP, FOR.... For example:

```
if cardcount < 52
  ProcessNextCard()
else
  deckfinished = TRUE
next statement goes here and is not part of if statement cuz it is not indented.

```

Here is an even better example:

```
for c1 = 1 to 50
 for c2 = (c1+1) to 51
  for c3 = (c2+1) to 52
   ProcessHand()
nextstatement goes here but it is not part of any loop.

```

Ideally the programming environment would show indentation brackets to confirm the alignment and have a special printing program that does the same.

Of course if there are a lot of lines of code in the body of the if statement then it would be better (clearer) to insert the endif, ifend or fi "missing" part of the if statement. The compiler should allow both options. Forcing the programmer to indent is a good way to teach new programmers good programming practice and to penalize lazy programmers.

Also how about a language that self profiles (or at least assists) using a special directive? For example, if someone wrote a file compressor program and wanted to know where it was eating up most of the time and in what proportion, it would be nice if the language automatically inserted some markers or at least allowed the programmer to insert them easily and then the profiler would tell the programmer what proportion of the runtime was between each set of markers (such as A-A, B-B, C-C... Z-Z).

I could go on and on with a wish list of enhanced features to make programming easier but I will just stick with these few for now.

So my main question is why are many of these features lacking in modern day languages or are they actually there?

# Answer
You are asking a lot of questions, here are quick answers on some of them:

1. Syntactic sugar for integer literals: in a language like C, commas already have a function (they are an operator on their own), so there would be an ambiguity. Other languages allow them. In many countries in Europe, the roles of , and . are switched, and this highlights the fact that this type of issue is best handled by a preprocessor.
2. Large integers: operations on larger integers are slower than ones on smaller integers, so it makes sense to have different types in many circumstances. Libraries typically provide support for large integers even if the language doesn't natively support them.
3. Math library lacking support for your favorite functions: everybody's favorite functions are different. There is probably a library that supports yours, and otherwise you can write one. Computer algebra systems tend to support all mathematical functions you will ever want to use.
4. Indentation: you might like indentation, others might not. Generally speaking, the rule in most programming languages (other than Python and perhaps a few others) is that whitespace shouldn't matter. There are many reasons for that, including (historically) macro expansions (or INCLUDEs), and differing indentation styles. If you want to enforce your type of conventions, use a preprocessor.
5. Built-in profiling: many C compilers already have this feature, and it is part of the tool chain in most widely used programming languages. There is no need for explicit support in language syntax.

In general, one can think of many "improvements" and features for programming languages. That is one of the reasons why there are so many of them. Different compilers might actually implement some of these, perhaps optionally. To answer your general question, why your favorite feature isn't part of your favorite language, the answer is twofold. First, there are many potential features, and programming languages cannot implement all of them (see for example the recent C++ standards, adding lots of features and making the language ever harder to learn). Second, there are some performance issues that you might be ignoring.
> 1 votes

---
Tags: programming-languages
---


# Question
Title: What is inapproximability of NP-hard problems?
Recently I have come across a paper which talks of "(1+ε)-inapproximability" and of "logarithmic approximation".

While I have a basic knowledge of computational complexity (I more or less know what it means to be in P, NP, NP-hard and so on), I tried to study some basic texts on approximability but I'm not sure I really get what this inapproximability is. Could you enlighten me on what the above expressions mean?

If you want to know the paper I was referring to, it was DasGupta & Desai. «On the complexity of Newmanʼs community finding approach for biological and social networks». Journal of Computer and System Sciences 79, n. 1 (2013): 50–67. The found inapproximability is a property of the modularity measure (the so-called Q) related to the Newman-Girvan algorithm for finding community structure in networks, a measure whose maximization has been proved NP-complete by Brandes, Delling, Gaertler, Gorke, Hoefer, Nikoloski, and Wagner in 2008. Thank you in advance.

# Answer
Optimization problems come in two flavors: minimization and maximization. For definiteness, in this answer we consider minimization problems; for maximization problems the situation is completely analogous.

Generally speaking, when we say that a minimization problem $\Pi$ is $c$-hard to approximate, we mean the following:

> If there is a polynomial time approximation algorithm for $\Pi$ whose approximation ratio is better than $c$ then \[something bad happens\].

Usually the "something bad" is $\mathsf{P} = \mathsf{NP}$, but sometimes we can only prove that, say $\mathsf{NP} \subseteq \mathsf{DTime}(n^{\log \log n})$ (that is, SAT can be solved in time $O(n^{ \log \log n})$). Since we believe that the "something bad" is wrong, it follows that probably no polynomial time approximation algorithm for $\Pi$ has an approximation ratio better than $c$.

Why this form of result? If $\mathsf{P} = \mathsf{NP}$, then all NP optimization problems (that is, all optimization problems whose decision version is in NP) can be solved in polynomial time. Therefore in order to prove that a certain problem cannot be approximated well we need to make some complexity assumption such as $\mathsf{P} \neq \mathsf{NP}$.

The best one can hope for is to prove that is an NP-hard to approximate $\Pi$ better than $c$. What this means is that for each $\epsilon \> 0$ there is a polynomial reduction $A$ from SAT to $\Pi$ with the following properties:

1. If the input formula $\varphi$ is satisfiable than the optimal value of $A(\varphi)$ is at most $x$, for some value $x$ which the reduction explicitly calculates (in polynomial time).
2. If $\varphi$ is not satisfiable than the optimal value of $A(\varphi)$ is more than $(c+\epsilon)x$.

In particular, any polynomial time $(c+\epsilon)$-approximation algorithm would be able to distinguish the two cases, and thus to solve SAT in polynomial time.

Technically, what we have described is known as a *promise problem*: decide whether an instance of $\Pi$ has value at most $x$ or more than $(c+\epsilon)x$; or stated differently, find the optimal value of an instance of $\Pi$ (or at least distinguish the two cases) under the promise that the optimal value is either at most $x$ or more than $(c+\epsilon)x$.

In some cases we are able to prove that a certain problem $\Pi$ is $c$-hard to approximate, and also show that a polynomial time $c$-approximation algorithm exists. In this case we say that the inapproximability threshold of $\Pi$ is $c$. For example, Håstad shows that the threshold of inapproximability for 3SAT is $7/8$.

Our definition above of $c$-inapproximability states that in polynomial time it is impossible to approximate a certain problem better than $c$, but allows an approximation ratio of $c$. Sometimes we also want to disallow an approximation ratio of $c$. The terminology doesn't reflect this fine point, and formal statements of theorems have to be consulted.

Finally, $(1+\epsilon)$-inapproximability means that (under some complexity assumptions) it is impossible (in polynomial time) to approximate the problem to within $1+\epsilon$ for some $\epsilon \> 0$ (in terms of our notation above, the problem is $1$-hard to approximate). We also say that the problem is *APX-hard*.

Logarithmic inapproximability means that it is impossible to approximate the problem to within $O(\log n)$, where $n$ is some natural parameter inherent in the problem, usually the number of vertices in the input graph.
> 11 votes

# Answer
There are some NP-complete problems where you can get good approximations to an optimal solution, and some where you can't. Take colouring of a planar graph: Deciding whether a planar graph can be coloured in 3 colours is NP complete. On the other hand, every planar graph can be coloured in 4 colours. But there is no graph that would take say 3.01 colours. So if you try to colour a 3 colourable graph, you either solve the problem, or your solution is at least 33.3333% worse than the optimal solution. No (1 + eps) approximation if eps \< 1/3.

Other problems allow arbitrarily good approximations that get harder to find as you try to improve the approximation.
> 0 votes

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


# Question
Title: Cyclic deterministic finite automata, exponential advantage over DFA
Let's define Cyclic deterministic finite automata (CDFA) as a DFA that treats its input a bit differently -- namely, CDFA when given input $w$, firstly transforms its input into $w@$, where $@$ is a special character outside the alphabet that acts as a loop, gluing end of $w$ to the beginning of $w$. So, when CDFA reads $@$ and is currently in state $q$, it then reads whole input (i.e. $w@$) again (so CDFA acts as if it was reading infinite word $w@w@w@w@\ldots$), starting this time from the state $q$. CDFA accepts iff during reading symbol $@$ it is in accepting state.

How to show the following:

> For every $n$ natural, there is language $L\_n$ and CDFA $C\_n$ such that $C\_n$ has less than $3n$ states, but every DFA recognizing $L\_n$ has at least $2^n$ states.

?

I tried firstly to find some regular language that I know requires approximately $2^n$ states, but the only candidate that springs to my mind is

> $L = \\{w \in \\{0,1\\}^{\star} : \text{n-th symbol counting from the end is 0}\\}$

However, I'm not sure whether there exists CDFA having less than $3n$ states. To be honest, I have no idea why it is $3n$ and not other $kn$.

# Answer
> 6 votes
Let $\Sigma$ be an alphabet of size $n$, and consider the language $L\_n$ of all words over $\Sigma$ which contain all letters of the alphabet. It is well-known that the minimal DFA for $L\_n$ contains $2^n$ states. On the other hand, $L\_n$ is accepted by a CDFA with $n+1$ states.

# Answer
> 4 votes
Hint: Try

$$L = \\{w \in \\{0,1\\}^{\star} : \text{n-th symbol counting from the end is 0, and }|w| \in S\\}$$

for some set $S$ that you choose to enable you to solve the problem. Can you think of any set $S$ that would make it easy to find a small CDFA for $L$?

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


# Question
Title: Difference between a turing machine and a finite state machine?
I am doing a presentation about Turing machines and I wanted to give some background on FSM's before introducing Turing Machines. Problem is, I really don't know what is VERY different from one another.

Here's what I know it's different:

> FSM has sequential states depending on the corresponding condition met while Turing machines operate on infinite "Tape" with a head which reads and writes.
>
> There's more room for error in FSM's since we can easily fall on a non-ending state, while it's not so much for Turing machines since we can go back and change things.

But other than that, I don't know a whole lot more differences which make Turing machines better than FSM's.

Can you please help me?

# Answer
The major distinction between how DFAs (Deterministic Finite Automaton) and TMs work is in terms of how they use memory.

Intuitively, DFAs have no "scratch" memory at all; the configuration of a DFA is entirely accounted for by the state in which it currently finds itself, and its current progress in reading the input.

Intuitively, TMs have a "scratch" memory in the form of tape; the configuration of a TM consists both of its current state and the current contents of the tape, which the TM may change as it executes.

A DFA may be thought of as a TM that neither changes any tape symbols nor moves the head to the left. These restrictions make it impossible to recognize certain languages which can be accepted by TMs.

Note that I use the term "DFA" rather than "FSM", since, technically, I'd consider a TM to be a finite-state machine, since TMs by definition have a finite number of states. The difference between DFAs and TMs is in the number of configurations, which is the same as the number of states for a DFA, but is infinitely great for a TM.
> 37 votes

# Answer
Turing Machines describe a much larger class of languages, the class of recursively enumerable languages. Finite state machines describe the class of regular languages.

Finite state machines have no "memory", it is limited by its states.

A finite-state machine is a restricted Turing machine where the head can only perform "read" operations, and always moves from left to right.

Take this language as an example:

$$ L = \\{ a^ib^i | \ i\>= 0 \\} $$

Because finite states machines are limited in the sense that they have no memory, a FSM that accepts L can't be constructed.

To summarize:

Finite state machines describe a small class of languages where no memory is needed.

Turing Machines are the mathematical description of a computer and accept a much larger class of languages than FSMs do.

Turing Machines have has more computational power than FSM. There are tasks which no FSM can do, but which Turing Machines can do.
> 25 votes

# Answer
I had the same doubt and I saw two very enlightning videos and one explanation on Quora as follows:

> A finite state machine is just a set of states and transitions. The only memory it has is what state it is in. Thus, the number of memory states is... finite.
>
> A Turing machine is a finite state machine plus a tape memory. Each transition may be accompanied by an operation on the tape (move, read, write).

I have understood from it that a turing machine uses/has a a finite state machine as part of its operating procedure, plus adding some editable memory to it.

Please watch also those two videos, they are enlightning!

https://youtu.be/gJQTFhkhwPA

https://youtu.be/E3keLeMwfHY
> 4 votes

# Answer
As far as I understand the differences between (standard model) Turing and (standard model) Mealy Machines:

* Turing Machines read and write on the same tape *vs.* Mealy Machines read on one input tape and write on another output tape
* Turing Machines can change the "tape direction" (proceed leftwards or rightwards \[or halt\]) *vs.* Mealy Machines can only proceed rightwards (thats why there is no direction set {L,R,H} in the transition function of the Mealy Machine \[it is implicitly {R}, which means no choice at all\])
* Turing Machines can halt on any tape cell *vs.* Mealy Machines read the complete input and then halt accepting or rejecting it
> 3 votes

# Answer
A Turing machine can store, as part of the tape, things it want to remember.
> -3 votes

---
Tags: terminology, turing-machines, finite-automata, machine-models
---


# Question
Title: Question on Virtual memory and Physical memory
This is the question where I'm stuck: With a 32-bit virtual address, 4 KB pages(12 offset bits), and 4 bytes per page table entry, we can compute the total page table size:

Number of page table entries = 2^(32-12) = 2^20 Size of page table is 2^20 * 2 = 4MB

I understand this, but what I don't get is that each page table entry is of 4 bytes which is 32 bits. That would make the Physical address= 32+ 12 (offset bits)= 44 bits. Wouldn't it?

I've read and understood the point that Virtual Memory size should be bigger than Physical address because that's when the Virtual memory can hold more memory value (Main memory+Disk, though virtually) than the physical address. Am I right?

Also, I've found a block diagram showing all virtual addresses pointing to physical through a page table, and from there they are mapped to main memory and disk address; mapped to disk if valid bit is 0 or else mapped to main memory.

Let me know if I'm wrong anywhere.

# Answer
The page entry contains other things than the base of the physical page. Typically:

* a present or absent bit (to handle the case where the page is not present in the memory: is on disk or just does not exist)
* access right: may the process read, write, execute the page
* some kind of use count (to help the OS makes its choice when there is a need page out)

and obviously some bits may be unused or reserved for future usage.

Note that, although in 64-bit system we are in a phase where the virtual address space is bigger than the physical address space, historically on architectures which lived long enough that tends to be followed by a phase where the physical address space is bigger than the virtual one. The additional memory may be visible only by the OS (which will put other processes there), or even made available to user processes with some kind of bank switching (see extended and expanded memory or more recently PAE in x86 world, some other architectures have had similar things)
> 2 votes

# Answer
Each page table entry is 4 bytes, i.e., 32 bits, but not all of those bits may be used. For instance, 20 bits might be used to hold a physical frame (top 20 bits of physical address) and the other 12 bits might be unused or used for other things (storing permissions, reserved for future use, etc.). If only 20 bits are used, then physical addresses would be 20+12 = 32 bits.

If only 20 bits are used for storing the physical address, why would we take up an entire 4 bytes for the page table entry? Well, it leaves us some bits for other things. And, more importantly, it is useful for a page table entry to be an integer multiple of the word size (4 bytes) long; that way we don't have to deal with unaligned memory accesses.
> 0 votes

---
Tags: operating-systems, virtual-memory, process-scheduling, paging
---


# Question
Title: Numerical ratio between the length of a string and the transited states
If we have a finite automaton that accepts a string,

is there any numerical relationship that always is true like S ≥ |w| or something similar?

Where |w| the length of the string and S the number of transited states (counting multiplicities).

For example, if we have this automata and the string w = 010 :

S = 3 and |w| = 3.

In this case, S = |w|

I'm new in computer science and i was thinking there has to be a rule of that kind but I have not found explicitly in the books that I started on computational theory.

# Answer
> 1 votes
The way you have defined S, we will always have $S \ge |w|$. Why? Because each time the automaton reads one symbol from $w$, it follows one transition and visits the state at the end of that transition, incrementing $S$ by one. In other words, we add one to $S$ for each symbol in $w$. Thus $S$ is at least as large to the number of symbols in $w$. (It might be larger if you follow $\epsilon$-transitions, as they don't consume any symbols in $w$ but do visit a state.)

Try working through a few examples and it should become clearer.

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