# Question
Title: Is this problem NP-Complete (Bin packing with seperable items and penalty)?
The problem is a bit like bin-packing, so I'll describe it with similar naming:

* You have $N$ bins, with the same size, $V$, where $V$ is a positive integer
* This problem has items, and also "pieces" of items: each item is considered a piece, and each piece must always have a "valid size": size must be a positive integer
* You have a set, $S\_1$, of items that must all be placed into bins, but can be seperated into "pieces" of any valid sizes (ie. the sum of the sizes of the pieces of an item must always equal the original size of the item)
* You have a second set, $S\_2$, with non-seperable items of all the same size, $F$, where the cardinality of this set is sufficiently large / unbounded
* If you place any piece from $S\_1$ into a bin you must also place exactly one item from $S\_2$ into the same bin

Given an instance is it possible to place all elements from $S\_1$ into the bins without exceeding the capacity of the bins?

More simply put: Is bin-packing still NP-Complete if you allow for items to be separated into pieces, but there is a "penalty" for having more pieces in each bin, where you're forced to place a "filler" between each piece in a bin?

I've considered trying to reduce from bin-packing, scheduling, 3-partition, 3-col, 3-SAT, TSP, but I can't think of a way to do it. Also, in trying to solve the problem in poly time. I can only think of approximation algorithms such as greedily placing the largest item in the bin with the largest remaining capacity.

Any answers or observations on this would be very appreciated.

# Answer
We can reduce from 3-Partition. In 3-Partition instance we have:

* A set, $S = \\{ s\_1, s\_2, ..., s\_n \\}, n = 3m$, where $m$ in a positive integer
* $B = \sum\_{ i = 1 }^{ n } \frac { s\_i } { 3 }$
* $\frac { B } { 4 } \< s\_k \< \frac { B } { 2 }$, $\forall k \in \\{ 1, ..., n \\}$

Where the problem is whether $S$ be partitioned into m triples such that they all have the same sum, $B$.

To reduce from my problem, let:

* $N = m$
* $F$ may be set to anything
* $V = B + 3F$
* $S\_1 = S$, ie. the values from the 3-Partition instance become the item sizes in the new problem

In the reduced problem the total space available is:

size of each bin $\times$ number of bins

$ = (B + 3F) m $

$ = Bm + 3mF $ (1)

And the total space that the items will occupy is at least:

Sum of item sizes from $S\_1 +$ number of pieces, $p$, from items $S\_1 \times$ size of items in $S\_2$

$ = Bm + pF $ (2)

We know that:

$ p \geq n = 3m $ (3)

and

total space occupied $\leq$ total space available:

(1),(2) $\Rightarrow Bm + pF \leq Bm + 3mF $

$\Rightarrow p \leq 3m $

(3) $\Rightarrow p = 3m $

Implies that for the reduced problem to be satisfiable then all the available bin space is occupied by the items, and that it's not possible to separate any of the items from $S\_1$ into smaller pieces. (4)

It's clear now that this is equivalent to the 3-partition problem, but I've shown it below:

If a 3-partition problem is satisfiable then there exists corresponding triplets in the reduced problem that can be placed into each of the separate bins with exactly $3F$ remaining in each to allow for the required items from $S\_2$. Hence 3-partition $\Rightarrow$ reduced problem. (5)

Because $\frac {B}{4} \< s\_k$ from the original 3-particiation problem, and item sizes in $S\_1$ correspond to the values in $S$ (from 3-partition), we know that if we place more than 3 items in a bin that we exceed the capacity of the bin:

$s\_{1,k} \> \frac {B}{4}$

If we place $x$ items into a bin, where $s\_{min}$ is the size of the smallest item:

total size of bin used for $x$ items $ = x ( s\_{min} + F )$ (6)

Because $\frac {B}{4} \< s\_k$ from the original 3-particiation problem, and item sizes in $S\_1$ correspond to the values in $S$ (from 3-partition):

$ s\_{min} \> \frac {B}{4} $ (7)

(5), (6) $ \Rightarrow$ total size of bin used for $x$ items $ \> x ( \frac {B}{4} + F )$

$\Rightarrow$ total size of bin used for $x$ items $\>$ total capacity of bins $ = B + 3F $, $ \forall x \> 3 $

$\Rightarrow$ A satisfiable solution to the reduced problem has no more than 3 items in any bin. (8)

Likewise, because $s\_k \< \frac {B}{2}$ from the original 3-particiation problem:

$ s\_{max} \< \frac {B}{2} $

$ \Rightarrow$ total size of bin used for $x$ items $ \< x ( \frac {B}{2} + F )$

$\Rightarrow$ total size of bin used for $x$ items $\<$ total capacity of bins $ = B + 3F $, $ \forall x \< 3 $

(4) $\Rightarrow$ A satisfiable solution to the reduced problem has no fewer than 3 items in any bin. (9)

(8), (9) $\Rightarrow$ A satisfiable solution to the reduced problem has exactly 3 items in each bin. (10)

If any reduced problem is satisfiable: We know from (4) that the items cannot be separated; we know from (10) that each bin contains exactly 3 items.

$\Rightarrow$ The triples from each bin (items from $S\_1$) have sizes that sum to $B$, and that the sizes for each item in $S\_1$ have a one-to-one correspondence to the values in the set $S$. Therefore there is a partition of the $S$ set into triples, where each of the triples sums to $B$. Hence reduced problem $\Rightarrow$ corresponding 3-partition problem. (11)

