# Question
Title: What is the time-complexity of histogram computation?
Suppose I have an Image $I$ of $n\times m$ (or a matrix), I would like to compute its histograms in a loop.

Pseudocode:

```
for i=1:s1:n
      h = hist(I(i:i+s1,m),bins)
end

```

$I$ is a matrix (or an image of data). When we say, $I(i:i+s1,m)$ we take the block of the matrix that starts in row from $i$ to $i+s1$ and have $m$ elements in columns.

**hist** is a function that counts the number of elements in its first parameters and store that number in its $bins$. For example : $hist(\[1,2 ,1 ,1 ,3\],3)$ is equals to $\[3, 1, 1\]$ because there is three elements of $1$ and just one elements of $2$ and $3$. $hist$ computes the frequency of an element.

So if I understand well ... the time-complexity of this simple algorithm is $O(n/s1) * TC(hist)$.

With the $TC(hist)$ the time-complexity of histogram computation. Since $s1$ is constant. I can deduce that TC of the algorithm is $O(n)\*TC(hist)$.

If we use a hash table of size $bins$, (it is a memory, so it won't impact the time complexity). We will have to browse the $s1\times m$ part of the image. So the $TC(hist)$ is equal $O(s1\*m)$.

I don't know how to link $O(s1\*m)$ to the $n$ and $m$. Is $TC(hist)$ **linear** following $m$ so equals $O(m) $ since $s1$ is a constant ?

please, check if my reasoning is correct ? and what is the global time-complexity ? do we take in consideration the memory usage in the computation of time-complexity ?

# Answer
> 2 votes
Presumably the time complexity of the function `hist` applied to data of length $N$ and to $B$ bins is $O(N+B)$ (the exact definition of $B$ depends on the implementation of `hist`; in your case, it seems to be the maximum of the input). In your case, each of the $n/s\_1$ iterations of the loop is applied to data of length $s\_1 m$, and so the total running time is $$ \frac{n}{s\_1} O(s\_1m + B) = O(nm + \frac{n}{s\_1} B). $$ The answer that your teacher expects is $O(nm)$.

# Answer
> -1 votes
\[From Mahaj Riad\]

I hope you're familiar with C/Java syntax.

So, if I understand your algorithm, it should be composed of 3 nested loops; the first inner loop depends on the former, and the deepest loop is independent.

```
for ( i = 1; i <= n - s1; i +=s1 ) {
    for ( j = 1; j <= i + s1; j ++ ) {
        for ( k = 1; k <= m; k ++ ) {
            bins[I[j,k]] ++; // frequency counting, symbolized by 'c'
        }
    }
}

```

Based on the above:

$$ \\ T(n, m) = \frac{1}{s\_1} \sum\_{i = 1}^{ n - s\_1} \sum\_{j = 1}^{ i + s\_1} \sum\_{k = 1}^{ m}c \\ T(n,m) = \frac{c}{s\_1} \sum\_{i = 1}^{ n - s\_1} \sum\_{j = 1}^{ i + s\_1}m \\ T(n, m) = \frac{cm}{s\_1} \sum\_{i = 1}^{ n - s\_1}(i + s\_1) \\ T(n, m) = \frac{cm}{s\_1} \left(\sum\_{i = 1}^{ n - s\_1}i + \sum\_{i = 1}^{ n - s\_1}s\_1\right) \\ T(n, m) = \frac{cm}{s\_1} \left(\frac{(n - s\_1)(n - s\_1 + 1)}{2} + s\_1(n - s\_1)\right) \\ T(n, m) = \frac{cm}{s\_1} \left( \frac{n^2 + n - s\_1^2 - s\_1}{2} \right) \\ \text{The order of growth is } \Theta(mn^2). \\ \text{In other words, when } n = m \text{, we can affirm } \Theta(n^3) \rightarrow \text{ Cubic order of growth.} \\ \text{and when } n \< m \rightarrow T(n, m) \in \Omega(n^3) \\ \text{and when } n \> m \rightarrow T(n, m) \in \mathcal{O}(n^3) $$

---
Tags: algorithm-analysis, runtime-analysis
---


# Question
Title: How to prove that the probability that a random graph has a stable set of size $2\lceil \log n\rceil$ is sub-constant?
Given a random graph on $n$ vertices where each edge is included with probability $1/2$. Lets call it $G=(n,1/2)$. How can we show that the probability that this graph has a stable set of size at least $2\lceil \log n\rceil$ is sub-constant?

# Answer
> 2 votes
The probability that a specific set of size $k$ is a stable set is $2^{-\binom{k}{2}}$. Hence the probability that *some* set of size $k \leq n/2$ is stable is at most $$ \binom{n}{k} 2^{-\binom{k}{2}} \leq 2\left(\frac{en}{k}\right)^k 2^{-k^2/2}. $$ When $k = c\log n$ (logarithm to the base 2), this upper bound is $$ 2\left(\frac{en}{C\log n}\right)^{C\log n} 2^{-C^2\log^2 n/2}= \frac{2^{(C-C^2/2)\log^2n}}{\Omega(\log n)^{\Omega(\log n)}} = o(2^{(C-C^2/2)\log^2n}). $$ For $C \geq 2$, this is $o(1)$.

---
Tags: graphs
---


# Question
Title: Running time analysis of a linear algorithm seems to me quadratic
I have been analyzing an algorithm for several hours in order to find out why it is expressed as $O(n)$ (I saw this solution in a PowerPoint presentation which refers to it as a *linear algorithm*). I see a `while` loop inside a `for` loop.

The `for` loop executes $n$ times.

The `while` loop executes "at most" $n$ times $(0, 1, 2, ..., n - 1)$ which can be represented as $n\*(n+1)/2$

So, the running time formula can be $(n)\*\[n\*(n+1)/2\]$ which yields to a quadratic expression. (I have not taken into account individual statements inside the loops for simplicity).

What is wrong with my reasoning?

`Algorithm spans2(X, n)
 S = new array of n integers
 A = new empty stack
 for i = 0 to n - 1 do
 while (!A.isEmpty() && X[A.top()] <= X[i] ) do
 A.pop()
 if A.isEmpty() then
 S[i] = i + 1
 else
 S[i] = i - A.top()
 A.push(i)
 return S`

# Answer
> 3 votes
Inner while loop will be executed at most $L$ times, where $L$ is number of integers that will be added to stack $A$, and it will be at most $N$ pushes to stack, because `A.push(i)` is called in outer for loop, so body of inner while loop (`A.pop()`) will be executed at most $N$ times.

# Answer
> 2 votes
Your analysis is *too coarse*; cf. also the analysis of Dijkstra's algorithm. You find $O(n^2)$ (due to saying "at most" and ignoring constant factors) which is a valid upper bound, but it is a bad one.

If you look closer, you can show an $O(n)$ upper bound; together with a trivial $\Omega(n)$ lower bound (from the `for` loop alone) you get $\Theta(n)$ asymptotic runtime, i.e. linear. One way to do this is to count how often every statement is executed.

Here are the relevant observations:

* Ever iteration of the `for` loop pushes exactly one element to the stack.
* The `while` loop has at most one iteration for every element ever on the stack.

Combine these observations with what you already know, write up your statement counts and obtain the result.

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


# Question
Title: Formal languages: constructing * for a linear set
Right now, I'm working on a computer verified proof in Agda, showing that the Parikh images of regular languages are semi-linear (i.e. a limited form of Parikh's Theorem).

Right now, I'm trying to construct the equivalent of \*-closure for a linear set. (Once I have this, it's easy to find for semi-linear sets).

More formally:

* A linear set is a set of the form $\\{ v\_0 + c\_1 \cdot v\_1 + c\_n \cdot v\_n \mid c\_i \in \mathbb{N}\\}$. i.e. a linear combination of vectors from $\mathbb{N}^k$.
* A semi-linear set is a finite union of linear sets

For a linear set $L$, I'm trying to construct $L^\*$, the semi-linear (possibly linear?) set $L^\* = \\{ u\_1 + \ldots + u\_m \mid u\_i \in L, m \geq 0 \\}$, i.e. the infinite sum of L with itself.

I know that this set must be semi-linear, from Parikh's theorem. It basically corresponds to the case where, if $R$ is a regular languages with a linear Parikh image $L$, then $L^\*$ is the Parikh image of $R^\*$. (From this I know how to build up the case where R has semi-linear Parikh image).

I'm wondering if someone can either point me to a proof that Regular Expressions are semi-linear languages that doesn't rely on Parikh's theorem for context-free languages, or can point me in the right direction for constructing $L^\*$ myself.

# Answer
> 5 votes
**Hint**. It suffices to observe that if $L = \\{ v\_0 + c\_1v\_1 + c\_nv\_n \mid c\_1, \dotsm, c\_n \in \mathbb{N}\\}$, then $L^\* = \\{ c\_0v\_0 + c\_1v\_1 + c\_n v\_n \mid c\_0, \dotsm, c\_n \in \mathbb{N}\\}$.

---
Tags: formal-languages, reference-request, regular-languages
---


# Question
Title: Getting the sorted sequence from a level-wise sorted min-heap
A *heap sorted by levels* is a heap which:

1. Every parent is smaller than its children.
2. The nodes in each level are sorted from the smallest to the greatest.

I need to describe an algorithm with $O(n)$ runtime that prints the values in the heap in sorted order.

I only manage to do it in $O(n \log(\log n))$ using another heap but have no idea of how to do it in $O(n)$.

# Answer
> 3 votes
Use a recursive algorithm. Suppose the heap has depth $D$. Recursively compute a sorted list of all the numbers in the top $D-1$ levels (i.e., all but the bottom level); let $L$ be this list. Let $L'$ be the list of numbers in the bottom level. Note that both $L$ and $L'$ are in sorted order, so we can use the Merge procedure from Mergesort to compute a sorted list of all of the numbers.

If you work out the recurrence relation, you'll see that the running time of this algorithm is $O(n)$. Indeed, Merge runs in $cn$ time, for some constant $c$, so the total running time will be $cn + cn/2 + cn/4 + \dots \le 2cn = O(n)$.

---
Tags: algorithms, data-structures, sorting, heaps
---


# Question
Title: Why are functional programs considered slower than procedural counterparts asymptotically, if the opposite appears true?
I've read and been told way too many times that functional algorithms and data structures have an obligatory `O(log(N))` slowdown in respect to their procedural (for-loop/array-based) counterparts. But, after thinking about it, I don't see how that could be true. Mind this `for loop`

```
int arbitrary_sum(int* arr, int size, int n){
    int sum = 0;
    for (int i=0; i<n; ++i)
         sum += arr[(int)(random()*size)];
    return sum;
}

```

