title: Description of shape in a vector form

text:
# Question
Title: Description of shape in a vector form
I would like to ask for references to algorithms that can project shape information about an object to 1 dimension. Specifically I am training a neural network to be able to identify objects with similar shape as the ones in the training set. The objects in my case are molecules for which the positions, masses and radii of the atoms are known. So far I have used information about the interatomic distances. The shape of the molecule is characterized by the distributions of atomic distances to four strategic reference locations. In turn, each of these distributions is described through its first three moments. In this way, each molecule has associated a vector of 12 shape descriptors. E.g.

shape = \[5.263145206201491, 2.374050283937628, 0.5667128412399703, -0.9294169868091768, 5.248610806623028, 2.540858433874688, 0.6060854720036649, -0.8149532304046945, 10.186033275946016, 5.224912272773887, -0.5637327938909833, -1.1097296046204561\]

However, a 12-element feature vector is too small to describe accurately the molecular shape. I tried to add more reference location and consequently more atomic distances but I noticed no gains in accuracy. Is anyone aware of any other algorithm that can express the molecular shape in a feature vector form? Please point me to references if you know.

# Answer
> 0 votes
There's lots of work in the computer vision community on "shape descriptors". This might or might not be useful. See e.g., https://en.wikipedia.org/wiki/Shape\_analysis\_(digital\_geometry), https://en.wikipedia.org/wiki/Shape\_context, https://en.wikipedia.org/wiki/Image\_moment, https://en.wikipedia.org/wiki/Spectral\_shape\_analysis.

---
Tags: computational-geometry, computer-vision, features
---


# Question
Title: Scoring metric for machine learning method
For a machine learning method `X` (Deep Neural Nets variant), which performs classification tasks.

In the output layer, for every label method, `X` also emits the uncertainty `U` associated with the respective prediction.

So, in case the testing dataset is very different then the predictions made by `X` should have a high `U`. (Mean of `U` across all labels should be high)

In the case of testing, the dataset is indeed from the same source from which training dataset was generated. For true positives, the mean of uncertainty for the correct label would be low. In the case of false positives, the mean of `U` would be high (ideally).

What is the principled approach to measuring the effectiveness of method `X` in outputting the uncertainty? In other words, what would be a good metric to understand the performance of the method in computing the uncertainty for each label?

Metric similar to `Root mean squared error` or others.

# Answer
There are at least two possible interpretations of uncertainty: (a) uncertainty/confidence in the label that the network predicts; (b) uncertainty in the probability/confidence score that the network outputs for the predicted label. (There might be others as well.) Let me explain both of those.

## Confidence scores: uncertainty in the label

Standard deep learning methods already provide a confidence score for their prediction. They output not a single label, but a probability distribution on labels (through a final softmax layer). Then a cross-entropy loss function is used to measure how well the predicted distribution matches the known labels, on the training set.

Once you have this, you can easily measure uncertainty. When applied to a test instance $x$, the output will be a probability distribution on labels. If the label $\ell$ has the highest probability (in this distribution), say probability $p$, then $p$ is a measure of the network's uncertainty/confidence: the smaller $p$ is, the more uncertain (the less confident) the network is in its prediction.

For example, suppose we have a neural network whose input is an image of a stoplight, and classifies whether it is showing a red light, i.e., the two labels are "red" or "not red". Such a neural network (if it ends with a softmax layer) actually outputs a vector $(p\_\text{red},p\_\text{not red})$ where we interpret $p\_\text{red}$ as the network's estimate of the probability that the light is red. Thus, the network classifies the image as "red" if $p\_\text{red} \ge p\_\text{not red}$ and "not red" otherwise, and the confidence score is the probability score associated with that label.

This provides a notion of uncertainty. For instance, suppose the network outputs the vector $(0.8,0.2)$. Then we'll classify the image as "red", and the confidence score indicates that the network thinks there is a 80% chance that the image is red, so that is a notion of how certain it is that the image is "red". This confidence score is also known as a "posterior probability", in a Bayesian framework, and it can be treated as measuring one kind of confidence.

## Uncertainty in the confidence score

Alternatively, perhaps what we want to measure is not uncertainty in the predicted label, but uncertainty in the confidence score associated with that label. For instance, if the output vector is $(0.8,0.2)$, then we'll classify the image as "red", with 80% confidence; perhaps what we care about is, how certain/uncertain are we, in the number "80%"?

That can be measured by the variance of this score. We can construct 1000 different neural networks for this task. Each one will output an output vector, and in particular, a confidence score that the image is red. If we want our best estimate of the posterior probability that the image is red, we take the average of those 1000 scores. If we want to know the uncertainty in that estimate, we take the variance (standard deviation) of those 1000 scores. Thus, this might let us say "we classify the image as 80% likely to be 'red', with standard deviation of 5% around the 80%". That variance (or standard deviation) can be taken as a measure of our uncertainty in the number 80%.

This is what Nicolas Mancuso's excellent answer is explaining, in mathematical terms. I've tried to explain it in non-mathematical terms, to help understand the idea.

Why 1000 networks? The number 1000 is arbitrary. A smaller number will be faster. A larger number will provide a more precise measure of the standard deviation.

How do you train 1000 random networks? There are several possibilities. One is to use bagging. Another is to train on the same training set, but use different random values when creating the network (e.g., initialize each network randomly and independently; use dropout, and use different randomization for each network's dropout, and maybe enable dropout at test time too).
> 1 votes

# Answer
To talk about the uncertainty in our model's prediction, we need to adopt a Bayesian framework. Here, our predictions $y^\*$ are the mean of the posterior predictive distribution $\hat{y}^\* = \mathbb{E}\[y^\* | y\]$, which minimize the mean square error. However, even if we have a value close to 0 or 1 in the classification setting, this does not imply that we necessarily have high confidence in our prediction. To get a sense of the "spread" of possible predictions on average, we can estimate the predictive variance. The link OP provided details this as, $$\underbrace{\tau^{-1}I}\_{\text{prior variance}} + \underbrace{\frac{1}{T} \sum\_{t=1}^T \hat{y}\_t^\*(x^\*)^T \hat{y}\_t^\*(x^\*) - \mathbb{E}\[y^\*\]^T \mathbb{E}\[y^\*\].}\_{\text{variance in predictions}}$$

In this setting, predictions are obtained by averaging over the $T$ drop-outs rather than the single mean from the posterior predictive, $$\mathbb{E}\[y^\*\] = \sum\_{t=1}^T \hat{y}\_t^\*(x^\*).$$

Full disclosure, I have not completely read through the author's dissertation, but after skimming it, it appears to link several interesting concepts: 1) Bayesian variational inference and drop-out, and 2) deep neural networks and gaussian processes. IMHO this is the first step to couching neural networks in a proper statistical setting that enables researchers to better understand what is going on and why things work at all.
> 1 votes

---
Tags: machine-learning, neural-networks, classification
---


# Question
Title: Does every r.e. set containing the set of total recursive functions contain all partial recursive functions?
Any r.e. subset of $A\subseteq\mathbb{N}$ which contains the set $$\mathrm{Tot}=\\{i\mid i\ \mbox{is an index of a total function } f\\}$$ must, by a standard argument (of Post?) contain *some* partial recursive function indices.

Given a partial function index (and every total function), it's pretty easy to construct many others, e.g. an index for the function which returns $0$ on prime inputs and is undefined otherwise.

But must $A$ contain *all* partial functions? This seems like a simple question, but I can't find an argument one way or the other.

Edit: I'm equally (more, actually) interested in the case where $A$ is *recursive*, e.g., represents the programs from some programing language.

# Answer
> 2 votes
Take $A = \\{i\ |\ \phi\_i(0) \downarrow \\}$. It is obviously r.e., and includes $\mathrm{Tot}$.

Yet, it does not contain any index of, say, the always-undefined function $u$. Nor indices for any recursive partial function which is undefined at $0$.

The Kleene set also works: $K = \\{i\ |\ \phi\_i(i) \downarrow \\} \supset \mathrm{Tot}$, yet it does not contain any index for $u$. (And it is r.e.)

---
Tags: computability
---


# Question
Title: Is it possible to define branches which, once taken once, will become the default forever?
Assuming I have a very simple branching:

```
switch on var:
  1 => branch1
  2 => branch2
  default => branch3

```

And I wish to implement a program that will forever take "branch2" when entering this sequence of instructions once branch2 is taken.

This is quite easy to do by adding an additional variable and setting it when branch2 is entered, however, this will keep the overhead of having to execute the control statement, I'm wondering if there is a way to remove that overhead or diminish it.

I'd be interested in knowing if:

a) This sort of optimization exists in theory ?

b) This sort of optimization is implemented languages which run in controlled environments (e.g. can use jitc) ?

c) This sort of optimization is implemented in statically compiled languages which don't need a VM/RE/etc ? (e.g. C, C++, Rust, D, Go) ?\

Edit:

Just to clarify, what I'm asking is if its possible that, once branch-x is taken once, for the instructions executed by the cpu to become:

```
//Code
//Instructions of branch x
//Code

```

rather than what we had before which was:

```
//Code
//Control Statement
//Code

```

That is in order to "skip" the overhead of having to select branch x to being with, not to optimize how that selection is done.

# Answer
> 5 votes
### Update

Based on your comment,

> I'm not concerned so much about switch statement being inefficient as I am by the fact that the switch statement exists at all.

, I think that I understand the question better now. And the answer is that you want currying to be applied on the first execution.

As a quick explanation of currying, consider a mathematical function $$f\left(x,y,z\right)=x+y+z,$$ but you know that $x=y=z=1$, such that this could be reduced down to $$f\left(\right)=3.$$ You want this, except in your case you want to reduce a switch function down to a single one of its branches.

This is entirely possible - you basically just need to recompile the code for that function. Or, if you're working in an interpreted language (e.g., JavaScript), you can simply define the switch function as its branch to replace it.

In practice, you won't need to worry about it too much in typical cases because:

1. Most switch statements aren't executed enough to be computationally significant.
2. When switch statements are executed enough to be computationally significant, but continue to resolve to the same branch each time (as you're asking about), the CPU will tend to use branch prediction to optimize it away automatically.

Still, if the switch statement's proving to be a major bottleneck or you just want to do this anyway for fun (which is a very under-valued rationale - where would we be today if people just didn't do stuff for the heck of it?!), then you have a few options:

1. Split up the method that calls the switch statement into several variants, each of which does a different branch.

* Perform this split just high enough to be outside of the critical section.
    * In effect, this will be like having pre-compiled (and optimized!) versions of the code for each of the possibilities.
    * For a jargon description, you'd be hoisting the switch nodal point outside of the performance-critical code region.
2. Actually curry-and-recompile the method at runtime.

* Depending on your platform, this can have some technical barriers.
    * When you recompile, you have to figure out what part of the program to recompile. If you do the entire thing, then it could take a while, etc.. But if you do only the switch statement, then optimizations around that area in the code will become prohibited, plus your program will need an extra function-call step to call the switch statement and its ultimate reduction.
    * As with Option (1), the optimal choice here is probably to recompile the critical section, as opposed to *just* the switch statement or the *entire* program.

### Specific answers

> a) This sort of optimization exists in theory ?

Sure, you're talking about splaying, such as implemented in a splay tree.