So long as we accept that the problem from the question is in NP (I'm not going to prove this!) (5), (11) $\Rightarrow$ the problem from the question is in NP-Complete.
> 0 votes

---
Tags: algorithms, np-complete, reductions
---


# Question
Title: Is Carry Look-Ahead adder used in modern ALUs?
I recently came across **carry look-ahead adder**(CLA) in *David and Sarah Harris's book*(Digital Design and Computer Architecture). The circuitry for a 64 bit number (standard integer size in C) is probably huge and gets very complicated.The generate function has just too many gates.

My question is: *are CLAs used in current processors* such as the Intel i3 or in similar series? Also, *are there any better implementations of carry adders?*

I am aware of the fact that older processors like the Intel 8008 and the kind did use a CLA.

# Answer
> 1 votes
“Huge and complicated” is no problem, as long as it is fast. It isn’t.

A good choice seems to be a conditional sum adder (CSA) which has a total delay of O(log n) gates. Log n is nice for 64 bit adders.

---
Tags: computer-architecture
---


# Question
Title: Why is Boolean satisfiability such a rare case?
In the space of all K-sat formulas, True and False should have an equal set size. For every un-Satisfiable formula (F), there will an F' (or F-prime) which will be Satisfiable by definition. I cannot get my head around this.

Edit: Let me put it this way: I have constructed a circuit based on a Boolean formula, it is not Satisfiable, now I add one NOT-gate just before the output of the circuit. Does it make sense?

# Answer
Your trick doesn't really work. There are several issues.

First, your trick shows that for every unsatisfiable circuit of size $n$, there exists a satisfiable circuit of size $n+1$. But that doesn't tell you anything about the relationship between the number of unsatisfiable circuits of size $n$ vs the number of satisfiable circuits of size $n$. And, in general, there are *way more* circuits of size $n+1$ than circuits of size $n$, and most circuits are satisfiable, so the mapping you've found doesn't prove what you want it to prove. To prove what you're trying to prove, you'd need to find a bijection between unsatisfiable circuits of size $n$ and satisfiable circuits of size $n$ (not $n+1$); no such bijection exists.

Second, the mapping you describe isn't a bijection. Consider for example the circuit $\phi(x) = x$. This is satisfiable. Slapping a "not" in front if it, to get $\phi'(x) = \neg x$, yields *another* circuit that is also satisfiable. Many circuits are both satisfiable (there exists an assignment that makes $\phi$ true) and their-complement-is-satisfiable (there exists a different assignment that makes $\phi$ false). So negating an unsatisfiable circuit makes it satisfiable, but negating a satisfiable circuit doesn't necessarily make it unsatisfiable.

Finally, there's the distinction between circuits vs formulas, as David Richerby explains. If you negate the output of a CNF formula, the result isn't a CNF formula.
> 5 votes

# Answer
The sets of satisfiable and unsatisfiable formulas *are* the same size: both are countably infinite. However, that doesn't imply that there's any particular relationship between the number of satisfiable and unsatisfiable formulas of length $n$. For example, considering the natural numbers:

* There are countably many odd numbers and countably many even numbers. Asymptotically, half the numbers between $0$ and $n$ are odd.
* There are countably many multiples of seven and countably many non-multiples of seven. Asymptotically, only one seventh of the numbers between $0$ and $n$ are multiples of seven.
* There are countably many perfect squares and countably many non-squares. Asymptotically, the fraction of perfect squares in $\\{0, \dots, n\\}$ is zero.

Your trick of negating a satisfying formula to get an unsatisfiable one has two problems:

1. The negation of a tautology is unsatisfiable, but most satisfiable formulas are not tautologies. All you can say about the negation of a satisfiable formula is that it's falsifiable (has at least one truth assignment that makes it false); that's not the same thing as being unsatisfiable (*every* truth assignment makes it false).
2. $k$-SAT demands that the formula is in CNF. If you just slap a "not" sign on the front of a CNF, the result isn't a CNF any more, and converting it back to CNF can make the formula exponentially longer.
> 4 votes

---
Tags: complexity-theory, satisfiability, boolean-algebra
---


title: Prove that the language is not regular

text:
# Question
Title: Prove that the language is not regular
Prove that the following language $Σ = \\{1\\}$ is not regular. $L$ = $\\{w | |w| = k$, where $k$ is a prime number}.

How should one go about proving this? Should I use pumping lemma for this?

# Answer
We use the pumping lemma for regular languages.

$w \in L$, $|w| = n$, and $n$ is prime.

according to the lemma, $w$ can distribute to $xyz$ s.t:

$\bullet y \neq \epsilon $

$\bullet |xy| \< n$

$\bullet$ for any $i \geq 0$ $ xy^iz \in L$

Now, let us denote $|y| = k$.

Now we only need to think of an $i$, where $|xy^iz|$ is not prime.

let's choose $ i = n$.

$|xy^{i+1}z| = n+ik = n+kn= (k+1)n$

since $(k+1)n$ is not prime (divides by $k+1$), we reached a contradiction and we can conclude $L$ is not regular.
> 1 votes

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


title: Algorithm to distribute items "evenly"

text:
# Question
Title: Algorithm to distribute items "evenly"
I'm searching for an algorithm to distribute values from a list so that the resulting list is as "balanced" or "evenly distributed" as possible (in quotes because I'm not sure these are the best ways to describe it... later I'll provide a way to measure if a result is better than other).

So, for the list:

```
[1, 1, 2, 2, 3, 3]

```

One of the best results, after re-distributing the values, is:

```
[1, 2, 3, 1, 2, 3]

```

There may be other results as good as this one, and of course this gets more complicated with a less uniform set of values.

This is how to measure if a result is better than other:

1. Count the distances between each item and the next item with the same value.
2. Calculate the standard deviation for that set of distances. A lower dispersion means a better result.

Observations:

* When calculating a distance and the end of the list is reached without finding an item with the same value, we go back to the beginning of the list. So, at most, the same item will be found and the distance for that item will be the length of the list. This means that the list is *cyclic*;
* A typical list has ~50 items with ~15 different values in varied quantities.

So:

* For the result `[1, 2, 3, 1, 2, 3]`, the distances are `[3, 3, 3, 3, 3, 3]`, and the standard deviation is `0`;
* For the result `[1, 1, 2, 2, 3, 3]`, the distances are `[1, 5, 1, 5, 1, 5]`, and the standard deviation is `2`;
* Which makes the first result better than the second (lower deviation is better).

Given these definitions, I ask for a clue of which algorithms or strategies should I search for.

# Answer
I ran across this question while researching a similar problem: optimum additions of liquids to reduce stratification. It seems like my solution would be applicable to your situation, as well.

If you want to mix liquids A, B, and C in the proportion 30,20,10 (that is, 30 units of A, 20 units of B, and 10 units of C), you end up with stratification if you add all the A, then all the B, and then all the C. You're better off mixing smaller units. For example, do single-unit additions in the sequence \[A,B,A,C,B,A\]. That will prevent stratification altogether.

The way I found to do it is to treat it as a kind of merge, using a priority queue. If I create a structure to describe the additions:

```
MergeItem
    Item, Count, Frequency, Priority

```

The Frequency is expressed as "one every N". So A, which is added three out of six times, has a frequency of 2 (6/3).

And initialize a heap that initially contains:

```
(A, 3, 2, 2)
(B, 2, 3, 3)
(C, 1, 6, 6)

```

Now, I remove the first item from the heap and output it. Then reduce its count by 1 and increase Priority by Frequency and add it back to the heap. The resulting heap is:

```
(B, 2, 3, 0)
(A, 2, 2, 4)
(C, 1, 6, 6)

```

Next, remove B from the heap, output and update it, then add back to the heap:

```
(A, 2, 2, 4)
(C, 1, 6, 6)
(B, 1, 3, 6)

```

If I continue in that fashion, I get the desired mixture. I use a custom comparer to ensure that when equal Priority items are inserted into the heap, the one with the highest Frequency value (i.e. the least frequent) is ordered first.

I wrote a more complete description of the problem and its solution on my blog, and presented some working C# code that illustrates it. See Evenly distributing items in a list.

## Update after comments

I do think my problem is similar to the OP's problem, and therefore that my solution is potentially useful. I apologize for not framing my answer more in the terms of the OP's question.

The first objection, that my solution is using A, B, and C rather than 0, 1, and 2, is easily remedied. It's simply a matter of nomenclature. I find it easier and less confusing to think about and say "two A's" rather than "two 1's". But for purposes of this discussion I have modified my outputs below to use the OP's nomenclature.

Of course my problem deals with the concept of distance. If you want to "spread things out evenly," distance is implied. But, again, it was my failing for not adequately showing how my problem is similar to the OP's problem.

I ran a few tests with the two examples that the OP provided. That is:

```
[1,1,2,2,3,3]  // which I converted to [0,0,1,1,2,2]
[0,0,0,0,1,1,1,2,2,3]

```

In my nomenclature those are expressed as \[2,2,2\] and \[4,3,2,1\], respectively. That is, in the last example, "4 items of type 0, 3 items of type 1, 2 items of type 2, and 1 item of type 3."

I ran my test program (as described immediately below), and have posted my results. Absent input from the OP, I can't say if my results are similar to, worse than, or better than his. Nor can I compare my results to anybody else's results because nobody else has posted any.

I can say, however, that the algorithm provides a good solution to *my* problem of eliminating stratification when mixing liquids. And it *looks like* it provides a reasonable solution to the OP's problem.

For the results shown below, I used the algorithm that I detailed in my blog entry, with the initial priority set to `Frequency/2`, and the heap comparer modified to favor the more frequent item. The modified code is shown here, with the modified lines commented.

```
private class HeapItem : IComparable<HeapItem>
{
    public int ItemIndex { get; private set; }
    public int Count { get; set; }
    public double Frequency { get; private set; }
    public double Priority { get; set; }

    public HeapItem(int itemIndex, int count, int totalItems)
    {
        ItemIndex = itemIndex;
        Count = count;
        Frequency = (double)totalItems / Count;
        // ** Modified the initial priority setting.
        Priority = Frequency/2;
    }

    public int CompareTo(HeapItem other)
    {
        if (other == null) return 1;
        var rslt = Priority.CompareTo(other.Priority);
        if (rslt == 0)
        {
            // ** Modified to favor the more frequent item.
            rslt = Frequency.CompareTo(other.Frequency);
        }
        return rslt;
    }
}

```

Running my test program with the OP's first example, I get:

```
Counts: 2,2,2
Sequence: 1,0,2,1,0,2
Distances for item type 0: 3,3
Stddev = 0
Distances for item type 1: 3,3
Stddev = 0
Distances for item type 2: 3,3
Stddev = 0

```

So my algorithm works for the trivial problem of all counts being equal.

For the second problem that the OP posted, I got:

```
Counts: 4,3,2,1
Sequence: 0,1,2,0,1,3,0,2,1,0
Distances for item type 0: 3,3,3,1
Stddev = 0.866025403784439
Distances for item type 1: 3,4,3
Stddev = 0.471404520791032
Distances for item type 2: 5,5
Stddev = 0
Distances for item type 3: 10
Stddev = 0
Standard dev: 0.866025403784439,0.471404520791032,0,0

```

I don't see an obvious way to improve on that. It could be rearranged to make the distances for item 0 \[2,3,2,3\] or some other arrangement of 2 and 3, but that will change the deviations for items 1 and/or 2. I really don't know what "optimum" is in this situation. Is it better to have a larger deviation on the more frequent or on the less frequent items?

Lacking other problems from the OP, I used his descriptions to make up a few of my own. He said in his post:

> A typical list has ~50 items with ~15 different values in varied quantities.

So my two tests were:

```
[8,7,6,5,5,4,3,3,2,2,2,1,1,1,1]  // 51 items, 15 types
[12,6,5,4,4,3,3,3,2,2,2,1,1]     // 48 items, 13 types

```

And my results:

```
Counts: 8,7,6,5,5,4,3,3,2,2,2,1,1,1,1
Sequence: 0,1,2,3,4,5,7,6,0,1,2,8,9,10,4,3,0,1,5,2,0,1,3,4,6,7,14,11,13,12,0,2,5,1,0,3,4,2,8,10,9,1,0,7,6,5,3,4,2,1,0
Distances for item type 0: 8,8,4,10,4,8,8,1
Stddev = 2.82566363886433
Distances for item type 1: 8,8,4,12,8,8,3
Stddev = 2.76272565797339
Distances for item type 2: 8,9,12,6,11,5
Stddev = 2.5
Distances for item type 3: 12,7,13,11,8
Stddev = 2.31516738055804
Distances for item type 4: 10,9,13,11,8
Stddev = 1.72046505340853
Distances for item type 5: 13,14,13,11
Stddev = 1.08972473588517
Distances for item type 6: 17,20,14
Stddev = 2.44948974278318
Distances for item type 7: 19,18,14
Stddev = 2.16024689946929
Distances for item type 8: 27,24
Stddev = 1.5
Distances for item type 9: 28,23
Stddev = 2.5
Distances for item type 10: 26,25
Stddev = 0.5
Distances for item type 11: 51
Stddev = 0
Distances for item type 12: 51
Stddev = 0
Distances for item type 13: 51
Stddev = 0
Distances for item type 14: 51
Stddev = 0

```

And for the second example:

```
Counts: 12,6,5,4,4,3,3,3,2,2,2,1,1
Sequence: 0,1,2,0,3,4,7,5,6,0,1,8,9,10,0,2,0,3,4,1,0,2,6,7,5,12,11,0,1,0,3,4,2,0,1,10,8,9,0,7,5,6,0,
4,3,2,1,0
Distances for item type 0: 3,6,5,2,4,7,2,4,5,4,5,1
Stddev = 1.68325082306035
Distances for item type 1: 9,9,9,6,12,3
Stddev = 2.82842712474619
Distances for item type 2: 13,6,11,13,5
Stddev = 3.44093010681705
Distances for item type 3: 13,13,14,8
Stddev = 2.34520787991171
Distances for item type 4: 13,13,12,10
Stddev = 1.22474487139159
Distances for item type 5: 17,16,15
Stddev = 0.816496580927726
Distances for item type 6: 14,19,15
Stddev = 2.16024689946929
Distances for item type 7: 17,16,15
Stddev = 0.816496580927726
Distances for item type 8: 25,23
Stddev = 1
Distances for item type 9: 25,23
Stddev = 1
Distances for item type 10: 22,26
Stddev = 2
Distances for item type 11: 48
Stddev = 0
Distances for item type 12: 48
Stddev = 0

```
> 13 votes

# Answer
This "smells" like it might be NP-hard. So, what do you do when you have a NP-hard problem? Throw a heuristic at it, or an approximation algorithm, or use a SAT solver.

In your case, if you don't need the absolute optimal solution, one reasonable starting point might be to try simulated annealing. There is a natural way to take any candidate solution and move it to a nearby candidate solution: randomly pick two items in the list, and swap them. Simulated annealing will iteratively try to improve the solution. You can find lots of resources on simulated annealing, if you're not familiar with it. You can also experiment with other sets of "local moves" that make small changes to a candidate solution, with the hopes of incrementally improving it (i.e., reducing the standard deviation of distances).

If that doesn't work out so well, my second suggestion would be to try throwing this at a SAT solver. Your problem sizes are small enough that this might just work. Start with the decision problem associated with your optimization function: given $t$, is there a solution whose standard deviation is $\le t$ (i.e., where the variance is $\le t^2$)? This can be expressed as a SAT instance. Expressing it as SAT will be messy, but if you use a front-end like STP, it will get a bit easier, as STP has support for integer arithmetic. So, you might have boolean unknowns $x\_{i,j}$, where $x\_{i,j}$ is true if the $i$th element of the array holds the value $j$. Now you can express some constraints that this is a valid permutation of the original input. You can also create some more integer unknowns and add constraints to force them to be equal to the distances between the elements, and then compute the variance of those distances and add a constraint asserting that it must be $\le t^2$. Of course, the worst-case running time of SAT solvers is exponential, so it's possible that SAT solvers might blow up on this problem... but it's also possible that they might be able to handle this problem. It's another technique you could try.

But I would suggest you start with simulated annealing. That's the first thing I would try, because I think it might just work.
> 7 votes

# Answer
## Sketch of a heuristic algorithm

I have no exact solution for this problem. But since Raphael's comment suggests it looks like the partition problem, for which heuristic algorithms have been developed, I will try a heuristic approach. This is only a sketch of a heuristic algorithm.

Let $v$ be the number of values, and let $n$ be the number of elements in the list. We assume without loss of generality that the values are the numbers in $\[1..n\]$. For each value $i$ we note $n\_i$ the number of its occurrences in the list.

We first note that the sum of the distances for all occurrences of a value is $n$. So the sum of all distances for all elements of the list is $vn$. Hence, the average distance for all elements of the list is $vn/n$, i.e., $v$.

Our purpose is to minimize the standard deviation on distances, which amounts to minimizing the sum of the squares of distance deviations, i.e. of differences between $v$ and each distance.

When placing the occurrences of one value, we try to equalize distances, up to integer constraints (and to the fact that slots may be occupied at some point). That is how they contribute the least to the standard deviation. If we are forced to increase a distance, it is always better to increase one that deviates the least. The the optimal distance for a value $i$ is $n/n\_i$. Taking into account integer constraints, $n\mod n\_i$ occurrences should use the integer value just above $n/n\_i$, and the others just below.

That will guide our algorithm.

But first, we note that singleton values (occurring only once) will always have the same associated distance $n$. Hence their placement does not matter and can be ignored by the algorithm. They will just take whatever slots are left available at the end.

Then, since those distances that deviate most have to be the most exact to contribute less to the sum of squares, we try to place first the values that necessarily deviate most, i.e. the values $i$ such that $|n/n\_i -v|$ is greatest.

It may be a value with very many of very few occurrences at first. I think it does not actually make a difference, since the constraints created by occupying slots are in proportion of the number of values well (?) placed.

Thr first value considered can be placed without any constraint. Then The other values must be placed so as to minimize their contribution to the standard deviation, but only in the slots left free by whatever values have been placed before.

The placement of the occurrences of a value in the remaining slots can be done with a dynamic programming algorithm, so as to merge computations that place the same number of values between two positions, keeping only those that have minimal contribution to the standard deviation (i.e. minimum value for the sum of the square of their deviations).

Occasionally, there will be several minimal solutions. In that case you try to preserve some slack by choosing the minimal solution that has the remaing slots most evenly distributed. THis can be computed, for each solution, by computing the standard deviation of the distances between the remaining free slots (with repect to their mean value, not with respect to $v$).

Then you repeat for the next remaining value $j$ such that $|n/n\_j -v|$ is greatest, an so on until all non singleton values are placed.

Then you put the singleton values in the remaining slots.

I believe this should generally give reasonable solution, but I have yet no idea on how to prove it or estimate the gap with an optimal solution.
> 2 votes

# Answer
It looks like I'm very late to the party, but posting in case anyone runs into this again. My solution is similar to @babou's plus. Earlier today, I had a scheduling problem in an embedded system which led me to this thread. I have an implementation specific to my problem in C, but I figured I'd post a more generic solution in Python here (the C version is complicated by the fact that I've restricted myself to a small, fixed size stack and no memory allocations, so I perform the whole algorithm in-place). The anti-aliasing technique used below is something you might use for drawing a line on a screen with 2 bit colour. The algorithm here achieves a lower score (i.e., better) when measured using the sum of standard deviation for the inputs used by Jim Mischel than that particular solution. Run-time for this implementation (assuming a good sorting algorithm): O(m\*n) where m is the number of types of items and n is the total number of items to distribute.