That sums `N` random elements of an array. You'd saiy this is `O(N)`, but that is taking in account array indexing is `O(1)`, which can't be true. For simplicity, assume memory cells are stored linearly. Since that chip must occupy a linear amount of space, and since a signal requires a linear amount of time to travel given space, then it is obvious an indexing operation takes at least `O(S)` time to complete. That is the time a signal takes to go from the CPU to the memory cell and come back. This means that **the complexity of a for-loop is O(N\*S)**, where `N` is the number of interactions and **S is the size of the state that is visible on that `for-loop`.** This way, the textbook `int sum(int* array, int size)` function, for example, can't be `O(N)` \- it is, actually, `O(N^2)`, for any reasonable implementation of `for`, as far as physical laws apply. Using layers of caches we are able to shrink the initial `S` factor and amend this effects, but that has a runtime cost and doesn't change the asymptotics. Now, lets look at the functional counterpart. The most obvious way to sum a container of numbers functionally is folding over a list. For simplicity, lets examine the sum of `0` to `4` using church lists:

```
((λc.(λn.(c 0 (c 1 (c 2 (c 3 (c 4 n))))))) + 0)

```

We can optimally evaluate a λ program is using an interaction net, so, lets encode that program as one:

Now, let me propose a new model of computer. Instead of separating the CPU and the memory, we instead store a simplistic computing unit together with each memory cell, each one capable of sending/receiving signals and processing local reductions. On this system, we can reduce the `((λ ...list...) +)` abstraction by sending parallel signals from the topmost `λ` node to each corresponding application. We can also reduce the outermost abstraction by sending `0` to the last application of the list. All that takes no more than 2 runs through the list, and the result is:

From here on, it is clear that the rest of the computation will take a linear amount of time to complete. After all, each redex is local, and the redexes are reduced one by one, producing the result from the tail of the list up to its head.

Under this point of view, it seems to me that functional programs are actually asymptotically faster than imperative counterparts, so, why is the opposite considered the truth?

# Answer
Without fully answering your question, I would like to answer it at least partially by remarking that computation cost can be evaluated only with respect to an abstract model of computation.

If you want to use two different models, for two different programs, than you have to determine the complexity of reducing each model to the other, in order to have a meaningful comparison.

Another point is that physics does not well qualify as a computation model for several reasons:

* it is not clear enough what physics allows and does not allow regarding of computation, computation speed, storage, etc.
* computation models are defined with various assumptions about unit operations and their costs, and about infinity and asymptotics, which are not meant to be a reflection of reality, but only an approximation of reality intended to facilitate the analysis of some phenomena, whether abstract or physical.

This is why Turing machines are more appropriate than finite automata theory to analyse the behavior of devices with very large, though still finite memory. For example, the powerset construction of DFA may exist in theory when the memory is finite, however big, but may also quickly exceed the capacity of our limited universe, thus hardly making any sense.

Considering your first example about the "physical" time cost of executing a `for loop` on an array of size $n$. If we are to do asymptotic physics, we have to do it right, or at least as right as current knowledge in physics will allow. Due to universe expansion, the part of the universe that we can ever hope to access is bounded by a radius of some $z$ zillion light-years (corresponding to a distance at which the expansion speed relative to us equals the speed of light), so that nothing relevant to us can be further away.

You can see that as good news: distances being bounded, access is asymptotically in constant time, so that the classically accepted cost analysis does hold, despite your remarks.

Of course, since you still want to have arbitrarily large memory, you have to assume that this finite sphere can hold infinitely many bits of information ... which I fear physicists cannot really tell. But let's be optimistic.

Another way to do away with your remark is to consider that the access time is small enough that it will not really impact the computing time, unless you have specific reasons to think otherwise.

Some high speed computer do have to be programmed taking into account physical distances, in particular to memory. But why should functional program be exempted from such physical limitations. How much computational capacity do you store with each cell? Instead of the $+$ operator, can you pass any arbitrarily complex fuction as parameter and still have it reduced locally in each memory cell.

Or to put it differently, what prevents an imperative program from taking advantage of an architecture that has computing power in each memory cell. This is remindful of various specialized architectures, such as vector processors.
> 5 votes

---
Tags: algorithm-analysis, lambda-calculus, efficiency, functional-programming, loops
---


# Question
Title: Time complexity of a vertical sweep algorithm with histogram computations
In the paper

the authors claim that the running time of the algorithm (Matlab implementation) is $O(h)$. I don't understand how they arrive at this.

The algorithm works as follows: The algorithm does a vertical sweep of a whole image of size $h\times w$. For every $l$ between $0$ and $h$, a score function $s$ is computed. To compute $s$ we we calculate *histogram* computation of the four parts of the whole image : $\[0:l,1:w/2\]$, $\[l:h,1:w/2\]$, $\[0:l,w/2:end\]$ and $\[l:end,w/2:end\]$.

How do they arrive at $O(h)$ time complexity for the algorithm? Do they consider histogram computation to be $O(1)$?

**PS**: This question is related to What is the time-complexity of histogram computation? but I hope to get the exact answer in concrete case this time ...

# Answer
> 1 votes
$O(h)$ sounds hard to believe, unless there's some pre computation that's not counted here, as it takes $\Theta(hw)$ time just to read every pixel of the image.

Computing a histogram from scratch can't be done in $O(1)$ time. But *updating* a histogram *can* be done efficiently. If you already have a histogram for some set of pixels, and then you add or delete one pixel, you can update the histogram in $O(1)$ time. This kind of idea can be used to speed up the sort of thing you're talking about, because all of the histograms we want are closely related.

In particular, when we increment $l$, we add or delete a row from a histogram. Thus you can update the histogram more efficiently than computing it from scratch.

---
Tags: time-complexity, image-processing
---


# Question
Title: What is the reason of using Gaussian model for Background Modeling?
I am a new learner to Background Subtraction (Background Modeling) and I am reading a few previous works on how it is performed. Starting with Wikipedia (by searching "Background Subtraction"), I could understand the first few simple methods, until the part "Running Gaussian average". I simply have no idea why a Gaussian probabilistic density function was proposed to fit on the most recent n frames. Reading from the original paper by Wren et al., the reason for using the Gaussian PDF is "computational convenience", which baffled me since the Gaussian PDF does not look simple to me.

In addition, many later methods were based on the Gaussian Mixture Model by Stauffer and Grimson, which was even more complicated. But there seems no explanation about why a Gaussian PDF was used, and why the use was justified.

Can anyone throw some light to me on these questions? Thanks!

# Answer
> 1 votes
The Gaussian function is ubiquitous in statistics and many other fields. One reason is the Central Limit Theorem, which says that the means of independent identically distributed random variables themselves have a normal (Gaussian) distribution. This is why you see the bell curve in nature so often.

The Gaussian PDF may not look simple at a first glance, but it is actually very simple to differentiate and integrate. Remember that exp(x) is its own derivative and its own indefinite integral. It is also one of very few functions whose Fourier Transform can be computed analytically.

Finally, the reason Stauffer and Grimson and others used the Gaussian Mixture Model, is that it is an easy way of approximating a complicated multi-modal distribution.

---
Tags: image-processing, computer-vision, modelling
---


# Question
Title: position to insert element in inserionsort (equality of probablity)
prove that in algorithm insertionsort, for successively considered element a\[i\] there is equal probablity that element will be inserted in one of i positions:

a\[1\] \<= a\[2\] \<= ... \<= a\[i-1\]

To my eye it is obvious and I can't prove it. What is your opinion ?

# Answer
Try counting the number of permutations where it is inserted in position $i$. How does this number depend on $i$? That will lead immediately to a proof.

In general, when you need to calculate a probability of some event, and you have a uniform distribution, one way is to use counting to compute the probability: count the number of outcomes where the event is true, and then divide by the total number of possible outcomes.
> 3 votes

---
Tags: sorting
---


# Question
Title: Proving algorithm for removing nodes from a complete graph with two kinds of edges
Lets say $G$ is complete undirected graph with a set of edges coloured either black or red. The problem is to find an algorithm answering if it is possible to remove a subset of nodes from $G$ in a way such that all black edges are gone, but for any two nodes in the set of removed nodes there was no red edge between them.

I think I found a solution: If the graph has more than one black strongly connected components, then the answer is "no", because then there are two black edges $E\_1$ and $E\_2$ with no common nodes, and for every black edge at least one of its nodes should be removed to remove that edge from graph, and for any pair of nodes of $E\_1$ and $E\_2$ we choose to remove, there is a red edge between them, so we fail. Otherwise, we can sort all nodes by the number of linked black edges in descending order and then iterate this list node by node removing them from graph. If for current node there is a linked red edge, then mark the node on other end as "dangerous", and if we come across such node before all black edges are gone, then answer is "no". Otherwise, when there is no black edges, stop and answer "yes".

But now I want to prove this algorithm is correct. I think the case of more than one black SCCs is simple and doesn't require anything more rigorous, but the other case is more complicated and I'm not even entirely sure it's correct. Currently this is where I got:

Lets say the strategy of always removing a node with more linked black edges first is incorrect. Then it means, such strategy can make algorithm answer "no" when there was an other way to choose nodes which would make algorithm answer "yes". Then there is a step where some max-black-edges node $X$ is improperly chosen. Lets take a look at set of its black-adjacent nodes $S$. If all of them have the same number of linked black edges as $X$, then all other choices are symmetric and we will fail anyway, otherwise, there are nodes with less linked black edges than $X$ which means there are at least two nodes in $S$ which have a red edge between them. And to remove all black edges that make nodes in $S$ black-adjacent to $X$, we should remove all these nodes, so we will remove two with that red edge, so such strategies are incorrect and max-black-edges nodes should always be removed first.

I think this proof is somewhat naive and vague (especially in the end) and maybe even incorrect, so I'm seeking suggestions to make a better one. Not necessarily super-formal, but at least something which is sufficiently strict and believable.

# Answer
A complete graph with red and black edges is just an unnecessarily complicated way of describing an arbitrary graph (where black edges correspond to neighbors and red edges to non-neighbors).

Effectively, given a graph $G$ you are looking for a subset of the vertices that is both a clique and a vertex cover.

Restating the problem like this, it is easier to see that your arguments are correct: in a graph with no isolated vertices, if there is more than one connected component (in an undirected graph every connected component is also strongly connected so stating "strongly connected" is redundant) then clearly there is no clique that covers both components.

Let $\Delta$ be the maximum degree of the graph $G=(V,E)$ and let $v$ be a degree-$\Delta$ vertex. Suppose there is a valid solution $S\subseteq V$ that does not contain $v$, then this solution must contain all of $v$'s neighbors. Suppose $S$ can not be extended to a valid solution by adding $v$, then $S$ contains some vertex not adjacent to $v$, thus the graph restricted to $S$ is a clique of size least $\Delta+1$ in which all vertices have degree at least $\Delta$. However, then the graph restricted to $S\cup{v}$ has a vertex of degree at least $\Delta+1$, contradicting that $\Delta$ is the maximum degree. Thus if a valid solution exists then this solution remains valid when adding a maximum-degree vertex.

