# Question
Title: Clarification for a class of Turing machine problems
So say I have a task like this:

> Construct a Turing machine transforming the word u to the word v byt removing all the sequences of form "ba" from the word u. Input alphabet = {a,b,c}.
>
> Example: for IN cabbaacba, OUT cac.

And my problem always is: can I leave blank characters in place of "ba" sequences in tasks like this so that in the end, I have something like $ca \Phi \Phi \Phi \Phi c \Phi \Phi$ on the tape or do I have to work on the tape in such a way that I end up with, for example "cac", written consecutively, without blanks?

# Answer
The question does not mention replacing "ba" by spaces. It does not say that you can have spaces between the symbols in the output word. Is the blank character even in the output language?
> 2 votes

---
Tags: turing-machines
---


# Question
Title: What's the complexity of calculating the shortest path from $u$ to $v$ with Dijkstra's algorithm using binary heap?
> **Problem:** Consider a graph $G = (V, E)$ on $n$ vertices and $m \> n$ edges, $u$ and $v$ are two vertices of $G$.
>
> What is the asymptotic complexity to calculate the shortest path from $u$ to $v$ with Dijkstra's algorithm using Binary Heap ?

To clarify, Dijkstra's algorithm is run from the source and allowed to terminate when it reaches the target. Knowing that the target is a neighbor of the source, what is the time complexity of the algorithm?

**My idea:**

Dijkstra's algorithm in this case makes $O(n)$ **inserts** ( $n$ if the graph is complete) and 1 **extract min** in the binary heap, before calculate the shortest path from $u$ to $v$.

In a binary heap insert costs $O(\log n)$ and extract min $O(\log n)$ too.

So the cost in my opinion is $O(n \cdot \log n + \log n) = O(n \log n)$

But the answer is $\Theta(n)$, so there is something wrong in my thinking.

Where is my mistake?

# Answer
> 3 votes
Your answer actually depends on what implementation of Dijkstra's algorithm is used. The textbook implementation inserts all nodes in the queue, and then proceeds with the extraction. The other starts with only the source in the queue. This is generally more efficient in practice, although it needs a bit of book-keeping.

For the standard implementation, you can do better than $O(n \log n)$. Instead of successively inserting each node in the heap based queue, you create an array, and "heapify" it. "Heapify" is a bulk operation for converting a list of numbers into a heap, in $O(n)$, or rather $\Theta(n)$ (see here or here). After that, there will be only one/two extract-min operations (one or two depending on whether the source is originally in the queue or not) in $O(\log n)$. So overall, $\Theta(n)$.

For the other implementation, you can do it in $\Theta(\Delta \log \Delta)$, where $\Delta$ is the degree of the source $u$.

---
Tags: algorithms, graphs, algorithm-analysis, runtime-analysis, shortest-path
---


title: Contrast vs. Brightness question

text:
# Question
Title: Contrast vs. Brightness question
As part of my homework I need to prove (or disprove) that changing the contrast and, then, changing the brightness is (or isn't) the same as changing the brightness and, then, changing the contrast.

Let's assume that we are using gray-scale.

* **Brightness**: the mean of the gray levels.
* **Changing brightness**: adding or decreasing a constant value from every pixel.
* **Contrast**: max - min of the gray-scale levels.
* **Changing the contrast**: stretching the gray levels around the mean.

I understand that you need to disprove it, but I don't know how to do it in a formal way.

# Answer
> 3 votes
Write down brightness and contrast as functions that act on a single gray-scale pixel. As you said, brightness is $b(x) = x + \alpha$ and contrast is $c(x) = \beta(x - x\_\text{mean}) + x\_\text{mean}$ or something similar. Now all you need to show is that $b \circ c \neq c \circ b$.

---
Tags: image-processing
---


# Question
Title: Is there a term for the general method used in XORed linked list?
The XOR linked list is perhaps the most prominent example of storing a reversible hash of two values and using a known value and the stored hash value to derive the other value. Is there a term for the general mechanism (or a way to describe it very concisely)?

As a related question, are there other somewhat recognized examples of using this mechanism?

In informally studying computer architecture, I have encountered what I think are two or three examples. One was a suggestion for a MRU-based cache way predictor by XORing the MRU bit with a bit derived from the address; the derived bit is the "known" value. The other was a similar, XORing the hysteresis bit of a branch predictor with a bit derived from branch information. A possible third example might be the agree branch predictor which uses a (possibly static) per-branch prediction to bias entries in a dynamic predictor so that aliasing tends to be non-destructive. A confirmation that these actually should be recognized as the same general mechanism as used by the XOR linked list would also be helpful.

# Answer
It is a typical example of a space-time tradeoff trading increased time (CPU instructions required) for decreased space (memory required). There are many examples of this.

In this particular case I'd say it is a (simple) form of lossless compression. This because the data is stored in a minified but unusable form and needs some computation (decompression) done to receive the original (and usable) form, but no information is lost.
> 3 votes

---
Tags: terminology, reference-request, data-structures, lists
---


# Question
Title: Information theory from a (very pure) mathematician's perspective
I'm a pure mathematician interested in learning about information theory. Unfortunately, I'm about as pure as they come - my specialty is mathematical logic, and I have absolutely no experience with programming or anything of a computational nature. I tried looking at Shannon's original paper, but the profusion of numbers intimidated me (I'm a mathematician after all!) When he starts discussing the particulars of coding specific alphabets, my brain begins to asking whether this attention to detail is really necessary and soon zones out... It took Church's thesis for granted some time ago. (Pathetic, I know.)

I'm wondering if there's some introduction to information theory written with people like me in mind. Something which uses the language of measure theory and recursion theory, and works in the greatest generality. Perhaps an expert in the area has written some notes in this direction as an idle folly?

I realize that this might not be the place to ask this question, and apologize if this is the case.

# Answer
> 1 votes
I think you are looking for the topic of "**Algorithmic Information Theory**" (AIT). This area is the collision of information theory and computer science. For example "Information and Randomness: An Algorithmic Perspective" written by cristian calude contains interesting subjects in this area. You can find more in the AIT website.

---
Tags: information-theory
---


# Question
Title: Are you allowed to have empty states on Turing machine?
So I'm doing some exercises with Turing machine and quite often it happens that a given set of states can be achieved if and only if some character was met. Therefore, we may have some states q3-q7 which the machine may be pointed to if and only if we spotted a and (because of the task spec, for example), we know that we may find only some chars (say b, d but not c, e) from the input language there so there's no need to have a separate state for every symbol. Can I then just program the states I'll actually use there and have some void states or do I have to put something there (like just reprinting the found character) anyway, even though I'm 100% sure the machine will never go to the state for some symbols?

# Answer
The output and transition functions have to be defined for all state and character combinations. But if you say you can't get into the state, it means that if you do get there, the input was invalid. Therefore simply append a definition like "and all transitions not mentioned so far are to a rejecting state" (which is an endless loop if you are doing a stop/don't stop machine).
> 3 votes

---
Tags: turing-machines
---


# Question
Title: Understanding Dijkstra's notation $f.x.y$
I recently discovered that I have a fondness for the work of Dijkstra. I am currently reading random EWDs, and stumbled across one with some notation that I couldn't quite grasp.

Dijkstra states that $\[ x \< y \implies f.x.y \< f.y.x\]$

OK, so. This isn't a list comprehension, right? Why the brackets?

Also, how could this be read aloud? What does $\implies$ mean?

And finally, what does $f.x.y$ and $f.y.x$ mean?

And how could this statement be written more conventionally? And does Dijkstra's notation derive from anything, or is it entirely his own invention?

# Answer
I think this would read as follows in modern notation (although field-local variations are possible):

$$\forall x y. x \< y \Rightarrow f(x,y) \< f(y,x).$$

Read aloud: *for all x and y, x is less than y implies that f of x and y is less than f of y and x*.

If you read the first sentence of the linked document, it says that square brackets represent universal quantification over $x$ and $y$. The second states that $f$ is a function. `=>` is ASCII art for $\Rightarrow$ (logical implication).

The main problem here is missing context (and detective skills). This article refers to EWD878. Perhaps looking there would have helped. Indeed, looking at that article, you see notation slightly closer to what is used today (at least, by Haskell programmers: `f.x.y` becomes `f\ x\ y`).
> 8 votes

---
Tags: terminology, history
---


# Question
Title: Which is more computationally efficient: multiplication or 0 padding?
On a PC I am implementing an algorithm in which a number from a look table will be chosen randomly, and will be multiplied by 1000 or 10000. Instead of multiplying by 1000 or 10000 I am thinking of simply padding the numbers with the required 0s. This padding will be nothing but some write operations (though random writes) in memory.

Which is more computationally efficient: multiplication or 0 padding?

# Answer
> 2 votes
I'm assuming that your numbers are in binary. In this case, 0 padding is shift left: `x << 3` is the same as `x * 0x08`, where 0x08 (hex) is 1000 (binary).

Shifting is much simpler to implement in hardware and is generally more efficient. You could check by writing a short C program.

Note that there is one significant difference between shift left and multiplication. The former does not signal if there is an overflow error, whereas the latter will.

# Answer
> 2 votes
If 1000 and 10000 are constants, then any decent compiler will figure out the most efficient way to do the multiplication by itself. This is platform dependent.

Any memory operation is most likely much more costly than multiplication (by orders of magnitude if the data is not in cache).

---
Tags: efficiency, binary-arithmetic
---


# Question
Title: How optimal is Lempel-Ziv at reaching the Shannon limit?
I find this a bit difficult to describe, but I am interested in the following idea :

The LZ algorithm factors (verb) an input stream into adjacent factors, these are by definition the maximal prefixes of the piece of text that occur in the previous text (or equivalently the previous concatenation of LZ factors).

I know and believe that in the long term (given infinite input and infinite window) this coding scheme can achieve the Shannon limit, that it will find all repeat patterns that exist.

However in *any given finite text* (but with an unbounded window) how optimal is this?

Do the choice of factors earlier in the input have potential detrimental effects later on? For instance, could LZ converge to a choice of factors that omits certain larger factors, or factor-choices that would result in a better cover of the input (i.e. a choice of factors that cover more of the text?).

Or is the optimality of LZ only constrained by the window limit, and the finite nature of a text? Please provide some kind of hand waving or intuitive proof.

# Answer
> 5 votes
If you apply the LZ77 algorithm twice, it doesn't find any new repeat patterns the second time. You can show that if there were any repeat pattern present after the LZ77 algorithm has been applied. this would have arisen from a repeat pattern in the original data which LZ77 would have found.