```
def generate(item_counts):
'''item_counts is a list of counts of "types" of items. E.g., [3, 1, 0, 2] represents
   a list containing [1, 1, 1, 2, 4, 4] (3 types of items/distinct values). Generate
   a new list with evenly spaced values.'''
# Sort number of occurrences by decreasing value.
item_counts.sort(reverse=True)
# Count the total elements in the final list.
unplaced = sum(item_counts)
# Create the final list.
placements = [None] * unplaced

# For each type of item, place it into the list item_count times.
for item_type, item_count in enumerate(item_counts):
    # The number of times the item has already been placed
    instance = 0
    # Evenly divide the item amongst the remaining unused spaces, starting with
    # the first unused space encountered.
    # blank_count is the number of unused spaces seen so far and is reset for each
    # item type.
    blank_count = -1
    for position in range(len(placements)):
        if placements[position] is None:
            blank_count += 1
            # Use an anti-aliasing technique to prevent bunching of values.
            if blank_count * item_count // unplaced == instance:
                placements[position] = item_type
                instance += 1
    # Update the count of number of unplaced items.
    unplaced -= item_count

return placements

```

Results for

```
Input counts: 8,7,6,5,5,4,3,3,2,2,2,1,1,1,1
Sum of stddev: 16.8 (vs. 22.3 via Jim Mischel)

Input of counts: 12,6,5,4,4,3,3,3,2,2,2,1,1
Sum of stddev: 18.0 (vs. 19.3 via Jim Mischel)

```

