title: What makes a metaheuristic meta?

text:
# Question
Title: What makes a metaheuristic meta?
According to Wikipedia:

> ...metaheuristic is a higher-level procedure or heuristic designed to find, generate, or select a lower-level procedure or heuristic (partial search algorithm) that may provide a sufficiently good solution to an optimization problem...

So a metaheuristic is something like a shaman (master algorithm), who tries to heal a person (solve a mathematical problem) by mixing various spells and herbs (simple heuristics). But why is Evolutionary computation considered a metaheuristic, instead of a simple heuristic:

https://en.wikipedia.org/wiki/Metaheuristic#/media/File:Metaheuristics\_classification.svg

What are the simple heuristics that evolutionary computation is composed of? Is it the crossover, mutation, fitness based selection? Are these the simple heuristics?

---

Also related: Difference between heuristic and approximation algorithm?

# Answer
The distinguishing factor is that meta-heuristics are problem independent.

Look at something like Travelling Salesman. You have 2-OPT, 3-OPT, Nearest Neighbour heuristics. These are all things that really don't carry much meaning outside the specific problem of Travelling Salesman.

A Meta-heuristic, on the other hand, assumes no prior knowledge of the problem. It's not saying "this is something that's likely to produce a good solution to our problem," it's saying that "this is something that is likely to produce good search results in general."

For TSP, the heuristic is that similar solutions will have correlated fitness values. More precicely, the simple heuristic is that, given your current population, the best solutions will look similar to the best ones in your population.

This is where "meta" comes in. Your population is always evolving, which means your heuristic is evolving as your search continues.

When I learned about metaheuristics, they talked less about pure GAs and more about combined techniques, things like Genetic Local Search or Probabilistic Model-based GAs. For PMBAs, it's easier to see the heuristic evolving: you choose some probabilistic model (such as Baysean networks) modelling correlations between input bits and fitness. You search, but the heuristic for which nodes you look at next isn't something static determined beforehand, it's dynamic, based on your probability model. The model keeps evolving, which means the search keeps evolving.

The slides from the class I took are here, you might find them interesting.
> 5 votes

---
Tags: algorithms, terminology, heuristics, evolutionary-computing
---


# Question
Title: Misunderstanding the Church-Rosser property
I am contemplating the Church-Rosser property and I clearly misunderstand it, but I do not exactly know why. If $x$ and $y$ are such that $x \overset{\*}{\leftrightarrow} y$, then $x \overset{\*}{\rightarrow} y$ and since $y \overset{\*}{\rightarrow} y$, we have that both $x$ and $y$ reduce to $y$ (or $x$, for that matter). So, $x \downarrow y$. I am obviously making a mistake, but where?

$\rightarrow$ is an abstract relation on some set ("reduction"). $\overset{\*}{\rightarrow}$ is its reflexive transitive closure, $\overset{\*}{\leftrightarrow}$ is the associated reflexive transitive symmetric closure, $\downarrow$ is confluence.

# Answer
> 3 votes
> If $x$ and $y$ are such that $x \leftrightarrow^\* y$, then $x \rightarrow^\* y$

This is not true in general. It is not even true if $\rightarrow$ is confluent!

For example, consider the lambda calculus with for $\beta$ reduction. $(\lambda x. x) y \rightarrow y$, therefore $(\lambda x. x) y \leftrightarrow^\* y$, but it is not the case that $y \rightarrow^\* (\lambda x. x) y$ ($y$ does not reduce to any term).

---

The statement $x \leftrightarrow^\* y$ means that there exists a chain of reductions $x \leftarrow \rightarrow \leftarrow \leftarrow \leftarrow \rightarrow \ldots \rightarrow \leftarrow \leftarrow y$, indiscriminately mixing “reduces to” and “reduced from”. This is a lot coarser than the statement that $x$ and $y$ converge, which is usually written $x \rightarrow^\* \leftarrow^\* y$. A relation is Church-Rosser if for all $x$ and $y$ such that $x \leftrightarrow^\* y$, it is the case that $x \rightarrow^\* \leftarrow^\*$. Church-Rosser means that whenever there is a chain of reductions in arbitrary directions, then there exists another chain of reductions where all the $\rightarrow$ arrows are to the left of all the $\leftarrow$ arrows.

---

> it just seems to me that the reflexive transitive closure of any relation trivially has the C-R property

No. Taking the reflexive transitive closure doesn't help Church-Rosser along. Church-Rosser is in fact a property of the reflexive closure of a relation (if two relations have the same reflexive closure, then one is CR iff the other is) — you can see in the definition that arrows in the same direction are always taken in a group.

For example, a partial order is not in general confluent. Confluence, for a partial order, is the existence of a least upper bound.

# Answer
> 1 votes
The mistake in your reasonning is that the reflexive transitive symmetric closure $x \overset{\*}{\leftrightarrow} y$ of the relation is neither the relation $x \rightarrow y$ nor its transitive symmetric closure $x \overset{\*}{\rightarrow} y$. The transitive closure of a relation is usually a different relation (unless the original relation was already transitive), and the same holds for its reflexive transitive symmetric closure.

You have to prove that if $x \overset{\*}{\leftrightarrow} y$ is verified, then there is a $z$ such that $(x \overset{\*}{\rightarrow} z) \wedge (y \overset{\*}{\rightarrow} z)$, i.e. both $x$ and $y$ must derive $z$, but using only repeatedly the relation $\rightarrow$, i.e. its transitive symmetric closure $\overset{\*}{\rightarrow}$.

You cannot use the relation $\rightarrow$ backward as $\overset{\*}{\leftrightarrow}$ would permit.

More precisely in your reasonning, you cannot infer from $x \overset{\*}{\leftrightarrow} y\\;$ that $x \overset{\*}{\rightarrow} y$, as you do on the second line of your question.

---
Tags: term-rewriting
---


title: Kernels in parameterized complexity

text:
# Question
Title: Kernels in parameterized complexity
Can anyone explain me what (problem-)kernels are and what's the use of them? My slides say:

The kernel of a parameterized problem $L$ is a transformation $(x,k) \mapsto (x',k')$ such that:

* $(x,k) \in L \Leftrightarrow (x',k') \in L$
* $|x'| \leq f(k)$ for some function $f$
* $k' \leq g(k)$ for some function $g$
* transformation must be computed in polynomial time.

My questions are:

* How is this connected with a problem being fixed parameter tractable?
* What makes kernels useful?
* Where does this definition come from.

The example on my slides is for vertex cover, but I don't really get it, cause the slides are kind of short.

# Answer
Intuitively, a kernelization algorithm is an algorithm which in polynomial time preprocesses a given instance and outputs an instance whose size is bounded in the parameter. The goal of kernelization is (at least) two-fold. We get provable performance guarantees, i.e., we can prove upper bounds on the output instance, which has applications both in the design of algorithms, and also as a complexity measure.

More formally a kernelization algorithm (often referred to as the kernel), is an algorithm for a problem which on an input $(G,k)$ outputs an *equivalent instance* $(G',k')$ with $\max\\{|G'|,k'\\} \leq f(k)$ for some function $f$. Furthermore, the algorithm needs to run in polynomial time.

The following result shows that the power of kernels is, so to speak, equivalent to the power of fixed parameter tractability (PDF)

**Theorem** (Folklore). *A problem is fixed parameter tractable if and only if it admits a kernel and is decidable.*

Although the notion of kernel coincides with fixed parameter tractability, there is a stronger version of kernelization where we demand the function $f$ above to be a polynomial.

If you want to see the original definitions, I advice you to pick up Downey and Fellows' book on parameterized complexity, or start from Niedermeier's Habilitation thesis mentioned above. There is also a Wikipedia article on Kernelization.
> 8 votes

---
Tags: parameterized-complexity, algorithm-design
---


title: Many-one-reductions with finite image

text:
# Question
Title: Many-one-reductions with finite image
Let $K$ be the halting set and suppose $K \leq\_m A$ (under some function $f$), that is, $K$ is many-one-reducible to $A$.

1. How can $f(K)$ be a finite set?
2. Why if $B$ is recursive, is $f^{-1}(B)$ also recursive?

# Answer
> 4 votes
As the name suggests, a many-one reduction can map many instances of $K$ onto a single instance of $A$. If there are no restrictions on the power of $f$, then you can pick some $a\in A$ and $b\notin A$ and then define $$f(x)=\begin{cases} a &\text{ if }x\in K\\ b &\text{ if }x\notin K\\,. \end{cases}$$

However, if $f$ is restricted to be computable then the image of $f$ is necessarily infinite. This is because every finite set is computable so, if the image of $f$ were finite, you'd have a computable reduction from the halting set to a computable set, which is impossible because that would mean the halting set would be computable too.

If $B$ is recursive and $f$ is computable then you can decide whether $x\in f^{-1}(B)$ just by checking whether $f(x)\in B$. If $B$ isn't recursive or $f$ isn't computable, all the bets are off.

---
Tags: computability, undecidability, recursion-theory
---


# Question
Title: Why is linear programming in P but integer programming NP-hard?
Linear programming (LP) is in P and integer programming (IP) is NP-hard. But since computers can only manipulate numbers with finite precision, in practice a computer is using integers for linear programming. Because of this, shouldn't LP and IP be in the same complexity class?

# Answer
I can't comment since it requires 50 rep, but there are some misconceptions being spread about, especially Raphael's comment "In general, a continous domain means there is no brute force (and no clever heuristics to speed it up)."

This is absolutely false. The key point is indeed convexity. Barring some technical constraint qualifications, minimizing a convex function (or maximizing a concave function) over a convex set is essentially trivial, in the sense of polynomial time convergence.

Loosely speaking, you could say there's a correspondence between convexity of a problem in "mathematical" optimization and the viability of greedy algorithms in "computer science" optimization. This is in the sense that they both enable local search methods. You will never have to back-track in a greedy algorithm and you will never have to regret a direction of descent in a convex optimization problem. Local improvements on the objective function will ALWAYS lead you closer to the global optimum.

This is not so in the non-convex case. Here, there may be a global minimimum, but several local minima that a local descent algorithm will always be drawn to, in the same way greedy algorithms do when applied to NP-problems. Sometimes they find the true optimum, most of the time not.
> 19 votes

# Answer
The short answer: because you can use Integers to simulate Booleans for SAT, but when you don't restrict yourself to this, then you can't actually simulate SAT. You'll get a feasible answer, but it no longer carries any meaning in terms of whatever SAT instance you were trying to simulate.

The tough answer to this is that we don't know that they aren't in the same complexity class. Nobody has a proof that $P \neq NP$. If we understood the deeper reasons why the problems were so different, that would require that we understood why the complexity classes were different, which we don't.
> 28 votes

# Answer
The reason linear programming is "efficient" is that the solution space may be represented by a single convex polyhedron. If one is trying to find the "highest" vertex on that polyhedron (one may apply a linear transform to any linear programming problem to make "height" correspond to the quantity to be maximized), then from any vertex one may travel along edges to the highest point without ever having to go "downhill". What makes integer programming "hard" is that there isn't a continuous solution space, but there are instead many *disjoint* solution spaces, and no way to work incrementally toward the optimal solution.
> 22 votes