So the algorithm can be restated in much simpler terms: take all maximum-degree vertices, and check that they are a valid solution.
> 3 votes

---
Tags: algorithms, graphs
---


title: Inducing a context free grammar

text:
# Question
Title: Inducing a context free grammar
I have a file containing a subset of possible strings from a context free language. I am looking for a mechanism to induce the grammar from this information. Is that possible?

# Answer
If you have only positive examples (strings that are in the language), in principle, no, you cannot infer the grammar. For all you can tell, the language might be $\Sigma^\*$: no matter how many example strings you have, you'll never be able to rule that out as the language.

However, if you have a little more information, there are known solutions. You can take a look at Angluin's algorithm. If you need a software implementation, take a look at LearnLib. See also Wikipedia's page on grammar induction for other approaches.

Another approach is to try to find the smallest context-free grammar that can generate every string in your set of examples, and nothing else. Finding the absolute smallest CFG is probably hard, but there are known heuristics that tend to give a good solution in practice. I'd recommend the Sequitur algorithm, if you need something in practice and have only positive examples. This gives up generalization -- there might be an even simpler/smaller CFG that can generate every one of your example strings as well as some others -- but for some applications it works reasonably well in practice.
> 5 votes

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


# Question
Title: Has this model of random directed graphs been studied?
Youtube recently added a feature called autoplay, where each clip is assigned a (presumably related) clip that follows it. This, in effect, defines a directed graph on the set of youtube clips, where each vertex has outdegree 1. The user starts at a vertex of his choice and takes a walk along this graph.

This got me thinking. Since the graph is finite, the user will eventually get stuck in a loop. Each loop acts as a sink, and each vertex will eventually lead the user to some sink. This raises some questions - how many sinks are there? How many steps does it take before the user reaches the loop? What is the distribution of the sink sizes? And so on.

Here is a random graph model that can be used to model this process: For each vertex $v$ we choose a single neighbor $w$ uniformly at random and add the edge $(v,w)$ to the graph. It might be interesting to investigate the properties of this model and to see if they can teach us anything about the Youtube network. Have people looked at this type of thing before?

# Answer
this may be a bit unexpected but yes, this has been studied in at least one particular context: PRNGs. a PRNG can be visualized as a directed graph, specifically a functional graph (all vertices, single outdegree) of "current value, next value". however most PRNGs are designed to have a single very long cycle. there is some analysis of PRNGs with multiple embedded cycles. eg:

there is also some theory on cycle detection eg the Tortoise/ Hare and Brents algorithm. did not find other contexts where "random" functional graphs are studied. note your definition did not ensure that vertices are connected, not sure if that is what you intended. there would be some theory about how many edges would have to be placed before separate disconnected graphs become connected. Erdos did studies in this area with undirected graphs on Erdos-Renyi model and its famous as being one of the early discoveries of phase transitions in discrete math theory. the random functional graphs you describe could be regarded as a specialized version of Erdos Renyi model.
> 4 votes

# Answer
It is very easy to say something about the expected length before you get stuck in a loop: if there are $n$ videos, it will (starting from a random video) take in expectation $\Theta(\sqrt{n})$ videos before you loop around (the actual value is around $1.25\sqrt{n}$). This is effectively the birthday problem, since each time you draw a video at random.

Since each video in the chain of $\Theta(\sqrt{n})$ videos is equally likely to be the one you loop back to, the average length of a loop is also $\Theta(\sqrt{n})$ videos (actual value $0.625\sqrt{n}$).

This gives the expected length of the loop you end up in after starting from a random video. This means that a loop with many videos leading to it is counted more strongly. If instead you want to know the expected length of a loop if you pick a random loop, this may be found as $T(1)$, where

$$T(i)=\frac{n-i}{n}T(i+1)+\frac{i}{n}\frac{i+1}{2}$$

and $T(n)=\frac{n+1}{2}$. Computing the values of $T$ experimentally it seems to match up with $0.625\sqrt{n}$, so both ways of counting the expected loop length are the same.

Computing the expected number of cycles seems to be a harder problem. We start by counting the expected number of cycles of a given length. The probably that a node is part of a length-1 cycle is $\frac{1}{n}$, so there are in expectation $1$ length-1 cycles. The probability that a node is in a length-2 cycle is $\frac{n-1}{n}\frac{1}{n}$, so there are in expectation $\frac{1}{2}\frac{n-1}{n}$ length-2 cycles. In general, the number of cycles of length $l$ is $\frac{1}{l}\Pi\_{i=1}^{l-1} \frac{n-i}{n}$.

We can obtain a crude upper bound on the number of cycles by considering $\Sigma\_{i=1}^n \frac{1}{i} = H\_n$ which is $O(\log n)$. Unfortunately the number of cycles doesn't seem to converge to $\log n$ so this bound is not tight.
> 8 votes

---
Tags: random-graphs, network-analysis
---


# Question
Title: Finding a pair of non-overlapping bit vectors
I give you a list of $n$ bitvectors of width $k$. Your goal is to return two bitvectors from the list that have no 1s in common, or else to report that no such pair exists.

For example, if I give you $\[00110, 01100, 11000\]$ then the only solution is $\\{00110, 11000\\}$. Alternatively, the input $\[111, 011, 110, 101\]$ has no solution. And any list that contains the all-zero bitvector $000...0$ and another element $e$ has a trivial solution $\\{e, 000...0\\}$.

Here's a slightly harder example, with no solution (each row is a bit vector, the black squares are 1s and the white squares are 0s):

```
■ ■ ■ ■ □ □ □ □ □ □ □ □ □
■ □ □ □ ■ ■ ■ □ □ □ □ □ □
■ □ □ □ □ □ □ ■ ■ ■ □ □ □
■ □ □ □ □ □ □ □ □ □ ■ ■ ■
□ ■ □ □ □ ■ □ □ □ ■ ■ □ □
□ ■ □ □ ■ □ □ □ ■ □ □ □ ■
□ ■ □ □ □ □ ■ ■ □ □ □ ■ □ <-- All row pairs share a black square
□ □ ■ □ □ □ ■ □ ■ □ ■ □ □
□ □ ■ □ □ ■ □ ■ □ □ □ □ ■
□ □ ■ □ ■ □ □ □ □ ■ □ ■ □
□ □ □ ■ ■ □ □ ■ □ □ ■ □ □
□ □ □ ■ □ □ ■ □ □ ■ □ □ ■
□ □ □ ■ □ ■ □ □ ■ □ □ ■ □

```

How efficiently can two non-overlapping bitvectors be found, or be shown not to exist?

The naive algorithm, where you just compare every possible pair, is $O(n^2 k)$. Is it possible to do better?

# Answer
## Warmup: random bitvectors

As a warm-up, we can start with the case where each bitvector is chosen iid uniformly at random. Then it turns out that the problem can be solved in $O(n^{1.6} \min(k, \lg n))$ time (more precisely, the $1.6$ can be replaced with $\lg 3$).

We'll consider the following two-set variant of the problem:

Given sets $S,T \subseteq \\{0,1\\}^k$ of bitvectors, determine where there exists a non-overlapping pair $s \in S, t \in T$.

The basic technique to solve this is divide-and-conquer. Here is a $O(n^{1.6} k)$ time algorithm using divide-and-conquer:

1. Split $S$ and $T$ based upon the first bit position. In other words, form $S\_0 = \\{s \in S : s\_0=0\\}$, $S\_1 = \\{s \in S : s\_0 = 1\\}$, $T\_0 = \\{t \in T : t\_0 = 0\\}$, $T\_1 = \\{t \in T : t\_0 = 1\\}$.
2. Now recursively look for a non-overlapping pair from $S\_0,T\_0$, from $S\_0,T\_1$, and from $T\_1,S\_0$. If any recursive call finds a non-overlapping pair, output it, otherwise output "No overlapping pair exists".

Since all bitvectors are chosen at random, we can expect $|S\_b| \approx |S|/2$ and $|T\_b| \approx |T|/2$. Thus, we have three recursive calls, and we've reduced the size of the problem by a factor of two (both sets are reduced in size by a factor of two). After $\lg \min(|S|,|T|)$ splits, one of the two sets is down to size 1, and the problem can be solved in linear time. We get a recurrence relation along the lines of $T(n) = 3T(n/2) + O(nk)$, whose solution is $T(n) = O(n^{1.6} k)$. Accounting for running time more precisely in the two-set case, we see the running time is $O(\min(|S|,|T|)^{0.6} \max(|S|,|T|) k)$.

This can be further improved, by noting that if $k \ge 2.5\lg n+100$, then the probability that a non-overlapping pair exists is exponentially small. In particular, if $x,y$ are two random vectors, the probability that they're non-overlapping is $(3/4)^k$. If $|S|=|T|=n$, there are $n^2$ such pairs, so by a union bound, the probability a non-overlapping pair exists is at most $n^2 (3/4)^k$. When $k \ge 2.5 \lg n+100$, this is $\le 1/2^{100}$. So, as a pre-processing step, if $k \ge 2.5 \lg n + 100$, then we can immediately return "No non-overlapping pair exists" (the probability this is incorrect is negligibly small), otherwise we run the above algorithm.

Thus we achieve a running time of $O(n^{1.6} \min(k, \lg n))$ (or $O(\min(|S|,|T|)^{0.6} \max(|S|,|T|) \min(k, \lg n))$ for the two-set variant proposed above), for the special case where the bitvectors are chosen uniformly at random.

Of course, this is not a worst-case analysis. Random bitvectors are considerably easier than the worst case -- but let's treat it as a warmup, to get some ideas that perhaps we can apply to the general case.

## Lessons from the warmup

We can learn a few lessons from the warmup above. First, divide-and-conquer (splitting on a bit position) seems helpful. Second, you want to split on a bit position with as many $1$'s in that position as possible; the more $0$'s there are, the less reduction in subproblem size you get.

