# Question
Title: Hash function floating point inputs for genetic algorithm
I am implementing a genetic algorithm to use as an optimisation algorithm to evolve robots. The robots have certain parameters (represented as floats) which can lie anywhere within a certain range defined for each parameter. My goal is to optimise these parameters to produce the fittest robot.

There are about 25 parameters to optimise over, all of which are \>= 0. A generation consists of 32 robots and a typical evolutionary run may have 6000 generations, so that is 192000 robots in total.

One problem I was noticing was that many times, the same robot was being produced by the random mutation function and its fitness was re-evaluated. I want to try and minimise this from happening as the physics simulation engine has a large time expense.

It would be impractical (especially from a memory point of view) to remember all robot parameters that have ever been produced and use a brute force solution.

One solution I thought of was to use a hash function to and a large array of booleans, and everytime a mutation occurs, `largeArray[hash(robotParameters)]` is checked to see if it is set. If it is, the mutation occurs again to produce a different set of parameters, and if it isn't, `largeArray[hash(robotParameters)]` is then set.

What is a good hash function implementation that would work for me? Preferably, there would already be an implementation in Python or C++.

# Answer
> 3 votes
**Hashing an array of floats**

You need some hash function that:

* low computational cost
* low probability of generating the same hash value for two input vectors = evenly distributed hashes

If you language/library have some function for hashing float array, it should be ok.