Obviously you can't implement this sort of optimization in rigid control structures like a `switch` statement in C/C++, so it'll take making your own implementation of something like a a splay tree that has methods as terminal nodes.

According to your description, you may want the reorganization process to stop after order's been changed once. If so, that's a modification you can add into the splay tree's logic. You can even instruct it to recompile itself in a more rigid, `switch`-like structure once the structure's determined and the splay logic's no longer needed.

> b) This sort of optimization is implemented languages which run in controlled environments (e.g. can use jitc) ?

Perhaps in some. It's an implementation detail, so it may be implemented in some implementations but not others.

> c) This sort of optimization is implemented in statically compiled languages which don't need a VM/RE/etc ? (e.g. C, C++, Rust, D, Go) ?

Yeah, definitely! You need to statically compile the methods, but you can have a splay tree that resolves method pointers, then run those.

### Comments

Just in case there was any confusion, `switch` statements don't normally need to check cases one-by-one.

For example, consider:

```
switch (x)
{
    case 0:    foo_0();    break;
    case 1:    foo_1();    break;
    case 2:    foo_2();    break;
    case 3:    foo_3();    break;
}

```

I'd expect a good compiler to implement this more like:

```
function[] switchBranches = { foo_0, foo_1, foo_2, foo_3 };
var selectedBranch = switchBranches[x];
selectedBranch();

```

than as:

```
if      (x == 0) { foo_0(); }
else if (x == 1) { foo_1(); }
else if (x == 2) { foo_2(); }
else if (x == 3) { foo_3(); }

```

So if you're doing something like this, you don't really need to worry about the compiler reordering the `switch` statement's cases since it's already a constant-time lookup.

In more general cases, where a deterministic index isn't practical, dictionary-lookup logic can be applied.

# Answer
> 2 votes
Unroll the loop. Instead of

```
while true:
  switch on var:
    1 => branch1
    2 => branch2
    default => branch3

```

replace that with an unrolled version:

```
while true:
  switch on var:
    1 => branch1
    2 => goto loop2
    default => branch3
return

loop2:
while true:
  branch2

```

Or, if you prefer:

```
while true:
  switch on var:
    1 => branch1
    2 => while true:
           branch2
         break
    default => branch3

```

# Answer
> 2 votes
It is reasonably common nowadays that code is recompiled on occasion. For example, a JVM compiler will initially assume that some function call is not virtual (but can be proved wrong). It will then for a virtual function call generate code like "if (function implementation is what I thought it would be) then (call that implementation) else (recompile this code without that assumption and run it again)". So technically no problem.

However: What on earth are you actually trying to achieve here? You say "the default should be branch2". So you want to change the code from

```
switch on var:
  1 => branch1
  2 => branch2
  default => branch3

```

to

```
switch on var:
  1 => branch1
  2 => branch2
  default => branch2

```

or at least that's what you say. As a feature of a programming language, the value of this is less than zero. I cannot see any application for this whatsoever. It is so out of the norm that nobody in their right mind will ever use it. If someone else uses it, everyone reading the code will be forever confused what this is doing.

On the other hand, something similar is actually used. Either explicitly as a function (for example dispatch\_once or pthread\_once) or hidden in the language (static variables in C++, C#, Swift etc.) people want code that is executed only once. With a thread safety guarantee, which means that if one thread is running this code to be run once, all other threads wait if they reach this code.

It turns out that any compiler optimisation there is of very little value. All that needs doing is checking the value of a variable and branching accordingly, which due to branch prediction has a cost of approximately zero.

---
Tags: programming-languages, compilers, code-generation, access-control, meta-programming
---


# Question
Title: Why doesn't playing audio stop other tasks?
If processors can only execute one thing at a time, how come I can play music continuously and still be able to run other tasks?

I understand the interrupt system, but isn't it needed that CPU continuously process audio for it to not sound jittery/laggy?

I am asking about the underlying implementation, is this question related to multi-threading? How does a 1-core, 1-threaded CPU be able to achieve this multitasking?

# Answer
Since the CPU works in fixed clock cycles, nothing is really continuous, only seems so because the discretization is sensitive enough.

Suppose your CPU clock rate is $1\text{GHz}=10^9Hz$. If the CPU only devotes one in $t$ clock cycles to processing audio (and utilizes the remaining clock cycles for unrelated tasks) then you have a delay of $\approx t\cdot 10^{-9}s$ between every "audio processing tasks" preformed by the cpu (for simplicity, we assume the cpu preforms this processing using only one clock cycle).

Lets say we allow a delay of $10^{-5}s$ (humans hear frequencies in the range of 20Hz to 20Khz, so the human hearing will not be sensitive to such delay), then we need to require $t\<10^4$, so the CPU can handle simultaneously $10^4$ more tasks while keeping a delay of $10^{-5}s$.
> 9 votes

# Answer
40 years ago, you might have had a computer where the CPU controlled the speaker directly. Those times are over, long ago.

You may have a computer with a primitive sound card. Such a sound card will have a buffer for stereo audio samples, that buffer can be filled, the output function will be started, and the sound card starts generating audio from the samples in its buffers, without the CPU having to do anything. All the CPU needs to do is fill the buffers with more audio samples before it runs out. If you have a one megabyte buffer, that's 250,000 stereo samples in CD quality, that's about six seconds. So every few seconds, the CPU has to fill these buffers again.

In reality, your computer will have something much more advanced. In principle the same, but the buffers can be filled directly with sound in mp3 or aac format, for example, and the sound card will decode this data to stereo samples on its own. Most likely it can be programmed to produce all kinds of different effects, from sound volume, improving sound quality, changing pitch or speed independently, generate surround sound and so on.

The CPU doesn't do very much, just filling the sound buffers from time to time. The rest is done by something else. Of course when I say "sound card", these have shrunk from sound cards to chips to a tiny fleck of transistors on a massive chip with lots of different functionalities.

For one maker of such cards, look at https://en.wikipedia.org/wiki/Wolfson\_Microelectronics as a starting point.
> 9 votes

---
Tags: cpu, multi-tasking
---


# Question
Title: Why when I unchecked DMA in Windows 7, the CPU usage was still very low?
I am studying about PIO mode and DMA mode for accessing IO devices, and based on what I have read, in PIO mode the data transfer have to go through the CPU.

So I have unchecked DMA in Windows 7 (which I guess will enable PIO mode):

And I copied and pasted a large file to see the CPU usage, and the CPU usage was still very law (about 5%). Shouldn't PIO mode exhaust the CPU?

# Answer
Your understanding of DMA is OK. But disk accesses are generally slow. So the CPU may spend is time on waiting for the disk to write the bytes on the disk, he is not stressed.
May be you can try to run something like CPU Burner that will stress the CPU and then measure the time to copy with/without DMA enabled.
Note that many things can interfere with your measurements, particularly HD caches.
> 1 votes

---
Tags: computer-architecture
---


title: what is the complexity of this program?

text:
# Question
Title: what is the complexity of this program?
// assume 'n' is given. What is the time complexity of this code ?

```
     java.util.LinkedList<Integer> k = new java.util.LinkedList<Integer>();
     for(int i = 0;i<n;i++)
        for(int j = 0;j<n;j++)
           k.add(k.size()/2,j);

```

# Answer
> 1 votes
See, the first two times, the function $add(,)$ adds to 1st of list. Next two times it skips 1 element. Next two elements it has to skip 2 elements. So the number of steps goes like this:

$1+1+2+2+3+3+...$(Total of $n^2$ terms as there are two for loops) $=2(1+2+3+...+\frac{n^2}{2})$

$=\frac{n^2}{2}(\frac{n^2}{2}+1)\in \Theta(n^4)$

Hence time complexity is $\Theta(n^4)$

**NOTE** Here we make the assumption that adding in a linked list means going through the elements of the list. Assuming an oracle can add to the list in constant time we will get $\Theta(n^2)$complexity though.

# Answer
> 1 votes
The question cannot be answered at all. There are obviously $n^2$ calls to a function k.add(), but we have no idea whatsoever what the execution time of that function is. If it is implemented in a very simplistic manner then the way it is called may take $\Theta (n^2)$ steps on average for a total of $\Theta (n^4)$ operations.

If I had to implement this class LinkedList as a single linked list, I would keep two pointers in the list, one to some element close to the end of the list, and one to some element close to the place where the last insertion happened that wasn't at the very start or end. That way insertions, deletions and indexed access close to the beginning, close to the end, and near to the last location can be done in constant time. Since these are the typical uses, that should make the average must faster. In this case, such an implementation could easily lead to a $\Theta (n^2)$ total.

# Answer
> 0 votes
Assuming the basic operation is the `k.add()`

considering this section, say sectionA.

```
for(int j = 0;j<n;j++)
           k.add(k.size()/2,j);

```

k.add() gets executed n-times. `O(n)`

consider the full case.

```
for(int i = 0;i<n;i++)
        sectionA.

```

sectionA get executed n-times `O(n).O(n)` == `O(n^2)`. And hence the program has complexity `O(n^2)`.

# Answer
> -1 votes
I think it is O(n^2) as there is a nested loop.

**Edit:**

If we take the loop body also into account, the complexity would be O(n^3) as the add() function takes O(j) time to insert an element to a linked list `(j < n)`

It is something like this,

```
java.util.LinkedList<Integer> k = new java.util.LinkedList<Integer>();
     for(int i = 0;i<n;i++)
        for(int j = 0;j<n;j++)
        {
              //another loop with O(j) complexity to add element
        }

```

I still don't get how it's O(n^4). Could you explain little detail

---
Tags: runtime-analysis, java
---


# Question
Title: When are range-based for loops better than regular for loops?
Is it when you need faster performance, to iterate over a container, or when you don't need an index variable?

From my understanding it should be when you need to iterate over a container.

Am I understanding this properly?

# Answer
In my experience, if you don't need an index variable and don't need to iterate over the objects in a particular order, then range-based for loops can be easier to understand, and less verbose. Outside of those conditions, it's usually a matter of taste. You're basically saying, "for each object in the container, do this," as opposed to saying, "for each index in the container, retrieve the object at the index, and for each object you've retrieved, do this."
> 0 votes

# Answer
I follow a simple rule: Use regular for loops only if you HAVE to. Use range based anytime you can as they make your code cleaner, more concise and less prone to error.
> 0 votes

---
Tags: loops
---


# Question
Title: DFA for $L=\{w: w\in \{a,b\}^*, |w|_a\ \equiv |w|_b \equiv 0$ $(mod$ $5) \}$
There is a language: $L=\\{w: w\in \\{a,b\\}^\*, |w|\_a\ \equiv |w|\_b \equiv 0$ $(mod$ $5) \\}$. My idea for DFA is - we count number of $a$$\pmod{5}$ and separately we count number of $b$$\pmod{5}$. So we end up with $5\*5=25$ states, because each state have to keep track for both number of $a$ and $b$$\pmod{5}$. Is there any better aproach to this DFA ? Because for example when we have$\pmod{10}$ we end up with 100 states. I would appreciate any sugestions.

# Answer
The minimal DFA for $L$ contains 25 states, as can easily be shown using Myhill–Nerode theory.

Indeed, consider the 25 words $\\{a^ib^j : 0 \leq i,j \< 5\\}$. I will show that when a DFA reads any two different words from this list, it cannot end up in the same state. To show this, for any two different words $x,y$ from the list, I will give a word $z$ such that $xz \in L$ but $yz \notin L$.

Let $x = a^i b^j$ and $y = a^k b^\ell$ be two different words from the list. Since $x \neq y$, either $i \neq k$ or $j \neq \ell$ (or both). Assume without loss of generality that $i \neq k$. Take $z = a^{5-i} b^{5-j}$. Then $|xz|\_a = |xz|\_b = 5$, and so $xz \in L$. In contrast, $|yz|\_a = 5-i+k \not\equiv 0 \pmod{5}$, since $i \not\equiv k \pmod{5}$ by assumption, showing that $yz \notin L$.
> 2 votes

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


# Question
Title: Register Allocation and Definition of Interference
In my textbook on compiler design \[1\], it describes interference between two variables (the property that they cannot be in the same register at once) as follows:

> ***Definition 9.2****: A variable $x$ interferes with a variable $y$ if $x \neq y$ and there is an instruction $i$ such that $x \in kill\[i\], y \in out\[i\]$ and instruction $i$ is not "$x := y$"*

This definition does not make sense to me. If I interpret this in plain English:

> A variable interferes with another if some variable $x$ is being overwritten, while some variable $y$ is live at the exit of the instruction, and the instruction is not $x := y$ and $x$ and $y$ have distinct values.

To me, a more logical definition of interference is if two variables $x$ and $y$ appear in the same $gen$ set of some instruction $i$. This necessarily means that these two variables are used (i.e their value) in the same instruction. Is there some crucial detail that I am missing?

For those interested, this definition appears on page 197 of the book referenced above.

# Answer
Your "reading" of the definition is a little unclear. In particular, it says nothing about the *values* of the variables. Here's a clearer reading:

> A variable $x$ **interferes** with a variable $y$ if 1) they are not the same variable, i.e. a variable never interferes with itself, and 2) there is some instruction other than $x := y$ where $x$ is overwritten while $y$ is live at the end of the instruction (and typically also during, but a multiple assignment instruction like $(x,y):=(a,b)$ would be an example where variables can interfere even though $y$ is not live during the instruction).