Third, this suggests that the problem gets harder as the density of $1$'s gets smaller -- if there are very few $1$'s among the bitvectors (they are mostly $0$'s), the problem looks quite hard, as each split reduces the size of the subproblems a little bit. So, define the density $\Delta$ to be the fraction of bits that are $1$ (i.e., out of all $nk$ bits), and the density of bit position $i$ to be the fraction of bitvectors that are $1$ at position $i$.

## Handling very low density

As a next step, we might wonder what happens if the density is extremely small. It turns out that if the density in every bit position is smaller than $1/\sqrt{k}$, we're guaranteed that a non-overlapping pair exists: there is a (non-constructive) existence argument showing that some non-overlapping pair must exist. This doesn't help us find it, but at least we know it exists.

Why is this the case? Let's say that a pair of bitvectors $x,y$ is *covered* by bit position $i$ if $x\_i=y\_i=1$. Note that every pair of overlapping bitvectors must be covered by some bit position. Now, if we fix a particular bit position $i$, the number of pairs that can be covered by that bit position is at most $(n \Delta(i))^2 \< n^2/k$. Summing across all $k$ of the bit positions, we find that the total number of pairs that are covered by some bit position is $\< n^2$. This means there must exist some pair that's not covered by any bit position, which implies that this pair is non-overlapping. So if the density is sufficiently low in every bit position, then a non-overlapping pair surely exists.

However, I'm at a loss to identify a fast algorithm to find such a non-overlapping pair, in these regime, even though one is guaranteed to exist. I don't immediately see any techniques that would yield a running time that has a sub-quadratic dependence on $n$. So, this is a nice special case to focus on, if you want to spend some time thinking about this problem.

## Towards a general-case algorithm

In the general case, a natural heuristic seems to be: pick the bit position $i$ with the most number of $1$'s (i.e., with the highest density), and split on it. In other words:

1. Find a bit position $i$ that maximizes $\Delta(i)$.
2. Split $S$ and $T$ based upon bit position $i$. In other words, form $S\_0 = \\{s \in S : s\_i=0\\}$, $S\_1 = \\{s \in S : s\_i = 1\\}$, $T\_0 = \\{t \in T : t\_i = 0\\}$, $T\_1 = \\{t \in T : t\_i = 1\\}$.
3. Now recursively look for a non-overlapping pair from $S\_0,T\_0$, from $S\_0,T\_1$, and from $T\_1,S\_0$. If any recursive call finds a non-overlapping pair, output it, otherwise output "No overlapping pair exists".

The challenge is to analyze its performance in the worst case.

Let's assume that as a pre-processing step we first compute the density of every bit position. Also, if $\Delta(i) \< 1/\sqrt{k}$ for every $i$, assume that the pre-processing step outputs "An overlapping pair exists" (I realize that this doesn't exhibit an example of an overlapping pair, but let's set that aside as a separate challenge). All this can be done in $O(nk)$ time. The density information can be maintained efficiently as we do recursive calls; it won't be the dominant contributor to running time.

What will the running time of this procedure be? I'm not sure, but here are a few observations that might help. Each level of recursion reduces the problem size by about $n/\sqrt{k}$ bitvectors (e.g., from $n$ bitvectors to $n-n/\sqrt{k}$ bitvectors). Therefore, the recursion can only go about $\sqrt{k}$ levels deep. However, I'm not immediately sure how to count the number of leaves in the recursion tree (there are a lot less than $3^{\sqrt{k}}$ leaves), so I'm not sure what running time this should lead to.
> 10 votes

# Answer
# Faster solution when $n \approx k$, using matrix multiplication

Suppose that $n = k$. Our goal is to do better than an $O(n^2k) = O(n^3)$ running time.

We can think of the bitvectors and bit positions as nodes in a graph. There is an edge between a bitvector node and a bit position node when the bitvector has a 1 in that position. The resulting graph is bipartite (with the bitvector-representing nodes on one side and the bitposition-representing nodes on the other), and has $n + k = 2n$ nodes.

Given the adjacency matrix $M$ of a graph, we can tell if there is a two-hop path between two vertices by squaring $M$ and checking if the resulting matrix has an "edge" between those two vertices (i.e. the edge's entry in the squared matrix is non-zero). For our purposes, a zero entry in the squared adjacency matrix corresponds to a non-overlapping pair of bitvectors (i.e. a solution). A lack of any zeroes means there's no solution.

Squaring an n x n matrix can be done in $O(n^\omega)$ time, where $\omega$ is known to be under $2.373$ and conjectured to be $2$.

So the algorithm is:

* Convert the bitvectors and bit positions into a bipartite graph with $n+k$ nodes and at most $nk$ edges. This takes $O(nk)$ time.
* Compute the adjacency matrix of the graph. This takes $O((n+k)^2)$ time and space.
* Square the adjacency matrix. This takes $O((n+k)^\omega)$ time.
* Search the bitvector section of the adjacency matrix for zero entries. This takes $O(n^2)$ time.

The most expensive step is squaring the adjacency matrix. If $n=k$ then the overall algorithm takes $O((n+k)^\omega) = O(n^\omega)$ time, which is better than the naive $O(n^3)$ time.

This solution is also faster when $k$ grows not-too-much-slower and not-too-much-faster than $n$. As long as $k \in \Omega(n^{\omega-2})$ and $k \in O(n^\frac{2}{\omega-1})$, then $(n+k)^\omega$ is better than $n^2 k$. For $w \approx 2.373$ that translates to $n^{0.731} \leq k \leq n^{1.373}$ (asymptotically). If $w$ limits to 2, then the bounds widen towards $n^\epsilon \leq k \leq n^{2-\epsilon}$.
> 8 votes

# Answer
This is equivalent to finding a bit vector which is a subset of the complement of another vector; ie its 1's occur only where 0's occur in the other.

If k (or the number of 1's) is small, you can get $O(n2^k)$ time by simply generating all the subsets of the complement of each bitvector and putting them in a trie (using backtracking). If a bitvector is found in the trie (we can check each before complement-subset insertion) then we have a non-overlapping pair.

If the number of 1's or 0's is bounded to an even lower number than k, then the exponent can be replaced by that. The subset-indexing can be on either each vector or its complement, so long as probing uses the opposite.

There's also a scheme for superset-finding in a trie that only stores each vector only once, but does bit-skipping during probes for what I believe is similar aggregate complexity; ie it has $o(k)$ insertion but $o(2^k)$ searches.
> 4 votes

# Answer
Represent the bit vectors as an $n\times k$ matrix $M$. Take $i$ and $j$ between 1 and $n$.

$$\begin{align} (MM^T)\_{ij} = \sum\_l M\_{il}M\_{jl} \end{align}.$$

$(MM^T)\_{ij}$, the dot product of the $i$th and $j$th vector, is non-zero if, and only if, vectors $i$ and $j$ share a common 1. So, to find a solution, compute $MM^T$ and return the position of a zero entry, if such an entry exists.

**Complexity**

Using naive multiplication, this requires $O(n^2k)$ arithmetic operations. If $n=k$, it takes $O(n^{2.37})$ operations using the utterly impractical Coppersmith-Winograd algorithm, or $O(n^{2.8})$ using the Strassen algorithm. If $k=O(n^{0.302})$, then the problem may be solved using $n^{2 + o(1)}$ operations.
> 2 votes

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


title: Analysing Space Complexity

text:
# Question
Title: Analysing Space Complexity
I have to compute the space complexity of this function:

```
double foo(int n){
     int i;
     double sum;
     if(n==0) return 1.0;
     else
          for(i=0;i<n;i++)
              sum+= foo(i);
     return sum
}

```

What I have done:

When function is called, the activation record is created on the call stack. For $foo(n)$ let the size of AR be $x$.

* $foo(0)$ does not place any recursive calls.
* $foo(1)$ places 1 recursive call. Terminates at $foo(0)$.
* $foo(2)$ places 2 recursive calls to $foo(0)$ and $foo(1)$.
* $foo(1)$ places another recursive call. Therefore total calls placed is 2+1.
* $foo(3)$ places 3 recursive calls to $foo(0)$,$foo(1)$ and $foo(2)$. Therefore total calls placed is $3+0+1+3= 7$ recursive calls.
* $foo(4)$ places 4 recursive calls. $4+0+1+3+7= 15$.

Hence we can see that $foo$ produces calls in the pattern: 0,1,3,7,15,31,...

This shows us that $foo(n)$ produces $(2^n)-1$ recursive calls.

If we count the total no. of recursive calls made by $foo(n)$ it becomes a geometric series and evaluates to approximately $(2^n)-n$.

Hence I am getting Space complexity to be $O(2^n)$.

However several books have merely listed the answer as $O(n!)$ without giving an explanation. I just want to know where I am going wrong in my approach.

# Answer
In my opinion you are not quite right...

During the loop, when you return from `foo(i)`, the spaces used by the call `foo(i)` is released (I mean, the stack pointer is back to the previous position).

So actually `foo(i)` only uses `1` more AR than `foo(i - 1)`. The space cost should be `O(n)`.

This can be verified by running the code with `foo(25)` and specify a stack of size `1 MB` (disable all optimizations, of course). It will return normally within several seconds, without "stackoverflow". This is a proof that it's not using O(2^n) space.
> 7 votes

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


title: Heuristic function

text:
# Question
Title: Heuristic function
Is there any way to prove that an admissible heuristic may not be consistent? Most proof I came across are through examples .Is there a generalized proof?

# Answer
> 2 votes
If you want to prove a heuristic is not consistent a counterexample is all you need, you don't need a more "generalized" proof. A counterexample is proof enough.

This is because a heuristic is consistent if some property *always* holds. It is not consistent if the property doesn't hold *once*. An example is all you need to show something happens *once*, if you want to show something *always* holds then you need a general proof.

---
Tags: search-algorithms, artificial-intelligence, heuristics
---


# Question
Title: why do CPU architectures use a flags register (advantages?)
Some CPUs have a flags register (ARM,x86,...), others don't (MIPS,...). What's the advantage of having a CMP instruction to update the flags register followed by a branch instruction instead of using a zero register and conditional branches to check for sign, overflow etc?

# Answer
> 11 votes
In modern micro-architectures with register renaming the implementation cost for flags or not flags is pretty similar. The main difference I can think of is that some flags indicate the characteristics of a value (Is the value negative? Is the value zero? Does the value have even or odd parity?), while some represent an event that occurred during a previous operation (did the add instruction have a carry out or an overflow?) This led to a less-than-ideal situation on the MIPS when you wanted to simulate 64-bit addition on the 32-bit architecture (or 128-bit addition on the 64-bit architecture.) On most architectures with a carry flag there is a special `add-with-carry` instruction, that includes the carry flag from the previous add instruction. This makes simulating multi-precision arithmetic relatively inexpensive on many architectures with flags registers.

On the flip side, testing an N-bit register for zero or not-zero is actually surprisingly expensive. To test an N-bit register for zero you need to perform an N-bit NOR operation, which requires $O(\log N)$ levels of logic to calculate. On architectures with flags registers the extra logic for the zero/not-zero calculation at the end of the ALU stage can cause the clock to run slower (or force the ALU to have two cycle operations.) For this reason, I think, some architectures, like SPARC had two versions of each arithmetic operation, one that set flags and one that didn't.

But MIPS doesn't save anything here. They just moved the problem somewhere else. On MIPS there is a `branch-on-equal` instruction. This means that the branch instruction must actually have an ALU stage (including something like a bitwise `xor` operation followed by a `nor` to reduce down to the single equal/not-equal bit) before determining which way the branch goes.

The DEC Alpha architecture tried to split the difference by using a trick. DEC Alpha had no flags registers, but also didn't have a `branch-on-equal` instruction. Instead the branch instructions all look at the state of a single general purpose register. There is `branch-on-zero`, `branch-on-not-zero`, `branch-on-less-than-zero`, etc. The trick is that you can give every general purpose register an extra 65th bit that tells you whether the other 64 bits are all zero or not. This makes it more like having a flags register: all the branch instructions look at a single bit (that is already calculated) to make their decision, but now you are back to figuring out how to calculate that extra zero indicator bit during a normal ALU cycle. (And you still can't do multi-precision arithmetic just by looking at the carry flag from the previous operation.)

# Answer
> 7 votes
# 1 From an ISA perspective

1. Having test instructions which set only the flags is just a way to reduce the register pressure in register starved architectures. If you have enough registers, just modify one of them and ignore the result. The trick of having a register 0 with input value 0 is just an encoding trick convenient when you have enough registers that fixing one of them to 0 is better than increasing the number of instructions. It is then convenient to use it as a target as well (it reduces the number of false dependencies).
2. Encoding again. If you encode the condition in jumps, you'll have jumps with 3 operands (the two to be compared and the jump target), two of which you'd like to be immediate values, one you'd like to be as big as possible (jumps have often their own encoding format so that the target can use as many bits as possible). Or you drop possibilities.
3. Using flags gives you more opportunities to set them. It is not just the comparison operations which can set the flags, but whatever you want. (With the caveat that the more operations you have which set flags, the more careful you have to be to ensure that the last operation which set the flags is the one you want). If you have flags, you are able to test the number of conditions (often 16) multiplied by the number of instructions which are able to set the flags (If you are not using flags, you end up with about as many conditional jumps as you have things to test or there are things you don't allow to test as easily (carry or overflow for instance).

# 2 From an implementer perspective

1. Testing flags is easy and can be done quickly. The more complex your test is, the more effect it will have on the cycle time (or the pipeline structure if you are pipelined). That's especially true for simpler implementations, when you get to a high end processor using all the tricks of the book, the effect is pretty minimal.
2. Having flags means that a lot of instructions have multiple results (the natural result and each of the modified flags). And from a micro-architecture POV, multiple results are bad (you have to keep track of their association). When you have just one set of flags, that introduce dependencies (unneeded if the flag is not then used) you have to handle way or another. Again that's especially true for simpler implementations, when you get to an high end processor using all the tricks of the book, the additional difficulties are dwarfed by the rest of the processor.

# Answer
> 2 votes
On a 32-bit machine, an "add-with-carry" instruction used as part of a multi-precision addition sequence needs to accept 65 bits worth of operands and compute a 33 bits sum. The source-register specifications will identify where 64 operand bits should come from, and the destination-register specification will say where the lower 32 bits of the result should go, but what to do with the "add one extra" operand or the upper bit of the result? Being allowed to specify as part of the instruction where the extra operand should come from and where the extra result bit should go would be moderately useful, but it would generally not be so useful as to justify an extra field in the opcode. Having a fixed "location" to handle the carry flag can be little bit awkward from an instruction-scheduling perspective, but it's a lot cheaper than having additional operand fields, and is much more practical than most other ways of trying to handle multi-precision arithmetic.

If one were trying to design an instruction set to allow multi-precision arithmetic but each instruction were limited to two 32-bit operands and one 32-bit destination operand, one could implement a 64-bit "add" in four instructions: "set r5 to 1 if r0+r2 would carry or zero otherwise; compute r4=r1+r3; compute r5=r4+r5; compute r4=r0+r2", but going beyond that would require three instructions for each additional word. Having a carry flag available as a supplemental source and destination reduces the cost to one instruction per word.

Note, btw, that having an instruction bit control whether the instruction updates the flag register may facilitate out-of-order execution, since instructions which use or modify the flag bits must maintain their sequence relative to each other, but instructions which do neither may be freely rearranged. Given the sequence:

```
ldr  r0,[r1]
add  r0,r0,r2
eors r4,r5,r6

```

an execution unit could fairly easily recognize that the third instruction could execute without having to wait for data to be read from `[r1]`, but if the second instruction had been `adds r0,r0,r2` that would only be possible if the execution unit could ensure that by the time anything tried to use the flags, the zero flag would hold the value established in the third instruction but the carry flag would hold the value in the second.

# Answer
> 0 votes
Simple answer ... quick cheap memory operation that requires absolutely no internal buss usage except the instruction itself. It can be used as a stack bool with out a stack or a process bit, with no memory.

---
Tags: computer-architecture
---


# Question
Title: Why do we need so many transistors in a chip, and how are they managed?
My knowledge is very vague as all we have are visual diagrams etc, but we have memory address and registers, the ALU being the heart(apparently). Single core CPUs process one instruction at a time AFAIK and multi-core have parallelism to some degree. So where do the millions of transistors come in and how do 32 registers manage everything. We have FPU's I know, how many transistors would these use roughly. Any way to get a fairly simple idea of what the bulk of the transistors do, why more means faster and how the registers 'manage' everything.

# Answer
This is a *huge* question. To fully answer it would take far more space than you'd want to read (not to mention that I suspect that there's a limit on the length of any SE answer), but I'll try to give you an idea of what goes on in the CPU.

First, a transistor (when used in a CPU) is essentially a switch, like a light switch except that you don't have to turn it on or off manually. Rather, it is controlled by an electrical current. The most important thing to understand is that modern computers are two-state devices: the only thing that really matters is whether a wire has a current or not.

One then begins the process of chip design by, for example, deciding how an integer (or other data) will be represented. For integers, say, the chip designers generally decide to them by ganging wires together in a logical unit, so with a collection of four wires it would be possible to represent 16 possible patterns: $\mathtt{0000}, \mathtt{0001}, \dots \mathtt{1111}$, where a pattern like $\mathtt{1101}$ would represent a voltage in wires 1, 2, and 4, and no voltage in wire 3 and this collection might be interpreted as the number 13. In this example, we'd have what's known a a *4-bit chip*. A modern computer would have either 32 or 64 wires treated as a unit.

It happens that with a suitably-connected collection of switches (aka transistors), one can do things like add two numbers, compare two numbers for equality, decide whether a number is zero or not, and so on. Often, all of these operations are often done at once, simultaneously, and the relevant one is chosen by the current instruction, which determines which of the various results to use, and where that result will be sent. All of this traffic control is also controlled by switches, depending on what the current instruction is (in the program being executed). In addition, things like memory and registers which store information can also be implemented by these switches.

To get a feel for the number of transistors used, an adder circuit in a $n$-bit computer might require about, say, $20n$ transistors, an $n$-bit register might require $50n$ transistors, and the traffic control circuitry to sent the results to the right place might require several hundred more for each bit. It's not hard to imagine that with a lot of functionality and a wide data path (the number of wires ganged together) a modern CPU could easily take millions of transistors.

As to why "more \[transistors\] means faster", the answer is "not necessarily", but in general, doubling the width of the data path, say from 32 bits to 64, gives you the ability to manipulate larger numbers in a single instruction at the cost of requiring more transistors.

Finally, the registers don't really "manage everything". A register is simply a very fast storage unit, capable of storing and retrieving information far faster than, say RAM memory. For that reason, things like the current instruction are often stored in a special register (called the instruction register), simply because access to its bits is very fast. The current instruction actually "manages everything", and it's stored in a register for speed.

This is a very abbreviated explanation---I've left out a ton of detail and glossed over a lot of technical matters, but I hope it at least gives you a sense of what goes on in a modern computer. \[entering duck-and-cover mode in expectation of howls of complaints from computer engineers\]
> 17 votes

# Answer
Typically one bit of cache memory requires 6 transistors (some designs use more or less, with different tradeoffs; see http://en.wikipedia.org/wiki/Static\_random-access\_memory), so modern CPUs with large caches spend a lot of transistors there.

Modern CPUs also execute multiple instructions concurrently, so there are multiple execution units (ALUs) on the chip, each of which is fairly complex.

Certain mathematical algorithms in the FPU can be accelerated by table lookup plus interpolation; the reciprocal square root instruction in Intel SSE units, for example, is implemented with a table that gives 12-bit precision almost instantly; this table is essentially a chunk of ROM on the chip -- that is, still more transistors.
> 7 votes

# Answer
there are several questions here & will just focus on one of them. the transistors on a chip is "roughly" proportional to the surface area used for the transistors. so you can find diagrams of a chip that show the graphical boundaries of different subsystems and simply use the formula that # of transistors in a region is equal to the proportion of area of that region to total area times total number of transistors on the chip.

example in this paper:

fig 1 shows the graphical boundaries on the chip. see fig 4 that gives area and # of devices in the millions for the separate functions of the CPU. the exception is that it appears that cache circuits are very dense and have much more transistors per area, it seems to have 3x the transistors at 2/3 the area. apparently on this chip it looks like about ¾ the transistors are dedicated to fast cache.
> 1 votes

# Answer
The simple answer is transistors are the basic components of logic gates, registers and storage devices. their various configurations make possible the or and not and flip-flops that comprise the higher order registers and processors. Look up the 7404 (not gate)7408 (and) and the 7432 (or gates). the basic 7474 and the 74279 are storage configurations. I am not sure if national semiconductor still publishes the actual schematic but texas instruments does.
> -2 votes

---
Tags: computer-architecture
---


# Question
Title: Existence of shortest path in a graph with no negative cycles?
Suppose that the input graph $G$ does not have any negative cycles but however it is permitted to contain edges having negative weight. Let $s$ be the source vertex.

How do I prove that for every vertex $v$ in $G$, there is a shortest $s-v$ path with $\<= n - 1$ edges?

Where $n$ is the number of vertices in $G$.

# Answer
If there is a path $P$ from $s$ to $v$, there is one where no vertex occurs more than once, with a weight that is less or equal to $P$. Indeed, if a vertex $x$ occurs twice, there is necessarily a loop from $x$ to itself. This loop cannot have a negative weight by hypothesis. So by removing it, we get a path that is no heavier. This can be repeated until we obtain a path where no vertex occurs more than once. Hence there are at most $n$ vertices on such a path, which means that the path has at most $n-1$ edges.

Thus we can consider only paths with at most $n-1$ edges, with each edge occurring at most once, since any other path is no lighter than a path in that set.

Since this set is finite, the number of edge conbinations to be used for a path is necessarily finite too (further limited by the constraint or forming a path from $s$ to $v$). Thus the set of weights has a minimum corresponding to some path(s) wich is (are) the minimum /shortest path(s).
> 4 votes

# Answer
Basically you have not much options here – do relaxation on each vertex peeking them from the list like Bellman-Ford does and you'll end up with a shortest path to one vertex, and move on.
> 0 votes

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


# Question
Title: How many bits would be needed for the byte?
**The Problem:** A high speed workstation has 64 bit words and 64 bit addresses with address resolution at the byte level. Assuming a direct mapped cache with 8192 64 byte lines, how many bits are in each of the following address fields for the cache? 1) byte 2) Index 3) Tag?