If given inputs of the form specified by @moraes, one can convert it to a form usable by this function in O(n) steps using Big Omega(n * log(n)) bits of memory where n is the number of items (in a list with 255 elements, you won't need more than 255 extra bytes) by keeping a parallel array with the repetition counts. Alternately, one can perform a pair of in-place sorts with O(1) extra memory.

P.S.

```
import numpy
import collections

def evaluate(l):
    '''Given a distribution solution, print the sum of stddevs for each type in the solution.'''
    l2 = l * 2
    distances = [None] * len(l)
    distance_dict = collections.defaultdict(list)
    for i in range(len(l)):
        distances[i] = l2.index(l[i], i + 1) - i
        distance_dict[l[i]].append(l2.index(l[i], i + 1) - i)

    keys = list(distance_dict.keys())
    keys.sort()
    score = 0
    # Calculate standard deviations for individual types.
    for key in keys:
        sc = numpy.std(distance_dict[key])
        score += sc
    print('Stddev sum: ', score)

```

*Edit:* I know this solution does not produce the optimal output by counterexample. An input of `[6, 2, 1]` produces `[0, 1, 0, 0, 2, 0, 0, 1, 0]`; a better solution is `[0, 0, 1, 0, 2, 0, 0, 1, 0]`.
> 1 votes

# Answer
This algorithm works with an array of integers, where each integer represents a different category. It creates separate arrays for each category. For example, if the starting array is \[1, 1, 1, 2, 2, 3\], it will create three arrays, \[3\], \[2, 2\], \[1, 1, 1\].

From there it recursively combines the two smallest arrays (in this example, the \[3\], and \[2,2\]) and spaces the placement of the elements of the smaller array into the second smallest array based mostly on the ratio of the number of occurrences of the larger vs the smaller categories. In this example, we would wind up with \[2,3,2\]. Then it would use this array as the smaller array that will be combined into the next larger array, until there is only one array left.

```
<?php
/**
 *This will separete the source array into separate arrays for each category
 */
function splitArrayByCategory($source) {

    //  index is the category, value is the tally
    $categoryCounts  = array_count_values($source);

    // Sort that list, keep index associations
    asort($categoryCounts);

    // build separate arrays for each category
    // index = order, smaller index = smaller category count
    // value = array of each category
    $separated = array();
    foreach ($categoryCounts as $category => $tally)
        $separated[] = array_fill(0, $tally, $category);

    return $separated;
}

/**
 * Will take the array of arrays generated by splitArrayByCategory, and merge
 * them together so categories are evenly distributed
 */
function mergeCategoryArrays($categoryArray) {

    // How many entries are there, for the smallest & second smallest categories
    $smallerCount = count($categoryArray[0]);
    $largerCount  = count($categoryArray[1]);

    // Used to determine how much space there should be between these two categories
    $space = $largerCount/$smallerCount;

    // Merge the array of the smallest category into the array of the second smallest
    foreach ($categoryArray[0] as $domIndex => $domain) {
        // Where should we splice the value into the second array?
        $location = floor($domIndex*$space+$domIndex+($space/2));
        // actually perform the splice
        array_splice($categoryArray[1], $location, 0, $domain);
    }

    // remove the smallest domain we just spliced into the second smallest
    unset($categoryArray[0]);

    // reset the indexes
    $categoryArray = array_values($categoryArray);

    // If we have more than one index left in the categoryArray (i.e. some things
    // still need to get merged), let's re-run this function,
    if (count($categoryArray)>1)
        $categoryArray = mergeCategoryArrays($categoryArray);

    return $categoryArray;
}

// The sample list we're working with.
// each integer represents a different category
$listSample = [1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,1,2,2,2,2,2,2,2,2,2,2,2,3,3,3,3,3,3,3,3,3,3,3,4,4,4,4,4,4,4,4,4,4,4,4,4,5,5,5,5,6,6,7,7,7,7];

// Split the sample list into separate arrays for each category
$listSplitByCategory = splitArrayByCategory($listSample);

// If there are not at least two categories, what's the point?
if (count($listSplitByCategory) < 2) throw new Exception("You need at least two categories");

// perform the actual distribution of categories.
$listEvenlyDistributed = mergeCategoryArrays($listSplitByCategory)[0];

// Display the array before and after the categories are evenly distributed
for ($i=0; $i<count($listSample); $i++) {
    print $listSample[$i].",";
    print $listEvenlyDistributed[$i]."\n";
}

```
> 1 votes

# Answer
# ANSI C CODE

This code works by imagining a straight line in n dimensional space (where n is the number of categories) passing through the origin with directional vector (v1, v2, ..., vi, ... vn) where vi is the number of items in category i. Starting from the origin the aim is to find the next nearest point to the line. Using the example \[0 0 0 0 0 1 1 1 2 2 2 3\] it produces the result \[0 1 2 0 3 1 0 2 0 1 2 0\]. Using Lungj's example \[0 0 0 0 0 0 1 1 2\] we get \[0 1 0 0 2 0 0 1 0\], which is exactly the same as Lungj's result.

The algorithm is made more efficient by only using integer arithmetic and considering only the deltas between the distances from each point to the line.

#define MAXCATEGORIES 100

int main() { int i = 0; int j = 0; int catsize = 0; int vector\[MAXCATEGORIES\]; int point\[MAXCATEGORIES\]; int categories = 0; int totalitems = 0; int best = 0; long d2 = 0L; long vp = 0L; long v2 = 0L; long delta = 0L; long beta = 0L;

```
printf("Enter the size of each category (enter 0 to finish):\r\n");
do
{
    catsize = 0;
    #ifdef _MSVC_LANG
            scanf_s("%d", &catsize);
    #else
            scanf("%d", &catsize)
    #endif
    if (catsize > 0)
    {
        vector[categories] = catsize;
        totalitems += catsize;
        categories++;
    }
} while (catsize > 0);

for (i = 0; i < categories; i++)
{
    v2 += vector[i] * vector[i];
    point[i] = 0;
}

for (i = 0; i < totalitems; i++)
{
    for (j = 0; j < categories; j++)
    {
        delta = (2 * point[j] + 1)*v2 - (2 * vp + vector[j])*vector[j];
        if (j == 0 || delta < beta)
        {
            best = j;
            beta = delta;
        }
    }
    point[best]++;
    vp += vector[best];
    printf("%c ", best + '0');  // Change '0' to 'A' if you like letters instead
}
return 0;

```

}
> -1 votes

# Answer
my solution:

```
    vc = train['classes'].value_counts()
    vc = dict(sorted(vc.items()))
    df = pd.DataFrame()
    train['col_for_sort'] = 0.0

    i=1
    for k,v in vc.items():
        step = train.shape[0]/v
        indent = train.shape[0]/(v+1)
        df2 = train[train['classes'] == k].reset_index(drop=True)
        for j in range(0, v):
        df2.at[j, 'col_for_sort'] = indent + j*step + 0.0001*i
    df= pd.concat([df2,df])
    i+=1

    train = df.sort_values('col_for_sort', ascending=False).reset_index(drop=True)
    del train['col_for_sort']

```
> -1 votes

---
Tags: algorithms, optimization, sorting, approximation
---


# Question
Title: Proof that a guard digit bound the error of subtraction
I was reading What Every Computer Scientist Should Know About Floating-Point Arithmetic, which is extremely interesting. But I have some troubles understanding the proof of Theorem 9 (page 33).

First a pretty trivial question. When the formula $(15)$ say: $$y - \bar{y} \lt (\beta - 1)(\beta^{-p} + \dots + \beta^{-p-k})$$ Shouldn't it be $\le$ instead of $\lt$, or did I miss something?

More importantly, I do not understand why it say that *if $x-\bar{y} \lt 1$, then $\delta = 0$*. How can there be no rounding error?

It is then said that: $$x - y \ge 1.0 - 0.\overbrace{0 \dots 0}^k\overbrace{\rho \dots \rho}^k \\; \textrm{with} \\; \rho = \beta - 1$$

Why is that so? Can't the difference be arbitrarily small or even $0$? Why would there be as many $\rho$'s as there are $0$'s?

# Answer
*I'll post some elements of answer to my own question from what I understand. Anyone feel free to make a better, less sloppy answer.*

First, there are several versions of this document online. They all have some typographic defects at some point. So when in doubt, better check those 3 versions first.

Second, there's a lot of implicit stuff going on with this first actual proof. So let's clarify some of them.

---

## Reachable bound of $y - \bar{y}$

I think that, **no**, the bound on $y - \bar{y}$ cannot be reached. Let's try to go for the worst case with $k = p+1$. Let's assume $p = 6$ and the radix $\beta = 10$. \begin{align} y & = \overbrace{0.000000}^{k=7}\overbrace{999999}^{p=6} \\ \bar{y} & = \overbrace{0.000000}^{p+1=7} \\ y - \bar{y} & = 0.000000999999 \\ & = 9 \times (10^{-7}+\dots+10^{-12}) \\ & = (\beta - 1)(\beta^{-p-1}+\dots+\beta^{-p-p}) \\ & \lt (\beta - 1)(\beta^{-p-1}+\dots+\beta^{-p-p}+\beta^{-p-(p+1)}) \\ & \lt (\beta - 1)(\beta^{-p-1}+\dots+\beta^{-p-p}+\beta^{-p-k}) \end{align}

I had to add an extra term to the sum (i.e. an extra digit) to get the same formula as the paper. Hence the $=$ got transformed to $\lt$.

This exact bound simplify the second case of the proof. Although a looser and simpler bound $y - \bar{y} \lt \beta^{-p}$ would be enough for the first case when $x - y \ge 1$.

## No rouding error when $x - \bar{y} \lt 1$

The assertion that *if $x - \bar{y} \lt 1$, then $\delta = 0$* seems true. The rounding error $\delta$ is the error we introduce by removing the guard digit to produce the final result. This is sometimes needed because $\bar{y}$ has $p+1$ digits and $x - \bar{y}$ might as well have $p+1$ digits.

For instance: \begin{align} x & = 2.00000 \\ y & = 0.0123456 \\ \bar{y} & = 0.012345 \\ x - \bar{y} & = 1.987655 \end{align} The result has $7$ digits therefore has to be rounded to $6$ digits.

But when $x - \bar{y} \lt 1$ then the result starts with the digit $0$. Meaning that at most only $p$ significant digits remain from the $p+1$ digits used to perform the subtraction. For example: \begin{align} x & = 1.00000 \\ y & = 0.0123456 \\ \bar{y} & = 0.012345 \\ x - \bar{y} & = 0.987655 \end{align} The result $x - \bar{y}$ already has 6 digits. So no rounding error need to be introduced.

However, it is worth noting that this doesn't change anything to the error introduced by truncating $y$ to $\bar{y}$.

## Minimum value of $x - y$

When the paper say that the smallest value $x - y$ can take is: $$1.0 - 0.\overbrace{0 \dots 0}^k\overbrace{\rho \dots \rho}^k$$ there's actually a typo that has been corrected in other documents. What was ment to be written is: $$1.0 - 0.\overbrace{0 \dots 0}^k\overbrace{\rho \dots \rho}^p$$ which make more sens and is the general formula when $k$ is fixed. Maybe a better form could be: \begin{align} x - y & \ge 1.0 - 0.\overbrace{0 \dots 0}^k\overbrace{\rho \dots \rho}^p \\ & \ge 0.\overbrace{\rho \dots \rho}^k\overbrace{0 \dots 0}^{p-1}1 \\ & \gt 0.\overbrace{\rho \dots \rho}^k \end{align}

Which lead naturally to the formula written in the paper.

## Third case: $x - \bar{y} = 1$

And finally, another implicit point of this proof (not asked but worth writing down): why would having both $x - y \lt 1$ and $x - \bar{y} \ge 1$ imply that $x - \bar{y} = 1$?

I think the informal answer would be that since $x$ is a float with $p$ digits, then $x - 1$ is also a float with $p$ or $p - 1$ significant digits (if $x \>= 2$ or $x \< 2$ respectively). Meaning that truncating $y$ to $\bar{y}$ cannot make it less than $x - 1$ since $y \> x - 1$ and $x - 1$ is a candidate value for $\bar{y}$ and is less than $y$.

In other words: $x - y \lt 1$ imply that $x - \bar{y} \le 1$. Therefore, having this and $x - \bar{y} \ge 1$ at the same time imply that $x - \bar{y} = 1$.
> 2 votes

---
Tags: floating-point, numerical-analysis, error-estimation
---


# Question
Title: Solving $T(n)=4T(n/2)-1$ without using the master theorem
How can I solve the following recurrence without using the master theorem?

$T(n)= 4T(n/2)-1$ for $n\>4$ and $T(n)=5$ for $n\le 4$, $n$ is a power of $2$.

# Answer
> 2 votes
The idea is to convert this recurrence to the simpler recurrence $$ S(n) = 4S(n/2). $$ How do we do this? Let $S(n) = T(n) + f(n)$. Since $$ S(n) = T(n) + f(n) = 4T(n/2) - 1 + f(n) = 4S(n/2) - 4f(n/2) - 1 + f(n), $$ we need that $$ f(n) = 4f(n/2) + 1. $$ Luckily, $f(n) = -1/3$ is a solution. So $S(n) = T(n) - 1/3$ satisfies $$ S(n) = 4S(n/2), \qquad S(4) = 14/3. $$ You take it from here.

# Answer
> 2 votes
You can use a change of domain here:

$$T(n) = \begin{cases} 5 & n \leq 4\\ 4T(n/2) - 1 & n \> 4\\ \end{cases}$$

Assume $n = 2^{k}$, then let $S(k) = T(2^k)$ and we have:

$$S(k) = \begin{cases} 5 & k \leq 2 \quad \text{because }2^2 = 4\\ 4S(k-1) - 1 & k \> 2\\ \end{cases}$$

Now we can turn this into a sum because $k$ is decreasing by 1 each time:

$$\begin{align\*} S(k) &= 5 + \sum\_{i = 3}^k -1 \cdot 4^{k - i}\\ &= 5 - \sum\_{i = 3}^k 4^{k - i}\\ &= 5 - \sum\_{i = 0}^{k-3} 4^i\\ &= 5 - (4^{k-2} - 1)/3\\ \end{align\*}$$

Now we can plug $n$ back in with $k = \log\_2 n$:

$$\begin{align\*} T(n) &= S(\log\_2 n)\\ &= 5 - (4^{\log\_2 n - 2} - 1)/3\\ &= 5 - (4^{\log\_2 n}/16 - 1)/3\\ &= 5 - (2^{2\log\_2 n}/16 - 1)/3\\ &= 5 - (n^2/16 - 1)/3\\ &= 16/3 - n^2 / 48 \end{align\*}$$

No Master Theorem needed. If you wish, you could prove $S(k)$ equals the summation I mention by induction, but it should be obvious.

# Answer
> 0 votes
Start with T(1) = c, then T(2) = 4c - 1, T(4) = 16c - 5, T(8) = 64c - 21, T(16) = 256c - 85, T(32) = 1024c - 341.

Hopefully you spot that 1 = (4 - 1) / 3, 5 = (16 - 1) / 3, 21 = (64 - 1) / 3, 85 = (256 - 1) / 3, 341 = (1024 - 1) / 3. So we can guess that maybe $T(2^k) = 4^k \cdot c - (4^k - 1) / 3$, and this guess is easily shown to be true by complete induction.

If $n = 2^k$, then $T(n) = n^2 \cdot c - (n^2 - 1) / 3$.

---
Tags: asymptotics, recurrence-relation
---


# Question
Title: Dijkstra’s versus Lowest-cost-first (best first), resolving some contradictions regarding complexity analysis
Our professor took three statements from various textbooks that seem to be a little contradictory regarding the complexity analysis of Dijkstra’s algorithm as well as the lowest-cost-first or best first algorithm.

Edit: I've discovered a related question which can be referenced here: https://stackoverflow.com/questions/10374357/why-use-dijkstras-algorithm-instead-of-best-cheapest-first-search

The statements are as follows:

```
•   “…lowest-cost-first search is typically
exponential in both space and time.  It
generates all paths from the start that have
a cost less than the cost of a solution.”
(Poole, 2nd ed., Section 3.5.4, last
sentence)

•   Dijkstra’s algorithm runs in time O(V^2)
(Cormen, et. al., Ch. 24)

•   Lowest-cost-first search is Dijkstra’s
algorithm where you terminate the search
after you have found the shortest distance to
the goal node.

These statements seem contradictory.
How do you resolve the contradictions?

```

I'm a bit confused about how to approach this question.

From what I've gathered, the answer may have to do with the fact that lowest-cost-first search is said to be an uninformed search strategy whereas, Dijkstra's is said to be an informed search strategy but I don't fully understand the implication.

The first statement confuses me the most, the part that says that:

```
"It (lowest cost first) generates all paths
from the start that have a cost less than the
cost of a solution"

```

My guess is that this statement refers to bounded arc costs which the same text further elaborates on by stating:

```
If the costs of the arcs are all greater than
a positive constant (bounded arc costs) and
the branching factor is finite, the lowest-
cost-first search is guaranteed to find an
optimal solution – a solution with lowest
path cost

```

and

```
The bounded arc cost is used to guarantee the
lowest-cost search will find a solution, when
one exists, in graphs with finite branching
factor. Without such a bound there can be
infinite paths with a finite cost.

```

However this is difficult for me to understand as I am still very much a novice student. If anyone could help explain this I would be eternally grateful, thank you.

# Answer
Imagine you're playing a game, and are currently at state $S\_{0}$. In order to win, you must reach the state $S\_{finish}$.

In every turn, you can do one of $c$ moves. Your goal is to reach $S\_{finish}$ in as little moves as possible; in other words, every move has a cost $1$.

To find the optimal path $P = \\{S\_{0}, S\_1, S\_2 \dots S\_{finish}\\} $, would be finding the set of moves $c\_1 \dots c\_n$ so that $P$ is minimum.

So what would a lower cost first algorithm do? the same thing a $BFS$ would do; in each turn $i$, search $S\_i^1...S\_i^c$ possible states that can be reached from the previous state $S\_{i-1}$.

so, searching $n$ times, how many moves have you effectively searched?

$1$ in turn 1

$c + 1$ in turn 2

$c\*c + c+1$ in turn 3

$=\sum\_{i=0}^{n-1} c^i$ in turn $n$, which is exponential in $n$.

But its also exponential in terms of space. To search all the next states $S\_{i+1}$, you must keep all your current states $S\_i$ in your memory.

How many states $S\_i$ are there? $c^i$ as shown above.

When your professor mentioned Dijkstra is polynomial in $V$, he meant on input size that is $V,E=n, O(n^2)$ respectively. However, when searching the optimal path to some wanted state, like in chess, the number of states (or $V$ essentially, if we suppose a state is a vertex), grows exponentially.
> 2 votes

---
Tags: time-complexity, search-algorithms, shortest-path
---


# Question
Title: Is it possible to balance a already constructed un-balanced AVL tree, with no prior information of last insert?
Im learning about tree data structures, and had a question that i couldnt find answer to so I came here.

Usually when we balance a tree, we insert keys and keep checking balance factor, as soon as it exceeds the given limit of `(-1,0,1)` we immediately balance it and continue to insert keys, if any.

But lets say, I construct a tree, and I dont check balance factor after each key is inserted and I just completely construct the tree first and then I calculate balance factor for each node and attempt to balance the tree.

**Q)** Is it possible to balance tree using such approach ? If yes, then how?

**Q)** If no, then why not? What would be the flaws/problems that would arise using such approach ?

# Answer
What you are asking is simply how to balance a binary search tree (BST) $T$. By the way, the phrase "un-balanced AVL tree" is somewhat confusing since AVL tree is height balanced by definition.

If there is enough space for a whole new tree, then we can simply construct a new AVL tree from scratch, by removing one element from the $T$ and inserting it to the new tree repeatedly. You may call this cheating. While I would agree with you if I were on your side, I can also argue this is just an alternative simple way of balancing a BST, although slightly revolutionary and possibly heavy. Note that we can improve the performance of this approach by taking advantage of the fact that $T$ is a BST, as shown in the exercise 2 below.

Suppose we do not have that much space. Here is how we can balance $T$ in-place. Count the number of nodes in the left subtree of the root node and the number of nodes in the right subtree of the root. If their difference is greater than one, then let us find $m$, the median node of all nodes when the number of all nodes is odd or one of the two median nodes of all nodes when the number of all nodes is even.

* Suppose $m$ is the left child of its parent node. Consider $R$, the right subtree of $m$ and $T'$, which is $T$ with the subtree with root $m$ removed. Note that all nodes of $R$ is smaller than all nodes of $T'$. So we can merge $R$ and $T'$ into a new BST $T''$ easily in $O(1)$ operations. Now set the right subtree of $m$ to $T''$ and set $m$ to be the root.
* Otherwise $m$ is the right child of its parent node. This case is symmetric to the above case.