# Answer
The other answers are correct, but I find them a bit technical. Suppose you have swept (eliminated) a matrix and are looking for any solution and the matrix looks like this:

```
column x1 x2 x3 x4 x5 x6 | solution
-----------------------------------
       1           1  1  | 3
          1              | 1
             1     1     | 2
                2  1  1  | 1

```

In lineair programming, you can now set the non-pivot columns (x5,x6) to 0, and set x4 to 0.5 and find a trivial solution. In integer programming, you cannot just set the non-pivot columns to 0. The solution is harder (NP-hard) to find. Note also that the solutions are in $Q$, so this is not directly related to finite/infinite precision.
> 3 votes

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


title: Little-o notation

text:
# Question
Title: Little-o notation
Can anyone help me demonstrate these two statements?

$$ n! = o(n/2)^n $$

$$ n! = o(n/3)^n $$

I am sure about the first one but I don't know how to demonstrate it. As for the second one I am not sure whether it is true or not.

# Answer
These statements have nothing to do with time complexity. They have everything to do with asymptotics.

Hint: Use Stirling's approximation: $$ n! \sim \sqrt{2\pi n}\left(\frac{n}{e}\right)^n. $$ Use the fact that $2 \< e \< 3$.
> 2 votes

---
Tags: asymptotics
---


title: New Assembler in compiler

text:
# Question
Title: New Assembler in compiler
I'm currently developing my degree thesis, and the lab's idea is to design a new micro architecture, and then, be able to compile stuff for this architecture. So the question is, how do you instruct a compiler to generate your new assembler??? The general idea is to be able to compile with gcc and run netbsd or similar kernel with this new architecture. Well, thanks a lot!

# Answer
Many compilers, gcc included, are divided into two major parts: a *front-end* and a *back-end*. The front end is in charge of compiling the input language into some sort of intermediate form, and perform some of the optimization. The back-end takes this intermediate form and generates actual machine code. You only need to construct a new back-end (or even less than that). Luciano in his answer gave you a good pointer regarding that.
> 1 votes

---
Tags: computer-architecture, compilers
---


title: What is the complement of ACFG

text:
# Question
Title: What is the complement of ACFG
What is the complement of $\mathrm{ACFG} = \\{ G \mid G \text{ is a CFG and }L(G) = \Sigma^\* \\}$?

I think it is $\mathrm{ECFG} = \\{ G \mid G\text{ is a CFG and }L(G) = \emptyset \\}$.

It makes sense to me because the complement of the empty language is the universal language?

Am I correct?

# Answer
> 3 votes
First of all, the complement of a set is only defined when there is an (understood) universal set. In this case, the universal set is probably the set of all context-free grammars, but it could plausibly be the set of all grammars.

The complement of a set $A$ given a universal set $U$ is defined as the set of elements in $U$ but not in $A$; it is understood that all elements in $A$ are also in $U$. So if $U$ is the set of all context-free grammars, then the complement of ACFG is the set of all context-free grammars $G$ such that $L(G) \neq \Sigma^\*$. If $U$ is the set of all grammars then the complement of ACFG is slightly more complicated: it consists of all non-context-free grammars together with all context-free grammars $G$ such that $L(G) \neq \Sigma^\*$.

If $G$ is a context-free grammar and $L(G) = \emptyset$ then $G$ certainly belongs to the complement of ACFG1; but other context-free grammars also belong there.

1This actually depends on your definition of grammar and on the value of $\Sigma$. If $\Sigma$ is understood and non-empty then what I wrote is correct; if $\Sigma$ is part of the grammar and is always non-empty, again what I wrote is correct; but if $\Sigma$ could be empty, then $\Sigma^\* = \emptyset$, so what I wrote is wrong.

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


# Question
Title: Can nodes in red-black trees have one nil child and one non-nil child?
I don't recall hearing that nodes in red-black trees can't have one nil child and one non-nil child. However, I did hear that red-black trees have a worst-case height of $2log\_2(n + 1)$, where n is the number of nodes, and I don't see how this could be the case if nodes can have one nil and one non-nil child, as a tree could be constructed that is simply a straight line/linked list, which would have a height of n.

# Answer
> 1 votes
> Can nodes in red-black trees have one nil child and one non-nil child?

Yes. A red-black tree is a special case of binary search tree: each node is colored red or black. In red-black tree, if a child does not exist, the corresponding pointer field of that node contains the value NIL. NILs are treated as leaves.

> red-black trees have a worst-case height of $2 \log 2(n+1)$

The fact that the height is of $O(\lg n)$ is guaranteed by the red/black coloring rules (copied from CLRS):

1. A node is either red or black.
2. The root is black.
3. All leaves (NIL) are black.
4. If a node is red, then both its children are black.
5. For each node, all paths from the node to descendant leaves contain the same number of black nodes.

These rules, especially rules 4 and 5, ensure that the tree is approximately balanced: no any path is more than twice as long as any other. In terms of tree height, we have

> A red-black tree with $n$ internal nodes has height at most $2 \lg (n+1)$.

Finally,

> how this could be the case if nodes can have one nil and one non-nil child, as a tree could be constructed that is simply a straight line/linked list, which would have a height of $n$.

By the red/black coloring rules, a non-trivial (with enough number of nodes) red-black tree cannot be a straight line/linked list.

---

For more details, you may want to read the book "Introduction to Algorithms" by CLRS.

---
Tags: data-structures, binary-trees, search-trees
---


# Question
Title: Which cellular automata rules are suitable for randomizing an input sequence?
S. Wolfram has in has book "A New Kind of Science" listed 256 simple rules of cellular automata. Which of these rules could via iteration essentially contribute to render an input sequence more random in a certain sense?

Rule 170, for examples, simply produces a left shift and evidently is not of use in this, if I don't err. My limited computations with inputs that are more or less random seem to indicate that the majority of the 256 rules are even contraproductive in this context. How could one best proceed to clarify this issue or are there already relevant published results available?

# Answer
Rule 30 is probably the "most random" of all 256 rules. It has been used as random number generator, but there are some issues:

* Some initial states will result in repetitive output, which is not what we want from a random number generator. However, given that the automaton is large enough, and that the initial state is itself somewhat random, this shouldn't a problem.
* There are better ways to generate random numbers.
> 1 votes

---
Tags: automata, randomness, cellular-automata
---


# Question
Title: Solving road trip problem in linear time
Consider the following problem:

> You are on a road trip, and there are $n$ cities along a road, labeled $1$ to $n$. Conveniently, these cities all lie on a single road, and the distance between two adjacent cities is one mile. We are currently at city $1$, and would like to drive to city $n$. Each day, we can drive at most $k$ miles, before we sleep for the night. We pay $a\_i$ for lodging at the city located at mile $i$. Each lodging cost is a positive number. Given that we can spend an arbitrary number of days on the road trip, determine a plan of driving to minimize lodging costs.
>
> Input: An integer $k$, and a length $n$ array of positive integers $a\_1,...,a\_n$.
>
> Output: The minimum lodging cost to complete the road trip starting from city 1 and ending at city n.

The most trivial way of solving this problem is to adapt the well-known dynamic programming algorithm for computing the longest increasing subsequence of an array. This requires $n$ iterations and at each iteration, we must compute the minimum of the previous $k$ values, due to the restriction on distance driven per day. This yields an algorithm of time complexity $O(nk)$.

I'm wondering...is there a way to solve this problem in only $O(n)$ time? My intuition is telling me that there is a way to *not* have to check $k$ prior values at each iteration. Does anyone have an idea?

# Answer
> 6 votes
This problem *can* be solved in $O(n)$ time, using a min-queue. We can build a data structure that has enqueue, dequeue and get-min operations that all work in amortized $O(1)$ time (rather than $\Omega(\log n)$ time as greybeard seems to think).

Building a min-stack (pop, push, get-min) that does these operations in $O(1)$ time is easy (keep track of the previous minimum in a separate stack when the minimum changes due to a push, so that we can use this secondary stack to restore the previous minimum when the current minimum gets popped). To build a min-queue, we can use the classical construction that builds a queue (with amortised $O(1)$ operations) from two stacks.

The $O(nk)$ dynamic programming algorithm can be modified using the min-queue to run in $O(n)$ time.

---
Tags: algorithms, optimization, dynamic-programming
---


title: Searching through a heap complexity

text:
# Question
Title: Searching through a heap complexity
Pretend you want to search through a max-heap to find a specific element. I know there is no such option but still... Would it take worse case O(n) or O(logn) time? I am assuming O(n) since the property of a max-heap doesn't really help us unlike a bst. Thanks.

# Answer
You are correct: it's $\Theta(n)$ in the worst case. Suppose you're looking for something that's no bigger than the smallest value in a max-heap. The max-heap property (that the value of every node is at least as big as everything in the subtree below it) gives you no useful information and you must check both subtrees of every node.
> 9 votes

---
Tags: data-structures, runtime-analysis, heaps, search-problem
---


# Question
Title: How long would it take a computer with twice the processing power to solve a polynomial time problem?
Say I have some problem of $O\left(n^k\right)$ complexity.

If I were to solve the problem on a computer $x$, it would take time $t$.

Now I have a new computer $x'$, which has **double** the computing power of $x$.

How long would it take $x'$ to solve the same problem in terms of $t$?

# Answer
> 2 votes
It will take half the time of course, $t'=t/2$, and the asymptotic complexity remains $O(n^k)$ !

# Answer
> 3 votes
Comment: This actually answers a much more interesting question:

> Suppose algorithm $A$ runs in time $O(n^k)$ on inputs of length $n$. If we double the input length, how long would it take $A$ to run on the new input in terms of its running time on the original output?

The answer you were supposed to give is:

> $2^kT$, where $k$ is the exponent in the running time $O(n^k)$.

The idea is that if your running time is *exactly* $T(n) = Cn^k$ then $$ T(2n) = C(2n)^k = 2^k(Cn^k) = 2^kT(n). $$

However, the running time need not be exactly $Cn^k$, and if it isn't, you can't really tell what the exact relation is between $T(2n)$ and $T(n)$. You can come up with pathological examples like $$ T(n) = \begin{cases} 1 & \text{if $n$ is odd}, \\ n & \text{if $n$ is even}. \end{cases} $$ If $n$ is odd then $T(2n) = 2nT(n)$, and the factor $2n$ isn't bounded; yet $T(n) = O(n)$ has polynomial growth.

If $T(n) = \Theta(n^k)$ then we can say that $T(2n) = \Theta(T(n))$, but it could still be that, say, $T(2n) \< T(n)$, as in this examples: $$ T(n) = \begin{cases} 100n & \text{if $n$ is odd}, \\ n & \text{if $n$ is even}. \end{cases} $$ If $n$ is odd then $T(2n) = T(n)/50$.

---
Tags: algorithm-analysis, asymptotics, runtime-analysis, applied-theory
---


