# Question
Title: Is there a reversible transform that reduces the number of distinct values?
The idea is to take a sequence like $\langle 1,2,3,4 \rangle$ and reduce it to something like $\langle 1,2,2,3 \rangle$, or something similar. The key point is that there are fewer distinct values $\\{1,2,3\\}$ vs $\\{1,2,3,4\\}$. In the case that the number of distinct values cannot be reduced, i.e. $\langle 0,0,0,0 \rangle$, it would output the same value $\langle 0,0,0,0 \rangle$. An algorithm that doesn't always decrease the number of distinct values is ok, as long as it doesn't *increase* the number of distinct values, or as long as it does so only rarely. The output sequence length can be less than or equal to the input sequence length, and the input sequence is bounded by $\[0,255\]$, but the output sequence need not be, though they should be integers in the range $(-\infty,+\infty)$. Another restriction on the input, if it helps at all, is that it's a restricted growth string. A property of restricted growth strings that might be useful is that the first $0$ in the sequence always comes before the first $1$, the first $1$ before the first $2$, and so on. So a valid sequence might look something like $\langle 0,0,1,0,2,1,1,0,2 \rangle$.

As an example, consider this simple algorithm. First, construct a "dictionary" from the input sequence consisting of all distinct values in the input. So, for the input sequence $\langle 1,2,2,3 \rangle$, the dictionary would be $\langle 1,2,3 \rangle$. It then iterates over the input, doing two things: replacing the input value with its position in the dictionary, and rotating the dictionary left by one. For most inputs, this will do little to reduce the number of distinct values, but for the input sequence $\langle 1,2,3,4 \rangle$, it will output $\langle 0,0,0,0 \rangle$. This can be inverted by applying a similar algorithm. Starting with the same dictionary, iterate over the output, successively replacing the values in the output with the value in the dictionary at that output value's index (that is, if $D$ is our dictionary and $i$ is a value in our output sequence, replace that value with $D\_i$) and then rotate the dictionary to the left by one.