The DEFLATE algorithm follows LZ77 with Huffman coding, and does better for finite strings than LZ77 alone. So LZ77 can be improved upon for finite strings fairly easily, just not by using another iteration of LZ77.

However, the Huffman algorithm doesn't use repeat patterns. If you're asking the question of whether, for finite strings, the LZ77 algorithm does as well as any other algorithm based solely on finding repeat patters, I don't know if anybody has looked at this. The problem isn't quite well-defined as stated, but somebody might be able to prove some interesting theorems about this.

# Answer
> 1 votes
The book *Elements of information theory* by Cover and Thomas contains some information on the Lempel-Ziv algorithm, including a proof of its asymptotic optimality (see Chapter 13).

---
Tags: complexity-theory, combinatorics, data-compression, lempel-ziv
---


# Question
Title: What is $R_\min$ in this formulat for optimal buffer size?
I read a question from my recitation about optimal buffer size. As solution there is a furmula for calculating the optimal buffer size; I'm not sure about one of its parameters. The formula is

$\quad \operatorname{Buffer}\_{\text{optimal}} = \frac{\operatorname{Buffer}\_{\text{current}}}{1-\frac{R\_{\text{app}}}{R\_{\min}}}$

Where

* $\operatorname{Buffer}\_{\text{optimal}}$ is the optimal buffer size we want to calculate.
* $\operatorname{Buffer}\_{\text{current}}$ is the current buffer size.
* $R\_{\text{app}}$ is the rate the application reads data from the buffer at.
* $R\_{\min}$ -- this is the one I'm not sure about.

The example problem is this:

> Alice connects to web server and downloads a file of 12KB size from the server. There is a router between them. The transmission rate between Alice and router is 400,000B/s and the transmission rate between router and server is 1MB/s. Buffer size in the router is 4KB, and buffer size in Alice is 3KB. The rate the application reads from Alice buffer with is 100KBps. Calculate the optimal buffer size for Alice as a fuction of router buffer size and free space at the buffer.

So as described in the solution, according to the above formula the solution is

$\qquad \operatorname{Buffer}\_{\text{optimal}} = \frac{3\*10^3}{1-\frac{10^5}{4\*10^5}}$

So what $ R\_{\min} $ could be ?

# Answer
> 2 votes
$R\_{min}$ is the "***Writing Rate in Application Buffer***" (from router in your example).

This formula makes sense for different conditions like **$R\_{app}=R\_{min}$**. In this case the buffer size should be infinite (very large buffer) and it is intuitively correct. **$R\_{app} \>R\_{min}$** makes the size negative which shows that buffering does not help while the reading data is very faster than buffering data in user side.

---
Tags: computer-networks
---


# Question
Title: How does sorting come into play with convex hull?
I am investigating a convex hull algorithm that involves sorting. In fact, its running time is limited by sorting, so it is $O(n \log n)$, where $n$ is the number of points on the plane.

That algorithm first sorts the points by x-coordinates. It then includes the first and last points in the convex hull. From there on, I am confused. How could an algorithm like this get the other points of the hull?

# Answer
It is easier to catch the connection with sorting if you first sort the points by their **polar angle**. This is the basic idea for the Graham scan. Though, the idea with sorting points by the x-coordinates also works: you need then to apply just a slight modification of the same Graham's algorithm.
> 4 votes

---
Tags: algorithms, computational-geometry
---


title: median filter one after the other

text:
# Question
Title: median filter one after the other
Operate on an image by performing Median Filtering in a 3x3 window.
Operate on the resulting image by performing, again, Median Filtering in a 3x3 window.
Can the resulting image be obtained from a single Median filtering?

my initial thought is that it can be done with the right mask. maybe a median next to a median. but i'm not sure.

# Answer
> 1 votes
The value a pixel gets after applying the median filter only depends on points in the $3\times 3$ window centered at it. So applying the media filter twice, any pixel depends only on points in the $5\times 5$ window centered at it. So you could in principle do it in one go, using a larger window and a more complicated function. How complicated - I'll let you to find out.

# Answer
> 1 votes
The median is a value of a sample which states that half of the other values of the sample have higher values and the other ones are smaller ones. In a 3⨉3 filter you are selecting the median out of a sample of 8 elements. Let's assume we have the following values in our sample (an image of size 3⨉3):

```
1  2   4
8  16  32
64 128 255
```

If we apply the median filter for the upper left value \[sample: {2, 8, 16}\], the median is 8 (not processing out of boundary values). After the first application of the median filter we get a new sample:

```
8  8  16
16 20 16
16 32 32
```

If we apply the median filter again, we get:

```
16 16 16
16 16 20
20 16 20
```

So my point here is that after each application of the median filter, you will get a new sample \[0\]. But the evaluation of one new pixel depends on all the other sample values and modifies the sample itself. Because of this dependence I cannot see any way to be able to apply the filter twice in one step. I also did not find any literature about this \[1\].

\[0\] Unless the image contains only the same value at each pixel which we cannot assume.
\[1\] which I *don't* want to use as a pro or contra argument.

---
Tags: image-processing
---


# Question
Title: What mechanisms prevent a process from taking over the processor forever?
Suppose a process keeps running code (e.g. an infinite loop). How can other programs take over? What prevents the process from remaining active forever?

# Answer
> 12 votes
Various peripherals are connected to the main processor. When an event happens in a peripheral, the peripheral sets an electric signal which causes the processor to take some action. The act of setting this signal is called an interrupt request (IRQ for short), and the aftermath of the interrupt request on the processor is called an interrupt.

When a processor receives an interrupt, it typically does something like this:

* Mask interrupts. This means that if other IRQs happen (coming from the same peripheral or a different one), they won't be noticed just yet: they will not have any effect on the processor until interrupts are unmasked.
* Save the value of the program counter register to a register dedicated to that effect. Also save the value of a register that contains the processor mode (e.g. user mode, kernel mode, interrupt mode, …). Depending on the processor architecture, other registers may be saved as well (e.g. stack pointer).
* Switch the processor mode to interrupt mode.
* Read a value from a predefined address in memory, or from a register. This value is called the interrupt vector.
* Jump to the address given by the interrupt vector.

The code at that address is typically kernel code. On computer architectures with memory access permissions, the kernel normally prevents unprivileged processes from setting interrupt vectors or from changing the code at that address. The kernel code typically begins by copying the saved register values into memory, so that they won't be forgotten if some other interrupt occurs.

One of the peripherals that can send interrupts is the clock. To avoid a process running forever, whenever the operating system kernel allows a process to execute (by branching to its code), it first programs the clock to send an interrupt at a certain time in the future, allowing the program to run uninterrupted only for a time slice.

If the process is still running at the end of the time slice, the clock interrupt occurs. The code at the interrupt vector is kernel code, so the process is no longer running: it has been preempted. The process's code and data are still around: the kernel can later decide to let the process execute some more by restoring the saved register values (finishing with the program counter).

After the kernel has finished its basic interrupt processing, and has performed whatever tasks it deems useful, it decides which process to execute next. This decision is called scheduling.

Some operating systems (mostly on tiny embedded systems) allow processes to run as long as they like. This is known as cooperative multitasking. (And some operating systems are even more basic: they only allow a single task at a time.)

# Answer
> 5 votes
The technique is called preemptive multi tasking. See for example this Wikipedia article.

Basically the operating system runs every process for a short time, then suspends it and continues with the next process.

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


# Question
Title: Difference between decision tree and rule based reasoner
I am new to this topic, and in some scientific papers I've been reading about prediction in sports I encountered the term rule based reasoner. Is it this term the same as a semantic reasoner( where the two main directions are forward and backwards chaining?). If yes, can you point out the difference between a decision tree and this? Because for me, it seems pretty much the same.

# Answer
Decision tree classifiers could be easily converted to rule based classifiers in data mining and vice Versa. please have a look at "Introduction to Data Mining", chapters 4 and 5.

Usually it depends on the data characteristics, how to choose between these two methods and which of the mentioned methods give you smaller classification errors.
> 3 votes

---
Tags: terminology, artificial-intelligence, data-mining
---


# Question
Title: What is the decision version of independent set?
I always read that finding an independent set of size $k$ in a graph is $\mathsf{NP}$-complete. However, this only requires looking for all combinations of $k$ vertices and this is a polynomial procedure of order $k$.

I know that we can reduce directly SAT to independent set, with $k$ the number of clauses.

The problem is that I can't grasp correctly, as in 3-COLORING or 3-SAT, the required format to study the complexity of INDEPENDENT SET.

What is the decision version of independent set? And why isn't $k$-independent set in $\mathsf P$?

# Answer
The definition of the decision version of independent set is the following:

Given as input a graph $G = (V,E)$ and an integer $k \in \mathbb{N}$, does there exist a set of pairwise non-adjacent vertices $I \subseteq V$ of size $|I| \geq k$?

The problem is polynomial time solvable if you consider $k$ to be *constant*, i.e., you can solve the problem in time $\mathcal{O}(n^k)$ but we usually take $k$ to be a part of the input. If you reduce an NP-complete problem to this problem, you will see that the $k$ is indeed unbounded.
> 15 votes

# Answer
The problem is $k$ might be very big, say as big as about $n$. Then $n^k$ would be exponentially large.
> 6 votes

# Answer
You should distinguish the following two things.

**Independent Set** (what Pål GD described in his answer)
Instance: A graph *G* and an integer *k*∈ℕ.
Question: Does *G* have an independent set of size *k*?

***k*-Independent Set** (*k*∈ℕ)
Instance: A graph *G*.
Question: Does *G* have an independent set of size *k*?

Note that the latter is not a single problem. Rather, it is an infinite family of problems: 1-Independent Set, 2-Independent Set, 3-Independent Set, 4-Independent Set, and so on.

Independent Set is NP-complete. *k*-Independent Set is in P for every *k*∈ℕ. They are completely different.
> 6 votes

---
Tags: complexity-theory, terminology, decision-problem
---


# Question
Title: Finding the complexity of a recursive method
An assignment question asks me to find the complexity of a \[tail\] recursive algorithm, copied below. While I understand all the complexity specifics, for example that the while loop's complexity is $n-1$ and the complexity of setting $j$ to $0$ is 1, I don't understand how I could trace the code recursively, that is within itsel - it's too hard to keep track of.

What I tried doing, is turning the algorithm into an iterative one, by simply putting all the code into a big while loop and thus avoiding the recursive call. But I'm not sure if this affects the complexity of the original algorithm.