I know that an address for specifying data within a cache is 64 bits.
I know that an address for a cache has to have the byte, index, and tag field so
byte + index + tag = 64
The index field should take up 13 bits to account for the 8192 byte lines

How many bits would be in the byte field though? I know that a processor processes one word at a time and each word consists of 8 bytes. A 64 byte cache line would contain 8 words. Would this byte field need to identify each word or each byte itself. If it was byte itself, it be 6 bits but if it was word it be 3 bits.

If I had to take a stab, I would say the byte field needs to be 3 bits to identify each word because it doesn't make sense for the processor to just process one byte. Can anyone confirm my suspicisions?

# Answer
In a processor architecture of 64 bits the smallest single 'word' is 64 bits. that is each cyclic transfer from buffer to buffer occurs on a 64 bit buss. to identify a single byte of this native word in fact would only take 3 bits, but the actual register might in fact be 8-16 bits... if it was designed that way. the compiler that was designed to handle this would take all this into account and when you incremented a pointer it would do the conversion for you. as well as if the 'byte ' was actually an Unicode 16 bit character'. you need to look at the cpu programmers guide or manual for actual specifics and also the compilers manual, specifically with regards to data types and to addressing them.
> 1 votes

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


# Question
Title: How does the Sutherland-Hodgman Algorithm work?
The following are the Pages-96 and Page-97 of the book Schaum's outline series of Computer Graphics.