As the book points out immediately after that definition, if $x$ and $y$ have the same value (for some stretch of code), then there is no reason they can't be held in the same register (in that stretch of code). This is what makes ignoring $x := y$ instructions valid. The analysis does not calculate the values of anything however. $x$ and $y$ interfere in $\\{x := k;y := k; f(x,y)\\}$ and so will be assigned different registers. For this analysis to exploit the fact that they have the same value, a prior optimization pass would need to rewrite it to $\\{x := k; y := x; f(x,y)\\}$.

Your definition is also incorrect. The $gen$ set of $x := k$ is empty, but certainly two variables can't share a register if one is being mutated and the other isn't. Again, as the book points out immediately after the definition, the definition is close to saying that distinct variables $x$ and $y$ can't both be *live* at the same time. (Both being live at the same time would be formulated as $x,y \in out\[i\]$.) This is a more conservative condition than yours, but it is still incorrect for the same reason. If $x := k$ is the last occurrence of $x$, and thus isn't in the $out$ set of that instruction, it still interferes with $y$.
> 2 votes

---
Tags: compilers
---


title: What is a batch compiler?

text:
# Question
Title: What is a batch compiler?
I have the following quotation from my compiler's course (in the context of graph coloring):

> Because it is slow, graph coloring tends to be used in batch compilers, while linear scan tends to be used in JIT compilers.

I couldn't find a clear definition online. So, what makes a compiler be a batch compiler?

# Answer
> 43 votes
A JIT (Just-In-Time) compiler compiles code at run-time, i.e. as the program is running. Therefore the cost of compilation is part of the execution time of the program, and so should be minimized.

The opposite of this is an ahead-of-time (AOT) compiler which is basically synonymous with "batch compiler". This converts the source code to machine code and then just the machine code is distributed. Therefore, the compiler can be very slow as it doesn't impact the execution time of the resulting program.

Nowadays, when people say "compiler" they typically mean an AOT compiler. Indeed, the term "AOT compiler" only really started becoming popular relatively recently when people started making AOT compilers for JIT compiled languages, particularly JavaScript. Many of these languages, e.g. C#, compile to an intermediate language for a VM which is then JIT compiled to machine code at run-time. The term "AOT compiler" has the connotation that the source code will be compiled directly to machine code, so no form of JIT compilation is required at run-time.

"Batch compiler" is a bit of an archaic term at this point. The real contrast to a batch compiler when the term was popular was an incremental compiler. Incremental compilation is often associated with languages like Lisp where you had a REPL and you could interactively request the language implementation to compile a specific function. If a function was executed whose compilation had not been requested before, it would typically be interpreted. A batch compiler, by contrast, compiled all functions at once, i.e. in a batch.

# Answer
> 13 votes
The meaning is implied within the quote you give! It stems from the computing term batch processing which is used when the task is not performed in real-time, but it scheduled for later execution by the operating system when the load (often for real-time activities) is less.

A batch compiler is one that does the compiling when a user is not waiting for the result of the compilation. It is one that we would say, using more modern terminology, done in the background.

This is the converse of a JIT (Just-In-Time) which is done "live" at the exact time it is needed without the luxury of spending the extra time to do the processing more thoroughly.

The slower speed of batch compiling can be illustrated by this:

Source: https://xkcd.com/303/

Or even this:

Source: http://dilbert.com/strip/2013-06-22

---
Tags: compilers
---


# Question
Title: Quadratic probing maximum load factor with $c_1 = c_2 = 0.5$ to guarantee successful insertion
For quadratic hashing, i.e an open-addressed table with the hash function of the form -

$h(x, i)= (h'(x) + c\_1i + c\_2i^2) \mod m$

Setting $c\_1 = c\_2 = 1/2$, and $m$ to some power of 2, leads to a hash function

$h(x, i) = (h'(x) + 1 + 2 + ... +i) \mod m$

I have read that the load-factor of a quadratically probed table should not exceed $0.5$ to guarantee insertion to succeed if an empty cell exists in the table. Wikipedia's article here https://en.wikipedia.org/wiki/Quadratic\_probing#Limitations says that

"With the exception of the triangular number case for a power-of-two-sized hash table, there is no guarantee of finding an empty cell once the table gets more than half full, or even before the table gets half full if the table size is not prime. "

So what is the maximum load factor that will guarantee successful insertion for this case?

# Answer
For the case you describe ($c\_1=c\_2=1/2$, $m=2^k$), you can reach a load factor of 1. The probe sequence touches all the cells in the table.

As a practical matter, you probably don't want to get really close to a load factor of 1, as the probing can take $O(n)$ time.
> 5 votes

---
Tags: hash-tables
---


# Question
Title: Relation between best case and average case complexity
I have two questions,

1. Does $T\_\mathrm{best}(N) = O(f(N))$ imply that $T\_\mathrm{avg}(N) = \Omega(f(N))$?
2. Does $T\_\mathrm{avg}(N) = O(f(N))$ imply that $T\_\mathrm{best}(N) = O(f(N))$?

Where, \begin{align\*}T\_\mathrm{best}(N) &= \min \\{T\_1, \dots, T\_N\\}\\ T\_\mathrm{avg}(N) &= \frac1N \sum\_{1\leq i\leq n} T\_i \end{align\*} for some sequence $T\_1, T\_2, \dots$.

I think both are true but don’t know how to prove them. Any ideas?

# Answer
> 3 votes
I think your definitions of $T\_{\text{best}}$, $T\_{\text{worst}}$, and $T\_{\text{avg}}$ could use some clarification. I'll proceed assuming the correspond to best-, worst-, and average-case runtimes \[1\].

The first claim is false. The problem is that $f$ could dominate $T\_{\text{best}}$ at an arbitrary rate. So we cannot make any claims about $f$'s status as an asymptotic lower bound of $T\_{\text{avg}}$.

The second claim is true. Hint: prove $T\_{\text{best}} = O(T\_{\text{avg}})$, then use transitivity of $O$ to conclude the result.

\[1\] https://en.wikipedia.org/wiki/Best,\_worst\_and\_average\_case

---
Tags: complexity-theory, time-complexity, asymptotics
---


# Question
Title: What's the difference between a broadcast algorithm and a flooding algorithm?
Both the broadcast algorithm and the flooding algorithm seem exactly the same to me, some sites try to explain the difference but then other sites contradict their statements. At the moment I see both algorithms starting at a specific starting node. This starting node will send a message to all of its neighbors, and once received, the neighbors will send the message to all of their neighbors in turn, etc, etc. What is the difference?

Does the broadcast algorithm use a spanning tree, and the flooding algorithm doesn't? Does the flooding algorithm use previously used edges, whereas the broadcast algorithm only use edges that aren't used yet?

# Answer
> 1 votes
Broadcast routing is of three types :

1.) **N-way unicast routing** \- There are N destinations and the source sends a copy of the packet to each destination by making N copies of the packet and addressing each copy to a different destination.

2.) **Uncontrolled flooding** \- The source node sends a copy of the packet to all of its neighbors. When a node receives the packet, it duplicates the packet and send to all of its neighbors except the sender.

3.) **Controlled flooding** \- A source node puts its address and broadcast sequence number into the packet. It sends the packet to all of it's neighbor. Each node maintains a list of the source address and sequence number of each broadcast packet it has received. When a node receives a broadcast packet. If the received broadcast message has the source address and sequence number already present in the list then it will drop the packet otherwise make a copy and forward it to all the neighbors except sender.

---
Tags: algorithms, distributed-systems
---


# Question
Title: What is the difference between $x:A$ and $x \Xi A$?
Given a type hierarchy $(\tau,\sqsubseteq)$ and a signature $(VSym, FSym, PSym, \alpha)$, one says that the typing function $\alpha$ assigns to each variable symbol $x \in VSym$ a non-empty type $A \in \tau \setminus\\{\bot\\}$ and is written as:

$$ x: A \tag1$$

Furthermore, for every type $A \in \tau \setminus\\{\bot\\}$, there is a predicate symbol $\Xi A \in PSym$ called the type predicate which tells us if or not a certain $x$ is an *instance of* type $A$. We write it as:

$$x \Xi A \tag2$$

That makes me think what set constitutes the domain of a predicate symbol. Clearly, if the domain is $VSym$, then $(1)$ and $(2)$ mean exactly the same thing, and therefore, would be a redundancy of definition.

If not, which is surely the case, how do they differ? In particular, can you tell if a certain object is an instance of a certain type and not just a variable symbol with the given type assigned to it (or vice versa)?

More precisely, if a predicate symbol is a function from a certain domain to the set $\\{\mathrm{True},\mathrm{False}\\}$, what exactly is the domain of this map? Is there any overlap of this domain with $VSym$?

I am reading the chapter on first order logic from Deductive Software Verification – The KeY Book. (I am not fully sure if this question fits in a mathematics or a computer science forum.)

Thank you for your time.

---

## **Background:**

Please refer to this document (the first couple of pages actually) to update yourself with the relevant ideas and definitions. Here's a brief summary.

---

A *type hierarchy* is a pair $\mathscr T = (\tau,\sqsubseteq)$, where