Now we have obtained a BST tree whose root is a median of all nodes. Repeat the process above on its left subtree and right subtree, as long as the subtree has more than 2 nodes. In the end, we will obtain a BST where the difference of the number of nodes in the left subtree and the number of nodes the right subtree of any node is at most 1. Let us call this kind of BST "optimally-balanced". Intuitively and apparently, you cannot make a BST more balanced than an optimally-balanced BST. It is not hard to prove that an optimally-balanced BST must be an AVL tree.

I might have skipped over a few boundary cases and a few finer points in the above explanation. Hopefully, the above is able to convince you that the answer to "is it possible to balance an already constructed 'un-balanced AVL tree'" is positive once you have taken some time to reflect.

---

Here are several related exercises that you can think about. $T$ is a given BST with $n$ nodes.

**Exercise 1.** Show that an optimally-balanced BST must be an AVL tree.

**Exercise 2.** If there is enough space, convert $T$ to an AVL tree in $O(n)$ time. (Hint, convert $T$ to a sorted array first.)

**Exercise 3.** With $O(1)$ working space, balance $T$ into an AVL tree in $O(n)$ time. (This might be a difficult exercise.)
> 1 votes

---
Tags: data-structures, trees, avl-trees
---


# Question
Title: find separate pairs of points with minimal total distance
I am looking for suitable algorithm how to solve the following problem.

For finite set $S \subset \mathbb{R}$ ($|S| = N\_{S}$) we need to find its disjunctive separation $S = A \cup B$ ($A \cap B = \emptyset$) on two ordered sets and assignment $\pi$ between elements of these two sets, where the following conditions must be fulfilled:

1. $|A| = |B| = N$ where $N = \lfloor N\_s/2 \rfloor$
2. $s\_k \in S$ where $k = 1,2, ...,N\_s$
3. $a\_i \in A$ and $b\_j \in B$ where $i,j = 1,2, ..., N$
4. $\sum\_{i=1}^{N}|a\_{\pi(i)} - b\_i| \to min$

In other words, I am looking for method how to find set of separated pairs $\[a\_{\pi(i)},b\_i\]$ assignments.

Example: $$S = \[3.0, 2.1, 0.9, 2.9, 1.1\], N\_s = 5, N = 2$$ then $$A = \[3.0, 0.9\]$$ and $$B = \[2.9, 1.1\]$$ which produce following separate pairs:

$$\[3.0, 2.9\], \[0.9, 1.1\]$$

Note: I am not sure if my problem description is sufficiently rigorous and clear. But I tried do my best.

# Answer
> 2 votes
Sort the items so that $s\_1 \le s\_2 \le \dots \le s\_{N\_S}$. Then:

* If $N\_S$ is even, assign all the odd-numbered items to $A$, all even-numbered items to $B$, and pair the first item of $A$ with the first of $B$, etc. This assignment must be optimal, since any pairing in which two pairs overlap can always be transformed into a pairing with no overlap that does not cost more.
* If $N\_S$ is odd, enumerate over all possible items $s\_i$ in $S$ and for each of them, compute the best partition of $S \setminus \\{s\_i\\}$, which is an even-size set, using the previous case. Return the best partition among all $N\_S$ cases.

The total cost of this procedure is $O(N\_S \log N\_S)$ when $N\_S$ is even and $O(N\_S^2 \log N\_S)$ when $N\_S$ is odd.

---
Tags: assignment-problem
---


# Question
Title: Reducing Exact Cover to Subset Sum in practise!
The reduction of Exact Cover to Subset Sum has previously been discussed at this forum. What I'm interested in is the practicality of this reduction, which I will discuss in **section 2** of this post. For you who are not familiar with these problems I will define them and show the reduction Exact Cover $\leq\_p$ Subset Sum in **section 1**. For the readers who are already familiar with these problems and the reduction can move ahead to **section 2**.

## section 1

The **Exact Cover** defined as follows:

Given a family $\\{S\_j\\}$ of subsets of a set $\\{u\_i, i=1,2,\ldots,t\\}$ (often called the Universe), find a subfamily $\\{T\_h\\}\subseteq\\{S\_j\\}$ such that the sets $T\_h$ are disjoint and $\cup T\_h=\cup S\_j=\\{u\_i, i=1,2,\ldots,t\\}$.

The **Subset Sum** is defined as follows:

Given a set of positive integers $A=\\{a\_1,a\_2,\ldots,a\_r\\}$ and another positive integer $b$ find a subset $A'\subseteq A$ such that $\sum\_{i\in A'}a\_i=b$.

For the **reduction** Exact Cover $\leq\_p$ Subset Sum I have followed the one given by Karp R.M. (1972) Reducibility among Combinatorial Problems

Let $d=|\\{S\_j\\}|+1$, and let $$ \epsilon\_{ji}=\begin{cases}1 & \text{if} & u\_i\in S\_j, \\ 0 & \text{if} & u\_i \notin S\_j,\end{cases} $$ then $$ a\_j=\sum\_{i=1}^{t}\epsilon\_{ji}d^{i-1}, \tag{1} $$ and $$ b = \frac{d^t-1}{d-1}. \tag{2} $$

## section 2

In practise (meaning for real world problems) the size of the Universe for the Exact Cover problem can be very large, e.g. $t=100$. This would mean that if you would reduce the Exact Cover problem to the Subsets sum problem the numbers $a\_j$ contained in the set $A$ for the Subset Sum could be extremely large, and gap between the $\min\\{A\\}$ and $\max\\{A\\}$ can therefore be huge.

For example, say $t=100$ and $d=10$, then its possible to have an $a\_j\propto 10^{100}$ and another $a\_i\propto 10$. Implementing this on a computer can be very difficult since adding large numbers with small numbers basically ignores the small number, $10^{16} + 1 - 10^{16} = 0$. You can probably see why this could be a problem.

> Is it therefore possible to reduce the Exact Cover to Subset Sum in a more practical way, that avoids the large numbers, and have that the integers in $A$ are of a more reasonable size?

I know that it is possible to multiply both $A$ and $b$ by an arbitrary factor $c$ to rescale the problem, but the fact still remains that gap between possible smallest and largest integer in $A$ is astronomical.

Thanks in advance!

# Answer
The short answer is *no* :-)

Why? ... Because SUBSET SUM is weakly NP-complete; you cannot avoid the exponential blowup of the numerical value of the arguments with respect to the input size of the original problem (in other words the length of the binary representation of the $a\_j$ is kept polynomial by the reduction but the values obviously are exponential)

If this was not the case you could use Dynamic Programming to solve an NP-complete problem in polynomial time.
> 5 votes

---
Tags: reductions
---


# Question
Title: How are problems classified in Complexity Theory?
I'm reading Sipser's Introduction to the Theory of Computation (3rd edition). In chapter 0 (pg. 2), he says we don't know the answer to "*what makes some problems computationally hard and others easy*," however, he then states that "*researchers have discovered an elegant scheme for classifying problems according to their computational difficulty. Using this scheme, we can demonstrate a method for giving evidence that certain problems are computationally hard, even if we are unable to prove that they are.*"

So my question is: HOW is it possible to classify problems according to their computational difficulty, if we don't even know what makes a problem computationally easy/hard in the first place?