For example, this function is what Java would do with an float array (it's not a direct copy of Java library):

```
int hashFloatArray(float[] arr) {
    //this is done in Arrays.hashCode()
    int h = 1;
    for (int i = 0; i < arr.length; i++){
        int floatAsInt = Float.floatToIntBits(arr[i]);
        //in C: int floatAsInt = *(int*)(&arr[i]);
        h = 31 * h + floatAsInt;
    }
    //this is done in HashMap
    h ^= (h >>> 20) ^ (h >>> 12);
    return h ^ (h >>> 7) ^ (h >>> 4);
}

```

**Finding matching hashes**

Storing hashes instead of whole float arrays reduces amount of memory needed. Space of hashes is smaller than the space of float arrays, so matching hashes never give 100% certainty that original objects (float arrays) where identical. The longer hashes the smaller is the change of hash collision (situation when two different inputs produce the same hash).

**Array indexed with hashes** (as OP proposed)

Indexing array with hashes means that the length of the array must be 2^k where k is length of key in bits. For example: Assuming single field of array occupies 1 byte (boolean variable usually occupy 1 byte). Using 30 bit key requires 2^30 * 1 bytes = 1GB of memory (**O(2^k) space complexity**). As mentioned before:

* shorter key = smaller array = higher chance of hash collision
* longer key = bigger array = lower chance of hash collision

**Hash table** (Hash set)

Hash table is a data structure that can be used to implement hash set. Main advantage of hash set is it's O(1) average time complexity combined with **O(n) space complexity**.

You can use hash set to store and effectively find:

* long hashes (64 bit?) of float arrays without wasting memory
* float arrays themselves (if you have enough memory)

Hash sets are available in standard libraries of almost all programming languages.

* `java.util.HashSet` in Java
* `unordered_set` in C++11
* `set` in Python

**Why comparing and hashing floats is a problem?**

Let's take two float numbers: 1.2345678 and 1.2345679 The difference between them is small enough to have no influence on the quality of your Robot, but comparing 1.2345678 and 1.2345679 results in "not equal" and hashing them results in two different hashes. Introducing an "almost equal" term may be a good idea, but that can't be done with hashes.

# Answer
> 0 votes
I'll describe how I solved this problem in Python. To combat the problem of two similar floats not mapping to the same hash, I used the function below to round the parameters to a certain no. of significant figures

```
def roundToNSigFigs(x, n):
  return 0 if (x == 0) else round(x, -int(math.floor(math.log10(abs(x)))) + (n - 1))

```

Within the `Robot` class, the `self.args` member variable was a list holding all the floating point parameters. I started with

```
hashTable = set()

```

And every time a Robot was created I used:

```
hashTable.add(hash(tuple([roundToN(i, sigFigs) for i in self.args])))

```

The `tuple` cast is needed because you cannot take the hash of a mutable object

And in my mutation member method, I checked to see if the new mutated parameters (`newArgs`) were already tested by checking `hash(tuple(newArgs)) not in hashTable`

# Answer
> 0 votes
If you're interested, I just made a hash function that uses floating point and can hash floats. It also passes SMHasher ( which is the main bias-test for non-crypto hash functions ). It's a lot slower than normal non-cryptographic hash functions due to the float calculations.

I'm not sure if tifuhash will become useful for all applications, but it's interesting to see a simple floating point function pass both PractRand and SMHasher.

The main state update function is very simple, and looks like:

```
function q( state, val, numerator, denominator ) {
  // Continued Fraction mixed with Egyptian fraction "Continued Egyptian Fraction"
  // with denominator = val + pos / state[1]
  state[0] += numerator / denominator;
  state[0] = 1.0 / state[0];

  // Standard Continued Fraction with a_i = val, b_i = (a_i-1) + i + 1
  state[1] += val;
  state[1] = numerator / state[1];
}

```

Anyway, you can get it on npm Or you can check out the github

Using is simple:

```
const tifu = require('tifuhash');

const message = 'The medium is the message.';
const number = 333333333;
const float = Math.PI;

console.log( tifu.hash( message ),
  tifu.hash( number ),
  tifu.hash( float ),
tifu.hash( ) );

```

---
Tags: hash
---


# Question
Title: Understanding of SPACE in non deterministic Turing Machines
Let's consider the following situation. We have a finitie alphabet $A$. Let $A = \\{a\_1, .., a\_k\\}$ We consider words over $A$ of length exactly $n$. I am trying to solve some problem and I am going to:

Generate every word using non-deterministic Turing Machine. And, for every generated word make a computation $C$. that uses only constant space and linear time. So, it seems that we have to remember (for a moment) generated word. I mean the situation that we have to generate word $w$ and then make a computation $C$ on $w$.

The scheme of Turing machine looks like:

The question is: Is my Turing machine NPSPACE? I have a problem with thinking about space complexity when it comes to nondterministic TM.

# Answer
> 3 votes
A nondeterministic Turing machine is a Turing machine that has a "guessing" mechanism. It accepts an input if there is a sequences of guesses that leads it to an accepting state. It rejects an input if all guesses lead it to a rejecting state.

The *time complexity* and *space complexity* of the Turing machine are defined in exactly the same way as for deterministic Turing machines:

* The time complexity on inputs of size $n$ is the maximum number of steps that the machine executes before halting over *all* inputs of size $n$ and *all* guesses.
* The space complexity on inputs of size $n$ is the maximum number of tape cells that the machine uses over *all* inputs of size $n$ and *all* guesses.

If your machine always uses only a polynomial amount of space, then it is is NPSPACE. Note that NPSPACE=PSPACE, a consequence of Savitch's theorem, and so you can convert it to a deterministic machine using polynomial space (the amount of space used could increase).

---
Tags: turing-machines, space-complexity, nondeterminism
---


# Question
Title: construct a deterministic PDA for the language
Can someone help me to construct a deterministic PDA for the following language:

$L = \\{0^n1^m | n \geq m$ and $m,n \geq 0 \\}$

Here is my suggestion : the states are z0,z1,z2 , z0 is final state , for the empty string , z1 should also be finate state :

# Answer
Since you are confused, here are four hints to get you going. You will still have to think through the machine, but here are some of the big pieces:

1. Push a marker onto the stack that will tell you where the bottom of the stack is. (Let's say, $\\$$)
2. Every time you find an $0$, push a symbol (let's say, $p$) onto the stack.
3. When you finally find an $1$, stop pushing. Start popping off $p$s.
4. If you reach the $\\$$ before you've reached the end of your $1$s, then you've broken the $n \geq m$ condition.
> 0 votes

---
Tags: pushdown-automata
---


title: Does our PC work as Turing Machine?

text:
# Question
Title: Does our PC work as Turing Machine?
Does our PC work as Turing Machine? The model of a Turing Machine consists of infinite memory tape, which means infinite states. But suppose if our PC has 128 MB memory and 30GB disk it would have 256^30128000000 states and thus, it has finite states.

I know that we can write a type of program that, if during execution we run out of memory, will request to swap memory disk with empty memory disk and resume execution.

**But what if we don’t swap memory disk, in this case is it right to consider PC as FA**?

# Answer
You're right that physical computers have finite memory and so are not Turing-complete. There are other ways in which computability theory is not a good model for computing - it doesn't take into account time and memory constraints. Complexity theory was invented (perhaps) as a more realistic depiction of computing, but IMHO suffers from similar (but subtler) problems.

On the other hand, in order to mathematically study the capabilities and limits of computing, we need to use some abstraction which is unconstrained. That makes the analysis possible. Similarly, in statistical mechanics we assume that the number of elements (atoms or molecules) is so large, that the behaviour is close to the limit (that is, we let the number of elements tend to infinity). Studying computing from an asymptotic perspective has similar advantages, but sometimes is misleading. Here are some examples of the latter:

1. In cryptography, exponential algorithms are sometimes feasible. If we choose the wrong security parameters, our encryption might be insecure even though it's "provably secure".
2. Polynomial-time algorithms are supposed to represent efficient and feasible computing, but many of them aren't feasible. As an example, most sophisticated matrix multiplication algorithms aren't used in practice.
3. Modern complexity theory is obsessed with worst-case performance, and cannot analyze heuristic algorithms which are used in practice. NP-hard problems are considered infeasible, yet they are being solved in practice all the time.

A separate issue is that real computers don't work like Turing machines at all. They work like RAM machines, which are a better abstraction for actual computing.
> 13 votes

# Answer
I think you've given the answer yourself already. If the main aspect you are concerned about is the (in)finity of states, then a Turing Machine as such only exists as "a hypothetical device".

No matter how much memory you'll give your PC, it will always be limited, hence you can find program that will run on a "real" Turing Machine, but not on this PC due to the bounded tape.

http://en.wikipedia.org/wiki/Turing\_machine#Comparison\_with\_real\_machines
> 4 votes

# Answer
At the time Turing machines were invented, computers were women who would execute calculations on scrap paper. That is the notion of computation Turing machines express. Their tape isn't part of them any more than scrap paper is part of a person performing calculations.

This is still a good model for computer-based calculation because the bounds on resources in computers are usually quite large. Inherently finite computation models only become useful when the number of possible states is very small.
> 1 votes

# Answer
A modern computer is Turing complete, generally this term is used with the exception of infinite storage device. In practice, the memory can be quite long. For example, along with being universal function approximators, recurrent neural networks with memory (and running repeatedly) are said to be Turing complete. Indeed, Neural Turing Machines take this idea to a stage further inferring simple algorithms.
> -1 votes

---
Tags: complexity-theory, computability, turing-machines, automata
---


# Question
Title: Throwing an error when initializing an object in c++
Let's say that when initializing a pet class, I wanted to exclude or disallow dogs or cats as species. What would be the proper way to throw an invalid\_argument exception?

```
using std::string;
#include <stdexcept>
using std:: invalid_argument;
struct Pet {
  const string name;
  long age = 0;
  const string species;
  Pet() : name("Dan"), age(0), species("alligator"){}
  Pet(const string & the_name, const string & the_species): name(the_name),
  species(the_species), age(0) {};
};

```

# Answer
```
Pet(const string & the_name, const string & the_species): name(the_name), species(the_species), age(0)
  {

     if (species == "cats" || species == "dogs")
        throw std::invalid_argument( "received negative value" );
  }

```
> -1 votes

---
Tags: data-structures
---


# Question
Title: finding normality from a set of samples of MEAN
I have set of 1000 samples. each sample represents MEAN of X amount transactions response time.

Now I have a running transaction , I know it's current response time but I want to know if this particular transactions elapsed time is normal relative to my all previously collected sample.

is there a statistical method that is a good fit for this case ?

# Answer
> 0 votes
You can't, from the information listed.

You say in the comments that the distribution of transaction times is Gaussian. A Gaussian distribution has two parameters: $\mu$ (its mean) and $\sigma^2$ (its variance). Based on the 1000 observed values, you can make a good estimate of what the underlying value of $\mu$ is. However, there is no way to infer $\sigma^2$, the variance. Consequently, when you observe a new transaction time, you can't tell whether it is normal or abnormal.

Suppose $\mu = 100$ and you observe a transaction whose response time is $105$. Is that abnormal? There's no way to know. If the variance of the Gaussian distribution is $0.1$, it is highly abnormal. If the variance is $10$, it is entirely typical/normal.

# Answer
> 0 votes
Generally, data gathered from natural phenomena obeys normal distribution, I think your data should obey the normal distribution as well. The more you have data the better you may do estimation or prediction. Wikipedia says:

> In statistics, normality tests are used to determine if a data set is well-modeled by a normal distribution and to compute how likely it is for a random variable underlying the data set to be normally distributed.

There are many methods to do the test.

> Simple back-of-the-envelope test takes the sample maximum and minimum and computes their z-score, or more properly t-statistic (number of sample standard deviations that a sample is above or below the sample mean), and compares it to the 68–95–99.7 rule: if one has a 3σ event (properly, a 3s event) and substantially fewer than 300 samples, or a 4s event and substantially fewer than 15,000 samples, then a normal distribution will understate the maximum magnitude of deviations in the sample data.

But if your sample data is fixed ( I mean does not change with time) then you can precompute necessary statistics and later compare and draw conclusion in $O(1)$ time. But I would update my sample data once a day or hour, and then check it visually (for example you may detect outliers) and recompute statistics on a regular base.

---
Tags: statistics
---


title: Negative edge weight cycle SSSP

text:
# Question
Title: Negative edge weight cycle SSSP
Why are we interested in negative edge weight cycles when finding out SSSP. In a path, we are not allowed to traverse a node more than once.

# Answer
> 2 votes
In a *simple* path, no node can be traversed more than once. However, paths in general can. The SSSP asks for single-source shortest paths, without specifying that the paths need to be simple. This allows the paths to contain cycles. Thus, negative cycles are a concern as they may allow arbitrarily "short" paths, and so the definition of a "shortest" path falls apart. This is because if a path contains a node on a negative cycle, we can always lower the cost of the path by going around the negative cycle.

Of course, this also depends on how you define a path, and how the SSSP has been presented to you. The above explanation assumes typical definitions of both, so if you have different definitions, please leave a comment.

---
Tags: graphs, graph-traversal
---


title: Reduction from 2-SAT to 2-XOR-SAT?

text:
# Question
Title: Reduction from 2-SAT to 2-XOR-SAT?
*2-SAT is unsatisfiable iff it contains unsatisfiable XOR-2-SAT*.

So, first, we just need to combine **every** clause that contains share same variables (both of them). Then, all of those which remain uncombined are "uninteresting" (don't affect satisfiability).

Example:

$\Phi = (x \lor y) \land (\overline x \lor \overline y) \land (x \lor \overline z)\land(\overline x \lor z)\land (\overline y \lor z)\land (y \lor \overline z)\land (z \lor t)$

Now I can replace this formula by equisatisfiable (under log-space reduction):

$\Phi' = (x \oplus y)\land(x \oplus \overline z)\land(y \oplus \overline z)$

As you can see, clause $(z\lor t)$ was removed as "uninteresting".

Ah, well, I need to see if there are cycles in implication graph. So, finding a cycle in directed graph that contains two given vertices is $\mathsf{NL}$-complete problem, right?

# Answer
> 1 votes
This method doesn't work since you can't always pair clauses as in your example.

According to Wikipedia, 2SAT is NL-complete. In particular, this means that it is not in logspace unless L=NL, which is considered unlikely.

---
Tags: complexity-theory, satisfiability
---


# Question
Title: Are all decidable languages mapping reducible to its complement?
I dont think this is true, take the language with a single element L = {0}, then the complement L' would have infinitely many strings (everything that isn't 0). So if it were true that A is mapping reducible to its complement, everything in L' can be obtained via a computable function from some element in L, i.e 010 is in L' however there is no x in L that gives f(x) = 101, since theres only one element, 0, it maps to one result.

Would this be correct?

# Answer
> 4 votes
Let $L\_1,L\_2$ be two languages over $\\{0,1\\}$. A (computable) mapping reduction from $L\_1$ to $L\_2$ is a computable function $f\colon \\{0,1\\}^\* \to \\{0,1\\}^\*$ such that for all $x \in \\{0,1\\}^\*$ it holds that $x \in L\_1$ iff $f(x) \in L\_2$.

In your example, $L\_1 = \\{0\\}$ and $L\_2 = \overline{\\{0\\}}$, there does exist a mapping reduction, given by $$ f(x) = \begin{cases} 1 & \text{if }x = 0, \\ 0 & \text{if }x \neq 0.\end{cases} $$ Clearly $f$ is computable, and you can check that $x \in L\_1$ iff $f(x) \in L\_2$.

Hence your example doesn't work. You can check, however, that $\emptyset$ and $\\{0,1\\}^\*$ are two examples of languages not reducible to their complement. Indeed, these are the *only* examples, which you can try to prove.

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


# Question
Title: Implement multi-fragment heuristics for the traveling salesman problem
I would like to implement the *multi-fragment* heuristics algorithm for finding a solution to the traveling salesman problem.

The algorithm is described here as follows:

> This seriation method re-organises the $D$ matrix by iteratively placing the smallest distances in matrix $D$ in the $n-1$ cells contiguous to the diagonal.
>
> This is a greedy approach, with $n-1$ steps.
>
> At each step, rows $i$ and columns $j$ in $D$ are moved so that the smallest distance is placed in a not yet allocated cell. The smallest distance is not chosen freely. It is constrained by the necessity to keep the already allocated cells in place.
>
> ...
>
> This heuristic do not guarantee to find an optimal solution but give quickly a "reasonable good" solution. This solution could be improved by a local search heuristic.

According to the mentioned article, this algorithm was mentioned in a 1992 paper "Fast Algorithms for Geometric Traveling Salesman Problems" by "Bentley", but I couldn't find it on the internet. Moreover, there are almost no other information regarding this algorithm online, except from the usual definition like:

> The multi fragment algorithm works as follows:
>
> 1. Consider a distance matrix (such as the type at the back of a road atlas of Britain), containing all the distances between all cities on the tour.
> 2. Find the shortest distance and link these two cities together.
> 3. Then, find the second shortest distance, and link these two cities.
> 4. Now, find the next smallest edge whose cities conform to the following criteria:
>
> 1. Both must have an edge degree ratio \<=1 (i.e. neither can already be linked to more than one other city)
>     2. Adding an edge between the cities must not result in a closed tour, which does not already include all the cities on the tour.
> 5. Repeat until all cities end up being connected to two other cities.

I understood the algorithm according to this last article I'm linking to, but I'm not seeing the connection between this last description and the description above.

If the first description is correct, I'm actually not understanding it fully and how could I implement it in practice. For example, suppose we have this simple distance matrix $D$

$$D = \begin{pmatrix} 2& 1 &2 &3\\ 3 &2 &7 &2 \\ 3 &1 &1& 0\\6& 2& 5 &1\end{pmatrix}$$

In the first description, they mention the $n -1$ cells contiguous to the diagonal, but of course we have $2$ of this $n-1$ cells, one in the left triangular matrix (currently from the top to the bottom $3, 1, 5$) and one in the upper one ($1, 7, 0$). Is it ok to choose one arbitrarily?

Then they say:

> At each step, rows $i$ and columns $j$ in $D$ are moved so that the smallest distance is placed in a not yet allocated cell. The smallest distance is not chosen freely. It is constrained by the necessity to keep the already allocated cells in place.

Of course if we move a row or a column in the matrix $D$ and if we number the nodes from $1..N$, then we need to rename the nodes according to the moves.

But actually I'm not fully understanding how these moves could proceed in practice? Any concrete example?

Furthermore, after these moves, what should we do?

I would really appreciate a pseudo-code, if anyone has ever implemented this algorithm.

# Answer
> 4 votes
> there are almost no other information regarding this algorithm online
> \[...\]
> I would really appreciate a pseudo-code, if anyone has ever implemented this algorithm.

I invite you to read my paper "*An Empirical Study of the Multi-fragment Tour Construction Algorithm for the Travelling Salesman Problem*" appeared in the Proceedings of the 16th International Conference on Hybrid Intelligent Systems (HIS 2016) pp 278-287. DOI: 10.1007/978-3-319-52941-7\_28.

You'll find a pseudo-code of the algorithm, which is similar to the "usual definition". It's explained with some examples of a small instance. The paper also presents briefly other tour construction methods and gives experimental results for the Multi-Fragment algorithm and a comparative study to show the effectiveness of this method.

> If the first description is correct, I'm actually not understanding it fully and how could I implement it in practice.

It's correct but maybe a little bit hard to explain. The main idea is to move columns and rows following the criteria such that we can read the constructed tour from the $n−1$ cells contiguous to the diagonal **{D\[1\]\[0\],D\[2\]\[1\],... D\[n\]\[n-1\]}**.

> In the first description, they mention the n−1 cells contiguous to the diagonal, but of course we have 2 of this n−1 cells, one in the left triangular matrix (currently from the top to the bottom 3,1,5) and one in the upper one (1,7,0). Is it ok to choose one arbitrarily?

The distances matrix in the Traveling Salesman Problem (TSP) is symmetric $(D\[i\]\[j\]=D\[j\]\[i\])$, we may consider only the upper/lower triangular portion of the matrix $D$.
There is another variant of the TSP which is the Asymmetric TSP.

---
Tags: algorithms, heuristics, traveling-salesman, adjacency-matrix
---


# Question
Title: Is the langauge of (descriptions of) DFAs that accept $\Sigma^*$ decidable?
Is $L = \\{\langle A\rangle\mid A\text{ is a DFA and }L(A) = \Sigma^\*\\}$ decidable?

I know that $L'=\\{\langle A,w\rangle \mid A\text{ is a DFA and }w\in L(A)\\}$ is decidable, but I'm not sure if this is related.

# Answer
> 3 votes
It's decidable. Think about what an DFA's accepting states must look like if it accepts every possible string. That property is very easy to check.

# Answer
> 1 votes
Yes.

Every accessible state $s$

* must be accepted
* must have a successor state $\tau (s, \sigma)$ for $\sigma \in \Sigma$, where $\tau$ is the transition function of the DFA.

You can check this by breadth-first (or depth-first or whatever) search from the initial state. The search terminates since the automaton is finite.

---
Tags: computability, automata
---


# Question
Title: How to compare computational complexity of algorithms
I have three different algorithms for achieving a target. Algorithm 1 takes $O(Mn)$ - $M$ is constsnt and n is variable,Algorithm 2 takes $O(min(p^3,n^3))$ - both $p$ and $n$ is variable and Algorithm 3 takes $O(nk+nd)$ - $k$ constant, $n$ and $d$ is variable. Is it possible to compare these algorithms? Which algorithm is fast and how much fast than other two algorithms?

# Answer
> 0 votes
Since you have three different variable it is not easy to compare their running times. For example if $d = 1/n$ then $nd = 1$. But if $d = n$ then $nd$ is $n^2$. If $d$ and $n$ are unrelated to each other asymptotically or functionally I think you may not compare them. Analogously for $p$.

**Update**: If $M,p,k$ and $d$ are constant then we have Alg1 is $O(n)$, Alg2 is $O(min(p^3, n^3)) = O(p^3) = O(1)$, and Alg3 is $O(n)$.

---
Tags: algorithm-analysis, landau-notation
---


title: CPU cache - retrieving data from memory

text:
# Question
Title: CPU cache - retrieving data from memory
Regarding CPU cache, if the CPU does not find the data it needs in the cache, I understand it then looks for it in the main memory (RAM). (Let's assume we have only one level of cache in order to keep this question as simple as possible.)

My question is this: if the data is found in main memory, what happens? Does the processor use this data directly, or is the data loaded into the cache and then read from there?

# Answer
> 2 votes
Nobody can say what *every* computer will do, but there are some reasonable assumptions.

When you access data that is not in the cache, you want it to be in the cache afterwards. So the CPU will read the data from memory, and move it to the cache. That's one half of the job.

There is some part of the CPU that *needs* the data, and we want to get the data to that part of the CPU as fast and as cheap as possible. There is already a mechanism in place to provide the data if it is in the cache. So the CPU could just move the data to the cache, then use the existing mechanism. That's cheap and easy.

Or the CPU can move data from memory to the place where it is needed either simultaneously with the cache, or even before the data is moved to the cache. That has the advantage that the data may appear a little bit faster where it is needed. It has the disadvantage that now the two situations (in cache, not in cache) need to be handled by different hardware. That is likely more complicated and more expensive.

Which one is chosen depends on how much quicker the more complicated method is, how much it costs more, and how much the cost is compared to other possible improvements.

---
Tags: computer-architecture, cpu-cache, memory-management, cpu
---


# Question
Title: Complexity for checking if an array is a min-d-heap
**The problem is this**: Let us have an int array of length n. Find an algorithm to determine if the array represents a min-d-heap.

**My solution**: We start from the first index in the array, and compare its value to the value of its children (all the nodes at locations $i\*d+k$ where $k \in \\{1,2,...d\\}$, assuming we start the array at index 0). We do it for every index until we reach an index that "has no children", meaning $i\*d+1\>n-1$. If at every point the value of the parent's key was lower than the value of all of its children' keys we return $True$, meaning the array represents a min-d-heap.

Now - my problem is calculating the time complexity for this algorithm:

I have managed to prove that if we look at a "complete" d-tree, we get a time complexity of $O(n)$ worst case. This is my proof:

Let us assume the tree is of height $h$. We note that at the last level we have $d^{h-1}$ items. Now, we can show that the tree excluding the last level has $O(\frac{n}{d})$ items: $$\frac{\sum\_{i=0}^{h-1}d^i}{d^{h-1}} = \frac{d^{h-1}-1}{(d-1)d^{h-1}} = O(\frac{1}{d})$$ Therefore, for every node excluding the last level we make $d$ comparisons, and we get that the time complexity for the algorithm is $O(d\*\frac{n}{d}) = O(n)$.

My problem is that my proof was based on the fact that we have a complete tree. There are cases which are asymmetric and I found harder to prove for the general case. I did check it by hand and showed that it is indeed the same time complexity but couldn't prove it.

Would like your help in the last part, Thanks!

# Answer
> 1 votes
Apart from the answer given by rici in the comment to the question, I've come up today with an answer to prove this exact algorithm's time complexity, and it's pretty simple:

Since the algorithm goes over all of the parents in the heap (i.e all the nodes that have children), we only need to look at them while calculating the time complexity. The first parent is obviously the first item in the array. The last parent, is the parent of the last item in the array. The last item in the array is located at index $n-1$, therefore the parent of the last item (and the last parent) is located at index $\lfloor\frac{n-2}{d}\rfloor$ which is $O(\frac{n}{d})$. Therefore - we have $O(\frac{n}{d})$ parents in the array. For each parent we make $d$ comparisons, and finally we get the time complexity of $O(\frac{n}{d}\*d) = O(n)$.

---
Tags: algorithm-analysis, data-structures, heaps
---


# Question
Title: What should be the way to design code for such a situation?
I have a graph as given below:

Let us assume one node as transmitter and another as receiver.

1. We need to transfer particles in every time slot constrained by maximum particles N and minimum 0. The combination of which particle in which time slot makes a code. I mean if 2 1 0 0 is a code that means that 2 particles in slot zero 1 in slot 1 and 0 particles in slot 2 and 3
2. Now let us suppose that any particle in a time slot can take any path and suffer through at most K delays. Delays are given by number of dots. More dots more delay. The delay to particles can be assigned randomly. The maximum delay for this graph is 4 it can be generalized to K. How to design codes so that information is reliably transferred across transmitter and receiver.

I just want to know how these codes are constructed, assuming that other codes must exists to be revealed. Also please tell me the prerequisites I need for such problem as I am not a computer engineer. One way is given in here

# Answer
Off the top of my head...

Given a Packet, encode both the slot and count into the number with known limits.... a code can be computed ... and both the Sender and Receiver know what the limits are.

For example: 5 slots, and 7 possible counts (max count from 0..6 is 7 )

A CODE to determine what slot and count in that slot when it arrives

**Code = Count\_in\_slot + (slot\_number * (Max\_Counts ) )**

```
   Table of example CODES that could be sent or received

Slot            n counts
       0   1   2   3   4   5   6
      --- --- --- --- --- --- ---
 0     0   1   2   3   4   5   6
 1     7   8   9  10  11  12  13
 2    14  15  16  17  18  19  20
 3    21  22  23  24  25  25  27
 4    28  29  30  31  32  33  34

```

Decode a Slot and count from the number :

```
 Sequence Initialize all ZERO's

 for each Code received
   temp  = Code
   Count = temp mod max_count  (NOTE: Remainder of a division (Modular math )
   temp  = temp \ max_count    (NOTE: integer divide)
   Slot  = temp mod Number_of_slots
   Sequence(Slot) = Count

```

And when either all slots are received, or max time wait occurs the reconstructed sequence is completed.

ALSO NOTE: If time delay is used to close the sequence, then slots with ZERO do not need to be sent.
> 0 votes

---
Tags: discrete-mathematics, information-theory, coding-theory, encoding-scheme
---


# Question
Title: Warm starting LP solver at non-basic feasible solution
I'm approaching some continuous optimization problems by considering discrete approximations of them at different resolutions. Those discrete approximations can be solved with linear programming solvers, like GLPK.

After having solved a discrete approximation at resolution $h\_0$, I can produce a reasonably good feasible solution $x\_h$ for any discrete approximation of the problem at a higher resolution $h$. BUT, that reasonably good feasible solution $x\_h$ is in general not a corner(i.e. basic) solution.

Given that solvers like GLPK can do a warm start only at a basic solution, how can I come up with a basic feasible solution near $x\_h$ to warm start the solver with? Are there any open source, or at least free, solvers that can be warm started with feasible non-basic solutions?

# Answer
LP solvers use simplex typically, so starting from nonbasic solution doesn't have too much sense. You can try finding a basic solution to $x\_h$ by minimizing $||x-x\_h||\_p$ over your feasible region. I believe it's still an LP for $p=1$ and $p=\infty$. However, there is no guarantee warm start combined with this is faster.
> 2 votes

---
Tags: optimization, linear-programming
---


# Question
Title: Partial type inference for dependent types
I'm looking for resources on (partial) type inference for dependent types.

For example there could be a type inference scheme that fails if the term doesn't have a principal type, or a scheme that makes some choices and infers non-principal types.

I'm also not sure how to integrate type inference into constraint-based type checking.

Are there any papers on this?

# Answer
I recommend to look at (1) first, which might be the canonical early work on this problem and lead to the ATS programming language. (2) is a recent work on the same problem.

As to using constraints for type inference, (3) is probably the canonical reference.

---

<sub> 1. H. Xi, F. Pfenning, Dependent Types in Practical Programming.
2. T. Terauchi, Dependent Types from Counterexamples.
3. F. Pottier, D. Remy, The Essence of ML Type Inference.

</sub>
> 2 votes

---
Tags: reference-request, type-theory, dependent-types, type-inference
---


# Question
Title: What's the difference between a calculus and a programming language?
I think I'm pretty confused about what's called a calculus and what's called a programming language.

I tend to think, and might have been told, that a calculus is a formal system for reasoning about the equivalence of programs. Programs have an operational semantics specified by a machine, that should (I think?) be deterministic. In this way, a (correct) calculus for a language $L$ is a proof method for program equivalence.

This seems like a reasonable split to me, but is this the commonly accepted meaning? Or maybe it's even wrong?

Related, why are some operational semantics nondeterministic (assume it is confluent)? What is gained from leaving the choice of strategy open?

I'd really appreciate some clarification on these; and concrete references even more! Thanks!

# Answer
> 10 votes
The meaning of the words is not fixed, but I can give you my interpretation.

A *calculus* is something that we *calculate with* in the sense of juggling equations (think manipulation of Taylor series or computation of integrals in analysis). A calculus tells us what the rules of manipulation are, but not which ones we should used in a given situation.

A *programming language* is something that tells us *how* to calculate. It tells us precisely how to use the rules. We typically let the computer use the rules, as it is much faster. The rules may be non-deterministic, and there may be very good reasons for them being non-deterministic. It may be in the nature of the calculus that it is non-deterministc (think concurrent communicating processes), or fixing a particular strategy may be detrimental to implementation techniques and optimization.

For example, the $\lambda$-calculus is an *equational* theory. There are expressions and equations telling us when expressions are equal. The equations do *not* tell us how to apply them, although people usually have hidden agendas and they present the equations so that later on they can *derive* useful evaluation strategies from them. But in its essence $\lambda$-calculus is a bunch of equations. It is not a programming language.

In contrast, Standard ML is a programming language. It is given in terms of operational semantics, i.e., rules of computation. There are *derived* notions of equality (contextual equivalence, observational equivalence, etc.) which we can put on top of it to think of it as a kind of calculus.

Of course, there are often useful connecitons between a calculus and its manifestation as a programming language. Confluent normalization is just one way of passing from the calculus to the programming language (although sadly some people have made it into a religion of sorts). The interplay between calculi and programming languages is important: the programming languages can actually be used, but the calculi *explain* what the programs are about.

Just to annoy people, let me also state that pretending that there is no difference between a calculus and its operational manifestation sometimes leads to skewed views of programming and mini-religions within the programming community. You may try to guess which language I have in mind. (It's a very cool language!)

# Answer
> 1 votes
The goal of calculi is not just to study program equivalences, it's to study programs. An example of fancy calculus is this where the strategy (call-by-value or call-by-name) is determined locally. It could be implemented someday in a programming language but it's first studied as a calculus. You also use calculi to study type systems (with some calculi such as the one in Martin-Löf type theory also computing types).

---

I believe the main difference is that calculi are meant to be (relatively) easy to study formally while programming languages are meant to be (relatively) easy to use. This leads the the following differences:

Calculi tend to be minimalist while PLs tend to have redundancy (for loop when you already have while loop, switch when you already have if, ...) to make expressing what you want easier.

Calculi have fully specified semantics, while a PLs semantics is often described by a default interpreter / compiler.

---

Some operational semantics are non-deterministic because it allows:

* To prove things about all "subsemantics".
* To allow implementation to choose and therefore to (maybe) speed up things.
* Because sometimes, you have a "radnom()" operation, and if you don't care about probabilities but only what's possible, non-determinism is a good way to represent it.

Note that call-by-value is non-deterministic: You can choose to evaluate either the function or the argument first.

# Answer
> 1 votes
"Programming language" and "calculus" are polysemic terms, that is, they mean different things depending on the context.

In some contexts, programming languages and calculi have converged to refer to the same concept, that of a **rewriting system** based on a set of formal rules that can be "mechanically" applied.

The reason why this convergence is occasionally enigmatic to us (but not to working software developers or mathematicians) is that our job is to conceive concrete programming languages as if they were calculi, and to physically embody calculi in concrete programming languages.

To answer your question directly, the confusion between calculi and programming languages (to the extent that it exists) is not an accident, but a project. Our project. It is a testament of our relative success as a scientific discipline.

---
Tags: terminology, programming-languages, lambda-calculus, semantics, operational-semantics
---


title: Linked lists in practice

text:
# Question
Title: Linked lists in practice
I have some questions about the ideas proposed in this video.

The speaker shows an array that holds values and pointers, and he also shows a separate "free" linked list, that is updated whenever an item is added/removed.

Why are these used? Doesn't using an array / limiting yourself to a set of free nodes defeat the purpose of a linked list?

Isn't one of the perk of using a linked list the ability to traverse fragmented data?

Why use these free nodes, when you can dynamically allocate storage?

The proposed structure, to me, doesn't seem dynamic at all, and is in fact a convoluted and inefficient array.

# Answer
I have not watched the video, so I'll go by your description. There is an array of items which contain pointers to other items. These pointers form a linked list structure.

This sort of data structure tends to arise when a collection of items needs to be easy to traverse in multiple different orders. For example, a priority queue may need to be traversed both according to the elements' age and according to the elements' priority. This can be implemented with an array of elements, with new elements added at the end so that they're in age order, and a linked list or a search tree for priorities.

One common case for linked lists of array items is in a memory allocator. You ask, “Why use these free nodes, when you can dynamically allocate storage?” Well, what about the cases when you *can't* dynamically allocate storage, because you're implementing the dynamic storage allocator? The concept of “free list” is common to most memory allocators. A block of memory that isn't in use is an element of the free list. With fixed-size blocks, to free a block, you write a pointer to the current head of the free list at the beginning of the block, and you set the head of the free list to the address of this block. To allocate a block, you take the current head of the free list as the block to use, and set the head of the free list to the block that was second in the list. In pseudocode:

```
allocate() :=
    block := free_list_head
    if free_list_head is null: raise out_of_memory
    free_list_head := free_list_head.next
    return block
free(block) :=
    block.next := free_list_head
    free_list_head := block

```

Allocators for variable-sized blocks typically use fancier data structures so as to be able to merge adjacent blocks and find blocks of an appropriate size.
> 2 votes

# Answer
The linked list in the video keeps the data lexicographically sorted, while the table is not. The video is not trying to show the best way to maintain such order, just an example on something you could do with linked lists. It still takes O(N) comparison to find where to place the new item in the list, but it's actually faster than having to move the whole table to make space for the new item.

As Gilles said, it essentialy let's you get two different orderings in linear time just by traversing the list (data lexicographically sorted) or the table (data sorted by insertion time).
> 1 votes

---
Tags: data-structures, linked-lists
---


# Question
Title: What is a difference between cross-lingual IR and multi-lingual IR?
In papers usually **Cross-Lingual Information Retrieval** (**CLIR**) and **Multi-Lingual Information Retrieval** (**MLIR**) use equivalently or distinctly. I want to know is there any difference between these two terms?

# Answer
In this paper they differentiate between these two terms as follows:

> While CLIR is concerned with retrieval for given language pairs (i.e. all the documents are given in a specific language and need to be retrieved to queries in another language), MLIR is concerned with retrieval from a document collection where documents in multiple languages co-exist and need to be retrieved to a query in any language. MLIR is thus inherently more difficult than CLIR.
> 4 votes

---
Tags: information-retrieval
---


# Question
Title: What runtime complexity if DNF formula not PAC-learnable, $O(2^N)$ or $O(2^{2^N})$ runtime?
Valiant's theory of PAC learning looks at the tradeoff between expected error and algorithm runtime in different classes of learning problems. In particular, a lot of his analysis focuses on which classes of disjunctive normal form (DNF) formulae are learnable in polynomial time while minimizing expected error (PAC learnable).

However, many classes of DNF formulae are not PAC learnable. This means that learning takes an exponential amount of time based on the number of variables $N$ in the formula, i.e. the algorithm runtime is $O(2^N)$.

I assume that the DNF formula that is learned in this case is not the minimal DNF formula, since it is NP-Hard to do so, meaning the complexity is $O(2^{2^N})$.

If so, then this is confusing to me.

Say there are $2^{10}-5$ samples from $f$, and the algorithm has to predict the remaining 5 bits. If my understanding of PAC learning is correct, there is an algorithm that should be able to accurately predict the 5 bits in $O(2^N)$ time.

However, it also seems to me that to accurately predict the 5 bits the algorithm has to figure out which of the $2^{5}$ different ways of filling in the bits has the shortest DNF formula, due to Occam's razor. But, if the algorithm has to figure out the shortest DNF formula in each of the $2^5$ permutations, then it has to perform logic minimization, which has a runtime of $O(2^{2^N})$. Then, that means that if a DNF formula is not PAC learnable, its runtime is super-exponential, not exponential.

So, which is it? Does a DNF being not PAC learnable mean the algorithm's runtime is $O(2^N)$ or $O(2^{2^N})$?

# Answer
There's a misconception here. PAC learning doesn't require the learning to find the *shortest* formula. It merely requires the learner to find *any* formula that has sufficiently low generalization error. If there are multiple formulas that meet that criteria, the learner is allowed to output any of them -- not necessarily the shortest.

Take a closer look at the formal definition, and hopefully you'll see how that follows from the definition.
> 1 votes

---
Tags: machine-learning
---


# Question
Title: Why is the node with the greatest DFS post-order number not necessarily a sink?
A sink in a directed graph is a node with no outgoing edges. If I perform a depth first search, why is it that the node with the least post-order number (and thus the highest pre-order number) not necessarily a sink - isn't this node found last?

Also, intuitively, the node with the greatest post-order number should be a source - a node with no incoming edges.

# Answer
> 2 votes
The earliest finished vertex of a DFS is a leaf (or sink in your language) of the **search tree**, i.e. a leaf in the original digraph or the last seen vertex of some directed cycle.

The vertex which is finished last (biggest post order number) is the vertex where you started the search and, by construction, a source of the search tree. It may have any number of incoming edges in the original graph.

# Answer
> 2 votes
If your graph is strongly connected, there is no sink, so I guess that answers your question...

# Answer
> 2 votes
See this graph, d = pre-order, f = postorder. Vertex 4 is not a sink. For more http://www.cs.usfca.edu/~galles/visualization/ConnectedComponent.html

---
Tags: graphs, graph-traversal
---


# Question
Title: Is a two-opt move guaranteed to produce a non-worse tour?
I have a little doubt with respect to the two-opt improvement heuristic for TSP. I understand how it works, from the Wikipedia article on 2-opt and "Heuristics for the Traveling Salesman Problem". However, from my understanding and subsequent experiments, it appears this heuristic does not give any guarantee to at least not lead to a worse tour. If this is so, I don't understand how a two-opt move is any better than a random swap of cities. I would really appreciate if this can be clarified for me. Thanks!

# Answer
> 3 votes
2-Opt is a move that doesn't guarantee to give a better tour.

We use such moves ($k$-Opt, swap, insertion,..) in local searches to look for a better tour in the neighbor of the input (which is a tour).
Local search consists of browsing all (feasible) tours that can be produced with only one move from the input.
If the input tour is not improved, we call it a local optimum which may be the optimal solution.

---
Tags: heuristics, traveling-salesman
---


# Question
Title: What precisely/concisely is the "head" of a singly linked list? I ask bc of ambiguity online
So I have a pic which I think illustrates my confusion:

the read surrounds what I wonder is the head? Does head refer to a node with both a data and next, or only a node with next? In other words, which marked box does it refer to in my pic?

# Answer
You're right, there are many different definitions of a List/Linked List. No one definition is correct nor incorrect. This answer is a bit long-winded, but having a backstory on the logic behind lists is worthwhile.

### History of Lists

Let's start with the definition of a List, in Computer Science, as described by the developers of the structure (Newell, Shaw, and Simon \[1\]) for their Information Processing Language \[1\] in 1957. It was initially developed as a method for flexible memory assignment in the Logic Theory Machine.

### Definition of Lists (1957)

> $Lists$ : Lists are the general units of information in the memory. A list consists of an ordered set of items of information. Any item on a list may be either a list or an element, and these are fundamentally different types of unit. \[1\]

### Formation of Lists

> To form a list, we use a set of *location words*, each containing two addresses. One address locates an item on the list, the other address locates the next location word. \[1\]

*Location words* are JOHHNIAC \[2\]\[3\] words that contain two addresses.

> The left address is the address of the next location word, the right address is the address of the item on the list. \[1\]

Here is an example of a List containing three elements:  \[1\]

You can see in this example, the items link to nothing. This is why items are "on the list", they are attached to the list but not a direct piece of the list. Saying the first element is the "head" of a list makes no sense in this context. They are not part of the list at all.

### The Head of a List

Newell and Shaw describe the *head* of a list as the first *location word* in the list \[1\]. Thus, in a strict sense, the *head* has an address to the first element *on* the list, while itself is the first location word *in* the list.

This representation of a list was traditionally followed. This can even be seen in the LISP \[4\] programming language invented by John McCarthy. Also check the LISP 1.5 Programmer's Manual \[5\].

---

### Definition of Lists (1964)

Soon came along the idea of putting "symbols" *in* the list, rather than attaching them *on* the list. Wilkes \[6\] describes the registers (nodes) of a list as having two parts (similar to Newell, Shall, and McCarthy) in his paper *Lists and why they are useful* \[6\]:

1. The **CAR**, left free, and may be used to hold a symbol. Alternatively, can store an address memory. \[6\]
2. The **CDR** (pronounced "cudder") contains an address pointing to the next register in the list. \[6\]

Here is a simple example of a list under Wilkes' definition, with symbols *in* the list:

\[6\]

### Head of a List

> A list must start somewhere, and the address of its first register is stored in a sequence of fixed memory registers known as *base registers*. \[6\] Normally, it is not necessary to show the base registers in diagrams of lists. \[6\]

With Base registers \[6\]:

Typical representation without base registers \[6\]:

In this definition, the *head* of a list is more in line with your first picture, it is an external register, not part of the list itself that merely contains the address to the first register in the list.

---

You may be wondering why I chose these examples instead of giving you the simple wiki definition \[7\]:

> The *head* of a list is its first node.

This definition is left ambiguous most likely intentionally because there are many different implementations. We can now discuss the *head* in regards to the two examples I presented.

### The Sentinel Node (wiki \[8\])

Of these two examples, the latter is a list using a sentinel node (the base registers), the former does not. When using a sentinel, the *head* is the sentinel, the first node in the list, even though the sentinel contains no elements or addresses to elements. Clearly without a sentinel, the *head* is simply the first node in the list.

### Internal vs External Storage (wiki \[9\])

Of these two examples, the latter is an example of internal storage, the former is an example if external storage. With internal storage you could attempt to think of the *head* as the first element in the list (though I wouldn't recommend it, because it contains also the address of the next node), because the element is *in* the node. With external storage, the head contains a pointer (memory address) to the first element of the list and a pointer to the next node in the list.

### Nodes vs Elements

Much of the confusion about lists comes from the fact that many people mix up an element of a list with a node of a list. To prevent any confusion, whether you're using internal/external storage or a sentinel node or not, in my opinion, it's best not to refer to the elements (data stored in the list) as nodes of the list. Conceptually they are distinct.

The node of a list should thus contain two parts (as previously mentioned), the element or address, and an address to the next node. In programming, even if the two are not separated in code, conceptually they should be. Therefore when Wikipedia refers to the *head* of a list, it refers to the first node in the list. That node, then contains element data and an address to the next node.

---

1. Programming the logic theory machine by A. Newell and J. C. Shaw (1957, pp. 233)
2. The History of the JOHNNIAC by F. J. Gruenberger (1968) (available here for free, no sign-in required)
3. Johniac by E. Thelen (accessed Oct 29, 2017, last updated Aug 6, 2015)
4. LISP I Programmer's Manual by J. McCarthy et al. (1960)
5. LISP 1.5 Programmer's Manual by J. McCarthy et al. (1962, 2nd ed)
6. Lists and why they are useful by M. V. Wilkes (1964, pp. 1-5)
7. https://en.wikipedia.org/wiki/Linked\_list#Basic\_concepts\_and\_nomenclature (accessed Oct 29, 2017)
8. https://en.wikipedia.org/wiki/Linked\_list#Using\_sentinel\_nodes (accessed Oct 29, 2017)
9. https://en.wikipedia.org/wiki/Linked\_list#Internal\_and\_external\_storage (accessed Oct 29, 2017)
> 6 votes

# Answer
Head is a reference to the first object of class or struct that represent the link of the specified list. The object generally contains both data and link. So head is pointing to both data and next.According to your image, 2nd is the correct answer.
> 1 votes

# Answer
> Does head refer to a node with both a data and next, or only a node with next?

Head refers to the first node of your linked list. It can be a reference from an empty node which is in your words "only a node with next". Or it can be a variable that points to the first node of your list.

Practically, this would make a difference because the head will not always remain the same, so in your picture it might make sense to label the leftmost thing as the 'pointer to the head' and the first node of the linked list as the head. For example,

```
a = new Node(1);
b = new Node(2);
a.next = b;
head = a; // at this point, both a and head are pointers to the beginning of our linked list
// now we want to add c to the beginning of the linked list
c = new Node(3);
c.next = a;
head = c; // now c and head are pointers to the beginning of our linked list, but not a

```

So the concept of a 'pointer to the head' is important so that you can consistently have a pointer to beginning of your linked list (it will have to be updated every time you delete or add something to front of the linked list)

EDIT: thanks to David for pointing out in the comments that the distinction between the head and pointer to the head should be made clearer
> 1 votes

# Answer
Head in case of singly linked list is the pointer which points to the first node of the linked list. So it's not a node, it's a pointer reference.
> 0 votes

# Answer
Your confusion is understandable. As others have said, strictly speaking the head is the pointer to the first node in the list. BUT: Procedures for list manipulation - insertion, deletion in particular - can be simplified by always putting a special *stub node* at the start of the list *\[basically, this lets you eliminate the 'is this the first node?' special-case test\]*. When this is done, the stub node (or its 'next' pointer) is sometimes called the head instead.
> 0 votes

---
Tags: data-structures, linked-lists
---


title: The convoy effect in process scheduling

text:
# Question
Title: The convoy effect in process scheduling
As I understand the *convoy effect*, in the context of vehicular traffic in a road system. A slow moving group of vehicles passes through the system, slowing traffic even in areas which were not directly affected by the convoy.

How does this apply in the context of CPU scheduling? It does not seem to be an analogous situation.

# Answer
> 9 votes
Convoy Effect is a result of using First-Come-First-Serve (FCFS) Scheduling algorithm. In this case the dispatcher (short term scheduling) feeds the processes present in ready state to the processor in FIFO fashion. This is basically a simple implementation of Queue. Processes coming first gets to use the processor first.

Since it implements the **non-preemptive** policy, which means that once the process starts running it won't stop unless it completes its task or is blocked by OS because of some fatal error or I/O need, it obstructs processes behind itself. If a CPU intense process gets to run, then a number of I/O intense processes don't get to dispatched. In this case the **I/O devices are idle**. When the CPU intense process relinquish the control, the I/O bound processes quickly pass through the CPU following by adding into the I/O queues. During this period **CPU is idle**.

As you can see this method is not very efficient as both CPU and I/O devices are left idle for a long time. Apart from that this method often gives very high average waiting time.

The effect is analogous to the traffic example. Because of *slow moving vehicles*, the traffic system is turning inefficient. Vehicles that can move faster and reach their *destination (similar to exit state of a process)* quicker than the slow moving vehicles ahead of them are not able to do that. If these vehicles were able to move on their potential speed, then the road would be less congested then what it is in this case. *Vehicles are analogous to the processes in the ready queue.*

# Answer
> 10 votes
FCFS (First-Come, First-Served) scheduling can also cause blocking in a busy dynamic system in another way, known as the convoy effect.

When one CPU intensive process blocks the CPU, a number of I/O intensive processes can get backed up behind it, leaving the I/O devices idle. When the CPU hog finally relinquishes the CPU, then the I/O processes pass through the CPU quickly, leaving the CPU idle while everyone queues up for I/O, and then the cycle repeats itself when the CPU intensive process gets back to the ready queue.

# Answer
> 5 votes
In a multiprogramming system, if multiple processes are waiting for the CPU for execution in an F.C.F.S. system, and a slow processing process is utilizing the CPU then due to the convoy all fast processes waiting for CPU waits for unnecessarily long time. This is convoy effect.

# Answer
> 1 votes
in the FCFS if the first process is having large service time than other processes having shorter service time then it will lead to increase in the average waiting time , which will not in the case if in the same first shorter service time processes will be served first and then the process having large service time in the last, then it will result in lesser average waiting time then that of the first case above when we are taking the process having larger service time first. it is termed as convoy effect.

---
Tags: operating-systems, process-scheduling
---


# Question
Title: Edge Constraint satisfaction in a Directed Graph Path?
Given a directed Graph and two vertices $S$ and $D$ (source and destination) such that each of its edges has a weight of the form:

$A\_i+B\_ix\_i = V$

where $A\_0$ is a non negative integer, $B\_0$ is a positive integer, $x\_i$ a variable that can take non negative integer values (each variable used only once in the graph).

Find a positive value $V$ such that it there exists a path from $S$ to $D$ in Graph such that $V$ satisfies all edges in that path.

Of course the trivial method would be testing each positive integer value of $V$. But this might take an exponential time. Is there something better we can do to achieve the solution in polynomial time, or that is the best we have ?

# Answer
Assume first that the $x\_i$ can take any arbitrary values. Then the constraint $A\_i + B\_i x\_i = V$ just states that $V \equiv A\_i \pmod{B\_i}$. Two such constraints are contradictory if $A\_i\not\equiv A\_j \pmod{(B\_i,B\_j)}$, where $(B\_i,B\_j)$ is the GCD of $B\_i$ and $B\_j$. The Chinese Remainder Theorem should show (after some work) that any set of constraints in which no two are contradictory can be simultaneously satisfied. (Prove or refute!)

The constraint that $x\_i \geq 0$ doesn't actually impose any further constraints. Indeed, take a solution $V$ to the original problem. By adding to $V$ a large enough multiply of $\prod\_i B\_i$, we obtain another solution in which all $x\_i$ are non-negative.

This reduces your problem to the following problem:

> Given a directed graph and a set of forbidden pairs of edges, does there exist a path from $s$ to $t$ that doesn't contain a forbidden pair of edges?

Unfortunately, this problem is NP-complete, by reduction from SAT. Given $m$ clauses $\varphi\_1,\ldots,\varphi\_m$, there will be $m+1$ vertices $v\_0,\ldots,v\_m$. For each literal $\ell \in \varphi\_i$, there is a corresponding edge from $v\_{i-1}$ to $v\_i$. Two complementary literals form a forbidden pair. A legal path from $v\_0$ to $v\_m$ exists iff the instance is satisfiable.

There are now two options:

* Either your particular instance has more structure, which you can employ to get a more efficient solution;
* Or your original problem is also NP-hard.
> 4 votes

# Answer
Building on Yuval's answer, your problem is NP-complete. Yuval shows a reduction from your problem to the forbidden-pairs path problem, and from there to SAT. However as Yuval says this doesn't immediately prove that your problem is NP-complete, as the reduction goes the wrong way. I'll show a reduction in the other direction, thus proving that your problem is NP-complete.

Let $\varphi\_1,\dots,\varphi\_m$ be the clauses of a SAT instance on the variables $u\_1,\dots,u\_n$. Let $p\_1,\dots,p\_m$ denote the first $m$ primes. We'll have $m+1$ vertices, $v\_0,\dots,v\_m$. The edges are as follows:

* For each positive literal $u\_j$ that appears in $\varphi\_i$, there will be a corresponding edge from $v\_{i-1}$ to $v\_i$, labelled with the constraint $V = 1 \pmod{p\_j}$.
* For each negative literal $\neg u\_j$ that appears in $\varphi\_i$, there will be a corresponding edge from $v\_{i-1}$ to $v\_i$, labelled with the constraint $V = 0 \pmod{p\_j}$.

Now note that if there is a satisfying assignment to the SAT formula, then there is a valid path through this graph: in each clause, we pick one of the literals that is satisfied (there will always be at least one, if this is a satisfying assignment to the SAT formula), and use that to derive a path. The path will be valid, because we can set $V$ to be a value such that $V = u\_1 \pmod{p\_1}$, ..., $V = u\_n \pmod{p\_n}$ (the Chinese remainder theorem guarantees such a $V$ will exist), and then all of the edge constraints will be satisfied.

Conversely, if we have a valid path through this graph, then we can read off a satisfying assignment to the SAT formula: use $V \bmod p\_j$ as the value of the variable $u\_j$ (i.e., set $u\_j$ to true if $V = 1 \pmod{p\_j}$, or false otherwise), and then the structure of the graph ensures that this will satisfy at least one literal in each clause of the SAT formula.

This completes the reduction.
> 1 votes

---
Tags: algorithms, graphs
---


title: How to Match Socks

text:
# Question
Title: How to Match Socks
When I do my laundry I tend to make a pile of unmatched socks, putting new socks on the top of the pile and matching off pairs if two of the same sock are near the top of the stack. Since eventually socks will get buried deep in the pile I occasionally dump some of the sock pile back into the laundry pile.

I started to wonder if there was an efficient way to choose when and how I return socks from the sock pile to the laundry pile. So I made up a formalism.

We have two collections of socks, the first one $L$ represents the laundry pile and the second one $S$ represents the sock pile. We have perfect knowledge of the contents of both collections. We then have three actions:

* Move the top sock from $S$ to $L$
* Move a random sock from $L$ to the top of $S$
* Remove the top two socks of $S$ iff they match. (*Make a pairing*)

Each sock has exactly one match and at the beginning of execution all the socks are in $L$. Our goal is to empty both $L$ and $S$ so that all of the socks have been matched off in as little time as possible. I want to measure the efficiency of an algorithm as expected number of performed operations, as a function of the number $n$ of socks.

What is the most efficient algorithm for this task? What is its asymptotic expected number of operations?

---

### My Algorithm

Here's the best algorithm I was able to come up with.

In the following, it should go without saying that if you ever encounter a pair on the top of $L$ you should remove it.

We start with phase one. In phase one we will count the number of complete pairs in $L$ if there are any pairs in $L$ we will move an sock from $L$ to $S$, if there are none we will move an sock from $S$ to $L$. We repeat this process until there are exactly three socks, two of them constituting a pair, in $L$, then we begin phase two.

In phase two we move one sock from $L$ to $S$ if it is not in the pair, we move the last two socks of $L$ to $S$ creating a pair, if it is in the pair we have two socks left in $L$ one that matches the top and one that does not. We keep moving socks from $L$ to $S$ moving them back if we do not create a pair. Once we have created a pair we move back to phase one.

---

The idea for this question is similar to this question, however the actual models for sock matching are radically different.

# Answer
> 1 votes
Suppose there are $n$ socks, of $m$ types. It's easy to pair off all the socks with $O(n^2)$ expected running time. I will show an algorithm that achieves $O(nm)$ expected running time. I don't know whether this is optimal.

# Notation

Let $T$ denote the set of types of the socks, so $m=|T|$. I'll assume two socks can be paired iff they're of the same type. Let $p(t)$ denote the probability that, if you pick a sock uniformly at random from all of the available socks, its type will be $t$.

# Algorithm

Here's the algorithm. Define $t^\*$ to be the type of the most common sock (i.e., with maximal $p(\cdot)$ value). Start with an empty stack. Draw a random sock from $L$; if it isn't of type $t^\*$, throw it back and repeat until the stack contains a single sock of type $t^\*$. Now do that again: draw a random sock from $L$; if it isn't of type $t^\*$, throw it back and repeat until the stack contains two socks of type $t^\*$. Remove the pair. Now you have $n-2$ socks; recurse.

What's the expected running time of this algorithm? It takes $1/p(t^\*)$ draws until you see the first sock of type $t^\*$ (multiply by two, to take into account throwing back the ones you didn't want). Then it takes another $1/p(t^\*)$ draws to get the second sock of type $t^\*$ (again, multiply by two for the same reason). So, it will take about $4/p(t^\*)$ draws to find one pair. How large could this be? In other words, how small could $p(t^\*)$ be? Well, it's easy to see that $p(t^\*) \ge 1/m$. Consequently, after at most $4m$ draws, we have removed one pair. We repeat until we've found all pairs, i.e., $n/2$ times. (At each stage, the number of types can only decrease so the value of $p(t^\*)$ can only increase.) So, the total number of operations is at most $4m \times n/2 = O(nm)$.

---

# Possible direction for improvement

If you wanted to improve further, you could try experimenting with the following idea. Unfortunately, I don't know how to analyze its worst-case running time in terms of $n$ and $m$.

Pick a threshold $q$. Define $T\_q = \\{t \in T : p(t) \ge q\\}$. Now replace the algorithm above with one that repeatedly draws from $L$ and throws back until the stack contains a single sock whose type is in $T\_q$; then repeatedly draw and throw back until you find another sock of the same type. Once you find a match, pair them off and recurse.

How long will it take to find the first match? It will take $1/\sum\_{t \in T\_q} p(t)$ iterations to find the first sock, and (crudely) $\le 1/q$ iterations to find the second stock. More precisely, the total number of iterations will be (after some manipulation)

$${1+|T\_q| \over \sum\_{t \in T\_q} p(t)}$$

You can now find the $q$ that minimizes that value, then apply the strategy above. I don't know whether this leads to any improvement in asymptotic running time, as a function of $n$ and $m$.

# Answer
> -2 votes
I assume you get to remove the matched socks

I am going to call them
RS for random socks
UN for unmatched
MA for matched
N is total number of socks

I see no benefit to dumping the UN back periodically

As in poker a dealt down card card is still unknown. The next card is still random. You have just as much chance the first two cards pair as the last two.

1. move 1 sock from RS and place on UN
2. remove 1 sock from RS and place on UN
the chance of a match is N - 1 - (size of MA)
if it matches the top sock move the pair to MA
in this case MA is an up or known sock
3. when there are no more socks in RS move all but 1 sock from UN to RS
you don't even need to shuffle as the remaining socks will still be random
4. go to step 2. until there are zero socks in UN

Now what is the order. Assume the first pair is found in (N-1) / 2 and after that every N - 1 - MA.

```
S = N/2
UN = N
count = 0
while (UN > 0)
{
    count++
    S++
    if (count == UN - 1)
    {
       UN -= 2
       count = 0
    }
}

```

OP this code please test it out
It is slightly different than the algorithm in I don't leave 1 in UN
I am confident it does a minimum number of comparisons and minimum moves
Remove and insert are expensive operations
On your code you need to include the cost of count matches in L
You don't get to spike the pool to increase the chance of a match and not charge for those steps
If you are not picking randomly for the L I think that is cheating

```
public static void MatchSocks()
{
    Random rand = new Random();
    List<int> Laundry = new List<int>();
    List<int> Matched = new List<int>();
    List<int> Unmatched = new List<int>();
    int? LastUnmatched = null;
    int Sock;
    int count = 0;
    for (int i = 0; i < 500; i++)
    {
        Laundry.Add(i);
        Laundry.Add(i);
    }
    while (true)
    {
        count++;
        if(Laundry.Count == 0)
        {
            if (Unmatched.Count == 0)
                break;
            Laundry = new List<int>(Unmatched);
            Unmatched.Clear();
            LastUnmatched = null;
        }
        Sock = Laundry.ElementAt(rand.Next(Laundry.Count));
        Laundry.Remove(Sock);
        if (LastUnmatched == null)
        {
            Unmatched.Add(Sock);
        }
        else
        {
            if (Sock == LastUnmatched)
            {
                Matched.Add(Sock);
                Unmatched.Remove(Sock);
            }
            else
                Unmatched.Add(Sock);
        }
        LastUnmatched = Sock;
    }
    Debug.WriteLine(count);
}

```

---
Tags: algorithms, algorithm-design
---


# Question
Title: Why is learning DNF harder than learning CNF?
In the PAC-learning setting, it is easy to learn a CNF formula when we know each clause has at most $c$ variables.

We go through each positive sample, and eliminate every clause that contradicts the sample.

Learning a DNF formula is said to be much harder, but it seems a similar procedure can be used, so it is unclear to me why DNF is more difficult.

Start with all conjuctive clauses that have at most $c$ variables. Go through each negative sample, and eliminate clauses that contradict the sample.

# Answer
It's important to distinguish between $k$-CNF and CNF. A $k$-CNF formula is a CNF formula where every clauses has at most $k$ literals; a CNF formula has no limit on the number of literals in each clause.

Both $k$-CNF and $k$-DNF are efficiently, properly PAC learnable, when $k$ is constant. In contrast, as far as I am aware, it is not known whether CNF or DNF are efficiently, properly PAC learnable (no PAC-learning procedure is known for either). So there is no asymmetry.

By "efficiently, properly PAC learnable", I mean that there is a polynomial-time algorithm for PAC learning, where the hypothesis space is the same as the concept space (e.g., given labelled instances from a $k$-CNF formula $\phi$, we want to find a $k$-CNF formula $\phi'$ that has low generalization error).

Since you haven't provided any references nor told us where you got the impression that $k$-DNF isn't PAC-learnable, it's hard to know what the exact source of your misconception might be.
> 5 votes

---
Tags: machine-learning, propositional-logic
---


# Question
Title: How to order the functions based on complexity $2^n$ vs $n^{\log n}$?
How to order the functions $2^n$ vs $n^{\log n}$ based on their complexity?

I found this question in a programming website (InterviewBit). But the answer given there, $n^{\log n}, 2^n$, does not seem convincing.

The graph of the two functions also indicates that $n^{\log n}$ is more complex than $2^n$.

I also tried substituting a couple of large value for $n$ like $10^{10}$ or $10^{10000}$. They all seem to indicate that $n^{\log n}$ is more complex than $2^n$.

1. Is $n^{\log n}$ greater than $2^n$?
2. Assuming 1 is true, how to prove it without using graphs?

# Answer
Firstly, your plot is wrong. See this: https://www.wolframalpha.com/input/?i=plot%5B+y%3D2%5Ex,+y%3Dx%5Elog\_2(x)%5D

Take the base 2 logarithm of them: $\log\_2 (2^n) = n$, $\log\_2 (n^{\log n}) = \log n \cdot \log\_2 (n)$.

As you can see, $n$ is larger than $\log n \cdot \log\_2 (n)$; therefore $2^n = \omega(n^{\log n})$.

So, the answer to your first question is no. I also show you an easy proof sketch.
> 1 votes

---
Tags: asymptotics
---


# Question
Title: Devise algorithm to travel destinations in a way that you always have enough money for the next destination (getting paid at each destination as well)
This problem probably falls under some category of algorithms but I don't know which.

> A given restaurant has $b\_1..b\_n$ branches around the world. A food critic has to travel all of the branches.
>
> 1. When the critic finishes visit to the branch $1 \le j\le n$ he gets paid $m\_j$ money by his employer for the job.
> 2. For branch $j \le n-1$ he takes a flight to the next branch $b\_{j+1}$ while the flight costs $c\_j$ money. From the last branch $b\_n$ a flight goes out to the first branch $b\_1$ for the cost of $c\_n$.
>
> It is also given that the total amount of money the critic received equals the total cost of flights so: $$ \sum\_{j=1}^n m\_j=\sum\_{j=1}^n c\_j $$ At any given point the critic can only pay for the next flight out of the money he **currently** has.
>
> Lastly, the critic can choose any branch which he will visit first and the first trip will be free.
>
> Prove that the branch $j$ exists such that the critic will be able to start from $b\_j$ and visit all branches and suggest an algorithm which will find such a $j$ in $\Theta(n)$ time.

The hint which was given to us is to use queue data structure.

I thought of the following algorithm:

1) Add all branches to a queue.

2) Check if we can travel to the next branch that is if $m\_j \ge c\_{j+1}$.

1. If no, that means we don't have enough money so push the branch to the tail of the queue.
2. If yes, check if $m\_j+m\_{j+1} \ge c\_{j+1}+c\_{j+2}$ that is if the critic does travel to the next branch will he have enough money to continue from that branch?

--If yes then advance one branch in the queue.

--If no push the next branch to the tail of the tail of the queue

After one traversal of the queue we should have branches in such an order that the critic can complete the journey and branch $j$ will be at the head of the queue.

I'm on the right track? I'm not sure this proves formally enough that a $j$ indeed exists so the critic can complete the journey.

# Answer
> 1 votes
The algorithm that you suggested using a queue does not seem to be linear-time with respect to $n$, because you did not prove that each restaurant gets pushed in the queue only once (or at most a constant number of times). I suppose there are cases where a restaurant gets pushed into the queue nearly $n$ times.

However, there is a simple algorithm for this problem and I got the idea based on a similar question in \`Introduction to Algorithms' by Cormen et al. The main idea is to start from the first restaurant and fly as much as possible, until we run out of money. If we reached the end, then that was the starting point, otherwise, we can start from the place where we run out of money. It is easy to see that the next starting point is exact the place where we run out of money (because previous restaurants did not pay enough money for sustaining).

1. **Let** $i \gets 1$;
2. **While** ($i \leq n$)
3. $~~~~$ **Let** $money \gets m\_i$;
4. $~~~~$ **Let** $starting \gets i$;
5. $~~~~$ **While** ($money \geq 0$)
6. $~~~~~~~~$ **Let** $money \gets money - c\_i$;
7. $~~~~~~~~$ **Let** $i \gets i + 1$;
8. $~~~~$ **EndWhile**;
9. **EndWhile**;
10. **Output** $starting$;

The main idea behind the proof is mentioned in my second paragraph. Once you start from a restaurant $b\_i$ and run out of your money in a restaurant $b\_j$, you can make sure that none of the restaurants $b\_i$ to $b\_{j-1}$ are not good starting points.

**How to prove that such $starting$ exist?** It is possible to show that by contradiction. We know that:

$$\sum\_{1 \leq i \leq n} m\_i = \sum\_{1 \leq i \leq n} c\_i,$$

which is equivalent to:

$$\sum\_{1 \leq i \leq n} m\_i - c\_i = 0.~~~~(Eq. X)$$

Let us assume that there is no such $starting$ for which the person can start from restaurant $b\_{starting}$ and visit all restaurants maintaining a positive amount of money in his pocket. We know that starting from restaurant $b\_i$, if we run out of money in restaurant $b\_j$, this means that for every restaurant $b\_k$ ($i \leq k \< j$) there is no way to pass restaurant $b\_j$ (because we will definitely run out of money). Given our assumption that no such $starting$ exist, this means that we will have a bunch of pairs $(b\_{i\_1}, b\_{j\_1}), \cdots, (b\_{i\_m}, b\_{j\_m})$ ($i\_{x+1} = j\_{x}$) that all result in running out of money. This means that for every pair $(b\_{i\_x}, b\_{j\_x})$ we have,

$$\sum\_{i\_x \leq y \leq j\_x} m\_{i\_y} - c\_{i\_y} \leq 0,$$

which results in either of the following two cases: (1) The money becomes zero and the critic does not have money to catch up with the next flight and cannot continue flying, (2) The overall summation becomes negative, which is in clear contradiction with our very initial assumption in Eq. (X).

# Answer
> 0 votes
This is a classic question in extremal combinatorics. The idea is very simple. Run the journey from the first branch and assume you have enough money saved. Find the branch in your journey where you had the minimum money. If you start the journey from that branch, you do not need the extra money!

---
Tags: algorithms, time-complexity, priority-queues
---


# Question
Title: Space and time complexity of balanced parentheses enumeration algorithm
Consider the following recursive algorithm for printing all balanced strings with $n$ left and right parentheses. It is called with *prefix* = $\epsilon$ (the empty string):

A(*prefix*):

1. If *prefix* contains $n$ right parens: print *prefix* and return.
2. If *prefix* contains more left parens than right parens: call A(*prefix* \+ ")").
3. If *prefix* contains less than $n$ left parens: call A(*prefix* \+ "(").

As an optimization, instead of counting the number of left and right parens at each step of the recursion, we carry them around (so A gets two more parameters, which are the number of parens of teach type in *prefix*).

For example, when $n = 3$, this outputs the following strings:

```
   ()()()
   ()(())
   (())()
   (()())
   ((()))

```

# Answer
> 1 votes
This is a simple enumeration algorithm. The space complexity is $O(n)$, and the time complexity is the size of the output, since you do not doing anything useless.

By the way, the number of rows in the Catalan number. $C\_n=\frac 1 {n+1}\binom {2n} n$.

---
Tags: time-complexity, recursion, space-complexity, permutations
---


# Question
Title: Algorithm to maximize dot product between two sets of vectors
I have two sets of vectors $(\mathbf{l}\_i)\_{1\le i \le n}$ and $(\mathbf{r}\_i)\_{1 \le i \le n}$. Each vector $\mathbf{l}\_i$ is in $\[0,1\]^4$, same for $\mathbf{r}\_j$. I'd like to maximize the dot product $\mathbf{l}\_i \cdot \mathbf{r}\_j$, i.e. find tuples $(i,j)$ s.t. $\mathbf{l}\_i \cdot \mathbf{r}\_j$ is as big as possible.

---

To be clear, if $\mathbf{l}\_i=(\mathbf{l}\_{i,1},\mathbf{l}\_{i,2},\mathbf{l}\_{i,3},\mathbf{l}\_{i,4})$ and $\mathbf{r}\_{j}=(\mathbf{r}\_{j,1},\mathbf{r}\_{j,2},\mathbf{r}\_{j,3},\mathbf{r}\_{j,4})$, then:

$$\mathbf{l}\_i \cdot \mathbf{r}\_j=\sum\_{k=1}^4 \mathbf{l}\_{i,k} \mathbf{r}\_{j,k}$$

---

* The number of tuples I'd like to find should be ideally a parameter of the algorithm, i.e. find the $K$ tuples $(i,j)$ that lead to the greatest values of $\mathbf{l}\_i \cdot \mathbf{r}\_j$. I won't mention $K$ in the complexities below, let's say $K \ll n$.
* I'm looking for $O(n \log^k n)$ ideas. The naive algorithm takes $\Theta(n^2)$ time, which is too big for me ($n \approx 2^{20}$).
* My first idea was to try to solve the problem in dimension 2, with the additional constraint on the input $|\mathbf{r}\_j|=1$. In that case it is easy to design a $O(n \log n)$ algorithm: sort all $\mathbf{r}\_j$ according to their angle with $(1,0)$, then for all $i$, find $\mathbf{l}\_i$ in that list by binary search.

---

In my opinion, intermediary tasks might be:

* Try to generalize the formula $\mathbf{u} \cdot \mathbf{v}=|\mathbf{u}| |\mathbf{v}| \cos(\mathbf{u},\mathbf{v})$ to dimension $4$.
* Try to remove the condition $|\mathbf{r}\_j|=1$ from the algorithm in dimension $2$.

I have no idea on how to solve these two problems.

I'm asking this in a single question because I'm also interested in more general algorithms that may give approximations (e.g. that solve the "maximum dot product" problem in arbitrary dimension).

# Answer
> 5 votes
As a completely different approach, assuming that $d \< \log n$, one can generate $O(\log n)$ random vectors $w\_i$ with unit norm. For each $w\_i$ we look at $\langle l\_i, w\_i \rangle$ and $\langle r\_i, w\_i \rangle$. Take the top largest $O(\sqrt n)$ from each list, as potential candidates. After completing we have $O(\sqrt n \log n)$ candidates, and then we check the dot products between the pairs. It is important that $d \< \log n$ so that $O(\log n)$ vectors are sufficient to cover the unit sphere well. In your case where $d = 4$ it would seem to be that $d \<\< \log n$.

# Answer
> 1 votes
Here is another idea.

Key observation:

Let $O$ be the origin in $\mathbb{R}^4$. Let $H$ be the convex hull of the set $\\{O\\} \cup \\{l\_i : 1 \leq i \leq n\\}$. Then one may only consider those $l\_i$ which are vertices of $H$. Same for those $r\_j$.

Finding convex hulls can be done in $O(n \log n)$ time, c.f. wiki page.

The problem is then: how many vectors still remain after this procedure.

Under certain assumptions, e.g. the vectors are uniformly distributed, this reduction could be good enough to allow a brute force on the remaining vectors.

More precisely, if the vectors are uniformly distributed, then it is known e.g. from this paper that the number of remaining vectors is, in average, $O((\log n)^3)$, which is quite small.

# Answer
> 1 votes
In the case of unit-length vectors, this problem reduces to the problem of finding the $K$ pairs of closest points in 4-dimensional space. There are reasonable algorithms for that.

In particular, note that

$$\\|\mathbf{u}-\mathbf{v}\\|^2 = \\|\mathbf{u}\\|^2 + \\|\mathbf{v}\\|^2 - 2 \\; \mathbf{u} \cdot \mathbf{v},$$

where $\\| \cdot \\|$ is the 2-norm. If $\\|\mathbf{u}\\|=\\|\mathbf{v}\\|=1$, then it follows that

$$\\|\mathbf{u}-\mathbf{v}\\|^2 = 2 - 2 \\; \mathbf{u} \cdot \mathbf{v},$$

so maximizing the dot-product $\mathbf{u} \cdot \mathbf{v}$ is equivalent to minimizing the Euclidean distance between the two vectors, $\\|\mathbf{u}-\mathbf{v}\\|$. You can use any standard data structure and algorithm for nearest neighbor search for that problem, such as a $k$-d tree. In particular, when the dimension is fixed (as it is here), there is apparently a $O(n \log n)$ algorithm to find the nearest neighbor to each point, from which we can immediately find the $K$ pairs of nearest vectors and thus read off the solution to your problem. See also https://en.wikipedia.org/wiki/Closest\_pair\_of\_points\_problem.

When the vectors aren't unit-length, this trick doesn't work any longer, and I don't know how to solve your problem. The following question on CSTheory.SE says there is a $\tilde{O}(n^{4/3})$ algorithm for the problem, but I don't know if it can be done in $O(n \log n)$ time: https://cstheory.stackexchange.com/q/34503/5038

# Answer
> 1 votes
Not guaranteed to be exact at all, but likely to work pretty well. Let $m \> 1$. Perform a k-means++ clustering first (using something like a cover tree for finding the nearest centroid) with $k = O(\sqrt n)$ for each of $l$ and $r$ (where you can do up to $O(\log^{m-1} n)$ clustering iterations). Then compare all the pairwise dot products between $l$ and $r$ centroids, in order to find the top $O(\log^m n)$ clusters to consider. Then check between all the vector pairs between the clusters found. Overall complexity is then $O(n\log^m n)$, assuming that each cluster has $O(\sqrt n)$ points in it.

---
Tags: algorithms
---


# Question
Title: How to tell if a spanning tree is a shortest-spanning tree of a DAG?
I know how to calculate the shortest paths from source `s` to all other reachable vertices in a DAG (with no negative weight on the edges)

By iterating the topological sort of the graph and `relax` each adjacent vertices. Which take `O(V+E)`

However - I'm required to determine if a certain spanning tree is the shortest-path tree of some directed (may be cyclic) graph in time `O(E)`

I've got a hint from my professor to use the algorithm to find shortest paths... but I fail to see how that helps me. All I've gotten so far is just building the shortest-path tree and comparing it with the tree given and return true or false.

# Answer
> 1 votes
Draw the tree you're given and add all edges from the initial graph in a different color (e.g. red). Then the tree is a shortest-path tree of the graph (there might be several of them) iff. no red edge breaks "the shortest-path structure", i.e. iff. it is never faster to go through a red edge than only through tree edges.

Therefore, if you pre-compute the distance $d\_T(u)$ from the source to every node $u$ in your input tree, you just have to check, for every red edge of length $l$ between two nodes $u$ and $v$, whether:

$$d\_T(v) \le d\_T(u)+l$$

---
Tags: graphs, shortest-path, dag
---


# Question
Title: Proof that quicksort's running time is ∼1.39 n log n
In the fourth edition of Sedgewick's *Algorithms*, it's claimed that the running time of QuickSort is $\sim 1.39n\log\_2 n$. I'm trying to find a "simple" proof and explanation of this.

All I know is that the total running time obeys $$C\_n = C\_{\mathrm{partitioning}} + C\_{\mathrm{leftArray}} + C\_{\mathrm{rightarray}}$$

and that quicksort's average case is about $2n\log\_\mathrm{e}n$.

# Answer
> it's claimed that the running time of QuickSort is $∼1.39\\,n\log\_2n$

I don't have the book handy, but it it most certainly does not claim this. That figure is the result of a close analysis of a very specific cost measure (which "time" is not); expected number of comparisons, if I remember correctly.

The proof is given in the book, if I recall correctly.

> quicksort's average case is about $2n\log\_e n$.

This is basically the same figure since $1.39 \approx \frac{2}{\log\_2 e}$, the difference probably being a rounding artifact.

From your comment, quoting Sedgewick/Wayne:

> In summary, you can be sure that the running time of algorithm 2.5 (quicksort) will be within a constant factor of $1.39n \lg n$ whenever it it used to sort n items.

This only states that the (expected) running time is in $\Theta(n \lg n)$; this follows from the (expected) number of comparisons being what it is, plus that comparison is a *dominant* operation in Quicksort.

For what it's worth, the formulation "you can be sure" without context is misleading since it seems to ignore the worst-case, and the asymptotic nature of the result.
> 4 votes

---
Tags: algorithm-analysis, runtime-analysis, sorting, quicksort
---


# Question
Title: Decide whether a DFA accepts at least two strings
Is the following language decidable? $$L = \\{A : \text{A is a DFA and } |L(A)| \ge 2\\}$$

# Answer
First remove dead states(those which do not lead to accept states). Then run depth first search. If all accepts states are not reachable or there is a single path leading to an accept state then REJECT. If there are two different paths leading to an accept state (or accept states) then ACCEPT. If there is a cycle including a state from which an accept is reachable also ACCEPT.
> 2 votes

# Answer
More generally, suppose that you have a class of languages (represented implicitly in some way) supporting the following operations:

* Given a language $L$, decide whether $L = \emptyset$.
* Given a language $L$ and a word $x$, decide whether $x \in L$.
* Given a language $L$ and a word $x \in L$, construct $L \setminus \\{x\\}$.

Then you can decide whether $|L| \geq k$ for any $k \geq 0$. You can similarly decide whether $|L| \leq k$ and whether $|L| = k$. If you can also solve the following problem, then you can compute $|L|$:

* Given a language $L$, decide whether $L$ is infinite.

The class of regular languages, represented as DFAs, supports all of these operations (exercise!), hence you can compute $|L|$ for a regular language $L$ given as a DFA, and in particular solve your problem.
> 2 votes

# Answer
Here is another approach. Suppose that the DFA has state set $Q$, accepting states $F$, initial state $q\_0$, and transition function $\delta$. Let $M$ be the $Q \times Q$ matrix defined as follows: $M(q\_2,q\_1)$ is the number of symbols $\sigma$ such that $\delta(q\_1,\sigma) = q\_2$. Let $s$ be the indicator vector of $q\_0$, and let $f$ be the indicator vector of $F$. Then the number of words of length $n$ accepted by the DFA is $f' M^n s$, and so the total number of words accepted by the DFA is $$ \sum\_{n \geq 0} f'M^ns = f' \left(\sum\_{n \geq 0} M^n\right) s = f' (I-M)^{-1} s, $$ where the latter formula is valid if $\\|M\\| \< 1$, which will be the case if the language accepted by the DFA is finite, assuming all states are accessible (reachable from $q\_0$) and co-accessible (can reach $F$).

A similar approach without inverting any matrices is to compute $c\_n = f'M^n s$ for $0 \leq n \< 2|Q|$. It is known that the language accepted by the DFA is infinite if and only if $c\_{|Q|} + \cdots + C\_{2|Q|-1} \> 0$, and otherwise the total number of words in the language is $c\_0 + \cdots + c\_{|Q|-1}$. Note that the sequence $c\_n$ can be computed using only matrix-vector multiplication, which is more efficient than matrix multiplication.
> 2 votes

---
Tags: turing-machines, finite-automata, undecidability
---


title: Algorithm Checking

text:
# Question
Title: Algorithm Checking
Is it possible giving a well defined problem, to write an algorithm which takes in as input another algorithm and checks if that algorithm is correct.
If it isn't possible, I'm thinking of storing solutions to a large number of problem sizes, randomly selecting a smaller number of problem instances and seeing if the algorithm solves those particular problem cases.

# Answer
In theory, testing weather an algorithm terminates in a finite time is undecidable! This is the Halting Problem. Checking the correctness is harder.

But in practice, you can try to test it. This book may help you:

Introduction to Software Testing
> 4 votes

# Answer
"randomly selecting a smaller number of problem instances and seeing if the algorithm solves those particular problem cases".

That's not quite trivial. First, you can't test algorithms. You can test implementations. An algorithm doesn't actually do anything, an implementation does. And you can have an incorrect implementation of an algorithm, which might fail even if the algorithm is correct.

Second, you either need to know the solutions, or need a method to check that a solution is actually the correct solution. Third, it might be that the implementation doesn't find a solution. In that case, you need to have proof whether a solution exists or not, or the implementation needs to provide a verifiable proof that no solution exists.
> 0 votes

---
Tags: algorithms
---


# Question
Title: Why does (y < 10) imply everywhere (x > 0 ^ y < 10)?
My lecturer recently released solutions to an assignment. One of the questions was to determine the weakest precondition of:

```
{y < 10} if (x > 0 OR y < 10) -> y:=10 fi {true}

```

According to the provided solution, the weakest precondition of the selection command

```
(x > 0 OR y < 10) -> y:=10

```

is

```
(x > 0 OR y < 10)

```

I understand how the weakest predicate was arrived at, but why does the solution then state that the total assertion is **true** because

```
 (y < 10) IMPLIES EVERYWHERE (x > 0 OR y < 10)

```

Isn't y \< 10 **weaker than** (x \> 0 OR y \< 10)? Therefore, there are potential precondition states where y \< 10 but x !\> 0. Since the program doesn't have guards for such a condition, it then *aborts*.

# Answer
> 1 votes
I'm an idiot.

Of course (y \< 10) implies (x \> 0 OR y \< 10). I was somehow mistaking OR for AND. I'm dumb.

---
Tags: logic, hoare-logic, software-verification
---


# Question
Title: What formal representation is commonly used to describe compiler optimizations?
I have devised a compiler optimization that works on any structured language that has arrays assignments `array[index] = value` and counted loops `(for i = n; i < N; i++) {doTHIS}` (\*).

Now I want to represent this optimization using some formal semantics. Since I want to publish my results in a Programming Languages venue, I would like to know:

**What formal(s) representation(s) is (are) most commonly used to describe compiler optimizations?**

I have already described my optimization using operational semantics, but I'm currently reviewing this choice. Hence, I came to the community for advice.

(\*) Please forgive this C-like representation in a question asking for formal semantics.

# Answer
> 9 votes
There are many compilers, which compile widely different kinds of languages which serve widely different purposes. For example, a database language will have very different optimizations than an array-based language like APL.

Compilers themselves use several intermediate languages, from the input language, to a de-sugared version of the input language, all the way down to "fancy" assembly-like versions. You might check here to get an idea of the intermediate languages involved.

Optimizations happen at each of these stages. In general it only makes sense to state optimizations in terms of a formal execution semantics of the language in question: an optimization must preserve the *observational semantics*, aka the result of the computation. Ideally you would use the semantics to say something about the *execution time* as well: typically the number of abstract reduction steps would get lower (in certain cases) after application of the optimization.

Pragmatically, many optimizations of imperative-style languages happen on an intermediate language that looks a lot like LLVM IR. Characteristics include SSA form (no variable repeated in the left-hand-side of an assignment) and three address code (at most one assignment, and one operation per statement).

The function calls, thunks, memory layout and semantics of things like pointers are going to tend to be specific to your language.

---
Tags: formal-languages, compilers, semantics, program-optimization, operational-semantics
---