```
Algorithm MyAlgorithm(A, n)
   Input: Array of integer containing n elements
   Output: Possibly modified Array A
     done ← true
     j ← 0
     while j ≤ n - 2 do {
       if A[j] > A[j + 1] then {
       swap(A[j], A[j + 1])
       done:= false
       }
     j ← j + 1
     end while
     j ← n - 1
     while j ≥ 1 do
       if A[j] < A[j - 1] then
       swap(A[j - 1], A[j])
       done:= false
    j ← j - 1
    end while
    if ¬ done
       MyAlgorithm(A, n)
    else
      return A

```

# Answer
You have to analyze the circumstances in which your algorithm makes a recursive call. That is, when is `not done` true? Well, your it's true whenever your algorithm is required to make a swap in one of its passes over the array (one of the while loops). To analyze the total worst case running time, determine the maximum number of recursive calls, and add up the total work in each of these calls. In some recursive algorithms, the amount of work in each recursive call might be different. Is that the case in your algorithm?
> 1 votes

# Answer
**Hint 1**: This algorithm is similar to bubble sort. It sorts the array in ascending order.

**Hint 2**: Try to work out what the series of swaps do when taken to completion. For example, what happens when the two `while` loops are run on the following array: $\\{4, 2, 5, 6, 1, 3\\}$. After the first while loop, is some part of the array sorted? What after the second loop? What after the function is recursively called again?

**Hint 3**: Worst case performance, as you guessed, would be when the array is reverse sorted - due to maximum number of swap operations.

I think these are substantial hints for an assignment problem, and you should be able to work it out from here.
> 1 votes

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


# Question
Title: Quicksort vs. insertion sort on linked list: performance
I have written a program to sort Linked Lists and I noticed that my insertion sort works much better than my quicksort algorithm. Does anyone have any idea why this is? Insertion sort has a complexity of $\Theta(n^2)$ and quicksort $O(n\log n)$ so therefore quicksort should be faster. I tried for random input size and it shows me the contrary. Strange...

Here the code in Java:

```
public static LinkedList qSort(LinkedList list) {

    LinkedList x, y;
    Node currentNode;
    int size = list.getSize();

    //Create new lists x smaller equal and y greater
    x = new LinkedList();
    y = new LinkedList();

    if (size <= 1)
        return list;
    else {

        Node pivot = getPivot(list);
        // System.out.println("Pivot: " + pivot.value);
        //We start from the head
        currentNode = list.head;

        for (int i = 0; i <= size - 1; i++) {
            //Check that the currentNode is not our pivot
            if (currentNode != pivot) {
                //Nodes with values smaller equal than the pivot goes in x
                if (currentNode.value <= pivot.value) {
                    {
                        x.addNode(currentNode.value);
                        // System.out.print("Elements in x:");
                        // x.printList();
                    }

                }
                //Nodes with values greater than the pivot goes in y
                else if (currentNode.value > pivot.value) {
                    if (currentNode != pivot) {
                        y.addNode(currentNode.value);
                        // System.out.print("Elements in y:");
                        // y.printList();
                    }
                }
            }
            //Set the pointer to the next node
            currentNode = currentNode.next;
        }

        //Recursive calls and concatenation of the Lists and pivot
        return concatenateList(qSort(x), pivot, qSort(y));

    }
}

```

# Answer
> 8 votes
Pedro's answer covers what is going wrong with your first attempt. But I want to talk about a few things when it comes to analyzing algorithms that may be a bit subtle.

**What is your algorithm?**

Before you can start analyzing an algorithm, you need to say exactly what you're doing. "Quicksort", for example, can mean a number of different things. The basic pattern is:

* Pick a *pivot* element
* *Partition* the input around the pivot
* *Recursively sort* the pieces
* *Combine* the sub-problems

Even at this level, there is some ambiguity, since I haven't actually described how to pick the pivot and how to partition. In the modern era, which probably means about 20 years, people think that you:

* Pick the pivot uniformly at random
* Parition into "less than", "equal", and "greater than" pieces

In which case the number of comparisons is $O(n\log n)$ in expectation and close to information theoretic bounds.

But! Notice that you and some commenters like to pick the pivot other ways, so it is still important to say what you really mean. Picking the pivot deterministically means that there are cases (depending on your rule) that will be much much worse.

**What are your primitives?**

Even once you've decided what you *really* want your algorithm to do, you need to think about the "basic steps". For quicksort we need:

* A way to pick the pivot
* A way to compare elements
* A way to partition
* A way to combine

Notice that most analysis of sorting devolves onto counting comparisons. We'll talk about why this is next.

**How much do your primitives cost?**

Finally, in any detailed running time analysis, you need some model of computation in which you can count "operations". The most popular model for algorithms is the "RAM" which has arrays with constant-time reads/writes, the usual arithmetic operations, and integer comparisons. (But there are lots of others.)

For the usual analysis of quicksort, on an input of length $n$, you'll want:

* Picking the pivot to be $O(n)$
* Partitioning to be $O(n)$
* Combining sub-arrays to be $O(n)$

You can do this with linked lists (as in your second try) or (more usually) arrays, but the actual implementations will be *very different*. The issue is that in your first try (according to other answers), you were spending $\Omega(n^2)$ on partitioning, which changes the complexity a *lot*.

**Why sorting analyses usually just count comparisons.**

The reason I wrote all of this down is that, even in your bad implementation, you weren't doing more *comparisons*. Most of the effort in analyzing sorting algorithms based on comparisons counts *only* comparisons for a few reasons:

* It is very general (machine independent)
* For most algorithms in that class, a reasonable implementation can "charge" every other operation to a comparison in a way that each comparison gets $O(1)$ operations

This second part is where your first try fell down. Hope this helps.

**Even more**

Everything so far was still theory. Practical sorting algorithms actually need to be tried on real machines. This is a whole area, and my understanding is that the current champ is not one of the standard algorithms, but something called "timsort", which you can find here http://svn.python.org/projects/python/trunk/Objects/listsort.txt

# Answer
> 11 votes
The problem is that the analysis of Quicksort, as you have implemented it, assumes that accessing any element can be done at a constant cost, i.e. in $\mathcal O(1)$. This is not the case with linked lists.

Note that at the top of the `while (right > left) {` loop in your code, you cycle through all the elements until `left` and then repeatedly cycle through all the elements adjusting `right`. While in Quicksort this should just cost at most $\mathcal O(n)$, in your case it costs at most $\mathcal O(N^2)$, where $n$ is the current level of recursion and $N$ is the total number of elements.

As Louis pointed out in the comments below, there is a linked list analogue of Quicksort, but it needs to be implemented quite differently from what you did.

The bottom line: Linked lists are not arrays, and algorithms that will work well on arrays will not necessarily work well on linked lists. There are several good books on algorithms out there that will point you to good algorithms for each case.

**Update**

The code in the question has now been modified to reflect the implementation described by Louis below. There are still potential inefficiencies, however, in the selection of the pivot. In essence, any single operation inside the main loop which is *not* $\mathcal O(1)$ will mess-up the asymptotic behavior.

Oh, and creating new lists in every level of recursion is probably not extremely efficient either.

# Answer
> 1 votes
The simplest way to sort lists is mergesort: Split the list into halves (just zip down, one element left, one right), sort left and right recursively, then merge (take the smaller of the first elements of the left and right lists). Well suited to lists (just linear transversals, mostly pointer juggling), and $\Theta(n \log n)$.

---
Tags: algorithms, algorithm-analysis, sorting, lists
---


# Question
Title: Why is push_back in C++ vectors constant amortized?
I am learning C++ and noticed that the running time for the push\_back function for vectors is constant "amortized." The documentation further notes that "If a reallocation happens, the reallocation is itself up to linear in the entire size."

Shouldn't this mean the push\_back function is $O(n)$, where $n$ is the length of the vector? After all, we are interested in worst case analysis, right?

I guess, crucially, I don't understand how the adjective "amortized" changes the running time.

# Answer
The important word here is "amortized". Amortized analysis is an analysis technique that examines a sequence of $n$ operations. If the whole sequence runs in $T(n)$ time, then each operation in the sequence runs in $T(n)/n$. The idea is that while a few operations in the sequence might be costly, they can't happen often enough to weigh down the program. It's important to note that this is different from average case analysis over some input distribution or randomized analysis. Amortized analysis established a *worst case* bound for the performance of an algorithm irrespective of the inputs. It's most commonly used to analyse data structures, which have a persistent state throughout the program.

One of the most common examples given is the analysis of a stack with a multipop operations that pops $k$ elements. A naive analysis of multipop would say that in the worst case multipop must take $O(n)$ time since it might have to pop off all the elements of the stack. However, if you look at a sequence of operations, you'll notice that the number of pops can not exceed the number of pushes. Thus over any sequence of $n$ operations the number of pops can't exceed $O(n)$, and so multipop runs in $O(1)$ *amortized time* even though occasionally a single call might take more time.

Now how does this relate to C++ vectors? Vectors are implemented with arrays so to increase the size of a vector you must reallocate memory and copy the whole array over. Obviously we wouldn't want to do this very often. So if you perform a push\_back operation and the vector needs to allocate more space, it will increase the size by a factor $m$. Now this takes more memory, which you may not use in full, but the next few push\_back operations all run in constant time.

Now if we do the amortized analysis of the push\_back operation (which I found here) we'll find that it runs in constant amortized time. Suppose you have $n$ items and your multiplication factor is $m$. Then the number of relocations is roughly $\log\_m(n)$. The $i$th reallocation will cost proportional to $m^i$, about the size of the current array. Thus the total time for $n$ push back is $\sum\_{i=1}^{\log\_m(n)}m^i \approx \frac{nm}{m-1}$, since it's a geometric series. Divide this by $n$ operations and we get that each operation takes $\frac{m}{m-1}$, a constant. Lastly you have to be careful about choosing your factor $m$. If it's too close to $1$ then this constant gets too large for practical applications, but if $m$ is too large, say 2, then you start wasting a lot of memory. The ideal growth rate varies by application, but I think some implementations use $1.5$.
> 34 votes

# Answer
Although @Marc has given (what I think is) an excellent analysis, some people might prefer to consider things from a slightly different angle.

One is to consider a slightly different way of doing a reallocation. Instead of copying all the elements from the old storage to the new storage immediately, consider copying only one element at a time -- i.e., each time you do a push\_back, it adds the new element to the new space, and copies exactly one existing element from the old space to the new space. Assuming a growth factor of 2, it's pretty obvious that when the new space is full, we'd have finished copying all the elements from the old space to the new space, and each push\_back have been exactly constant time. At that point, we'd discard the old space, allocate a new block of memory that was twice as large again, and repeat the process.

