title: about scheduling in operation system

text:
# Question
Title: about scheduling in operation system
1. In FIFO: when process get cpu time and then go to IO. What happend in the time it is in IO? another process can run? After finishing IO it continue or "loss its turn"? Why FIFO give priority to cpu bound process?
2. In RR: assume slice time is s and after (s-2) for eample it get IO, what happend with the 2 other seconds? it loss them?

3.In preemptive SJF we look on the *next* cpu burst. What about non preemptive SJF? we lock on all the cpu in the process will need?And in genreal we look only on cpu? not on io?

# Answer
Each program in the system is in one of three states: *running* (currently using the cpu), *waiting* (for i/o), or *ready* (not waiting for i/o, but not currently using the cpu). When discussing scheduling disciplines *jobs* are not programs, rather each burst of cpu usage between i/o requests in a program is a job.

*First-in-first-out* (FIFO), *round-robin* (RR) and *shortest job first* (SJF) are scheduling disciplines for choosing the next job to run from the ready queue of the operating system. So in all three cases the jobs under discussion correspond to the set of processes that are currently in the ready state.

In FIFO as each job reaches the head of the queue it gets the cpu, when the job requests i/o then it is done. The process (not the job) enters state waiting. When the i/o is done the process is moved from state waiting to state ready, and the *job* corresponding to its next burst of cpu is put on the back of the FIFO queue.

A *cpu bound* process is one where the average cpu bursts (the jobs) are much longer than the average time spent waiting for each i/o. Since FIFO is non-preemptive when a long cpu-burst gets to the head of the queue and starts running, all of the ready processes in the queue behind that job are stuck.

In round-robin we are also referring to jobs, not processes. When a job requests i/o it is done. When the process goes from waiting to ready the next job (cpu burst) from that process joins the round-robin queue.

Non-preemptive shortest job first is only practical if you really have future knowledge about exactly how long the jobs are. If some jobs are taking longer than you expected and you aren't preempting them, then you're not really running the shortest one first.

In general scheduling disciplines are only looking at the jobs in the ready queue. One of the points of SJF, though, is to make sure that the i/o system is kept as busy as possible. Jobs usually end with an i/o request, so by scheduling the shortest job first you are getting to the next i/o request the soonest.

This insight about shortest job first is what is behind the multi-level feedback queue scheduling used in most modern operating systems: you are using past behavior to predict future job lengths, and then scheduling (expected) shortest job first (but preempting the job if it goes much beyond its expected length.) The classic paper is Corbató, F. J., M. M. Daggett, and R. C. Daley, “An experimental time-sharing system”, *AFIPS Conference Proceedings*, Vol. 21, pp. 335-344, 1962.
> 2 votes

---
Tags: operating-systems
---


# Question
Title: Hoare's monitor - what happens after a "signal"
Assume I have producer and consumer in a monitor.

1. The code of the consumer signals the producer and then does something else. I know in a Hoare-style monitor, after signaling, the thread that is signaled wakes up and is is now schedule. What about the other instructions in the consumer after the signal? When will the consumer continue?
2. What if the consumer sends the signal before the producer does the wait? Will the producer be stuck forever?
3. If there is a context switch will the mutex of the monitor be released?

# Answer
> 4 votes
Here's the picture of a Hoare-style monitor from wikipedia user Theodore.norvell:

1. The circles are threads, the rooms off to the sides are various queues. Think of the monitor as being protected by a mutex. Only one thread gets the mutex at a time. Once a thread has the mutex it keeps the mutex until it releases the mutex by (1) waiting (in which case it goes to sleep on a condition variable), (2) signalling (in which case it goes into the queue labeled `s` in the picture or (3) exiting the monitor completely. The scheduling algorithm is given in the wikipedia article. At any point in time the relative priorities to get into the monitor are: (1) the single thread that was most recently signalled, (2) threads in queue `s` (usually `s` is FIFO), (3) threads in queue `e` (the entry queue).
2. If the consumer sends the signal before the producer waits then the producer will be stuck forever. This is sometimes called "the missed wakeup problem." It is avoided by recognizing that you should really be waiting for some *condition* to become true (e.g., "the queue is no longer full"), not waiting for some *condition variable* to get signaled. When the producer is in the monitor (has acquired the mutex) it only waits on the condition variable if it sees that the condition is not currently true. The consumer signals the condition variable every time the condition (state) "queue is full" changes to "queue is not full", whether there is anyone waiting on the condition *variable* or not.
3. If there is a context switch the mutex of the monitor will *not* be released.

---
Tags: operating-systems
---


# Question
Title: How to train a clustering system based on multiple initial clustering results
I got a very hard automatically clustering problem with some training data (500 samples, each with roughly 5-50 classes and 10000-20000 data points in total). What I need to do is to cluster an input into multiple classes (the number of classes is unknown).

So far I had some several clustering algorithms, each gives me an output. I noticed that none of them works sufficient robust over the entire training set, but some works better than others on data with a small number classes, some works better on data with a large number of classes. Meanwhile, some gives me very good cluster results on part of a sample, while performs bad on the other half. Visually speaking, I feel that human should be able to generate a better clustering output by combining all initial outputs of using existing methods. However, it seems that it is hard to translate my human selection logic into codes. Because I know that a good cluster result in my data should be of a shape like a long eclipse, if I see a class in one of my output is very dislike this shape, I know there is something wrong, and if I look up the results of this area in other outputs, I can easily pick those close to my expectations. The actual case is even more complicated, my human decision on choose which class in which output for which region in my data sample uses both relative information among different outputs and prior knowledge on the distribution of tested data points. Please help me, I even donot know where to start.

Any comments and hints are welcome.

Thank you.

---

Thank you for your comments. I see what you said, but it turns out that my ultimate goal is different from what you suggested. I am not interested in finding which clustering output is better than others, but trying to generate a new output based on existing clustering output.

At the first glance, these two goals look compatible: if I can choose one best clustering output for a given set of data points, then I shall be able to repeat this process and apply it iterative to cover the entire dataset, and in this way we can generate a new output, whose solution is composed of different clustering outputs at different regions. However, in my problem this is really not a feasible approach, because I really donot know how to separate an entire dataset into reasonable subsets.

If we know how to do this job properly, the clustering problem can be largely simplified. We can first separate the entire set into nonoverlapping subset, then use an appropriate clustering method for each individual subset, and finally collect all subset clustering outputs as a new output. Meanwhile, it seems that this way of sequential process might be harmful if we make mistakes in the early stage of dividing subsets.

# Answer
> 0 votes
If you can devise an algorithmic way to assess the quality of a clustering output, then one approach would be to run all algorithms on each data set, measure the quality of each, and use the one that is best.

So, you might want to focus on seeing if you codify your human intuition into a way to quantitatively measure the quality of a clustering output.

---

Are you familiar with a Gaussian mixture model? Your description of "long eclipse" makes me think that maybe that is what you are doing with your human intuition.

In particular, a scatterplot of samples drawn from such a a multivariate Gaussian distribution will look roughly like an eclipse. This makes me wonder if each cluster might perhaps be drawn from a multivariate Gaussian distribution (with different parameters for each cluster). If so, a Gaussian mixture model (e.g., using the EM algorithm to fit a Gaussian mixture model to the data) might produce a good clustering. Have you tried using that approach to clustering?

---
Tags: machine-learning, pattern-recognition
---


# Question
Title: Double hashing - probe count probabilities
From TAoCP, Vol. 3 by Knuth we know that *expected (mean)* probe counts for hash tables with open adressing and double hashing collision-resolution are:

* $1 \over 1 - \alpha$ - for unsuccessful search
* ${1 \over \alpha} ln({1 \over 1 - \alpha})$ - for succesful search

Where $\alpha$ is load factor.

Are there expressions for *probabilities* of making exactly $i$ = 1,2,3,.. probes?

# Answer
> 2 votes
As Wandering Logic noted, there are approximate expressions for probabilities of probe count in *unsuccessful* search case in TAoCP, a few pages later expressions for expected probe count:

$1-\alpha$, $\alpha(1-\alpha)$, $\alpha^2(1-\alpha)$, ... - probabilities of making 1, 2, 3, ... probes respectively.

In *successful* search case I derived approx. expressions myself, relying on explanation of expected probe count formula in the book:

$1 - {\alpha\over2}$, ${\alpha\over2} - {\alpha^2\over3}$, ${\alpha^2\over3} - {\alpha^3\over4}$, ...

---
Tags: hash, hash-tables
---


# Question
Title: Finding paths from the result of max flow
Suppose that I have run maxflow algorithm on a graph G and, as a result, I have a set of edges with flow on them. I would like to enumerate all possible sets of paths that comprise the maxflow. That is, each set of paths will make the max flow. But I suspect there could be multiple set of such paths.

# Answer
> -1 votes
Give the edges some value of priority. Once you have run a given maxflox algorithm, reduce the priority of a given edge by the amount of flow which got through the last time. This way edges which have gotten flow through them the last time running the algorithm will not be chosen as the first flow first this time and another way, if any, will be produced.

---
Tags: algorithms, graphs, network-flow
---


# Question
Title: Trying to improve minimax heuristic function for connect four game in JS
I have made a connect four game in JS and currently have a functioning minimax algorithm. The problem I'm having is that it is very, very easy to beat, even with a large depth. This is leading me to believe that I need a better heuristic function, but I cannot come up with much better than what I already have. So, I thought I would ask if anyone has any experience, or just a good idea, for a very good heuristic to use. I would also accept improvement ideas on my current heuristic below. Thank you in advance!

EDIT: I'm going to go ahead and post my total minimax in here (3 functions total), because I have added disjoints and made my 4-in-a-row higher, but my AI is still terrible. I know my 2,3 and 4-in-a-rows work because I tested them, but I can't pin-point why I'm still having trouble even at high depths.

```
    function getBestMove(currBoard,depth,who) {
        var opp;
        //Get opponent for next piece
        if(who == 'a') {
            opp = 'p';
        } else {
            opp = 'a';
        }

        var tBoard = new Array(rows);
        for(var i=0; i<tBoard.length; i++) {
            tBoard[i] = new Array(cols);
        }

        var moves = new Array(aiOpenCols.length);
        //Drop each piece and use minimax function until depth == 0
        for(var i=0; i<aiOpenCols.length; i++) {
            for(var j=0; j<rows; j++) {
                for(var k=0; k<cols; k++) {
                    tBoard[j][k] = currBoard[j][k];
                }
            }
            tBoard = dropPiece(aiOpenCols[i],who,tBoard);
            moves[i] = minimax(tBoard,(+depth - 1),opp,aiOpenCols[i]);
        }

        var bestAlpha = -100000;    //Large negative
        //Use random column if no moves are "good"
        var bestMove;// = Math.floor(Math.random() * aiOpenCols.length);
        //bestMove = +aiOpenCols[bestMove];
        //Get largest value from moves for best move
        for(var i=0; i<aiOpenCols.length; i++) {
            if(+moves[i] > bestAlpha) {
                bestAlpha = moves[i];
                bestMove = aiOpenCols[i];
            }
        }

        bestMove++; //Offset by 1 due to actual drop function
        return bestMove;
    }
    function minimax(currBoard,depth,who,col) {
        //Drop current piece, called from getBestMove function
        currBoard = dropPiece(col,who,currBoard);

        //When depth == 0 return heuristic/eval of board
        if(+depth == 0) {
            var ev = evalMove(currBoard);
            return ev;
        }
        var alpha = -100000;    //Large negative
        var opp;
        //Get opponent for next piece
        if(who == 'a') {
            opp = 'p';
        } else {
            opp = 'a';
        }

        //Loop through all available moves
        for(var i=0; i<aiOpenCols.length; i++) {
            var tBoard = new Array(rows);
            for(var i=0; i<tBoard.length; i++) {
                tBoard[i] = new Array(cols);
            }
            for(var j=0; j<rows; j++) {
                for(var k=0; k<cols; k++) {
                    tBoard[j][k] = currBoard[j][k];
                }
            }
            //Continue recursive minimax until depth == 0
            var next = minimax(tBoard,(+depth - 1),opp,aiOpenCols[i]);
            //Alpha = max(alpha, -minimax()) for negamax
            alpha = Math.max(alpha, (0 - +next));
        }
        return alpha;
    }
    function evalMove(currBoard) {
        //heuristic function
        //AI = # of 4 streaks + # of 3 streaks + # of 2 streaks - # of 3 streaks opp - # of 2 streaks opp
        var fours = checkFours(currBoard,'b');
        //If win return large positive
        if(fours > 0) return 100000;
        var threes = checkThrees(currBoard,'b') * 1000;
        var twos = checkTwos(currBoard,'b') * 10;
        var oppThrees = checkThrees(currBoard,'r') * 1000;
        var oppTwos = checkTwos(currBoard,'r') * 10;

        var scores = threes + twos - oppThrees - oppTwos;

        //If opponent wins, return large negative
        var oppFours = checkFours(currBoard,'r');
        if(+oppFours > 0) {
            return -100000;
        } else {
            return scores;
        }
    }

```

# Answer
Connect 4 is a solved game - under perfect play, white wins. Victor Allis's thesis contains a winning algorithm for white. The game had been solved a few weeks earlier by James D. Allen. Later on, John Tromp came up with a strategy that will win the game from *any* position, if possible, and thus solved the game strongly.
> 7 votes

# Answer
**Disclaimer:**

I'm assuming your minimax works perfectly and your logic of who wins when and when to apply your heuristic how is sound (mainly because you only gave part of your program and partly because it's been a while since I last implemented one of these, so I won't exactly know what to look for) and thus I'm only commenting on your heuristic. Don't assume these parts of your program work, regardless of whatever evidence seems to support this, it helps to be paranoid when it comes to Artificial Intelligence algorithms.

**In terms of weights:**

I presume `checkFours` returns the number of 4-in-a-row's on the board. This should be given a way higher weight, since as soon as there exists one such value, it will mean the end of the game. Thus this is the position the agent should strive to above all else (unless the opponent already won).

A bit of a guess, but my intuition says 3-in-a-row's need to be given a somewhat higher weight in relation to 2-in-a-row's.

**Other than that:**

Two unblocked 3-in-a-row's that don't require the same 4th cell cannot be countered, you will win next turn (unless your opponent wins first). This should also be incorporated into your heuristic, but may already largely be taken care of (except for a different 4th cell requirement) by simply counting the number of 3-in-a-row's (subject to the below). In general, 2/3-in-a-row's requiring the same cells to get to 4 as another 2/3-in-a-row isn't all that helpful.

You also need to count disjoint sets, e.g.:
`xx x` can be thought of as a 3-in-a-row.
`x x` can be thought of as a 2-in-a-row.

You also need to exclude 2/3-in-a-row's that can't get to 4, e.g. `oxxxo` contains a 3-in-a-row, but it's surrounded by opponent-occupied cells, thus you shouldn't count it.

You also shouldn't count a 3-in-a-row as a 3-in-a-row and 2 2-in-a-row's. Since you didn't give your functions, I can't tell if you're doing this.
> 6 votes

---
Tags: algorithms, heuristics, board-games
---


# Question
Title: Distributed problems in Financial Services?
When we talk about distributed computing - it often refers to problems in biology or web search where there is a large quantity of data to process, or email where there is a large number of concurrent users.

Often in financial services, the problem space is OLTP for online banking, or overnight batch processing for summing up EOD totals and reporting.

Is there an example problem in financial services that requires the tools available in distributed computing?

# Answer
There is a lots of problems which might be solved by using distributed algorithms. However most of this problems are so specific that there is no existing general purpose tool for all of them.

Banks and some financial institutions keeps their own solutions hidden and i doubt that they would like to share their ideas and code.

For instance let's consider loans, some as far as I know some banks do long term calculations using Markov process. It is possible to compute is on single machine, but those processes are so complicated that I it just wouldn't be effient to calculate them on single machine.

I also found this presentation, you might want to look at it.
> 0 votes

---
Tags: distributed-systems
---


# Question
Title: Exponential separation between NFAs and DFAs in the presence of unions
For a regular language $L$, its *DFA complexity* is the size of the minimal DFA accepting it, and its *NFA complexity* is the size of the minimal NFA accepting it. It is well-known that there is an exponential separation between the two complexities, at least when the size of the alphabet is unbounded. Indeed, consider the language $L\_n$ over the alphabet $\\{1,\ldots,n\\}$ consisting of all words *not* containing all symbols. Using the Myhill-Nerode theorem it is easy to calculate the DFA complexity $2^n$. On the other hand, the NFA complexity is only $n$ (if multiple initial states are allowed; otherwise it is $n+1$).

Problem 1.65 of Sipser's *Theory of Computation* concerns the *DFA covering complexity* of a language, which is the minimal $C$ such that $L$ can be written as the (not necessarily disjoint) union of languages of DFA complexity at most $C$. The DFA covering complexity of $L\_n$ is only $2$.

> Is there an exponential separation between NFA complexity and DFA covering complexity?

# Answer
Consider the language $M\_n = (L\_n \\#)^\*L\_n$, where $\\#$ is a new symbol.

The NFA complexity of $M\_n$ is $n$ (allowing for multiple initial states). Indeed, here is one NFA having $n$ states accepting $M\_n$. The states are $q\_1,\ldots,q\_n$, all both initial and final. There is a self-loop around $q\_i$ for each $j \neq i$. Furthermore, there are transitions from each $q\_i$ to each $q\_j$ labeled $\\#$. The matching lower bound follows from the DFA complexity of $L\_n = M\_n \cap \\{1,\ldots,n\\}^\*$ being $2^n$.

In contrast, we will show that the DFA covering complexity of $M\_n$ is $2^n$. For the upper bound, consider a DFA whose states are $q\_S$ for $S \subseteq \\{1,\ldots,n\\}$. The states keep track of the letters seen so far: the initial state is $q\_\emptyset$, and $\delta(q\_S,i) = q\_{S \cup \\{i\\}}$. All states other than $q\_{\\{1,\ldots,n\\}}$ are accepting. When seeing $\\#$, if we're in $q\_{\\{1,\ldots,n\\}}$ then we stay put, and otherwise we move to $q\_\emptyset$.

---

Let $\[n\] = \\{1,\ldots,n\\}$. For $S \subseteq \[n\]$, let $w\_S$ consist of all letters in $S$ in order. Let $P$ denote all words over $\[n\]$ containing each letter at most twice, and missing at least one letter.

Suppose that $M\_n = \bigcup\_{i=1}^N L(A\_i)$, where the $A\_i$ are DFAs. We can identify $L\_i := L(A\_i) \cap (P\\#)^\*P$ with a language over the alphabet $P$ in the natural way ($p\_1\\#\ldots\\#p\_\ell$ corresponds to the word of length $\ell$ whose letters are $p\_1,\ldots,p\_\ell$). Say that $x \in P^\*$ is *good for $L\_i$* if for all $p \in P$ there exists $y\_p \in P^\*$ such that $xpy\_p \in L\_i$.

Suppose that no $x$ is good for $L\_i$. Let $\ell \geq 0$. For $0 \leq r \leq \ell$, let $S\_r$ be the set of length $r$ prefixes of words in $L\_i \cap P^\ell$. If $|S\_{r+1}| \> (|P|-1)|S\_r|$ for some $r \< \ell$, then by the pigeonhole principle there is some $x \in S\_r$ such that $xp \in S\_{r+1}$ for all $p \in P$; but then $x$ is good. It follows that $|L\_i \cap P^\ell| = |S\_\ell| \leq (|P|-1)^\ell |S\_0| = (|P|-1)^\ell$.

If no $x$ is good for *any* $A\_i$, then for all $\ell \geq 0$ we have $$ |P|^\ell \leq \sum\_{i=1}^N |L\_i \cap P^\ell| \leq N(|P|-1)^\ell, $$ which is contradictory for large enough $\ell$. Therefore some $x$ is good for some $A\_i$.

Let us identify $x \in P^\*$ with the corresponding word over $\[n\] \cup \\{\\#\\}$. Thus for each $p \in P$ there is $y\_p \in M\_n$ such that $$ x\\# p\\# y\_p \in L(A\_i). $$

We claim that the $2^n$ words $x \\# w\_S$ (we allow $S = \[n\]$) are pairwise inequivalent in the Myhill–Nerode relation of $L(A\_i)$, and so $A\_i$ has at least $2^n$ states.

Indeed, let $S,T$ be two different subsets of $\[n\]$. Assume without loss of generality that $j \in T \setminus S$. Since $w\_S w\_{\[n\] \setminus \\{j\\}} \in P$, by assumption $x \\# w\_S w\_{\[n\] \setminus \\{j\\}} \\# y\_p \in L(A\_i)$, where $p = w\_S w\_{\[n\] \setminus \\{j\\}}$. In contrast, $w\_T w\_{\[n\] \setminus \\{j\\}}$ contains all letters, hence $x \\# w\_T w\_{\[n\] \setminus \\{j\\}} \\# y\_p \notin M\_n$, and so $x \\# w\_T w\_{\[n\] \setminus \\{j\\}} \\# y\_p \notin L(A\_i)$. This shows that the two words $x \\# w\_S, x \\# w\_T$ are inequivalent.
> 10 votes

---
Tags: regular-languages, finite-automata
---


title: Few Big O example

text:
# Question
Title: Few Big O example
I am confusing with the following example.

1. $n^{1.001} + n\log n = \Theta ( n^{1.001} )$, why not $n\log n$?

$c\_1 \le \frac{\log n}{n^{0.001}} \le c\_2 $

OR

$c\_1\le \frac{n^{0.001}}{\log n} \le c\_2$

For me both are same. Means both are giving some constant range for $c\_1$ and $c\_2$.
2. $10 n^3 + 15 n^4 + 100 n^2 2^n = \mathcal O (100n^2 2^n) $
3. $\frac{6 n^3}{ \log n + 1} = \mathcal O(n^3)$

# Answer
Note that $n^{1.001}+n\log n$ is $n\times(n^{0.001}+\log n)$.

Forget about the first factor and focus on $n^{0.001}+\log n$.

The key point is that, for $n$ large enough, $n^{0.001}$ is larger than $\log n$ (do you know/see that?). Hence $n^{0.001}+\log n$ is eventually between $n^{0.001}$ and $2 \times n^{0.001}$, i.e., is in $\Theta(n^{0.001})$.

Then $n^{1.001}+n\log n$ is in $\Theta(n\times n^{0.001})$, i.e., in $\Theta(n^{1.001})$.

On the other hand, for any fixed $c\>0$, $\log n$ is always eventually dwarfed by $c\times n^{0.001}$. Hence $n^{1.001}$ is not $O(n\log n)$.
> 4 votes

# Answer
To add on @phs's great answer:

Note that $$ \lim\_{n\to \infty} \frac{n^{0.001}}{\log n} = \infty$$ while $$ \lim\_{n\to \infty} \frac{\log n}{n^{0.001}} = 0$$ (use L'Hôpital's rule).

For (2), it's quite straight-forward: the term that is "most meaningful", that is, the term that grows the fastest is $n^22^n$. Again, $$\lim\_{n\to \infty} \frac{n^22^n}{n^3} = \lim\_{n\to \infty} \frac{n^22^n}{n^4} = \infty$$

Finally for (3), $O(n^3/\log n)$ would be correct as well, but the "O" notation gives only upper bound, which needs not necessarily be tight. Thus, $$ \frac{6n^3}{\log n+1} \in O(n^3/\log n) \in O(n^3) \in O(n^4) \in O(2^n) \in ...$$
> 3 votes

# Answer
Remember this `dominance rule`.It will always help you when you have to make `Asymptotic comparisons` quickly. I am arranging them in increasing order.

constants \< logn \< nlog n\<$n^2$\<$n^3$......\<$2^n$\<$3^n$.......

The zest is that you classify them into constants,logarithmic,linear and logarithmic and linear ,polynomial and then exponential and so on...

**Answer to your question:** Asymptotic comparision between $n^{1.001}$ and nlogn. Now the first one is polynomial and the second one is linear and logarithmic.Now observe the dominance rule and we can state that $n^{1.001}$ is asymptotically bigger than nlogn . Hope this helps!
> 1 votes

---
Tags: algorithms
---


# Question
Title: Number of rounds in interactive proofs - Arora & Barak
In the web draft of Arora and Barak, "Computational Complexity: A Modern Approach", the way I understand their definition of a round of interaction is that it consists of either the verifier or the prover sending a message. In other sources on the matter, it seems to me that a round consists of both the verifier and the prover sending a message. Could someone clarify which of the definitions is the one that is usually used?

# Answer
It could be that both definitions are used by different authors. Whenever you use the concept of rounds, make sure to tell the reader what you mean by a round. In any case, the two concepts differ by a factor of $2$.
> 5 votes

---
Tags: complexity-theory, interactive-proof-systems
---


# Question
Title: Can the plus operator in regex be replaced by the star operator?
Full disclosure, I'm interested in what this means about transformations on NFAs, but regex expressions seem like a easy way to ask the question.

If you have a regex that uses the plus operator (match one or more) can it, in the general case, be transformed into a regex that uses only the star operator (match zero or more).

Since all regular expressions can be converted into an NFA, and all NFAs can be converted into a regular expression (assuming the alphabet is the unicode character set lol), if it's true for one, it's true for both.

An hand-contrived example regex:

```
<[a-zA-Z]+>

```

A regex recognizing the same language, without the + operator:

```
<[a-zA-Z][a-zA-Z]*>

```

This may seem intuitively true for such a simple example, but I'd like to know for certain that it is generally true. Also, is there an algorithm that can convert an NFA containing a plus-like flow into a star-like flow NFA? Thanks!

# Answer
True. For any regular expression $R$, (the meaning of) $R^+$ equals $R \cdot R^\*$, and conversely, $R^\*$ equals $R^+\mid\varepsilon$ (where $\mid$ here is the choice operator 'or', and $\varepsilon$ the expression matching the empty string).

Thus in any regular expression dialect it suffices to include only one of star and plus without loosing expressibility. Translation of plus into star can be done recursively (inside-out).
> 9 votes

---
Tags: automata, regular-expressions
---


# Question
Title: A framework to capture common variation of sequence alignments
The global alignment problem can be generalized by setting the cost of some boundary gaps to 0.

* Gaps at both end in both strings have 0 cost, then we get the semiglobal alignment.
* Gaps are at the left end of the first string, and right end of second string have 0 cost, then we get overlap alignment.
* If both boundary gaps for the second string has no cost, we get the fitting alignment.

But this can't capture local alignment. Seems strange to let the local alignment to be the odd man out, are there a general (but not too general) framework that captures all the above alignment problems?

# Answer
> 5 votes
Despite the different uses of the algoritms, and the various names, I personally would say this is a single algorithm, with different variations. To make this answer more readable, I will add some details.

The basic algoritm **global alignment** (aka Needleman-Wunsch, below left) compares two strings $x=x\_1\dots x\_m$ and $y = y\_1 \dots y\_n$ (with match/mismatch score $\sigma$ between letters and *negative* gap cost $g$ between letter and missing letter). It is computed using an array $A$ and the recursion $$A\[i,j\] = \max \left\\{\begin{array}{lll}A\[i,j-1\]&+&g\\A\[i-1,j-1\]&+&\sigma(x\_i,y\_j)\\A\[i-1,j\]&+&g\end{array}\right.$$
The starting values along the borders of the matrix are $A\[i,0\]=i\cdot g$ and $A\[0,j\]=j\cdot g$.

The value of the alignment is found in the last cell of the computation, and the alignment itself can be found by tracing back how this maximum value is obtained.

For **local alignment** (aka Smith-Waterman, below right) we need not a complete match but only the optimal value of matches between substrings of $x$ and $y$. That can be obtained by considering only part of the 'full' computation, ignoring any prefix or suffix with a negative value. This requires two changes. First any negative value obtained by the basic recursion is set to $0$, and also we look for a maximum inside the matrix (not the last cell). As any negative values are set to $0$ this effects the boundary values in the same way: they are set to $0$.

The three variants of **semi-global alignment** you mention (including overlap and fitting alignment) are somewhat in the middle of these two, as they carefully select which prefixes and suffixes do not count towards cost. They each follow the basic recursion (allowing negative values). Such alignments follow a path from one border of the matrix to another one. Starting at a left or top border means ignoring prefixes, and setting the corresponding border to $0$. Ending at a right or bottom border (i.e. choosing the maximum value at that side) corresponds to ignoring that suffix.

The two pictures below represent overlap and containment/fitting.

---
Tags: algorithms, strings, bioinformatics
---


title: Making sense of asymptotic notation

text:
# Question
Title: Making sense of asymptotic notation
Let $W(n)$ and $A(n)$ denote, respectively, the worst case and average case running time of an
algorithm executed on an input of size $n$.
Which of the following is *always true*?
(A) $A(n) = \Omega(W(n))$
(B) $A(n) = \Theta(W(n))$
(C) $A(n) = O(W(n))$
(D) $A(n) = o(W(n))$

Answer: (C).

> What do all these options "mean"? I find it hard to reconcile the graphs exemplifying asymptotic notation and abstract situations such as this one.

# Answer
> 2 votes
The easiest way to remember asymptotic notation is to memorize the following table: $$ \begin{array}{cc} o & \< \\ O & \leq \\ \Theta & = \\ \Omega & \geq \\ \omega & \> \end{array} $$ For example, if $f(n) = O(g(n))$ then asymptotically *and up to a constant multiple*, $f(n) \leq g(n)$; formally, there exists a constant $C \> 0$ such that $f(n) \leq Cg(n)$ for large enough $n$. In your case, clearly the average case is at most the worst case, and so $A(n) = O(W(n))$.

---
Tags: asymptotics
---


# Question
Title: Interpretation of "expected cost" of an algorithm
I'm studying randomized algorithms and I sometimes come across results like

> (1) The algorithm has an expected $O(f(n))$ cost.

and

> (2) With constant probability, the cost is bounded by $O(f(n))$.

I'm perfectly fine with statements like (2), but I'm puzzled to what extent a statement like (1) is useful: For certain probability distributions of a random variable, the expected value itself occurs with less than constant probability; for other distributions, it occurs with $1-1/n$ probability. Of course, in many cases, (1) is extended via concentration bounds to show high probability, but in cases where this isn't done, it doesn't seem that a statement on the "expected cost" lets us derive any implications on the actual performance of the algorithm, right?

# Answer
If you have a cost of $1$ with probability one half and $0$ with probability one half, you never reach the expected cost of $\frac{1}{2}$.

But what the expected cost gives you is the average of costs. If you repeat the algorithm and make the average of the cost (after an infinite number of times) you will get an average cost equal to the expected cost.

I hope it's clear ...
> 2 votes

---
Tags: probability-theory, randomized-algorithms
---


# Question
Title: Search for minimum in an array of $k$ monotonic subarrays
Let $A$ be an array of totally ordered elements. A subarray $A\[i..j\]$ is decreasing if $A\[k\]\geq A\[k+1\]$ for all $i \leq k \< j$. It is increasing if $A\[k\]\leq A\[k+1\]$ for all $i \leq k \< j$. It is monotonic if it's either decreasing or increasing.

We call an array is $k$ monotonic if the array can be partitioned into $k$ monotonic subarrays.

> Given $A$ a $k$ monotonic array of length $n$, and the value $k$, find the minimum value in the array.

How many comparisons do we need?

If we let $m$ be the maximum number of times a value occurs in $A$, here are some known cases:

$k=1$, then the array is sorted, the minimum is at either end, a $O(1)$ solution.

$k=2$, then we could solve it in $O(m+ \log \frac{n}{m})$, by take the min of two cases.

* First decrease, then increase, use a $O(m+ \log \frac{n}{m})$ solution. Basically do ternary search unless one find a large segment of equal values, which turns into linear search.
* First increase, then decrease, just check the boundary values.

$k=n$, then a $O(n)$ time linear search is the best possible.

I believe a $\Omega(m+k \log \frac{n}{k})$ lower bound exists, since even if we are given position for $k/2$ partitions of first decreasing then increasing subarrays, $A\_1,\ldots,A\_{k/2}$, we still need to spend $O(m\_i+\log \frac{|A\_i|}{m\_i})$ time to search for the minima in each one of them, where $m\_i$ is the max number of times a value can appear in $A\_i$.

# Answer
> 4 votes
Here are algorithms and matching lower bounds, which fully resolve the situation:

* For $k=1$, you can find the minimum in $O(1)$ time: just examine the two endpoints of the array, $A\[0\]$ and $A\[n-1\]$.
* For $k=2$, you can find the minimum in $O(m + \lg (n/m))$ time, as was mentioned in the question. I prove below that you can't do any faster than this (up to a constant factor).
* For $k\ge 3$, I prove below that finding the minimum takes $\Theta(n)$ time, regardless of $m$ (it takes $\Omega(n)$ time even if you are guaranteed that $m=0$). The trivial algorithm takes $O(n)$ time, so if $k\ge 3$ it is not possible to do better (up to a constant factor) than the trivial algorithm.

Moreover, randomization doesn't help.

---

**Lower bounds.** For $k=2$, consider an array $A$ that is positive and strictly decreasing on $A\[0\ldots r-1\]$, then $A\[r\]=A\[r+1\]=\cdots=A\[r+m-1\]=0$, then is positive and strictly increasing on $A\[r+m\ldots n-1\]$. Now pick an index $i$ satisfying $r \le i \le r+m-1$, and replace $A\[i\]$ with $-1$. Notice that this is an array with $k=2$ monotonic sub-arrays (decreasing-then-increasing). However, even if you were given the value of $r$, you would still have to examine every element of $A\[r\ldots r+m-1\]$ to find the minimum, so any algorithm has to take $\Omega(m)$ time. Moreover, it's easy to show that any algorithm will need $\Omega(\lg n)$ time, so we get a $\Omega(\max(m,\lg n))$ lower bound on the running time. This implies a $\Omega(m + \lg(n/m))$ lower bound as well.

For $k=3$, consider an array that is positive and strictly increasing on $A\[0\ldots n-1\]$, then pick an index $i$ and modify $A$ by replacing $A\[i\]$ with $-1$. This is an array with $k=3$ monotonic sub-arrays, and to find the minimum, you have to scan every element of $A$, so the running time is $\Omega(n)$. Notice that in this example, $m=0$, so knowing (an upper bound on) the value of $m$ does not help you speed things up.

---

If you want a heuristic algorithm for $k=2$ (with no guarantees about worst-case running time), the following randomized algorithm might work well in practice, even though its asymptotic worst-case running time is not any better.

We'll assume the array is decreasing-then-increasing (until you find any evidence to the contrary; if you find evidence that it is decreasing-then-increasing, you can just look at the two endpoints and terminate immediately). We're going to search for the changeover point (which will be the minimum we're looking for). To do that, we'll use ternary search with random selection of the two midpoints.

In particular, we'll use random probing to find two indices $i\<j$ such that $A\[i\],A\[j\]$ are different from each other and from $A\[0\],A\[n-1\]$. Once we have these indices, we can do a case analysis on the relative order of $A\[0\],A\[i\],A\[j\],A\[n-1\]$ and recurse on either $A\[i\ldots n-1\]$ or $A\[0\ldots j\]$. This is a smaller sub-array of expected size $2n/3$.

How long does it take to find two indices $i,j$ that are acceptable? We can start by randomly choosing values for $i$ until $A\[i\]$ is different from $A\[0\]$ and $A\[n-1\]$; then we randomly choose values for $j$ until $A\[j\]$ is different from $A\[0\],A\[i\],A\[n-1\]$. If there are $m$ repeats, then $n-m$ of the entries are unique; thus, each random choice of $i$ (or $j$) has at least a $(n-m)/n$ probability of finding an acceptable value. Consequently, the expected number of random probes done is $O(n/(n-m))$.

Also, we recurse on an array whose expected size is a constant fraction smaller, so we expect to do only $\lg n$ recursions.

Of course, the total running time could still be bad (e.g., with the example I gave above), but it might often be OK if you have some reason to think the absolute worst-case inputs are unlikely.

# Answer
> 1 votes
For $k\>2$, the best algorithm takes $\Omega(n)$ time.

Consider when $A\[i\] = i$ for all $i$ except $i=j$, and $A\[j\]=-1$. In this situation, you can't find the minimum without examining every possible $A\[i\]$.

---
Tags: algorithms, arrays
---


# Question
Title: Difference between symbolic execution and reachability analysis
Now I am confused about symbolic execution (SE) and reachability analysis (RA). As I know, SE uses symbols to execute some code to reach each branch with branch conditions. And RA can be used to find the reachability of each branch, right? When RA is used, we can extract the branch condition for each branch. If so, what's the difference between them? Can they be swift? Are they all static analysis?

# Answer
Generally, reachability analysis is a goal (determine which points in the code are reachable), whereas symbolic execution is a specific algorithmic technique (a tool for analyzing code). You can use symbolic execution for reachability analysis, or for other goals. Conversely, you can use other algorithms for reachability analysis.

Classically, symbolic execution was a static analysis. However, recently it has been widely used in a hybrid static-dynamic analysis: see, e.g., concolic execution. These hybrid methods seem to be very effective, but they are not purely static.
> 4 votes

---
Tags: algorithm-analysis, compilers, program-optimization
---


# Question
Title: "OOD allows ADTs to be created and used."
I just had a CS mid-term and one of the questions was:

> OOD allows ADTs to be created and used.
>
> * True
> * False

I answered false, but my answer was marked as incorrect. I suspect what the question means is "objected-oriented design can be used to implement abstract data types", but if that's what it means it seems very clumsily worded to me. My rationale for answering false was ADTs are conceptual and exist outside of any particular programming paradigm, so "creation" of an ADT is purely a theoretical exercise.

To me it seems like the question is analogous to saying "OOD allows algorithms to be created". You might use OOD in the implementation of an algorithm, but it has nothing to do with its creation.

Would I be right in appealing my mark? My professor is kind of an idiot and I've already corrected him on several other points throughout the term, so I'm trying to avoid antagonizing him if I'm wrong.

# Answer
> 7 votes
First, if this is exactly the sentence on the exam and not your translation, it's ambiguous. It could mean that OOD is one possible way to create and use ADT, or that creating and using ADTs requires OOD.

Furthermore, ADT can mean two things: abstract data type or algebraic data type. The two concepts are completely different but are often confused. An algebraic data type is a type that is defined by its recursive structure, or equivalently by the ways to build an object of that type. An abstract data type is a type that is defined by its properties, with the way to build objects remaining hidden.

The second interpretation — that you need OOD for ADTs — is definitely false. There are programming languages which have no object orientation whatsoever but have ADTs in one sense or the other or both. Standard ML is a prime example: record and sum type definitions provide algebraic data types, while the module system provides abstract data types.

The first interpretation — that ADTs can be implemented with OOD — is contentious, because it depends on terminology that isn't standard. In typical languages that provide objects, you can build algebraic data types: define several implementations of a class to make a sum type, and put multiple fields in a class to make a product type. However this is not intrinsic to object-oriented programming. Regarding abstract data types, most object-oriented languages provide some kind of abstraction facility by hiding the implementation of a class under some interface. However, this isn't intrinsic to OOP: the key feature of objects is inheritance, and you can have inheritance without any abstraction whatsoever.

The question may be making a difference between object-oriented design and object-oriented programming construct, but OO*D* isn't really on the same plane as ADTs.

All in all this is a poorly-worded exam question. The connection between OOD and ADTs is an interesting subject, but the question is not phrased in a meaningful way.

# Answer
> 0 votes
It all depends on your definition of "created."

If by created you mean "defined," then certainly the answer is true. The concept of an Interface in Java or similar languages is an ADT. By giving a name to certain methods which can be called on a type, you have created an abstract data type, which you can use for variables and parameters.

If by created you mean "instantiated," then the answer is false, since you can't instantiate an abstract type. An object will have the type of an ADT. It will have the type of a class which implements an ADT.

# Answer
> 0 votes
No, I don't think you have a leg to stand on.

To the extent that there is any ambiguity in the question, it seems pretty clear to me what is meant. It seems that the claim is: object-oriented languages allow (enable, make possible) you to construct (implement, build) an abstract data type in your code. The answer to that is "true": standard object-oriented languages do allow you to implement and use abstract data types in your code.

Your argument for "false" in particular strikes me as weak. ADTs are not merely theoretical: you can implement an ADT in your code, and people often do. To say that they are "merely" conceptual is to miss the point. If I said "A hammer allows me to construct a chair by nailing together pieces of wood", and you replied "false: the notion of a chair is merely conceptual", we'd all look at you funny. I think about the same applies here.

Object-oriented design is relevant to ADTs. To the extent that you think of object-oriented design as recommending you build encapsulated objects, then that encapsulation basically means you are building an ADT.

I would not recommend appealing your grade on this question. Save your appeals for situations where you have a more reasonable case.

---
Tags: programming-languages, object-oriented, abstract-data-types
---


# Question
Title: Use Rice's theorem to show that the language of optimisable Turing machines is undecidable
I have an assignment to do and I'm quite stuck with the following question :

> Use Rice's theorem to show that
>
> $ \qquad L' = \\{ \langle M \rangle \mid \\; (\exists \text{ TM } M') \\; \[ L(M') = L(M) \text{ and } M' \text{ has less than 29 states} \] \\}$
>
> is undecidable.

I have absolutely no idea how to proceed.

Would someone be kind enough to, at least, give me some clues?

**EDIT**

First, I wrote the question wrong. It is now '$M'$ has less than 29 states' (not 'steps')."

Here's what I'm thinking after more reading and consulting other students at school.

Rice's theorem :

> $L = \\{ \langle M \rangle \mid L(M) \text{ has some property } P \\}$ where :
>
> 1. $P$ is non-trivial, i.e. there exists at least one machine $M\_1$ such that $\langle M\_1 \rangle \in L$, and at least one machine $M\_2$ such that $\langle M\_2 \rangle \not \in L$.
> 2. $P$ is indeed a property of the language of TMs, i.e. whenever $L(M\_a) = L(M\_b)$, we have $\langle M\_a \rangle \in L$ if and only if $\langle M\_b \rangle \in L$.
>
> Then, $L$ is undecidable.

So here, the property is "$M'$ has less than 29 states".

We can show that this property is non-trivial.

Let's take the language "abcdefghijklmnopqrstuvwxyz0123456789" (only one string is accepted). We can build a TM $M$ this way :

-\> Enter in state $q\_0$

-\> In $q\_0$ : if you read "a", proceed to $q\_a$, otherwise go to $q\_{reject}$ and halt.

-\> In $q\_a$ : if you read "b", proceed to $q\_{ab}$, otherwise go to $q\_{reject}$ and halt.

$\vdots$

-\> In $q\_{abcdefghijklmnopqrstuvwxyz012345678}$ : if you read "9" go to $q\_{accept}$, otherwise go to $q\_{reject}$ and halt.

So here we got 3 "basic states" : $q\_0$, $q\_{reject}$ and $q\_{accept}$ and we have $|abcdefghijklmnopqrstuvwxyz0123456789| - 1$ states (there is no $q\_{abcdefghijklmnopqrstuvwxyz0123456789}$ because when we read "9" at the end, we go to $q\_{accept}$). So that's 26 + 10 - 1 = 35 states. We have a total of 35 + 3 = 38 states.

Unless I am wrong, there can't be a TM $M'$ that can test wether a string $w$ belongs to that language without having *at least* 38 states !

So the property "$M'$ has less than 29 steps" is non-trivial as there is at least one TM that respects it, and at least one that does not.

Now, $P$ is indeed a property of the language of TMs, because any two machines $M\_1$ and $M\_2$ such that $L(M\_1) = L(M\_2)$ implies :

$\langle M\_1 \rangle \in L' \Leftrightarrow L(M\_1) = L(M\_2) \Leftrightarrow \langle M\_2 \rangle \in L'$.

(I know there is at least one missing clause in there, but I can't figure how to write it, it's got something to do with that "$M'$ has less than 29 steps")

So, according to Rice's theorem, $L'$ is undecidable.

# Answer
> 3 votes
There is some TM which is not in $L'$, and there is some TM which is in $L'$. So the definition of $L'$ determines a nontrivial property on r.e. languages and so by Rice's theorem it is not decidable.

---
Tags: computability, undecidability, rice-theorem
---


# Question
Title: Average number of slots needed in slotted-Aloha
Consider 2 stations that share the same bus. Both stations are perfect synchronized each other and when they have packets to transmit, they are starting the transmission in the beginning of a same slot. Transmission is as follows: when base $i$ has a packet to transmit attempts with probability $p\_i, i=1,2$. Different stations make the random selection independently and corresponding probabilities are $p\_1=0.5, p\_2=0.25$. Initially the station 1 has 2 packets for station 2, while the other has no package.

What is the average number of slots in order all packets reach their destinations? Then if station 1 has 1 packet for station 2 and station 2 has 1 packet for station 1, what is the average number of slots? We are using slotted-Aloha.

# Answer
> 2 votes
The protocol you are describing is most probably CSMA or slotted ALOHA.

As @wece mentioned, you need also to specify what you do in case of conflict (this is also the main difference between the above mentioned protocols). I would assume that a station sends regardless of the link-status and that a station will retransmit in the next slot with same probability $p\_{i}$ in case of collision. This is basically what happens in slotted ALOHA, just that you have individual transmission probabilities for you stations.

You would not refer to the specified protocol as TDM (time division multiplexing), because the channel access is *non-deterministic* and *non-repetitive*, although you do have fixed time slots.

To your calculative questions:

**1)** Station 1 has 2 packets to send:
The probability that 1 successfully transmits to 2 is:

$$P(transmit\_{1,2})=P(send\_{1})\*(1-P(send\_{2}))$$

Since we have no packets at station 2, $P(send\_{2})$ is zero. This is repeated over potentially many slots, always with probability $p\_{1}=0.5$ that 1 will send in a slot. Note that this is the same problem as a simple coin toss. The expected number of sends in n tries (if we had infinite packets at 1) is $E=n\*p$. Let's look at only one packet: We only want to know how many tries it takes on average. We can therefore write: $n=E/p$. This yields 2 tries on average for station 1. We can thereafter reason exactly the same way for the second package, because there is *no statistical dependence* between the events. We thereby obtain #tries = 4. (The same problem for station two would yield 4 + 4 tries.)

**2)** Now two stations want to send. We therefore have ($\neg$ means *not*):

$$ P(send\_{1}\\&send\_{2}) = \frac{1}{2}\*\frac{1}{4}=\frac{1}{8} $$ $$ P(send\_{1}\\&\neg send\_{2}) = \frac{1}{2}\*\frac{3}{4}=\frac{3}{8} $$ $$ P(\neg send\_{1}\\&send\_{2}) = \frac{1}{2}\*\frac{1}{4}=\frac{1}{8} $$ $$ P(\neg send\_{1}\\&\neg send\_{2}) = \frac{1}{2}\*\frac{3}{4}=\frac{3}{8} $$

Only the middle two give a first correct transmission. As in the previously calculation we see that we need 2 tries (or time slots) on average for this to happen. Once this happened, we are back to the first problem, sending one packet with the other station being quiet.

However, at this point it could have been the first or the second station which sent the first packet. We therefore need to account for it: We have 3/4 cases where it was station 1 and 1/4 cases where it was station 2 which transmitted correctly in the first step. This means we can simply add up the number of tries as: $$\\#tries\_{first-packet} + \\#tries\_{second-packet-from-1}\*p\_{second-packet-at-1} + \\#tries\_{second-packet-from-2}\*p\_{second-packet-at-2}$$ $$= 2 + 2 * \frac{1}{4} + 4 * \frac{3}{4} = 5.5$$

---
Tags: probability-theory, computer-networks
---


# Question
Title: Is developing an OCR considered a research project?
Is developing an optical character recognition system for an alphabet which has no previous ocr considered a reputable conference or journal worthy research project, given the fact that there are so many commercial ocr system? Though, lots of conference proceeding and journal entries shows up when googled, but most of them are old and are about performance of a specific algorithm. There are also research on ocr for cursive alphabets which are hard to segment, like Arabic. The alphabet I am developing ocr for is of Indic origin and cursive as my final year undergraduate thesis. So, I'm wondering if it's a good research project.

# Answer
> 2 votes
Rifat, you have to ask your supervisor. If (s)he accepts, then go for it, otherwise go back to the drawing board.

If this is, as you say, an area for which an OCR does not yet exist, then it sounds perfectly fine for an undergraduate project, but do not expect any reputable conference or journal to publish your results.

---
Tags: computer-vision, pattern-recognition
---


title: Where are M-Trees applied in practice?

text:
# Question
Title: Where are M-Trees applied in practice?
My similarity search seminar topic are M-trees. I would like to give some examples about where they are practically applied, but I can't find anything googling.

Does someone know if M-trees are still used and what for? I am interested in answers regarding both practice and applied research.

# Answer
> 4 votes
M-trees appear in this survey of image retrieval techniques (emphasis added):

> In Berretti et al. \[2000\], curves are represented by a set of segments, or tokens, whose feature representations (curvature and orientation) are *arranged into a metric tree \[Ciaccia et al. 1997\] for efficient shape matching and shape-based image retrieval.*

# Answer
> 3 votes
Digital libraries, databases and the WWW contain huge amounts of information. Any multimedia is first characterized by relevant features; think of shapes, textures, patterns, colors, loudness and harmonicity for sounds, and so on. There's applications everywhere, for example in image processing, geography systems, medical applications, and biomedicine. See the introductions in \[1\] and \[2\].

---

\[1\] Ciaccia, P., Patella, M., Rabitti, F., & Zezula, P. (1997, June). Indexing Metric Spaces with M-Tree. In SEBD (Vol. 97, pp. 67-86).

\[2\] Zhou, X., Wang, G., Yu, J. X., & Yu, G. (2003, January). M+-tree: a new dynamical multidimensional index for metric spaces. In Proceedings of the 14th Australasian database conference-Volume 17 (pp. 161-168). Australian Computer Society, Inc.

---
Tags: data-structures, search-trees, applied-theory
---


title: Transmission (Store and Forward) Delay

text:
# Question
Title: Transmission (Store and Forward) Delay
The Kurose & Ross book uses "store-and-forward delay" as a synonym for the transmission delay of a packet over a network link.

As a newcomer to computer networks, it isn't immediately obvious to me how these two terms are synonymous. My current understanding is that if not for the store-and-forward behavior of packet switches, the transmission delay of a link would be negligible as it would be pipelined with the propagation delay of the previous link; i.e. as the bits propagate across Link A, they are transmitted and stream into Link B. However, due to store-and-forward, no bits are transmitted onto Link B before all the bits have crossed Link A, and hence, we need to add the transmission delay of Link B.

Is this correct?

# Answer
Transmission delay refers to the time it takes to push the bits of data onto the link, and is given by $L/R$, where $L$ is the amount of data and $R$ is the rate. Propagation delay refers to the time it takes for a bit, once on the link, to reach the destination. The propagation delay is given by $d/s$, where $d$ is the distance the data must travel and $s$ is the speed at which data travels through the medium. Other kinds of delay include the processing and queuing delays.

Store-and-forward refers to the fact that most routers work by receiving entire chunks of data before forwarding any part of the chunk. Some store-and-forward is of course necessary, supposing that the forwarding information is contained in the body of the message, as is the case in any packet-switched system. Store and forward can actually be avoided, for the most part, in circuit-switched networks, or by using something referred to as wormhole routing. However, for the most part, entire messages are received from the transmitting protocol (link-layer for switches and network-layer for routers) before transmission continues, so that you can do things like verifying checksums/CRCs, etc.

Your understanding looks basically sound. If it weren't for store-and-forward, and neglecting both processing and queuing delays, the end-to-end delay would be the sum of propagation delays plus $L/min\\{R\\}$, where $min\\{R\\}$ is the slowest transmission rate of any link along the path.

Consider the following example. You want to send a dozen eggs to your friend in the next room. There is a large conveyor belt between you and your friend and it moves any items you place onto it at 1 m/s. Your friend is 10 m away, and so the propagation delay is 10 s. Using both hands, you are able to take eggs from the carton and place them on the belt at a rate of 2 eggs per second. The transmission delay is 6 seconds. Your friend finishes receiving all the eggs exactly 6 + 10 seconds after you began transmitting eggs.

Even though the propagation delay is larger than the transmission delay, you must still account for the transmission delay. To see what I say at the end of my answer, consider sending the dozen eggs over two conveyor belts. Assume the guy moving eggs between conveyor belts can move them at a rate of 1.5 eggs/second (and that he has an unbounded wait queue for arriving eggs). If we store and forward, the guy will let all 12 eggs fall into his queue (a basket, maybe) and then put them on the next belt; his transmission delay is added to the total. If he doesn't store and forward, and moves eggs along as they become available, assuming the same propagation delay on both belts... (1) I put the 12th egg on the first belt at t=6 ; the last egg arrives to him at t=16 ; he has put 9 eggs on the second belt and now has 3 in his basket; it takes him 2 more seconds to finish putting these on the second belt, so the last egg makes it onto the second belt at t=18 ; and the last egg arrives at the destination at t=28 . We see that this is the sum of propagation delays plus the larger transmission delay, as claimed. Using store-and-forward, the delay is 34 s.
> 2 votes

# Answer
I haven't read that book, so I may be off the mark.

Usually the transmission delay on a direct link is negligible compared with the processing delay at the endpoints and at each hop. In concrete scenarios, going via a geosynchronous satellite is the only way you have significant transmission delays on a link (about 0.2s to go up and down).

So when you have a network link that consists of a chain of direct links with a router at each hop, the total transmission delay is the sum of the store-and-forward delays on the routers. Strictly speaking, it's that plus the total length of the link divided by the speed of light (if the signal propagates at light speed), but that second part is usually negligible.
> 2 votes

---
Tags: computer-networks
---


title: Parse Tree building

text:
# Question
Title: Parse Tree building
I am trying to learn how to build parse trees. This is a very simple example as I am hoping I can catch on to the concept. $\mathtt{y=x+z}$

Wouldn't this simply require $\mathtt{(term) = (term) + (term)}$? I'm not sure how to express my answer on here but would it only require one branch due to the $\mathtt{=}$ sign?

# Answer
I would say it's

since you first add x and z and then assign the result to y.
> 2 votes

# Answer
Have you considered the Shunting-Yard Algorithm? If not, you may want to give it a shot.
> 1 votes

---
Tags: parsing
---


# Question
Title: How to show that a function is not computable? How to show a language is not computably enumerable?
I know that there exists a Turing Machine, if a function is computable. Then how to show that the function is *not* computable or there aren't any Turing Machine for that. Is there anything like a Pumping lemma?

Similarly, how can we show a language is *not* recursively enumerable?

# Answer
> 60 votes
Before I answer your general question, let me first take a step back, give some history background, and answer a preliminary question: Do non-computable functions even exist?

<sup> \[notational note: we can relate any function $f$ with a language $L\_f=\\{ (x,y) \mid y=f(x) \\}$ and then discuss the decidability of $L\_f$ rather than the computability of $f$\]</sup>

---

## Undecidable languages *do* exist

There are some languages that no Turing machine can decide. The argument is simple: there are "only" countably many $(\aleph\_0)$ different TMs, but uncountably many $(\aleph)$ different languages. Thus there are at most $\aleph\_0$ decidable languages, and the rest (infinitely many) are undecidable. Further reading:

In order to put our hand on a specific undecidable language, the idea is to use a technique named *diagonalization* (Georg Cantor, 1873) which was originally used to show that there are more real numbers than integers, or in other words, that $\aleph \> \aleph\_0$.

The idea for constructing the first undecidable language is simple: we list all Turing machines (which is possible since they are recusively enumerable!), and create a language that disagrees with each TM on at least one input.

$$ \begin{array}{c|ccccc} & \varepsilon & 0 & 1& 00 & \cdots \\ \hline M\_1 & \color{red}{1} & 0 & 1 & 0 & 1 \\ M\_2 & 0 & \color{red}{1} & 0 & 0 & 0 \\ M\_3 & 0 & 0 & \color{red}{0} & 1 & 0 \\ \vdots & & & & \ddots & \end{array} $$

In the above, each row is one TM and each column is one input. The value of the cell is 0 if the TM rejects or never halts, and 1 if the TM accept that input. We define the language $D$ to be such that $D$ contains the $i$-th input if and only if the $i$-th TM does not accept that input.

Following the table above, $\varepsilon \notin D$ since $M\_1$ accepts $\varepsilon$. Similarly, $0\notin D$, but $1\in D$ since $M\_3$ does not accept $1$.

Now, assume $M\_k$ decides $D$ and look up line $k$ in the table: if there is $1$ in the $k$-th column, then $M\_k$ accepts that input *but it is not in $D$*, and if there is a $0$ there, the input is in $D$ but $M\_k$ does not accept it. Therefore, $M\_k$ doesn't decide $D$, and we reached contradiction.

Now for your question. There are several ways to prove that a language is undecidable. I'll try to touch the most common ones.

### 1. Direct proof

The first method, is to directly show that a language is undecidable, by showing that no TM can decide it. This ususally follows the diagonalization method shown above.

**Example.**

> Show that the (complement of the) diagonal language $$\overline {L\_D} = \\{ \langle M \rangle \mid \langle M \rangle \notin L(M) \\}$$ is undecidable.

**Proof.**
Assume $\overline {L\_D}$ is decidable, and let $M\_D$ be its decider. There are two cases:

1. **$M\_D$ accepts $\langle M\_D \rangle$**: but then, $\langle M\_D \rangle \in L(M\_D)$ so $\langle M \rangle \notin \overline {L\_D}$. So this can't happen if $M\_D$ decides $\overline {L\_D}$.
2. **$M\_D$ does not accept $\langle M\_D \rangle$**: so $\langle M\_D \rangle \notin L(M\_D)$ and thus $\langle M \rangle \in \overline {L\_D}$. But if it is in $L\_D$, $M\_D$ should have accepted it, and we reached contradiction again.

### 2. Closure properties

Sometimes we can use closure properties to show some language is not decidable, based on other languages we already know not to be decidable.

Specifically, if $L$ is not decidable (we write $L\notin R$), then also its complement $\overline{L}$ is undecidable: if there is decider $M$ for $\overline{L}$ we could just use it to decide $L$ by accepting whenever $M$ rejects and vice versa. Since $M$ always halts with an answer (it is a decider), we can always invert its answer.

Conclusion: The diagonal language ${L\_D} = \\{ \langle M \rangle \mid \langle M \rangle \in L(M) \\}$ is undecidable, $L\_D \notin R$.

A similar argument can be applied by noting that if both $L$ and its complement $\overline{L}$ are recursively enumerable, both are decidable. This is particular useful if we want to prove that a language is not recursively enumerable, a strong property than undecidability.

### 3. Reducing from an undecidable problem

Usually, it's quite difficult to directly prove that a language is undecidable (unless it is already constructed in a "diagonal" fashion). The last and most common method for proving undecidability is to use another language which we already know to be undecidable. The idea is to reduce one language to another: to show that if one is decidable, then the other must also be decidable, but one of them is already known to be undecidable which leads to the conclusion that the first one is also undecidable. Read more about reductions in "What are common techniques for reducing problems to each other?".

**Example.**

> Show that the diagonal language $$HP = \\{ \langle M,x \rangle \mid M \text{ halts on } x \\}$$ is undecidable.

**Proof.**
We know that $L\_D$ is undecidable. We reduce $L\_D$ to $HP$ (this is denoted $L\_D \le HP$), that is, we show that if $HP$ was decidable we could use its decider to decide $L\_D$, which is a contradiction.

The reduction works by converting a candidate $w$ for $L\_D$ (i.e. an input for any potential decider/acceptor for $L\_D$) to a candidate $w'$ for $HP$ such that $w\in L\_D$ if and only if $w' \in HP$. We make sure that this conversion is computable. Thus, deciding $w'$ tells us whether or not $w\in L\_D$, so if we can decide HP we would be also able to decide $L\_D$

The conversion is as follows. Take some $w=\langle M \rangle$, and output $w'=\langle M' , \langle M \rangle\rangle$,² where $M'$ is a TM that behaves just like $M$, but if $M$ rejects, then $M'$ goes into an infinite loop.

Let's see that $w,w'$ satisfy the requirements.
If $w\in L\_D$, it means that $M$ *halts* and accepts the input $\langle M\rangle$. Therefore, $M'$ also halts and accepts the input $\langle M\rangle$. Thus, $\langle M', \langle M\rangle \rangle \in HP$.
On the other hand, if $w\notin L\_D$ then $M$ either rejects or never halts on $\langle M\rangle$. In both cases $M'$ will go into an infinite loop on $\langle M\rangle$. Thus, $\langle M', \langle M\rangle \rangle \notin HP$, and we are done showing that $w\in L\_D$ if and only if $w'\in HP$, and have thus shown that $HP\notin R$.

Further reading: many examples for reductions and proving undecidablility of languages can be found via the tag.

---

1. There are some more restriction on the reduction to be valid. The conversion itself must be *computable*, and well defined for any input.
2. An input of $HP$ looks like $\langle M,x\rangle$, where $M$ is a TM and $x$ is some string. So here we choose the string $x$ to be an encoding of the machine $M$, which is just some string..

---

### 4. Rice's Theorem

*"So every time we wish to prove $L$ is undecidable, we need to reduce $L\_D$ (or $HP$) to it? Isn't there any shortcut?"*

Well, in fact, there is. This is Rice's Theorem.

The theorem says that many languages that have a certain structure, are undecidable. Because all these languages have this certain structure, we can do the reduction once and apply it to any language that admits a similar structure.

The theorem is formally stated in the following way,

> **Theorem (Rice).** Given a *property* $\emptyset \subsetneq S \subsetneq RE$, the following language $L\_S$ is undecidable $$ L\_S = \\{ \langle M \rangle \mid L(M) \in S \\} $$

The set $S$ is a subset of languages in $RE$; we call it a property because it describes a property of the accepted language $L(M)$. All the TMs whose language satisfies this property belong to $L\_S$.

For instance, $S$ can be the property that the accepted language $L(M)$ contains exactly two words:

> $$S\_2 = \\{ L \mid |L| =2 , L \in RE\\}.$$ In this case $L\_{S\_2}$ is the set of all TMs whose language consists of exactly two words: $$L\_{S\_2} = \\{\langle M \rangle \mid L(M) \in S\\} = \\{\langle M \rangle \mid |L(M)|=2\\}.$$

The property can be very simple, but it cannot be **all** the RE languages, or **none** of the RE languages. If $S=\emptyset$ or $S=RE$ then the property is said to be *trivial*, and the induced $L\_S$ is computable. An example for a simple $S$ is one the contains only a single language, say $S\_{complete}=\\{ \Sigma^\*\\}$. Note that although $S$ contains only a single language, there are infinitely many machines $M$ whose language is $\Sigma^\*$, so $L\_{S\_{compete}}$ is infinite, and undecidable.

---

The theorem is very powerful to prove undecidability of many languages.

**Example.**

> The language $L\_\emptyset = \\{ \langle M \rangle \mid M \text{ never reaches the accepting state} \\}$, is undecidable

**Proof.**
We can write $L\_\emptyset$ as $\\{ \langle M \rangle \mid L(M)=0 \\}$, that is $L\_\emptyset=L\_S$ for the property $S=\\{ L \in RE, |L|=0\\}$. This is a non-trivial property (it includes the language $L=\emptyset$, but does not include, for instance, the language $L=\\{1, 11, 111,\ldots\\}$. Therefore, by Rice's Theorem, $L\_\emptyset$ is undecidable.

---

We now prove the theorem. As mentioned above, we are going to show a reduction from $HP$ to $L\_S$ (for any arbitrary non-trivial $S$).

**Proof.**
Let $S$ be a non-trivial property, $\emptyset \subsetneq S \subsetneq RE$. We show $HP \le L\_S$, that is, we reduce $HP$ to $L\_S$ so that if we can decide $L\_S$ we will be able to decide $HP$ (which we know to be impossible, therefore, $L\_S$ cannot be decidable). In the proof below we assume that the empty language is not part of $S$, that is $\emptyset \notin S$. (if the empty language is in $S$, an equivalent proof works on the complement property $\overline S = RE \setminus S$, I'll omit the details). Since $S$ is nontrivial, it includes at least one language; let's call that language $L\_0$ and assume $M\_0$ is a machine that accepts $L\_0$ (such machine exists, since $S$ includes only languages in RE).

Recall that in such a reduction (See section 3 above), we need to show how to convert an input $w$ for $HP$ into an input $w'$ for $L\_S$ so that $$ w\in HP \quad \text{ if and only if }\quad w' \in L\_S$$

Let $w=(\langle M \rangle, x)$, we convert it into $w'=\langle M' \rangle$ where the description of the machine $M'$ (on an input $x'$) is the following:

1. Run $M$ on $x$.
2. If Step 1 above halts, run $M\_0$ on $x'$ and accept/reject accordingly.

We see that this conversion is valid. First note that it is simple to construct the description of $M'$ given $w=(\langle M \rangle, x)$.

If $w\in HP$, then $M$ halts on $x$. In this case, $M'$ proceeds to step 2, and behaves just like $M\_0$. Therefore its accepted language is $L(M')=M\_0\in S$. Therefore, $w'=\langle M' \rangle \in L\_S$.
If $w\notin HP$ then $M$ loops on $x$. This case, $M'$ loops on any input $x'$ — it gets stuck in step 1. The language accepted by $M'$ in this case is empty, $L(M')=\emptyset \notin S$. Therefore, $w'=\langle M' \rangle \notin L\_S$.

### 4.1 The Extended Rice Theorem

Rice's theorem gives us an easy way to show that a certain language $L$ that satisfies certain properties is undecidable, that is, $L \notin R$. The extended version of Rice's theorem allows us to determine whether the language is recursively-enumerable or not, that is, determines whether $L \notin RE$, by checking if $L$ satisfies some additional properties.

> **Theorem (Rice, extended).** Given a property $S \subseteq RE$, the language $$ L\_S = \\{ \langle M \rangle \mid L(M) \in S \\} $$ is recursively-enumerable ($L\_S \in RE$) **if and only if** all the following three statements jointly hold
>
> 1. For any two $L\_1, L\_2 \in RE$, if $L\_1 \in S$ and also $L\_1 \subseteq L\_2$ then also $L\_2 \in S$.
> 2. If $L\_1\in S$ then there exists a finite subset $L\_2 \subseteq L\_1$ so that $L\_2 \in S$.
> 3. The set of all *finite* languages in $S$ is enumerable (in other words: there is a TM that enumerates all the finite languages $L\in S$).

**Proof.**
This is an "if and only if" theorem, and we should prove both its directions. First, we show that if one of the conditions (1,2,3) does not hold, then $L\_S \notin RE$. After that we will show that if all three conditions hold simultaneously, then $L\_S \in RE$.

*If (3) does not hold, then $L\_S \notin RE$*.
Let's assume that $L\_S \in RE$, and we'll see that we have a way to accept any finite languages in $S$ (and thus, the set of all these languages is RE), thus condition (3) holds and we reach a contradiction. How to decide if a finite $L$ belongs to $S$ or not? Easily – we use the description of $L$ to construct a machine $M\_L$ that accepts only the words in $L$, and now we run the machine of $L\_S$ on $M\_L$ (remember - we assumed $L\_S\in RE$, so there is a machine that accepts $L\_S$!). If $L\in S$ then $\langle M\_L \rangle \in L\_S$ and since $L\_S\in RE$, its machine will say yes on the input $\langle M\_L \rangle$, and we are done.

*If (1) does not hold, then $L\_S \notin RE$*.
We assume that $L\_S \in RE$ and we'll show that we have a way to decide $HP$, leading to a contradiction.

Because condition (1) doesn't hold, there is a language $L\_1 \in S$ and a superset of it, $L\_2 \supseteq L\_1$ so that $L\_2 \notin S$. Now we are going to repeat the argument used in Section 4 to decide $HP$: given an input $(\langle M \rangle,x)$ for $HP$, we construct a machine $M'$ whose language is $L\_1$ if $(\langle M \rangle,x)\notin HP$ or otherwise, its language is $L\_2$. Then, we can decide $HP$: either $M$ halts on $x$, or the RE-machine for $L\_S$ accepts $M'$; we can run both in parallel and are guaranteed that at least one will halt.

Let's give the details of constructing $M'$ (on input $x'$):

1. Do the following in parallel:
1.1 run $M$ on $x$.
1.2 run the machine of $L\_1$ on $x'$
2. If 1.2 halts and accepts - accept.
3. If 1.1 halts: run the machine of $L\_2$ on $x'$.

Why does this work? If $(\langle M \rangle,x)\notin HP$ then 1.1 never halts, and $M'$ accepts exactly all the inputs that are being accepted at step 1.2, so $L(M')=L\_1$. On the other hand, if $(\langle M \rangle,x)\in HP$ then, at some point step 1.1 halts and $M'$ accepts exactly $L\_2$. It may happen that $1.2$ accepts beforehand, but since $L\_1 \subseteq L\_2$, this doesn't change the language of $M'$ in this case.

*If (2) does not hold, then $L\_S \notin RE$*.
Again, we will assume $L\_S\in RE$ and show that $HP$ becomes decidable, which is a contradiction.

If condition (2) doesn't hold, then there exists $L\_1\in S$, all its finite subsets $L\_2 \subseteq L\_1$ satisfy $L\_2 \notin S$ (note that $L\_1$ must be infinite, since $L\_1\subseteq L\_1$). As in the above, in order to decide $HP$ for a given input $(\langle M \rangle,x)$, we construct a machine $M'$ whose language is $L\_1$ if $(\langle M \rangle,x)\notin HP$ and some finite $L\_2$ otherwise. The contradiction follows in a similar way as above.

The construction of this machine is quite similar to the previous $M'$ we constructed. The machine $M'$ (on input $x'$) does:

1. Runs $M$ on $x$ for $|x'|$ steps.
2. If $M$ halts during step 1 – reject
3. Otherwise, run the machine of $L\_1$ on $x'$.

It holds that, if $(\langle M \rangle,x)\in HP$, then at some point, say after 1000 steps, $M$ halts on $x$. Therefore, step 1 will halt on (and reject) any input $x'$ of length $\>1000$. Therefore, in this case, $L(M')$ is **finite**. Also note that $L(M') \subseteq L\_1$, and in particular, by our assumptions on the invalidity of condition (2), we have that $L(M) \notin S$.

On the other hand, if $(\langle M \rangle,x)\notin HP$, then step 1 never halts, and we never reject at step 2. In this case it is easy to see that $L(M)=L\_1$ and in particular, $L(M)\in S$.

We are left to show the other direction of the extended theorem. That is, we need to show that if all the conditions (1,2,3) hold, then we have a TM that accepts $L\_S$, that is, $L\_S \in RE$. In other words, we need to show a machine $M\_S$ so that for any input $\langle M \rangle$ for which $L(M) \in S$, the machine accepts this input, $M\_S(\langle M \rangle) \to \textsf{accept}$.

Here is how the machine $M\_S$ behaves (on input $\langle M \rangle$):

1. Let $M\_{\text{enum }S}$ be the machine that enumerates all the finite languages in $S$, guaranteed by condition (3).
2. Run the following in parallel (by dovetailing, see e.g., this and this) for $i=1,2,...$
2.1 Run $M\_{\text{enum }S}$ until it outputs the language $L\_i$
2.2. Check if $M$ accepts all the words of $L\_i$ (run $M$ on these words, again in parallel).
2.3. If for some $i$, $M$ accepts all the words of $L\_i$ – accept.

Why does it work? If $L(M) \in S$ then it has a finite subset $L\_j \in S$, and once $M\_{\text{enum }S}$ outputs that subset, step 2.2/2.3 will find that $M$ accepts all the words in that language and accept.

On the other hand, if $L(M) \notin S$ it cannot be accepting all the words in $L\_i$ for any $i=1,2,...$. Indeed, by condition (1), any $L' \supseteq L\_i$ is also in $S$, so if $M$ accepts all the words in $L\_i$ for some $i$, then $L(M)\supseteq L\_i$ and thus $L(M) \in S$, in contradiction.

---

Finally, note that the following is a simple (and very useful) corollary of the above:

> **Corollary (Rice, extended).** Given a non trivial property $S \subsetneq RE$, so that $\emptyset \in S$, the language $$ L\_S = \\{ \langle M \rangle \mid L(M) \in S \\} $$ is not recursively-enumerable, that is, $L\_S \notin RE$.

# Answer
> 13 votes
One useful tool is **Rice's theorem**. Here is what it says:

> Let $\emptyset \subsetneq P \subsetneq \mathcal{P}$ a non-trivial set of partially computable unary functions and $\varphi$ a Gödel numbering of $\mathcal{P}$. Then the index set of $P$
>
> $\qquad I\_P = \\{ i \in \mathbb{N} \mid \varphi\_i \in P \\}$
>
> is not recursive.

You find it also expressed in terms of Turing machines encodings (or any other Turing-complete programming language), i.e. $I\_P = \\{ \langle M \rangle \mid M\ \mathrm{TM}, f\_M \in P \\}$; here $\langle . \rangle$ defines a Gödel numbering.

That is, you can use Rice's theorem to prove such sets $S$ non-recursive which are index sets of non-trivial function sets (or such is reducible to $S$).

Note that there is an extension that can be used to show that certain index sets are not recursively enumerable.

### Example

Let $\varphi$ a Gödel numbering. Consider the set of naturals

$\qquad A = \\{ i \in \mathbb{N} \mid \varphi\_i(j) = 1 \text{ for all } j \in 2\mathbb{N} \\}$.

Now since for $P = \\{ f \in \mathcal{P} \mid f(j) = 1 \text{ for all } j \in 2\mathbb{N} \\}$

* $A = I\_P$,
* $(n \mapsto 1) \in P$ and
* $(n \mapsto 2) \notin P$,

Rice's theorem can be applied and $A$ is not decidable.

Since many are not familiar with Gödel numberings, note that the example works as well in terms of Turing machines (i.e. programs) by using $A = \\{ \langle M \rangle \mid f\_M(x) = 1 \text{ for all } x \in 2\mathbb{N} \\}$.

### Unexample

Consider the set of naturals

$\qquad A = \\{ i \in \mathbb{N} \mid \varphi\_i(j) = i \text{ for all } j \in 2\mathbb{N} \\}$

which is certainly not computable. However, $A$ is not an index set for any $P$! Let $f=\varphi\_i$ for some $i \in A$. Since $\varphi$ is a *Gödel* numbering, there are (infinitely many) $j \neq i$ with $\varphi\_j = f$ but for all $j \notin A$ holds because $f(2)=i \neq j$.

Be wary of this! As a rule of thumb, if the index of the function is used on "the right hand side" or as parameter of the function in the set definition, it is likely not an index set. You may need the $s\_{mn}$ property of Gödel numberings and fixpoint theorem to show that a set is no index set.

See here and here for related posts on Rice's theorem.

---
Tags: computability, undecidability, proof-techniques, reference-question, turing-recognizable
---


# Question
Title: What does a polynomial time reduction mean?
I am having a little trouble understanding what is meant by a poly-time reduction. Suppose I have two algorithms $A$ and $B$ and then I say that $A$ is reducible to $B$. Does polytime reduction mean that the algorithm that solves $A$ using $B$ as a helper runs in $O(n^k)$ for some $k$?

So for example suppose:

$A$ is an algorithm that takes as input a list of numbers and returns whether there is a sublist whose sum is $0$.

$B$ is an algorithm that takes as input a list of numbers, and an integer $k$, and returns whether there is a sublist of length $k$ whose sum is $0$.

Then

```
def A(L):
     for i in range (1, len(L)+1)"
           if B(L, i):
                return true
     return false

```

Since this $A$ calling $B$ as a helper runs in $O(n)$ so can this be described as a polytime reduction from $A$ to $B$?

# Answer
> 3 votes
Be careful, you probably mean a reduction from a *problem* to another, and not a reduction from an *algorithm* to another.

When a problem $A$ is polynomial time reducible to a problem $B$, it means that given an instance of $A$, there is an algorithm for transforming instances of $A$ into instances of $B$. This is often done to derive hardness results: if there was a fast algorithm for some problem, there would also be a fast algorithm for some other problem. The Wikipedia article on reductions gives as an example problem pair multiplication and squaring. Both of these happen to be rather easy problems, of course.

It doesn't matter what your problems look like and how the transformation actually works, as long as it is both correct and polynomial time.

---
Tags: time-complexity, reductions
---


# Question
Title: How can a Turing Machine recognize a regular language?
This is a practice problem for a midterm in a class I'm taking:

> Given a regular language $L$, describe formally a Turing machine that recognize $L$.

I'm not sure how I should do that.

# Answer
> 3 votes
Hint: A DFA consists of 5 parts: state-set, alphabet, initial-state, final-state-set and transition-function. What does a Turing Machine consist of, and which would correspond to each part of a DFA?

# Answer
> 0 votes
$L$ is regular and so accepting by a dfa. for each transition $\delta(p,a)=q$ in the dfa accepting $L$ let $\delta(p,a)=(q,a,R)$ for define a TM which accepting $L$.

---
Tags: turing-machines, regular-languages, automata, finite-automata, simulation
---


# Question
Title: A complicated variant of Weighted Median problem
Suppose, we have an array of numbers $x\_j$ and their corresponding weights $w\_j$ where $\sum\_j w\_j \gt 1$. Now we need to find $x\_m$ such that

$$\sum\_{j=1}^{m-1} w\_j \lt 1/2 \quad \text{and} \quad \sum\_{j=m+1}^{n} w\_j \ge 1/2$$

Moreover, $x\_m \> x\_j$, $x\_m \< x\_k$ where $j \ne k$. i.e. a solution should be like this --

$$\underbrace{x\_1, x\_2, \ldots, x\_{m-1}}\_{\lt \\, x\_m}, x\_m, \underbrace{x\_{m+1}, \ldots, x\_{n-1}, x\_n}\_{\ge \\, x\_m} \\ \underbrace{w\_1, w\_2, \ldots, w\_{m-1}}\_{\lt \\, 1/2}, w\_m, \underbrace{w\_{m+1}, \ldots, w\_{n-1}, w\_n}\_{\ge \\, 1/2}$$

Moreover, it was also mentioned that I may use Dynamic Programming that could be bounded by $O(n\lg n)$.

**EDIT:**

$\\{x\_j, w\_j\\}: \quad x\_j \text{ is the value and } w\_j \text{ is the weight.}$

Example Input: $\\{10, 0.4\\}, \\, \\{5, 0.1\\}, \\, \\{6, 0.9\\}, \\, \\{2, 0.3\\}, \\, \\{3, 0.1\\}$

Example Output: $\\{2, 0.3\\}, \\, \\{3, 0.1\\}, \\, \underbrace{\\{5, 0.1\\}}\_{x\_m}, \\, \\{6, 0.9\\}, \\, \\{10, 0.4\\}$

**How I tried**

Step 1: First sort the list according to $w\_j$. -- $O(n \lg n)$

Step 2: Start from the first element from the left, add the weights $w\_j$ until $\sum\_j w\_j \ge \\, 1/2$. The current $x\_j$ is the $x\_m$. -- $O(n)$

Step 3: Stop, now we have two lists. One is on the left $L=\\{x\_1, x\_2, \ldots, x\_{m-1}\\}$ and the other is on the right $R = \\{x\_m, x\_{m+1}, \ldots, x\_n\\}$.

Step 4: Go through the list $L$, if there is any value $x\_k \> x\_m$, move $x\_k$ into $R$ at an appropriate position. Do this until all elements in $L$ is smaller than $x\_m$. -- $O(n^2)$

Step 5: if $L \ne \emptyset$, $x\_m$ is the answer, otherwise $x\_1$ is the answer.

The overall complexity will be $O(n \lg n) + O(n) + O(n^2) \approx O(n^2)$. I got confused about the DP stuff at the end of the question, so I was wondering if there is really any way to do it in $O(n \lg n)$ (or better), how do I build the optimal substructure in the case of DP?

# Answer
A tip: this problem becomes much easier if you sort the $x$'s into increasing order. (If you sort by the $w$'s, your life will be much much harder.)

More precisely, you should sort the entries so the $x$-values are in increasing order, resolving ties so the $w$-values are in increasing order. This amounts to lexicographic order on $(x,w)$. This way, if $i\<j$, then $x\_i\le x\_j$ and either $x\_i\<x\_j$ or $w\_i\le w\_j$.

---

Once the elements are sorted in this way, you can solve this problem with a linear scan.

Just scan from left to right (i.e., from $i=1$ to $n$), keeping track of the sum of the weights seen so far (i.e., $w\_1+w\_2+\dots+w\_i$). When this sum transitions from less than $1/2$ to greater than $1/2$, you've found the weighted median. At the very end, if there are multiple elements with the same $x$-value as the one you found, scan leftwards to find the first element with the same $x$-value as the one you initially found.

Running time: $O(n \lg n)$. It takes $O(n \lg n)$ time to sort, plus $O(n)$ time for the linear scan. No need for fancy dynamic programming.

---

My thanks to Dukeling for helpful comments and corrections!
> 2 votes

# Answer
This answer assumes that you can't reorder the x's. Based on a clarification on the question, this does not seem to meet OP's requirements, but I thought I'd leave it here nonetheless.

---

I'm pretty sure this can be solved in $O(n)$.

* Construct a $minSoFar$ array storing the minimum so far from the left.
Constructed in $O(n)$ going from left to right.
* Construct a $maxSoFar$ array storing the maximum so far from the right.
Constructed in $O(n)$ going from right to left.
* Initialize $rightWeight$ as the sum of all the weights. Constructed in $O(n)$.
* Initialize $leftWeight$ to 0.
* For i = 1:n: (obviously $O(n)$)

+ $rightWeight {-}{=} w\_i$
    + If all these conditions hold, we've found the position we're looking for:

    - $x\_i \> minSoFar\[i\]$ (all elements to the left are smaller than $x\_i$)
        - $x\_i \<= maxSoFar\[i\]$ (all elements to the right are bigger than $x\_i$)
        - $rightWeight \< 1/2$ and $leftWeight \>= 1/2$
    + $leftWeight {+}{=} w\_i$

Total running time = $O(n+n+n+n)$ = $O(n)$
> 1 votes

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


# Question
Title: Relations of some exponential functions -- which is correct?
Consider the following functions

* $f(n) = 3n^{(n^{1/2})} $
* $g(n) = 2^{(n^{1/2}) \log n }$ // here base of $\log n$ is 2
* $h(n) = n !$

Which of the following is true?

1. $ h (n)$ is $O (f (n) ) $
2. $h (n)$ is $O (g (n)) $
3. $g (n)$ is not $O (f (n) ) $
4. $ f(n)$ is $O(g (n))$

I tried this way :

To check which function is large :

$3n^{(n^{1/2})}$ = taking log

$n^{1/2} \log 3n $

$g(n) = 2^{(n^{1/2}) \log n }$

by taking log :

$((n^{1/2})\log n )\log 2$ =\> $0.3 (n^{1/2})\log n $

$h(n) = n !$ =\> $n^n $

by taking log :

$n \log n $

So now comparing all these 3 functions I got following equality :

$f(n) \< g(n) \< h(n) $ So answer should be (4) but actually answer is (1).
Could anyone explain me where I am wrong ?

# Answer
(1) is not the correct answer. Perhaps there is an error in the book, or an error in what you entered. As you correctly concluded, $f(n) = 3 e^{n^{1/2} \log n}$ and $h(n) \approx e^{n \log n}$ (by Stirling's approximation), so it is not true that $h(n) = O(f(n))$.

I can't tell whether you've drawn the correct conclusions about the pairwise relationships between these three functions. You wrote that $f(n) \< g(n) \< h(n)$, but this is not correct. For instance, $f(1) = 3$, $g(1) = 3$, $h(1) = 1$. Those inequalities don't hold for all $n$ -- but if we care about big-O notation, then that's not the right question anyway, since big-O notation relates to the asymptotic behavior of these functions (as $n\to \infty$).

The right question is whether $f(n) = O(g(n))$, whether $g(n) = O(f(n))$ (be careful here! better double-check your work on this one another time), and so on.

See also Sorting functions by asymptotic growth and How does one know which notation of time complexity analysis to use?. They should answer your remaining questions.
> 2 votes

---
Tags: asymptotics
---


# Question
Title: Algorithm to maximize function of subsets
Let's say I have a finite set S with, say, 1000 elements, and a function f on some subset of S. Suppose that f has no useful mathematical properties.

What algorithm is most relevant in finding the subset of S that maximizes f?

# Answer
> 4 votes
The algorithm that iterates through every $2^{1000}$ subsets. Sorry, but stated like this, the answer is that there is no solution.

For every algorithm you come up with, I can come up with a subset $T \subseteq S$ such that $T$ is the last of all sets to be tested, and be the max of $f$.

---
Tags: optimization
---


# Question
Title: Optimal coverage of a $D$-dimensional grid with small blocks
I have a $D$-dimensional grid with the size $(N\_1, \ldots, N\_D)$, where $N\_i$ are natural numbers, and a "flat block size" $M$, also a natural number. I want to find a decomposition $(m\_1, \ldots, m\_D)$ such that:

1. $\prod\_{i=1}^D m\_i = M$,
2. $R = \prod\_{i=1}^D f(N\_i, m\_i) m\_i - \prod\_{i=1}^D N\_i$ is as low as possible. Here $f(N,m)$ is the minimal number of blocks of length $m$ necessary to cover a 1D grid with size $N$ (or, formally, $f(N, m) = N / m$ if $N$ is a multiple of $m$, and $f(N,m) = N\\,\mathrm{div}\\,m + 1$ otherwise).
3. The number of $m\_i$ equal to 1 is as high as possible (but this is low priority, the condition 2 is more important).

How should I approach this? Is there some standard algorithm this can be reduced to?

In my case $M$ is not very big (of the order of 1000). Also, an absolute minimum in all cases is not strictly required; if there is an approximate algorithm, it will do to.

(In case anyone is interested in the application, I want to use it to find work group dimensions for an OpenCL kernel with a known global size and total number of work items).

# Answer
One unsophisticated approach is to factor $M$, then exhaustively explore all possible decompositions of $M$ into a product of $D$ integers, and see which is best according to your criteria. I suspect this will prove to be an entirely reasonable solution for your example parameter ranges.

The number of possible decompositions is exponentially large, in general. If $M=\prod\_i p\_i^{e\_i}$, then there are $\prod\_i {D+e\_i-1 \choose e\_i}$ possible decompositions, which (depending upon $M$) could be rather a lot.

However, for your particular parameter values, the number of possible decompositions will probably still be manageable, so the unsophisticated algorithm should work fine. If $D=3$ and $M$ is 32 times a random number from 1 to 32, then the number of possible decompositions will range from a minimum of 21 possibilities (for $M=32\times 1$) to a maximum of 252 possibilities (for $M=32\times 30$). That's small enough that you can easily enumerate all possibilities and see which is best.

If you increase $D$ to $D=7$, then the number of possible decompositions will vary from a minimum of 462 (for $M=32\times 1$) to a maximum of 45276 possibilties (for $M=32\times 30$). That's still small enough that you can enumerate all possibilities and use the unsophisticated algorithm I mention above.

If you run into some other parameter choices where there are too many decompositions, a simple variant would be to randomly pick a bunch of different decompositions and see which of those is the best. It's not the fanciest algorithm around, but it's a reasonable thing to try.

Anyway, this should solve your problem for the parameter sizes you mention.
> 2 votes

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


# Question
Title: What is the most power/energy efficient sorting algorithm?
I am writing a Android phone application that needs to be very power efficient, and I would like to use the most power efficient sorting algorithm. I will implement it in C for extra power efficiency. What algorithm is the most power efficient algorithm for sorting arbitrary text strings?

# Answer
As concluded by this paper, the algorithm with the better asymptotic run time seems to also have the better energy efficiency, which corroborates the assumption that an algorithm with a higher performance also has a higher energy efficiency.
> 6 votes

# Answer
Smaller runtime is not all. In Evaluating Algorithms according to their Energy Consumption (Computability in Europe, 2009), Fudeus née Bayer and Nebel show that an algorithm with more executed instructions (this is typically analysed, at least in theory) might use less energy¹.

Keep in mind that energy consumption is determined by at least

* the algorithm itself,
* the compiler,
* the CPU and
* the hardware memory management.

One particular effect is that the energy consumption of modern CPUs is not just the sum of fixed contributions of all statements. The *sequence* is relevant, that is an addition may have different cost depending on whether it is executed after a jump or a subtraction. Hence, for example

* instruction reordering by the compiler can have effects in all directions on energy consumption, depending on the target system, and
* fewer operations cost more because e.g. the ALU is shut down in between operations and is costly to start up again.

---

1. It might also be faster, mind.
> 5 votes

# Answer
The sort benchmark website has a category on energy efficient sorting. Currently, NTOSort and Tritonsort seem to be the best.
> 3 votes

---
Tags: algorithms, sorting, efficiency, power-consumption
---


title: Reductions among Undecidable Problems

text:
# Question
Title: Reductions among Undecidable Problems
Im sorry if this question has some trivial answer which I am missing. Whenever I study some problem which has been proven undecidable, I observe that the proof relies on a reduction to another problem which has been proven to be undecidable. I understand that it creates some kind of an order on the degree of difficulty of a problem. But my question is - has it been proven that all problems which are undecidable can be reduced to another problem which is undecidable. Is it not possible that there exists a undecidable problem which can proved to have no reduction to any other undecidable problem (Hence to prove the undecidability of such a problem, one cannot use reductions). If we use reductions to create an order on the degree of computability then this problem cannot be assigned such a degree.

# Answer
> 9 votes
As Hendrik Jan mentioned, there are in fact different *degrees* of undecidability. For example, the problem of deciding whether a Turing machine stops on *all* inputs is harder than the halting problem, in the following sense: even given an oracle to the halting problem, we can't decide whether a given Turing machine stops on all inputs.

One important technique used to show relations like these is *diagonalization*. Using diagonalization, given a problem $P$ we can always find a harder problem, namely the halting problem for Turing machines with an access to a $P$ oracle. The new problem $P'$ is harder in the following sense: a Turing machine with an oracle access to $P$ cannot solve $P'$. In that sense there is no "hardest" problem.

---
Tags: computability, reductions, undecidability
---


title: Want to understand Big O by graph

text:
# Question
Title: Want to understand Big O by graph
$f(n) = 3n+3$ ;
$f(n) = O(n)$
By definition :
$3n+3 \leq c\_1.n$
By dividing both side by $n$
$3+\frac{3}{n} \leq c\_1$
means we are getting constant range for $c\_1$ for any $n$. Again it shows $c\_1$'s value must be greater than $3$ at any cost.
e.g. if we take $c\_1$'s value 3.5 so $n$'s value will be $6$.
Now if we plot graph ( Because I want to learn this concept by understanding graph )
$c\_1.g(n)$ graph goes below of $f(n)$ graph. I have taken following values for both functions :
$f(n)=3n+3$

$ \begin{matrix} n & f(n)\\ 1 & 6\\ 2 & 9\\ 3 & 12\\ -2 & -3 \end{matrix} $

for $g(n) = 3.5n$
$ \begin{matrix} n & g(n)\\ 1 & 3.5\\ 2 & 7\\ 3 & 10.5\\ -2 & -7 \end{matrix} $

If we plot graph by these values it doesn't bind $f(n)$ i.e. $3n+3$ above by the value of $g(n)$ i.e. $3.5n$
Can anyone explain me this concept by graph ?

# Answer
> 3 votes
Here are a picture and some description:

> The formal definitions associated with the Big Oh notation are as follows:
>
> • f (n)= O (g (n)) means c · g (n)isan upper bound on f (n). Thus there exists some constant c such thatf (n) is always ≤ c · g (n), for large enoughn (i.e. , n ≥ n0 for some constant n0 ).
>
> • f(n)=Ω(g (n)) means c · g (n) is a lower bound onf (n). Thus there exists some constant c such that f (n) is always ≥ c · g (n), for all n ≥ n0.
>
> • f (n)=Θ(g (n)) means c1 · g (n) is an upper bound on f(n) and c2 ·g(n) is a lower bound on f (n), for all n ≥ n0 . Thus there exist constants c1 and c2 such that f(n) ≤ c1 · g(n) and f(n) ≥ c2 · g (n). This means that g(n) provides a nice, tight bound on f(n).

You can find more details in the Chapter 2 of The Algorithm Design Manual,Steven S. Skiena.

# Answer
> 2 votes
The big $O$ notation describes the limiting behavior of a function. That mean the property you are looking for is true for $n$ large enough.

$g(n)$ may be smaller than $f(n)$ for small $n$ but as $n$ goes to the infinite $g(n)$ will at some point always be greater than $f(n)$.

What the big $O$ notation look like on a graph is: if you look at the two right end of both function $f(n)$ is lower than $g(n)$. But it's hard to look at infinity with a graph...

# Answer
> 2 votes
From introduction to the design and analysis of algorithms:

a function $t(n)$ is $O(g(n))$ if $t(n)$ is bounded above by some constant multiple of $g(n)$ for all large $n$.

So, $t(n) \le cg(n) \quad \text{for all $n\>n\_o$}$

This image is from here.

Edit: I meant to say that the referenced book, as well as the webpage have graphical explanations for Oh, Omega, and Theta notation.

---
Tags: asymptotics
---