1. $\tau$ is a set of type symbols;
2. $\sqsubseteq$ is a partial ordering on $\tau$, called the subtype relation;
3. there are two designated type symbols, the empty type $\bot \in \tau$ and the universal type $\top \in \tau$ with $ \bot \sqsubseteq A \sqsubseteq \top \forall A \in \tau$.

---

A *signature* (for a given type hierarchy $\mathscr T$) is a quadruple $\Sigma = (VSym, FSym, PSym, \alpha)$ of

* a set of variable symbols $VSym$,
* a set of function symbols $FSym$,
* a set of predicate symbols $PSym$, and
* a typing function $\alpha$,

such that

* $\alpha(v) \in \tau\_q := \tau \setminus\\{\bot\\}\ \forall v \in VSym$,
* $\alpha(f) \in \tau\_q^\* \times \tau\_q\ \forall f ∈ FSym$, where $\tau\_q^\*$ is the set of all (possibly empty) sequences of elements in $\tau\_q$, and
* $\alpha(p) \in \tau\_q^\*\ \forall p \in PSym$.
* There is a *function symbol* $(A) \in FSym$ with $\alpha((A)) = ((\top),A)$ for any $A \in \tau\_q$, called the *cast* to type A.
* There is a predicate symbol $\doteq \in PSym$ with $α(\doteq) = (\top,\top)$.
* There is a predicate symbol $\Xi A \in PSym$ with $\alpha(\Xi A) = (\top)$ for any $A \in \tau$, called the *type predicate* for type A.

---

*Notation*: We write

1. $v : A$ for $\alpha (v) = A$,
2. $f : A\_1,...,A\_n \to A$ for $\alpha(f)=((A\_1,...,A\_n),A)$,
3. $p: A\_1,...,A\_n$ for $\alpha(p)=(A\_1,...,A\_n)$,
4. $x \Xi A$ (read: $x$ is an instance of $A$) for $\Xi A(x)$,
5. $x \doteq y$ for $\doteq(x,y)$.

---

**NOTE:** Some texts (such as the document linked above) implicitly do the type assignment carried out by $\alpha$ and write down the definition in the standard notation mentioned above.

# Answer
> 6 votes
$x:A$ is a statement about objects in the formal system, like, for example, $\vdash 2+4:\texttt{int}$, whereas $x\Xi A$ is an expression in the formal system, like $\texttt{if}~ 2 + 4 ~\texttt{==}~5 ~\texttt{then}~ e\_1~ \texttt{else} ~e\_2$.

---
Tags: type-theory, first-order-logic, software-verification
---


# Question
Title: What is the height of avl tree with n nodes
what is the height of avl tree with n nodes ? Can you explain it with formula ? I couldn't find any formula to solve this problem.

# Answer
> 1 votes
AVL trees are self-balancing binary search trees (another example is red-black trees). By definition, a self-balancing binary tree maintains the property that its height is $\Theta(\log n)$, where $n$ is the number of leaves or vertices (the two properties corresponding to the two different definitions of $n$ are equivalent).

Usually it is costly to have a data-independent height, and so the height depends on the history of the data structure (it depends on the exact order in which values were inserted and deleted), but it is always $O(\log n)$. (Note that *every* binary tree has height $\Omega(\log n)$.)

---
Tags: trees
---


title: Filling a container with boxes

text:
# Question
Title: Filling a container with boxes
I have a problem in my Algorithms Class which i am trying to solve for the past two days but I can't. I want to fully fill a container with the MINIMUM number of given boxes with dynamic programming. My container has a certain size and I have different box sizes AND quantities of them (so i have 24 boxes of size 20, 15 boxes of size 48 etc). I think that i gotta somehow modify the knapsack problem? But the knapsack is not necessarily fully filled whilst in my problem i have to fill the container completely. Also I gotta somehow connect the hypothetical value of the knapsack with the sizes of the boxes. Any hints?

# Answer
Stripping away the "story", your problem is that you have a list of numbers $v\_1, \dots, v\_k$ along with a target $t$ and you're looking for a set $I\subseteq \\{1, \dots, k\\}$ such that $\sum\_{i\in I}v\_i = t$. (That is, you're looking for a collection of the numbers that add up to $t$ and you can't use any number more times than it appears in the initial list.) This is known as the subset sum problem.

You can solve it with classical dynamic programming. The intuition for all such dynamic programming problems is the following.

* Step through the values $v\_i$, $1\leq i\leq k$ one at a time.
* Any sum that can be made from $v\_1, \dots, v\_i$ either contains $v\_i$ or it doesn't.
    + If it contains $v\_i$, then its value is $v\_i$ plus some sum you can make from $v\_1, \dots, v\_{i-1}$;
    + if it doesn't, it's just a sum from $v\_1, \dots, v\_{i-1}$.

Naively, you'd do this by recursion but that involves lots of recalculation so it's very inefficient. Instead, you build up a table that tells you, for each $i$ and each possible sum $s\leq t$, whether you can make sum $s$ from $v\_1, \dots, v\_i$.
> 0 votes

---
Tags: dynamic-programming
---


title: Why is $\log n = O(2^n)$?

text:
# Question
Title: Why is $\log n = O(2^n)$?
In my theoretical computer science book I have the following statement regarding the **space complexity** of $f(n)=2^n$:

$$\log(n) = O(f(n))$$

I can't understand how this is true, any help will be greatly appreciated.

# Answer
As stated, $\log (n) = O (2^n)$ is trivially true.

All that it says is that $\log n$, in the end, grows no faster than $2^n$. For $2^n$, you can substitute $n$, $\sqrt n$, indeed any root of $n$.

---

However carelessly stated, I think this really refers to the following:

* To represent a number of size $2^n$, you need $n$ bits.
* So, to represent a number of size $n$, you need $\log n$ bits.

Bits are a measure of space.

---

I made heavy weather of this before, as I thought it was referring to the time it takes to calculate $2^n$. In case it is, I'll leave this in:

For $n$ a non-negative integer, and $f(n) = 2^n$

$$ f(n) = \begin{cases} 1 &\text{for }\\, n = 0 \\ (f (n \div 2))^2\times 2^{(n \mod 2)} &\text{for}\\; n \gt 0 \end{cases}$$

The implied algorithm is clearly $\Theta (log \\, n)$. But this is *time* complexity. In *space* complexity, it is $\Theta(1)$.

---

* $\Theta (f)$ are the functions that, adapting the words of Wolfram Mathworld, are no worse but also no better than $f$.
* $O (f)$ are the functions that are no worse than $f$.
> 0 votes

---
Tags: asymptotics, landau-notation
---


# Question
Title: What am I missing in this application of Dijkstra?
When running Dijkstra against the following graph:

```
   1   3
A -- B -- C
 \      /
2 \    / 1
   \  /
    D

```

...I come up with the following:

```
   Current
                A      B          C          D
         A      1(via A)   -          2(via A)
         B      1(A)       4(via B)   2(via A)
         C      1(A)       4(via B)   2(via A) (5 via C ignored)

The shortest path from A to B is 1 via A.
The shortest path from A to C is 4 via B.
The shortest path from A to D is 2 via A.

```

...but there is a path from `A` to `C` via `D` that is of magnitude 3 (2 + 1).

What am I missing here?

# Answer
> 2 votes
current should be the unexplored with the lowest cost. Which means that after you explored $B$ you should have explored $D$ because $2\<4$.

---
Tags: shortest-path
---


title: What hash algorithm is it?

text:
# Question
Title: What hash algorithm is it?
I've found a simple multiply-with-add hash function in an old Usenet post. Can someone identify what hash algorithm is it? An algorithm name or any attribution?

```
size_t hash(const char* data, size_t length, size_t seed = 1)
{
    for (size_t i = 0; i < length; i++)
    {
        seed = seed * (UCHAR_MAX + 2U) + data[i];
    }

    return seed;
}

```

# Answer
> 3 votes
This hash function is very similar to a linear congruential generator, a type of naive pseudorandom number generator. By now there are much better hash functions out there, and I suggest not using this one.

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


title: Make appends not degrade a splay tree

text:
# Question
Title: Make appends not degrade a splay tree
Splay trees offer armotized O(log n) access to tree elements. However, if you keep repeatedly appending elements to a splay tree, without splaying any other elements, it degrades into a linked list with O(n) access. Is there a way to avoid that? I have the idea of splaying a random element during an append, but will that do any help?

# Answer
> 1 votes
It's true that if you consider a long sequence of operation, it's possible to point at one operation and say "that one operation might take a really long time" (e.g., $O(n)$ time). That's in some sense the essence of amortized analysis. An amortized running time of $O(\log n)$ means that the average time per operation is $O(\log n)$, but it's still true that there might be a rare operation here and there that take much more (though it will be compensated by most operations taking less time). Amortized running time bounds are only useful if you're willing to accept that limitation.

If you want *worst-case* running time bounds, then don't use a data structure that only offers amortized worst-case bounds; use a different data structure, one that offers worst-case running time bounds. For instance, self-balancing binary search trees (like red-black trees, AVL trees, etc.) offer worst-case running time guarantees. If amortized running time bounds aren't good enough, maybe splay trees aren't the data structure for you.

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


# Question
Title: Local variables get assigned global addresses based upon call tree
When working with certain low-powered / embedded CPUs that are bad at using the stack, I need to avoid putting local variables there, instead opting to make them static variables. But this can waste a lot of address spaces since not every local in every function needs their own unique address. Rather, by looking at the call tree, functions that do call each other can share memory space.

For example, given code such as this:

```
void A() {
    int x;
    // ...
    B();
    C();
    // ...
}

void B() {
    int y;
    // ...
}

void C() {
    int z;
    // ...
}

```

The variables `y` and `z` can be assigned the same address, while `x` should be unique so that calls to B() and C() don't clobber it.

Obviously this breaks recursion and multi-threading, but neither of those are a problem for the use cases I'm working in.

Is there a name for this algorithm? I'm assuming that it's well known, but it's very hard to search for information about this specific problem.

# Answer
This sounds similar to register allocation. Normally, register allocation is done at the scope of a single function, but it can also be done globally (interprocedurally). If you ignore all recursive and mutually recursive calls, you might be able to apply standard algorithms for register allocation to your situation.
> 1 votes

---
Tags: algorithms, programming-languages, compilers
---


# Question
Title: Two way finite state Automaton NP Compleness definition clarification?
INSTANCE: A two-way nondeterministic finite state automaton A over single Alphabet I. QUESTION: Is there an string x (over I) such that A accepts x ?

Since a 2-way NFA with N states, there’s an equivalent nfa with n^(n+1) states. So that’s we get the exponential time from.

I am clear about that, but if I understand correctly the size of the string accepted by the 2Way NFA would still be (in the worst case) polynomial to number of states in the 2Way NFA. Cause if the smallest string accepted was exponential in size, the verification will also take exponential time and thus the problem by definition would not be NP Complete ? Or is there a mistake in this reasoning?

# Answer
For a problem to be in NP, there needs to be a polynomial time verifier for it. This polynomial time verifier need not be the "obvious" one. Ruling out one specific verifier doesn't prove that the problem is not in NP.