Pretty clearly, we can continue this indefinitely (or as long as there's memory available, anyway) and every push\_back would involve adding one new element and copying one old element.

A typical implementation still has exactly the same number of copies -- but instead of doing the copies one at a time, it copies all the existing elements at once. On one hand, you're right: that does mean that if you look at individual invocations of push\_back, some of them will be substantially slower than others. If we look at a long term average, however, the amount of copying done per invocation of push\_back remains constant, regardless of the size of the vector.

Although it's irrelevant to the computational complexity, I think it's worth pointing out why it's advantageous to do things as they do, instead of copying one element per push\_back, so the time per push\_back remains constant. There are are least three reasons to consider.

The first is simply memory availability. The old memory can be freed for other uses only after the copying is finished. If you only copied one item at a time, the old block of memory would remain allocated much longer. In fact, you'd have one old block and one new block allocated essentially all the time. If you decided on a growth factor smaller than two (which you usually want) you'd need even more memory allocated all the time.

Second, if you only copied one old element at a time, indexing into the array would be a little more tricky -- each indexing operation would need to figure out whether the element at the given index was currently in the old block of memory or the new one. That's not terribly complex by any means, but for an elementary operation like indexing into an array, almost any slow-down could be significant.

Third, by copying all at once, you take much better advantage of caching. Copying all at once, you can expect both the source and destination to be in the cache in most cases, so the cost of a cache miss is amortized over the number of elements that will fit in a cache line. If you copy one element at a time, you might easily have a cache miss for every element you copy. That only changes the constant factor, not the complexity, but it can still be fairly significant -- for a typical machine, you could easily expect a factor of 10 to 20.

It's probably also worth considering the other direction for a moment: if you were designing a system with real-time requirements, it might well make sense to copy only one element at a time instead of all at once. Although overall speed might (or might not) be lower, you'd still have a hard upper bound on the time taken for a single execution of push\_back -- presuming you had a real-time allocator (though of course, many real-time systems simply prohibit dynamic allocation of memory at all, at least in portions with real-time requirements).
> 17 votes

---
Tags: algorithms, time-complexity, amortized-analysis
---


# Question
Title: Is it possible to decide if a given algorithm is asymptotically optimal?
Is there an algorithm for the following problem:

> Given a Turing machine $M\_1$ that decides a language $L$,
> Is there a Turing machine $M\_2$ deciding $L$ such that $t\_2(n) = o(t\_1(n))$?

The functions $t\_1$ and $t\_2$ are the worst-case running times of Turing machines $M\_1$ and $M\_2$ respectively.

What about space complexity?

# Answer
Here is a simple argument to show that they are undecidable, i.e. there are no algorithms to check if a given algorithm is optimal regarding its running-time or memory usage.

We reduce the halting problem on blank tape to your problem about running-time optimality.

Let $M$ be a given Turing machine. Let N be the following Turing machine:

$N$: on input $n$
1. Run $M$ on blank tape for (at most) $n$ steps.
2. If $M$ does not halt in $n$ steps, run a loop of size $2^n$, then return NO.
3. Otherwise, return YES.

There are two cases:

1. If $M$ does not halt on blank tape, the machine $N$ will run for $\Theta(2^n)$ steps on input $n$. So its running time is $\Theta(2^n)$. In this case, $N$ is obviously not optimal.
2. If $M$ halts on blank tape, then machine $N$ will run for constant number of steps for all large enough $n$, so the running time is $O(1)$. In this case, $N$ is obviously optimal.

In short:

$$M \text{ halts on blank tape } \Leftrightarrow N \text{ is optimial }$$

Moreover given the code for $M$ we can compute the code for $N$. Therefore we have reduction from halting problem on blank tape to running-time optimality problem. If we could decide if a given Turing machine $N$ is optimal, we could use the above reduction to check if a given machine $M$ halts on blank tape. Since halting on blank tape is unecidable your problem is also undecidable.

A similar argument can be used for space, i.e. it is also undecidable to check if a given Turing machine is optimal regarding the space it uses.

Even a stronger statement is true: we can't decide if a given computable function is an upper-bound on the time complexity of computing a given computable function. Similarly for space. I.e. even basic complexity theory cannot be automatized by algorithms (which can be considered a good news for complexity theorists ;).
> 10 votes

# Answer
As others mentioned the answer is no.

But there is an interesting article written by Blum "A Machine-Independent theory of the Complexity of Recursive Functions". He showed that **there are some functions with the property that no matter how fast a program may be for computing these functions another program exists for computing them very much faster**.

a very nice property!
> 2 votes

# Answer
Ha! Were the answer yes, we would be living in a different world.

Imagine that the answer to your question was yes (and of course we knew the algorithm $A\_0$ that would answer your question), then for any algorithm $A$ for language $L$, we would be able to tell (using $A\_0$) if $A$ is optimal or not.

Unfortunately, this is not possible, and indeed I personally think proving (non-trivial) optimality is the most interesting (and difficult) problem in computer science. As far as I know - I would be glad to be corrected - there exists no optimality result for any polynomial problem (except the trivial optimality results of course of algorithms taking time proportional to input size).
> -3 votes

---
Tags: complexity-theory, computability, undecidability, decision-problem
---


# Question
Title: Subtracting an integer from an ASCII number
Theoretically, if I were to subtract the number 10 from the ASCII character 10 (which is really 00110001 00110000), what would I get?

Does the computer add both ASCII characters and subtract?

# Answer
> 0 votes
If you subtract the *integer* 10 from the *ASCII character (code)* for 'a' (which is decimal 61) you get the ASCII code for 'Q'.

If you are asking because of mysteriously looking expressions like `c - 'a'` (or `c - '0'`) (some C hacks are fond of those), they give the letter position of `c` (respectively the value of the digit `c`). Used for interesting stuff like `c - 'A' + 'a'` (uppercase to lowercase), or to translate a decimal ASCII string to integer:

```
p = string;
s = 0;
for(p = string; *p; p++)
        s = 10 * s + *p - '0';

```

# Answer
> 2 votes
It depends how exactly you do the subtraction. Depending on the processor, the string 10 is either 0x3031 (little endian) or 0x3130 (big endian). Most modern processors are little endian. That's assuming you regard 10 as a 16-bit integer, i.e. a C short on modern computers. If you're regarding it as a C char, then only the first digit 1 will be affected.

---
Tags: binary-arithmetic
---


title: Pool of photos for term extraction

text:
# Question
Title: Pool of photos for term extraction
I need a pool of photos (if possible with description) for my project. I mainly have to perform term extraction for semantic searching. Is there something available out there that is made available for such kinds of thing?

I'm going to mine the description of these photos, maybe build ontologies and then perform search on them. The result of the mining might give useful terms about the pictures.

# Answer
One good way is to use Flickr. For your project you could use available API for downloading photos with related information.

If you are using Java you could use the classes on Google Codes.
> 1 votes

---
Tags: machine-learning, data-mining, data-sets, ontologies
---


# Question
Title: How can $ww = www$ hold for any word $w$?
Speaking in terms of automata and regular languages, how would it be possible for a string repeating some $w$ twice equal a string repeating that same $w$ thrice? That is, why is the language

$\qquad L = \\{w \in \Sigma^ * \mid ww = www\\}$

not empty? The only thing I can think of is $w = abab, ww = abababab, www = abababababab$, but I don't think this is correct.

# Answer
The only way that $w w = w w w$ is that $w = \epsilon$. Algebra of strings (for mathematician types, the free monoid on $\Sigma$) isn't *that* different from multiplication...
> 6 votes

# Answer
A string of length $2$ cannot be equal to a string of length $3$. But a string constructed by concatenation of $2$ strings may be equal to a string constructed by concatenating $3$ strings. The empty string (denoted by $\epsilon$) is of length = $0$ and it's a member in $\Sigma^\*$. If $w$ is chosen to be the empty string, then $\epsilon \epsilon = \epsilon \epsilon \epsilon$.

This is true because for any string $w$, $w\epsilon$ = $\epsilon w$ = $w$.
> 4 votes

# Answer
It can be possible because of the empty string $ \epsilon$ which is a part of $\Sigma^\*$
> 3 votes

---
Tags: formal-languages, regular-languages, automata
---


# Question
Title: Convergence of Simulated Annealing Based Algorithms
I designed a simulated annealing-based optimization algorithm. My simulation shows that it converge fast. I am looking for some sort of proof to show that simulation annealing-based algorithm converge fast (based on satisfying some properties) to global/local optimal point and doesn't oscillate in the optimal points (or any related fast about its stability). Are there any useful literature about it?

# Answer
I copied this answer from computational science

There is a theorem that syas that a black box algorithm is guaranteed to find the global minimum of an arbitrary smooth (i.e., twice continuously differentiable) function if and only if it samples points densely in the search space.

Here dense is meant in the topological sense, i.e., it must sample points in arbirarily small neighborhoods of every point.

In this case, the worst case complexity is O((dδ)−n), \[the Latex parser chokes with nested big brackets\] where d is the diameter of the search space and δ the guaranteed error in x

Edit: While this looks like being the worst case complexity for locating an **δ-accurate x** rather than for locating a point for a **ϵ-accurate f**, the complexity for the latter is as bad (even for the rather big value of **ϵ=(ffirst−fglobal)/2)**, as one can easily construct a smooth function which interpolates all data points so far but takes much smaller values in the center of the largest open ball not containing one of the points evaluated.

Thus guaranteed convergence to a global minimum is worthless in practice. (For example, uniformly random search has a convergence guarantee to the global minimizer, whereas most practically fast algorithms don't have one.)

Note that simulated annealing usually performs much worse than modern methods. Rather use code recommended in:

Comparison of derivative-free optimization algorithms (2012, by Nick Sahinidis)

Black-Box Optimization Benchmarking (BBOB) 2012 (by Auger, Hansen, et al.)
> 1 votes

# Answer
If you want to learn about the theory behind simulated annealing, you should look for "Markov chain Monte Carlo". You might learn from this how the temperature (schedule) influences the convergence, how it can be monitored (or even controlled) and when you still can expect "progress" of a simulated annealing run.

Is it worth to study simulated annealing at all, given statements like: "Note that simulated annealing usually performs much worse than modern methods."? I don't know. Some global optimizers like the "DIRECT optimization algorithm" are easy to use without any fiddle parameters, and reliably find the global minimum. Other modern methods may perform better than simulated annealing, but come with many fiddle parameters, and may miss the global minimum if you don't set these correctly. This means that you often need some experience before you can effectively employ some great new optimization algorithm. The problem is that this state of affairs makes it difficult to evaluate which of a suite of different optimization algorithms is the best for your given problem, because you never know whether you used these algorithms correctly, and whether they would have performed better had you only...

I have used simulated annealing in practice. If I made a mistake in the problem formulation such that the resulting problem was not well conditioned, simulated annealing was unable to find the global minimum. (There are methods which are less affected by this.) Often it was possible to formulate the problem in a better conditioned form, and this normally solved the problem. (Here, "not well conditioned" just means that the largest eigenvalue of the Hessian divided by the smallest non-zero eigenvalue is big.)
> 1 votes

---
Tags: algorithms, reference-request, proof-techniques, optimization
---


title: How can SML infer types like this?

text:
# Question
Title: How can SML infer types like this?
Wikipedia says:

```
fun factorial n =
    if n = 0 then 1 else n * factorial (n-1)

```

> A Standard ML compiler is required to infer the static type int -\> int of this function without user-supplied type annotations. I.e., it has to deduce that n is only used with integer expressions, and must therefore itself be an integer, and that all value-producing expressions within the function return integers.

I don't understand how a compiler could infer this. It sounds like SML is essentially solving the halting problem for the `factorial` function, and showing that it only halts on positive integer inputs.

Am I missing something?

# Answer
> 8 votes
The classic Hindley-Milner type inference algorithm requires each literal value to be unambiguously inferable to a type: `0` is an `int`, while `0.0` is a `real`. Haskell's type system has been enhanced to include a certain kind of bounded polymorphism, so that `0` can have any type that is a number (more precisely, of any type that is an instance of the `Num` type class: `0` is of type `Num a => a`).

See the wikipedia article on Hindley-Milner for further details on the algorithm (the article explanations are much better than anything I could write on that topic).

# Answer
> 7 votes
I think it is important to realise what the type $\mathtt{int \rightarrow int}$ means and does not mean.

It does *not* mean that a program P having that type must return an integer, contrary to what the original poster said. Instead it means **if P terminates on a given input (of type int), P terminates by returning an integer.** This way the halting problem is not an issue.

In addition, well-typing guarantees that programs don't suffer run-time type errors even when not terminating.

The original Milner, Damas paper Principal type-schemes for functional programs is very readable. With 6 pages it's also short.

Finally, it is highly instructive, and not much effort, to implement a type-inferencer for a toy language. I recommend doing this to really understand how types work in programming languages.

# Answer
> 4 votes
Working with types is not as "hard" as working with values with respect to computability. You can know statically that a function will return a `bool` without knowing statically that it will return `true`, for example. Moreover, it's entirely possible and sometimes trivially easy to prove that a *specific given* function halts with a certain input, but this is a different problem than writing a general algorithm that determines whether or not *any* other given function will halt on an input.

With respect to how type inference works, let me recommend some sources which may help:

1. Unification on Wikipedia
2. Type inference on Wikipedia
3. Types and Programming Languages by Benjamin C. Pierce (chapter 22, especially)
4. Hindley-Milner method on Wikipedia.

The type inference algorithm happens essentially in two phases: constraint generation, and unification. During constraint generation, the AST of the program is traversed and a set of type constraints is generated.

For example, if somewhere in the program there is the application expression `myfun (3)`, the inference algorithm could infer that the type of `myfun` is $\tt{int} \rightarrow \alpha$. If in another part of the program the expression `4 + myfun(y)` is encountered, the constraint that `myfun` has type $\beta \rightarrow \tt{int}$ is generated. During the unification step, such constraints will be (successfully or unsuccessfully) unified. During this phase the set of constraints might include

* $ \tt{myfun} : \tt{int} \rightarrow \alpha$
* $ \tt{myfun} : \beta \rightarrow \tt{int}$
* $ \tt{y} : \tt{int}$
* $ \tt{y} : \beta$

From this set (really system) of constraints, we could infer that $\alpha = \tt{int}$ and $\beta = \tt{int}$, and everything would be consistent and the program would type check. It's possible for unification to fail, though, depending on what else is in the set of constraints.

---
Tags: compilers, functional-programming, type-theory, type-inference
---


# Question
Title: How to the examples for using the master theorem in Cormen work?
I'm reading Cormen's Introduction to Algorithms 3rd edition, and in examples of Master Method recursion solving Cormen gives two examples

1. $3T( \frac{n}{4} ) + n\log(n)$
2. $2T( \frac{n}{2} ) + n\log(n)$

For the first example we have $a=3$ and $b=4$ so $n^{\log\_4 (3)}=n^{0.793}$ and Cormen says that if we choose $\epsilon = 0.207$ then $f(n) = n\log(n) = \Omega(n^{\log\_4(3) + \epsilon})$

How? As I understand it if $\epsilon = 0.207$ then $\Omega(n^{\log\_4(3) + \epsilon})= \Omega(n)$ so we have $n\log(n) = \Omega(n)$ but it's not true; But he proves that $n\log(n) = \Omega( n^{\log\_4(3) + \epsilon} )$

And then he proves that for the second case $n\log(n)$ does not apply to masters method 3-rd case the same way as I prove above.

So could somebody explain me in detail how the third case of the master's theorem applies to $3T( \frac{n}{4} ) + n \log(n)$ but not to $2T( \frac{n}{2} ) + n\log(n)$.

# Answer
> 1 votes
I think you used that method wrong! As mentioned in master theorem case 3. In your case you should use case 3 which uses $\Omega$-notation which describes asymptotic *lower* bound. So the solution in the book is correct!

You used $O$-notations which is and asymptotic *upper* bound! Be careful about which cases in master theorem you are using!

To satisfy the second case you should also have $af(n/b) \leq cf(n)$ for some $c \< 1$ and large $n$. In your case, $f(n) = n \log(n)$. $a=3$, $b=4$ you should show that

$\qquad 3(n/4 \cdot \log(n/4)) \leq c n \log(n)$.

For large $n$ you could select $1 \geq c \geq 0.75$ which solves your equation.

# Answer
> 3 votes
First of all, please check what $O$ and $\Omega$ and the other Landau symbols mean; that should remove some of the confusion.

Note that $n \log n \in \omega(n)$, that is $n \log n$ grows *properly faster* than $n$, asymptotically. This can be seen by

$\qquad \lim\_{n \to \infty} \frac{n \log n}{n} = \lim\_{n \to \infty} \log n = \infty$.

By the same reasonining, though, $n \log n \in o(n^{1 + \varepsilon})$ for every $\varepsilon \in (0,\infty)$.

Therefore, $n \log n \in \Omega(n^\alpha)$ for all $\alpha \in \[0,1\]$, so in the example you can choose $\varepsilon$ arbitrarily so that $\varepsilon + \log\_4(3) \leq 1$. The authors pick one, namely the largest (up to dropped decimal places).

As has been noted, that does not conclude the proof that case three applies; you still have to check that $a f\left( \frac{n}{b} \right) \le c f(n)$ for some $c\>1$ and all $n\>n\_0$, $n\_0$ some natural number.

As for the second example, my above explanation shows that there is no $\varepsilon \> 0$ so that $n \log n \in \Omega(n^{\log\_2(2) + \varepsilon})$, so case three can not apply here. Note that $o(f) \cap \Omega(f) = \emptyset$ for all $f$.

---
Tags: asymptotics, recurrence-relation, master-theorem
---


# Question
Title: Give a grammar to show whether a language is regular or context-free
I have to generate a grammar for the language $L = \\{ w \in \\{ a, b\\}^\* \mid |w| \in 2\mathbb{N}, w \neq w^R\\}$ and give the type of the language.

I've generated the grammar

$\qquad \begin{align} S &\to aSa \mid bSb \mid aAb \mid bAa \\ A &\to abA \mid baA \mid aaA \mid bbA \mid \varepsilon \end{align}$

This grammar is a context free grammar. I now can say that $L$ is a context free language. But how can I say for sure that this language isn't regular ?

# Answer
Regular languages are closed under complement and intersection. The complement of $L$, intersected with the regular $\\{w : |w| \equiv 0 \pmod{2}\\}$ is the language of even palindromes. If you must, you can easily show that it is not regular using pumping lemma.
> 4 votes

# Answer
Your grammar is almost correct except for the fact that you cannot derive any word. Thus, it produces the empty language. However, as I said, the idea to produce a "difference" and then switch to another nonterminal is correct.

To prove that a language (no matter which one) is **not** regular, you can use the pumping lemma or, if you need it a little simpler, a proof by contradiction using a pumping argument.

Note, however, that the pumping lemma cannot be used to prove the converse.
> 1 votes

# Answer
Language categories are sets, and the context-free language set contains the regular language set. In other words, every regular language is context-free. It's useful to know that context-free contains LR, which contains LL, which contains regular.

Your language is regular because its definition conforms to the regular definition (strings that can be formed over an alphabet by applying the operations of concatenation, union, and closure).

There's an algorithm for converting a regular definition into a grammar. I believe that the algorithm would produce the following grammar for your language:

```
S -> aS
S -> bS
S -> ε

```

I'm not quite sure that the grammar you posted corresponds to the regular language definition. It's better to stick to proven stuff.
> -2 votes

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


# Question
Title: Show $x^y$ is a primitive recursive function
As this thread title gives away I need to prove $x^y$ to be a primitive recursive function.

So mathematically speaking, I think the following are the recursion equations, well aware that I am assigning to $0^0$ the value $1$, which shouldn't be, since it is an "indeterminate" form.

\begin{cases} x^0=1 \\ x^{n+1} = x^n\cdot x \end{cases}

More formally I would write: \begin{cases} h(0) = 1 \\ h(x,y+1) = g(y,h(x,x),x) \end{cases}

as $g(x\_1, x\_2, x\_3) = h\left(u^3\_2(x\_1, x\_2, x\_3),u^3\_3(x\_1, x\_2, x\_3)\right)$ and provided $h(x,y) = x \cdot y$ is primitive recursive.

Is my proof acceptable? Am I correct, am I missing something or am I doing anything wrong?

# Answer
> 1 votes
Supposing that $\times~(mult)$ is primitive recursive function. Then you could write:

$exp(x,y)={ x }^{ y }$

1) $exp(x,0)=x^0=1$

2) $exp(x,y+1)=x^{y+1}=(x^y)\times x=mult(exp(x,y),x)$