Also, what/where is this "scheme" that does this classifying. (I did some googling and couldn't find anything)

# Answer
**That's what you get when you distill a whole bunch of theory to a wider audience.**

In his book, Sipser addresses a general audience at the undergraduate level, possibly with no notion of computability theory; hence, he can only hint at concepts which are to be given a more formal treatment later on in the book. The part you cite is from chapter 0 (i.e., not really a chapter), whereas the material for complexity theory only appears at the end (i.e., part three). This is why the passage is so fuzzy. Most likely it is intended only as motivation and to give a broad overview for the topics to be covered in the book.

The "scheme" Sipser is talking about are *reductions*. If we know a problem $A$ is reducible to a problem $B$, then we know $B$ is at least as hard as $A$. (Incidentally, this is also why it is common practice to denote reductions with a "$\le$" sign.) This gives us a way of ordering problems according to their difficulty, at least for those having reductions we are aware of. As Sipser states, though, by using only reductions "we are unable to prove" whether the problems are really hard or not; reductions only give us *relative*, not *absolute* notions of hardness. This is why separation results are still rare in modern complexity theory: We have a bunch of reduction (e.g., NP-completeness) results, but only a handful of separation results (e.g., the time and space hierarchy theorems).
> 9 votes

# Answer
> HOW is it possible to classify problems according to their computational difficulty, if we don't even know what makes a problem computationally easy/hard in the first place?

I think the point that the piece is trying to make is that we know how to determine whether individual problems are easy or hard, even though we don't have an over-arching theory of *why* the hard ones are hard and the easy ones are easy. Just like you can classify people according to their weight, even though you don't know *why* they have the weight they do.

I should emphasise that in most cases, "hard" means "seem to be hard". You've probably heard of **NP**-complete problems. We don't know for certain that these problems have no efficient algorithm (by the standard definition of "efficient") but nobody has been able find an efficient algorithm for any of them in nearly 50 years of trying, and finding an efficient algorithm for just one of them would give efficient algorithms for all of them.

> Also, what/where is this "scheme"

Complexity classes, the relationships between them, and the concept of reductions for transforming one problem into another.
> 2 votes

# Answer
The "scheme" is based on the ideas of *reductions* among problems and *completeness* of problems, which are described in Chapters 5 and 7 of Sipser's book.
> 1 votes

---
Tags: complexity-theory
---


# Question
Title: Is it possible to achieve greater than perfect compression using machine learning and big data?
Imagine Google wanted to make their chrome browser faster. Let "database" be all the machines which serve content from Google's servers, including Search and Google cloud services. Google begins using machine learning to analyze thousands of petabytes of data on their database to extract a dictionary of the most redundant file sequences. Lets say the most redundant hexadecimal found was the sequence:

"64 65 63 69 6d 61 6c 20 66 6f 72 6d 61 74 2e 20 43 6f 6d 70 75 74 65 72 73 20 73 74 6f 72 65 20 74 65 78 74 20 61 73 20 6e 75 6d 62 65 72 73 2c 20 61 6e 64 20 77 69 74 68 20 68 65 78 20 79 6f 75 20 64 69 73 70 6c 61 79 20 74 68 65 20 6e 75 6d 62 65 72 73 20 6e 6f 74 20 61 73 20 61 20 64 65 63 69 6d 61 6c 20 6e 75 6d 62 65 72 2c 20 62 75 74 20 69 6e 20 62 61 73 65 20 31 36 2e 20 48 65 78 20 6f 72 20 62 61 73 65 20 31 36 20 6f 72 20 68 65 78 61 64 65 63 69 6d 61 6c 20 69 73 20 61 20 6e 75 6d 65 72 61 6c 20 73 79 73 74 65 6d"

They stored this sequence in their dictionary at index 1 and included this dictionary file in their Chrome update. For every user that had the latest Chrome update if they requested a file that had this sequence Google's server would return a flag and the index 1 (e.g. "D 1") such that the Chrome browser could lookup the bytes locally without the need of transferring them over the network. In essence the file being transferred would become something like "data data data D 1 data data"

Furthermore, they did this for gigabytes of sequences causing a larger Chrome update but faster file transfer times.

And to make things more interesting they used machine learning to analyze end-user behavior to predict which sequences were more likely to be requested.

After adding this functionality they achieved faster load times and decreased network congestion and possibly saved in electricity costs by removing redundancy across their entire network.

Questions:

What would this be called? Distributed Cached file transfer? Would this be practical or desirable? I imagine it could save money in terms of electricity for a large company like google.

# Answer
> Is it possible to achieve greater than perfect compression...

No. Any lossless compression scheme that makes at least one string shorter must make at least one string longer. This is an unavoidable consequence of the simple fact that there are more long strings than short ones.

The best you can do is be smart about what strings get made shorter, and I guess that's what you're trying to do with machine learning, big data, and any other applicable ~~buzzwords~~technologies. Effectively, though, you're trying to use a big global dictionary. This is probably less efficient than standard dictionary compression which builds up the dictionary from the data that's being compressed (a dictionary containing lots of Spanish and Chinese isn't going to be useful for compressing Stack Exchange, for example). Also, if you're going to cut network traffic, that big global dictionary needs to be already sitting on your computer, taking up huge amounts of space for dictionary entries you'll probably never use. Indeed, if that huge dictionary comes as part of my next Chrome update, it's not even obvious that there'll be a net saving in data transfer.
> 2 votes

---
Tags: machine-learning, information-theory, data-compression
---


title: One counter automaton as a function

text:
# Question
Title: One counter automaton as a function
We can associate a one counter finite automaton with a function $f:\Sigma^\* \to \mathbb{N} \times \\{0,1\\}$, where $f(x)=(n,b)$ describes the state where the automaton terminates when fed an input word $x \in \Sigma^\*$: $n$ holds the number inside the counter, and $b=1$ iff the state is an accepting state.

Is it decidable to determine whether two of these automata are associated with the same function?

I looked at posts like this one and this one too but I can't find the answer.

Furthermore, since these machines are always aimed to accept/reject a string, is there any natural way to expand them to represent a function? As an example, think of a machine that simply counts the number of times it visited a specific node in the DFA, or even simpler: counts the length of its input word.

# Answer
> 2 votes
You can use the counter value as the result of the function.

Furthermore, if I understood well your question, a simple way to map $(bool,nat)$ is the following: modify the state transitions of the original automata $A$ to make the counter value equal to $2x$ if the counter of the original A is $x$ and the state is rejecting, $2x+1$ if the counter of the original $A$ is $x$ and the state is accepting.

If the one-counter machine that returns $(bool, nat)$ (with no distinction between accept/reject states, because the accept/reject condition is embedded in the returned value as explained above) is deterministic, then you can decide equivalence using this trick:

Given automata $M\_1$, $M\_2$ computing $f\_1,f\_2:\Sigma^\* \to N \times \\{0,1\\}$; you can transform them back to two standard accept/reject automata $M\_1', M\_2'$ computing $f\_1',f\_2':\Sigma^\* \to \\{0,1\\}$.

Expand the alphabet adding an extra symbol $\*$; and make $M\_1'(x\*^k ) = Accept$ if and only if $M\_1(x) = k$.

When $M\_1', M\_2'$ find a $\*$ they decrement the counter if it is $\>0$, otherwise they enter a permanent reject state. If the counter reaches $0$ after the decrement, then they enter an accept state. If they find another symbol after a $\*$ they enter a permanent reject state.

Now you can check language equivalence of the "standard" one-counter automata $M\_1', M\_2'$ (decidable in the deterministic case, see *L.G.Valiant, M.S.Paterson, Deterministic One-Counter Automata, 1975*) and by construction $L(M\_1') = L(M\_2')$ if and only if $f\_1 = f\_2$.

# Answer
> 1 votes
A related model is the finite state automaton with two tapes: it accepts pairs of strings ($u,v)$, each read from its respective tape. This is equivalent to so-called finite state transductions. Those define a "regular" mapping from strings to strings. Just imagine that the finite state automaton has instructions for "read" (from the first tape) and "write" to the second tape.

Why is this relevant to your question? Because we can easily restrict the output tape to a single symbol. Thus the machine accepts a subset of $\Sigma\times \\{b\\}^\*$ for some symbol $b$. This is of course equivalent to subsets of $\Sigma^\* \times N$.

Unfortunately it is undecidable whether two of these machines are equivalent. Theorem 6.3 in O.H. Ibarra, Reversal-bounded multicounter machines and their decision problems, J. Assoc. Comput. Mach., 25 (1978), 116-133.

> Let $a$, $b$, and $c$ be three different symbols. Then it is undecidable whether or not, for an arbitrary regular transduction $R$ from $\\{a, c\\}$ to $\\{b\\}$, $g = \\{a, c\\}^\* \times \\{b\\}^\*$.

This does not contradict the fact that equivalence for one-counter machines is decidable. After all for one counter machines, the counter-value is not part of the output. In general one-counter machines accept if the counter is zero.

---
Tags: computability, finite-automata, undecidability
---


# Question
Title: Given directed connected weighted graph, check if d(v) = delta(s,v)
I'm having some hard time with this problem. Can someone give me some clue/guidance?

This is an homework question, so please don't just solve it.

> Given a weighted directed connected graph $G = (V,E)$ and given another function $d: V \to \mathbb{R}^+$ (including zero), find a linear time algorithm that checks if $d(v)=\text{delta}(s,v)$ for each $v$, for some fixed vertex $s$.
>
> $\text{delta}(s,v)$ is like in Dijkstra algorithm, meaning shortest path from $s$ to $v$.

My thought is to make use of BST to check if these functions are equal, but I can't avoid running Dijkstra for it.

# Answer
> 1 votes
If $d$ indeed represents the length of the shortest path, we must have

$$ d(v)= \begin{cases} 0, &\text{if $v=s$,}\\ \displaystyle\min\_{u:(u,v)\in E}\\{d(u)+w(u,v)\\}, &\text{otherwise,} \end{cases} $$

where $w(u,v)$ is the weight of the edge $(u,v)$.

So you can check whether $d$ satisfies this property for all $v$. It takes only linear time. If $d$ does not satisfy this property, it cannot represent the length of the shortest path. However, if $d$ does satisfy this property, does it really represent the length of the shortest path? I'll let you figure out this part.

For a further hint:

> Note what you need to prove is that, for all $v$, $d(v)$ is length of the shortest path from $s$ to $v$. Suppose the shortest path from $s$ to $v$ contains $k$ edges, you may try a mathematical induction on $k$.

---
Tags: graphs, shortest-path, weighted-graphs
---


title: Show that language is context-free

text:
# Question
Title: Show that language is context-free
Let $A$ be a pushdown automata with input alphabet $\Sigma$ and stack alphabet $\Gamma$ and let $R \subseteq \Gamma^∗$ be a regular language. Let $L\_R(A) \subseteq \Sigma^∗$ be a language of such words over alphabet $\Sigma$, for which there exists some run of automata $A$, such as in every step symbols on the stack belongs to the regular language $R$.

Show that language $L\_R(A)$ is context-free.

# Answer
> 3 votes
Let $Q$ be the set of states in a DFA $D$ for $R$. We replace $\Gamma$ with $\Gamma \times Q$, and update the PDA so that the stack contains, apart from the original stack symbols, also the state that $D$ is in after reading the current word on the stack. The PDA only allows transitions if the element at the top of the stack corresponds to an accepting state of $D$, and also checks this condition at the very end.

---
Tags: regular-languages, automata, context-free
---


title: Probabilistic r-way cut set algorithm

text:
# Question
Title: Probabilistic r-way cut set algorithm
I am reading Probability and Computing, by Mitzenmacher and Upfal, and the exercise 1.24 asks for a generalized algorithm for finding the cut-set of a Graph.

In this generalized version, instead of finding a set of edges that would break the graph into two components, it would break it in *r* components. The approach used for the 2-way cut-set is to contract edges until only two vertices remain, and treat the edges remaining as the cut-set $C$.

The question then is

> Explain how the randomized min-cut algorithm can be used to find minimum r-way cut-sets, and bound the probability that it succeeds in one iteration.

My idea is to instead of stopping when there are *r* vertices remaining, instead of 2. But I am unable to bound its success probability. A possible approach would be to find the probability of contracting an edge $\in C$. To do so, I define $|C|=k$, and based on that, $d(v)\ge k-r+2$, $\forall v \in V$. Thus, $|E|\ge \frac{(k-r+2) \cdot (n)}{2}$. But i can't remove this $k$ from the equation latter...

Any ideas here?

# Answer
> 2 votes
Your idea of stopping when there are $r$ vertices remaining is the correct approach. Now let us see how to bound the success probability of contracting one arbitrary edge not in a fixed $r$ way cut-sets.

Denote the graph by $(V,E)$ with $n=|V|$ and $m=|E|$.

**Lemma**: Let $C$ be an $r$-way minimum cut. The probability that a randomly selected edge is not in $C$ is at least $$\frac{(n-r+1)(n-r)}{n(n-1)}.$$

**Proof**: Let us count the number of elements in the following sets.

$$\begin{align} V^{r-1}&=\\{Q: Q \subseteq V\text{ such that } |Q| = r-1\\}\\ S&=\\{(e, Q): Q\in V^{r-1}, e\in E \text{ such that none of the endpoints of } e\text{ is in } Q \\}\\ S\_{e}&=\\{\phantom{(e,\\,} Q\phantom{)}: Q\in V^{r-1}\phantom{, e\in E } \text{ such that none of the endpoints of } e\text{ is in } Q \\}\\ S\_{Q}&=\\{\phantom{(}e\phantom{,Q)}: \phantom{Q\in V^{r-1},\\,} e\in E \text{ such that none of the endpoints of } e\text{ is in } Q \\}\\ \end{align}$$

$|V^{r-1}|=\binom{n}{r-1}.$
$|S\_e|=\binom{n-2}{r-1}$ for all $e\in V$.

Fix an arbitrary $Q\in V^{r-1}$. If we removes all edges not in $S\_Q$, i.e., all edges whose endpoints are in $Q$ and all edges between a vertex in $Q$ and a vertex not in $Q$, there will be $r-1$ connected components of single vertex and one or more connected components in the remaining vertices. That means the set of all edges not in $S\_Q$ is an $r$-way cut. Since the minimize size of an $r$-way cut is $k$, the number of edges not in $S\_Q$ is no less than $k$, i.e, $|S\_Q|\le m-k.$

Since $S$ is the disjoint union of all $S\_e$, $e\in E$ as well as the disjoint union of all $S\_Q$, $Q\in V^{r-1}$,
$$\binom{n-2}{r-1}m \le (m-k)\binom n{r-1},$$ which means, $$1-\frac k{m} \ge\frac{\binom{n-2}{r-1}}{\binom n{r-1}}=\frac{(n-r+1)(n-r)}{n(n-1)},$$ where the left side is exactly the probability that a randomly selected edge from $E$ is not in $C$, a set of $k$ edges. QED.

---

Now that we have the lemma above, we can proceed just as in the book to compute the probability that any given minimum $r$-way cut $C$ survives all $n − r$ random successive edge contractions.

---

**Exercise.** (One minute or less) Check that the lemma and its proof above specialize to the arguments given in the book in the case of $r=2$.

---
Tags: algorithms, complexity-theory, graphs, probabilistic-algorithms
---


# Question
Title: Is Breadth First Search Space Complexity on a Grid different?
Is the Space Complexity O(number\_rows + number\_cols) for Breadth First Search on a **Grid**. This is an attempt to show my reasoning:

For example, the flood fill question is described here:

https://www.geeksforgeeks.org/flood-fill-algorithm-implement-fill-paint/

The flood fill algorithm using breadth first search (queue) has space complexity: O(number\_rows + number\_cols).

Why? Suppose you start at the top left corner (or coordinate (0,0)). Going to the right we will get at most O(number\_cols) in the queue. When we reached the end of the column we can then start going down from coordinate (0, 0) giving us O(number\_cows + number\_cols) in the queue.

Then, is it the case that many of the questions where we use breadth first search on a grid we will get space complexity of O(number\_rows + number\_cols). For example:

1. Flood Fill question above,
2. Maze where we have to find the shortest path from start to exit,
3. Finding number of islands (reference below)

But for 3) finding the number of islands, it looks like some people are saying the space complexity is O(number\_rows * number\_cols) from : https://stackoverflow.com/questions/50901203/dfs-and-bfs-time-and-space-complexities-of-number-of-islands-on-leetcode

On the other hand, I would assume that the space complexity of dfs on a grid is O(number\_rows * number\_cols)

**The questions are as follows based on the above:**

1. Is the space complexity of breadth first search on a grid: O(number\_rows + number\_cols)?
2. Is the space complexity of depth first search on a grid: O(number\_rows * number\_cols)?

Other references:

https://stackoverflow.com/questions/21054959/time-and-space-complexity-for-breadth-first-search

https://stackoverflow.com/questions/4261112/time-and-space-complexities-of-breadth-first-search

# Answer
It depends what you mean by a "on a grid".

If you mean that you are working with the graph of a complete grid, with number\_rows * number\_cols vertices (one for each grid point) and an edge between every pair of adjacent vertices:

Yes, that's correct. The asymptotic time complexity of both is O(number\_rows * number\_cols), and the asymptotic space complexity is O(number\_rows + number\_cols) for BFS or O(number\_rows * number\_cols) for DFS.

If you mean that you are working with a graph that is a subgraph of a complete grid, then:

No, that's incorrect. The asymptotic time complexity of both is O(number\_rows * number\_cols), and the asymptotic space complexity of both could be as large as O(number\_rows * number\_cols), as explained in https://stackoverflow.com/a/50912382/781723.
> 4 votes

---
Tags: graphs, data-structures, trees, space-complexity, queues
---


# Question
Title: Turing Machine to Accept String from a 3 character alphabet
I need to create a turing machine that accepts the language $a^ib^jc^k$ where $i \ge j \ge k$, but I am not even really sure how to start. Turing machines in this context are a hard concept for me to grasp for some reason.

# Answer
> 1 votes
One idea is to delete characters, to make it easier let me introduce @ character - it will denote empty space after scratching characters.
For example let input string be $BaabccB$, where $B$ is blank symbol.
At first check for $a$ and create state, say $qa$ which looks for $a$ and then replaces it with $@$ switches to $qb$ moves right until it finds $b$.
Then it replaces $b$ with $@$ switches state to $qc$ and moves right until it finds $c$.
Here again replaces $c$ with $@$ and switches to state $ql$ moves to the left until $a$ is found.
While moving right if blank symbol is encountered, it means that there are less symbols of particular character, this is good according to given language, if the next character is also missing otherwise it breaks inequality and we reject. Also when we seek $b$ but encounter $c$ we reject. After consecutive $c$ if there are other symbols, we reject (it is something like $abca$
When moving left, when blank is encountered, we are finished and accept.

It may happen that there are not sufficient number of $a$ or any character, so after reaching blank character we move right to delete $@$ characters. If we clear all and hit blank, we accept, otherwise we reject as some characters broke inequality.

Example: $BaabccB$
$B@abccB$ move right, switch state, replace $b$
$B@a@ccB$ move right, switch state, switch $c$.
$B@a@@cB$ move left until $a$ replace
$B@@@@cB$ move right, switch state, $c$ is encountered in $qb$ state, it means that $#c \> #b$ reject.

Excersise 1:
Try to solve similar question where $i \ge j \le k$

Excersise 2:
Try to solve similar question where $i = 2j = 3k$

# Answer
> 1 votes
There are two things you need to do when designing a Turing machine (or, in fact, writing any computer program). The first is to decide what algorithm you're going to use, and the second is to express that as a Turing machine/Java program/whatever. I'll cover the first part.

Turing machines were inspired by what a human could compute using a pencil and paper so, usually, the best way to figure out an algorithm is to think, "How would I do this if somebody gave me a really long string written on a piece of paper and asked me to determine if the string is in the language?" First, you'd scan the input to check that it really is a bunch of $a$s followed by a bunch of $b$s followed by a bunch of $c$s. Then what?

1. You could count the $a$s, $b$s and $c$s, call those numbers $i$, $j$ and $k$, and check that $i\geq j\geq k$. That's all very well but the numbers are *big* so you'll lose count unless you write down the numbers step by step. As in, there are $1$, $2$, $3$, ..., $45\\,387\\,298$ $a$s. And then you need to figure out how to compare if one number is bigger than another and this is all rather tricky and tedious.
2. You don't actually care what the numbers are, as long as they're in the right pattern, so why bother computing them at all? If you had a big pile of stones and you wanted to know if it was an odd or even number, you could count, or you could just arrange the stones into pairs and see if there's one left over. The same idea applies here: go through the string and repeatedly cross out an $a$, a $b$ and a $c$. If you run out of $c$s first, there are more $a$s and $b$s than $c$s. Then cross out $a$s and $b$s and check that you run out of $b$s next. What is "crossing out"? Well, looking at it kinda literally, you're replacing a character $a$ with $\not{\\!a}$, etc., and you can always add $\not{\\!a}$, $\not{b}$ and $\not{\\!c}$ to your alphabet. Or you can make your life easier by interpreting "cross out" as "replace with $\times$" since, once a character is crossed out, you don't actually care what it used to be.

---
Tags: turing-machines
---


# Question
Title: Whats the best way to sort a dataset into groups by using a facial recognition algorithm that compares only 2 images at a time?
I have a facial recognition algorithm that compares two images A and B and returns the likelihood that they match.

I also have 50,000 images, and I would like to sort these images into groups.

Here's the immediate way I thought of to do this:

1. Start with image 0, compare it to all 49,999 images. Store the similarities in an array
2. Move on to image 1, compare it to 49,998 images (skip img\_0). Store the similarities in an array

At the end of it all I'm left with a `verified_list`of images that matched, and I can basically feed them into a network to combine them, ie if I have a `verified_list` like so:

`[[1,2,3],[2,5,6],[8,9]]` (`verified_list` is the same length as the number of images, so `verified_list[1]` contains references all the images that image\_1 matches with)

then the network graph combines them into:

`[[1,2,3,5,6], [8,9]`

Indicating I have two groups.

Obviously this is a huge amount of processing, I think it equates to: nCr(50000,2), some huge number!

Is there a faster way to sort my dataset into groups?

# Answer
> 1 votes
So it appears you actually have vectors over $\mathbb{R}^n$, one vector per face, and you want to group the vectors, using $L\_2$ distance (Euclidean distance) to measure similarity.

There are a number of techniques for this. See data structures for nearest neighbor search (https://en.wikipedia.org/wiki/Nearest\_neighbor\_search). I would suggest that locality sensitive hashing might be a promising choice for your situation. You could also look into clustering algorithms (though they will probably still require nearest neighbor search as one step of their working).

---
Tags: algorithms, graphs, sorting
---


# Question
Title: Single processor system supporting two running processes, A and B, with the following sequential execution patterns
Can anyone please help me with the following question?

Consider a single processor system supporting two running processes, A and B, with the following sequential execution patterns:

A: \[CPU 8 ms; IO 1 ms; CPU 8 ms; IO 1 ms; CPU 8 ms\]

B: \[CPU 2 ms; IO 1 ms; CPU 2 ms; IO 1 ms; CPU 2 ms\]

Assume that IO operations do not interfere with each other and are blocking, and that scheduling and context switch times are negligible.

a) What is the total elapsed time for the two processes to run to completion?

b) Assume the system runs a non-preemptive scheduler where processes are scheduled in the order in which they become runnable, and that B takes priority over A in the event of a tie. Give the combined execution pattern of the two processes in the format as in part (ii), and determine the total elapsed time for the two processes to run to completion.

c) Repeat part (ii) b) with a pre-emptive scheduler operating with a time slice of 4ms.