The algorithm considers several things:

(1) Whether the polygon is Convex or Concave.

(2) Whether the polygon is positively or negatively oriented.

(3) And, finally, testing polygon edges against the edges of the clipping window.

Consider the **`WXYZ`** as the clipping rectangle in the following picture.

I have several questions:

(1) Do I need to test an edge **`AB`** against all of the edges of **`wxyz`** or just **`wx`**?

(2) Suppose, I test **`AB`** against **`wx`**. According to the Page-97 of the book, I should be testing whether it is on the left or on the right side of the clipping edge. But,in this case, there are no lefts or rights. There are aboves and bellows. How can I determine whether it is inside or outside?

(3) How can I keep track of the **`Inside`** and **`Outside`**? For example, Consider the polygon edge **`BC`**. If I test it against `ZW`, it is on the Right side and Inside the Clipping Region. If I test it against `YX`, it is on the Left side and Inside the Clipping Region. It turns out to me that, it is actually not possible to find the position of a point with respect to the clipping region unless we consider the region at once and as a whole. Then why is the book testing points against one line at a time?

(4) Consider the edge **`DE`**. Is it going out or coming in?

# Answer
> 2 votes
As written in book:

> Let edge $E$, determined by endpoints $A$ and $B$, be any edge of the positively oriented, convex clipping polygon.

It means, that first of all you need orient your red rectangle counter-clockwise:

> We clip edge of the polygon in turn against the edge E of the clipping polygon, forming a new polygon. **...** The algorithm proceeds in stages by passing each clipped polygon to the next edge of the windows and clipping

I.e.:

1. Clip green polygon by $\overline{WX}$ (polygon will stay the same);
2. Clip polygon from step 1 by $\overline{XY}$ (still the same polygon);
3. Clip polygon from step 2 by $\overline{YZ}$ (yellow part will be cut off, and result of this step will be polygon $ABCKLE$);
4. Clip polygon from step 3 by $\overline{ZW}$ (blue part will be cut off, and result of this step will be polygon $ABCKLMN$);

Here we can answer on your **(1)** question - yes, $\overline{AB}$ will be tested against all edges of clipping windows. And answer for question **(4)**: $\overline{DE}$ will not be in resulting polygon, but $\overline{LM}$ (everything that lefts from $\overline{DE}$) will belong to result.

To address question **(2)** \- we need to have a look at this quote (definition when point is on the left side or on the right side):

> Let $A(x\_1,y\_1)$ and $B(x\_2,y\_2)$ be the endpoints of a directed line segment. A point $P(x, y)$ will be to the left of line segment if the expression $C=(x\_2-x\_1)(y-y\_1)-(y\_2-y\_1)(x-x\_1)$ is positive.

$\overline{WX}$ is directed line segment and points $A$ and $B$ is on the left side, then whole $\overline{AB}$ edge is to the left of the line segment (cliping edge) $\overline{WX}$.

Question **(3)**: again due to edge of clipping windows is directed $\overline{BC}$ really on the left side of $\overline{XY}$, $\overline{ZW}$ (also it's to the left of $\overline{YZ}$ and $\overline{WX}$).

*I think, the cause of the questions that you forget to orient clipping rectangle.*

---
Tags: graphics
---


# Question
Title: Why computer science papers rarely use advanced mathematics?
I am a M.Sc. student in computer science, working on information networks and recommender systems. This days when I went through the top-tier conferences papers in the field I have seen most of them use solely simple machine learning tools such as generalized linear model, Expectation Maximization, Maximum Likelihood, etc.

One may argue that this simple methods work better and We shouldn't take the blame for the sake of simplicity. That is true but I have not even seen an interest to try compare their results with some more advanced mathematical methods.

I am wondering why scientists don't try to explore more mathematics to involve in their research. Because there is not something better in exploding world of mathematics or because of its difficulty, etc?

Edit: I mean the areas that are more related to continuous mathematics than CS theory.

# Answer
> 3 votes
There are many reasons that you may not see a lot of complex mathematics in the papers you are reading.

First, the tools used depend on the task at hand. If a task is simple, a simple tool might be adequate. Also, if the task runs on a simple system, a simple tool is often best.

Second, usually in Computer Science, the goal is usually to make things usable to a layprogrammer; therefore, it would be detrimental to make something depend on an advanced or abstract concept that few people understand. Often, the proofs sections of algorithms papers have much more advanced mathematics than the rest of the paper; the assumption is that anyone who wants to verify the correctness of the algorithm or its complexity can invest the time in understanding the proof, but that that is not essential to use the results.

Finally, some of this has to do with a lack of familiarity; people who spend their lives reading and writing computer science papers might never have the time to learn about new, highly complex mathematics. Actually, a great way to expand the field is to introduce a concept that many mathematicians understand in a way that it is accessible to and usable by computer scientists. (For instance, I have a friend whose PhD work applied known concepts of Control Theory to problems in Motion Planning. He did very little new work, but he did advance Motion Planning.)

---
Tags: research
---


title: Set Associative Cache - duplicate Tag

text:
# Question
Title: Set Associative Cache - duplicate Tag
In a set associative cache (in this case 4-way) what happens when you try to read an entry with e.g. the tag *0x3B* and this tag appears two times within the same set. Given the first is invalid, would you search on for the second (which is valid) or simply get a miss? And why do would there be a duplicate line at all?

# Answer
> 3 votes
The CPU tests all caches ways and selects the one that is both valid and have a matching tag address. It may occur concurrently on all ways or be sequential (with a preferred way, depending on the address)

When invalidating cache lines, only the valid bit needs to be cleared, the tag address value do not need to be modified, so it may contain stray values.

(Cache lines may be invalidated by the operating system for coherency with some DMA peripherals, because of self-modifying code, by hardware cache coherency algorithms like MEI/MESI, etc. Depends on the architecture.)

You cannot have several lines that are simultaneously valid and with the same tag address \[and different data\].

It may occur at power-up, if registers are not automatically reinitialized, and the boot sequence may have to manually clear the cache before enabling it using special accesses and/or instructions.

# Answer
> 2 votes
The cache usually performs the tag comparison in parallel, and the same tag is not supposed to be in two different locations. However, since the valid bit is off at one place, it may be the case that the same tag appears more than one, where only one of the places is valid.

In fact, if the valid bit is off there is no reason to even compare that tag—even if it matches, the result will be a miss, similar to the case the tag was not found). So the most rational behavior here, is that the "valid" bit enables the selection of that cell, and cells with valid=0 are excluded form the tag comparison circuit.

---
Tags: cpu-cache
---


title: Classical Computation without NOT

text:
# Question
Title: Classical Computation without NOT
Is it possible to do universal classical computation using bits and 2-bit gates when you cannot perform a NOT operation on a single bit (hence cant do CNOT and so on). If yes, what are the possible universal sets of gates that do not utilise the NOT transformation. Thanks!

EDIT: to clarify, you can perform any set of operations you want, but if there is some sequence that you apply these operations in that is equivalent to a NOT operation then they are forbidden. For example, in quantum computing you can take the square root of a not operation, but as applying two of these gives a not operation then this would not be allowed

# Answer
You're confusing classical and quantum computation, so let me ignore the quantum aspects for now. If you forbid the unary NOT gate then you can use a binary NOT gate, say $g(a,b) = \lnot a$. You can also simulate NOT using natural gates: $XOR(a,1) = \lnot a$ (and this gate can even be made reversible!). So this kind of restriction is not really meaningful.

It is more meaningful to ask what happens if all gates are *monotone*, that is, they satisfy $g(x\_1,\ldots,x\_n) \leq g(y\_1,\ldots,y\_n)$ whenever $x\_i \leq y\_i$ (here $\text{FALSE}\leq\text{TRUE}$). Such circuits are known as *monotone circuits*, and they can only compute monotone functions. One natural complete basis is $\\{\text{AND},\text{OR}\\}$. You can show that this basis is complete using DNFs.
> 4 votes

# Answer
Yes, it is very possible to replace a one-bit not with a two-bit gate:

Few examples: not(a) = xor(a, 1) not(a) = nand(a, a) not(a) = nor(a, 0)

The keyword to describe "*universal sets*" is *functional compplete*. You can find the complete list of minimal,, functional complete sets (with 2 inputs) at wikipedia
> 2 votes

---
Tags: computation-models, circuits, boolean-algebra, digital-circuits
---


title: Finding the median in a heap

text:
# Question
Title: Finding the median in a heap
Given a binary heap $H$, indexed in $\[1..n\]$, whose elements are integers, is there a way to quickly find its median in $O(\log n)$-time?

# Answer
> 6 votes
It takes $\Omega(n)$ time to find the median of a heap in the worst case. The reason is that the lowest levels of the heap (the leaves and their close ancestors) can be very disordered, and they make up the majority of the heap. As a result, if you can find the median on a heap, you can find a median of the $\Omega(n)$ unordered elements near the leaves. Since finding the median in an unordered list takes $\Omega(n)$ time, so does finding the median in a binary heap.

For instance, if finding the median in an unordered array of size $n$ takes a given amount of time, presumably it shouldn't be any faster to find the median of that array if we prepend to it an array of size $n$ consisting of only $-\infty$ and append to it an array of size $n$ consisting of only $+\infty$. Yet, this new array of size $3n$ is a valid binary heap, and its median is also the median of the original unordered array of size $n$. Thus, if we can find the median of the heap in $O(\log 3n) = O(\log n)$ time, then we can also find the median of an unordered array in $O(\log n)$ time.