for $mult$ you could show that:

$mult(x,y)=x\times y$

1)$mult(x,0)=x \times 0=0$

2)$\operatorname{mult} \left({x, y + 1}\right) = x \times \left({y + 1}\right) = \left({x \times y}\right) + x = \operatorname{add} \left({\operatorname{mult} \left({x, y}\right), x}\right)$

and for addition $add$ the proof is straightforward.

Hope these are useful!

# Answer
> 1 votes
As I wrote in the comments, you haven't actually proved anything. If you want to prove that $x^y$ is p.r., you need to write it in the scheme form, and then you need to prove that indeed $x^y = f(y,x)$ for your defined $f$ for all $x$ and $y$ (by double induction).

Consider the following definition of $f(y,x) = x^y$:

$f(0,x) = s(z(x))$ (i.e., the successor of the constant zero function).

$f(y+1, x) = u^3\_1(u^3\_1(x^y, x, y) \cdot x, x, y)$.

I assume now that multiplication, $x \cdot y$ and wrote it infix, and obviously $x^y = f(y,x)$. The function $u^a\_b$ is the $a$-ary projection of $b$.

(Ps. if this doesn't work for you, please post your scheme you want to use, otherwise we cannot do else then guess.)

---
Tags: computability, recursion, check-my-proof
---


title: Algorithm books on a range of topics

text:
# Question
Title: Algorithm books on a range of topics
I've been tasked with building a library of books on algorithms for our small company (about 15 people). The budget is more than 5k, but certainly less than 10k, so I can buy a fair number of books. All people here have at least a Bachelor's degree in CS or a closely related field, so while I will get some basic textbook like Cormen, I'm more interested in good books on advanced topics. (I will get Knuth's 4 volumes, BTW.)