# Question
Title: Absolute orientation alignment with vectors
I have two trajectories of a moving object. Each trajectory is composed of poses at discrete time. Each pose is a translation vector and a rotation matrix.

Each trajectory defines the same path (with noise) but expressed in some arbitrary frame of reference. I need to find the relative transformation that aligns both trajectories.

This is the absolute orientation problem that can be solved with Horn's method for a collection of points in the 3D space. So, I can solve this by taking into account just the translation vectors of the poses. However, I'd like to include the rotations as well.

Does this new problem have a name? Is there any known technique to solve it?

# Answer
> 2 votes
A simple modification of Horn's approach can be made to incorporate local rotation information: rather than just matching the centers of the body (trajectory points), use several off-centered points on the body such as the endpoints of a tied reference frame (in a way, forming dipoles, quadrupoles, octupoles...). Then use Horn's method on this augmented point set.

By adjusting the remoteness of these points from the center, you can trade good translational fitting for good rotational fitting.

This aside, you can probably develop a method based on static equilibrium of two solids (formed by the whole trajectories), where elastic forces are developed between corresponding points as a function of distance and torques as a function of misalignment.

---

CAUTION: in case there is significant scaling difference, you will need to adjust the remoteness proportionally to the size of the whole trajectory, otherwise artificial discrepancies will arise because of rescaling.

---
Tags: algorithms, reference-request
---


title: Algorithm : Median of a dynamic array

text:
# Question
Title: Algorithm : Median of a dynamic array
This question is inspired by this SPOJ problem. That problem asks median of the final array, that can be done in $O(k+n)$, where *k* is the number of update queries and *n* is the size of the array.