d) What are the costs and the benefits of a pre-emptive scheduler over a non- preemptive scheduler for this workload, which would you choose, and why?

# Answer
Non-preemptive, starting with job A, does 8ms on job A, 2 ms on job B, 8 ms on job A, 2 ms on job B, 8 ms on job A, 2ms on job B. I/O is performed while the other job uses the CPU, so is free. Job A finishes after 28 ms, job B after 30 ms.

If you had started with thread B, B would have finished after 22 ms, A after 30.

You could finish B substantially faster by giving it higher priority: 2ms job B, 1ms job A (while B performs i/o), 2ms job B, 1ms job A, 2ms job B, then job A finishes without getting the I/O for free. B finishes after 8ms, A after 32ms.

If we preempt after 4ms, if we start with A, we run A for 4ms, B for 2ms, A for 4ms, B for 2ms, A for 4ms, B for 2ms, then A for 4 ms, 1ms I/O, A for 8ms. Takes 18ms for B, 31ms for A. You get different numbers if you start with B.

This is all quite unsatisfactory. Without preemption, and with little I/O, the execution time of each job is basically dependent on the number of I/O operations, because we switch on I/O operations. However, if we give priority to the job that takes fewer resources, it can finish much faster - unsatisfactory, because we don't know which job takes fewer resources.

Preemption after 4ms makes the process using less CPU time finish faster.
> 0 votes

---
Tags: operating-systems
---


# Question
Title: How to solve a DP problem that minimizes a sum of cubic powers?
I am trying to practice some coding problems and I came upon this problem:

As electricity prices are soaring, there must be a way to reduce wastage by increasing the utilization of heavy duty machines, such as elevators.
We formulate the problem as follows.
There are $N$ persons $ (p\_1,...,p\_N)$ waiting in a queue to get into an elevator. By the way, there is only one elevator, and it travels between the ground floor to the sky floor (i.e., there are no other stoppages in between). Also, all persons are waiting on the ground floor.
Just for simplicity, we are concerned only with the utilization of the ground-to-sky journey of the elevator. Each person $p\_i$ has a positive weight $w\_i$.
The weight capacity of the elevator is $M$. Therefore, all persons may not be carried together. They are carried in several trips. Each person gets into the elevator according to his order in the queue. Meaning, $p\_1$ gets in first, then $p\_2$ and so on. Suppose at the $t$-th trip, persons $p\_j$ through $p\_k$ gets into the elevator. The waste factor ($WF$) of the trip $t$ is defined as

$$WF\[t\]=M-\sum\_{i=j}^k(w\_i).$$

Your task is to minimize the total waste ($TW$), which is defined as:

$$TW=\sum\_{t=1}^{S-1}(WF\[t\])^3,$$

where $S$ is the total number of trips required to carry all the people from the ground to the sky floor. Note that the $WF$ of the last trip is not included in the $TW$ calculation.

I got completely stuck here, I figured that this can be solved via DP but I don't know how. Especially with the condition of maintaining the order. Full problem can be found in here Problem K: Elevate the Utilization!

# Answer
> 0 votes
The essence of the dynamic programming is to recognize the appropriate subproblems.

Here is a way to formulate the subproblems. Let us compute $dp\[i\]$, the minimum total waste for weight sequence $w\_{i}, w\_{i+}, \cdots, w\_N$, where $1\le i\lt N$. The wanted minimum total waste of the entire sequence shall be $dp\[1\]$.

The base cases are $dp\[N\]=dp\[N-1\]=\cdots=0$, where $dp\[i\]=0$ as long as $w\_{i} + w\_{i+1}+ \cdots+w\_{N}\le M$ since the last trip does not produce waste. Let $j$ be the smallest such index.

What about $dp\[j-1\]$, $dp\[j-2\]$ and beyond? We note that $dp\[k\]$ is the minimum of $$\begin{align} dp\[k+1\] &+ (M-w\_k)^3,\\ dp\[k+2\] &+ (M-(w\_k+w\_{k+1}))^3,\\ \cdots\\ dp\[k+t\] &+ (M-(w\_k+w\_{k+1}+\cdots+w\_{k+t-1}))^3\\ \cdots,\\ \end{align}$$ where the list goes on as long as $w\_k+w\_{k+1}+\cdots+w\_{k+t-1}\le M$. This recurrence relation enables us to compute $dp\[k-1\]$ if $dp\[k\], dp\[k-1\], \cdots, dp\[N\]$ are known.

The time complexity of algorithm is about $O(N\*N)$.

### Java code

The above is an implementation in Java that takes file "elevate.in" as input. Just click "run" to see the result.

### Exercises

Here are two exercises based on the same situation to think about.

**Exercise 1.** (One minute or two.) Suppose the total waste is defined as $$TW=\sum\_{t=2}^{S}(WF\[t\])^3$$ instead. Note that the WF of the first strip instead of the last strip is excluded.