Some list of topics would be:

* Sorting algorithms
* Graph algorithms
* String algorithms
* Randomized algorithms
* Distributed algorithms
* Combinatorial algorithms
* etc.

Essentially I'm looking for good recommendations on books about major topics within CS related to algorithms and data structures. Especially stuff that goes beyond what's typically covered in algorithm and data structure classes as part of a Bachelor's degree at a good school. I know the question is quite fuzzy, since I'm looking for generically useful material. The software we develop is mostly system level stuff handling large amounts of data.

The ideal would also be to find anything that would cover fairly recent cool data structures and algorithms, which most people might not have heard about.

---

EDIT: Here are some preliminary books that I think I should get:

* Introduction to Algorithms by Cormen et al.
* Algorithm Design by Kleinberg, Tardos
* The Art of Computer Programming Vol 1-4 by Knuth
* Approximation Algorithms by Vazirani
* The Design of Approximation Algorithms by Williamson, Shmoys
* Randomized Algorithms by Motwani, Raghavan
* Introduction to the Theory of Computation by Sipser
* Computational Complexity by Arora, Barak
* Computers and Intractability by Garey and Johnson
* Combinatorial Optimization by Schrijver

A few other books my colleagues wanted that deal with techniques and algorithms for language design, compilers and formal methods are:

* Types and Programming Languages by Pierce
* Principles of Model Checking by Baier, Katoen
* Compilers: Principles, Techniques, and Tools by Aho, Lam, Sethi, Ullman
* The Compiler Design Handbook: Optimizations and Machine Code Generation, Second Edition by Srikant, Shankar
* The Garbage Collection Handbook: The Art of Automatic Memory Management by Jones, Hosking, Moss

# Answer
I have not (nearly) read enough books to name $5000 worth of them. Therefore, I will suggest some groups of literature you should cover as well as point you towards selected representatives. I can not claim to have read most of the books in full myself, so I have to rely mostly on descriptions, cursory impression and reputation. I have looked into or worked with most of them to some extent, or had them recommended by experts.

I assume that you want your people to learn what can be done, and how to do it, as opposed to learning what they can't do. In particular, I will leave out books about computability and complexity theory as such; I expect your people to have taken away the relevant messages from their undergraduate education.

* **The Basics**
Even though your people have learned them at some point, expect them to look up the basics. Since sources like Wikipedia are frequently substandard or outright wrong, you want to get them proper reference texts.

Popular choices include

+ Introduction to Algorithms by Cormen, Leiserson et al.
    Very broad introduction that covers many elementary algorithms and data structures as well as basic analysis techniques. A standard text used frequently for teaching purposes and available in its 3rd edition (so most mistakes should have been purged by now). Lots of exercises.
    + Algorithms by Sedgewick and Wayne
    Another standard text in its fourth edition. Less broad than Cormen, but with more attention to implementation details. Lots of material online, including a free course on Coursera. Lots of exercises.
    + Introduction to Algorithms -- A Creative Approach by Udi Manber
    Also rather slim a selection of topics, but presented with attention to didactics. The focus is on *inductive* strategies. Contains lots of exercises and solutions (or at least hints) for some. A good secondary reference if you don't like the recommended textbook because of its unusual style.
    + Concrete Mathematics by Graham, Knuth and Patashnik
    Covers discrete mathematics as relevant to algorithm analysis. Rare in its focus on computer science needs *and* rigor. Very high quality. Lots of exercises with solutions.
* **Analysis of Algorithms** In most standard text books, analysis of algorithm usually stops at the level of $O$-asymptotics and RAM model. In order to estimate real-world efficiency more reliably, it can be necessary to investigate runtime more precisely and consider effects like memory hierarchy and communication.
* **Advanced Surveys**

+ Purely functional data structures by Okasaki
    Classic and basic literature often focuses on the procedural paradigm. If you want to work in the functional paradigm, new techniques for efficient data structures are needed. This book is a detailed overview over the area.
    + Advanced Data Structures by Brass
    Sometimes, the basic techniques are not enough. This is an overview over advanced data structures, with code and many references.
    + Algorithmics for Hard Problems by Hromkovič
    Complexity theory tells us (as practitioners) not to bother looking for exact yet efficient algorithms for many natural problems. There are plenty of techniques for practically solving these problems; this text shows you how.
* **Specialised Literature**

+ Compilers: Principles, Techniques, and Tools aka The Dragon Book by Aho et al
    Should you ever need to build or tinker with a compiler, this is *the* standard text on the area.
    + Network Flows: Theory, Algorithms, and Applications by Ahuja
    Many problems can be modeled as network flow problems; this book gives you a full coverage of the field.
    + Probabilistic Graphical Models by Koller and Friedman
    Graphical models are a major tool in modeling scenarios for machine learning (among others) probabilistically. This is a comprehensive overview about the complex. There is a related free online course.
    + Handbook of Exact String Matching Algorithms by Charras and Lecrog
    String matching is an ever important task when dealing with data. This book lists most (if not all) relevant algorithms for the job, including high-level descriptions as well as implementations.
    + Analytic Combinatorics by Sedgewick and Flajolet
    The deep mathematical dive after "An Introduction to the Analysis of Algorithms" by the same authors. Not for everybody, but gold for the interested.
    + Algorithms on Strings, Trees and Sequences by Gusfield
    Should you ever have to deal with huge amounts of string data (in particular in biology contexts) this is the go-to book as it provides an overview over the relevant data structures and algorithms.
* **For the Practitioner**

+ Patterns for Parallel Programming by Mattson et al.
    In practice, you might want to utilise multiple machines to deal with large problems. This book is a high-level, example-driven overview over ways to do so, that is how to organise and move data and computing agents. It also addresses ways to implement them with existing tools.
    + A Guide to Experimental Algorithmics by McGeoch
    When theoretical analysis is too hard or too coarse, you have to perform experiments. This is an introduction into how to properly design experiments on algorithms.
    + The Definitive ANTLR 4 Reference by Parr
    You often need domain specific languages and tools to parse them. ANTLR is a mature and convenient compiler generator, and this is the book best suited for learning how to use it. Parr also has some other books on DSLs worth checking out.

If you want very recent material, you should consider getting your people access to journals and conference proceedings, maybe by cooperating with a university library. You can also actually let them attend conferences on topics relevant to them resp. your company.

Also, consider asking your people. Have them do their own research (including free samples or copies on the web or libraries) and they will tell you which books they consider relevant to their work. There is no use in buying stuff no one will read.
> 18 votes

# Answer
Here is a random collection of books on advanced algorithms based on what I consider as great book about advanced algorithms. Of course this is only my personal opinion and there are many other good books.

* Approximation Algorithms by Vijay V. Vazirani
* The Design of Approximation Algorithms by David P. Williamson, David B. Shmoys
* Computational geometry: an introduction through randomized algorithms by Ketan Mulmuley
* Randomized Algorithms by Rajeev Motwani, Prabhakar Raghavan
* Algorithms on Strings, Trees and Sequences by Dan Gusfield
* Combinatorial Optimization by William J. Cook, William H. Cunningham, William R. Pulleyblank, Alexander Schrijver

you should definitely consider the Kleinberg/Tardos book, which is just a great textbook.

Also you should know that on certain topics there are "handbooks" which give an encyclopedic overview over a field (for example the Handbook of Computational Geometry). edited by J.R. Sack, J. Urrutia. Notice that these handbooks are pricy. So buying them might help you to spend the 5k.
> 4 votes

# Answer
You don't specify what your company specializes in, so it's not easy to provide more than general recommendations. On the whole, I think the list you've put together is pretty good, and I wouldn't remove anything from it. Just a couple of additions and comments:

1) Cormen is a standard text. Sedgewick is another standard text. I've always gotten more out of Sedgewick but YMMV. You seem to have the budget. Buy both.

2) I don't have a copy of "The Garbage Collection Handbook" but I do have a well-thumbed copy of Jones&Lin's earlier survey on garbage collection. If you intend to do any sort of automated memory management, you should definitely buy this one.

3) You've also got several useful books on parsing and automata theory, but you're missing the two books (three volumes) which I've found most useful: Sippu & Soisalon-Soisinen's *Parsing Theory*, and Dick Grune's *Parsing Techniques, a Practical Guide*. The first is a great overview of the theory, and the second an exhaustive overview of the practice. (By all means, get the dragon book, too. But I'll bet you'll end up using Grune more.)

4) Every library on data structures requires a copy of Okasaki's "Purely Functional Data Structures". I don't think I've ever read any book this slim with so many interesting ideas.

5) I don't own a copy of Maxime Crochemore's "Algorithms on Strings", but I wish I did. Highly practical, lots of useful ideas.

* Algorithms in C++/Java/C (select one), Third Edition by Robert Sedgewick. Two volumes. Addison-Wesley, 2001.
* The Garbage Collection Handbook by Richard Jones, Antony Hosking and Eliot Moss.
* Parsing Theory, by Seppo Sippu and Eljas Soisalon-Soininen. Two volumes: Vol . 1 Languages and Parsing; Vol. 2 LR(k) and LL(k) Parsing. Springer, 1988.
* Parsing Techniques, A Practical Guide, Second Edition by Dick Grune and Ceriel J.H. Jacobs. Springer, 2008.
* Purely Functional Data Structures by Chris Okasaki. Cambridge, 1998.
* Algorithms on Strings by Maxime Crochemore, Christophe Hancart, Thierry Lecroq. Cambridge, 2007.
> 4 votes

---
Tags: algorithms, reference-request, data-structures, books
---


title: Choose a "middle" point from a set