The variant : Given an array of length **N** (of the order $10^5$), initially all elements are 0. There are **K** (of the order $10^5$) queries of type **A B**, meaning array elements in range $\[A,B\]$ must be increased by 1. After ***every*** query operation, find the median of the array.
Can this be solved efficiently (subquadratic time, ie, better than $\Omega(N^2$)?

# Answer
> 4 votes
### UPD: O$(N \sqrt N)$ solution

### Bucketing

Let's split the array into blocks of $\sqrt N$ size. For each block let's keep all values in it in an array.

Let's also keep pairs $(Number, Count)$, counting the occurrences of each number, present in the block. We will also keep these pairs in an array, sorted by the $Number$. We also keep partial sums for this array, for each $Number$ indicating number of numbers less than this, in this block. (In the beginning this can be precalculated in $O(N log N)$ ).

Let's also keep a value $Mod$, that indicates that in reality all numbers in these block are not as they are saved, but actually bigger by $Mod$. Last, for each block let's keep a pointer in the array of pairs, pointing to the first $Number$, such that $Number+Mod$ is more than or equal to the current value of the median.

### Answering query

Let's count total number of values in all blocks less than the median - simply sum all partial sums for pointers. Let's also count number of values equal to the median - by summing second components of pairs, at which our pointers point. This takes $O(1)$ for each block and therefore $O(\sqrt N)$ for each query.

If we found out that total number of values less than or equal to the median is less than ${N \over 2} + 1$, we may need to shift some of the pointers forward, since the value of median then increases by 1. In total each query we will at most need to shift $\sqrt N$ pointers by 1, making in total $O(N \sqrt N)$ shift forward.

### Updating query $(A,B)$

For blocks fully covered by the interval we can simply increase the $Mod$ values. After that some of the pointers may need to be shifted backward by at most 1, to keep their invariant (pointing at first number more than or equal to the current median). Total number of shifts backwards won't exceed $O(N \sqrt N)$ for one query.

For two blocks half covered by the query let's update values in the array in the naive way:

First, increase each of them by $Mod$ and also increase each value in our sorted array of pairs by $Mod$. Clear $Mod$.

Then let's create a hash map of all values increased by 1 in the query.

Then let's loop through array of pairs and for each $Number$ we decrease it's $Count$ by an appropriate number in the hash map, and create an entry in the second array of pairs, indicating $(Number + 1, Count)$. Once we finish, we will have all numbers in our block presented by 2 array of pairs, both sorted by the first components. Then we can merge these to in the $O(\sqrt N)$.

Finally, recalculate partial sums for this new merged array and naively find the position of the pointer by looping through it.

Seems to be it, $O(\sqrt N)$ per query but I wouldn't want to code it;)

================================================================================

Here is an idea for $O(N \sqrt{N} log N)$ solution.

### Observation: (Intuitive, Beautiful, Tested but Unproven):

By increasing the subarray by 1 we can only increase the median

* By 0 or 1, if array has odd length
* By 0 or 0.5 or 1, if array has even length

I tested this hypothesis extensively locally.

Let's assume $N \approx K$.

### Bucketing

Then let's split our queries into $\sqrt N$ groups $\sqrt N$ each. At the beginning of each block we do the following:

* Calculate the median. Let it be $M$.
* Let's introduce $L=M-\sqrt N$, $R=M+\sqrt N$, $LC$ \- number of elements less than $L$ in the array.
* For each value $X$ between $L$ and $R$ create a sorted list of all positions, in which value $X$ currently resides. We will keep each list as an implicit cartesian tree (data structure that allows cutting and merging subarray in $O(log Length)$. Example - STL Rope). This is the most computationally expensive step of the above and it takes $O(N log N)$ in the worst case, making overall complexity of these steps for all query groups $O(N \sqrt{N} log N)$.

### Answering

When we will want to find the median, we will go through all values of $X$ between $L$ and $R$ and calculate sum $LC + CN(L) + CN(L+1) + CN(L+2)+ \cdots$ until it exceeds ${N \over 2} + 1$ for some value $L+t$ which will be new median. (Or average of two consecutive values). Here $CN(L)$ denotes number of items in the sorted list that corresponds to value $L$.

### Updating

When we will want to update our structure after the next query ($A$, $B$), we will do the following:

* For each $X$ between $R$ and $L$ find subarray that contains all values between $A$ and $B$ (if we, for example, keep in the node of implicit cartesian tree minimum and maximum values in the corresponding subtree, we can find the appropriate indexes of subarray in $O(log N)$).
* Erase the corresponing subarray and insert a subarray, obtained the same way from the previous list.
* For list with numbers equal to $L$ we don't insert anything since we know that all values less than $L$ will stay less than $L$ in the scope of next $\sqrt N$ queries so we simply add them during summation as variable $LC$
* Splitting and merging implicit cartesian tree requires $O(log N)$ operations, we have $O(\sqrt N)$ cartesian trees, and our actions happen for each of $O(N)$ queries, leaving total complexity at $O(N \sqrt N log N)$.

Finally, we can save all queries in current block and then update our array, for example in $O(N + \sqrt N log \sqrt N)$ time by sorting queries and using scanline.

### Afterthoughs:

I wonder if, since median can only increase by 1 or 0.5, we can solve this problem in $O(N log N)$ time somehow. Also, same as in the answer above, it may be possible that $O(N \sqrt N log N)$ can be optimized to $O(N log^2 N)$, although it is not obvious to me, how.

# Answer
> 3 votes
Assuming you're still in SPOJ context, you probably want a $\mathcal{o}(n^2)$ solution to fit the $1$ second time limit.

Here's a complicated solution that uses $\mathcal{O}(n)$ memory and has an $\mathcal{O}(n\sqrt{n} \log^2{(n)})$ runtime (whew!) assuming $\mathcal{O}(n) = \mathcal{O}(k)$. It probably wouldn't execute in a second, but might fit within 5-10.

**NOTE:** I'm going to conjecture that a $\mathcal{o}(n \log^3{n})$ solution is possible. This follows from my use of $\sqrt{n}$ buckets, and in my experience buckets can always be replaced by a tree (Splay?) for a $\mathcal{O}(\log{n})$ instead of $\mathcal{O}(\sqrt{n})$. Additionally I use a binary search that seems excessive. As a general rule of thumb, if the memory and time bounds are not balanced, you can improve one or the other until they are.

**Insights:**

*Not truly online*

In these problems, normally all the input is digested before any output is expected. We can use the information for all of the queries, before answering any of them. Even if it was interactive, this strategy would still work if $k$ was known ahead of time.

*Replace the array*

In the original problem, there are $\mathcal{O}(n)$ intervals of interest. These intervals are created by the start and end points of the $\[A, B\]$ query ranges. Intuitively, imagine dropping all of the start / end values on a number line. This creates the intervals, $x\_1,x\_2, \cdots, x\_m$, where $m \le n$. In the original problem, you realized that all the "haystacks" or array elements in any $x\_i$ take the same value or height. Effectively, the $x\_i$ are our smallest unit of concern.

*Bucketing*

If we group the intervals into $\sqrt{m}$ buckets of size $\sqrt{m}$, you can update any range of intervals in $\mathcal{O}(\sqrt{n})$. This will be clearer later.

*Select augmented BST*

It's well known that by storing the size of the sub-tree of each node, counting the elements less than some cutoff takes $\mathcal{O}(\log{n})$ time. We'll be storing the sum length of intervals instead, but the operation is identical.

*Binary Searching for the Median*

If we have an efficient way to count how many "haystacks" are under a given height, we can binary search to find the median.

**Setup:**

Let $p = \sqrt{m}$.

Now we create buckets, $b\_1 = \[x\_1, x\_2, \cdots, x\_{p}\], b\_2 = \[x\_{p + 1}, \cdots\], \cdots, b\_p = \[x\_{(p-1)p+1}, \cdots, x\_m\]$. We group the $x\_i$ into $p$ clumps of size $p$. Each bucket has a corresponding "offset", $s\_i = 0$, which is just a counter per bucket.

For each $b\_i$, build a augmented BST $BT\_i$ out of $x\_u \in b\_i$ keyed on the height of $x\_u$. Each node in $BT\_i$ will store the sum of the lengths of the intervals in its subtree, this is a well-documented strategy and can be maintained in $\mathcal{O}(\log{n})$ per operation. Remember that the length of an interval is in units of "haystacks", the number of array elements contained.

The $BT\_i$ is purely to be able to answer in $\mathcal{O}(\log{n})$:

How many "haystacks" have height under $v$?

**Dirty Stuff:**

Iterate through the $k$ queries and update the data structure. This involves:

1. Update all affected $x\_i$. If the query range completely encompasses any $b\_j$, just add $1$ to $s\_j$. Otherwise, manually update the $x\_i$ in $BT\_j$, which takes $\mathcal{O}(\log{n})$. There are at most $\sqrt{m}$ of each case, for a $\mathcal{O}(\log{(n)} \sqrt{2n})$ runtime.
2. Binary search for the median in the range $\[0, k\]$. We choose some guess $v$, and then ask all $\sqrt{m}$ $BT\_i$ how many elements have height or value under $v$. In the BST select algorithm, we include the offset $s\_i$ without affecting the runtime. This process takes $\mathcal{O}(\log{(k)}\log{(m)}\sqrt{m})$ or $\mathcal{O}(\log^2{(n)}\sqrt{n})$. Return when $v$ is the median.

There are $k \le n$ queries, for a $\mathcal{O}(n \sqrt{n} \log^2{(n)})$ total runtime, with $\mathcal{O}(m) = \mathcal{O}(n)$ memory, since we have constant storage for each $x\_i$ and $s\_u$.

I left out a lot of the details. Reply in the comments if you have questions, or if this approach has mistakes. Also this solution follows my hacky, inelegant style. Hopefully someone comes along with a cleaner, faster solution.

# Answer
> 1 votes
Consider a sequence $(A\_i,B\_i)\_{i=1}^k$ of update queries, i.e. $1 \leq A\_i \leq B\_i \leq n$ for all $i \in \[1..k\]$. I will show how to solve the problem in time $\Theta(K \log n)$ and space $\Theta(n)$ where $K = \sum\_{i=1}^k (B\_i - A\_i + 1)$.

**Idea:** Keep a sorted copy of the counter array and maintain pointers back and forth. When an entry is increased to be larger than its right neighbour -- say this one has value $c$ -- swap it across the block of subsequent entries with value $c$; the correct position can be found with binary search.

**Algorithm:** Assume that we have array `A` of length $n$ with pointers and array `B` of the same length with pairs of numbers and pointers. Initially, we have `A[i] = i` and `B[i] = [0,i]` for all `i`.

Then, the algorithm is as follows:

```
for each (a,b) in Updates {
  for i = a to b {
    j = A[i]
    B[j][0] += 1

    if ( B[j][0] > B[j + 1][0] ) {
      j' = BinarySearchInB(B[j + 1][0] + 0.5)
      i' = B[j][1]

      // Swap everything
      B[j][0]  -= 1
      B[j'][0] += 1
      A[i'] = j
      A[i] = j'
      B[j][1] = i'
      B[j'][1] = i
    }
  }
}

```

We assume that `BinarySearch` returns the index in `B` left of the gap the passed value belongs in; this is the right-most index with value `B[j + 1][0] = B[j][0] - 1`.

The algorithm clearly has the claimed cost. If $K \in o(n^2)$, this algorithm is indeed subquadratic.

---
Tags: algorithms, search-algorithms
---


# Question
Title: Finding the best N length combination between M items
Lets say I have a few million random items. Each item has 6 attributes: Type, Cost, Strength, Stamina, Agility and Intelligence. Type is one of 4 different possibilities, the other 5 are various numbers

Now I must produce a set of 4 items where the inputs are X (the maximum cost of all items) and Y (one of the latter 4 attributes that is favored) so that

1. Each of the types is present exactly once
2. The total cost must be below a certain amount (X)
3. The attribute determined by Y must be the highest among all possible combinations

Currently I'm doing this in a brute force manner, just trying every single combination and comparing it to the current best result but its very time consuming. I was wondering if anybody knows of an algorithm or something that would cut down the execution time?

# Answer
> 2 votes
This problem is similar to Knapsack Problem and it is NP-Complete. You may find its proof in here

---
Tags: algorithms
---


# Question
Title: Efficiently compute a complete set of representatives of cyclotomic cosets of $2$ modulo $2^n-1$
Let $n \> 1$. For an integer $k$ with $0 \leq k \leq 2^n-2$ the cyclotomic class $C\_k$ of $2$ modulo $2^n-1$ is the set given by $$C\_k = \\{k, k\cdot 2, k \cdot 2^2 , \ldots, k\cdot 2^{n-1} \pmod {2^n-1}\\},$$ where the entries are reduced modulo $2^n-1$. Note that either $C\_k = C\_i$ or their intersection is empty. A set $\\{a\_1, \ldots, a\_m\\}$ of integers in $\[0, 2^n-1\]$ is called a complete set of representatives of the classes if $C\_{a\_j} \neq C\_{a\_i}$ whenever $i \neq j$ and $$ \bigcup\_{i=1}^m C\_{a\_i} = \\{0, 1, \ldots, 2^n-1\\}. $$

I am interested in, given $n$, efficiently computing the corresponding complete set of representatives of the cyclotomic classes. Any ideas? I'm hoping to be able to compute this for large enough $n$. Thanks!

# Answer
> 2 votes
You can use simple enumeration. This will be about as fast as you can achieve, for a modulus of the form $2^n-1$.

Namely, for each possible $k$, you check whether $C\_k$ is a new set (distinct from the ones you already know about). If it is, you add it to the set; if it isn't; you skip it and move onto the next $k$.

This gives an algorithm like the following:

1. Set $S := \emptyset$ and $A := \emptyset$. ($A$ holds the set of representatives; $S$ holds the set of elements covered by one of the corresponding cyclotomic classes.)
2. For each $k=1,2,\dots,2^n-1$:

* If $k \notin S$, add $k$ to $A$ and set $S := S \cup C\_k$.

The running time of this algorithm will be $\Theta(2^n)$.

This is also within a $\Theta(n)$ factor of optimal. In particular, any algorithm must have running time at least $\Theta(2^n/n)$. The reason is that, for a modulus of the form $2^n-1$, the output size of any correct algorithm must be $\Theta(2^n/n)$: there are $\Theta(2^n/n)$ distinct cyclotomic classes. Therefore, no algorithm can run faster than $\Theta(2^n/n)$ time, since it will take at least $\Theta(2^n/n)$ time to print/construct the desired output.

Why is the output size $\Theta(2^n/n)$. Well, for the specific modulus $2^n-1$, it is guaranteed that each cyclotomic class has size $n$. (Proof: $2^n \equiv 1 \pmod{2^n-1}$, so no cyclotomic class can have size larger than $n$. Also $2^j \< 2^n-1$ when $j\<n$, so $2^j \not\equiv 1 \pmod{2^n-1}$ when $j\<n$. Therefore each cyclotomic class has size exactly $n$.) This result is specific to the particular kind of modulus you are focusing on.

---
Tags: efficiency
---


# Question
Title: Does a collision occur if two packets are sent at the same time in Slotted AHOLA?
There's something I don't really understand about the Slotted AHOLA protocol, and I hope you can help me: what happens if a station wants to send two packets *at the same time*? Will it be considered as a collision? If not, when will the first and second package be sent?

I did some research here but all I found was probability formulas that I haven't seen yet...

# Answer
> 2 votes
A station is not allowed to send two packets at the same time. Each station is only allowed to send one packet at a time. If the station has multiple packets it wants to send, it can start sending one of them but it must queue the others and wait to send them later.

The protocol does not impose any requirements on how long a station must wait to send the other packets. Suppose Alice has two packets to send. Alice is required wait to send the second packet until some later point after she has finished sending the first packet. Beyond that, it's up to her exactly when he tries to send it. The protocol doesn't specify anything in particular. Some stations might try to send the second packet immediately after they finish sending the first packet. Other stations might wait a while (for whatever reason) in between. There are no guarantees and no requirements.

# Answer
> 1 votes
In a network interface you have always a transmission queue for the packets waiting to be transmitted. So if you have two or more packets at the same time to be transmitted, you transmit the first one and put the other ones in the transmission queue. When you have finished with the transmission of the packet (after eventual retransmissions), you dequeue another packet and transmit it.

---
Tags: communication-protocols
---


# Question
Title: Does there exist a problem that is hard to do in parallel?
I am looking for a workload which is hard to paralellise/distribute between multiple machines.

For example, integer factorization does not go 10 times faster if you have 10 machines to split the load, but is there a better example?

# Answer
> 2 votes
Linear programming is **P**-complete with respect to either logspace or **NC** reductions (I'm not sure which). As such, it's unlikely to be efficiently parallelizable because, for either kind of reductions, that would imply that **P$\\,=\\,$NC**. It's generally believed that **P$\\,\neq\\,$NC**.

There's more information on Wikipedia's **P**-completeness page.

---
Tags: complexity-theory, linear-programming, factoring, primes
---


# Question
Title: Transformation from one feature space to another
I have found the following example:

> As an example consider the case when the input space $ {\mathcal{X}}$ consists of images of $ 16\times 16$ pixels, i.e. $ 256$ dimensional vectors, and we choose $ 5$th order monomials as non-linear features. The dimensionality of such space would be
>
> $\displaystyle \left(\begin{array}{c}5+256-1\\ 5\end{array}\right) \approx 10^{10} \\;$
>
> Such a mapping would clearly be intractable to carry out explicitly. We are not only facing the technical problem of storing the data and doing the computations, but we are also introducing problems due to the fact that we are now working in an extremely sparse sampled space. By the use of the SRM principle, we can be less sensitive to the dimensionality of the space and achieve good generalization.
>
> The problems concerning the storage and the manipulation of the high dimensional data can be avoided. It turns out that for a certain class of mappings we are well able to compute scalar products in this new space even if it is extremely high dimensional. Simplifying the above example of computing all $ 5$th order products of $ 256$ pixels to that of computing all $ 2$nd order products of two ''pixels'', i.e.
>
> $\displaystyle {\boldsymbol{x}} = (x\_1,x\_2)$ and$\displaystyle \quad\Phi({\boldsymbol{x}}) = \left(x\_1^2,\sqrt{2}x\_1x\_2,x\_2^2\right)\\;$

The problem that I have is in understanding the last formula, from where does the author gets those values for the individual transformation? To me, it seems that he is applying the formula of analytical geometry of a circle, but I am not quite sure.

Also how does the author apply the transformation from $ {\mathcal{X}}$ to $\displaystyle\quad\Phi({\boldsymbol{x}})$?

# Answer
> 2 votes
This is just the explicit form of the feature map for a homogenous, degree 2 polynomial kernel. Here your input space is $\mathbb{R}^2$ and the feature space can be identified with $\mathbb{R}^3$. The point the author is making is that instead of computing the feature map explicitly, and then taking the Euclidean inner product $\langle \Phi(p),\Phi(q)\rangle$, you can just compute $\langle p,q\rangle^2$.

---
Tags: machine-learning, classification, svm
---


# Question
Title: Can you generate random linear programming problems?
I looked at Linear Programming, and it are problems like this:

> You know that Cabinet X costs 10 cents per unit, requires 6 square feet of floor space, and holds 8 cubic feet of files. Cabinet Y costs 20 dollars per unit, requires 8 square feet of floor space, and holds 12 cubic feet of files.
>
> You have been given 140 dollar for this purchase, though you don't have to spend that much. The office has room for no more than 72 square feet of cabinets.
>
> How many of which model should you buy, in order to maximize storage volume?

But you notate them in special form, so that you can genericly describe many of such problems.

Now suppose I replace all the values in this problem (10, 6, 8, 20, 12, 140, 72) with random other numbers, so I randomly create a completely new problem.

* Do they take longer to solve, than to verify the solution?
* Can I check that they are solveable without solving them?
* Can I check how difficult they will be to solve, without solving them?

# Answer
> 5 votes
Sure, of course you can create random linear programming problems. Why not?

Yes, in general, you can usually verify the solution to a linear programming problem faster than you can find the solution. Verifying the solution just involves plugging into the equations and checking that all equations hold. Finding the solution requires a bit more work (e.g., the simplex method, interior point method, ellipsoid method, something else).

However, as you may know, linear programming problems can be solved in polynomial time, and solutions can be verified in polynomial time. Therefore, the difference between "time to solve" and "time to verify" is not as huge as for (say) NP-complete problems.

The best way to check that a linear programming problem is solvable is to solve it. If you want a slight improvement, you can simply test whether the constraints admit any feasible solution. The way you test feasibility is by omitting the objective function (or replacing it with a trivial objective function) and giving it to a LP solver; the solver will then tell you whether the linear program has a feasible solution or not. If it has a feasible solution, then it is solvable; if it doesn't have any feasible solution, it isn't solvable. In practice, testing for feasibility might be somewhat faster than solving it, for many problems. However, there are no guarantees. Based on theoretical work, we know that the worst-case running time to test for feasibility is approximately the same as the worst-case running time to find the optimal solution.

I know of no perfect way to test how difficult they will be to solve, other than solving it. In practice, though, linear programming solvers are so efficient that a problem of the sort you list (with half a dozen variables and a dozen or so constraints) will be solved almost instantaneously, no matter what values you use -- so there is no point in trying to figure out how difficult it will be to solve.

---
Tags: linear-programming, randomness, integer-programming
---


# Question
Title: Is there a generally agreed short notation for "a points to b"
Is there a conventional symbol for "points to" or "is a pointer to". I've been using a short right arrow; for example "a is a pointer to b" would be (approximately)

```
a -> b

```

but I wonder whether a short double right arrow would be better:

```
a => b

```

Best of all would be to know, and use, a universally-accepted standard symbol, if there is one?

# Answer
The problem with your question is that pointers and pointers semantics may vary significantly from language to language. Even your question is ambiguous. So you are asking a question about notation, i.e., about syntax, which is largely a matter of arbitrary convention, but it is not even clear what is the semantics intended by your question.

You apparently use as synonyms "a points to b", "a is a pointer to b", "a -\> b". But I am not sure what is the meaning and context. Does it assert that `a` is actually pointing to `b` (descriptive meaning) or does it modify the data so that `a` is now pointing to `b` (imperative meaning). Then what is `b`, or what can `b` be. Is it the location of some value, or is it the value of whatever is pointed by `a`. Is it intended to be part of a programming language syntax, or of the metalanguage used to discuss about programs.

If you have `a -> b` and `c -> b`, does it imply that `a = c`. Furthermore, if `a` and `c` are pointers, what is the meaning of `a = c`? See for example "shallow and deep equality".

Actually all this is often an issue of designation of container and content. A pointer is a designation for a container (a memory location, for example), and the content of that container may vary. But the content may also include container designation.

One major problem is that notations are often ambiguous as they often do not clearly distinguish between container and content, often implicitly casting one into the other.

If you consider a variable, say an integer variable `x` in some programmning language, this variable is actually a container where you can change the content (which is supposed to be an integer). But, within the scope of its declaration, `x` will always be the same container. An integer variable is actually a pointer constant: a location designator.

Then, can you write `x -> 3` to indicate that `x` denotes a pointer constant toward a location containing the value `3`?

Or is the arrow supposed to point on the right to whatever container is "designated" by the expression on the left. But if you have a pointer constant (i.e. a pointer value) on the left, what is the meaning of the notation.

Now, you can have pointer variables, which may contain a container. They can appear through explicit declaration, or via other mechanism such as parameter passing by reference.

When sharing a meal with other people, you can ask for the bottle or for the wine. It will mean the same. But in programming context, more precision may be needed.

So my first reaction to your question is: *Could you be more precise about the semantics you intend to express, before you suggest agreeing on a standard notation?*

Another minor point is that, while asking your question, you seem to suggest that a double shafted arrow `=>` would be better than a single shafted on `->`. But you do not give any hint as to why it might be better. This makes me uneasy, especially wen I am not even sure of what you want to talk about, and in what context.

Since this is supposed to be an answer rather than further questions, I would suggest that the lack of a standard may well come from the fact that programming languages vary significantly in their use of pointers, and on the semantics attached to various constructs using pointers. We can hardly standardize notation when what is to be denoted is not itself standardized.

Hence, our only recourse is to choose for ourselves a notation that is intuitive and consistent in its intended context, and define it precisely together with the associated semantics. I insist on consistency since there are many things you may want to do with pointers, and it is important that the notations for each remain intuitive, and that they combine naturally and consistently. The issue of equality is an example.
> 1 votes

# Answer
No. There is no standard, accepted notation. Different papers tend to use different notations. So, choose one that is suitable for your needs and define it before using it.

Here are some examples of notations I've seen used, in different contexts:

* I've seen some papers on points-to analysis use $\text{pt}(v)$ to refer to the set of objects that $v$ might point to. This allows you to write $b \in \text{pt}(a)$ if you want to say that $a$ points to $b$. This is convenient in that domain, because points-to analysis is a "may" analysis: for each variable $v$, it keeps track of all the objects that $v$ could potentially point to (along some feasible path of the program).
* As another notation, in some papers I've seen people draw heap graphs, where each vertex represents a variable and each edge represents a points-to relationship.
* As yet another notation, I've seen people use notation like $a \mapsto b$ to indicate that $a$ points to $b$.
* Steensgaard's seminal paper on points-to analysis used a notation like $A \vdash x : \text{ref}(\alpha)$ to mean, very roughly, that $x$ points to $\alpha$, more or less. Warning: this is not really an accurate statement of what that notation means. (Actually, $\alpha$ is a type -- see the original paper for details, before trying to use notation like this.)

There are probably many others as well.

My advice is to know your audience, choose a notation that will work well for your purposes, and use that. You might read other papers that are working in a similar area and see what notation they use, and try to use something similar if it is suitable for your needs, in hopes of choosing something familiar to your audience. But whatever you do, define your notation before first use, as there is no absolute accepted standard here.
> 0 votes

---
Tags: notation
---


# Question
Title: Extended Compact Genetic Algorithm question
I have a question regarding the ECGA algorithm. This is what I'm currently studying. If ECGA builds a model of the parent pool using the 'minimum description length' (MDL) measure, why cannot we simply choose the model which has the most likely fit of the parents?

Thanks.

# Answer
Read the answer from a thread on Google, thanks to Jeremy P. Harford. (Posted with permission.)

> ...You can! Standardized algorithms can always be altered to better fit your needs. They're generalized forms, and specific applications will often have better fits.
>
> But when you start talking about likeliness, be careful. Leveraging Bayes requires recursive optimization regarding which there are (too many) patent trolls and a performance pitfall that can be tricky to avoid. Plus, further empirical sampling can invalidate your algorithm.
>
> And when I say there are too many patent trolls, understand that people who know nothing about Bayesian statistics nor programming are granted patents by other people who know nothing about Bayesian statistics nor programming. It's a mess.
>
> In this case, applying Bayes can create two tiers of algorithms that don't always complete. Depending upon your use case, that can get rather hairy. It's usually a good idea to implement the generic algorithm first, and then alter it as needed -- kind of like when you replace standard containers with use case optimized custom containers.
> 1 votes

---
Tags: algorithms, genetic-algorithms
---


# Question
Title: Skienna's recursive algorithm for edit distance
I'm having some trouble understanding part of Skienna's algorithm for edit distance presented in his Algorithm Design Manual. I'm posting the recursive version, prior to when he applies dynamic programming to the problem, but my question still stands in that version too I think.

He provides the following code:

```
#define MATCH       0
#define INSERT      1
#define DELETE      2

int match(char c, char d)
{
    if (c == d) return(0);
    else return(1);
}

int indel(char c)
{
    return(1);
}

int string_compare(char *s, char *t, int i, int j)
{
        int k;                  /* counter */
        int opt[3];             /* cost of the three options */
        int lowest_cost;        /* lowest cost */

        if (i == 0) return(j * indel(' '));
        if (j == 0) return(i * indel(' '));

        opt[MATCH] = string_compare(s,t,i-1,j-1) + match(s[i],t[j]);
        opt[INSERT] = string_compare(s,t,i,j-1) + indel(t[j]);
        opt[DELETE] = string_compare(s,t,i-1,j) + indel(s[i]);

        lowest_cost = opt[MATCH];
        for (k=INSERT; k<=DELETE; k++)
                if (opt[k] < lowest_cost) lowest_cost = opt[k];

        return( lowest_cost );
}

```

I am having trouble understanding the logic behind how the indices are decremented when arriving at opt\[INSERT\] and opt\[DELETE\]. They seem backwards to me.

How can I prove to myself that they are correct?

# Answer
> 2 votes
The two strings `s` and `t` are compared starting from the high index, down to index `1`. This is not visible since the initial call to `string_compare` is not provided. The `i` and `j` arguments for that initial call are the length of strings `s` and `t`.

It should be noted that `s` and `t` could be globals, since they are the same in all calls.

A call to the function `string_compare(s,t,i,j)` is intended to compute the minimum edit distance of the prefixes `s[1..i]` and `t[1..j]`. It first compares the two strings at indices `i` and `j`, and the recursively at lower indices.

It always tries 3 ways of finding the shortest distance:

1. by assuming there was a match or a susbstitution edit depending on whether `s[i]==t[j]`;
2. by assuming there is an insertion edit of `t[j]`;
3. by assuming there is an deletion edit of `s[i]`;

Then it computes recursively the sortest distance for the rest of both strings, and adds 1 to that result, when there is an edit on this call.

When `s[i]==t[j]` the two strings match on these indices. Hence the corresponding indices are both decremented, to recursively compute the shortest distance of the prefixes `s[1..i-1]` and `t[1..j-1]`. A proper match does not increase the distance. Hence dist(`s[1..i]`,`t[1..j]`)= dist(`s[1..i-1]`, `t[1..j-1]`).

When `s[i]=/=t[j]` the two strings do not match, but can be made to match by a substitution edit. Hence the same recursive call is possible, but the resulting shortest distance must be incremented by one for the substitution edit. Hence dist(`s[1..i]`,`t[1..j]`)= dist(`s[1..i-1]`, `t[1..j-1]`)+1.

That is why the function match returns `0` when there is a match, and `1` when there is none.

Another possibility is not to try for a match, but assume that `t[j]` is due to an insertion edit in the case of the smallest distance. Hence that inserted symbol is ignored by replacing `t[1..j]` by `t[1..j-1]`, ie by computing the shortest distance of `s[1..i]` and `t[1..j-1]`, which is `string_compare(s,t,i,j-1)`, and then adding `1` for the insertion edit.

The next and last try is the symmetric one, when one assume that the symbol `s[i]` was deleted, and thus does not have to appear in `t`.

The results of the 3 attempts are strored in the array `opt`, and the smallest value of the 3 is kept as shortest distance for `s[1..i]` and `t[1..j]`.

The decrementations of indices is either because the corresponding string elements match, or because they have been taken into account by an edit operation.

---
Tags: algorithms, edit-distance
---


# Question
Title: Efficient computation of traces of all primitive elements in field extensions of GF(2)
Let $n \> 1$ and let $\mathbb{F}\_{2^n}$ be the finite field with $2^n$ elements. The trace function $T(x) = x + x^2 + x^{2^2} + \cdots + x^{2^{n-1}}$ is an onto linear transformation from $\mathbb{F}\_{2^n}$ to $\mathbb{F}\_2$. There are $\phi(2^n-1)$ primitive elements in $\mathbb{F}\_{2^n}$ (generators of the cyclic multiplicative subgroup of the field) where $\phi$ is Euler's totient function.

I am interested in computing the traces of all the primitive elements in $\mathbb{F}\_{2^n}$ efficiently. Note that all the primitive elements are given by $\alpha^k$ where $\alpha$ is one of the primitive elements, and $\gcd(k, 2^n-1) = 1$. Moreover two primitive elements $\alpha^k$, $\alpha^s$ have the same trace if and only if $k \equiv s\cdot 2^i \pmod{2^n-1}$ for some $i$ with $0 \leq i \leq n-1$. This means we need to compute $\phi(2^n-1)/n$ traces.

Is there an efficient algorithm to do this?

# Answer
> 2 votes
It's straightforward to solve this problem in time $\phi(2^n-1)$ field operations, and there's no hope to do significantly better than this.

Computing the trace of a single element can be done in $n$ field operations (just by applying the definition). So, we can simply compute the trace for each of the $\phi(2^n-1)/n$ elements with distinct trace. The running time will be $n \times \phi(2^n-1)/n = \phi(2^n-1)$.

There is no hope to do significantly better than this. There are $\phi(2^n-1)$ primitive elements in the field. If you want an algorithm to output the trace of all of those values, the length of the output from the algorithm has to be at least $\phi(2^n-1)$. It follows that the running time of any such algorithm has to be at least $\Theta(\phi(2^n-1))$. So, you can't do asymptotically better than the straightforward algorithm.

Finally let me point out that $\phi(2^n-1)$ is exponentially large in $n$ (in general). This means that any algorithm for your problem will have running time that is exponential in $n$. This means that no algorithm can possibly be efficient for anything except very small values of $n$.

---
Tags: algorithms, discrete-mathematics, number-theory
---


# Question
Title: Correctness of splitting an undirected tree into a forest of trees with even number of children
Given an undirected tree (i.e. a tree without any designated root) of even number of nodes. The task is *to remove as many edges from the tree as possible* to obtain a forest of trees, where each such tree contains even number of nodes. And return/output number of removed edges as an output/answer.

Counting maximum number of removed edges is relatively simple:

1. Choose any node as a root node;
2. Recursively traverse a tree using depth-first approach;
3. Count number of children of each sub-tree (from bottom to up), and cut sub-tree from the tree if this sub-tree has even number of children (i.e. simply increment counter of removed edges);

This solution is correct but I don't understand why.

I would like to see proof of correctness of such algorithm.

In particular, I have the following doubts (when I'm thinking on this solution):

1. Why starting DFS from any chosen root gives correct maximum number of removed edges?
2. Why cutting sub-trees with even number of children from bottom to up gives correct result?

I wrote on paper all possible configurations 1, 2, 3, 4, 5, 6-nodes of undirected trees.

For example, there are two possible configurations of undirected tree with 4 nodes:

(a)

```
x-x-x-x

```

(b)

```
x-x-x
  |
  x

```

In (a), you can split a tree into 2 sub-trees with 2 nodes each.

In (b), you can not do it since it will be two sub-trees of odd number of nodes (with 1 node and with 3 nodes respectively).

So my doubts based on suggestions:

1. What if it depends where you start cutting sub-trees?
2. What if greedy cutting sub-trees with even number of children from bottom to up doesn't give correct maximum number of removed edges? (continue of first question)

This puzzle is described on HackerRank as "Even Tree". Their editorial and discussion just declared algorithm but they don't say why it works. Also, I found discussion on stackoverflow but they also don't give explanation why such approach works.

# Answer
I got my "Aha! Gotcha" moment when I changed my point of view from nodes (as root of a subtree) to edges. Let me explain.

The set of edges that can be cut is a "static property", the set of choices is not changed by the earlier cuts that have been made. Any edge is considered to be "even" if on both sides it has an even number of nodes in the tree. Clearly we can only cut even edges. But also, cutting an even edge does not change the even property of the remaining edges, as we merely remove an even number of nodes in subtrees.

So, we are set to find the even edges, and we will cut them all. The proposed solution uses DFS, but any decent traversal will do I would think. The property that a subtree has an even number of nodes now means (in my terminology above) that the edge outside leading to the root of the subtree is in fact even.
> 0 votes

---
Tags: algorithms, trees, graph-traversal
---


# Question
Title: Are finitely many statements resp. variables sufficient to compute every function?
I prepare for local complexity contest and review some old Interview questions banks. I get stuck in one problem and no idea how we can solve it. please share your idea or help with this question:

> Suppose $C$ is a set of all one-variable computable functions, $C^{(n)}$ is a set of all one-variable computable functions using program with at most $n$ instruction, $C\_{(n)}$ is a set of all one-variable computable functions using program with just allowed to use variables $X, Y, Z\_1, ..., Z\_n$.

Which one is Correct:

> a) $ \exists n C^{(n)} = C , \exists n C\_{(n)} = C$
>
> b) $ \exists n C^{(n)} = C , \forall n C\_{(n)} \subsetneq C$
>
> c) $ \forall n C^{(n)} \subsetneq C , \forall n C\_{(n)} \subsetneq C$
>
> d) $ \forall n C^{(n)} \subsetneq C , \exists n C\_{(n)} = C$