# Answer
There are many reversible transformations that take a list of (let's say) non-negative integers and output a single integer. Here are two examples: $$ 2^{a\_1} \cdot 3^{a\_2} \cdot 5^{a\_3} \cdot 7^{a\_4} \cdot 11^{a\_5} \cdots \\ \langle a\_1, \langle a\_2, \langle a\_3, \ldots, \langle a\_{n-1}, a\_n \rangle \cdots \rangle, \quad \langle a,b \rangle = \binom{a+b+1}{2} + a. $$
> 10 votes

# Answer
What do you mean by "reduces the number of distinct values"?

* If you mean an invertible function whose input is, for example, $k$ things and whose output is fewer than $k$ things, the answer is yes. Yuval's answer gives two examples. Here's another example, which will make you laugh/cry/want to slap me/other (delete as applicable): the input is $k$ integers; the output is a list of those integers. There's just one list!
* If you mean an invertible function $f$ whose input ranges over some set $I$ and whose output ranges over some strictly smaller set $O$, then the answer is no. By the pigeonhole principle, there must be at least two distinct values $a,b\in I$ such that $f(a)=f(b)$, which means that the function cannot be invertible.
* If you mean something else, I'm gonna have to edit or delete this answer.
> 10 votes

# Answer
You're looking for a reversible function that takes a (long) list of integers in the range \[0,255\] and produces a very short list of integers in the range \[-infinity, infinity\]? Easy:

Add in base 255.

```
func(list)
  int result = 0
  for i = 0 => list.length
    result = (result * 256) + list[i]
  return result

```

... except that that loses leading 0s, so tweak the base and count inputs:

```
    result = (result * 256) + list[i] + 1

```

I mean, it's cheating, but func (a) will never produce more values than it was fed, and (b) can easily give you back the original list from the result. However, func will also (c) not work in the real world for any but the shortest of input lists.

If you want an actual list as the output, look for three or more duplicate values in a row; when you find one, output -1 * the count of identical values then a single copy of the value; eg:

{ 1, 2, 2, 3, 3, 3, 3, 4 } -\> { 1, 2, 2, -4, 3, 4 }

(you can do "two or more" instead of "3 or more", but you don't save anything on pairs)
> 2 votes

# Answer
If I understand the problem correctly, your aim is to reduce the entropy of the source sequence, by reducing the number of possible symbols. Then the closest thing you could do is apply a compression algorithm of your choice (LZMA, ZIP et al.). Modern compression leaves you with the minimal number of symbols neccesary to represent the *information* stored in the sequence.

If "reversible" means reversible with losses, see below. There are methods of approxization which might yield even greater savings if you allow for lossy compression.

What it will do is actually reduce the count of distinct patterns/numbers to the minimum possible amount, while maintaining the *information* that these numbers carry. If you discard this information (As I understand you did when transforming \<1, 2, 3, 4\> to \<1, 2, 2, 3\>), you will never ever be capable of reversing your transformation, unless you "cheat" by having this information hardcoded into your algorithm.

One example would be Entropy encoding, specifically MQ Coding, which I fathom would be adaptable, with some modifications, to work on integer granularity. A word of warning if you plan to use this in a commercial setting: There are patents pending on this method.

If a loss of information is acceptable, then you might use simple binning, but that is not reversible.

For certain special cases, you *might* be able to fit a mathematical function to your values, so you do not even need to maintain any list at all, just a number of parameters to that function, but as said, this only works in special cases (such as {1, 2, 3,4} - A linear function).

A possible option for more complex functions would be an approximization via (multiple) gaussian functions. When bounding the stored information to the list size, this will not be lossless however. Keyword: Radial Basis Function

*edit*

After reading your comment, I guess im way off the problem. But the way you ask for it is not possible. If each of your symbols has a different meaning, there is no reversible way in which you can reduce the number of symbols without discarding information. Any method you chose will have to rely on your sequence having a certain structure and will not be applicable every possible sequence.

Kudos to @minnmass. Why not invert his idea. If the list size does not matter, why aren't you just looking at individual bits? Then you only have two different values - 0 and 1. That does not really decrease entropy and would be reversible - just consume a bunch (8, 16, 32, whatever) of bits at once and you are back to your original representation.
> 1 votes

# Answer
Here's an interesting approach, based on the fact that my input is always a restricted growth string. Given the sequence $\langle a\_1, a\_2, ..., a\_n \rangle$, we know that $a\_{i+1} \leq max(a\_1,a\_2,...,a\_i)+1$. We can thus split our sequence into subsequences based on their greatest possible value. I.e., $\langle 0,1,0,1,1,2,1,0 \rangle$ would be split into $\langle 0 \rangle$, $\langle 1,0,1,1 \rangle$, and $\langle 2,1,1 \rangle$. The first sequence has a greatest possible value of $0$, the second of $1$, and the third of $2$. Since we know that each sequence will start with the greatest possible value, and may or may not contain lesser values, we may be able to reduce the number of distinct values by mapping each sequence to the range $\[1,-\infty)$ by changing the first value in the sequence to $1$ and subtracting the max value in the sequence from the remaining values.

The rationale for this is that if the range of a given subsequence is $\[n,m\]$, if $n$ is close to $m$, then there will be overlap between the values in this sequence and the previous sequence. For example, the three sequences $\langle 2,1,2,1 \rangle$, $\langle 3,2,3 \rangle$, and $\langle 4,3,3,4 \rangle$, would be mapped to $\langle 1,-1,0,-1 \rangle$, $\langle 1,-1,0 \rangle$, and $\langle 1,-1,-1,0 \rangle$, reducing the distinct values from $\\{1,2,3,4\\}$ to $\\{-1,0,1\\}$. The reason for always starting with $1$ is so that when we combine these subsequences back into one sequence we will be able to distinguish between subsequences, and thus be able to reconstruct the original sequence.

In practice this doesn't reduce the number of distinct values by very much. Also, in the worst case scenario it will increase the number of distinct values slightly.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Locality-sensitive hashing random projection
I'm trying to understand how the LSH works for Cosine Similarity metric. For instance, let's say you have $\vec{v} \in \mathbb{R}^d$ and the random vectors $\vec{r\_{i}} \sim \mathcal{N}(0, 1)^d$ that will be used for the random projection. So, in LSH for Cosine Similarity, the define the hash function $h\_i(\vec{v}) = 1$ only if $\vec{r\_i} \cdot \vec{v} \geq 0$ and $h\_i(\vec{v}) = 0$ only if $\vec{r\_i} \cdot \vec{v} \< 0$. There are a lot of places that mention that this dot product of $\vec{v}$ and $\vec{r\_i}$ means which side of the line (assuming a 2D dimension for instance) the point in question $\vec{v}$ is (negative for one side and positive for the other side), just like in the image below:

However, to my understanding, what will give which side of the line where the point $\vec{v}$ is, is the dot product of the norm of the $\vec{r\_i}$ (let's say that the norm is $\vec{n}$) and the vector $\vec{v}$, so the correct wouldn't be the equation $\vec{n\_i} \cdot \vec{v}$ instead of $\vec{r\_i} \cdot \vec{v}$ ?

# Answer
No. The statement you're reading is correct. Try working through an example (in 2 dimensions, i.e., $d=2$); pick specific values of $v$ and $r$, draw them on the picture, and see what happens. The set of points $v$ such that $v \cdot r = 0$ is a line; the set of points $v$ such that $v \cdot r \ge 0$ is a half-plane (e.g., the half-plane above that line).
> 3 votes

---
Tags: hash, linear-algebra, hashing
---


# Question
Title: Can integer linear programs have non-integer OPT solutions?
Why is it that **every** integer linear program has optimal solutions that are integers? At least in online text books, they are always integers. Can solutions of ILPs only be integers?

# Answer
Something that might be causing you confusion: "integer linear programming", *by definition*, restricts the variables to integer values.
Linear programming instances in which the input numbers are integers can easily have only non-integer solutions. Consider:

$\begin{cases} \begin{alignat}{1} 2 &\cdot x \le 1 \\\\[1.5ex\] -2 &\cdot x \le -1 \end{alignat} \end{cases}$
> 6 votes

---
Tags: optimization, integer-programming
---


# Question
Title: On proving NP-completeness by reduction to 3-partition problem
Consider a problem $X$ can be reduced to 3-partition problem. So, when 3-partition has a solution then $X$ has a solution. But if 3-partition does not have a solution, they $X$ may or may not have a solution. In this case, is it legal to say that the problem $X$ is np-complete?

# Answer
No, that doesn't prove **NP**-completeness.

1. The thing you describe isn't a reduction. It must be that the instance of $X$ has a solution if, and only if, the instance of 3-partition has a solution.
2. Reducing $X$ to 3-partition just proves that $X$ is in **NP**. To prove completeness, you need to reduce an **NP**-complete problem to $X$.

I suggest that you revise the basic concepts from your class notes, textbook or online resources.
> 3 votes

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


# Question
Title: Lamport’s fast mutual exclusion algorithm intuition
Here's Lamport’s fast mutual exclusion algorithm:

```
want[i]:=true
fast-lock:=i
if slow-lock<>0 then
     want[i]:=false
     while (slow-lock<>0) {//busy wait}
     goto 1
slow-lock:=i
if fast-lock <> i then
     want[i]:=false
     for j:=1 to n do:
       while (want[j] = true) {//busy wait}
     if slow-lock <> i then
         while (slow-lock <> 0) {//busy wait}
         goto 1
CS
slow-lock:=0
want[i]:=false

```

I understand why eventually all 4 criteria for mutual exclusion hold, but i dont understand the **intuition** behind this algorithm:

* In what sense are this locks fast/slow?
* What's the point, for example, after freeing the slow lock, go back to the **beginning** of the algorithm?

I tried to read this article, but it was to complex for me to understand.

# Answer
> In what sense are this locks fast/slow?

Lamport optimizes for a very specific scenario, as pointed out in the paper:

> The current belief among operating system designers is that contention for a critical section is rare in a well-designed system; most of the time, a process will be able to enter without having to wait.

The reasoning goes like this: Most of the time, only a single thread will attempt to get into the critical section. So the codepath that we should try to optimize is the one where the lock is readily available.

The case where there is actual contention on the critical section is considered exceptional. It is fine if the algorithm behaves less than ideal in that case - less than ideal here means, you will never let more than one process into the critical section, but if there's lots of contention, you might have to wait a long time (possibly forever) for your turn to enter the critical section.

To illustrate this point, let's take a look at a classic algorithm for mutual exclusion (coincidentally also by Lamport), the Bakery algorithm. Here, in a nutshell, a thread that wants to enter the critical section picks a number that represents its place in the waiting queue. The thread with the smallest number is at the front of the queue and can enter the critical section, all others have to wait. How do we determine whether we have the smallest number (and hence can enter the critical section)? We have to compare our number against the numbers of *all the other threads*. This means even if none of the other threads are in the queue at that time (no contention), we have to check the numbers of all the other threads. This is obviously not nice, as locking becomes more expensive as the number of threads increases.

The fast mutual exclusion avoids this: If there is no contention we check `slow-lock`, which is available. Then we check the `fast-lock`, which is also available and we enter the critical section. We only need two write operations and two read operations to get into the critical section, regardless of the number of threads.

> What's the point, for example, after freeing the slow lock, go back to the beginning of the algorithm?

It's the only safe thing to do. Remember, it is crucial that no more than one algorithm is allowed to enter the critical section. If we fail the `slow-lock` check, it means that some other thread might already be in the `fast-lock` check or even in the critical section. Thus we have to back off and restart from the beginning. We will keep doing this until the other thread has left the critical section, which will allow us to pass the check.
> 6 votes

---
Tags: algorithms, concurrency, mutual-exclusion
---


# Question
Title: Basic question about branches and pipelines
In which stage ( on an ideal 5-stage pipeline ) are branches and hazards handled? How much is the branch penalty for a branch hazard or data hazard. Is there different stages to find data hazards or branch hazards ( meaning for example branch hazards occurs on the 2th stage in the pipeline) or are all hazards detected at a specific stage?

# Answer
The classic RISC pipeline resolves branches in the decode stage, which means the branch resolution recurrence is two cycles long. More information can be found in the Wikipedia article on the Classic RISC pipeline.
> 2 votes

---
Tags: cpu-pipelines
---


# Question
Title: Can the unbounded knapsack problem be described as a matrix exponentiation?
It seems that the general approach to a dynamic programming problem is to formulate a recurrence relation and then either implement a top down recursive solution or a bottom up iterative solution.

But if there's a recurrence relation I think that means we could potentially represent the problem as a state vector and a matrix updates the state through a multiplication. This approach can be used to generate the Fibonacci sequence for example.

Can this linear algebra approach be applied generally to any dynamic programming problem such as the unbounded knapsack problem?

# Answer
For the Fibonacci sequence, the recurrence relation is *linear*. That's why it can be represented as a matrix representation, i.e., using linear algebra. If the recurrence relation isn't linear, you can't do something like that.

So, no, you can't always do that.
> 2 votes

---
Tags: dynamic-programming, linear-algebra, knapsack-problems
---


# Question
Title: Word Frequency with Ordering in O(n) Complexity
During an interview for a Java developer position, I was asked the following:

> Write a function that takes two params:
>
> 1. a String representing a text document and
> 2. an integer providing the number of items to return.
>
> Implement the function such that it returns a list of Strings ordered by word frequency, the most frequently occurring word first. Your solution should run in $O(n)$ time where $n$ is the number of characters in the document.

The following is what I answered (in pseudocode), it is not $O(n)$ but rather $O(n \log n)$ time because of the sort. I cannot figure out how to do it $O(n)$ time.

```
wordFrequencyMap = new HashMap<String, Integer>();
words = inputString.split(' ');

for (String word : words) {
  count = wordFrequencyMap.get(word);
  count = (count == null) ? 1 : ++count;
  wordFrequencyMap.put(word, count);
}

return wordFrequencyMap.sortByValue.keys

```

Does someone know or can someone give me some hints?

# Answer
> 13 votes
I suggest a variation of distribution counting:

1. Read the text and insert all the word encountered into a trie, maintaining in each node a count, how often the word represented by this node has occured. Additionally keep track of the highest word count say `maxWordCound` . -- $O(n)$
2. Initialize an array of size `maxWordCount`. Entry type are lists of strings. -- $O(n)$, since the count can't be higher.
3. Traverse the trie and for each node add the corresponding string to the array entry indicated by the count. -- $O(n)$, since the total length of strings is bounded by $n$.
4. Traverse the array in descending order and output the desired number of strings. -- $O(n)$, since that is a bound on both the size of and the amount of data in the array.

You can probably replace the trie by other data structures in the first phase.

# Answer
> 3 votes
Your algorithm does not even run in time $O(n \log n)$; inserting $\Theta(n)$ things in a hashtable costs time $\Omega(n^2)$ already (worst-case).

---

*What follows is **wrong**; I'm leaving it here for the time being for illustrative purposes.*

The following algorithm runs in worst-case time $O(n)$ (assuming an alphabet $\Sigma$ of constant size), $n$ the number of characters in the text.

1. Construct a suffix tree of the text, e.g. with Ukkonen's algorithm.

If the construction does not already do this, add the number of reachable leaves to every (inner) node.
2. Traverse the tree from the root and cut off all branches at the first (white)space.
3. Traverse the tree and sort the list of children of every node by their leaf counts.
4. The yield of the tree (leaves from left to right) is now a list of all words, sorted by frequency.

Regarding runtime:

1. Ukkonen's algorithm (in its enhanced form) runs in time $O(n)$; maintaining leaf counts does not increase the $\Theta$-cost of the algorithm.
2. We have to traverse one node per character of every word that occurs in the text. Since there are at most $n$ different word-character pairs, we visit at most $n$ nodes.
3. We visit at most $n$ nodes (cf 2.) and spend time $O(|\Sigma| \cdot \log |\Sigma|) = O(1)$ per node.
4. We can obtain the yield (which has of course size $O(n)$) by a simple traversal in time $O(n)$ (cf 2.).

More precise bounds can be obtained by parametrising runtime with the number of different words; if there are few, the tree is small after 2.

# Answer
> 3 votes
The gathering of occurrence counts is O(n), so the trick is really only finding the top k occurrence counts.

A heap is a common way to aggregate the top k values, although other methods can be used (see https://en.wikipedia.org/wiki/Partial\_sorting).

Assuming k is second param above, and that it's a constant in the problem statement (it appears to be):

1. Build a trie of words with occurrence counts on each node.
2. Initialize a heap of size k.
3. Traverse the trie and min-probe/insert each (leaf, occurrence-count) pair in the top-k heap.
4. Output the top k leaves and counts (this is actually kind of a pain because you need parent pointers to map each leaf back to a word).

Since the heap size is a constant, the heap operations are O(1), so step 3 is O(n).

The heap could also be maintained dynamically while building the trie.

# Answer
> 1 votes
Use a hash table (e.g., `HashMap`) to collect all words and their frequencies. Then, use counting sort to sort the words in order of decreasing frequency. Since all frequencies are integers in the range $1..n$, counting sort takes $O(n)$ time. The total expected running time is $O(n)$, which is more than likely more than sufficient for all practical purposes (unless the interviewer mentioned something that was left out of your question). Make sure to mention that this is *expected* running time rather than *worst-case* running time.

This might not be the answer that a teacher would be looking for in an algorithms class, because it is expected $O(n)$ running time rather than $O(n)$ worst-case running time. If you want to score extra points at the interview question, you can mention casually in an off-hand manner that of course this is expected running time, but it can also be done in $O(n)$ worst-case running time by replacing the hash table with a more sophisticated data structure -- and you'd be happy to elaborate on how you'd choose between algorithms in a situation like this.

Or, if you want to play it a bit safer, before giving an answer, first ask "do you care about the difference between expected $O(n)$ running time and worst-case $O(n)$ running time?". Then tailor your answer accordingly. Be prepared for the interviewer to ask *you* how you would choose, in practice. (If so, score! That's a question you should be able to hit out of the ballpark.)

# Answer
> 0 votes
**Hashtable based solution**

Not sure why hashtable makes the complexity $\Omega(n^2)$ if $n$ is the **number of characters** (not words).

If you iterate through every character in the document and as you are iterating, calculate the hashcode of the word, you will have gone through $n$ characters. That is, as soon as a letter is encountered, the word begins, so start computing hash until the word ends (there are some special cases for punctuation but those do not affect the complexity). For every word, once the hash is computed, add it to a hashtable. This is to avoid going over every word twice, i.e. first to iterate through the document to find the words and then to insert them in a hashtable, although the complexity in that case could also be $\Omega(n)$.

Collisions in the hashtable are surely a problem, and depending on how big the original hashtable was and how good the hashing algorithm is, one could approach close to $O(1)$ for insertions and keeping counts and thus $O(n)$ for the algorithm, although at the expense of memory. However, I still cannot appreciate how the worst case can be asserted to be $O(n^2)$ if $n$ is the number of characters.

The assumption is that the hashing algorithm is linear in time in relation to the number of characters.

**Radix sort based solution**

Alternatively, assuming English, since the length of the words is well-known, I would instead create a grid and apply radix sort which is $O(kN)$ where $k$ would be the maximum length of a word in the English language, and $N$ is the total number of words. Given $n$ is the number of characters in the document, and $k$ is a constant, asymptotically this amounts $O(n)$.

Now count the frequency of each word. Since the words are sorted, we will be comparing each word to its preceding word to see if it's the same one or different. If it's the same, we remove the word and add a count to the previous. If different, just make the count 1 and move on. This requires $2n$ comparisons where $n$ is the number of characters, and thus $O(n)$ in complexity as a whole.

The top few longest words in English are ridiculously long, but then one could cap the word length at a reasonable number (such as 30 or smaller) and truncate words accepting the margin of error that might come with it.

---
Tags: algorithms, sorting, strings, data-mining
---


# Question
Title: Stuck in converting finite automata to its corresponding regular expression
I'm trying to convert the following finite automata (DFA) to its corresponding regular expression using state elimination algorithm.

For this I'm following this link. The answer of that question has following example.

But in this sample automata, there is no state between the two looping transitions. For example there is no state between transition `q` to `r` and back `r` to `q`. But in my question, there is three such cases as mentioned in the above 1st diagram. For example there is a state `IV` between the transition `III` to `V` and back `V` to `III`, via `a`. For another example, there is three intermediate states between transition `I` to `V` and back `V` to `I` via `b`.

I've tried to search such case on INTERNET, but can't found such issue. I've tried to attempt this question and could eliminated the `II` state, as following:

I'm stuck in eliminating state `I`, `III` and `IV`. Suppose I remove state `III`, than where should the transition from `V` to `III` via `a` can be placed? If I eliminate state `IV`, what will happen to transition `IV` to `I`?

Is there any general method for this type of cases? Any help will be appreciated.

Thank you very much in advance!

# Answer
> 1 votes
Let's merge `IV`.

We have three edge transitions to consider:

* `IV` to `I`, consuming a `b` (1)
* `IV` to `V`, consuming an `a` (2)
* `III` to `IV`, consuming a `b` (3)

The only way I can enter state `IV` is via `III` (3). Hence, any state that can be reached from `IV` can also be reached from `III`.

Let's now look at the path `III -> IV -> I`, which is the concatenation of (3) and (1). Let's forget about states for a second and simply look at paths and the consumed symbols. There exists a path ((3),(1)) that allows us to get from `III` to `I` by consuming a `bb`.

Due to this fact, we can just add an edge `III` to `I` consuming a `bb` without changing the accepted language of the automaton. It's just a shortcut for the existing path. Once we added the edge, the original path is redundant. If I'm sitting at `III`, instead of walking the path (3),(1), I can just take the shortcut.

Once I have made all the paths redundant that pass through a state, the state itself becomes redundant and I can remove it along with all its edges.

We can apply the same logic to `III -> IV -> V`. This introduces a shortcut edge `III` to `V` consuming a `ba`.

With those two in place, we have covered all paths that pass through `IV`. You can easily enumerate all paths by taking the Cartesian product of incident and outgoing edges: I have a certain number of ways of reaching the state, and for each of those I have to consider all the possible ways of exiting the state again.

Now it's just rinse and repeat. Pick a state, enumerate all paths through it, insert shortcut edges that make all paths redundant and then remove the state along with all its edges.

The only thing to watch out for are loops. The answer you linked in your question should give you a good idea how to deal with those.

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


# Question
Title: Showing Regular Languages are closed under removal of rightmost character
"Show that if L is a regular language without the empty string, then the language in which the rightmost symbol of every string in is removed is also regular."

I tried going by closure properties of regular languages but got nowhere.. I said L' = {x| y is in L and xa = y, for some a in the alphabet} and didn't really know where to go from there... I also tried to argue that since L is a regular language, it can be expressed by some regex..and I wanted to show by cases that we can form a new regex by omitting the last unit of regex? But that seemed flawed. I also tried creating a skeleton dfa for L and just changing the set of accepting states to the states that transition into the previous final states.. I feel like there is a gap in my knowledge and would really appreciate it if someone could not only help me figure out the solution but also give me some advice on how to approach such problems and fill the gaps in my knowledge!

# Answer
This is just a special case of right quotient. Specifically, for a language $L$ over an alphabet $\Sigma$, this is $L / \Sigma$.

Many textbooks and course notes contain proof of regular languages' closure under right quotient. For example, here, on page 10.
> 5 votes

# Answer
Let's show this by transforming regular expression accepting $L$ over $\Sigma$ using function $T:X' \to X$, where $X$ is set of regular expressions, $X'$ is set of regular expressions not accepting empty words.

Smallest language not accepting empty word consists of single letter $a \in \Sigma$. In such case transformation is trivial:

$T(a) = \epsilon$

Now, if our regular expression is other regex starred, we apply transformation recursively (I will use dot to denote concatenation to distinguish it from $T$ application):

$T(R^\*) = R^\* \cdot T(R)$

In case regex is alternation, we go recursively into both regular expressions:

$T(R|S) = T(R)|T(S)$

Most tricky transformation is when we deal with concatenation, because we don't know if last character in word is accepted by first or second regex, we need to split this into 2 cases:

$$ T(R \cdot S) = \begin{cases} R \cdot T(S) & \text{when $ \epsilon \notin L(S) $} \\ T(R)|R \cdot T(S) & \text{when $ \epsilon \in L(S) $} \end{cases} $$

And that's it :) Proof of correctess is inductive over regex structure.
> 3 votes

---
Tags: regular-languages, finite-automata, regular-expressions, closure-properties
---


# Question
Title: Is the relation between the input and output of an arbitrary algorithm describable by a mathematical function?
I hope that this question is clear, and not off-topic:

I have been reading about neural networks (in the AI sense), and the textbook said that an artificial neural network can always be described by a single mathematical function (rather than by an "algorithm" in a register-machine, which is the standard way I intuitively look at an AI neural network).

So this made me think: is it possible for any arbitrary algorithm, meaning an arbitrary Turing machine, to be simulated by a **mathematical** function? (I do **not** mean a function as used in programming languages).

By simulated in this case I mean that given any arbitrary input in the algorithm, that function produces the same output as the algorithm.

# Answer
> 8 votes
Suppose $M$ is a Turing machine which halts for all inputs $x\in\Sigma^\*$, then we can define the corresponding function $f\_M$ in the following way:

$$ f\_M(x) = \begin{cases} 1, & \text{M accepts x} \\ 0, & \text{otherwise} \end{cases} \quad $$

$f\_M(x)$ is a legitimate mathematical function from $\Sigma^\*$ to $\left\\{0,1\right\\}$, it does not care about concepts such as "machine" or "algorithm" or any implementation you have in mind. Obviously the function $f\_M$ was tailored for the machine $M$, but this does not make it illegitimate in any way.

You could ask whether i can describe the output of $M$ using a simple function? Perhaps using only the four basic arithmetical operations (we can treat the input strings as numbers represented in binary). The term you should look up in this regard is expressibility, what functions can your model express? For example, when talking about neural nets, the more neurons we use, the bigger our expressive power gets (we can implement more functions).

Note that the converse is not true, not every function can be described by a Turing machine (look up the arithmetical hierarchy, a famous example is the halting problem, but we got a whole hierarchy of even "harder" functions).

# Answer
> 2 votes
You may be interested in $\mu$-recursive functions. These are a notion of formalizing mathematical functions in terms of a few extremely simple basic operations. The idea predates Turing Machines and was used by Gödel for the incompleteness theorems.

The short story is that once Turing introduced his Machines, it was shown that they are exactly equivalent in what they can compute to the $\mu$-recursive functions. So for any Turing machine, you can write down a $\mu$-recursive "formula" that computes the same thing.

However, $\mu$-recursive functions may not capture the intuition you're going for. They have some power that ordinary mathematical functions we usually write down do not. In particular they have a recursion operator, which is necessary to get anything like a loop. Without such a structure in our math, our functions will not be able to match Turing machines. The other advanced operator is a minimization one, but this is actually pretty natural in math notation.

A final note: you should be sure to separate in your head the idea of a "function" and of a "formula". A function is just a list of an output for each possible input. It does not have to be write-down-able or computable. By contrast, a formula or algorithm give an explicit method for computing a particular function. We know that the set of functions having algorithms is much smaller than all functions, and we also know that the number of formulae we can write down in a given number of characters is much smaller than all functions too.

Another small caveat is that dealing with actual real numbers and operations like $\sin$ is difficult and hairy with Turing Machines and computability; that's a whole 'nother issue.

# Answer
> 1 votes
Based on your comment to the existing answer:

> Ah, I didn't think of that \[piecewise\] way of defining the function. This makes the problem trivial, indeed. What I should have asked was: is an arbitrary algorithm describable by a function without conditionals, and only using standard operations like +,-,\*,/,^,sin,cos, etc?

No, not for *arbitrary* algorithms. However, **piecewise functions that are otherwise algebraic, can be encoded in algebra.**

All you need is absolute value. It is a little clunky, but it is completely possible.

Take the piecewise function:

If x \> 5, sine x, otherwise, 0. (Undefined at x = 5.)

You can encode this into standard algebra as follows:

f(x) = (sin x)(|x-5|+(x-5))/(2x-10)

The fractional part is equal to 1 when x is greater than 5, equal to 0 when x is less than 5, and is undefined when x equals five.

I have used this principle (just for fun) to write single equations—using just plain algebra—whose graphs when displayed on a graphing calculator, spelled out whole sentences. (This was using implicit equations, of course, not functions.)

Footnote: The Pacific Tech Graphing Calculator is the best of its kind and was indispensible for the actual graphing. (I'm not affiliated in any way.)

# Answer
> 1 votes
A computer program indeed implements a function, i.e. it maps to the input values to some uniquely defined output values. There are two exceptions to be considered:

* a program can be nondeterministic, meaning that different runs won't generate the same output;
* a program may fail to terminate, meaning that you are outside the domain of definition.

There is a trivial way to define that function mathematically, as the set of all pairs $(i,o)$ where $i$ is an input that causes the program to terminate, and $o$ the corresponding output.

Often an algorithm has a useful purpose and implements a relatively simple function that can be described in comprehension rather than in extension. For example, the Euclidean algorithm corresponds to the function $a,b\in\mathbb N\to\gcd(a,b)$.

Another interesting example is the Syracuse algorithm, which transforms an even number in its half, and an odd number in its triple plus one, and repeats until the value one is reached. Even though we still don't know the domain of this function, it is still a plain function, from some subset of $\mathbb N$ to $\text{true}$.

---
Tags: algorithms, turing-machines
---


# Question
Title: A question on decidable formal languages and turing machines
Let $L' \subseteq L \subseteq \Sigma^\*$ be decidable languages with deterministic Turing machines $M'$ and $M$ which decide the languages. Typically we have $t\_M(w) \le t\_{M'}(w)$ for all $w \in \Sigma^\*$, where $t\_M(w)$ is the time of $M$ on input $w$.

Suppose furthermore that $M$ and $M'$ have minimum length when interpreted on some chosen universal Turing machine $U$. So if $M''$ decides $L'$ then $l(M'')\ge l(M')$ where $l(M)$ is the length of $M$ when interpreted on $U$.

Is this just a coincidence of the chosen Turing machines, or does this property hold for all deciders of $L$ and $L'$ with minimum length?

"Typically" here means the following situation:

For instance if $L'$ is a decision problem on graphs and $L$ is the language of graphs (meaning that words correspond to adjacency matrix of a directed graph), then first for a word $w\in \Sigma^\*$ one must decide if this word corresponds to an adjacency matrix of a graph, then decide if that graph has the property one is looking for. If you know a counterexample to that, that would also answer the question.

# Answer
> 0 votes
We can make the relationship between $t\_M$ and $t\_{M^\prime}$ quite arbitrary. For example, consider $L$ the language of strings that encode a prime number, and $L^\prime$ the language of strings that encode either a prime number, or a satisfiable formula. Then $t\_M\<t\_{M^\prime}$ if **P$\not=$NP**. On the other hand, if we choose $L^\prime=\Sigma^{\star}$, then $t\_{M^\prime}\<t\_{M}$.

# Answer
> 5 votes
A counterexample is choosing L' as the empty language. That can be decided faster than most other languages.

---
Tags: formal-languages, turing-machines
---


title: Are numbers types and what is "Number"?

text:
# Question
Title: Are numbers types and what is "Number"?
I was pondering about what are the numbers. It seems like a number is data type. I mean, like Maybe in Haskell. Because, for instance, one on its own means nothing for me. However, one apple tells me about how many apples does one talking about. Thus, numbers are quite abstract. If somebody asks you "how is it going" you can't answer "10". 10 what? But you could say 10 out of 10. But this is another abstraction. So, what I want to say is that a number is an abstraction. It can only be used to quantify other things. Thus, very often people say that "Number" is a type or set or category, etc. But then if a concrete number is an abstraction what is Number?

I hope you've got my idea and question and sorry if I used some terms incorrectly. I'm trying to study CS on my own and do make lots of mistakes.

# Answer
So, you have to be very careful to distinguish values, and the types of those values.

We say $v : T$ when $v$ is a value with type $T$.

## The type Number

When people say "Number" is a type, usually they're referring to the type of natural numbers. But each number isn't a type, it's a value, and $Number$ is their type. So we can say $1 : Number$, $2 : Number$, etc.

Notation isn't always consistent. Sometimes people will refer to $Number$ as a type class that contains $Nat, Int, Float$ etc. But that's more complicated.

Now, as for each number being a type, in a language like Haskell (or any Hindley-Milner lanugage), this isn't the case, because numbers are values, and types and values are separate.

But there are a few ways we can look at this

## Numbers as singletons

But using dependent-types or GADTs, in a Haskell, Agda, Idris, or other languages with advanced types, you can form a type like this (using Agda-like pseudocode):

```
data TypeNat : Nat -> Set where
  TZero : TypeNat Zero
  TSucc : {n : Nat} -> TypeNat n -> TypeNat (Succ n)

```

For any number `n`, `TypeNat n` is a type, containing exactly one value, the `TypeNat` representation of `n`.

So here, the number isn't the type, but there's a 1:1 correspondence between the numbers and the types.

## Numbers to Quantify other things

We can use numbers to quantify things, but in a dependent-type system, usually this is done by indexing types.

So you can have a type like `Vec a n`, which is the type of Vectors containing exactly `n` elements of type `a`. So here, our types are indexed by numbers, but the number itself is not a type.
> 8 votes

---
Tags: data-structures, mathematical-foundations, abstract-data-types
---


title: Kleene star of L

text:
# Question
Title: Kleene star of L
$L^\*$ is the kleene star of L.

say we have a def: $L^\*$ = $L^0$ U $L^1$ U $L^2$ U ... U $L^K$

then prove that: $L^\*$ = $L$ if and only if $L$ = $L$ o $L$

how do i prove this?

# Answer
> 0 votes
Here are some hints. Start with

**Lemma**. If $L=L\circ L$, then $\epsilon\in L$.

**Proof**. By contradiction: consider a string $y\in L$ of minimal length and assume to the contrary that $|y|\>0$, then show that $y$ cannot be in $L\circ L$, contradicting the assertion $L=L\circ L$.

Now show that $L=L\circ L\Longleftrightarrow L^\*=L$:

$(\Rightarrow)$: If $L=L\circ L$, then since $L^\*=\\{\epsilon\\}\cup L \cup (L\circ L)\cup (L\circ L\circ L)\cup\dotsc$ by definition, we can show that $L^\*=L$ by observing, first, that all the terms $L\circ L, L\circ L\circ L, \dotsc$ are equal to $L$ and, second, that $\epsilon\in L$ by our lemma, so $L^\*=L$.

$(\Leftarrow)$: Now assume $L^\*= L$; we'll show $L=L\circ L$

$\quad(L\subseteq L\circ L)$: Since $\epsilon\in L^\*$, we know $\epsilon\in L$ (why?), so $L=\\{\epsilon\\}\circ L\subseteq L\circ L$.

$\quad(L\circ L\subseteq L)$: Trivial. Left to the reader.

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


# Question
Title: What class of problems does this problem belong to
I recently took a test and I had a particularly difficult time with one problem. I would like to know more about this problem: what general class of problems does this problem belong to, what are some good resources to learn more about this class of problems, how should I have recognized the problem for what it was?

So here is the problem, distilled down to its essential components.

You have a task you are trying to accomplish. There are `n` different ways to to accomplish that task but each approach has a cost and probability of success associated with it. The problem is to figure out how to order your attempts at the task so that the average cost is minimized.

There is a small twist, if all but your last attempt has failed then you are guaranteed success on your last attempt regardless of the probability of success associated with it.

So here is a concrete example. The following list of tuples represents three ways to complete a task. The first value is the cost and the second value is the probability of success:

`[(10,0.5),(8,0.25),(5,0.2)]`

One possible order would be `[0,1,2]` (each value is the index of an attempt in the above list).

That has an average cost of:

`0.5*10 + (1-0.5)*0.25*(10+8) + (1-0.5)(1-0.25)(10+8+5) = 8.975`

But the optimal order is `[0,2,1]`:

`0.5*10 + (1-0.5)*0.2*(10+5) + (1-0.5)(1-0.2)(10+8+5) = 8.8`

The obvious way to solve this problem is to simply try every possible order but that has a runtime of O(n!). What you are supposed to know is that by dividing the cost by the probability and sorting the list using that value as the key you will get the optimal order.

I did figure that out eventually but it was not obvious to me at all, I went down a long and winding route and hit many dead ends before I arrived at that solution. So what was the trick here to quickly come to this conclusion?

# Answer
> 4 votes
The algorithm that you have found is an example of a "greedy algorithm". When trying to find an algorithm for a problem there is a small bag of standard tricks that you can use but these are quite limited and for most problems, there's no easy solution: you have to "go down the long and winding route".

The trick here was to recognize that this problem has a property known as "optimal substructure": a solution to the problem consists of making some top-level choice, and then solving a smaller subproblem. The optimal substructure property states that any optimal solution consists of a top-level choice, and then an optimal solution to the subproblem (the way to solve the subproblem does not depend on previous choices).

If your problem has optimal substructure you can try solving it with dynamic programming (but that does not give a polynomial algorithm here because the problem does not have sufficient overlap between subproblems). Another option is using a greedy strategy, which happens to work here. The greedy strategy is (simply put): define some criterion by which to pick the locally "best" top-level choice and do not consider the possibility of making any choice.

In this case, the "right" criterion apparently is the expected cost of accomplishing that task by using that method. This intuitively makes sense (the option with highest success/cost ratio should be the one you try first) but to show that this choice indeed results in an optimal order, you have to show that the problem, coupled with this criterion, satisfies the "greedy choice property": any solution that does not use the "best" choice, can be modified to a solution that uses the "best" choice and whose objective value is at least as good or better as the objective of the solution that does not use the "best" choice. You can usually show this by some sort of exchange argument ("suppose the solution does not start with the best success/cost ratio, consider what happens if we swap the first step in the solution with the best success/cost ratio one, then the objective can only improve,...")

# Answer
> 3 votes
Assume no method is free: If some methods are free, you try all the free methods first obviously, and you are left with a problem without free methods.

Assume you have only n = 2 methods. Method 1 costs x and works with probability p. Method 2 costs y and works with probability q. The cost will be x+y if you have bad luck and your first attempt fails. If you use method 1, there's a probability p that you save y from the worst case cost. If you use method 2, there's a probability q that you save x from the worst case cost. You chose method 1 if the expected saving is greater, that is if p * y ≥ q * x or p / x ≥ q / y.

Assume you have more than n = 2 methods. Again, assume Method 1 costs x and works with probability p, and method 2 costs y and works with probability q. Assume you want to try these two methods first. No matter which one you try first, the probability of failure using both methods, the cost of trying both methods, and the cost of accomplishing the task after both methods failed, is the same - so we can ignore this. But now we only need to optimise the cost of using one or both methods, and the analysis is exactly the same as in the case n = 2 above. So if we decided to start with method 1 and 2 in unspecified order, we should start with method 1 if p / x ≥ q / y.

This doesn't apply to method 1 and 2 only: Whatever two methods we use first, we should try the one with the higher ratio (probability of success) / (cost of attempt) first. After trying one method, we have exactly the same problem except that n is now smaller by one and the method we just tried is not available anymore.

Therefore, if we decide to attempt methods 1 to n in any order, an optimal order will have the property that for any two methods that we use in turn, we should try the one with a bigger ratio (probability of success) / (cost of attempt) first. That means we find the optimal solution by sorting all methods according to that ratio, with the highest ratio first. So we found a very simple solution to this problem.

The problem is altogether different and much harder if the probabilities for success or the cost are not independent. The cost of method A might be lower if we tried method B first (because some of the work in method B can be used for method B) and vice versa. Or method A might be more likely or less likely to succeed if method B has already failed.

---
Tags: complexity-theory, optimization
---


# Question
Title: Is it undecidable if the language of a given Turing Machine is the set of composite numbers?
I am aware that the following problems are undecidable and tried to reduce the given problem to one of the following but with no success:

1. Halting problem
2. Blank Tape Halting problem
3. State-Entry problem
4. If a TM accepts nothing
5. If a TM accepts everything

I am looking for hints :)

Do I have to make multiple reductions?

Do I have to make a contradictory argument like we do for the Halting Problem?

# Answer
Hint 1: Do you know Rice's theorem? It's the go-to result for any version of "Prove it's undecidable whether $L(M) =\\,$ something."

Hint 2: You can reduce from "Does this TM accept everything?" You're given a Turing machine $M$ and you want to produce a new machine $T$ such that $T$ accepts the set of composites iff $L(M)=\Sigma^\*$. Have $T$ reject its input if it's prime. If the input is composite, use its factors to decide what input you'll feed to $M$. You need to do this in a way that every possible input to $M$ corresponds to some combination of factors of $T$'s input.

Hint 2.5: Alternatively, go from "Does this TM accept nothing?" Similar idea but now $T$ will accept if its input is composite and you'll use prime inputs to $T$ to code inputs to $M$. Actually, this one might be slightly easier to see.
> 5 votes

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


# Question
Title: Question about branch hazards on 4-stage pipeline
Let's say that conditional branches are resolved at the 2nd-stage on a 4-stage pipeline. Why is there different penalties on a taken branch versus an untaken branch ? Should the penalty be the same for both? I always assumed that the not taken and taken branch penalty is 2 cycles but this is incorrect according to my friend. Could someone clarify this ?

# Answer
> 0 votes
Ideally there are two possible branch outcomes which are unconditional and conditional branches.Conditional branches normally include a branch that can either be taken or not taken. Unconditional branches are usually known as jump or goto instructions.

**Jump instructions in a 4-stage pipeline**

Assuming that jumps can be resolved on the 2nd-stage (for a normal IF,ID,EX,WB) and that 1th-stage can always be done independently. This as a penalty will include 1 stall cycle. The main reason is simply because the pipeline fetches the next instruction following the jump(IF must update the PC , and the next sequential address is the only address known at this point). Now at the 2-stage when the jump resolves and realizes that the the fetch it issued was awrong address . The scenario will change,meaning that the pipeline will re-issue the fetch of the available instruction in the next cycle ( i + 1 ) causing *one-cycle stall*.

**branch instructions taken in a 4-stage pipeline**

Assuming that branches are resolved at the 3th-stage the pipeline then realizes taht it must reissue the fetch for the next instruction ( assuming the next instruction is not directly the branch) thus creating *two-cycle stalls*.

**branch instructions not-taken in a 4-stage pipeline**

For not taken branches the fetched instruction that is after the branch is actually correct because the branch is false ( meaning the instruction after it will execute). Mentioning that branches are resolved at the 3th-stage the pipeline then realizes that it doenst have to reissue the fetch and can therefore resume execution the instruction that was fetched after the branch. However the branch instruction cannot leave the 1th-stage (IF) since it has to resolve the branch thus including a penalty *of 1 cycle*.

Here is a picture showing every scenario:

---
Tags: cpu-pipelines
---


title: Packing chocolate boxes

text:
# Question
Title: Packing chocolate boxes
I've been trying to solve an interesting problem created by one of my friends. The following is the problem statement:

There are $n$ types of chocolates. $\langle a\_1,a\_2,a\_3....a\_n \rangle$ are positive integers which represent the number of chocolates of each type. These chocolates must be packed into boxes of capacity $k$ i.e. each box can contain at most $k$ chocolates. Also no box can contain two chocolates of the same type i.e. the chocolates in every box must be of distinct types. What is the minimum number of boxes needed to pack all the chocolates?

A greedy approach would be to iteratively fill boxes by picking chocolates from the top $k$ types (in terms of number of remaining chocolates). However this is not of polynomial time complexity.

I also tried to solve the decision version of the problem. (can the chocolates be packed using $m$ boxes ?). I was able to model it as a max flow problem but the number of vertices was not polynomial in the input size.

Is this problem NP-Complete? If not what would be a good polynomial time algorithm to solve it?

# Answer
The greedy algorithm will find an optimal solution: As long as there are more than k different chocolates, fill a box with one each of the k chocolates where the most pieces are left. Then as long as there are any chocolates left, fill a box with one of each of the chocolates. That solution is linear in the number of chocolate pieces but unfortunately not linear in the problem size. So instead of doing the greedy algorithm, we simulate how it would run and calculate how many boxes would be filled, in polynomial time.

Let $x\_i$ be the number of pieces of type $a\_i$. Sort in descending order, then remove the chocolates where $x\_i$ = 0. If n ≤ k you need $x\_1$ boxes.

As long as $x\_k$ \> $x\_{k+1}$ you would put chocolates $a\_1$ to $a\_k$ into a box. This fills $x\_k - x\_{k+1}$ boxes, and you decrease $x\_1$ to $x\_k$ by $x\_k - x\_{k+1}$. You simulate this in constant time.

After that you have $x\_1$ to $x\_j$ greater than $x\_k$, and $x\_{j+1}$ to $x\_m$ equal to $x\_k$, for some j \< k and m \> k. So you have a larger number of j chocolates, and an equal number of m-j chocolates, m \> k. You would fill m-j boxes by putting m-j of the chocolates $a\_1$ to $a\_j$ into each box, and filling with k-j of the chocolates $a\_{j+1}$ to $a\_m$.

You would do that t times. t is limited: With each round of m-j boxes, the number of the top j chocolates is reduced by m-j, the next chocolates are reduced by k-j. The difference is reduced by t (m-k), so t ≤ $(x\_j - x\_{j+1}) / (m-k)$. The next chocolates are reduced by t (k-j), so t ≤ $(x\_m - x\_{m+1}) / (k-j)$, letting $x\_{m+1} = 0$ if m = n. You take the largest possible t and simulate t (m-j) steps in constant time.

When this is done (and t may be 0) we remove all chocolates with a zero count, and we may be done. If not, then we do one simulation step which will change the situation, and start all over.

That's the idea. You can probably clean this up a bit.
> 1 votes

---
Tags: algorithms, complexity-theory, optimization, time-complexity, packing
---


# Question
Title: Bin-packing satisfiability rather than minimization
Here's a problem I need to solve that's clearly related to the standard bin-packing problem, but I'm not sure how to approach it.

Suppose you have some finite set of bins $B$, and each $b\_i \in B$ has some integer capacity $\mathit{cap}(b\_i)$. You also have some set of items $L$ where each item $l\_j \in L$ has some integer volume $vol(l\_j)$. The question is, is there some way of assigning each item in $L$ to some bin in $B$ where no bin is overful, i.e. to find any total mapping $M : L \rightarrow B$ such that $\forall b\_i \in B$, the sum of all $vol(l\_j)$ with $M(l\_j) = b\_i$ is less than $cap(b\_i)$.

The notable differences from the classic bin-packing problem are: first, we have only a finite set of bins, not an infinite number of bins to draw from. Second, we have no notion of cost; we only want to find *some* total mapping or determine that no such mapping exists. Third, bins are not homogeneous; we might have one bin with capacity 5 and another with capacity 10.

I'm not sure how to approach this problem or whether standard bin-packing approaches can be adapted to work with it. What is a good algorithm for answering the question?

For extra credit, there are a few extra bells and whistles that I would like to add, though these are optional:

* Add a constraint that some bins can only contain a maximum *number* of items as well as having a volume limit
* Some bins may have a minimum per item volume as well as a maximum volume; i.e. you don't have to put an item in the bin, but if you that item must have at least a given volume

# Answer
> 1 votes
Having a fixed number of bins makes little difference. If you use sorted-first-fit for example, the only difference is that the algorithm can fail. On the other hand, if you use a better algorithm for bin-packing (one that considers all bins *before* it is proven that they are all needed), you would find a trivial lower bound l for the number of bins, try to fit them all, and if it fails increase l by 1 and start all over again.

The different sizes make the problem likely harder to solve. For example, if you only wanted to decide which bin contains the largest item, that would in normal bin packing be no problem: Just put it into the first bin; it doesn't matter which one. With different bin sizes, pick all the bins that are big enough, remove duplicates with the same size, and try putting it into each of these bins. So you have more possible combinations. (If you had 100 bins of size 10 and 100 bins of size 5, then items of size 6 would be no problem, but a largest item of size 5 or smaller would be put into one of two bins).

I say "likely harder" because in the extreme you might have items that fit into one bin only.

Once you try to find an optimal solution using brute force, any additional restrictions make it easier because they remove possibilities from the search tree.

---
Tags: algorithms, packing
---


# Question
Title: Is a TM that is simulated by a universal TM theoretically inherently slower than the TM itself?
When a CPU simulates a certain program, as they do all the time, this is inherently slower than if the program would have been "baked in" into the hardware and computed directly. We know this from practical experience.

My question is: Is there some theoretical relationship that shows that a program that is simulated by a universal program, is inherently slower than that program executed by itself?

# Answer
The way i see it, talking about slowdowns on simulations of a specific Turing machine $M\_0$ doesn't make much sense. I could always just run $M\_0$ and call this a simulation, which will result in no slowdown. I could also hardwire the code of $M\_0$ , and in case the input was $M\_0$, use some better algorithm (as D.W. did in his answer).

The more interesting question here is (in my opinion at least), what is the optimal slowdown achievable when simulating an arbitrary Turing machine $M$ on some input $x$ ? (asymptotically, in terms of $|x|$ and the length of the description of $M$)

We look at all possible inputs, and examine the worst case slowdown (perhaps for some machine $M\_0$ you can do a better job, but here we consider the worst case running time).

More formally, Let $\mathcal{U}(\langle M\rangle,x)$ denote the universal Turing machine, which takes as input an encoding of a machine $M$ and some string $x$, and outputs $M(x)$, or does not halt in the case that the computation of $M$ on $x$ does not halt. We know that we can implement $\mathcal{U}$ in such a way that if the computation $M(x)$ requires time $T$, then $\mathcal{U}(\langle M\rangle,x)$ requires time $O\left(T\log T\right)$. Here the $O$ notation hides constants which depend on the number of states and the alphabet size of $M$ (but independent of $|x|$). Your question then translates to whether we can implement $\mathcal{U}$ such that the computation of $\mathcal{U}(\langle M\rangle,x)$ requires only $O(T)$ time?

It seems that for single tape machines, it is not known whether this $\log T$ factor is necessary, however for $k\ge 2$ tapes machines we can avoid it (proved by Furer, 1982). See this post by Kaveh for a detailed discussion and related quotes.
> 4 votes

# Answer
No. There is no such proof. There exists a universal Turing machine $U$ and a machine $M\_0$ such that $U$ simulating $M\_0$ is *faster* than running $M\_0$ directly.

For instance, $M\_0$ might implement sorting using a bubble sort. $U$ might be a universal Turing machine that has an extra check: it checks its input, and if its input is exactly $M\_0$ (it has the source code of $M\_0$ hardcoded and it checks for that one particular string on its input), then instead of simulating $M\_0$ step-by-step, it instead branches to execute Turing machine $M\_1$, which is a faster version of $M\_0$ (e.g., using mergesort instead of bubble sort) that otherwise has the same behavior. Such a $U$ is universal and has the property I articulated above.

Bottom line: No, simulation by a universal Turing machine is not necessarily slower than running the Turing machine itself. There is no such theorem.

---

That said, I don't see why you need such a theorem. As you said, we all know that simulation is typically slower than direct execution. That ought to be enough.
> 3 votes

---
Tags: turing-machines, computation-models, efficiency, simulation
---


# Question
Title: Finding a maximum-weight base of a a matroid, in reverse
Given a weighted matroid with positive weights, we can find a independent set with a maximum weight with a greedy algorithm:

* Start with an empty set (by definition of matroid, it is independent).
* Add an element with maximum weight among all elements whose addition keeps the current set independent (if there are no such elements, terminate).

My goal is to found out whether this approach can also work in reverse. My first attempt was:

* Start with a set containing all elements.
* As long as the set is NOT independent, remove the element with minimum weight.

This attempt proved to be false. Here is an example:

There are 8 elements, divided to two groups: A and B. The matroid contains all subsets that have at most two elements of each group. The weights are:

* Group A: 303,302,301,300.
* Group B: 203,202,201,200.

The forward-greedy approach picks 303, 302, 203, 202 - which is optimal. But the reverse-greedy approach removes 200,201,202,203,300,301, and leaves only 302,303.

But, I think the following alternative algorithm should work:

* Start with a set containing all elements.
* As long as the set is not independent, remove the element with minimum weight *among all elements whose removal leaves a base in the current set*.

So, in the above example, this algorithm removes 200 and 201, but does not remove 202 and 203 (since then no base will remain), then removes 300 and 301, and stops with the maximum-weight independent set.

I am not sure about the complexity of this algorithm. Particularly, how much time does it take to calculate whether the current set (after removing an element) contains a base?

# Answer
> 2 votes
Let $M$ be a matroid with non-negative weight function $w$ and rank function $r$ (the rank of a set of points $S \subseteq M$ is the maximal size of an independent subset of $S$). Suppose that the matroid has rank $m$. You propose the following algorithm:

1. $S = M$.
2. While $|S| \> m$: remove from $S$ a minimum weight element $x$ such that $r(S-x) = m$.
3. Return $S$.

This algorithm clearly returns a base. Let $W(S)$ denote the maximum weight of an independent subset of $S$. We prove by induction on the steps of the algorithm that $W(S) = W(M)$. The base case is clear. For the inductive step, suppose that $S$ contains a base $B$ of weight $W(M)$, and suppose that we removed an element $x \in S$ to obtain the new set $S'$. If $x \notin B$ then clearly $W(S') = W(M)$. Otherwise, let $B'$ be a base contained in $S'$ (which exists by the definition of the algorithm). Since $|B'| \> |B-x|$, there exists an element $y \in B' \setminus B$ such that $B'' = B-x+y$ is a base. By definition, $w(y) \geq w(x)$, and so $$W(S') \geq w(B'') = w(B)-w(x)+w(y) \geq w(B) = W(M),$$ completing the proof.

---

Answering your question, it is a classical result that the rank function can be computed efficiently using an independence oracle. Perhaps you can come up with the algorithm.

---
Tags: optimization, combinatorics, greedy-algorithms, matroids
---


title: Can a heap have no elements?

text:
# Question
Title: Can a heap have no elements?
Is it correct to call something with no elements a binary heap? I think it is correct, for one element too, but I'm not sure. It seems to satisfy the definition (from Wikipedia):

> Shape property: a binary heap is a complete binary tree; that is, all levels of the tree, except possibly the last one (deepest) are fully filled, and, if the last level of the tree is not complete, the nodes of that level are filled from left to right.
>
> Heap property: the key stored in each node is either greater than or equal to or less than or equal to the keys in the node's children, according to some total order.

# Answer
It's up to you to decide. It's a pathological case which is quite similar to the empty graph (on zero vertices) — sometimes it makes sense to admit it, and sometimes not. It depends on the circumstances. The definition in Wikipedia is irrelevant here — there are many other similar definitions in the literature, that might disagree on this point.

I recommend the classic article Is the null-graph a pointless concept by Harary and Read.
> 3 votes

---
Tags: data-structures, heaps
---


# Question
Title: Number of submatrices with a particular sum- Answer Explantion
I read Evgeny Kluev answer on this and was not able to understand the mechanism. Now let us understand using an example. let us say we have this matrix.

```
[1  2  3  2   5,
 2  4  6  4  10,
 3  6  9  6  15,
 2  4  6  4  10,
 5  10 15 10 25]

```

Now applying step 1 we get .

```
[ 1  2  3  2  5 ,
  3  6  9  6  15,
  6  12 18 12 30,
  8  16 24 16 40,
  13 26 39 26 65]

```

Now applying step 2 we get all the possible pair of row indices i.e.

```
(1,2) (1,3) (1,4) (1,5) (2,3) (2,4) (2,5) (3,4) (3,5) (4,5)

```

Now comes the last part of applying two pointer algorithm. Which i am failing to understand.For ex.
Lets take (1,2)

```
B[2][1] - B[1][1]= 3-1 = 2
B[2][2] - B[1][2]= 6-2 = 4
B[2][3] - B[1][3]= 9-3 = 6
B[2][4] - B[1][4]= 6-2 = 4
B[2][5] - B[1][5]= 15-5 =10

```

Now how is that helping? I mean on these values if we apply two pointer algorithm what will we achieve? For example i am looking for all occurrences of 36. How do i get close to it. ?

Can anybody carry this forward and explain the solution?

# Answer
The two-pointer algorithm is described in this post. Given a non-negative sequence $\alpha\_1,\ldots,\alpha\_n$ and a target sum $S$, we want to find the number of pairs $(i,j)$ such that $\alpha\_i + \cdots + \alpha\_j = S$. Let's make life a little easier by requiring the sequence to be strictly positive. For each $i$ there is therefore at most one $j$ such that $\alpha\_i + \cdots + \alpha\_j = S$, and we could find it by enumerating over all $j$ (resulting in an $O(n^2)$ algorithm) or using binary search (this requires $O(n)$ preprocessing, and leads to an $O(n\log n)$ algorithm).

The two-pointer algorithm is very similar but uses data from the $i$th iteration to make the $(i+1)$th iteration faster. Here is one variant For each $i$, we calculate the minimal index $j(i)$ such that $\alpha\_i + \cdots + \alpha\_{j(i)} \geq S$. The main observation is that $j(i)$ is a non-decreasing sequence, that is, $j(1) \leq \cdots \leq j(n)$. This suggests the following algorithm:

1. Initialize $j(0) = 0$.
2. For each $i$ in turn, calculate $j(i)$ by going over $j = j(i-1),j(i-1)+1,\cdots$ until $\alpha\_i + \cdots + \alpha\_j \geq S$. We then set $j(i) = j$. If $\alpha\_i + \cdots + \alpha\_{j(i)} = S$, we have found a subsequence summing to $S$.

This algorithm runs in linear time (basically since the index $j(i)$ keeps increasing) and finds all contiguous subsequences summing to $S$. I'll also let you figure out yourself what to do when some entries could be $0$.
> 1 votes

# Answer
As the values you have computed till now is array `C[j] = summation of A[p][j] to A[q][j]`. Now if we will be able to find the sub array `C[x..y]` with sum `K` then definitely sum of sub matrix `A[p..q][x..y]` will be `K`. In **step 3** instead of applying two pointer algorithm, we can use this method for finding a sub array with given sum, which works in `O(n)`.
> 0 votes

---
Tags: algorithms, matrices
---


# Question
Title: Why can PDAs only write one symbol to the stack according to this definition?
This is in regards to the definition 2.13 of non-deterministic PDA given in Theory of Computation 3rd ed. by Michael Sipser.

The transition is defined as $$ \delta: Q\times \Sigma\_\varepsilon \times \Gamma\_\varepsilon \to P(Q\times \Gamma\_\varepsilon) $$ where $Q$ is the set of states, $\Sigma = \Sigma\_\varepsilon\cup \varepsilon$ is input alphabets, and $\Gamma\_\varepsilon = \Gamma\_\varepsilon\cup \varepsilon$ is the stack alphabets.

I think $\Gamma\_\varepsilon$ in the co-domain of the transition should be replaced with $\Gamma\_\varepsilon^\*$; otherwise, I don't see how this definition can pop/push from/onto its stack.

Please help me clarify this.

# Answer
> 6 votes
The addition of $\epsilon$ to the alphabets allows the pop and push operations. For example, if you want to push the letter $a$ in state $q$, without reading anything from the input, you can have the transition $\delta(q,\epsilon,\epsilon)=\\{(s,a)\\}$, where $s\in Q$.

And if you want to pop $a$ without reading anything from the input, you can have $\delta(q,\epsilon,a)=\\{(s,\epsilon)\\}$.

Of course you can combine the two for a simultaneous pop/push, and you can do that while reading from the input.

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


title: Change in Training Accuracy

text:
# Question
Title: Change in Training Accuracy
I am solving a problem in the Kaggle learn section : https://www.kaggle.com/c/facial-keypoints-detection

The problem involves detecting facial keypoints in a 96x96 image, some 30 features are detected. It is a supervised dataset.

I am using a convolutional neural network with max pooling, 2 convolutional layers and 2 max pooled layers, and one fully connected layer.

The problem uses the rmse metric for scoring. So i used an ADAM optimizer to minimize the rms loss.

**CASE 1**:

I just simply trained the model, i got an average training rms error of 11.2, and finally when the output is generated I clamp the values which are greater than 96 (It's a 96x96 image) to 96, i get a test rms error of 9.1.

**CASE 2**:

I train the model itself with the clamped output values, i.e any output of greater than 96 gets clamped to 96 while training.

I thought **CASE 2** would lead to faster and better convergence. I used the same hyper-parameters for **CASE 2** and found that it is converging more slowly and gives a very high rms error of around 180.

Can anyone explain what is happening?

# Answer
> 2 votes
The problem with your second approach (Case 2) is that the neural network might decide to output very large numbers for keypoints near or on the edge. If it does, the loss function won't do anything to discourage it from doing that.

For instance, suppose the keypoint is at (30,94) for one instance in the training set. Then outputting (30,1000) has the same penalty as (30,96). So a network might just learn to output (30,96), and then start increasing the second coordinate (it learns (30,97), then (30,98), etc.) -- there's no penalty for that.

In particular, suppose that at some point the network is outputting (30,96) on that instance, and suppose the gradients encourage increasing the 96 a little bit. Then in the next iterations the weights will be adjusted so it outputs (30,97). Because the output is clamped before applying the loss function, (30,97) will receive the same penalty as (30,96). Also it will have the same gradient. Thus the learning process will continue adjusting the weights to cause the second coordinate to keep increasing forever.

This causes learning to fail to converge, or to converge very slowly. And if learning fails to converge, it's plausible that overall rms error (including on other instances where this issue doesn't arise) might be very bad.

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


# Question
Title: Can we find k shortest paths between all pairs faster than solving the pairwise problem repeatedly?
I want to produce $k$ shortest path ($k$ would be less than 10) between all pairs in a graph. The graph is (actually a subway map):

* positively weighted
* undirected
* sparse
* with about 100 nodes

My current plan is to apply $k$ shortest path routing to each pair; I am now looking for a more efficient alternative (possibly with dynamic programming).

# Answer
> 7 votes
First of all, a crucial difference in computing $k$-shortest paths is if the paths need to be simple or not. A path is called *simple*, if it does not contain nodes repeatedly. A path with a loop, for example, is not simple. Note that on the Wikipedia page you linked, the articles are concerned with not necessarily simple paths. The case of simple paths seems to be harder than the case with not necessarily simple paths.

### The all-pairs $k$-shortest *simple* paths problem

This seems to be a quite young area of research. A recent paper by Agarwal and Ramachandran can be found on the ArXiv \[1\]. The previous-work section will also give you some insight into the history of the problem.

### The all-pairs $k$-shortest paths problem

Here, indeed, it is the best choice to just repeatedly apply Eppsteins algorithm \[2\]. The general observation that a repeated application of an algorithm for the single-source version of the problem is the fastest approach was already made in 1977 by E. L. Lawler \[3\]; Eppstein provides the fastest algorithm to date for this subproblem.

### References

\[1\] Agarwal, U. and Ramachandran, V. Finding $k$ Simple Shortest Paths and Cycles. arXiv:1512.02157 \[cs.DS\] https://arxiv.org/pdf/1512.02157.pdf

\[2\] Eppstein, D. Finding the k shortest paths. SIAM Journal on Computing 28, 2 (1999), 652–673.

\[3\] Lawler, E. L. Comment on a computing the k shortest paths in a graph. Communications of the ACM, 20(8):603–605, 1977.

---
Tags: algorithms, graphs, optimization, shortest-path
---


# Question
Title: Approximation ratio when optimal solution is $0$
This might be a basic technicality but I'd like to make sure how to handle it. The question is: how do we measure an algorithm's approximation (multiplicative) factor on instances with optimal value $0$.

Suppose I have a minimization problem $Pb$, and it is NP-Hard to decide if a given instance $I$ has optimal value $OPT(I) = 0$.

As a concrete example, say that $Pb$ is the problem of removing a minimum number of edges from a graph so that it is $3$-colorable. Deciding if $0$ edges suffice is NP-hard.

Suppose now that I have an approximation algorithm $A$ for $Pb$ that runs in polynomial time. How could $A$ achieve any kind of approximation factor?
Suppose $A$ always finds a solution of value $APP(I)$ within factor $\alpha$. Then on instances of value $0$ it must return a value $APP(I) \leq \alpha \cdot OPT(I) = 0$. Thus $APP(I)$ decides whether $OPT(I) = 0$. Unless $P = NP$, this is impossible and so $A$ cannot approximate $Pb$ within any factor in polynomial time, let it be constant, $poly(n)$, superexponential in $n$, whatever...

Is that it? Or is there some way around this technicality?

# Answer
That's right. Such a problem is not approximable to within any constant factor large than 1 (unless P=NP).

Is there a way around this? Yes, there are several possibilities:

1. Use a different measure of approximation, rather than multiplicative factor. For instance, you could consider its *additive* approximability.
2. Re-define the problem so it cannot have output of 0. For instance, let $Pc(G)=Pb(G)+1$, i.e., $Pc$ is the problem of computing the minimum number of edges to remove from a graph so it becomes 3-colorable, plus one. Then there is no such barrier to achieving some constant approximation factor. (There might still be other barriers, of course.) Suppose you found that $Pc$ has a 2-approximation. Then you could unfold what that implies for $Pb$.
> 7 votes

# Answer
This is correct. $P$ (that is quite an unfortunate name for a problem if you also want to talk about $P$ as a class of problems) can not be approximated within any constant factor unless $P=NP$.
> 3 votes

---
Tags: complexity-theory, approximation
---


# Question
Title: Is it possible to get Nth Fibonacci number in sublinear time?
I was researching the topic of Fibonacci numbers and asymptotic complexity of generating them. Coming across a seemingly paradoxical conclusion, I've decided to check out if you agree with my explanation.

1. The naive algorithms runs in $O(n)$, if we ignore the cost of addition.
2. The Binet's formula or matrix exponentiation method should both theoretically run in $O(\lg(n))$ (since exponentiation of both matrices and real numbers takes $O(\lg(n))$ steps)

The problem arises when you analyze the size of Nth Fibonacci number by assuming that after first few members of the sequence, the ratio between two numbers is at least 1.5 (picked randomly, I assume it can be easily proved by induction).

We can then bound the number to be at least as big as: $c\_1\*(1.5)^n$. Its logarithm gives us the number of digits the Nth Fibonacci number has ($c\_2\*n$). Am I right to assume that you can't print out (or calculate) linear number of digits in sublinear time?

My explanation of this "paradox" is that I forgot to add multiplication costs in 2nd algorithm (Binet/matrix), making its complexity $n\*\lg(n)$. I've found out that naive algorithm (1st) runs better for very small inputs, and 2nd algorithm runs better for bigger ones (python3).

Is my explanation of complexity correct, and should the naive algorithm get better running time at even larger inputs ($n\>10^9$ or such)?

I do not consider this to be a duplicate question, since it adresses the problem of arbitary values and arbitary integer aritmetic.

# Answer
> 10 votes
Let's assume that you could store such large Fibonacci numbers. In that case, the length of $n^{th}$ Fibonacci number is $\lfloor n \log\_{10}\phi+1\rfloor$. That is the length of the $n^{th}$ Fibonacci number is $\Theta(n)$.

If you go by the naive method, then calculating the $n^{th}$ Fibonacci number would cost you $\Theta(n^2)$ time.

In comparison, matrix exponentiation will take $O(n^2\log n)$ time, assuming you use schoolbook long multiplication to multiply numbers. (A slightly more refined analysis shows that it is in fact $\Theta(n^2)$, by summing a geometric series.) But if instead we use Karatsuba multiplication, the running time to compute the $n$th Fibonacci number using matrix exponentiation becomes $O(n^{1.585}\log n)$. (Analogous to before, a slightly more refined analysis shows that the running time is in fact $\Theta(n^{1.585})$.) Thus, if you use sophisticated multiplication algorithms, matrix exponentiation would be better for large $n$ compared to the naive algorithm.

In short: which method is better depends on which multiplication algorithm used.

# Answer
> -1 votes
This formula (from wikipedia) may be much faster, depending on how you manage floating point and exponentiate. The first term dominates.

$$ F\_n = \frac1{\sqrt{5}}\cdot\left(\frac{1+\sqrt{5}}2\right)^n - \frac1{\sqrt{5}}\cdot\left(\frac{1-\sqrt{5}}2\right)^n\\,.$$

(From Wikipedia.)

---
Tags: algorithm-analysis, time-complexity, asymptotics
---


title: Rearrange an array using swap with 0

text:
# Question
Title: Rearrange an array using swap with 0
This is a Google interview question. I got it from a website.

> You have two arrays **source** and **target**, containing two permutations of the numbers `[0..n-1]`. You would like to rearrange source so that it equals to target. The only allowed operations is **“swap a number with 0”**. Find the minimum number of swaps?
>
> e.g. {1,0,2,3} -\> {1,3,2,0} swap 0 with 3. one swap is enough.

My attempt on problem: If we consider arrays as strings we could use edit distance to convert source to target if other edit distance operations like insert,delete,replace etc are allowed but here only allowed operation is swapping.

# Answer
> 9 votes
Without loss of generality you can assume that the target array is $0,1,...,n-1$: you can "relabel" the target array as 0,1,2,...,n-1 (and relabel the corresponding numbers in the source array, too). The allowed operation becomes "swap a number with x" (where x is not necessarily 0) and the target array is 0,1,2,...,n-1.

You can build a directed graph with $n$ nodes and an edge from node $n\_i$ to node $n\_j$ if $n\_i = j$, i.e. the target position of $n\_i$ is $j$ (skip nodes that are already in the correct position). The resulting graph contains one or more distinct cycles.

You can arrange the cycle containing the zero following the arcs in the *reverse direction*, then "jump" to another cycle and arrange it; the "entry point" doesn't matter.

In the example of the figure above the swap number is zero and the target permutation is $0,1,...6$; after completing the first cycle (blue one) you must enter the second cycle (red one) in order to complete it; if $(n\_i \rightarrow n\_j)$ is a directed arc of the second cycle, then it must modified in $(n\_i \rightarrow 0 \rightarrow n\_j)$. The "entry point" is irrelevant (the number of swaps needed to arrange the second cycle doesn't change). You can also interpret the swaps on a cycle like a shift of its numbers.

The procedure always ends with the sorted array (after arranging a cycle, its numbers are never moved again). If there are $m$ cycles and the $i$-th cycle has $p\_i\>1$ numbers that needs to be arranged and cycle 1 contains the number used for the swaps, the total number of swaps is $(p\_1-1)+(p\_2+1)+...+(p\_m+1)$. If the number used for the swaps is already in place the number of swaps is $(p\_1+1)+(p\_2+1)+...+(p\_m+1)$. To prove that the number of swaps used is optimal, you can observe that every number of each cycle must be moved (requires a swap), and there is no way to move a number of a cycle without "moving" the zero on that cycle.

# Answer
> -1 votes
In order to minimize the number of swaps, each time the 0 is not in its correct place you can take advantage of its current position and swap it with the number that should go there.

For example, if you have `{3,1,4,0,2}` and you want `{4,2,0,3,1}` the `0` is not in its correct position, and the number that should go there is `3` so you swap them, on the next iteration you have `{0,1,4,3,2}`. Again the `0` is not on its correct position so you swap it with `4` to obtain `{4,1,0,3,2}`. This time the `0` is on the correct position so you just swap it with the any number which is not yet on the desired position, say `1` `{4,0,1,3,2}` and continue with the original process `{4,2,1,3,0}` and finally `{4,2,0,3,1}`

# Answer
> -1 votes
@Vor's solution is awesome! Here is a Java implementation for that:

```
// 0 1 2 3
// 3 2 1 0  (0,3) (1,2)
// http://cs.stackexchange.com/questions/13930/rearrange-an-array-using-swap-with-0
public static int sortWithSwap(int [] a) {
    Integer[] A = new Integer[a.length];
    for(int i=0; i<a.length; i++)   A[i] = a[i];
    Integer[] B = Arrays.copyOf(mapping(A), A.length, Integer[].class);

    HashSet<Integer> all = new HashSet<>();
    List<HashSet<Integer>> list = new ArrayList<>();
    list.add(new HashSet<Integer>());

    for(int i=0; i<B.length; ) {
        HashSet<Integer> cur = list.get(list.size()-1);
        if(!all.contains(B[i])) {   // add to existing cycle
            all.add(B[i]);
            cur.add(B[i]);
            i = B[i];
        } else {
            if(cur.contains(B[i])) {     // duplicate in existing cycles
                list.add(new HashSet<Integer>());
            }
            i++;
        }
    }

    list.remove(list.size() - 1);     // remove last empty set
    int sum = 0;
    for(int i=0; i<list.size(); i++) {
        HashSet<Integer> cur = list.get(i);
        if(cur.size() <= 1) continue;
        if(cur.contains(0)) {
            sum += cur.size() - 1;
        } else {
            sum += cur.size() + 1;
        }
    }

    return sum;
}

// a b b c
// c a b b
// 3 0 1 1
private static Object[] mapping(Object[] A) {
    Object[] B = new Object[A.length];
    Object[] ret = new Object[A.length];
    System.arraycopy(A, 0, B, 0, A.length);
    Arrays.sort(A);
    HashMap<Object, Integer> map = new HashMap<>();
    for(int i=0; i<A.length; i++) {
        map.put(A[i], i);
    }

    for(int i=0; i<B.length; i++) {
        ret[i] = map.get(B[i]);
    }
    return ret;
}

```

# Answer
> -2 votes
@Vor's solution is awesome!My simple solution.

public static void ReArray(int\[\] src) {

```
    if (src == null || src.length == 0) {
        return;
    }

    int[] reverseSrc = new int[src.length];

    for (int i = 0; i < src.length; i++) {
        reverseSrc[src[i]] = i;
    }

    for (int i = 0; i < src.length; i++) {
        if (reverseSrc[i] == i) {
            continue;
        }

        if (reverseSrc[0] == 0) {
            swap(reverseSrc, 0, i);
            System.out.println(Arrays.toString(reverseSrc));
        }

        while (reverseSrc[0] != 0) {
            swap(reverseSrc, 0, reverseSrc[0]);
            System.out.println(Arrays.toString(reverseSrc));
        }
    }

    System.out.println(Arrays.toString(reverseSrc));
}

public static void swap(int[] reverseSrc, int a, int b) {
    int temp = reverseSrc[a];
    reverseSrc[a] = reverseSrc[b];
    reverseSrc[b] = temp;
    System.out.format("Positon %d and Position %d are swaped. \n", a, b);
}

```

---
Tags: algorithms, sorting, permutations
---


# Question
Title: Applying the Master Theorem on Merge sort
I found the proof below in a textbook. I would like to know why it is important for the proof that it uses $\lceil \frac{n}{2} \rceil$ instead of just $\frac{n}{2}$? I know that you can't split into calls which aren't natural numbers, but how do I present this argument formally?

**The proof:**

The recursion splits the problem into two sub problems, each with at most $\lceil \frac{n}{2} \rceil$ elements. Therefore, we can apply the Master Theorem with $a = b = 2$. So, $\log\_b{a}$ = 1. The cost of splitting is $0$ comparisons, and that of combining is at most $n−1$ comparisons. Hence the cost of split/combine is $\Theta(n) = \Theta(n\log\_b{a})$, so we are in the second case of the Master Theorem, and therefore the total cost is $\Theta(n\log n)$.

# Answer
> 6 votes
You can't use $n/2$ since this bound just isn't always true. Suppose that $n = 5$. It is not the case that you can split an array of length 5 into two arrays of length 2.5. It's not even true that you can split it into two arrays of length at most 2.5. But you are able to split it into two arrays of length at most $\lceil 2.5 \rceil = 3$.

Note that the textbook estimates the time it takes to sort an array with *at most* $n$ elements (rather than the time it takes to sort an array with *exactly* $n$ elements).

---
Tags: algorithm-analysis, runtime-analysis, sorting, recurrence-relation, master-theorem
---


# Question
Title: Unsupervised Learning: BCM or Oja's Rule
I am learning about unsupervised machine learning, and am a bit confused regarding different algorithms to update weights. So, I understand that both Oja's Rule and BCM can be used.

In Oja's rule:

```
dw/dt = k*x*y - w*y^2

```

Where `x` is the value at the input neuron, `y` is the value at the output neuron and `w` is the connection strength between the two. The idea is that this prevents weights from growing out of proportion.

In BCM:

```
dw/dt = k*(y-theta)*x

```

Where the idea is that unless my postsynaptic strength exceeds a threshold theta then I don't want my connectio to be strenghtened.

Studying competitive learning, which is yet another type of unsupervised learning I cam across another rule:

```
dw/dt = n*(x-y)

```

In this case however `x` is the full input vector and `y` is the vector representation of the output vector. The idea being that we move the prototype that responded the strongest to a given input closer to it, making the two more similar.

However, I don't understand when should I use which rule? For example, why couldn't I use a rule that combines both Oja's and BCM, hence only increasing connection weights when the output exceeds a given threshold, and preventing weights from growing out of proportion?

# Answer
Oja's learning rule and the BCM share the underlying generative model, a linear perceptron: $$y = w^T x,$$ where $w$ and $x$ are vectors of the similar dimension.

But they differ in their goals:

Oja's rule (run with a sufficiently small learning rate) extracts the 1st principle component of the covariance matrix of the data: $$C = \langle xx^T \rangle\_{p(x)}$$ s.t. $ \lambda\_1 w\_1 = C w\_1$, where $\lambda\_1$ is the largest eigenvalue.

The BCM rule maximizes the input selectivity with respect to a specific input pattern. The selectivity is defined as $$ s(w) = 1 - \frac{\langle w^T x^{(i)} \rangle}{ \max\_i w^T x^{(i)} }. $$ The selectivity is maximized if the output neuron responds strongly to one of the input patterns (e.g. the kth stimulus $x^{(k)}$) but barely responds to all others.

The third rule doesn't make sense to me (I'll use explicit notation for vectors now). Assuming that $n$ is a scalar (e.g. learning rate), $\vec{x}$, $\vec{y}$ and $\vec{w}$ must have the same dimensions. Then, what's your generative model? Neither can it be $y = \vec{w}^T \vec{x}$ (because $\vec{y}$ is a vector) nor $\vec{y} = W \vec{x}$ because your weights are vector and not a matrix..
> 3 votes

---
Tags: machine-learning
---


title: Subset sum NP-Completness

text:
# Question
Title: Subset sum NP-Completness
I know that the subset sum problem is NP-Complete because I can reduce a known NP-Complete problem to subset sum.

However, since subset sum can be solved by dynamic programming, I was not completely convinced that it is NP-Complete. I then realized that the dynamic programming solution in fact tries all possible combinations and because of this, is in fact the same as a brute force approach. Is this a valid insight into why subset sum is NP-Complete?

# Answer
> tries all possible combinations and because of this, is in fact the same as a brute force approach

You don't share the specific algorithm you have in mind, but I think you are wrong. Trying all splittings at every level of the recursion is *not* the same as trying all solutions.

> since subset sum can be solved by dynamic programming, I was not completely convinced that it is NP-Complete

Again, you don't share the specific algorithm, but it probably has pseudo-polynomial running time. So no, there is no contradiction; "dynamic programming" does not equal "polynomial time" let alone "fast".
> 1 votes

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


# Question
Title: Hungarian Algorithm - Arbitrary Assignments
I've looked at several explanations of the Hungarian Algorithm for solving the Assignment Problem and the vast majority of these cover only very simplistic cases.

The most understandable explanation I've found is a YouTube video.

I can code the algorithm but I'm concerned about one special case. If you watch the video, the relevant case is explained from 31:55 to 37:42, but I’ll explain it below.

I should first mention that I will be dealing with a 300 x 300 matrix, so visual inspection is out of the question. Additionally, I need to find *all* minimum assignments. In other words, if there are multiple assignments that produce the same minimum value, I need to find them all.

Here's the particular case that I'm concerned about. You can see this explained in the YouTube video but I’ll go over it here. We start with this matrix:

```
3   1   1   4
4   2   2   5
5   3   4   8
4   2   5   9

```

When we reduce the rows and columns, we get this:

```
0   0   0   0
0   0   0   0
0   0   1   2
0   0   3   4

```

(Let me mention that I can visually see there are 4 solutions to this matrix and the total score is 13.)

Given the above reduced matrix, there are no unique zeros in any row or column, so, according to the algorithm described in the video, I can *arbitrarily* select any zero element for assignment, so I select (1,1).

I’ll mark the assigned zero with an asterisk and I’ll put an “x” next to those zeros in the rows and columns that are no longer available for consideration. Now we have this:

```
0*  0x  0x  0x
0x  0   0   0
0x  0   1   2
0x  0   3   4

```

Next, we continue examining rows for a unique zero. We find one at (3,2) so we mark it with an asterisk and mark the unavailable zeros with "x":

```
0*  0x  0x  0x
0x  0x  0   0
0x  0*  1   2
0x  0x  3   4

```

Next, we start looking for unique zeros in the columns (since all rows have been exhausted). We find column three has a unique zero at (2,3) so we mark it:

```
0*  0x  0x  0x
0x  0x  0*  0x
0x  0*  1   2
0x  0x  3   4

```

At this point, there are no more available zeros and row 4 has been left unassigned. (This particular YouTube video now uses a “ticking procedure”, which is a common technique for determining the minimum number of lines needed to cover all the zeros. If you are unfamiliar with this technique it is explained starting at 14:10 through 16:00, although the presenter uses a different matrix than shown here.) The “ticking procedure” is this:

1. Tick all rows that have no assigned zeros (row 4).
2. For each row that is ticked, tick the columns that contain a zero in that row.
3. For each column ticked in step 2, tick the corresponding rows that have *assigned* zeros.
4. Repeat steps 2 and 3 until no more ticking is possible.
5. Draw lines through all ticked columns and un-ticked rows.

At this point, the ticking procedure generates 4 vertical lines, covering all zeros. The four vertical lines tell us the zeros in the matrix represent one or more solutions, yet, as we see, row 4 is unassigned. The fact that fourth row remains unassigned in spite of the four vertical lines tells us that we chose the wrong zeros for assignment!

The video’s presenter indicates this problem is a result of our initial (arbitrary) assignment of element (1,1). The presenter says, “there are more sophisticated methods available” to get us out of this situation be he does not explain what these techniques are. He alludes to the existence of “intelligent” ways of selecting a zero, rather than the arbitrary selection we used to select the zero at (1,1).

One approach I could take (I’m not sure it’s the best) when faced with making an arbitrary assignment is to make the assignment from the row or column with the fewest number of available arbitrary choices. In this example, this means I would make the arbitrary assignment from either row 3 or 4, where there are only two arbitrary choices, rather than from row 1 or 2 where there are four arbitrary choices. Of course, since I need all correct solutions, I would have to iterate over all the available arbitrary assignments, whenever an arbitrary assignment is made. For example, if I select (3,1) as an arbitrary assignment, I would also have to assign (3,2) later.

My question then, after all this, is, when I am faced with the choice of arbitrarily selecting a zero for assignment, what is the best approach? Is it what I mention in the previous paragraph? How can I eliminate the dead-end solutions like the one shown? Please remember I still need to enumerate all solutions having the same minimal score.

# Answer
> 3 votes
See Finding all minimum-cost perfect matchings in Bipartite graphs.

Once you run the Hungarian Algorithm, you can use the result to

1. *find all "admissable" edges*. Roughly speaking, admissable edges are those that are part of *some* min-cost perfect matching (potentially with a few extras).
2. *generate perfect matchings of the subgraph of just the admissable edges*. During this step, you don't need to look for min-cost perfect matchings. By the choice of admissable edges, any perfect matching of the subgraph is automatically a min-cost perfect matching of the original graph. This step is much easier than explicitly looking for min-cost perfect matchings.

---
Tags: algorithms, graphs, bipartite-matching
---