text:
# Question
Title: Choose a "middle" point from a set
I read a post which talks about pretty much the same problem. But here I simplify the problem hoping that a concrete proof can be offered.

There is a set $A$ which contains some discrete points (one-dimensional), like $\\{1, 3, 37, 59\\}$. I want to pick one point from $A$ which minimizes the sum of distances between this point and others.

There may be lot of posts out there, and my problem is just the one-dimensional version of those. I know how to prove it if $A$ is not discrete, but I fail when $A$ is discrete like above.

Please answer with a concrete proof.

# Answer
For a point $x$, let $d(x)$ be the sum of distances between $x$ and points in $A$. For $x \notin A$, the derivative $d'(x)$ has the nice formula $$ d'(x) = |\\{y \in A : y \< x\\}| - |\\{y \in A : y \> x\\}|. $$ This shows why the median is the best answer when you don't have to select a point from $A$. For a point $x \in A$, $d(x)$ is the same as your objective function, hence the solution is to choose the median. You can find the median in linear time, as described in Wikipedia and various other resources.
> 2 votes

---
Tags: algorithms, computational-geometry
---


title: Slow MIS Distributed Algorithm

text:
# Question
Title: Slow MIS Distributed Algorithm
I am interested in precise time complexity of distributed algorithm for finding MIS (Maximum Independent Set) of a given graph $G$.

I investigate the Slow MIS distributed algorithm (from these lecture notes, page 2).

Following is the more detailed version than in lecture notes.

* Every node sends its UID to it's neighbors.
* Run procedure join

**on event**: getting a message *decide(1)* from a neighbor $w$ do

* Set $b = 0$ - flag that node terminates and not participating in further phases.
* Send *decide(0)* to all neighbors

**on event**: getting a message *decide(0)* from a neighbor $w$ do:

* Invoke procedure **join**.

Procedure **Join**

if every neighbor $w$ of $v$ with a larger identifier has decided $b(w) = 0$, then do

* Set $b = 1$.
* Send *decided(1)* to all neighbors.

The question is what's time complexity of the algorithm $\Theta(n)$ or $\Theta(D)$, where $D$ is a diameter of $G$.

In the lecture notes linked above, they say that time complexity is $O(n)$. I think that in our case it can be expressed as $\Theta(D)$ (simultaneously $O(D)$ and $\Omega(D)$) for special cases.

The problem is how to prove that that time complexity in general is $O(D)$ and there are special cases when time complexity is $\Omega(D)$ if it's right at all.

Let's take a look at the example I have in mind.

$D=1$ and $n=4$, and as I understood the algorithm every vertex will decide to join MIS on the first round.

If you have an idea how to show that, please, share it with us.

# Answer
> 2 votes
It is not actually the diameter. It is the longest chain in the partial order $P$ of the input graph $G = (V,E)$. The poset $P$ is constructed as follows. Given an input graph $G = (V,E)$ such that each vertex has a unique identifier. Build an oriented graph $G' = (V,E')$ such that an edge $(u,v) \in E'$ if $(u,v) \in E$ and $u \succ v$. Then build a partial order $P$ of $G'$ by taking the transitive closure of $G'$. Let $l$ be the length the longest chain of $P$, then the time complexity of your algorithm is exactly $l$ (assuming here that the time complexity is measured by the number of communication rounds and in each round a node can send/receive a message to/from all its neighbors). Note that $l$ is $\in O(n)$ and in $\Omega(1)$.

**What about average complexity ?** Let's $G(n,p)$ be a random graph of $n$ vertices and an edge between any pair of nodes exist with probability $p \in \[0,1\]$. Then, if you build a partial order $P$ of this graph (called *random graph order*), you will find that the longest chain $l$ is in $\Theta(n)$. This result is proven in \[1\].

\[1\]: Albert, Michael H., and Alan M. Frieze. "Random graph orders." Order 6.1 (1989): 19-30.

**(This is for additional knowledge)** It is possible that assigning identifiers on the input graph such that the complexity of this MIS algorithm is minimized (that is, minimize $l$). The problem is NP-Hard as it is reducible to minimum coloring. This NP-Hard problem was given in: \[2\] and \[3\].

\[2\]: Deming, R. W. "Acyclic orientations of a graph and chromatic and independence numbers." Journal of Combinatorial Theory, Series B 26.1 (1979): 101-110.

\[3\]: Chvátal, Vašek, and Carsten Thomassen. "Distances in orientations of graphs." Journal of Combinatorial Theory, Series B 24.1 (1978): 61-75.

**(Ok this is just for fun, and you can skip it)** Now assume that you want to measure time with a different metric. And let's add a restriction to the definition of communication rounds (found in \[4\]). And let's say that a node 1) can send a message to *only* neighbor in a communication round, and 2) can receive a *messages* (more than one) from all its neighbors In such case, the order that a node follow to send a message to its neighbors will affect the time complexity. Let's consider three strategies that a node $v$ follows to visit its neighbors (with smaller identifiers) which are $\\{u \_1, ..., u \_k\\}$ such that $u \_i \succ u \_j$ if $i \> j$. Then:

* Strategy 1: $v$ sends messages in an order from $u \_k$, to $u \_{k-1}$ ..., $u \_1$ etc .. . This strategy leads to $\Theta(n)$ time complexity.
* Strategy 2: $v$ sends messages in an order from $u \_1$, to $u \_{2}$ ..., $u \_k$ etc .. . This strategy leads to $\Theta(n^2)$ time complexity.
* Strategy 3: $v$ sends messages to its neighbors in a uniformly random order. This strategy will also lead to $\Theta(n^2)$ in expectation.

(Why I am interested in all that ?) - because it was found in some practical wireless networks (Bluetooth networks), that this slow MIS algorithm is the *fastest* although not being the theoretically fastest one. It was found that this type of networks follow the modified communication model I defined above.

\[4\]: Peleg, David. Distributed computing: a locality-sensitive approach. Vol. 5. Society for Industrial Mathematics, 1987.

---
Tags: algorithms, time-complexity, distributed-systems
---


# Question
Title: MinHeap represented by an array - two simple statements
I'm trying to prove/disprove two statements. I just want to make sure with you I'm on the right line.

These are the following statements:

**Preface :** Let A\[n\] be an array of min-heap (a min-heap represented by an array\], whereas all the elements in the heap are different from each other. Let i and j be two indexes in the range : $0 \le i, j \le n-1$.

***Prove or disprove :***

1. If $i \< j $ then $A\[i\] \< A\[j\]$
2. If $A\[i\] \< A\[j\] $ then $i \< j$

I believe I managed to disprove both of them using the following heap:

$\qquad \[2, 6, 7, 11, 14, 13, 12, 12, 13,15, 16, 71, 72, 13, 81\]$

For:

1. Simply plug in the following indexes: $i = 4$ and $j = 13$.

So $i \< j$ but $A\[i\] \> A\[j\]$.
2. Simply plug in the following indexes: $i = 13$ and $j = 4$.

So $A\[i\] \< A\[j\]$ but $i \> j$.

Am I missing something here? Or It is really that easy?

# Answer
You're not missing anything, this problem really is that easy. Your solution works, but I feel like I should point out that you can disprove both statements with a much smaller heap. In particular

\begin{array}{} \[2, 7, 6\] \end{array}

with $i = 1$ and $j = 2$ for the first statement and swapping them for the second.

Furthermore, I'm pretty sure those two statements only hold if the array is sorted (assuming distinct elements).
> 4 votes

---
Tags: data-structures, binary-trees, arrays, heaps
---


title: Transform inverse result

text:
# Question
Title: Transform inverse result
let us assume that:
**f** is a grayscale image of size NxN, and **F** is the Fourier transform of **f**.
**G** is a 2Nx2N transform obtained by inserting 0 between every value in **F**:

What is the inverse transform of **G**?

solution: so i have programmed it, and the picture will be 4 times bigger with the picture 4 times in it. g= \[f f;f f\] can you please explain why this is the answer?