Answer sheet (2). Any Expert can describe and help idea for solving this difficult contest question?

Edit 1: i see in refrences book, $Y$ is output variable, $X$ is input and $Z\_1, ...., Z\_n$ is local variable by program P. can see in p. 25 ref

# Answer
> 2 votes
Your example sheet is wrong (assuming (2) means (b)). The answer is ambiguous, because it depends on the notion of "program", or rather "instruction".

The main trick one has to use here is the existence of a universal program. A universal program takes two inputs, $X\_1$ and $X\_2$, and simulates the one-input program encoded by $X\_2$ on the input $X\_1$. In order to implement *any* one-input program, all we have to do is to supplement the universal program with code that sets the value of $X\_2$ to one encoding our desired program.

Using this trick, we see that if the universal program uses $n$ variables, then in fact *every* computable function can be implemented using $n$ variables. This means that (b) and (c) are wrong. In order to see whether (a) or (d) are correct, we need to consider three cases.

**Case 1: The instruction set are finite; there are finitely many instructions.** In that case, there are only finitely many programs of length $n$. Since there are infinitely many computable functions, there is no $n$ such that all computable functions can be implemented using $n$ instructions. So (d) is correct.

**Case 2: There is an instruction $X\_2 \gets m$ for arbitrary $m$ (or more generally, we can implement this operation using a bounded number of instructions).** In this case, given universal program with $n$ instructions, we can simulate any program using only $n+1$ instructions, by prepending the instruction $X\_2 \gets m$ for the correct value of $m$. So (a) is correct.