Since we know that it takes $\Omega(n)$ time to find the median of an unordered array of size $n$, it must also take $\Omega(n) = \Omega(3n)$ time to find the median of a heap of size $3n$.

# Answer
> 2 votes
It depends on the structure of your heap. You can create a heap based around the median being the first element, but in a typical min or max heap, it's going to be `O(n)`.

Check this post: https://stackoverflow.com/questions/2579912/how-do-i-find-the-median-of-numbers-in-linear-time-using-heaps

---
Tags: data-structures, priority-queues, selection-problem
---


title: What is a Universal Turing machine?

text:
# Question
Title: What is a Universal Turing machine?
Could a Universal Turing machine be set up so that it is able to 'reprogram' itself to 'behave' like any specific Turing machine without using some 'outside' source of info to cause it to do this?

# Answer
> 6 votes
Turing machine is a formalized representation of the concept of algorithm (aka effective method). Why do we need a formalized representation? So that we can reason precisely about the thing and that's why Turing created this formalized representation to answer Hilbert question of decision problem.

A Universal Turing machine is a machine that can simulate any Turing machine i.e An algorithm that can simulate any algorithm. Intuitively it may seem that this algorithm that can simulate any other algorithm must be really complex BUT it turns out that this algorithm is really the dumbest algorithm possible. In Turing machine the "state transition table" is the logic of the algorithm and the state of the tape is the Input and Output of the algorithm. Now if I want to create a Turing machine that can simulate any algorithm than I could try to design a state transition table that has logic for every possible algorithm (e.g sorting, hashing, compression and on and on ...) but that is not feasible as the number of all algorithms is infinite. What about if we encode this state transition table as the input and the state transition table of the machine is designed such a way that its logic depends on the state transition table encoded in the input. In this way this single and quite simple Turing machine can simulate any other Turing machine.

> So if an algorithm can not be 'inputted' to the Universal turing machine it is not computable , is this true?

I guess by 'inputted' you mean that the algorithm cannot be encoded as input to the UTM. Any algorithm can be encoded as input to the UTM the only requirement is that you should "know the algorithm first". If you don't have the algorithm then obviously the function is not computable .... yet :)

---
Tags: computability, turing-machines, recursion-theory
---


title: Data compression using prime numbers

text:
# Question
Title: Data compression using prime numbers
I have recently stumbled upon the following interesting article which claims to efficiently compress random data sets by always more than 50%, regardless of the type and format of the data.

Basically it uses prime numbers to uniquely construct a representation of 4-byte data chunks which are easy to decompress given that every number is a unique product of primes. In order to associate these sequences with the primes it utilizes a dictionary.

My question is:

* **Is this really feasible as the authors suggest it?** According to the paper, their results are very efficient and *always* compress data to a smaller size. Won't the dictionary size be enormous?
* **Couldn't this be used to iteratively re-compress the compressed data using the same algorithm?** It is obvious, and has been demonstrated, that such techniques (where the compressed data is re-compressed as many times as possible, dramatically reducing the file size) are impossible; indeed, there would be no bijection between the set of all random data and the compressed data. So why does this feel like it would be possible?
* Even if the technique is not perfect as of yet, it can obviously be optimized and strongly improved. **Why is this not more widely known/studied?** If indeed these claims and experimental results are true, couldn't this revolutionalize computing?

# Answer
> always compress random data sets by more than 50%

That's impossible. You can't compress *random* data, you need some structure to take advantage of. Compression must be reversible, so you can't possibly compress *everything* by 50% because there are far less strings of length $n/2$ than there are of length $n$.

There are some major issues with the paper:

* They use 10 test files without any indication of their content. Is the data really random? How were they generated?
* They claim to achieve compression ratios of *at least* 50%, while their test data shows they achieve *at most* 50%.

> This algorithm defines a lossless strategy which makes use of the prime numbers present in the decimal number system

* What? Prime numbers are prime numbers regardless of the base.
* Issue #1 with decompression: prime factorization is a hard problem, how do they do it efficiently?
* Issue #2 with decompression (**this is the kicker**): they multiply the prime numbers together, but doing so you lose any information about the order, since $2\cdot 5 = 10 = 5\cdot 2$. I don't think it is possible to decompress at all using their technique.

I don't think this paper is very good.
> 34 votes

# Answer
I'm going to defer to Tom van der Zanden who seems to have read the paper and discovered a weakness in the method. While I didn't read the paper in detail, going from the abstract and the results table, it seems like a broadly believable claim.

What they claim is a consistent 50% compression ratio on *text files* (not "all files"), which they note is around the same as LZW and about 10% worse than (presumably zero-order) Huffman coding. Compressing text files by 50% is not hard to achieve using reasonably simple methods; it's an undergraduate assignment in many computer science courses.

I do agree that the paper isn't very good as published research, and I don't think it speaks well of the reviewers that this was accepted. Apart from the obvious missing details that makes the results impossible to reproduce (e.g. what the text files were), and no attempt to tie it into the field of compression, there is no sense that they really understand what their algorithm is doing.

The conference web site claims a 1:4 acceptance ratio, which makes you wonder what they rejected.
> 16 votes

# Answer
You ask:

> * Is this really feasible as the authors suggest it? According to the paper, their results are very efficient and always compress data to a smaller size. Won't the dictionary size be enormous?

Yes, of course. Even for their hand-picked example ("THE QUICK SILVER FOX JUMPS OVER THE LAZY DOG"), they don't achieve compression, because the dictionary contains every 4-byte substring of the text (minus 4 bytes for the one repetition of "THE")... and the "compressed" version of the text has to include the whole dictionary *plus* all this prime number crap.

> * Couldn't this be used to iteratively re-compress the compressed data using the same algorithm? It is obvious, and has been demonstrated, that such techniques (where the compressed data is re-compressed as many times as possible, dramatically reducing the file size) are impossible; indeed, there would be no bijection between the set of all random data and the compressed data. So why does this feel like it would be possible?

Again you seem to have a good intuitive grasp of the situation. You have intuitively realized that no compression scheme can ever be effective on *all* inputs, because if it were, we could just apply it over and over to compress any input down to a single bit — and then to nothingness!

To put it another way: Once you've compressed all your .wav files to .mp3, you're not going to get any improvement in file size by zipping them. If your MP3 compressor has done its job, there won't be any patterns left for the ZIP compressor to exploit.

(The same applies to encryption: if I take a file of zeroes and encrypt it according to my cryptographic algorithm of choice, the resulting file *had better not be compressible*, or else my encryption algorithm is leaking "pattern" into its output!)

> * Even if the technique is not perfect as of yet, it can obviously be optimized and strongly improved. Why is this not more widely known/studied? If indeed these claims and experimental results are true, couldn't this revolutionalize computing?

These claims and experimental results are *not* true.

As Tom van der Zanden already noted, the "compression algorithm" of Chakraborty, Kar, and Guchait is flawed in that *not only* does it not achieve any compression ratio, it is *also* irreversible (in mathspeak, "not bijective"): there are a multitude of texts that all "compress" to the same image, because their algorithm is basically multiplication and multiplication is commutative.

You should feel good that your intuitive understanding of these concepts led you to the right conclusion instantly. And, if you can spare the time, you should feel pity for the authors of the paper who clearly spent a *lot* of time thinking about the topic without understanding it at all.

The file directory one level above the URL you posted contains 139 "papers" of this same quality, all apparently accepted into the "Proceedings of the International Conference on Emerging Research in Computing, Information, Communication and Applications." This appears to be a sham conference of the usual type. The purpose of such conferences is to allow fraudulent academics to claim "publication in a journal", while also allowing unscrupulous organizers to make a ton of money. (For more on fake conferences, check out this reddit thread or various StackExchange posts on the subject.) Sham conferences exist in every field. Just learn to trust your instincts and not believe everything you read in a "conference proceeding", and you'll do fine.
> 12 votes

# Answer
Entropy effectively bounds the performance of the strongest lossless compression possible. Thus there exist no algorithm that can compress random data sets by always more than 50%.
> 6 votes

# Answer
Compression methods, that are restorable, in general find a pattern and re-express it in a simplistic way. Some are very clever, some very simple. At some point there is no pattern. The process(es) have 'boiled' the data set down to it simplest unique pattern. Any attempts at compression from that point forward result in a larger data set, or dilute the uniqueness. In magic number compression schemes there is always a flaw, or a slight of hand, or loss. be wary of any process that claims to out do the latest WinZip or RAR.
> 1 votes

---
Tags: information-theory, data-compression, primes
---


# Question
Title: Unique path sums in a DAG using vertex instrumentation
I stumbled across this paper from Ball et al. In their paper they assign specific values to the edges of a graph. When the graph is traversed, or lets call it executed (since they talk about control flow graphs of programs), these values are summed up. Afterwards they are able to reconstruct the executed path from the sum of the values of the traversed edges.

For my research problem, I can not instrument edges, but vertices. To optimize vertex instrumentation I found a great paper from Knuth. However, I can not find a publication about determining vertex values that can be used in a manner as the edge values from the Ball paper.

Does anyone know about an algorithm to fulfill my task?

# Answer
> 1 votes
The paper of Ball can be found here: http://www.cs.ucr.edu/~gupta/teaching/260-08/Papers/pathprof.pdf

I think the solution is easy. In addition to the global variable r, we keep a global variable lastVertex. Before exiting a vertex v, we set lastVertex=v. Now, when entering a vertex, we know which vertex we came from and we only need to keep a map in each vertex from each possible previous vertex to the corresponding transformation of r. This is only slightly less efficient than with edges, as we need to do a lookup in a map in each vertex. For larger graphs, this may be memory intensive though.

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


# Question
Title: How to compare the time-complexity of an optimized algorithm with that of the original?
I had an algorithm with time-complexity of $O(h\times w)$, knowing $h$ is the height and $w$ is the width of an image being processed (or a simple matrix of size $h\times w$).

I managed to reduce the range that the algorithm process. So rather than dealing with $h\times w$ elements, it is dealing with $n\times m$ elements, where $n\<h$ and $m\<w$.

To recapitulate the optimization :

* Time-complexity of old algorithm is $O(h\times w)$
* Time-complexity of new algorithm is $O(h) + O(n\times m)$

Now my question is : how to express this time complexity optimization in terms of $h$ and $w$ ? is it a real optimization ?

# Answer
I am not sure what you mean by "complexity optimization".

A proper way to compare complexities is by considering their ratio, which is defined up to a constant factor. Considering the difference makes no sense, as there is always the invisible constant factor lurking around, invisible but not negligible.