For a problem to be NP-complete, it needs to satisfy two properties: (i) it needs to be in NP, and (ii) it need to be NP-hard. You can look these concepts up in many sources. In particular, the fact that there is some natural exponential time algorithm for a problem *doesn't* imply that it is NP-complete, though it is true that every problem in NP has an exponential time algorithm.

Unfortunately I am not versed well enough in two-way automata to answer your specific question, but my comments above imply that the answer doesn't necessarily have a direct bearing on whether the emptiness problem for 2NFAs is NP-complete or not (or even in NP or not).
> 2 votes

---
Tags: automata
---


# Question
Title: how long will it take to execute a ten-stage pipeline
Suppose you design a computer with a `ten-stage` Pipeline to execute one instruction, with each stage taking `5nsec`

A)how long will it take to execute a program that has `30 sequential` instructions. **Answer: 195nsec**

B) how long will it take to execute a program that has `30 sequential instructions` in a `non-pipeline computer` **Answer: 1500nsec**

can some one please help me to understand how was the answer achieved.

# Answer
> 1 votes
An instruction needs 10 times 5 nsec to execute. With pipelining, the next instruction can start when the previous one is in the next pipeline stage, that is 5 nsecs after the previous one started. Without pipelining, the next instruction starts only when the previous one has finished, that is after 10 times 5 sec. The rest is basic arithmetic.

# Answer
> 1 votes
Suppose the first instruction enters the pipeline at time $0$. Each successive instruction enters $5$ ns after the previous one. The first instruction exits the pipeline at time $10\cdot 5$ ns and each of the other $29$ instructions exits $5$ ns after the previous one. In sum, $10 \cdot 5 + 29 \cdot 5 = 195$ ns.

For the non-pipelined processor, the somewhat pessimistic assumption is made that each instruction takes $10\cdot 5$ ns to execute; then, $30 \cdot 50 = 1500$.

---
Tags: mathematical-foundations, cpu-pipelines
---


title: Vertex Cover special cases

text:
# Question
Title: Vertex Cover special cases
This was from a test from my university:

Consider $T = t\_1, t\_2, \cdots, t\_n$ a set of intervals of the form $(s, e)$, representing the start and end time, respectively. Now, select the minimum number of intervals such that their "union" intersects all other intervals. The question then asked for an optimal greedy algorithm.

From what I can see, this is a vertex cover problem (each interval is a vertex; draw an edge between each pair of intervals that intersect), which is NP-complete on general graphs.

Consider $W(i)$ the number of intervals intersecting $i$, and $M$ a set of intervals already covered. Here is my solution:

1. Order $T$ by $W$ and insert in $T\_{ord}$;
2. If $T\_{ord} = \emptyset$ terminate
3. Remove the first element $e$ from $T\_{ord}$;
4. If $e \in M$ go to $2$;
5. Decrease $1$ for every element $e^{'}$that intersect $e$, and $M \cup\\{e,e^{'}\\}$;
6. Order $T\_{ord}$ and go to $2$.

I managed come up with a greedy solution, but couldn't come up with a counterexample. Given that, I was thinking if this is a special case of the vertex cover problem. Is it?

# Answer
> 1 votes
This is dominating set, not vertex cover.

The graph has the set of intervals as vertices and two vertices are adjacent if the corresponding intervals overlap. Such a graph is known as an interval graph, which is a special case of intersection graphs (vertices are sets of some kind, and two vertices are adjacent if their sets intersect).

You're looking for a minimum-sized set $S$ of intervals such that every other interval intersects at least one interval in $S$. In the interval graph, this means that you're looking for a minimum-sized set $S$ of vertices such that every other vertex is adjacent to $S$: this is a dominating set.

The problems of omputing minimum vertex covers and minimum dominating sets are both **NP**-hard on general graphs. However, on interval graphs, both problems can be solved in polynomial time, by

* M.V. Marathe, R. Ravi and C. Pandu Rangan, *Generalized vertex covering in interval graphs*. *Discrete Applied Mathematics*, 39(1):87–93, 1992.
* K.S. Booth and J.H. Johnson, *Dominating sets in chordal graphs*. *SIAM Journal on Computing*, 11(1), 191–199, 1982.

In the former case, a $2$-vertex cover is an ordinary vertex cover; in the latter, the algorithm actually works for all for all directed-path graphs, and every interval graph is a directed-path graph.

---
Tags: graphs, np-complete, greedy-algorithms
---


title: 4 Neurons to Decide 10 Digits