**Case 3: There are infinitely many instructions, but $X\_2 \gets m$ cannot be implemented using a bounded number of instructions.** In this case, *assuming variable assignment can be implemented using a finite number of instructions*, in particular we cannot implement the constant function $m$ using finitely many instructions. So (d) is again correct.

Note that Case 1 is actually a subcase of Case 3.

---
Tags: computability, computation-models
---


# Question
Title: Why is $\{a^n b^m c^p: n\neq m\} \cup \{a^n b^m c^p: m\neq p\}$ an inherently ambiguous language?
I came across a very hard interview question in last month’s Ph.D. entrance exam. It was asking which one of the languages is inherently ambiguous. Short answer says 2). Why is the language in 2) an inherently ambiguous language?

1) $L = \\{a^n b^{2n} c: n\geq 0\\} \cup \\{a^{2n} b^n d: n\geq 0\\}$

2) $L = \\{a^n b^m c^p: n\neq m\\} \cup \\{a^n b^m c^p: m\neq p\\}$

3) $L = \\{a^n b a^{2n}: n \geq 0\\} \cup \\{a^{2n} b a^n: n\geq 0\\}$

4) $L = \\{\omega: \omega \in \\{a,b\\}^\*: \omega \text{ does not have substring $baba$}\\} \cup \\{\omega : \omega \in \\{a,b\\}^\*: \omega \text{ does not have substring $abab$} \\}$

# Answer
If $L\_1,L\_2$ are two disjoint context-free languages which are not inherently ambiguous, then $L\_1 \cup L\_2$ is also a context-free language which is not inherently ambiguous. The reason is simple: starting with context-free grammars for $L\_1,L\_2$ with start symbols $S\_1,S\_2$ (respectively) and otherwise disjoint non-terminals, you can construct an unambiguous grammar for $L\_1 \cup L\_2$ by adding a new start symbol $S$ and the productions $S\to S\_1|S\_2$. This takes care of 1) and 3), once you construct unambiguous grammars for the constituent languages.

As Palec mentions, 4) is regular, and so admits a regular grammar which corresponds to a DFA accepting it. This grammar has as non-terminals the states of the DFA, and productions $A \to aB$ if the DFA moves from $A$ to $B$ upon reading $a$. For each final state $F$ we add a production $F\to\epsilon$, and the start symbol is the start state. This description should make it clear that the grammar is unambiguous.

Intuitively, 2) could be inherently ambiguous since words of the form $a^n b^m c^p$ with $n \neq m \neq p$ could have two different parse trees, corresponding to the two constituent languages. Proving this formally could be tedious. The only method I know consists of coming up with two words $x,y$ that can be pumped to the same word $w$ in such a way that makes it clear that the corresponding parse trees are different. If you want to pursue this further, a good first step will be to read some examples of this method.
> 6 votes

---
Tags: formal-languages, regular-languages, context-free, pushdown-automata, ambiguity
---


# Question
Title: Matrix Multiplication Algorithms for Non-Square Matrices
I'm interested in learning about some of the algorithms available for multiplying non-square matrices, yet despite exhaustive Googling efforts I have been unable to find any discussions of such algorithms except for a couple of extremely general pieces of pseudocode that I found on Wikipedia and MIT OCW.

If anyone could pass on some links to papers that discuss these algorithms in greater detail, I would greatly appreciate it! Thanks!

# Answer
There is an algorithm due to Coppersmith (later improved by him) that can multiply an $N \times N^\alpha$ matrix by an $N^\alpha \times N$ matrix in time $\tilde{O}(N^2)$ for some $\alpha \> 0$. The state of the art in this regard is a paper by Le Gall achieving a better $\alpha$, though his algorithm is much more complicated than Coppersmith's. Both algorithms are probably impractical. Ryan Williams (Appendix C) explains how to implement Coppersmith's algorithm, which a priori is non-uniform, in the context of a circuit lower bound; later it was shown that Coppersmith's algorithm can be replaced by other ingredients.
> 3 votes