# Answer
> 2 votes
Think of it the other way around.
If you duplicate an image then you get zeros in between the transform ( This can intuitively be explained:
duplicating an image is like convolving with 2 deltas (comb) of wavelength 1/2 the new image size.
so is equivalent under convolution theorem to multiplying with comb of freq size of image / 2 which gives a comb with delta every other pixel -\> every other pixel is zero.

---
Tags: image-processing
---


# Question
Title: General start rule question for a context free grammar
Suppose I have a context free grammar described:

> $S \rightarrow 0SS1$
> $S \rightarrow 1$
> $S \rightarrow \epsilon$

Because the first rule is considered the start rule does that mean that this grammar could never generate a string that starts with 1 or can you apply the second $S$ rule first to generate the string?

# Answer
Yes you can apply the second rule you have written if you'd like. Since $S$ is your start symbol, you can apply any of its productions when you begin. It might be clearer if you wrote it as follows (where $|$ denotes or):

> $S \rightarrow 0SS1 \\; |\\; 1 \\; | \\; \epsilon$
> 3 votes

---
Tags: context-free
---


title: NAE SAT reduction to weighted MAX CUT

text:
# Question
Title: NAE SAT reduction to weighted MAX CUT
I am trying to reduce NOT-ALL-EQUAL SAT to MAX-CUT with weighted edges.

I know that if there are weights to the edges, then I can reduce NOT-ALL-EQUAL SAT to MAX CUT by have a $G$ with $2n$ nodes ($x\_i$ and $\bar{x}\_i$) and edges between the nodes based on each clause. And, adding edges between $x\_i$ and $\bar{x}\_i$, so on. But, I am not sure how to assign weights if I have to reduce a NOT-ALL-EQUAL SAT to weighted MAX CUT.

How should I go about this problem?

# Answer
NAE-SAT is clearly in NP, while MAX-CUT is NP-complete. So by the definition of NP-complete, there is some reduction from NAE-SAT to MAX-CUT.
> 1 votes

---
Tags: complexity-theory, reductions
---


# Question
Title: Can you specify a programming language without implementation?
Is it theoretically possible to specify a programming language for which no implementation could exist? A programming language is a way of defining functions. An implementation means a method to execute a given program in that language on a given input to the output of the function corresponding to the program on that input.

What is are the minimal requirements of such a language?

# Answer
> 7 votes
Usually, implementing a programming language is at least giving a interpreter in a language (or a compiler to a language) that is no more than Turing-complete.

Using this "definition" we can specify a programming language like this:

* there only one possible program that is `HALT`;
* specification of `HALT`: it is a function that solve the halting problem.

Implementing this programming language requires solving the halting problem with the implementation. (Which is impossible since our implementation should not be more powerful than a Turing machine).

Specification handles logic and thus can ask for a lot more. Another specification that will be impossible to implement is "false". (Or any contradictory sentence in the specification) But this does not feels like a specification, which is why I used the halting problem example.

# Answer
> 4 votes
Just a curious side note: the C++ template engine is Turing-complete

**Theorem 1:** *In the absence of instantiation bounds, C++ templates are Turing-complete.*

**Corollary 1:** *In the absence of instantiation limits, whether a C++ compiler will halt when compiling a given program is undecidable.*

... so the C++ itself can be considered a programming language for which no "implementation" could exist ... :-D

# Answer
> 2 votes
It is unclear what you mean by a "programming language" and "an implementation of a language". You need to provide rigorous definitions of these two to get an answer.

A "programming" language for computing a (partial) functions over strings can be considered a mapping from $\Sigma^\*$ to $2^{\Sigma^\*}$. As long as one of the uncomputable functions is in the range the language cannot be implemented.

For example, one can take first-order arithmetic. Then it is easy to define functions that are not computable, e.g. the function that given a TM $M$, decide if $M$ returns $0$ on all inputs. This can be easily expressed by a first order formula in the language of arithmetic. On the other hand it is an easy result in computability theory that it is not a computable function, so there can be no implementation of the function.

But this is not the kind of specification language that people mean when they use the phrase "programming language". A programming language is typically meant to be a language to express computable functions (processes,...) and to communicate the instructions to a machine and therefore there is a TM that can simulate those its programs and output their results. So in a sense having a programming language which cannot be implemented is not meaningful.

(My guess is that you are probably confusing programming languages either with specification languages or with formal languages. In any case, we can define languages that are not computable.)

# Answer
> 1 votes
There have been plenty of languages specified without an implementation, e.g. Algol 60 was supposed to be a language for writing up algorithms, not to be implemented. Some of the many "just for fun" languages were specified long before an implementation came along, Intercal comes to mind.

---
Tags: formal-languages, computability, programming-languages
---


title: Dfs algorithm and cycles question

text:
# Question
Title: Dfs algorithm and cycles question
Is it true or false that for running a dfs on an undirected graph G with a simple cycle than this cycle will have exactly one back edge?

Looks to me likes its true ,is it?

# Answer
No, it is not true. Consider the graph with vertices 1, 2, 3, 4, 5, 6 and edges 12, 23, 34, 45, 46, 56, 61. The dfs starting at vertex 1 yields two back egdes for the cycle (1,2,3,4,6).
> 1 votes

---
Tags: algorithms, graphs, search-algorithms, graph-traversal
---


# Question
Title: Why is binary subtraction referred to as the invert-add-shift-add method?
I'm being asked this question for my computer conceptes class, can't find anything about this in my text book, and have only been able to find half-baked answers googling it.

Why is binary subtraction referred to as the invert-add-shift-add method?

# Answer
I found an excellent answer here, which I summarize below.

Given two number $A,B$ in binary notation, we calculate $A-B$ by adding to $A$ the two's complement of $B$. Since the two's complement of $B$ is formed by inverting all bits of $B$ and adding $1$, one way to implement this idea is *invert* $B$, *add* the result to $A$, *shift* the carry $1$ bit (which will appear if $A\geq B$), and *add* it (i.e. $1$) to the result.
> 5 votes

---
Tags: binary-arithmetic
---


title: Speech vs Music classification

text:
# Question
Title: Speech vs Music classification
I want to determine which parts of an audio file contain speech respectively music.

I hope someone has a made something like this or can tell me where to start. Can you please suggest some method or tutorial for doing the same?

# Answer
The appropriate technique is machine learning. Some keywords you could search for are "music speech discrimination", and you could look at this survey. (These pointers came from Vor's comment.)
> 2 votes

# Answer
If you have many data ( large number of audio pieces with human labels), I would suggest you try Deep Convolutional Neural Networks. But I think there should be a much more direct way than that, since I believe the spectrum could be a very good feature for discriminate decisions.
> 0 votes

---
Tags: reference-request, pattern-recognition
---


# Question
Title: Is matching with mismatches a special(parametrized) case of Closest String problem?
I am a bit confused. Somehow I have a problem connecting two problems together. The Closest String problem and the problem of matching with mismatches. They seam to be related but, I fail to see the connection. The Closest String problem is defined as :

> *Instance:* Strings $S\_{1},S\_{2}...S\_{n}$ over alphabet $\Sigma$ of length $L$ each and a non-negative integers $d$ and $n$.
>
> *Parameters:* $n,d$
>
> *Question:* Is there a string $s$ of length $L$ such that $\delta(s,S\_{i})\leq d$ for all $i=1..n$?

Note: $\delta(x,y)\leq d$ is the Hamming distance between $x$ and $y$.

This problem is proven to be NP-complete.

On the other hand we have a problem of matching with mismatches, which is described as:

> The problem of string matching with $d$ mismatches consists of finding all occurrences of a pattern of length $m$ in a text of length $n$ such that in at most $d$ positions the text and the pattern have different symbols. In the following, we assume that $0 \< d \< m$ and $m\leq n$.

Landau and Vishkin gave the first (to my knowledge) efficient algorithm to solve this problem in $O(kn)$ time.

Now my question is:

Is matching with mismatches, or can it be seen, as a special parametrized case of the Closest String problem and how is this connection made?

# Answer
> 1 votes
In the latter you are given the string $s$ that you are looking for in the former.

An algorithm for the first one is to search for a string $s$ (try all strings) and run the latter procedure and verify that the set you get is the entire set.

---
Tags: np-complete, decision-problem, matching
---


# Question
Title: Regular expression for binary words with few zeros
What is the regular expression for the set of binary strings with the property that

1. every $0$ is followed by *exactly* $m$ times $1$ and
2. every $0$ is preceded by *at least* $n$ times $1$?

$m$ and $n$ are integers.

# Answer
@SamM's answer isn't completely right. Yes, it is $(01^m)^\*$ for "each zero is followed by exactly $m$ ones", but this can't just be combined with "at least $n$ ones before". And a string of only ones complies always. So consider the ones between two zeroes:

* If $m \< n$, you can't comply with both conditions, so the language is just $1^n 1^\* 0 1^m \mid 1^\*$
* If $m \ge n$, the only way to comply in between zeroes is to have $m$ ones there, so the language is $1^n 1^\* (0 1^m)^+ \mid 1^\*$
> 2 votes

# Answer
Vonbrand already provided an answer for the case where the strings are defined over $\\{0,1\\}$. I'm considering the larger alphabet $\\{0,1,2\\}$ (this can easily be extended to any other alphabet, $2$ basically stands for anything but a $0$ or a $1$).

The answer still depends on $n$ and $m$

* If $m\<n$, you need separators between blocks of $1^\*1^n01^m$: $$(1|2)^\*\quad\left(1^n01^m2(1|2)^\*\right)^\*\quad(1^n01^m)^?$$
* If $m\>=n$, you either have a separator (and thus a new sequence of at least $n$ $1$s) or you don't: $$ (1|2)^\*\quad\left(1^n\left(01^m\left(2(1|2)^\*1^n\right)^?\right)^\*\right)^?\quad\left(2(1|2)^\*\right)^? $$
> 1 votes

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


title: Unbiasing of sequences

text:
# Question
Title: Unbiasing of sequences
There is the well-known method of unbiasing of bit sequences due to von Neumann. Are there similar schemes applicable to other sequences, e.g. the result of throwing a normal die?

# Answer
The following simpler adaptation of von Neumann's trick is more efficient than the one described in HdM's answer. Throw your die twice. If the two answers $x,y$ are different, write $0$ if $x\<y$ and $1$ if $x\>y$. This way, you get an unbiased bit source. If you are so inclined, you can use this bit source to simulate fair die throws.
> 4 votes

# Answer
You can generalize the von-Neumann procedure canonically. Assume you have a discrete RV $X$ which you want to make fair, i.e., each event in the event space $\Omega$ of $X$ shall occur with the same probability. Then you can redraw $X$ exactly $n:=| \Omega|$ times, yielding $x\_1, \ldots, x\_n$. In case $x\_1 \not = \ldots \not = x\_n$, you return $x\_1$. Otherwise, you repeat the above procedure.

Since the probability of drawing $x\_1, \ldots, x\_n$ differently is just a product of probabilities, the order of the elements does not matter. Hence, the probability of drawing an element $x$ at position $1$ is just $1/n$.
> 3 votes

# Answer
It seems to me that presumably the only viable satisfactory solution would be: Obtain a bit sequence from the sequence from the die, apply the von Neumann unbiasing, then generate from that a sequence for the die.
> 0 votes

---
Tags: reference-request, probability-theory
---


title: Validity of predicate logic formulas

text:
# Question
Title: Validity of predicate logic formulas
The following predicate logic formula is invalid (*i.e.* not a tautology):

$\Bigl\[\forall x \\,\exists y {\\,.\\,} P(x,y)\Bigr\] \implies \Bigl\[\exists y \\, \forall x {\\,.\\,} P(x,y)\Bigr\]$

Which of the following are counter-models (*i.e.* counterexamples) for it?

1. The predicate $P(x,y) \equiv \bigl\[ y \cdot x = 1 \bigr\]$, where the domain of discourse is $\mathbb{Q}$.
2. The predicate $P(x,y) \equiv \bigl\[ y\<x \bigr\]$, where the domain of discourse is $\mathbb{R}$.
3. The predicate $P(x,y) \equiv \bigl\[ y \cdot x = 2 \bigr\]$, where the domain of discourse is $\mathbb{R} \smallsetminus \\{ 0 \\}$.
4. The predicate $P(x,y) \equiv \bigl\[y \\,x \\,y = x\bigr\]$, where the domain of discourse is $\\{0,1\\}^\ast$
— that is, the set of all binary strings, including the empty string).

**Is my answer below true ?**

**Answer:** I think the first model is not a counter model since 0 is a member of rational numbers there exists no rational y for which $x \cdot y = 1$. So $\forall x \\,\exists y {\\,.\\,} P(x,y)$ is false, thereby validating the conditional for this choice of predicate $P$. Also sentence 4 is not a counter model. The other two are counter-models.

# Answer
> 2 votes
1. Not a counter model, for as you say, the antecedent is not true when $x = 0$.
2. A counter model: Every number has a number less than it in $\mathbb{R}$, however there are no least number.
3. A counter model: For $x$, let $y = 1/x$, so the antecedent holds, there is no $y$ such that for all $x$, we have that $x \cdot y = 2$.
4. Not a counter model: The consequent is always true, let $y = \epsilon$, then for all $x$, it holds that $yxy = x$.

---
Tags: logic, logical-validity
---