**Exercise 2.** Suppose the total waste is defined as $$TW=\sum\_{t=2}^{S-1}(WF\[t\])^3$$ instead. Note both the WF of the first strip and the last strip are excluded.

# Answer
> 0 votes
Here is a very simple Python implementation:

```
def solve(M, q):
    dp = [0 for i in range(len(q))]
    for i in range(len(q)-2, -1, -1):
        if sum(q[i:]) <= M:
            continue  # last elevator is free
        dp[i] = min(
            [(M-sum(q[i:j]))**3 + dp[j]
             for j in range(i+1, len(q))
             if sum(q[i:j]) <= M])
    return dp[0]

M = 20
q = (10, 4, 6, 7, 6, 9, 4)
assert solve(M, q) == 217

```

The dynamic programming step is obviously minimizing $M - (\sum\_{i}^j w\_i)^3 + \text{dp}\_j$.

The complexity is as Apass.Jack analyzed in their answer, $O(N^2)$.

---
Tags: dynamic-programming
---


# Question
Title: Is there a way to calculate the number of all the languages over an alphabet?
Let $\Sigma = \\{ a,b,c \\}$ be an alphabet.

How should I calculate the number of Languages over $\Sigma$?

# Answer
> 7 votes
It's uncountable infinite.

There are the languages $\\{ a^0 \\}$, $\\{ a^1 \\}$, $\\{ a^2 \\}$, $\\{ a^3 \\}$ etc., which is already countable infinite.

But the powerset of the integers is uncountable infinite. So for every set S of integers, take the language $\\{ a^k: k \in S \\}$ and you have an uncountable infinite set.

(The number of languages that can be defined by any algorithm is only countable infinite, so most of these uncountable many languages cannot be described in any way).

---
Tags: automata
---


# Question
Title: What is the importance of the condition "| xy | < p" in pumping lemma?
Let $L$ be a language. $w \in\ L$ , and $w$ could be broken in $xyz$.

Then if $L$ is regular, there exists a pumping length $p$ such that:

1. $\vert y\vert\>0$
2. $\vert xy\vert \leq p$
3. $\forall i \geq 0,\ xy^i z\ \in L$

I understand that this lemma is

* based on pigeon hole principle
* we use it to prove that a language is not regular by contradiction.

For condition (1), I understand that the string we are pumping should be $\geq 1$.

But I don't understand the significance of condition (2).

Why should the length of $xy$ be equal to or smaller than $p$ . Won't it work otherwise?

# Answer
> 5 votes
$p$ is the number of states in the automaton. As you say, the pumping lemma is about the pigeonhole principle. Suppose that $q$ is the first state that's repeated when you read input $w$. Then $x$ is the string that you read before you reach $q$ for the first time, and $y$ is the string you read between the first and second visits to $q$. Since there are only $p$ states including the start state, you must repeat a state after doing at most $p$ transitions, i.e., reading a string of length at most $p$. So the condition $|xy|\leq p$ comes from the proof.

In reality, when an automaton reads a particular string $w$, there might be many times when it returns to a state that has already been visited. If you take $w\in L$ any split $w=xyz$ with $|y|\geq 1$, such that the automaton is in the same state at the beginning and end of $y$ then $xy^iz$ will be in $L$ for all $i$, regardless of how long $xy$ is.

---
Tags: automata, pumping-lemma
---


# Question
Title: Algorithm: Calculate every number in a given list using addition and numbers you've created
I'm creating an algorithm to calculate every number in an array using only addition and numbers we've created - in the shortest amount of steps. That's confusing so here is an example:

```
input: [5, 11], used numbers (start with 1): [1]
1+1=2, used: [1, 2]
2+2=4, used: [1, 2, 4]
1+4=5, [1, 2, 4, 5]
5+5=10, [1, 2, 4, 5, 10]
10+1=11, [1, 2, 4, 5, 10, 11]

```

We have hit 5 and 11 so we are done in 5 steps. There are other ways to get \[5, 11\], eg. \[1, 2, 3, 5, 6, 11\]. They are the same amount of steps. Imagine we have input \[5, 11, 20\]. Now it matters which we choose above because \[1, 2, 4, 5, 10, 11\] only requires one more step, 10+10.

The input can be hundreds of numbers. Certainly I can't attempt every possibility. I was thinking about an "elegant" solution using prime factors. If my input is \[16, 30, 36, 40\], does it help me to think about this as \[2\*2\*2\*2, 2\*3\*5, 2\*2\*3\*3, 2\*2\*2\*5\]? I'm not sure. I've also thought about using the differences of each input, eg. \[16, 30, 36, 40\] would give me \[14, 6, 4, 20, 24, 10\], but I'm not sure how to use that either.

Any thoughts?

# Answer
It's NP complete, but you may have a chance in many practical cases, especially if you need to produce a lot of numbers in a not very large range. I'll call the numbers you want to produce "desired numbers", and assume that 1 is not one of the "desired numbers".

An important observation is that in any chain, performing an addition that produces one of the desired numbers is optimal. Therefore, we need only count the additions that don't produce one of the desired numbers (and if you want to produce 100 numbers from 1 to 200 those additions might be very few).

So instead of the initial set { 1 }, we add { 2 } if it is one of the desired numbers, then add 3 or 4 if they are among the desired numbers, and so on. If you wanted { 2, 3, 5, 6, 10, 19, 20, 21, 50 } then you start with the initial set { 1, 2 = 1+1, 3 = 2+1, 5 = 3+2, 6 = 5+1, 10 = 5+5, 20 = 10+10, 21 = 20+1 } and you only need to find 19 and 50.

Then each move consists of adding the sum of two numbers, and then adding all of the desired numbers that can now be produced. In the example, one move would be adding 16 and 19, another move adding 40 and 50. All this really cuts down on the number of possibilities you need to try out.

Some more ways to cut down on the possibilities: We can require that the non-desired numbers are produced in increasing order. So if you produced 2 and 4, you cannot produce the number 3 anymore. Or if you produced 2, 3, 5, you cannot produce the number 4 anymore - if you wanted it, you should have produced it earlier.

Obviously you don't ever produce a number larger than the highest desired number. Or higher than the highest desired number that wasn't produced yet. And all numbers greater than the highest desired number that wasn't produced yet must have been used producing one of the higher desired numbers.

And you cannot ever produce a number larger than the smallest desired number not found yet.

Apart from that, I cannot think of any "elegant" algorithm. I'd try all the possibilities, producing large numbers first, and of course stopping when you can prove you are not going to find a solution than the best so far.

Your example: \[16, 30, 36, 40\].

First attempt, always adding the largest number possible according to the rules: 2, 4, 8+16, 24, 28+30, 34+36+40. That's six moves, so you can try to find a better solution using five or fewer moves using backtracking. (Note that in move 4 and 5 we couldn't produce a number \> 30 according to the rules).

Producing 26 or 25 in step 5 doesn't help. In step 4, we could produce 20+36+40, 18+36+40, 17, 12, 10, 9. 20+36+40 can be followed by 28+30, so we found a better solution using five moves only (2, 4, 8+16, 20+36+40, 28+30). Now the goal is to find a chain with four or fewer extra additions.

2, 4, 8+16 doesn't give success with four extra additions. We can try 2, 4, 6 or 2, 4, 5 or 2, 3, 6 or 2, 3, 5 or 2, 3, 4 which all don't solve the problem in four moves. So (2, 4, 8+16, 20+36+40, 28+30) with five moves plus four moves adding the four desired numbers is an optimal solution.
> 1 votes

# Answer
You're looking for an algorithm to generate an addition chain that includes each of the specified numbers. As Wikipedia explains, the problem is NP-complete in general. However, there are approximation algorithms and heuristics. Searching for algorithms for computing addition chains should give you some candidate methods.
> 3 votes

# Answer
This is the addition sequence problem. You can transform the addition sequence problem into the vector addition chain problem as well. The best known algorithm for computing these is:

D. Bleichenbacher and A. Flammenkamp "An Efficient Algorithm for Computing Shortest Addition Chains"

This is unpublished but you can find it on the addition chain website:

http://wwwhomes.uni-bielefeld.de/achim/addition\_chain.html

You essentially need to write a function what will approximate (find a lower bound) the size of an addition sequence. For this I use the bounding sequences in this paper:

E. G. Thurber "Efficient Generation of Minimal Length Addition Chains", SIAM Journal of Computing, V. 28(4) 1999 pp 1247-1263.

Myself and Ed have an update to this paper with better bounds. Now you work in reverse with the algorithm of Flammenkamp etc by removing the largest element in the set and splitting it as per the paper. You then prune with known l(n) values that I have already calculated as well as using your lower bound for the addition sequence that is updated with the split values. You will need to understand the graph representation of addition chains to understand this algorithm. I have numerous unpublished updates to this algorithm in the code that I use. This is quite old work of mine as there are better approaches for the single number addition chain problem I study.
> 2 votes

---
Tags: algorithms
---


# Question
Title: Permutation of n-size array with possible repeated elements. E.g [1, 2, 1]
What would it be a recursive algorithm to get permutations for any list of **`n`** elements that might contain or not repeated elements?

For the following 3-element list `[1, 1, 2]` I would expect the following result:

```
[1, 1, 2]
[1, 2, 1]
[2, 1, 1]

```

So far I have the following result:

```
[1, 1, 2] <- duplicate
[1, 2, 1] <- duplicate
[1, 1, 2]
[1, 2, 1]
[2, 1, 1] <- duplicate
[2, 1, 1]

```

with algorithm below:

```
FUNCTION permute(array, nestingLevel) :
    FOR index = nestingLevel TO array size -1
        SWAP array[index] WITH array[nestingLevel]
        CALL permute (array, nestingLevel + 1)
        SWAP array[nestingLevel] WITH array[index]
    END FOR

    IF recursionNestingLevel EQUAL TO array size - 1
        PRINT array
    END IF
END FUNCTION

DEFINE array[] := 1, 1, 2
CALL permute (array, 0)

```

# Answer
> 2 votes
I will change your function a bit, because there is too much going on with swaps and there is variable `recursionNestingLevel` which is not really declared or needed.

```
FUNCTION permute(array, nestingLevel) :
    IF nestingLevel EQUAL TO array size
        PRINT array
        RETURN
    END IF

    CALL permute (array, nestingLevel + 1)

    SET index TO nestingLevel + 1
    WHILE index LESS THAN array size
        SWAP array[index] WITH array[nestingLevel]
        CALL permute (array, nestingLevel + 1)
        INCREMENT index BY 1
    ENDWHILE
END FUNCTION

DEFINE array[] := 1, 1, 2
CALL permute (array, 0)

```

Now there is a simple idea to prevent recursing over same elements - it eliminates first unnecessary swap of and all redundant calls when array\[index\] is equal array\[nesting level\]:

```
FUNCTION permute(array, nestingLevel) :
    IF nestingLevel EQUAL TO array size
        PRINT array
        RETURN
    END IF

    CALL permute (array, nestingLevel + 1)

    SET index TO nestingLevel + 1
    WHILE index LESS THAN array size
+       IF array[index] EQUAL array[nestingLevel] CONTINUE
+       array = CLONE array
        SWAP array[index] WITH array[nestingLevel]
        CALL permute (array, nestingLevel + 1)
        INCREMENT index BY 1
    ENDWHILE
END FUNCTION

DEFINE array[] := 1, 1, 2
CALL permute (array, 0)

```

CLONE here prevents passing by reference of array, which would propagate changes to every recursive call

When you prevent swapping same elements and calling permute, it effectively blocks call with same parameters, so there are no duplicates.
BTW I have tested this code, for `[1, 1, 2]` it yields `[ 1, 1, 2 ], [ 1, 2, 1 ], [ 2, 1, 1 ]`, with JavaScript

---
Tags: algorithms, data-structures, combinatorics, permutations
---