---
Tags: algorithms, algorithm-analysis, mathematical-programming
---


# Question
Title: Complexity of recognizing whether two $\omega$-regular expressions represent the same language
If the complexity of recognizing whether two regular expressions represent different languages is **EXPSPACE-complete**, then what can be said for the complexity of recognizing whether two $\omega$-regular expressions represent different languages?

# Answer
It's quite easy to reduce the equivalence problem for regular expressions to the equivalence problem for $\omega$-regular expressions, so you have EXPSPACE hardness.

For EXPSPACE completeness, observe that given two $\omega$ regular expressions $r\_1$ and $r\_2$, you can translate them to equivalent NBWs $A\_1,A\_2$, where the size of $A\_i$ is at most single-exponential in the size of $r\_1$. Then, checking whether $L(A\_1)=L(A\_2)$ can be done in PSPACE (nontrivial, but well known).
> 4 votes

---
Tags: complexity-theory, space-complexity, buchi-automata
---


title: Why is Oracle Turing Machine important?

text:
# Question
Title: Why is Oracle Turing Machine important?
As you know, an *Oracle Turing Machine* (OTM) is a "black box" which somehow can tell us whether a given Turing machine with a given input eventually halts. By Church's Thesis it is impossible to design an algorithm which is able to solve such a problem.

If we will never get such a *black box* then why is it important and, in computer science, do they talk about it?

# Answer
Why are oracles used in the context you mentioned (where we have an oracle for the halting problem)? Because that allows us to answer questions that are fascinating, questions like "Are there problems that are *even harder* than the halting problem?". I'm not saying these questions are necessarily useful or important in practice -- but they are fascinating, fun, and lead to a deep theory. Just as not all art has to be directly useful, not all theory has to be directly useful.

Why are oracle Turing machines important, more broadly? They are used widely in computer science theory, to help us study the relative difficulty between different problems. They help us encode the notion of Turing reductions. They help identify some barriers to proving results in complexity theory, like proving that $P \ne NP$ (see e.g. relativizing proofs). They are useful in other places as well.

See also Are there any existing problems that wouldn't be solvable with a halting oracle?, Are all undecidable/uncomputable problems reducible to the Halting problem?, and Reductions among Undecidable Problems.
> 12 votes

# Answer
Some optimization algorithms are formulated as algorithms for an oracle Turing machine. This is common, among else, in submodular optimization. An algorithm for minimizing or maximizing a submodular function given some constraints typically has oracle access to the submodular function (and sometimes to the list of constraints). This has the advantage of making it possible to prove tight lower bounds. For example, consider the problem of maximizing a non-negative submodular function. There is a polynomial time algorithms achieving a $1/2$ approximation, but any algorithm doing better (in the worst case) has to access its oracle exponentially many times.
> 4 votes

---
Tags: complexity-theory, computability, oracle-machines, church-turing-thesis
---


# Question
Title: Does Church-Turing thesis also apply to artificial intelligence?
By Church-Turing's thesis, it is impossible to design an algorithm to decide the halting problem.

Does the word algorithm in this context include artificial intelligence or not, that is, does Church-Turing thesis also apply to artificial intelligence?

Is it possible to design an intelligence system in the future to decide this problem, or, by Church-Turing thesis, no AI will also be able to decide the halting problem?

# Answer
The Church-Turing thesis says that the informal notion of an algorithm as a sequence of instructions coincides with Turing machines. Equivalently, it says that any reasonable model of computation has the same power as Turing machines.

An artificial intelligence is a computer program, i.e., an algorithm. If the Church-Turing thesis holds, then you could implement that algorithm on a Turing machine. Since Turing machines cannot decide their own halting problem, it follows that, under the Church-Turing thesis, artificial intelligences cannot decide the halting problem for Turing machines.
> 18 votes

---
Tags: computability, artificial-intelligence, halting-problem, church-turing-thesis
---


# Question
Title: Abstract algebra and programming languages
Quite often, I stumble upon abstract algebra concepts like initial algebra, free algebra, and similar while reading papers on programming languages. For instance, in papers on algebraic data types, monads, separation logic, models of polymorphic lambda calculus, etc.

Where can I find materials that will introduce me to such concepts, i.e., ones that are related to programming languages and logics? Hopefully, the number of such materials would be small.

# Answer
Initial algebras and free algebras are basic concepts of category theory. Thus you may try the first chapters of \[1\] (in particular Section 2.2 Functional programming languages as categories) or the books \[2\] or \[3\].

\[1\] Category Theory for Computing Science by Michael Barr and Charles Wells

\[2\] Basic Category Theory for Computer Scientists by Benjamin C. Pierce.

\[3\] A taste of category theory for computer scientists by Benjamin C. Pierce.
> 7 votes

---
Tags: reference-request, programming-languages, logic, computer-algebra
---


# Question
Title: Why can no task have a utilization rate greater than one?
> Let $C\_i$ be the execution time for task i, $T\_i$ be the task period and utilization rate $U = \frac{C\_i}{T\_i}$
>
> Then $U$ must be less or equal to $1$ for the task to be schedulable
>
> Proof:
>
> Let $\hat T$ be the lcm of task $T\_1,...T\_n$ i.e. $\hat T = \prod\_i \> T\_i$. Define $\hat L\_i = \hat T/T\_i$ the number of times the task is run. Then the total number of execution is $\sum\_i C\_i/\hat L\_i = \sum\_i \frac{C\_i \hat T} {T\_i}$. Suppose utilization rate $U \>1$, then $\sum\_i \frac{C\_i \hat T} {T\_i} \> \hat T$ which is impossible. End of proof.

I am confused about several things in the proof.

First, what is the physical quantity representing the product or lcm of all the task periods $T\_i$? It would make more sense if it was the sum of all the $T\_i$ which represents the total task period.

Second, $\sum\_i C\_i/\hat L\_i$ represents the total time spent on execution, I do not get how if this time is larger than $\hat T$, then the tasks would not be schedulable. This goes back to my misunderstanding of what $\hat T$ is.

Can anyone help?

# Answer
> 2 votes
It appears that you have a periodic scheduling system on a single processor where task $i$ must run for $C\_i$ seconds out of every $T\_i$.

If this is the case, then the requirement that $\tfrac{C\_i}{T\_i}\le1$ is just saying that $C\_i\le T\_i$, i.e., you're not saying something like "Task 3 must run for 15 seconds out of every 10 seconds", which is physically impossible.

It looks like there's actually a mistake in the statement of the theorem. I think it should say that the utilization of task $i$ is given by $U\_i=\tfrac{C\_i}{T\_i}$, then define the total utilization to be $U = \sum\_{i=1}^n U\_i$ and then require the stronger condition that *this* $U$ satisfies $U\leq 1$. That is, you don't just require each task individually to use at most 100% of your resources: you require the whole ensemble to use at most 100%. You can think of it this way: if I'm supposed to spend $p\_1\\%$ of my time on task 1, ..., and $p\_n\\%$ of my time on task $n$, I'd better not be committing more than 100% of my time!

The physical significant of defining $\hat{T} = \mathrm{lcm}(T\_1, \dots, T\_n)$ is that it's the shortest period of time in which every task is supposed to run an integer number of times. It's not essential that you consider the shortest such period: the proof would work fine if you used any period in which every task needs to run an integer number of times. Perhaps it would be conceptually easier to set $\hat{T} = \prod\_{i=1}^n T\_i$ instead.

---
Tags: optimization, scheduling
---


# Question
Title: What is a lay explanation for universal search?
I am reading a book on a computer science topic but lack some of the prerequisite background. Normally when I run into terms I don't understand I simply look them up, but for *Universal Search* I simply haven't been able to find an explanation suitable for a reader without a background in statistics/computer science.

I've been reading this article on Universal Search from Scholarpedia, which seems to cover the topic. I'd appreciate an explanation for what *Universal Search* (or *Levin Search*) means.