text:
# Question
Title: 4 Neurons to Decide 10 Digits
I am trying to solve this algorithm exercises (http://neuralnetworksanddeeplearning.com/chap1.html#exercise\_513527) in Michael Nielson's online book: Neural Networks and Deep Learning (http://neuralnetworksanddeeplearning.com/chap1.html#complete\_zero).

In another word, he says that there is a way to use four neurons to decide 10 digits on top of of the last hidden layer (which consists of 10 neurons and decides 10 digits separately with a high correct rate).

However I couldn't figure out the way. Do you have any idea about this? I look forward to your idea. Any help is appreciated.

# Answer
You could use 4 neurons to produce a 4-bit output, which then represents the digit in binary. A digit in the range 0-9 can be expressed in binary as a 4-bit number.

However, classification accuracy might potentially be worse than the standard method of 10 output neurons with a softmax layer.
> 2 votes

---
Tags: algorithms, neural-networks, algorithm-design
---


title: Searching related works for papers

text:
# Question
Title: Searching related works for papers
How do you search related works for your papers? To be concrete I have implemented few techniques of indirect call promotion for pure C and want to share my results. But at first I want to understand if there are some existing papers about it.

I searched with Google, Google shcolar, citeseerx, microsoft academic search, acm library and semanticscholar. I found only papers on C++ devirtualization but not for pure C. I searched the papers referenced to those what I found but I still did not found anything about pure C.

Can I think my research will be uniqe and interesting for scientific community or I just failed to find existing papers?

# Answer
This site may also offer you a resource for locating content similar to your paper. Most academic institutions and public libraries have free access to these sorts of research tools to look for published work in selected areas of research. Good Luck.

Click Here
> -1 votes

---
Tags: compilers, research
---


# Question
Title: Difference between Bandwidth and Propagation Speed in computer networks?
I want to know the difference between Bandwidth and propagation speed. How are they associated with each other i.e. the impact on bandwidth if propagation speed varies or the impact on speed if bandwidth varies. I have gone through this difference between propagation speed and bandwidth in digital communication still I am unable to understand it very clearly. Could it be possible to explain with some other example like may be with water pipes etc.

# Answer
> 2 votes
These two terms are actually completely unrelated. Bandwidth is a way of expressing how much "stuff" you can send on a network link at a time. Think of it like a highway. If you have only one lane on the highway, then you have a bandwidth of 1 car per some unit of time (let's say seconds). So every second, only 1 car can pass through that particular segment of roadway. But if you widen the road to have 4 lanes, then you can get 4 cars per second. It's literally the width of the frequency band you can send data over.

Now propagation speed is how quickly something can propagate, or move a certain distance. Consider the cars again. If they are driving 60 mph, then then it will take one hour to travel 60 miles. Regardless of how many lanes are on the highway, each car will still take one hour to travel that whole distance. Cars in the front and the back of each lane will take one hour. By the way, the reverse is true as well: increasing the speed of each car has no affect on how many you can fit side by side on any stretch of road.

# Answer
> 0 votes
Think of a bucket chain.

* The *bandwidth* is the number of buckets you pass along every minute (or second, or ...).
* The *propagation speed* is how long it takes to pass a bucket along the chain,
    + which is ${(number \\; of \\; buckets \\; in \\; the \\; chain) \over bandwidth}$.

---
Tags: computer-networks
---


# Question
Title: Given the alphabet $\{a, b, c\}$, how many words can we form with 4 letters?
*Question: Given the alphabet $\\{a, b, c\\}$, how many words can we form with 4 letters? And how many words can we form with up to 4 letters?*

I was thinking about the logic behind this and came up with this: perhaps the number of words that can be formed with 4 letters is $4^3 = 64$ words. Is that correct?

I could not think about how many words up to 4 letters, because that includes words with 1, 2 and 3 letters.

# Answer
Assume you have the alphabet $\\{A,B,C\\}$ and you want to form words of length 4.

For the first letter you have 3 choices, $A, B$ or $C$. For the second letter you have again 3 choices, $A,B$ or $C$ and so on. In total: $ 3 \cdot 3 \cdot 3 \cdot 3 = 3 ^ 4 = 81 $ possibilities.
> 3 votes

# Answer
Does not "with up to 4 letters" mean that we should count 1-letter, 2-letter, 3-letter, and 4-letter words? Then the answer is $3 + 3^2 + 3^3 + 3^4$.
> 2 votes

---
Tags: combinatorics, word-combinatorics
---


# Question
Title: How many bits to represent a quantity $\omega$ bounded in a particular way?
I'm working out some details to implement a division algorithm, I'm following the explanation given in this book (chapter 5) for who is interested.

Anyway I need to work out how many bits are necessary to represent a value $\omega$ bounded by

$$ | \omega | \leq \rho r^{k+1} y $$

where

$$ \begin{array}{l} \frac{1}{2} \< \rho \leq 1 \\ r = 2^l, \text{where $l\geq 1$ is some integer} \\ 0 \leq y \leq 2^{k} - 1, \text{ $k$ positive integer} \end{array} $$

My approach is finding the number of bits to represent $| \omega |$ and then adding one bit to represent the sign of $\omega$, in two complement.

There fore

$$ \left\lceil \log\_2(|\omega|) \right\rceil \leq \left\lceil \log\_2(\rho r^{k+1} y) \right\rceil = \left\lceil \log\_2(\rho) + (k+1)\log\_2 r + \log\_2(y) \right\rceil \leq \left\lceil (k+1)l + \log\_2(2^k-1))\right\rceil \leq \left\lceil (k+1)l + k \right\rceil = \left\lceil (k+1)(l+1) - 1 \right\rceil = (k+1)(l+1) - 1 $$

Therefore in two complement I would need a total of $(k+1)(l+1)$ bits to represent my value $\omega$.

Is this correct?

# Answer
Yes it's correct, but I would not introduce the rounding until the end. Let $w = |\omega|$, then in the worst case:

$$w \leq \rho r^{k+1}y$$

$$w \leq 1\cdot r^{k+1}y$$ $$w \leq (2^l)^{k+1}y$$ $$w \leq (2^l)^{k+1}(2^k-1)$$ $$\log\_2(w) \leq \log\_2((2^l)^{k+1}) + \log\_2(2^k-1)$$ $$\log\_2(w) \leq \log\_2(2^{l(k+1)}) + \log\_2(2^k)$$ $$\log\_2(w) \leq {l(k+1)} + k$$ $$\log\_2(w) \leq {(l+1)(k+1)} -1$$ $$\lceil\log\_2(w)\rceil \leq {(l+1)(k+1)} -1$$ $$\lceil\log\_2(w)\rceil \< {(l+1)(k+1)}$$
> 1 votes

---
Tags: arithmetic
---


# Question
Title: Inline caching in not object oriented languages
I've been recently studying inline caching as a technique to optimize method dispatch in object oriented languages. Basically, the idea is that one can remember what was previously dispatched and predict that things will go on in the same way.

My question is whether this technique has been used in pure functional languages (I'm a native of Scala which mixes both paradigms thus the uncertainty).

# Answer
As Gilles points out, it's not immediately obvious what the analogue of this would be in a non-object-oriented language. Below is one suggestion.

Let's say you have a function `h :: (A -> B) -> C` (this is using Haskell syntax). `h` is a higher order function and particularly it takes a function of type `A -> B`. The definition of `h` will be something like:

```
h f = ... (f a) ...

```

`h` doesn't know what `f` will be so it must emit code for a call to an unknown function. Of course, if `(h g)` occurs in the code where `g` is a known function, the compiler may choose to inline `h` and then further optimize the inlined body of `h` with `f` now known. This is just normal inlining. We could also imagine a similar variation where we make specialized versions of `h` for some finite collection of functions `A -> B` and call the appropriate specialized version rather than inlining. (For GHC Haskell, this occurs with type classes via the SPECIALIZE pragma.) Neither of these are inline caching, though you could imagine a "static" version of inline caching that adds the appropriate guards and branches to specialized code if possible and otherwise falls back to generic code. I don't believe this is a particularly common optimization whether a language is functional or not. It's similar to rearranging branches to improve branch prediction though.

On the other hand, this optimization and inline caching in OO languages will both happen automatically with a trace-based JIT compiler. If you view a first-class function as an object with a single method as many OO languages with higher order functions do, then inline caching will do this optimization. That said, there aren't that many functional languages with a JIT compiler (tracing or otherwise) based implementation, particularly for a JIT compiler specifically geared to the functional language. Two trace-based systems for functional languages described in the literature are Pycket for Racket, which is not a purely function language, and Lambdachine for Haskell. I'm not aware of any JIT compiler for a functional language that explicitly and specifically targeted this particular optimization.
> 3 votes

---
Tags: compilers, functional-programming, caching
---


# Question
Title: Creating a Grammar that is equivalent to "RegEx A, RegEx B, or BOTH"
I have the following problem, create a Grammar on the Language {1,0} that accepts

> "strings with a length divisible by 3, **or** strings with a number of 0s divisible by 3, **or** *BOTH*".

I created grammars for each part, but I'm not sure how to account for the "BOTH" clause.

I started by making a regular expression:

```
1*(01*01*01*)+|((0|1)(0|1)(0|1))+

```

Then I made the following Grammars for each of the two main parts:

```
1*(01*01*01*)+

```

becomes

```
S_1 -> 1F | F
F   -> 1F | 0G
G   -> 1G | 0H
H   -> 1H | 0M
M   -> F | (empty)

```

and

```
((0|1)(0|1)(0|1))+

```

becomes

```
S_2 -> 0C | 1C
C   -> 0D | 1D
D   -> 0E | 1E
E   -> S | (empty)

```

My question is, if I just use the central **or** in the regular expression and start the complete Grammar by branching to one of the two Grammars I made with no cross over\*, will it somehow potentially compromise the "**or** *BOTH*" requirement in some cases? Or is that extra requirement just a red herring and will be *necessarily* satisfied by covering both of the base requirements? As far as I can tell, both are more or less completely independent of one another.

\*ie just tack the two together with this at the start:

```
S -> S_1 | S_2
...

```

# Answer
> 2 votes
$S \to S\_1 | S\_2$

That is correct. A grammar doesn't care which derivation it used, or how many could have been used, as long as *at least one* derivation is valid.

Now if the question said *but not both*, then it would get complicated!

---
Tags: formal-grammars, regular-expressions
---


title: time complexity of word break algorithm

text:
# Question
Title: time complexity of word break algorithm
I found this question here but I don't think the answer is correct.

Here is the original word break question:

> Given a string s and a dictionary of words dict, add spaces in s to construct a sentence where each word is a valid dictionary word.
>
> Return all such possible sentences.
>
> For example, given s = "catsanddog", dict = \["cat", "cats", "and", "sand", "dog"\].
>
> A solution is \["cats and dog", "cat sand dog"\].

One way to do it is to use backtracking:

```
vector<string> wordBreak(string s, vector<string>& wordDict) {
    vector<string> sentences;
    string prefix = "";
    findWords(prefix, 0, s, wordDict, sentences);
    return sentences;
}

void findWords(string prefix, int start, const string s, const vector<string> &wordDict, vector<string> &sentences) {
    if (start == s.size()) {
        sentences.push_back(prefix);
        return;
    }
    for (int i = start; i < s.size(); i++) {
        string word = s.substr(start, i - start + 1);
        if (find(wordDict.begin(), wordDict.end(), word) != wordDict.end()) {
            string new_prefix = prefix == "" ? word : prefix + " " + word;
            findWords(new_prefix, i + 1, s, wordDict, sentences);
        }
    }
}

```

In the worst case, the dictionary contains all prefix of s. From my understanding, in this case, the time complexity is

```
T(n) = T(n-1) + T(n-2) + ... + T(1) = 2T(n-1) = O(2^n)

```

I'm not sure if this is correct because I see some threads say it is O(n^n)?

The other way is to use backtracking with memorization:

```
vector<string> wordBreak(string s, vector<string>& wordDict) {
    return constructSentences(0, s, wordDict);
}

// Return all sentences that can be constructed using substring s[start, ...]
vector<string> constructSentences(int start, const string s, const vector<string> &wordDict) {
    if (dict.count(start)) {
        return dict[start];
    }
    vector<string> sentences;
    if (start == s.size()) {
        sentences.push_back("");
        return sentences;
    }
    for (int i = start; i < s.size(); i++) {
        string word = s.substr(start, i - start + 1);
        if (find(wordDict.begin(), wordDict.end(), word) != wordDict.end()) {
            vector<string> subsentences = constructSentences(i + 1, s, wordDict);
            dict[i + 1] = subsentences;
            for (const auto elem : subsentences) {
                sentences.push_back(elem == "" ? word : word + " " + elem);
            }
        }
    }
    return sentences;
}

```

I'm not sure how to analyze the time complexity of this approach since some subproblem can be solved in constant time by dictionary lookup but some cannot.

Furthermore, I'm not sure how to analyze the space complexity of these two approaches. From my understanding, the space is bounded by the final output. Since we have O(2^n) final sentence and each sentence have size O(n), does it mean the space complexity for both approach is O(2^n * n) ?

# Answer
> 1 votes
If there is one string x that can be parsed in two ways then repeating x n times can be parsed in at least $2^n$ ways. So the problem has either 0, 1, or an exponential number of solutions. Asking for all is likely pointless.

However, you could provide an answer with many solutions in a much more compact format. Say your input is "catsanddog" repeated 100 times with $2^{100}$ solution, clearly infeasible. Instead we present a solution like this: "word1 word2 word3" if a solution consists of these three words. \[solution1 | solution2 | solution3\] if there are say three alternatives. And everything concatenated. So the solution in the case above would be written as \["cats and dog" | "cat sand dog"\] repeated 100 times.

In practice, this will usually give a solution with size cN for a not very large c, where N is the input size. You can still have extremes. Take the dictionary \["a", "aa"\] and a string of n a's as input. The first few solutions are:

```
"a": "a"
"aa": ["a a" | "aa"]
"aaa": ["a aa" | ["a a" | "aa"] "a"]
"aaaa": [["a a" | "aa"] "aa" | ["a aa" | ["a a" | "aa"] "a"] "a"]

```

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


# Question
Title: Confirmation of Dijsktra application explanation
Please can someone confirm that my description of the application of Dijkstra's algorithm is correct for this graph?

```
    1   3
 A -- B -- C
  \      /
 2 \    / 1
    \  /
     D

Step   Current Node

                       B        C        D
1      A               1(A)     -        2(A)
2      B               1(A)     4(B)     2(A)
3      D               1(A)     3(D)     2(A)
4      C               1(A)     3(D)     2(A)

```

Description:

1. Tentative distances to `B` and `D` determined. `C` not yet visible.
2. Shortest distance from previous step taken. No new information on shortest path to `B`. Tentative distance to `C` now known. No new information on `D`.
3. We choose to backtrack to `A`, and then move to `D` because the distance to `D` (2) is smaller than that to `C` (4). We update the tentative distance to `C` because via `D` it is shorter than via `B`.
4. We choose to move to `C` directly from `D` because it is shorter (3) than backtracking and going via `A` (4). Moving to `C` gives us no new shorter distances. All nodes visited, so end.

# Answer
> 1 votes
It's more traditional to describe dijkstra with the open and closed sets:

You start with an empty closed set and an open set containing $ \\{ (A,0) \\}$

You select the node with the lowest cost and remove it from the open set, then you expand the neighbours and add them to the open set $ \\{ \\{B,1\\} \\{D,2\\} \\}$ or update the elements in the open set and Add the selected node to the closed set

step1:
open = $ \\{ (B,1, A), (D,2, A) \\}$
closed = $\\{(A)\\}$

step2:
open = $ \\{ (C,4, B), (D,2, A) \\}$
closed = $\\{(A),(B,A)\\}$

step3:
open = $ \\{ (C,3, D) \\}$
closed = $\\{(A),(B,A),(D,A)\\}$

There is no actual sense of "backtracking" because you are considering all the open nodes in parallel.

Many other search algorithms work in the same way with the only difference in how a node is selected from the open set. Breadth-first takes the oldest node in the set, depth-first takes the youngest, Dijkstra takes the node with the lowest cost, A\* takes the node with the lowest cost+heuristic.

---
Tags: shortest-path
---


# Question
Title: How can, e.g., Dijkstra find all shortest paths in linear time?
As I understand one can modify BFS for unweighted graph or Dijakstra for weighted graph to find all possible shortest paths from $s$ to $t$ in linear time. But how can this be, when there are $O(2^n)$ such paths? What am I missing here?

# Answer
> 2 votes
As you (almost) observe, there can be $2^{\Theta(n)}$ shortest paths between a pair of vertices:

```
       *   *           *
      / \ / \ /     \ / \
    s*   *   *  ...  *   *t
      \ / \ /       / \ /
       *   *           *

```

With $k$ cycles, this graph has $3k+1$ vertices and there are $2^k = 2^{n/3-1}$ shortest $s$–$t$ paths: you can go clockwise or anticlockwise around each cycle, independently of the others.

The simple answer to your question is that you are mistaken. It is impossible for any algorithm to output all shortest paths in linear time (time $O(n)$), just because it is impossible to output an exponential amount of data in a polynomial number of steps: a Turing machine can only write one character of output per step.

Outputting all shortest paths is an example of an enumeration problem. Typically, we use different measures for these problems because it seems "unfair" to say that an algorithm is slow just because it has a lot of work to do. The usual standard for enumeration algorithms is to look at the number of steps between each successive output. Using modified Dijkstra will (I assume) have polynomial delay: there's a constant $c$ such that, for any large enough graph on $n$ vertices, the algorithm will output some shortest path after at most $n^c$ steps and, after each output, there will be at most $n^c$ more steps before the algorithm outputs another shortest path or terminates.

---
Tags: algorithms, complexity-theory, graphs, time-complexity
---


# Question
Title: Mapping many transition functions into two transition functions
Continuing from this answer: https://cs.stackexchange.com/a/56072/43035

I don't understand how it's possible to map many transition functions $\delta\_1,...,\delta\_n$ of a NDTM into just two transition functions $\delta\_0',\delta\_1'$. How will conflicts be handled?

For example: $\delta\_1(q\_1, a) = (q\_2, b, R)\\ \delta\_2(q\_1, a) = (q\_3, c, L)\\ \delta\_3(q\_1, a) = (q\_4, d, R)$

How can you map $\delta\_3$?

# Answer
> 4 votes
Suppose that you have three options $o\_1,o\_2,o\_3$.

You first guess whether to apply $o\_1$ or not; if not, you stay in place.

If you didn't apply $o\_1$, you guess whether to apply $o\_2$ or $o\_3$.

Here is how to implement it using transitions, using your example: $$ \begin{align\*} &\delta\_1(q\_1,a) = (q\_2,b,R) \\ &\delta\_2(q\_1,a) = (q\_s,a,R) \\ &\delta\_1(q\_s,\sigma) = (q\_t,\sigma,L) \\ &\delta\_2(q\_s,\sigma) = (q\_t,\sigma,L) \\ &\delta\_1(q\_t,a) = (q\_3,c,L) \\ &\delta\_2(q\_t,a) = (q\_4,d,R) \end{align\*} $$ Here $q\_s,q\_t$ are new states, and $\sigma$ is any tape symbol.

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


# Question
Title: Prove the time complexity of this algorithm of finding longest subarray with maximum value in the middle
I'm trying to find time complexity $T(n)$ of the algorithm by a given pseudocode:

```
1: for i:=1 to N do
2: begin
3:   len := 1
4:   while i - len >= 1 and i + len <= N do
5:   begin
6:     if a[i] > a[i - len] and a[i] > a[i + len] then
7:       len := len + 1
8:     else
9:       break
10:   end
11:   print(i, len)
12: end

```

I know that the answer is $T(n) = O(n\log n)$ but I struggle to prove that.

From the pseudocode its clear that this algorithm is designed to find the longest subarray with each element smaller then the middle one. (actually this algorithm prints the length of such array for each array element)

I can't prove it formally because I struggle with the content-dependent loop at 5-10, but informally I went like this: Lets construct the array which will be the worst case for this algorithm.

For the sake of simplicity lets use array with 15 elements and start with array filled with zeros: $$0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0$$ external loop will execute 15 times and each time the loop 5-10 will perform a single comparison Now we will do the following: we divide array in two and put maximum value in the middle. Then for each half we will do the same, except the value will be decresed by 1.

We will get the following array: $$0, 1, 0, 2, 0, 1, 0, 3, 0, 1, 0, 2, 0, 1, 0$$

Now, intuitively I can see why this is the worst case for the algorithm and where $logn$ comes from, but I can't prove it properly.

As a side note I would appreciate any pointers toward where one can practice these kind of problems (concrete algorithms time complexity analysis, preferably with answers/explanations)

# Answer
> 1 votes
Let an array $a\[1\],\ldots,a\[n\]$ be given. For an index $i$, let $\ell(i)$ be the largest $\ell$ such that $\\{i-\ell,\ldots,i+\ell\\} \subseteq \\{1,\ldots,n\\}$ and $a\[i\]$ is larger than all elements $a\[i-\ell\],\ldots,a\[i-1\],a\[i+1\],a\[i+\ell\]$. It is not difficult to see that the running time of the algorithm on the array is $\Theta(n + \sum\_{i=1}^n \ell(i))$.

This prompts the following definition:

> Given $n$, the quantity $M(n)$ is the maximum of $\sum\_{i=1}^n \ell(i)$ over all arrays of length $n$.

Let $a$ be an array for which $M(n)$ is achieved, and let $a\[i\]$ be an element of maximum value. Then $\ell(i) = \min(i-1,n-i)$. Moreover, since $a\[i\]$ is not smaller than any other element, we have $\sum\_{j=1}^{i-1} \ell(j) \leq M(i-1)$ and $\sum\_{j=i+1}^n \ell(j) \leq M(n-i)$. This shows that $$ M(n) \leq \max\_{i=1}^n M(i-1) + M(n-i) + \min(i-1,n-i). $$ In fact it is not hard to check that equality holds: take the maximum $i$, and combine two arrays attaining $M(i-1)$ and $M(n-i)$ with a larger element in the middle. This gives the recurrence $$ M(0)=0, \\; M(n) = \max\_{i=1}^n \[M(i-1) + M(n-i) + \min(i-1,n-i)\]. $$ This recurrence is A078903. It is intuitively clear that the best choice for $i$ is $\lfloor \frac{n+1}{2} \rfloor$ or $\lceil \frac{n+1}{2} \rceil$.

We can solve the recurrence explicitly: for $0 \leq k \< 2^m$, we have $$ M(2^m+k) = (m-2)2^{m-1}+1+N\_2(k), $$ where $N\_2(k)$ is the total number of 1s in the binary expansions of $1,\ldots,k$ (this is A000788). It is known that $N\_2(k) = k\log\_2 k + O(k)$, and so $M(n) = \Theta(n\log n)$. This asymptotic estimate also follows from the monotonicity of $M(n)$, by considering the cases $k = 0$.

We conclude that the running time of the algorithm is indeed $O(n\log n)$, and moreover this estimate is tight.

---
Tags: algorithms, complexity-theory, algorithm-analysis, time-complexity
---


# Question
Title: Why doesn't this quine-less language contradict Kleene's recursion theorem?
Kleene's recursion theorem implies that every Turing complete programming language that satisfies certain properties have quines. This website claims that this is incorrect, and that there is a Turing complete without a quine.

I give a slightly simplified version of what they gave. Start with a Turing complete programming language $P$. Create a programming language $P'$ that is interpreted according to the following rules:

* Try running the program according to the rules for $P$
* If the input was empty, and if it outputs it own source code and then would terminate according to the rules of $P$, throw an error instead. We'll call this error a "quine error".

For example, $Python'$ is like $Python$, except that when given no input, if the program outputs its own source, it will throw a quine error instead of terminating normally.

What is the resolution to this apparent paradox?

# Answer
> 3 votes
The recursion theorem only applies to admissible programming languages. A programming language $P$ is admissible if it satisfies the following three properties, with respect to some reference programming language $U$:

1. The problem of simulating a $P$-program on an input $x$ is r.e.
2. There is a computable transformation $f$ which, given a $P$-program, outputs an equivalent $U$-program.
3. There is a computable transformation $g$ which, given a $U$-program, outputs an equivalent $P$-program.

In your case the first two properties hold, so the third must fail. You can try to implement $g$ by "compiling" a $U$-program to a $P$-program, but this compilation would fail if the resulting program attempts to print its own source code. The recursion theorem shows that there is no way around this problem.

---
Tags: fixed-point
---


# Question
Title: What would you get if you add parameters to context free grammars?
I was thinking of grammars for indendation-sensitive languages and it looks like CF grammars would do the trick if combined with parameters. As an example, consider this fragment for simplified Python grammar in ANTLR-like format:

```
// on top-level the statements have empty indent
program
    : statement('')+
    ;

// let's consider only one compound statement and one simple statement for now
statement(indent)
    : ifStatement(indent)
    | passStatement(indent)
    ;

passStatement(indent)
    : indent 'pass' NEWLINE
    ;

// statements under if must have current indent plus 4 spaces
ifStatement(indent)
    : indent 'if' expression ':' NEWLINE (statement(indent '    ')+)
    ;

```

My question: Does this kind of grammars (CFG with parameters) have a name?

It looks that it wouldn't be hard to write a recursive descent parser for this grammar (parameters should be basically parsers). What could be the difficulties with this approach?

Does addition of parameters raise the supported language class above context-free?

# Answer
Affix grammars (parameterised context-free grammars) were studied extensively by the eminent Dutch computer scientist Cornelis HA Koster, starting with his 1962 paper "Basic English, a generative grammar for a part of English", co-written with LGLT Meertens. In 1970, he produced a formalism of the concept; a useful overview is available in his 1971 paper "Affix Grammars for Programming Languages", a version of which I found on Citeseer.

In that paper, Koster compares his formalism (and another similar one) with Van Wijngaarden two-level grammars, and finds them to be very similar.

Dick Grune's invaluable annotated bibliography of parsing techniques includes a large number of other useful references for affix grammars and other non-Chomskyian formalisms. (See section 18.2.6 of the bibliography, although there are useful papers in other sections.) Grune covers affix grammars briefly in §15.3.2 of the second edition of Parsing Techniques: A Practical Guide (and even more briefly in the first edition, available online) mentioning the fact that it is easy to adapt top-down (and other) parsing techniques.

Unless the domain of parameters is finite, in which case they can be removed by statically generating all possible productions resulting in a CFG, the class of affix grammars is certainly a strict superset of the set of context-free grammars. (An affix grammar for $a^n b^n c^n$ can be found in Dick Grune's *Parsing Techniques* reference above.)

Koster, who was also an editor of the Algol 68 report, was the original developer of the Compiler Description Language (CDL), based on his ideas about affix grammars. This toolkit and its later derivatives were used in production for many years. This page, which I found with a Google search and whose permanence I cannot guarantee, has links to the manual and download site for CDL3.
> 15 votes

# Answer
Take the pumping lemma for CFGs:

Take the grammar

```
S -> A("")
A(p) -> p
      | p '\n' A(p"*") '\n' p

```

This describes a star triangle:

```
*
**
***
**
*

```

There is no way to split a star triangle up in 5 parts $uvwxy$ such that $\\{uv^nwx^ny|n\>0\\} $ is also a star triangle (with $vx$ non empty).

This means that the star triangle is not a context free language.

Or a simpler example:

```
S-> B("")
B(p)-> p 'a' p 'a' p
     | B(p 'b')

```

This describes the language $\\{b^nab^nab^n | n\ge0 \\}$ which is not context free.
> 6 votes

# Answer
I've never seen this formalism presented (even in something like Grune's *Parsing Techniques*), depending on the details on how you define exactly "parameters should be basically parsers" it looks mappable to van Wijngaarden two level grammars, which have the same power as unrestricted phase structure grammar (i.e. more powerful than context sensitive, you could write a VW grammar which gives all halting programs).
> 3 votes

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


# Question
Title: Algorithm to find if exists a k-length acyclic path with negative weight on an weighted undirected graph
Consider the following problem: given an undirected graph with weighted edges (positive and negative) I would like to know if there is a k-length acyclic path with negative weight. Is there an algorithm for that with a good complexity? Maybe I can find the lighter k-length acyclic path and check if is negative, but it could be that this approach may have a bigger complexity. Let me know what do you think.

(Sorry for the lousy english)

# Answer
If $k$ is part of the input to the algorithm (as opposed to a constant chosen ahead of time), and if "acyclic path" means a path that does not visit any vertex more than once, then this problem is already at least as hard as Hamiltonian Path, which is NP-hard: to reduce the latter to this problem, just give every edge some negative weight (e.g., -1) and set $k=n−1$.
> 1 votes

---
Tags: algorithms, complexity-theory, graphs
---


# Question
Title: Info about dataset from which a Huffman tree was generated
I know that given the following huffman tree:

you can say that C occurs most in the dataset from which it was generated and D and B occur the least. Can you also say that the left most leaf on a level has a occurence that is greater than or equal to the rightmost?

# Answer
> 1 votes
My claim was not true. I've found counterexample on mathworld. If you look on the 4th level, you will see that 5th element is not in the correct position (if my statement were to be true).

---
Tags: binary-trees, huffman-coding
---


title: Vertical sticks challenge explanation

text:
# Question
Title: Vertical sticks challenge explanation
This is a question based on this one

I've also tried this problem but I can't seem to understand Henry's solution to it.

Why is the average distance between the sticks $(n+1) / (k+1)$ and not $n/ k$

# Answer
> 2 votes
Let me first repeat the setting. There are $k$ sticks, one of them distinguished. We randomly choose $k$ different positions for them from $1,\ldots,n$, and put a special stick at $0$. How far to the left of the distinguished stick is the closest stick?

The trick here is to observe that we obtain the same distribution if we first choose positions for the sticks and then permute the $k$ sticks (without changing the set of $k$ positions). This is equivalent to choosing the $k$ positions and then choosing one of the sticks at random as the distinguished one. If the positions are $i\_1 \< \cdots \< i\_k$, the average distance to the left is $$\frac{(i\_1 - 0) + (i\_2 - i\_1) + \cdots + (i\_k - i\_{k-1})}{k} = \frac{i\_k}{k}. $$ Therefore the average distance to the left is $\mathbb{E}\[i\_k\]/k$.

It remains to compute the average position of the maximum of $k$ distinct random positions. There is probably a smart way of doing that; here is a brute force calculation. The number of choices in which the maximum is $\ell$ is exactly $\binom{\ell-1}{k-1}$. Hence the average is $$ \frac{1}{\binom{n}{k}} \sum\_{\ell=k}^n \ell \binom{\ell-1}{k-1} = \frac{k}{\binom{n}{k}} \sum\_{\ell=k}^n \binom{\ell}{k} = \frac{k}{\binom{n}{k}} \binom{n+1}{k+1} = \frac{k(n+1)}{k+1}. $$ Overall, we get that the average distance to the left is $$ \frac{1}{k} \cdot \frac{k(n+1)}{k+1} = \frac{n+1}{k+1}. $$

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


title: Balanced Distribution Of Items

text:
# Question
Title: Balanced Distribution Of Items
I shall call this the "Curtain Hook" problem.

Please excuse my lack of formal maths notation as it has been over 20 years since I have needed it.

A standard pencil pleat curtain has L number of loops on the back (evenly spaced along the width) with which to hang the curtain. The curtain pole will come with H number of hoops to hang the curtain upon.
The problem is how to distribute - with as uniform as possible gaps between - the hooks across the loops.

For example, if I have 15 hooks (per curtain) and each curtain has 38 loops where should I hang the 15 hooks?

By hand I came up with:
HoHooHooHooHoHooHooHoHooHooHoHooHooHoH
Which is not evenly spaced. (H being a hook, o being an unused loop)

Is there an evenly balanced solution for this combination?
Is there an algorithm that can be used to describe where to place the hooks evenly?

Ps. Not homework, just someone with a curious analytical mind who had to put up some curtains recently. I was thinking of creating a web page to help others if a general solution/algorithm could be found.

Thanks

Craig

# Answer
> 1 votes
You haven't quite defined your problem, so let me answer a more concrete one: when can there be an evenly spaced solution. I assume that by "evenly spaced" you mean that all the spaces are the same, and that there must be hooks and the first and last positions. If the space is $s$, then we must have $$ L = 1 + (s+1)(H-1), $$ since the string is of the form $H(o^sH)^{H-1}$. This is possible if and only if $H-1$ divides $L-1$, in which case the spacing is $$ s = \frac{L-1}{H-1} - 1. $$ In your case, 14 doesn't divide 37, so an even spacing is impossible.

---
Tags: algorithms
---


title: Prove that $BPP^{BPP} = BPP$

text:
# Question
Title: Prove that $BPP^{BPP} = BPP$
> Prove that $BPP^{BPP} = BPP$.

Obviously $BPP\subseteq BPP^{BPP}$. So we're left with proving $BPP^{BPP} \subseteq BPP$. Let's consider $L\in BPP^{BPP}$. Then, there's a PTM $M$ to decide $L$ for some $BPP(\alpha, \beta)$ which uses an oracle for some language $O\in BPP$. $O$ also has a $PTM\in BPP$, let's denote it $M\_o$. So we could create $M'$, a PTM which behaves exactly as $M$, but everytime $M$ uses the oracle, it simulate $M\_o$ on the given input for the oracle.

Now, I want to show that $M\in BPP$. By definition, $BPP=BPP(1/3, 1/3)$, so every time $M$ calls $M\_o$ it takes a probabilistic risk basing a deciion upon $M\_o$ answer.

We've learned in class that $BPP = BPP(1/3, 1,3) = BPP\left(\frac{1}{3^n}, \frac{1}{3^n} \right)$ and I think I shall explain that even though $M\_o$ may return false answers, $M\_o$ is still in $BPP$.

Can you help me with doing that?

Thanks

**EDIT:**
Basically, I want to give a lower bound for the probability of $M$, answering correctly. Let's assume that $M$ queries the oracle $n^c$ times for some $n\in\mathbb{N}$. I think the lower bound is $\frac{1}{3^{n^c}}$.

My explanation is that we're assuming the worst case. That is, if the oracle is returning a false answer then we are returning a false answer.

Is that right?

**EDIT2**
I'm not sure it's $100\\%$ correct, since I didn't take into account the probabilistic behavior of $M$ itself.

# Answer
Here's a sketch: you seem to be on the right track. Let $L\in BPP^{BPP}$ be decided by a BPP machine $M$ that makes queries to an oracle $A\in BPP$ decided by a $BPP$ machine $M'$. Let $E$ be the error for $M$, $E'$ the error for $M'$ (that is, the probability that the BPP machines fail is at most $E, E'$). We will choose $E, E'$ appropriately via error reduction.

Now, fix a string $z$ to use as randomness for all queries to $M'$. There are at most polynomially many queries to $M'$, say at most $|x|^k$, since $M$ is a ppt TM. Thus, $$\operatorname{Pr}\[\text{an error occurs in some query to } M'\]\le |x|^k\cdot E'$$ So the overall probability of error by $M$ in deciding $L$ is at most $|x|^k\cdot E' + E$, so if we choose $E=\frac{1}{6}$ and $E'=\frac{1}{6|x|^k}$ (which we may do by the standard BPP error reduction), we get an overall probability of error $\le\frac{1}{3}$, so the procedure described is a $BPP^P\subseteq BPP$ procedure.

By the same proof we have the more general statement that $BPP^{BPP^A}\subseteq BPP^A$.
> 2 votes

---
Tags: complexity-theory
---


# Question
Title: Maximum size of Huffman codes for an alphabet containing 256 letters
I made a Huffman algorithm for data compression: it takes the content of a file as an input and outputs a compressed string. More important, it generates optimal prefix codes (made of 0 and 1) for every possible character, that is to say for every number between 0 and 255.

While the size of a code cannot exceed 256, it is possible to encode every character with a code of size 8 at most.

However, it is impossible that the algorithm generates a code of size 256 because then the codes wouldn't be optimal. It will give to the most likely chars, codes of size \< 8 and it will give codes of size \> 8 to the others (intuitively).

My question thus is, how can we get an upper bound of the maximum size a code can have, better than 256? I don't see how to approach the problem.

PS: the upper bound I'm looking for doesn't depend on the probability distribution. It has to be an upper bound for every possible probability distribution. As I said, I doubt that there is a probability distribution for which there is a code of size 256, so there has to be an upper bound.

I think I found the solution: For an alphabet of size $n$, the longest possible code is of size $n-1$, so here the answer is 255. So I was actually wrong in my intuition. You just need to arrange the weights so that each one is at least twice as much as the precedent and you get a Huffman tree which outputs a code of maximal size.

# Answer
> I don't see how to approach the problem.

OK, here is how you can approach the problem. Can you solve this problem if you replace the number 256 with the number 3? How about 4? 5? Try solving those special cases, then see if you spot a pattern...

This is a useful, general pattern. When a problem is too hard, try to find a simpler version of it and think about that. When you see a constant in the problem, try solving simpler versions where the constant is smaller (so the problem becomes easier to think about), then look for a pattern, try to generalize, form a hypothesis, and see if you can prove your hypothesis.
> 8 votes

# Answer
The maximum possible code size for a 256 symbol alphabet is 256 bits. Consider the case when the most frequent symbol has frequency 1/2, the next most frequent symbol has frequency 1/4, then 1/8 ....

This get encoded as:

```
1
01
001
0001
...
<255 0 bits>1

```
> 3 votes

# Answer
In theory, 256 characters can have probabilities $2^{-1}$, $2^{-2}$, ..., $2^{-255}$, $2^{-255}$ (yes, the last one is $2^{-255}$, not $2^{-256}$), so there could be two codes of 255 bits.

In practice, if you compress let's say a document of 1 Gigabyte, no character can have a probability less than $2^{-30}$, so the maximum length would be 30 bits.

And again in practice, you can make a decoder faster if it has a limited maximum number of bits, say 14. That's called "length limited Huffman codes". There's a rather complicated algorithm that can be given the maximum length l of any code that you want to achieve (obviously ≥ 8 for 256 codes), and it will calculate the optimal codes under that restriction. Obviously not optimal globally, but usually very close, if you limit the length to 14 bits, for example.
> 3 votes

# Answer
The maximum size of the code should be the size of the code for the least probable symbol.

PS: The above answer was before the question was clarified, and is still accurate for any one probability distribution. CWallach's answer describes a probability distribution that results in the longest code of any possible probability distribution.

The key is the resulting Huffman tree has to be as unbalanced as possible. This happens when every internal node generated has a probability less than or equal to the lowest probability leaf node in the queue.
> 0 votes

---
Tags: huffman-coding
---


# Question
Title: Create an order from several incomplete orders
Here is the motivation and how it should behave, but I need a help how to implement it.

I have several (typically) incomplete orders given as ordered values, for ex.:
1. A, C, D
2. D, E
3. X, B
4. B, C
5. C, F
6. C, A

and the resulting order should be: A, X, B, C, D, E, F or A, X, B, C, F, D, E or A, X, B, C, D, F, E

The idea behind it is sort the result based on first seen order. I will try explain it on the example in steps:
order A, C, D
D, E - D seen, so add E after D, so order A, C, D, E
X, B - no value seen yet, so we can not determine the order now, so create 2nd temporary order X, B
B, C - C already seen, so order A, B, C, D, E
and 2nd order can be merged via B, so A, X, B, C, D, E
C, F - C see, so order A, X, B, C, D, E, F
C, A - ignore, both values are part of already defined order (by first incomplete order A, C, D)

But what if an additional incomplete order F, D or F, E will be part (added to the end) of the input? The step-by-step mental algorithm will fail - F was already placed.

How can the idea be implemented, any idea?

# Answer
I will answer the following question:

> Given a list of partial orders, how can we find a total order compatible with all of them, if any?

Form a directed graph on the ground set by putting an edge $a \to b$ if $a$ immediately precedes $b$ in one of the partial orders. If this graph contains any directed cycles, then there is no solution. Otherwise, we can find a solution by performing a topological sort.
> 3 votes

---
Tags: algorithms
---