However your problem here is that you have several variables, not the same in both variants of your algorithm, and no indication of how they relate. If you do not say precisely how $n$ and $m$ relate to $h$ and $w$, there is nearly nothing that can be done.

Given That all you know is that $n\<h$ and $m\<w$, the best you can say is that $n\times m\<h\times w$. But they may differ by a constant additive term or by a constant multiplicative factor, which does not change the complexity.

So the best you can say is that $O(m\times n)\subseteq O(h\times w)$, short of more precision on how $n$ and $m$ relate to $h$ and $w$

Thus $O(h)+O(m\times n)\subseteq O(h)+O(h\times w)$.

But $O(h)\subseteq O(h\times w)$, because both are linear in $h$ and the first is constant in $w$ while the second is linear.

Hence you get: $O(h)+O(m\times n)\subseteq O(h\times w)$.

All we know is that the **complexity is not worse than before**.

But that should not worry you too much. You seem to have the wrong vision of complexity, when asking:

> is it a real optimization ?

Your optimizations aim at improving performance in your range of applications.

**Complexity does not measure performance but scalability.** A constant multiplicative factor of ten zillions does not change the complexity but has a drastic effect on performance. The matrix multiplication algorithm that have the best complexity are never used because they have abysmal performance. You have to consider huge matrices for them to be any use.

Furthermore, raw complexity on arbitrary measure of the size of the problem may have little practical meaning in some cases. The relevant size for some complexity analyses may be the number of occurences of a specific feature of the problem input, rather than the length of the problem in number of symbols. Some exponential algorithms are routinely used without problems because the feature causing the high complexity is actually rarely used, independently of the input size.

Your modification of the algorithm may be a real optimization, that may give you an algorithm ten times faster, but this may not show in complexity analysis.

This is why it is sometimes useful to do precise cost analysis. But that is more difficult since you must account for the different costs of different elementary operations (which is not required for complexity analysis).

A possible way to assess your optimization is benchmarking, rather than tedious theoretical counting.

Your question did not say whether you were considering worst case or average complexity. I did not ask because my remarks apply in both cases.

Note: The fact that the algorithm has better performance, with the same worst case complexity does not imply that the average complexity was improved.
> 5 votes

# Answer
It appears that, before your optimization, your algorithm had the same worst- and average-case complexity, which is why it was easy to consider.

The change in asymptotic complexity really depends on how $n$ and $m$ relate to $w$ and $h$. If they are reduced by a constant factor, then your asymptotic complexity is not improved. If they are some root or logarithmic function, then your complexity has improved.

"\[If the asymptotic complexity is the same,\] is this a real optimization?"

Yes! Anything you can do that improves the average case without (or rarely) hurting the worst case, even if the improvement is only by a constant factor, makes the algorithm more useful in real world problems. 4x might be a constant improvement, but if you can make me run 4x faster, I'll be ecstatic. As @babou states in his answer, the asymptotic complexity is only useful in studying how the running time changes with a change in input size.
> 2 votes

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


# Question
Title: Combining two infinite algorithms to create a single infinite algortihm
Suppose I have an algorithm $F$ that, given a numeric input $x$, generates an infinite sequence of numbers that converges to a $f(x)$, where $f$ is some continuous real-valued function.

Similarly, I have an algorithm $G$ that, given a numeric input $y$, generates an infinite sequence of numbers that converges to $g(y)$, where $g$ is another continuous real-valued function.

I would like to have an algorithm $H$ that, given $x$, generates an infinite sequence of numbers that converges to $g(f(x))$. How can I do this?

My current idea is as follows. For every algorithm $A$ and integer $i$, let $A\_i(x)$ be the $i$-th value in the sequence returned by algorithm $A$ when run on input $x$.

Then, the algorithm $H$ should return the sequence:

$$G\_i(F\_i(x))$$

Initially, $H$ runs a single step of $F$ on $x$ and runs a single step of $G$ on the result. Then, $H$ runs two steps of $F$ on $x$ and runs two steps of $G$ on the result. This goes on infinitely.

Is this idea correct? Is there a better idea?

# Answer
**Is this idea correct?**

(I apologize for my initial, poorly thought-out response to this question, and thank the commentors for pointing out the flaws.)

Your solution will work if $g(\cdot)$ is differentiable around $f(x)$.

Since $G(y)$ converges to $g(y)$, for any constant $\epsilon\_G\>0$ there exists some $N\_G\>0$ such that for *any* $y$ and all $i\>N\_G$, $$-\epsilon\_G \< G\_i(y)-g(y) \< \epsilon\_G.$$

If $g(\cdot)$ is differentiable around $f(x)$, there exists constant $\epsilon\_f\>0$ such that $g(y)$ slopes toward $g(f(x))$ for all $y \in \left(f(x)-\epsilon\_f, f(x)+\delta\_g\right)$. Because $F$ converges to $f(x)$, there exists some $N\_F\>0$ such that for all $i\>N\_F$, $$-\epsilon\_f\< F\_i(x) - f(x) \< \epsilon\_f.$$

Since $g(\cdot)$ slopes toward $f(x)$ in the neighborhood containing all $F\_i(x)$ for $i\>N\_F$, as $F(x)$ approaches $f(x)$, $g(F(x))$ approaches $g(f(x))$; i.e., $g(F\_i(x))$ converges to $g(f(x))$. That is, for any $\epsilon\_g\>0$, there exists some $N\_g\>N\_F$ such that for all $i\>N\_g$, $$-\epsilon\_g \< g(F\_i(x)) - g(f(x)) \< \epsilon\_g.$$

Now let $y=F\_i(x)$. For any $\epsilon\>0$, set $\epsilon\_G = \epsilon\_g = \frac{\epsilon}{2}$. Then for all $i\>N$ (where $N=\max(N\_G, N\_F, N\_g)$), $$-\epsilon = -(\epsilon\_G+\epsilon\_g) \< G\_i(F\_i(x))-g(F\_i(x)) + g(F\_i(x)) - g(f(x)) \< (\epsilon\_G+\epsilon\_g) = \epsilon,$$ or, $$-\epsilon \< G\_i(F\_i(x)) - g(f(x))) \< \epsilon.$$ That is, $G\_i(F\_i(x))$ converges to $g(f(x))$.

---

**Is there a better idea?**

Probably. Your algorithm generates $O(i)$ numbers to create the $i$th output number.

Consider if the algorithms were finite (i.e., you stopped at the $n$th output). Then, you would run $F$ to $F\_n(x)$, then run $G$ using this as your input. This would only take generating $O(n)$ numbers. Your problem is not finite, though.

However, you can choose some constant $c$ and only restart $G$ after every $c$ steps. That is, the $i$th output will be $G\_i(F\_{c\lfloor i/c\rfloor}(x))$. This will make the convergence less smooth, but it will help your running time; it will now only generate $O(i/c)$ (amortized) numbers to create the $i$th output number.
> 2 votes

---
Tags: algorithms
---


title: Best sort approach for small data sets

text:
# Question
Title: Best sort approach for small data sets
I am working with small data sets of N elements, usually with N = 8, 16, or 32 elements; all are positive 64-bit float numbers. I need to identify the smallest N/2 elements. It is not required that the smallest N/2 elements be sorted, just that I identify which ones they are from among the group of N. Each program run must perform this sort up to a billion times, so sort speed improvements could generate useful returns for me. Right now I am using a simple Quicksort that orders all N elements just to prove out my concept.

It is quite likely that my data are not randomly distributed, but I am not yet at the point where I can get a handle on that.

Eventually, the grand design is that this will find its way into the real world via an X-code implementation.

Any recommendations as to what my best sorting strategy ought to be?

# Answer
> 3 votes
Here are two ideas. It's hard to say whether they're any good - you'll have to implement them.

1. Use (randomized or deterministic) QuickSelect in order to find the median, and then find the bottom half with a single scan.
2. Use some hard-coded sorting network, e.g. Batcher, bitonic or pairwise. If there is some hardware support for the basic operation of sorting two memory cells, then this can be pretty fast (even though you're not using parallelism). You can also try to come up with your own sorting network that only sorts in your sense - perhaps trimming one of the ones I listed would do.

# Answer
> 2 votes
You can modify your quicksort to a quickselect for the $N/2$ position.

Also, try implementing your own insertion sort. Insertion sort is REALLY fast for small arrays, and may be even faster than the quickselect.

---
Tags: algorithms, sorting, efficiency
---


# Question
Title: In an Inverted Page Table, will following chains happen very often for small addresses?
I just learned about the Inverted Page Table and immediately thought about the chaining model used. If two processes use the same virtual address, resolving the address will have to include following the chaining information in the table.

If all memory addresses were used uniformly, that should not be a problem, since address collisions would happen seldomly.

But if many processes use the first page (because they usually start using small addresses) will that not deteriorate performance on a real system a lot?

# Answer
> 2 votes
According to my knowledge, inverted page table has an entry for each physical frame, not for each logical page.

It is usually designed as a Hash table, where the Hash function takes both the task id and the page number as parameters. Thus (task A, address X) and (task B, address X) will not be likely to produce the same Hash value.

Does that answer your question?

---
Tags: performance, virtual-memory, paging
---


title: Universal binary rewriting system

text:
# Question
Title: Universal binary rewriting system
What is the simplest example of a rewriting system from binary strings to binary strings

$$f:\Sigma^\*\rightarrow\Sigma^\*\qquad\Sigma=\\{0,1\\}$$

that can perform universal computation? Binary string rewriting systems in general can compute any computable function, but I have trouble finding *particular* instances that can by themselves compute any computable function given an appropriate input. I've seen statements that a class of rewriting systems (e.g., the set of cyclic tag systems) is Turing-complete, but I'm looking for a single rewriting system that is universal.

I was thinking a self-modifying bitwise cyclic tag system might be a candidate, but I'm not sure how to interpret the output of such a system.

# Answer
> 6 votes
Rule 110 is a binary rewriting system that can perform universal computation, i.e., it has been proven to be universal. It can be implemented by a finite-state transducer: it needs only finite state.

However, Rule 110 is not a tag system or a cyclic tag system, so this does not provide an instance of a specific binary tag system that is known to be universal. It might be that examining the proof of universality of Rule 110 could yield such a system, as apparently the proof involves a reduction that goes by way of cyclic tag systems -- though personally I've never read the proof, so this is only speculation.

A side note: From Rule 110, you can construct a particular queue automaton that is universal: the queue alphabet is $\\{0,1,\\$\\}$ and contains the state of the cellular automaton (a binary string representing the contents of each cell, followed by $\\$$). I don't know whether it'd be possible to use this to construct a specific tag system that is universal (e.g., if you can find a way to use a tag system to emulate a queue automaton).

# Answer
> 3 votes
Binary Combinatory Logic is an example with simple rewriting rules.

---
Tags: computability, turing-machines, strings, computation-models, term-rewriting
---