# Answer
> 15 votes
Think of it like this. You have a problem, with input $x$ and you know how to verify a solution if you ever found one (like the inverse of a matrix or whatever you'd like to imagine).

Now, take your favourite programming language (say Python), and create *every single Python program* consisting of at most 10 characters! Then you run all those programs with your input for 10 seconds each, each on input $x$. If none of them give you the answer, you go all the way to 11. Run each program of at most 11 characters (including the ones you already tried, of course) for 11 seconds each, on input $x$. If none of them give you the correct answer, you continue to 12 and so on.

More formally, in iteration $i$, you run all programs of length *at most $i$* (finitely many, but of course exponential in $i$), each for $i$ seconds (or steps).

There is a program, say $P$ that gives the correct output in $s$ seconds. When you have come to iteration $i = \max\\{|P|, s\\}$, this program will be run for at least $s$ seconds, and you will output both $P$ and the solution.

# Answer
> 3 votes
Just to add to what Pål GD said, remember that you're running *all* the programs of length $i$ or less, and letting them run for at most $i$ seconds. So it might be that there's a program that gets the right answer that is 100 characters long, but it takes 120 seconds to run. Call that program $P$. On $i=100$ you'll check this program, but it takes too long to run so you discard it. After checking all the programs of length 100, you find none of them give the right answer, so you try programs of length $101$ *and all the programs you tried before*. So you retry $P$, the program that (we know) will give you the right answer, but it still takes too long so you discard it. We keep that process up, until we get to $i=120$. Then we try all the programs of length $\leq 120$, and when we get to $P$ we let it run for long enough for it to give the right answer. Then we stop -- we've found the algorithm we wanted. The iteration we're on is $i = 120$, because although the length of the program $P$ is less (we would write $|P|=100$), we had to wait until the amount of time it took was 120 seconds ($s=120$). So $i=\mathrm{max}\\{|P|,s\\}$ simply means the maximum of the length of the program $P$ and the amount of time it took to run $s$.

Another way to look at it is for a program $P$ that takes $s$ seconds to produce the right answer, we have to check *at least* $|P|$ iterations, and *at least* $s$ iterations before we'll find it, because if $i \< |P|$ then we haven't checked that program yet, and if $i \< s$ then we haven't let the program run for long enough.

Note that this method of searching is only guaranteed to get you an answer if there is one; it is not guaranteed to find the shortest or quickest answer. The reason for that should be apparent if you consider that the process terminates as soon as it finds a program that gives the right answer.

---
Tags: algorithms, terminology, search-algorithms
---


# Question
Title: Splitting permutations into transpositions
Suppose we are given an array $\texttt{a\[\]}$ of $n$ non-negative integers. The algorithm should give back $\texttt{-1}$ if an integer appears more than once in $\texttt{a\[\]}$.

Otherwise we interpret $\texttt{a\[\]}$ as a permutation $\pi:\\{0,\ldots, \texttt{max(a\[\])}\\} \to \\{0,\ldots, \texttt{max(a\[\])}\\}$ sending $\texttt{i}$ to $\texttt{a\[i\]}$ for $\texttt{i} \in \\{0,\ldots,n-1\\}$, and $\pi(k) = k$ for $k\geq \texttt{length(a\[\])}$.

What could be an algorithm to write $\pi$ as represented by $\texttt{a\[\]}$ as a sequence of transpositions, and what is the complexity?

# Answer
> 4 votes
One way to do it consists of two steps:

1. Find the cycle representation of the input.
2. Convert the cycle representation into a product of transpositions.

The first step is very similar to DFS. The second step is an exercise in permutation group theory.

---
Tags: algorithms, algorithm-analysis
---


# Question
Title: Why the pointer in linked list is of structure type?
Since any node points to a memory location is there any specific need in using it's pointer as *structure* type.Why couldn't we use integer as the pointer type in linked list rather than structure?

# Answer
The nodes in a linked list need to hold two things:

* the node's value
* a (possibly null) pointer to the next node

That makes them structs, so a pointer to a node is a pointer to a struct.
> 2 votes

# Answer
You can use an untyped pointer if you wish, but the advantage of having a pointer to a structure is type safety – it helps you protect yourself from misusing the pointer. When implemented in machine code, the pointer is indeed untyped.

It's not a terribly good idea to implement a pointer as an integer, however, since the sizes of both are implementation dependent and could differ. On your system a particular type of integer has the same size as a pointer, but on another system that same type of integer has a different, perhaps smaller, size. Sometimes you even have to worry about several types of pointers.
> 1 votes

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


title: Prove correctness of DFA ending with ab

text:
# Question
Title: Prove correctness of DFA ending with ab
I have the following deterministic finite automaton and I am need to prove correctness of the claim that this automata accepts $\\{wab \mid w\in \\{a,b\\}^\*\\}$

I know that I need to prove by induction on the length of the word but I am not sure how to do the induction step.

My try:

**Anchor**: After processing the only string of length zero, ε, the automaton is in state $q\_0$ as claimed.

**Hypothesis**: After reading a string u the automaton is in state $q\_1$ iff $u=xa$, and in state $q\_2$ iff $u=xab$ and in $q\_0$ iff $u=ε$ or $u=xb$. The claim holds for input fragments of length up to n.

**Step**: Any string $v$ of length $n+1$ is either $v=ua$ or $v=ub$

We split to cases:

1. $v=ua$ : According to the hypothesis- if $u$ ends with $b$ then it must be either in $q\_0$ or $q\_2$ - there for if we call $a$ after that we get to $q\_1$ so $ua$ is *not accepted*. Also, if $u$ ends with $a$ then it must be in $q\_1$ - there for if we call $a$ after that we get to $q\_1$ so $ua$ is *not accepted*.
2. $v=ub$ : According to the hypothesis- if $u$ ends with $b$ then it must be either in $q\_0$ or $q\_2$ - there for if we call $b$ after that we get to $q\_0$ so $ub$ is *not accepted*. Also, if $u$ ends with $a$ then it must be in $q\_1$ - there for if we call $b$ after that we get to $q\_2$ so $ua$ is *accepted*.

# Answer
> 4 votes
There is no induction needed. There is only one transition reaching the final state $q\_2$, namely $q\_1 \xrightarrow{b} q\_2$. Furthermore, every transition reaching $q\_1$ is labelled by $a$. It follows that every word accepted by the automaton has to end by $ab$. It remains to prove that, conversely, any word of the form $uab$ is accepted. After reading $u$ from the initial state $q\_0$, you reach one of the three states $q\_0$, $q\_1$ or $q\_2$. It suffices now to observe that $q\_0 \xrightarrow{ab} q\_2$, $q\_1 \xrightarrow{ab} q\_2$ and $q\_2 \xrightarrow{ab} q\_2$. Thus $q\_0 \xrightarrow{uab} q\_2$ in all cases, which means that $uab$ is accepted.

# Answer
> 0 votes
The induction hypothesis can look like: "after reading a string $u$ the automaton is in state $q\_1$ iff $P\_1(u)$, and in state $q\_2$ iff $P\_2(u)$." I leave it to you to determine what are the properties $P\_1$ and $P\_2$.

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


# Question
Title: Finding the values for a particular bucket in a list
I have a list of `n` items. I need to find the items that will be present in a given range, if the list were to be sorted. Sorting the entire list is not required and not desired, the buckets can be evenly spaced, but if an approach can handle a particular bucket starting at index `i` and ending at index `j` it would be preferred.

The ultimate goal is to have a sorted subset starting from index `i` and ending at index `j`. Though for the above problem sorting isn't required.

Example:

```
i := 2
j := 4
a := [9,0,1,8,2,7,3,6,4,5]
b := selectBucket(a, i, j)

[2,3] // b
[3,2] // also could work

```

I found an answer about dividing a list into k buckets, this approach is alright, but if there is a better way to get only a single bucket it would be preferred (that is of course faster).

# Answer
You should use the Quick Select algorithm. I will spare you the details and let you look up the algorithm on your own if you do not know it, but quick select roughly does the following:

Given a list A of size n and and index i, the algorithm will return the ith smallest element of A. Additionally, A will be such that this ith element is in index i, all element earlier in the array are less than or equal to this element, and all later element are greater than or equal to this element. And it does this in O(n) time!

So, just use this algorithm twice on the two indices (you will need to restrict which part of the array you are using for the second query and change the index appropriately, but you can work this out), and you will get what you want! Hope that helps.

Here is a link to the Quickselect Wikipedia article (I have not read it to verify its accuracy): http://en.wikipedia.org/wiki/Quickselect
> 4 votes

---
Tags: algorithms
---


# Question
Title: Finding the best combinations between items of 2 arrays in a sequential manner
I'm reposting this because people found the last description to be too hard to follow.

1. The data unit I'm working with is a pair of 2 numbers. The numbers can be any integer that is bigger than 0. Example:
`[X, Y]`
2. The input is 2 arrays of these pairs, each array can have any length. Example:
`A = {[1, 2], [3, 2], [5, 1]}`
`B = {[2, 3], [4, 5], [5, 3]}`
3. If I combine 2 pairs, one from each array, I get a new pair like this:
`[X1, Y1] + [X2, Y2] = [X1 + X2, Y1 + Y2]`
4. The output is a result of all combinations between the elements of the 2 input's where each element is the "best" and is ordered as ascending by Y

What "best" means in this case is that given `[X, Y]`,

1. this pair would have the highest or equal to highest X compared to all the other pairs that might have the same Y Example: `[2, 2], [2, 2],``[1, 2]`
2. it cannot have an X equal or lower than the maximum of any other pair that has a lower Y Example: `[2, 1], [4, 2],``[2, 4]`

To illustrate how the output can be reached

1. Lets take this example input:
`A = {[1, 2], [3, 2], [5, 1]}`
`B = {[2, 3], [4, 5], [5, 3]}`
2. First we combine every item in A with every item in B
`A[1] + B[1] = [3, 5], A[1] + B[2] = [5, 7], A[1] + B[3] = [6, 5]`
`A[2] + B[1] = [5, 5], A[2] + B[2] = [7, 7], A[2] + B[3] = [8, 5]`
`A[3] + B[1] = [7, 4], A[3] + B[2] = [9, 6], A[3] + B[3] = [10, 4]`
3. Next we order the combinations by Y
`[7, 4], [10, 4], [3, 5], [6, 5], [5, 5], [8, 5], [9, 6], [5, 7], [7, 7]`
4. Filter the combinations by the rules described above
`[10, 4]`

So in this example, the output is an array with the length of 1 because all other pairs with Y of 4 have lower X and all other pairs with Y \> 4 have equal or lower X.

I didn't include it in the example because its not necessary but the process can be optimized by prefiltering A and B by the same rules.

Now to my problem: I'm not dealing with arrays with the length of 3 but rather several hundred and the input count isn't 2 but 5+, as you can imagine, this process can be nested like this:
`result5 = process(process(process(process(A, B), C), D, E)`

So in practice, the potential memory use is `A.size * B.size * C.size * D.size * E.size`.. which is a lot more than fits in the 20something kB i have available.

What I'm looking for is an algorithm that will fetch me the same results, in the same order, one by one. The fetches will be sequential and will start from 0 so I think any algorithm that can produce all the results in the right order without sorting in the end can be modified for this. Does anybody know how this could be achieved?

# Answer
> 1 votes
Negate the `Y` values. Then you are looking for the Pareto-optimal frontier of the set of combinations.

There are standard algorithms for computing the Pareto-optimal frontier of any set. In particular, see the last part of this answer for an overview of algorithms (the simple cull algorithm, divide-and-conquer, and hybrids between those two). Those algorithms should be much more efficient than what you were considering before. For example, the simple cull algorithm has $O(n^2)$ running time to compute the Pareto-optimal frontier of a set of size $n$ (or $O(nm)$ time, if you know the output is of length $m$).

Here's how you can use this in your setting. First, compute the Pareto-optimal frontier of A and the Pareto-optimal frontier of B. Then, enumerate all combinations of those two frontiers. Finally, compute the Pareto-optimal frontier of that list of combinations. If you use the simple cull algorithm, the running time will be at worst $O(n^4)$, where $n$ is the length of the input lists. If the output has size $m$, the running time will be at worst $O(n^2 m)$. In either case, the memory consumption will be $O(n^2)$. The algorithms might perform better than that in practice, depending on your data.

If you want the output to be in sorted order, you can sort by `Y` value after computing the set.

I would recommend that you try these algorithms and see what the memory consumption looks like. If the memory consumption is still too much, then you can let us know.

---
Tags: algorithms
---


title: Shortest path in a matrix

text:
# Question
Title: Shortest path in a matrix
I am trying to solve this problem, and i have tried multiple methods, but i must be missing something, here is the problem: Given a matrix MxN. Find the shortest path from (1,1) to (M,N), where each number in the matrix represents the costs and one can only move horizontal and vertical:

e.g.

M =

```
1, 50,50,50,50;
1, 50,1, 1, 1 ;
1, 1, 1, 50,1 ;
50,50,50,50,1 ;
50,50,50,50,1 ;

```

where the shortest path is: (1,1) , (2,1) , (3,1) , (3,2) , (3,3) , (2,3) , (2,4) , (2,5) , (3,5) , (4,5) , (5,5)

Initially i tried to solve this recursion using Dynamic Programming:

```
SP(i,j) = {
    M[i][j], if i=M and j=N
    min(SP(i+1,j), SP(i-1,j), SP(i,j+1), SP(i,j-1)) + M[i][j], otherwise
}

```

It however loops infinitely since it calls in every direction e.g. going right is dependent on going left and so on..

Can anyone help me solve this problem?

# Answer
Treat the matrix as a weighted graph and use your favourite least-weight path algorithm.

To transform the matrix into a graph, say that the cost of going along the edge from $a$ to $b$ is the cost of visiting $b$. You'll need to separately add the cost of visiting the first node to the cost of any path the algorithm comes up with.
> 2 votes

---
Tags: shortest-path, dynamic-programming, matrices
---